本次CS代写的主要涉及如下领域: 北美程序代写,加拿大程序代写,University of Waterloo代写
Assignment 6: Prolog
CS 442/642
Due April 7th
You will complete this assignment in Prolog.
The Unlambda Programming Language
Not all programming languages are a pleasure to use. If you search the Web, you will find many examples of programming languages (Intercal, for example) that were designed to be as difficult to use as possible, while (hopefully) remaining Turingcomplete. These are sometimes called obfuscated programming languages.
In this assignment, we focus our attention on a particular obfuscated language that enjoys the dis tinction of also being a functional language. This language is called Unlambda. We consider only a (Turingcomplete) subset of Unlambda here; for information on the full language, see the creator’s web site: http://www.madore.org/~david/programs/unlambda/
At its core, an Unlambda program consists of a string made entirely of the characters s, k, and ‘. s and k are functions (or combinators). The symbol ‘ is an “apply” operator. It is a prefix operator, and since all functions in Unlambda are curried, it eliminates the need for parentheses. For example, we represent (ab)c as ‘‘abc, and a(bc) as ‘a‘bc. s is a ternary combinator with the property that, for any a, b, and c, ‘‘‘sabc evaluates to ‘‘ac‘bc (that is, (ac)(bc)). k is a binary combinator with the property that, for any a and b, ‘‘kab evaluates to a. For example, consider the evaluation of the following Unlambda program:
‘‘‘skkk → ‘‘kk‘kk
→ k
Unlambda is an applicativeorder language—to reduce ‘ab, we reduce a first, then b, and finally, we apply the reduced a to the reduced b.
The core language, consisting of s, k, and ‘, are enough to guarantee Turingcompleteness. However, Unlambda supports a number of other interesting primitives, outlined below:
 i—the identity function. i is a unary function, and ‘ix returns x for all x.
 v—the “voracious” combinator. v is a unary function, and ‘vx returns v for all x.

 r—a special case of .x. r is a unary function that prints a newline and then returns its argument.

promise as before, applied to i), Unlambda evaluates the argument to the promise first, the contents of the promise (‘.xi) second, and finally applies the reduced promise to the argument. For example, ‘‘d‘.xi‘ii reduces s follows: ‘‘d‘.xi‘ii → ‘(promise)‘ii → ‘(promise)i → ‘‘.xii → (prints
x) ‘ii → i.
Unlambda also supports the primitive c (callwithcurrentcontinuation), but we shall ignore this.
Part A—An “Unlambda Machine”
For part A, you are to construct an interpreter for the subset of Unlambda discussed above. To simplify the task, the input to your interpreter will be a list consisting of a sequence of Unlambda tokens. We will represent the s, k, i, v, and r operators in our input lists as the symbols s, k, i, v, and r, respectively. To avoid potential compatibility issues across Prolog implementations, we will represent ‘ as the symbol
 Finally, we will represent .x by dot(x), where x represents the character following the dot in the input string.
The interpreter will work as follows: if the head of the input is anything other than a, then the interpreter terminates. Otherwise, it recursively reduces the tail of the list until it is no longer reducible (i.e. it begins with anything other than a), and then does the same with the tail of the tail of the list. At this point, the original list consists of a, followed by two characters other than a, and we can then perform the application requested by the initial a. Applications of the primitive operators proceed as follows:

 [a, k, x, ...] should be replaced with [k(x’), ...] after reduction of x to x’1;
 [a, k(x), y, ...] should be replaced with [x, ...] after reduction of y;
 [a, s, x, ...] should be replaced with [s(x’), ...] after reduction of x to x’;
 [a, s(x), y, ...] should be replaced with [s(x,y’), ...] after reduction of y to y’;

to z’;

 [a, i, x, ...] should be replaced with [x’, ...] after reduction of x to x’;
 [a, v, x, ...] should be replaced with [v, ...] after reduction of x;



 The reduction for d is for you to determine.
The predicate that runs your interpreter should be called interpret. Its first argument should be an Unlambda expression represented as a list; its second argument will be used for output of the reduced expression. For example, invoking interpret([a,a,a,s,k,k,k], Y) should result in a binding of Y to [k].
1Note that the wording here is a bit imprecise, because the precise version is awkward. But in essence, when we say “after reduction of x to x’,” we mean after reduction of (some prefix of the remainder of the list that starts with x and represents a complete subexpression) to x’. Similar comments apply to the other bullets.
Part B—Interpreting from Text
Write a predicate interpretFromText that takes two parameters. The first will be an Unlambda expression represented as a (doublequoted) string. The second will be the reduced Unlambda expression, represented in the format given in part A. interpretFromText will work by translating its input into the format required by interpret and invoking interpret. For example, invoking interpretFromText("‘‘‘skkk", Y) should result in a binding of Y to [k].
For a small bonus, you can arrange to have interpretFromText return the reduced term as a string, by translating the result of the interpreter back to a string before returning it. But note the following: if an Unlambda expression is an incomplete application (and therefore irreducible), like ‘ki or ‘‘skk, your interpreter will return a closure—in this case k(i) and s(k,k), respectively. As the correct answers are really the unreduced ‘ki and ‘‘skk, you will need to look out for closures and translate them back into unreduced Unlambda expressions. Keep in mind that closures may be nested, and so a recursive expansion may be necessary. Similar comments hold for the treatment of dot(x). If the result is (or contains) a promise, you can represent the promise in text as <promise>, or some other suitable representation.
Notes

 The “apply” character in Unlambda is a back quote (ASCII 96).
Part C—“Unlambdafication”
The Unlambda operators s and k were not chosen arbitrarily; they are actually Moses Sch¨onfinkel’s “Ver schmelzungsfunktion”, or S combinator, and “Konstanzfunktion”, or K combinator, both of which may be represented in the λcalculus. The S combinator is λx.λy.λz.(x z)(y z) and the K combinator is λx.λy.x.
Sch¨onfinkel showed that every closed term in the λcalculus may be converted to an equivalent expression consisting only of combinations of S and K. In this way, we may actually remove all of the (bound) variables from an expression. This transformation, which we call “unlambdafication”, is presented below:
unlambda[[x] 
= 
x 
unlambda[[f ] 
= 
f 
unlambda[[M N ] 
= 
unlambda[[M ] unlambda[[N ] 
unlambda[[λx.E] 
= 
[x](unlambda[[E]]) 

[x]y = I if y = x K y otherwise
[x]f [x]I 
= = 
K f K I 
[x]K 
= 
K K 
[x]S 
= 
K S 
[x](M N ) 
= 
S([x]M )([x]N ) 
In the definitions above, we use f to denote function symbols. These represent primitive functions, with which we augment the bare λcalculus.
For Part C of your assignment, you will implement, in Prolog, a translator from the untyped λcalculus to the Unlambda programming language. To do this, you will need a Prolog representation for λterms. The representation you will use is as follows:

 The variable x will be represented by the structure var(x);

the abstraction λx.E will be represented by the structure abs(var(x), E), where E is our Prolog representation for the expression E;

the application M N will be represented by the structure app(M,N), where M and N are our Prolog representations for the expressions M and N , respectively;

 the function symbol f will be represented by the structure func(f).
For example, we would represent the λterm λy.λx.y(y x) in Prolog as
abs(var(y), abs(var(x), app(var(y), app(var(y), var(x)))))
You will support the following function symbols:

r—prints a newline and returns its argument. For example, the expression app(func(r),var(x)) prints a newline (after first reducing the expression var(x)—in this case there is nothing to do) and then reduces to var(x);

dot(x), where x is any character—prints the character x and returns its argument. For example, the expression app(func(dot("*")),var(y)) prints the character * (after first reducing the expression var(y)—in this case there is nothing to do) and then returns var(y);

v consumes its argument and returns v. For example, the expression app(func(v), var(x)) reduces, after reduction of var(x), to func(v).

d—“delay”. See the description in part A of this assignment. For example,
app(func(d), app(func(r), func(i))) returns a promise to evaluate app(func(r), func(i)) (and prints nothing); app(app(func(d), app(func(r), func(i))), func(v)) prints a newline and re turns func(v).
Your translator will be called unlambdafy/2. Its first parameter will be λexpression to be reduced. Its second will be used for output, and will contain the translation of the the λexpression to Unlambda. The output parameter should have format matching the input format for your solution to part A, so that the two predicates could be chained together, if desired.
Notes

 Take note of the spelling of unlambdafy.
Submission
Submit electronically. The distribution of marks is expected to be 40% for part A, 20% for part B, and 40% for part C.