« Return to index

HOP WPO 8 (Solutions)

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

Section 1: More About Evaluators

Exercise 1: Quick Fire Questions

Question 1

Q: What are the three ways for expanding the metacircular evaluator?

There are two types of expressions: procedure applications, and special forms. The former can be modified by introducing more primitive procedures available to the metacircular evaluator. There are two ways for implementing special forms. The first by making use of syntactic sugar, which converts a program using one special form in a identical program using other special forms that are already available in the evaluator. Another approach is via explicit evaluation: where the semantics of a special form are implemented directly in the implementation of the evaluator.

Question 2

Q: What are special forms? How are they different from procedures? How do you add support for them?

A procedure application will always evaluate its arguments first, before evaluating the body.

Special forms have a different evaluation strategy. Not every structure in a special form is evaluated like a procedure application. Special forms are identified by name. In other words, the following program does not work.




		

Question 3

Q: What special forms are available in Scheme?

This question can be answered by reading the R5RS specification, the specification does not use the term “special form”, only “syntax”. A brief overview of the most important ones is shown below (this list is not complete!).

Question 4

Q: What is the advantage of an analysing evaluator?

If during the evaluation of an expression, the raw expression needs to be parsed at each evaluation step where it is needed, a lot of CPU cycles are wasted on the same computation over and over again (in the case of a recursive loop or a frequently visited part of the program).

Question 5

Q: What are the semantics of call-with-current-continuation?

call-with-current-continuation is a procedure that takes on argument. This argument is expected to be a procedure that also takes one argument. When this procedure is evaluated its parameter will be bound to the a continuation value. This value contains information to “escape” the current continuation and “jump back” to the continuation created by call-with-current-continuation.

This continuation value is, conceptually, also a procedure that takes one argument. When this continuation is evaluated … (continue in question 6).

Question 6

Q: What is a continuation? What happens when you evaluate a continuation application expression.

In computer science and computer programming, a continuation is an abstract representation of the control state of a computer program. Source

In other words, it contains the information about what steps still need to be evaluated. When a continuation application expression is evaluated, it will restore a previously seen continuation and resume the control state of that previous point in time with the value given to the continuation.

Exercise 2: Add support for while




		

And the actual definition.




		

Note that in this case the value returned by #f is the last value returned when the expression sequence was evaluated. This is why another procedure while-loop is necessary that has the same formal parameters as eval-while + the value to return if the condition expression evaluated to false. A much simpler solution was shown in class…




		

The exact requirement of what value is returned as the result of evaluating a while was left unspecified, therefore either solution would be correct.

Download solution

Section 2: Lambda Calculus

An executable file can be found together with the solution of exercise 6.

Exercise 3: Church to Scheme, Scheme to Church




		

A church number is a function that expects two arguments[1]: a value for \(f\), and a value for \(x\). It will then calculate \(f^n(x)\), which is the function \(f\) applied \(n\) times over \(x\). In other words \(C_3 = \lambda{}f.\lambda{}x.f (f (f \: x))\), or in Scheme (lambda (f) (lambda (x) (f (f (f x))))).

Therefore, given \(C_n\) (the \(n\)th Church number), we have to find a value for \(f\) and a value for \(x\) such that it produces just the number \(n\). A possible solution is to count how often the function f is applied, since the result of a call of f is used for the next application we can start with 0, and apply add1 \(n\) times in total.

For the other way around we create a Church number ourself (a function that expects a value for \(f\) first, then for \(x\)), and it applies this function \(n\) times.

Exercise 4: Equal to zero?




		

Note from the previous exercise that a Church number is nothing more than a function that (ignoring the abscense of multi-parameter functions in \(\lambda\)-calculus) expects two arguments: a value for \(f\), and a value for \(x\).

As Church numbers are functions, we have to apply them in order to do something with them, such as producing a boolean value. We start by finding a value for \(x\)…

For the Church boolean 0 (\(C_0\)) the function \(f\) is not applied at all (see its definition), it is thus ignored. It immediately returns the value for \(x\). In other words, we have to supply true as an argument to a Church number.

The next step is to find a value for \(f\)…

Note that every function \(\lambda\)-calculus expects a value, for Church numbers the value given to f is either… the value of x for \(C_1\), or the value generated by \(C_{n - 1}\) for every other Church number. Thus for \(C_1\) the value given to this function is true (as this has already been determined to be a good value for \(x\)).

Given that \(C_1\) is not a Church number equal to zero, we have to find a function that always returns false. An example of such a function in \(\lambda\)-calculus is \(\lambda{}i.false\) [2], or in Scheme syntax (lambda (i) false). Thus a possible solution…

\[zero? = \lambda{}n.(n (\lambda{}i. \: false)) \: true\]

Exercise 5: Fixpoint combinator




		

We start from the original code for calculating Fibonacci numbers in Scheme (without \(\lambda\)-calculus).




		

The body of a function making use of the fixpoint combinator can be placed as-is. However, we need to take into account the following:

The “supercharged” version of the recursive function is created by the Y-combinator. Note that in order to make use of almost-fib we have to call it differently: we first need to create the “supercharged” function, before supplying it the actual arguments. Note that this is not the case in the body of the recursive function: as the first argument that it receives already is the supercharged function.

Exercise 6: Actual Factorial




		

Note that the following does not work:




		

Can you explain why?

Hint! There is a difference in the evaluation rules between lambda calculus, and Scheme.

Download solutions

Bonus Exercises

If you want to verify the solution of the bonus exercises, you can send your solution via email.


  1. In \(\lambda\)-calculus, a function can only receive one argument. In other words, it is a function that expects one argument (the first one), that produces a new functions that expects one argument (the second one), and then executes the body of that inner function. ↩︎

  2. Note that \(\lambda\)-calculus does not have support for global variables as in Scheme: upon evaluation all free variables in the body of a function are replaced with its argument expression (since \(\lambda\)-calculus uses normal order evaluation!). Therefore, if in any of these examples we make use of a variable, we could have just as well pasted its definition in-place. In other words, this expression would be identical to \(\lambda{}i.(\lambda{}t.\lambda{}f. \: f)\). ↩︎