Plt1314 5

(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau


  • Course site
  • Date published: 4 Dec 2013
  • Deadline SVN: 10 Dec 2013 (End of Day)
  • Other logistics as previously


Option 1

Invent a "strange" language and define (implement) either small or big-step semantics for it in Prolog. You could inspire yourself with examples from previous exams.

Option 2

Start from the following code from the lecture:

Revise the syntax of expressions such that there is a form both(E1, E2) with the intended semantics that the expression evaluates to the set of results combined from the results of E1 and E2. Revise the semantics, indeed, to compute sets of results.

Option 3

Start from the following code from the lecture:

Consider the Church numeral for "0":

lambda(s, lambda(z, var(z)))

Consider the increment function:

lambda(n, lambda(s, lambda(z, apply(var(s), apply(apply(var(n), var(s)), var(z))))))

Now apply the latter to the former. This would result in the following value:

lambda(s, lambda(z, apply(var(s), apply(apply(lambda(s, lambda(z, var(z))), var(s)), var(z)))))

Instead, we would like to see a more simplified term like this:

lambda(s, lambda(z, apply(var(s), var(z))))

Revise the following rule of the semantics to achieve this simplification:

eval(apply(lambda(X, T1), V), T2) :-
  substitute(T1, X, V, T2).