Computer Science Homework

 

Consider the following concrete syntax for a simple λ-calculus (lamdba) expression:

<expression> ::= <literal>

<expression> ::= <identifier>

<expression> ::= (lambda ({<identifier>}*) <expression>)

<expression> ::= (<expression> {<expression>}*)

<literal>  ::= number?

<identifier>   ::= symbol?

The abstract syntax of the expression is defined in eopl (#lang eopl) as follows.

(define-datatype expression expression?

  (literal-expresssion

          (literal_tag number?) )

  (variable-expression

          (identifier symbol?) )

  (lambda-expression

           (identifiers (list-of symbol?) )

           (body expression?) )

  (application-expression

           (operator expression?)

           (operands (list-of expression?) ) ) )

Assignment Tasks:

a. (30p) Parsing:

Define a function parse-expression that converts a concrete-syntax (i.e., list-and-symbol) representation of an expression into an abstract syntax representation of it (using the expression data type given above).

The function parse-expression maps a concrete-syntax representation given above (in a list-and-symbol S-expression) into an abstract syntax representation of it.

Hints: This is similar to the parse-expression introduced in Lecture 18 (Slide 9) and Lab 4.

Some test cases:

> (parse-expression '(b))
#(struct:application-expression #(struct:variable-expression b) ())

> (parse-expression '(b 1))
#(struct:application-expression #(struct:variable-expression b) (#(struct:literal-expression 1)))

> (parse-expression '(b 1 2 a 1 x))
#(struct:application-expression #(struct:variable-expression b) (#(struct:literal-expression 1) #(struct:literal-expression 2) #(struct:variable-expression a) #(struct:literal-expression 1) #(struct:variable-expression x)))

> (parse-expression '((a lat) (b latt)))
#(struct:application-expression #(struct:application-expression #(struct:variable-expression a) (#(struct:variable-expression lat))) (#(struct:application-expression #(struct:variable-expression b) (#(struct:variable-expression latt)))))

> (parse-expression '(lambda (x) (x 1)))
#(struct:lambda-expression (x) #(struct:application-expression #(struct:variable-expression x) (#(struct:literal-expression 1))))

> (parse-expression '(lambda (x y) (eqv? x y)))
#(struct:lambda-expression (x y) #(struct:application-expression #(struct:variable-expression eqv?) (#(struct:variable-expression x) #(struct:variable-expression y))))

i. (20p) Create 4 test cases to test the function like above examples. Your test cases must be significant different from these examples.

b. (30p) Implement unparse-expression

Define a function unparse-expression that converts an abstract syntax representation of an expression (using the expression data type given above) into a concrete-syntax (i.e., list-and-symbol) representation of it. The function unparse-expression maps an abstract syntax representation of a λ-calculus expression into a concrete-syntax representation defined above (in a list-and-symbol S-expression).

(This is similar to the unparse-expression introduced in Lecture 19 (Slide 12)). 

i. (20p) Run the test cases in (a.i) to test.

Example:

> (unparse-expression (parse-expression '(lambda (x y) (eqv? x y))))
(lambda (x y) (eqv? x y))