EXTRA CREDIT EXERCISES (OPTIONAL)

For these exercises, download the following files and put them all in the same folder. Then open extra-credit-startcode.scm in DrRacket.

Lambda calculus expressions are defined by the grammar below.

  <exp> ::= <variable>
          | (lambda (<parameter>) <exp>)
          | (<exp> <exp>)

A <variable> is any symbol other than lambda, such as x or y. A <parameter> is also any symbol other than lambda, but it always appears inside a single set of parentheses as part of a lambda expression. For example, in the expression (lambda (x) y), the symbol x is a parameter and the symbol y is a variable. Examples of valid lambda calculus expressions:

(define lc1 'x)
(define lc2 '(lambda (y) x))
(define lc3 '(x y))
(define lc4 '(x (y y)))
(define lc5 '(x (lambda (y) y)))
(define lc6 '(lambda (x) (x y)))
(define lc7 '(lambda (x) (lambda (y) x)))
(define lc8 '((lambda (x) x) (lambda (y) y)))
(define lc9 '((lambda (f) (lambda (x) (g x))) y))
(define lc10 '(lambda (x) (lambda (y) ((lambda (z) (x y)) z))))

  1. Write the function (count-lambdas exp), which counts the total number of lambda symbols that appear in a lambda calculus expression.

    (count-lambdas 'x)  → 0
(count-lambdas '(lambda (y) x))  → 1
(count-lambdas '(x (lambda (y) y)))  → 1
(count-lambdas '(lambda (x) (lambda (y) x)))  → 2
(count-lambdas '((lambda (x) x) (lambda (y) y)))  → 2
(count-lambdas '(lambda (x) (lambda (y) ((lambda (z) (x y)) z))))  → 3

  2. Write the function (count-lvars exp), which counts the total number of variables that appear in a lambda calculus expression. Remember that the parameter of a lambda expression is not a variable. For example, in the expression (lambda (a) (b c)), there are only two variables: b and c.

    (count-lvars 'x)  → 1
(count-lvars '(lambda (y) x))  → 1
(count-lvars '(x y))  → 2
(count-lvars '(x (y y)))  → 3
(count-lvars '(x (lambda (y) y)))  → 2
(count-lvars '((lambda (f) (lambda (x) (g x))) y))  → 3

  3. Write the function (count-lparams exp), which counts the total number of parameters that appear in a lambda calculus expression.

    (count-lparams '(lambda (y) x))  → 1
(count-lparams '(x (y y)))  → 0
(count-lparams '(x (lambda (y) y)))  → 1
(count-lparams '(lambda (x) (x y)))  → 1
(count-lparams '(lambda (x) (lambda (y) x)))  → 2
(count-lparams '((lambda (f) (lambda (x) (g x))) y))  → 2

  4. Write the function (get-lvars exp), which takes a lambda calculus expression and returns a list of all of the variables that appear in the expression, in the order that they appear.

    (get-lvars '(lambda (y) x))  → (x)
(get-lvars '(x (y y)))  → (x y y)
(get-lvars '(x (lambda (y) y)))  → (x y)
(get-lvars '(lambda (x) (x y)))  → (x y)
(get-lvars '(lambda (x) (lambda (y) x)))  → (x)
(get-lvars '((lambda (f) (lambda (x) (g x))) y))  → (g x y)

  5. Write the function (get-lparams exp), which takes a lambda calculus expression and returns a list of all of the parameters that appear in the expression, in the order that they appear.

    (get-lparams '(lambda (y) x))  → (y)
(get-lparams '(x (y y)))  → ()
(get-lparams '(x (lambda (y) y)))  → (y)
(get-lparams '(lambda (x) (x y)))  → (x)
(get-lparams '(lambda (x) (lambda (y) x)))  → (x y)
(get-lparams '((lambda (f) (lambda (x) (g x))) y))  → (f x)

  6. Write the function (show-lform exp), which takes a lambda calculus expression and constructs a similar expression with all variables replaced by the symbol var and all parameters replaced by the symbol param.

    (show-lform 'x)  → var
(show-lform '(lambda (y) x))  → (lambda (param) var)
(show-lform '(x (y y)))  → (var (var var))
(show-lform '(x (lambda (y) y)))  → (var (lambda (param) var))
(show-lform '((lambda (x) x) (lambda (y) y)))  → ((lambda (param) var) (lambda (param) var))
(show-lform '(lambda (x) (lambda (y) ((lambda (z) (x y)) z))))
    → (lambda (param) (lambda (param) ((lambda (param) (var var)) var)))