Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 5 - Fall 1996 - Michael Elhadad

Parameter Passing / Continuations

Problems for Sun 26/1


Interpreter with call by value, by reference and by need

Write an interpreter that can pass parameters to procedures either by value, by reference or by need. We need to define special syntax in the definition of procedures to specify what type of parameter passing mechanism is to be used for each parameter (similar to the var specification in Pascal to specify parameters passed by reference). The following syntax is to be used to this end: 
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<par-decl>}*) <exp>)   proc (formals body)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
<decls>       ::= ({<decl>}*)
<decl>        ::= (<var> <exp>)             decl (var exp)
<par-decl>    ::= <var>                     val-param (var)
               | (:ref <var>)               ref-param (var)
               | (:need <var>)              need-param (var)
The following is an example of how a procedure can be defined and called: 
(let ((a 1) (b 2))
  (begin 
    ((proc (x (:ref y) (:need z)) 
        (begin (:= x 1) (:= y 2) (:= z 3)))
     a b (+ a b))
    (write a b)))
For this language, we define the following value structure: 
Expressed Value = Number + Procedure
L-value = Cell(Expressed Value)
Denoted value = Expressed Value + L-value + Memo
Memo = Cell(Thunk + L-value)
Thunk = () -> L-value
Implement the interpreter and write two programs in this language that demonstrate:
  1. the interaction of assignment and side effects and parameter passing mode
  2. the interaction of assignment and side effects and delayed computation

Coroutines in Scheme

Implement the make-coroutine function discussed in the book p.319 in Scheme, using call/cc. Illustrate its use by implementing the same-fringe predicate using coroutines in Scheme. The version using letcont is reproduced here: 
define makecoroutine =
  proc(body)
    let lcs = ignored 
    in letrecproc
      newcoroutine(value) = lcs(value);
      localresume(cont, value) =
        let value = letcont localcont
                    in begin
                      lcs := localcont;
                      cont(value)
                    end
        in begin
          resume := localresume;
          value
        end
    in letcont exit
      in begin
        body(localresume(exit, newcoroutine));
        error()
      end
Last modified Jan 9th, 1997 Michael Elhadad