« Return to index

HOP WPO 7 (Extra Info)

Exercise 3

Before starting with this exercise, it is important to understand what a continuation is.

When you enter an expression in the Read-Eval-Print Loop in DrRacket, the top-most continuation is something that expects a value, prints it, and asks for a new expression to evaluate. This is what happens when an expression gets evaluated. If you type a complicated expression, different continuations exists.




		

I will be using using a down arrow (↓) to point to a location in a program, it is not part of the actual program text.

The continuation at in this program expects a value, and prints it to the REPL. Thus the result of evaluating (+ 5 (/ 20 2)) will be printed on the REPL.




		

The continuation at expects a value (which will be the result of evaluating (/ 20 2)), and adds the number five to it. It will then print this number to the REPL.

This is how continuations are used by the Scheme evaluator. However, in Scheme, the procedure call/cc (the abbreviated name of call-with-current-continuation) is used to get a first-class continuation. Just like procedures, continuations are first-class entities in Scheme (they can be assigned to variables, and passed as arguments to procedures).




		

call/cc will call the procedure given to it as argument, and pass the continuation as a value to that procedure. In other words, the anonymous procedure, created using lambda in this example, will receive the continuation (denoted using ) as its argument for cnt. In this example, it is not used.

Normally, the last evaluated expression will be used to generate the return value of a procedure application. However, we can “cheat” this system by making use of this first-class continuation value. The following example program introduces a procedure called foo that, in its body, calls cnt. When we pass foo to call-with-current-continuation, what value is returned by the last expression? What is printed?




		

For these exercises, you have to play Scheme evaluator yourself. For brevity, I skip the definition of foo, and the evaluation of + and 5, and immediately go to the evaluation of (call-with-current-continuation foo).

The continuation around (call-with-current-continuation foo) is something that expects a value, and adds five to it. And then prints this value to the Read-Eval-Print Loop. This continuation is passed to foo. Thus its body will be evaluated in an extended environment where cnt is bound to that continuation.

During the evaluation of the body, the string "hello" is printed. Then (cnt 10) is evaluated. Since cnt is bound to a continuation, it will therefore pass its arguments as the value to that continuation. In other words, it will jump back to the in (+ 5 ↓(call-with-current-continuation foo)) and will therefore evaluate (+ 5 10), and print its result (15) to the Read-Eval-Print Loop.

The rest of the body of foo is not evaluated: the string "world" is not evaluated, nor does it evaluate (and therefore, not even return) (/ 20 2).


Continuations can be stored in variables. In other words…




		

will bound the variable c to a continuation that adds 100 to a given value, and prints it to the Read-Eval-Print Loop. It will also print 200 as the result of evaluating the procedure given to call-with-current-continuation is the number 100 (and \(100 + 100 = 200\)).

When we later encounter the following in the program (assuming that the variable c has not been modified).




		

The value 200 is given to that continuation: it will thus calculate \(100 + 200 = 300\), and print that to the Read-Eval-Print Loop. Note that this value is not returned as the result of evaluating (c 200) inside (+ 100 (c 200)), as the continuation in (+ 100 ↓(c 200)) is simply discarded.

Exercise 5

The first part of this exercise is whether the boolean operators (and and or) are special forms, or procedures.

One way to find out is whether it is possible to implement and in regular Scheme (not in a metacircular evaluator). One way to write your own and (with only 2 parameters) could be the following…




		

If a is considered to be #t (true), then the result of (my-and a b) depends on b. If it is considered to be #f (false), then it can immediately return #f (or a, as it is equal to #f).

However, there is a discrepancy between my-and and and.




		

The first expression simply returns #f, the second expression also returns #f, but first prints the string "test". In Scheme, only the sub expressions that are necessary to determine the return value of boolean operators (and and or) are evaluated. In this case, the second expression does not need to be evaluated, as the first one already evaluates to #f, thus there is no need to evaluate any further sub expressions.

Note! not in Scheme is a procedure, not a special form, since it only needs to invert the boolean value, which can be handled as a procedure, not as a special form.


Therefore, when we have to expand to metacircular evaluator with support for and and or, we have to add them as special forms, not as primitive procedures.

There are two ways for adding new special forms: either you make use of syntactic sugar, or using explicit evaluation rules.

For the former strategy, you convert an expression to an equivalent expression that does not depend on the initial syntactic name.

For example, we can convert procedure definitions using define




		

Therefore, if we first convert all procedure defintions using define in this manner, we only need to add support for define for values (as the creation of the procedure objects happens using lambda).

This approach can also be used for the boolean operators. However, this is not straightforward, as we have to avoid evaluating a sub expression multiple times. (This solution is left as an exercise!).

The latter strategy requires us to write explicit evaluation rules.




		

The solution of this exercise is thus…

  1. Get the constituent (sub) expressions of the and expressions.
  2. If there are none, (in other words, the expression to evaluate is just (and)) we immediately return #t. Otherwise…
  3. Evaluate the first expression…
  4. If it is #f (4a), or there are no further expressions to evaluate (4b), then we return the evaluated value (4c). Otherwise…
  5. We return to step 3, advancing the list lst by one.

The solution for or is quite similar…




		
  1. Get the constituent (sub) expressions of the or expressions.
  2. If there are none, (in other words, the expression to evaluate is just (or)) we immediately return #f. Otherwise…
  3. Evaluate the first expression…
  4. If it is considered to be #t (4a), or there are no further expressions to evaluate (4b), then we return the evaluated value (4c). Otherwise…
  5. We return to step 3, advancing the list lst by one.