### Some differences between lambda-calculus and Lisp (1).

 ;                        0. Introduction ; ; ; At the first sight, Lisp dialects appear like extensions of the ; lambda-calculus. Syntax of the two is especially similar. For ; instance, ; ;                          ((^ x . x) y) ; ; in lambda-calculus is very similar to ; ;                         ((lambda(x)x) y) ; ; in Lisp. However, it turns that there are many important ; differences between lambda-calculus and Lisp, some of these ; are obvious, and others are quite subtle. In this post, I'll ; list and comment few of these I've find to be interesting and ; important. The post is not tutorial on lambda-calculus, but ; another view that might be interesting to those who already ; know lambda-calculus, but maybe also - to some extent - to those ; who do not know it yet. ; ; ; ;        1. The notion of lambda-expression ; ; ; There is significant difference even in basic terminology. ; For instance, this is definition of lambda-expression in Common ; Lisp Hyperspec: ; ;    "lambda expression n. a list which can be used in place of a ;     function name in certain contexts to denote a function by ;     directly describing its behavior rather than indirectly by ;     referring to the name of an established function; its name ;     derives from the fact that its first element is the symbol ;     lambda." ; ; In lambda-calculus, lambda-expression is the name used for ; all allowed expressions of lambda-calculus. According to definition, ; lambda expressions are: ; ;       1. variables: a, b, c, d ... a1, a2, ... ;       2. functions: (^ v . F), where v is any variable, F any lambda-expr. ;       3. applications: (E F), where E and F are lambda-expressions. ; ; This difference, although not essential is very confusing one. ; ; ; ;                 2. Evaluation vs. reduction ; ; ; In Lisp, expressions are "evaluated." For instance, ; ;            ((lambda(x)x) y) => value of y. ; ; In lambda-calculus, expressions are "reduced". Reduction ; doesn't require replacement of the variables with values, so ; ;                   ((^ x . x) y) => y ; ; and not ; ;                   ((^ x . x) y) => value of y. ; ; If we remember high school math, some of the exercises were of ; the form "simplify" or "expand", and didn't required knowledge ; about value of the variables to be solved. ; ;           (x+1)^2 -1 ==> (x^2+2x+1) -1 = x(x+2) ; ; Other group of exercises clearly required evaluation: ; ;       "Find the area of the rhomboid with sides ;        a=4, b=3, and angle of 30° between them." ; ; ; ;       3. Recursiveness of evaluation in Lisp ;                                 vs. ;           non-recursiveness of beta-reduction ;                     in lambda-calculus ; ; ; There are three reductions in lambda-calculus; only short ; resume here - formal definition find somewhere else. ; ;     1. Beta-reduction: the application of the function ;   ;                ((^x.x) a) => a, ;                ((^x.(x x)) a) => (a a). ;   ;     2. Alpha-reduction: renaming of the bounded variables ;       ;                (^x.x) => (^y.y). ;       ;     3. Eta-reduction: elimination of the redundant function ;       ;                (^x.((^y.y)x)) => (^y.y). ;       ;        (eta-reduction is not essential; it can be replaced ;         with other two.) ; ; Beta-reduction is very similar to function application ; in Lisp. However, there are significant differences. ; ; ; In Lisp, evaluation of the function application, for instance, ; ;                  ((lambda(x)(x x)) (a b)) ; ; is performed on the following way: ;     ;    - argument (here (a b)) is evaluated; ;    - result is assigned to the parameter (here x), and ;    - body of the function, (here (x x)) is evaluated. ;    - the result is returned as the result of  evaluation of ;      whole expression. ; ; ; In lambda-calculus, beta-reduction of the application, ; for instance, ; ;                    ((^x.(x x)) (a b)) ; ; is performed on a following way: ; ;     - argument (here (a b)) is substituted for parameter (here x) ;       in the body of the function (here (x x)). ;     - the result of the substitution is result of beta-reduction. ; ; The result of the two is significantly different. ; ;     Note that beta reduction does significantly less than ;     evaluation. Beta-reduction doesn't apply itself recursively ;     on y and on (x x), while evaluation in Lisp does - it requires ;     evaluation of ; ; ; ;      3.1. Example: Church's lambda in Newlisp ; ; ; I'll use previous discussion to define ; ;                        lambda-Church ;     ; in Newlisp, so expressions using it are evaluated just like ; lambda-expressions are beta reduced in lambda-calculus. For ; instance, I want ; ;                   ((lambda-Church (x) (x x)) (a b)) ; ; to evalute to ; ;                      ((a b)(a b)). ; ; What should I do? In Newlisp, because it has fexprs, its easy. ; Expression ; ;                     (lambda-Church (x) (x x)) ; ; should be evaluated to ; ;               (lambda-macro(x)(expand (quote (x x)) ;                                       (quote x))) ; ; and that's all. (define-macro (lambda-Church head body)   (let ((var (first head)))      (expand (lambda-macro(var)(expand (quote body)                                        (quote var)))              (quote body)              (quote var)))) ; Let's test it. (println (lambda-Church (x)(x x))) ;    ==> (lambda-macro (x) (expand (quote (x x)) (quote x))) (println ((lambda-Church (x)(x x)) (a b))) ;    ==> ((a b) (a b)) ; ; It works. In future, lambda-Church expressions can ; be freely mixed with other Newlisp expressions. ; ; ; ; To be  continued  ... ;

---