本次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 Turing-complete. 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 (Turing-complete) 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 applicative-order 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  Turing-completeness.   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.

 

•

.x—display function. This is actually a family of functions. .x is literally the function that prints the character x to the screen, but x may be replaced with any character. Note that . on its own is not a function. Also note that .x is a unary function, and does nothing until an argument is supplied. At that point, the function prints x and returns its argument. For example, ‘.*i prints the character * and returns i.

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

 

•

d—“delay”. d is a unary function; the application ‘dF, where F is an unlambda expression representing the argument to d, produces a “promise” to evaluate F. Note that, unlike with normal function appli-  cation, F is not evaluated before it is passed to d.  Hence, for example, ‘d‘.xi produces a promise to    return ‘.xi, but nothing is printed; if the promise is applied, as in ‘‘d‘.xii (this reduces to the same

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 (call-with-current-continuation), 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

1. 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’;

 

•

[a, s(x,y), z, ...] should be replaced with [a, a, x, z’, a, y, z’, ...] after reduction of z

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;

 

•

[a, dot(x), y, ...] should be replaced with [y’, ...] after first reducing y to y’, and then print- ing x to the screen;

 

•

[a, r, y, ...] should be replaced with [y’, ...] after first reducing y to y’, and then printing a newline to the screen.

• • 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 (double-quoted) 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]])

 

 

.

The notation [x]E denotes the bracket abstraction, and roughly means “remove the variable x from the expression E”. The bracket abstraction is presented below:

 

[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: