Submit: Turn in your hw3.scm source file using the turnin command on morbius.mscsnet.mu.edu or one of the other Systems Lab machines.

Work is to be completed in teams of two. Be certain to include both teammates names in the file. You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline.

Include a comment block at the very top of each file that contains the following:

  ; COSC 3410 - Project [#]
  ; Explain briefly the functionality of the program.
  ; @authors [your names]
  ; Instructor [your instructor]
  ; TA-BOT:MAILTO [your email addresses]


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: (parse-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.

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.

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