; 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 ... ; |
---
No comments:
Post a Comment