Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 4 - Spring 2000 - Michael Elhadad

Parameter Passing / Continuations

Problems for Tue 13/6/2000


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 (cf definition in the book p.317). 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 May 30, 2000 Michael Elhadad