Consider a language with following abstract syntax:

(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?) ) ) )

(define parse-expression

(lambda (expr)

(cond

((symbol? expr) (variable-expression expr))

((pair? expr)

(cond

((eqv? (car expr) 'lambda)

(lambda-expression (caadr expr)

(parse-expression (caddr expr))))

(else (application-expression

(parse-expression (car expr))

(parse-expression (cadr expr))))))

(else (eopl:error 'parse-expression

"Invalid concrete syntax "expr)))))

a. (30p) implement parse-expression:

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 (in this case, a list-and-symbol S-expression) of a -calculus expression into an abstract syntax representation of it.

(This is similar to the parse-expression introduced in Lecture 18 (Slide 7))

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 syn- tax 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 (in this case, a list-and-symbol S-expression) of it.

(This is similar to the unparse-expression introduced in Lecture 18 (Slide 11)).

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))

You need to write your code in a report and include corresponding screenshots of Dr. Rackat demonstrating how your programs work with the test cases.