COSC 3410 Programming Languages

Homework Assignment #3

λ-Calculator

Due: Feb 10, 2020 @ 11:59PM
Submit: Turn in a single Scheme source file called "hw3.scm" using the turnin command on the Systems Lab machines.

Work is to be completed in teams of two. Your source file should be in the EoPL dialect ("#lang eopl" at top of file) supported by DrRacket, and should not make use of non-standard features like comment boxes that produce an XML file rather than a flat text .scm file.

At the bottom of your hw3.scm, please include the line:

(provide parse-expression unparse-lc-exp occurs-free? occurs-bound?)

λ-calculus parse-expression

Build a parser that converts λ-calculus expressions from the grammar given in EoPL Exercises 2.29 into abstract syntax trees. You may start with the define-datatype given on EoPL p.46, and modify it to account for λ expressions with multiple parameters. The parse-expression function on EoPL p.53 is an excellent starting point.

parse-expression : SchemeVal → LcExp
Usage: (parse-expression e) = ast, an abstract syntax tree for λ-calculus expressions including identifiers, λ terms with multiple parameters, and application.

AST unparse-lc-exp

Define a function "unparse-lc-exp", ala EoPL Exercise 2.28, which takes an abstract syntax tree from your parse-expression function above and returns a Scheme value for the original concrete syntax.

unparse-lc-exp : LcExp → SchemeVal
Usage: (unparse-lc-exp ast) = e, a Scheme value for a λ-calculus expression.

Note that unparse-lc-exp performs the inverse operation of parse-expression. For any well-formed λ-calculus expression "e", (unparse-lc-exp (parse-expression e)) should return e.

The code for unparse-lc-exp on EoPL p.53 is an excellent starting point for this problem.

Bullet-proofing

EoPL Exercises 2.23 and 2.30. Add code to your parse-expression implementation to make it more robust against ill-formed input. Generally speaking, your implementation should not crash and should print an appropriate error message no matter what kind of expression it is asked to parse.

Occurs-free? and occurs-bound?

Adapt the code for occurs-free? on EoPL p.46 to work with the expanded grammar from EoPL 2.29 (for helpful rules, see EoPL p. 19)

occurs-free? : Sym x LcExp → Bool
Usage: (occurs-free? sym (parse-expression exp)) = true if the symbol occurs as a free variable reference in the expression, otherwise returns false.

Build a new function occurs-bound?.

occurs-bound? : Sym x LcExp → Bool
Usage: (occurs-bound? sym (parse-expression exp)) = true if the symbol occurs as a bound variable reference in the expression, otherwise returns false.

For whatever reason, EoPL v3 omitted their explanation of occurs-bound. Here is the second edition's explanation:

Note that occurs-bound? is not simply the opposite of occurs-free?. It is possible for both functions to return false for a given expression (the variable does not occur at all,) and it is also possible for both functions to return true for a given expression (a variable occurs both free and bound in different places.)

Examples:
> (occurs-free? 'x (parse-expression 'x))
#t
> (occurs-free? 'x (parse-expression 'y))
#f
> (occurs-free? 'x (parse-expression '(lambda (x) (x y))))
#f
> (occurs-free? 'x (parse-expression '(lambda (y) (x y))))
#t
> (occurs-free? 'x (parse-expression '((lambda (x) x) (x y))))
#t
> (occurs-free? 'x (parse-expression '(lambda (y) (lambda (z) (x (y z))))))
#t
> (occurs-bound? 'x (parse-expression 'x))
#f
> (occurs-bound? 'x (parse-expression 'y))
#f
> (occurs-bound? 'x (parse-expression '(lambda (x) (x y))))
#t
> (occurs-bound? 'x (parse-expression '(lambda (y) (x y))))
#f
> (occurs-bound? 'x (parse-expression '((lambda (x) x) (x y))))
#t
> (occurs-bound? 'x (parse-expression '(lambda (y) (lambda (z) (x (y z))))))
#f