Enumeration of Lambda-Expressions.

(setf [println.supressed] true [print.supressed] true) (load "http://instprog.com//Instprog.default-library.lsp") (setf [println.supressed] nil [print.supressed] nil) ; The lambda-expressions are defined on following way: ; ; (a) a, b, c, ... are lambda-expressions. These lambda expressions ;     are named "variables". ; ; (b) if X is variable and E is lambda-expression, then ; ;                            (^ X . E) ; ;     is lambda-expression as well. These lambda-expressions are ;     named "functions". ; ; (c) if E and F are lambda-expressions, then (E F) is lambda- ;     expression as well. These lambda expressions are named ;     "applications." ; ; Using functions for Cantor's enumeration developed in last few ; posts, now in my library, I'll define functions for enumeration ; of all lambda-expressions, i.e. bijective function ; ;                    lam: N -> all lambda-exprsions ; ; Enumerations of variables, functions, and applications will be ; defined independently. ; ;       var1, var2, ..., varn, ... ;       fun1, fun2, ..., funn, ... ;       app1, app2, ..., appn, ... ; ; After that, all lambda expressions will be enumerated on following ; way: ; ;       var1, fun1, app1, var2, fun2, app2, ... ; ;--------------------------------------------------------------- ; ; First - enumeration of variables; and inverse enumeration. ; ; If alphabet is, for example, "xyz", I'll enumerate variables ; on following way: ; ;       x, y, z, x1, y1, z1, x2, y2, z2 ... ; ; It slightly complicates enumeration, but it looks better than ; ;       x0, y0, z0, x1, y1, ... (setf var (lambda(n alphabet)              (letn((l (length alphabet))                    (first-char (alphabet (% (- n 1) l)))                    (rest-chars (let((n1 (/ (- n 1) l)))                                (if (= n1 0) "" (string n1)))))                   (sym (append first-char rest-chars)))))                                     (setf var-inverse (lambda(v alphabet)                      (letn((l (length alphabet))                            (first-char (first (string v)))                            (rest-chars (rest (string v))))                           (when (= rest-chars "")                                 (setf rest-chars "0"))                           (+ (* (int rest-chars) l)                              (find first-char alphabet) 1)))) ; ;--------------------------------------------------------------- ; ; Second, enumeration of functions - and inverse enumeration. ; ; Every function has form (^ <var> <lambda-expression>), where ; any variable and lambda-expression is allowed. All pairs of ; variables and lambda-expressions can be enumerated using ; Cantor's enumeration: (setf fun (lambda(n alphabet)              (list '^                    (var (cantors-row n) alphabet)                    '.                    (lam (cantors-column n) alphabet))))                          (setf fun-inverse   (lambda(f alphabet)      (cantors-enumeration-inverse (var-inverse (f 1) alphabet)                                   (lam-inverse (f 3) alphabet)))) ; ;--------------------------------------------------------------- ; ; Third, enumeration of applications - and inverse enumeration. ; ; Every application has form (<lambda-expression1> <lambda-expression2>), ; For enumeration of pairs of lambda-expressions, we need Cantors ; enumeration again. (setf app (lambda(n alphabet)             (list (lam (cantors-row n) alphabet)                   (lam (cantors-column n) alphabet))))                    (setf app-inverse   (lambda(a alphabet)     (cantors-enumeration-inverse (lam-inverse (first a) alphabet)                                  (lam-inverse (last a) alphabet)))) ; ;--------------------------------------------------------------- ; ; Finally, enumeration of lambda expressions - and inverse enumeration: (setf lam (lambda(n alphabet)             (letn((n1 (- n 1))                   (row (+ (% n1 3) 1))                   (column (+ (/ n1 3) 1)))               (case row (1 (var column alphabet))                         (2 (fun column alphabet))                         (3 (app column alphabet)))))) ; For lam-inverse, I need few helper predicates: (setf var? (lambda(l)(symbol? l)))    (setf fun? (lambda(l)(and (list? l) (= (length l) 4)))) (setf app? (lambda(l)(and (list? l) (= (length l) 2)))) (setf lam-inverse       (lambda(l alphabet)          (local(row column)            (cond ((var? l)(setf row 1)                           (setf column (var-inverse l alphabet)))                  ((fun? l)(setf row 2)                           (setf column (fun-inverse l alphabet)))                  ((app? l)(setf row 3)                           (setf column (app-inverse l alphabet))))             (+ (* 3 (- column 1)) row)))) ;--------------------------------------------------------------- ; ;                          TEST (for(i1 1 10)   (letn((i2 (lam i1 "xyz"))        (i3 (lam-inverse i2 "xyz")))        (println i1 " -> " i2 " => " i3))) ; Here is output - ten nice lambda expressions ; 1 -> x => 1 ; 2 -> (^ x . x) => 2 ; 3 -> (x x) => 3 ; 4 -> y => 4 ; 5 -> (^ x . (^ x . x)) => 5 ; 6 -> (x (^ x . x)) => 6 ; 7 -> z => 7 ; 8 -> (^ y . x) => 8 ; 9 -> ((^ x . x) x) => 9 ; 10 -> x1 => 10 ; ; In case you like these, here is one million lambda-expressions. ; ; ; (set 'out-file (open "C://lambda-expressions.txt" "write")) ; (for(i1 1 1000000) ;   (letn((i2 (lam i1 "xyz")) ;         (i3 (append (string i1) ".  " (string i2)))) ;        (write-line out-file i3))) ; (close out-file) ; (exit)