Program Transformation (Autumn 2005)

EXERCISE MULTI-LEVEL LANGUAGE

Exercises

a) Read Sect. 3 ("A case study...") in [GJ97]. Implement the two-level program iprod2 and the two-level code generation shown in Fig.5+6. The Scheme system SCM is available at DIKU (or install it on your own computer; any Scheme system will do). The Scheme system Guile is also available (see below).
Run the two-stage computation: (i) Run iprod2 with known n=3, v='(7 8 9) and unknown w='w. This produces a residual expression (cf. Fig. 4). (ii) Wrap the residual expression into a function definition, and run the program with w='(1 2 3). Show the output of each stage. You will need to add the following function definition:

(define (ref n v) (if (> n 1) (ref (- n 1) (cdr v)) (car v)))

b) Implement the multi-level program iprod3 and the multi-level code generation in Fig.7+8. Run the three-stage computation with the same values as in 1.a). Document each stage by showing its output.
c) Explain the notion of a multi-level generating extension using the example 1 b). Hint: read Sect. 2.2.3 about offline specialization pipelines.

a) Perform by hand a 2-level monovariant binding-time analysis of the Norma interpreter. The initial binding-times are pgm:0 and x:1. Show the result of your analysis by annotating by hand all constructs in the Norma interpreter with their binding-times. Write the annotation in multi-level form. For example, write (car ...) when car:0 and (_ 'car 1 ...) when car:1. Ignore the dummy function memo.
b) Complete the annotated interpreter from 2.a) into a runnable two-level interpreter by inserting lift where needed. Hint: see the example program in Fig. 7. Read also about multi-level lifting on p.126. Congratulations, you just completed a translator from Norma to Scheme. We also say that the translator is a generating extension of the interpreter. Want to test it? Use your two-level interpreter and translate a loop-free Norma programs into Scheme. For example, the Norma-program Y:=Y+1, Y:=Y+1.

c) What happens if you use your two-level interpreter to translate a Norma program computing y := 2 * x? Explain the behavior.

(Advanced, optional) Read Sect. 5.2 - 5.4 [GJ97]. You may ignore the discussions about closures and higher-order specialization. Implement the first-order variant of memo shown in Fig. 16+17. Modify your two-level interpreter (from 2.b) by inserting your memoization function. You find examples in Fig. 18. For your convenience, the points to memoize are marked by MEMO in the Norma interpreter. Show how your new translator works by translating a Norma programs that contains at least one loop. Document your experiments.
[GJ97] Glück R., Jørgensen J., An automatic program generator for multi-level specialization. In: Lisp and Symbolic Computation, 10(2): 113-158, 1997.

Msg from EDB: Guile Scheme. On machines kand-4 and kand-5.Executables are found in /usr/bin and called guile (the main application), guile-config, guile-snarf and guile-tools.Manuals and FAQ. Example to start and exit the Guile Scheme interpreter. The command to load a file into Scheme is (load "filename").

me> guile guile> (+ 2 3) 5 guile> (exit) me>

Introduction to Scheme: See slides and courses note of OS2.

RG, rev. 1.2.2006

	Exercises



	a) Read Sect. 3 ("A case study...") in [GJ97]. Implement the two-level program `iprod2` and the two-level code generation shown in Fig.5+6. The Scheme system SCM is available at DIKU (or install it on your own computer; any Scheme system will do). The Scheme system Guile is also available (see below). Run the two-stage computation: (i) Run `iprod2` with known `n`=`3`, `v`=`'(7 8 9)` and unknown `w`=`'w.` This produces a residual expression (cf. Fig. 4). (ii) Wrap the residual expression into a function definition, and run the program with `w`=`'(1 2 3)`. Show the output of each stage. You will need to add the following function definition: (define (ref n v) (if (> n 1) (ref (- n 1) (cdr v)) (car v))) b) Implement the multi-level program `iprod3` and the multi-level code generation in Fig.7+8. Run the three-stage computation with the same values as in 1.a). Document each stage by showing its output. c) Explain the notion of a multi-level generating extension using the example 1 b). Hint: read Sect. 2.2.3 about offline specialization pipelines. a) Perform by hand a 2-level monovariant binding-time analysis of the Norma interpreter. The initial binding-times are `pgm:0` and `x:1`. Show the result of your analysis by annotating by hand all constructs in the Norma interpreter with their binding-times. Write the annotation in multi-level form. For example, write `(car` ...`)` when `car:0` and `(_ 'car 1` ...`)` when `car:1`. Ignore the dummy function `memo`. b) Complete the annotated interpreter from 2.a) into a runnable two-level interpreter by inserting `lift` where needed. Hint: see the example program in Fig. 7. Read also about multi-level lifting on p.126. Congratulations, you just completed a translator from Norma to Scheme. We also say that the translator is a generating extension of the interpreter. Want to test it? Use your two-level interpreter and translate a loop-free Norma programs into Scheme. For example, the Norma-program `Y:=Y+1,` `Y:=Y+1`. c) What happens if you use your two-level interpreter to translate a Norma program computing y := 2 * x? Explain the behavior. (Advanced, optional) Read Sect. 5.2 - 5.4 [GJ97]. You may ignore the discussions about closures and higher-order specialization. Implement the first-order variant of `memo` shown in Fig. 16+17. Modify your two-level interpreter (from 2.b) by inserting your memoization function. You find examples in Fig. 18. For your convenience, the points to memoize are marked by `MEMO` in the Norma interpreter. Show how your new translator works by translating a Norma programs that contains at least one loop. Document your experiments. [GJ97] Glück R., Jørgensen J., An automatic program generator for multi-level specialization. In: Lisp and Symbolic Computation, 10(2): 113-158, 1997. Msg from EDB: Guile Scheme. On machines kand-4 and kand-5.Executables are found in /usr/bin and called guile (the main application), guile-config, guile-snarf and guile-tools.Manuals and FAQ. Example to start and exit the Guile Scheme interpreter. The command to load a file into Scheme is `(load "filename")`. me> guile guile> (+ 2 3) 5 guile> (exit) me> Introduction to Scheme: See slides and courses note of OS2.