CSc 8710 - DDLP - Fall 2010
Homework 4 - Due October 24 (Sunday), 2010
WAE Interpreter
-------------------------------------------

Consider the following grammar defining a functional language
of arithmetic expressions:

<WAE> ::= <num>
    | {+ <WAE> <WAE>}
    | {- <WAE> <WAE>}
    | {* <WAE> <WAE>}
    | {/ <WAE> <WAE>}
    | {with {{<id> <WAE>} ...} <WAE>}
    | <id>
where an <id> is not +, -, *, /, or with.

In this grammar, the ellipsis (...) means that the previous non-terminal 
is present zero or more times.

Examples of wae-expressions are:

2
x
{+ 2 2}
{+ x 2}
{/ 4 2}
{with {x 3} {with {y 4} {+ y z} } }
{with {{x 2} {y 3}} {with {{z {+ x y}}} {+ x z}}}
{+ {+ {+ 2 3} {+ 4 5}} {+ 5 7}}
{with {x {with {y 3} {+ y y}}} {+ x x}}
{with {x {with {x {with {y 3} {+ y y}}} {+ x x}}}  {+ x 2} }

If a wae-expression has duplicate identifiers, we consider it a semantic error. 
For example, {with {{x 10} {x 20}} 50} has the duplicate identifier error. 

We will code the above wae-expressions in Prolog using function terms and lists as
follows:

2
x
plus(2,2)
plus(x,2)
divide(4,2)
with([[x,3]],with([[y,4]],plus(y,z)))
with([[x,2],[y,3]],with([[z,plus(x,y)]],plus(x,z)))
plus(plus(plus(2,3),plus(4,5)),plus(5,7))
with([[x,with([[y,3]],plus(y,y))]],plus(x,x))
with([[x,
       with([[x,
              with([[y,3]],plus(y,y))
            ]],
            plus(x,x)
       )
     ]],
     plus(x,2)
)

Write a Prolog program to do the following:

(1) Syntax check: define a predicate, wfe(E), which returns true
    if and only if E is a well-formed wae-expression.

(2) Semantic Check: define a predicate, semCheck(E), which returns 
    true if and only if there are no semantic errors in E.
    You should check for two semantic errors: duplicate identifier
    in with-list and value-not-available for evaluation. Example of
    the second semantic error is: {with {{x 2}} {+ x y}}
    If there are errors, a message indicating the error should be
    printed.

(3) Evaluate WAE Expression: define a predicate, evalWAE(E,V), which
    returns the value of expression E in V.