Modern Programming Languages - Chapter 23 - Exercise 2

In this exercise you will define language four, an extension of language three. Here is a sample program in language four, showing all the new constructs:

let

val fact = fn x => if x<2 then x else x * fact (x-1)

in

fact 5

end

As you can see, language four extends language three with three new constructs: the < operator for comparison, the - operator for subtraction, and the conditional (if-then-else) expression. The sample program above defines a recursive factorial function and uses it to compute the factorial of 5.

A. Define the syntax of Language Four by extending the syntax of Language Three with the three additional constructs required. Show your new BNF. Make sure it is unambiguous.

B. Define the three new kinds of AST nodes you need to match your extended syntax. Extend the Prolog implementation of Language Three to handle them. (You will need to start with the dynamic-scoping implementation, since the static-scoping one cannot handle recursive definitions. For this reason, the sample program above is not legal in ML.) Verify that your implementation evaluates the sample program correctly _ the factorial of 5 is 120.

C. Give a natural semantics for Language Four.