computer science

Updated April 5, 2017: conditional expression has been removed. Some test case examples have been added. 

From programming exercise 9.6.1 in the textbook.

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

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