2  Installation

To use the system, you first have to install the Scheme48 system [20], which is available from http://www.s48.org/. The current version 1.8 is required to run PGG.

Once you have installed Scheme48, unpack the distribution file by

kailua> mkdir pgg-1.4
kailua> cd pgg-1.4 
kailua> zcat ⟨path-where-you-downloaded⟩/pgg-1.4.tar.gz | tar xvf -

(with kailua> being the shell’s prompt) This creates the directory pgg-1.4 in the current directory.

Next, you should build yourself an image file of the system, to speed up loading later on. To do this type:

kailua> cd pgg-1.4
kailua> make
(echo ",bench on"; \
 echo ",config,load genext-packages.scm pgg-packages.scm"; \
 for package in pgg-residual pgg ; do \
 echo ",load-package $package"; \
 done ; \
 echo ",open pgg signals"; \
 echo ",open auxiliary pgg-library pgg-specialize pp"; \
 echo ",collect"; \
 echo ",dump pgg.image \"(PGG-1.2 made by $LOGNAME `date`)\""; \
 echo ",exit" ) \
| scheme48 -h 10000000
Welcome to Scheme 48 1.8 (made by thiemann on Fri Aug  8 16:50:56 CEST 2008).
Copyright (c) 1993-2008 by Richard Kelsey and Jonathan Rees.
Please report bugs to scheme-48-bugs@s48.org.
Type ,? (comma question-mark) for help.
> will compile some calls in line
> > > > > > Before: 2527559 words free in semispace
After:  4203309 words free in semispace
> Writing pgg.image

Next time you want to use PGG, type

kailua> scheme48 -h 6000000 -i pgg.image

to save the time spent with loading and compiling the system. You might want to put the above into a shell script. The -h parameter determines the heapsizewhich might have to be increased when dealing with larger programs. The pgg.imagefile may be moved to an arbitrary location, it is independent of the directory containing the PGG distribution.

3  First Steps

This section goes through a few examples of using PGG. It assumes that the system has been started in the pgg-1.1 directory. The subdirectory example contains the sources of all examples.

3.1  Power

One of the simplest examples is the exponentiation function power. It resides in file examples/power.scm.

(define (power x n)
  (if (= 0 n)
      (* x (power x (- n 1))))) 

To specialize it, PGG must know three things

The latter two are specified using a binding-time skeleton,i.e., a list that contains the entry point and the binding times of the parameters. In the example, ’(power 1 0) is a sensible binding-time skeleton. It specifies the entry point power and the binding times 1 (dynamic) for the base x and 0 (static) for the exponent n.

> (cogen-driver (list "examples/power.scm") '(power 1 0))
bta-solve done
'((define (specialize-$goal x2) ...

PGG’s answer is the corresponding generating extension. Pretty printing yields:
 (define (specialize-$goal x2)
   (specialize $goal '(power 1 0) (list 'x1 x2)))
 (define (power x_1 n_1)
   (if (_op 0 = 0 n_1)
       (_lift 0 1 1)
       (_op 1 * x_1 (power x_1 (_op 0 - n_1 1)))))
 (define ($goal x_1 n_1)
   (power x_1 n_1))

To use the generating extension, we need to compile it. There are several ways to do that:
> (define genext
    (cogen-driver (list "examples/power.scm") '(power 1 0)))
bta-solve done
; no values returned
> (load-program genext)
; no values returned

Alternatively, we can first save the generating extension to a file and then load and compile the file.
> (writelpp genext "/tmp/power-10.scm")
> (load "/tmp/power-10.scm")
; no values returned

The latter approach is recommended if the source program does not yet specialize satisfactorily. In this case, inspection of the generating extension reveals possible problems. For this reason, the syntax of the generating extension is as close as possible to binding-time annotated Scheme.

Now that we have loaded the generating extension, we are ready to specialize. This is facilitated by the specialize-$goal function provided as part of the generating extension.

> (specialize-$goal 0)
'(power-2 x1)
> (get-residual-program)
'((define (power-2 x-3) 1))

The specializer responds with the call template for the residual program, ’(power-2 x1), indicating that power-2 is the entry point of the residual program and that it takes one parameter. The specializer puts the residual program in a variable whose contents can be retrieved with the get-residual-program procedure, for further examination, compilation, or to save it to a file.

Here is a more interesting run, specializing power for n=4.

> (specialize-$goal 4)
'(power-2 x1)
> (p (get-residual-program))
((define (power-2 x-3)
   (let* ((mlet-11 (* x-3 1))
          (mlet-9 (* x-3 mlet-11))
          (mlet-7 (* x-3 mlet-9)))
     (* x-3 mlet-7))))

(The function p invokes the pretty printer.)

This residual program looks more complicated than we expected. The reason is that PGG—by default—avoids to duplicate or to reorder residual code. This feature makes it easy to have impure (side-effecting) primitives. In the present case, we know that * is pure and that no code duplication arises from it. An appropriate declaration,

(define-primitive * - pure)

as provided in the file "examples/pure-arith.scm", instructs PGG that * is indeed a pure function. Now we can say
> (define genext
    (cogen-driver (list "examples/power.scm"
                        "examples/pure-arith.scm") '(power 1 0)))
> (load-program genext)
; no values returned
> (specialize-$goal 4)

and PGG generates the expected code:
(define (power-2 x-3)
  (* x-3 (* x-3 (* x-3 (* x-3 1)))))

A post-processor would have reduced the expression (* x-1 1) to x-1. This example demonstrates that there is none. It is nevertheless possible to obtain the same effect by slightly rewriting the source program. This is left as as exercise.

3.2  Lambda interpreter

This section shows a classic example, an interpreter for an applied lambda calculus with Scheme’s constants, a conditional, and primitive operations. The input to the interpreter is a lambda expression, a list of free variables, and a list of values of the free variables. The following grammar specifies the concrete syntax of expressions.

E ::= X | (lambda (X) E) | (apply E E)
   |  C | (if E E E) | (O E*)

This interpreter employs partially static data to represent the environment. The environment is a list of pairs of variable name and value. The intention is that the length of the list and all variable names are static, but the values are dynamic. Traditionally1, the Scheme built-in lists cannot be used for this, so we define a new algebraic datatype for this purpose.

(define-data my-list (my-nil) (my-cons my-car my-cdr)) 

This line declares the algebraic datatype my-list with constructors my-nil and my-cons (see 4.9.2). The elements of this datatype may be partially static, i.e., the components may have a different (higher) binding time than the structure itself. In addition, they can be memoized separately.

It is a little tedious to enter such an environment by hand, so we also supply a function that transforms a static list of names and a dynamic list of values into an environment. Finally, it calls the interpreter function int.

(define (main exp names values)
  (let loop ((names names) (values values) (env (my-nil)))
    (if (null? names)
        (int exp env)
        (loop (cdr names) (cdr values)
              (my-cons (my-cons (car names) (car values)) env)))))

The interpreter has two local functions, int* and apply-prim. Int* evaluates a list of expressions to a list of values. Apply-prim takes a primitive operator and a list of value and returns the result. The interesting part of apply-prim is its use of eval. Eval’s argument op is static, whereas the result of eval is dynamic.
(define (int exp env)
  (let loop ((exp exp))
    (define (int* exp*)
      (let recur ((exp* exp*))
        (if (null? exp*)
            (cons (loop (car exp*))
                  (recur (cdr exp*))))))
    (define (apply-prim op args)
      (apply (eval op (interaction-environment))
     ((constant? exp)
     ((not (pair? exp))
      (lookup exp env))
     ((eq? (car exp) 'IF)
      (let ((test-exp (cadr exp))
            (then-exp (caddr exp))
            (else-exp (cadddr exp)))
        (if (loop test-exp)
            (loop then-exp)
            (loop else-exp))))
     ((eq? (car exp) 'LAMBDA)
      (lambda (y)
        (int (caddr exp) (my-cons (my-cons (caadr exp) y) env))))
     ((eq? (car exp) 'APPLY)
      ((loop (cadr exp))
       (loop (caddr exp))))
      (apply-prim (car exp) (int* (cdr exp)))))))

All that’s missing are two auxiliary functions, constant? and lookup, that indicate whether an expression denotes a constant and perform lookup in the environment.
(define (constant? e)
  (or (boolean? e)
      (number? e)
      (and (pair? e) (eq? (car e) 'QUOTE))))

(define (lookup v env)
  (let loop ((env env))
    (if (eq? v (my-car (my-car env)))
        (my-cdr (my-car env))
        (loop (my-cdr env)))))

As already mentioned, the idea is that the inputs exp and names are static and that values is dynamic. So we start the binding-time analysis with
> (define genext 
    (cogen-driver (list "examples/int.scm") '(main 0 0 1)))
bta-solve done
; no values returned

To load this generating extension, we need to load the define-data operation from module pgg-residual.
> ,open pgg-residual
> (load-program genext)
> (specialize-$goal 5 '())
'(main-2 x3)
> (p (get-residual-program))
((define (main-2 x-3) 5))
> (specialize-$goal '(+ x y) '(x y))
'(main-2 x3)
> (p (get-residual-program))
((define (main-2 x-3)
   (let* ((mlet-5 (cdr x-3))
          (mlet-7 (car x-3))
          (mlet-9 (cdr mlet-5))
          (mlet-11 (car mlet-5)))
     (+ mlet-7 mlet-11))))
> (specialize-$goal '(lambda (x) (+ x y)) '(y))
'(main-2 x3)
> (p (get-residual-program))
((define (main-2 x-3)
   (define (loop-4 mlet-3)
     (lambda (y_1-5)
       (+ y_1-5 mlet-3)))
   (let* ((mlet-5 (cdr x-3)) (mlet-7 (car x-3)))
     (loop-4 mlet-7))))

The examples demonstrate that the environment is specialized away. Only the dynamic values survive and become parameters (this is called “arity raising”). Furthermore, eval and apply have been specialized satisfactorily, as demonstrated by the last two specializations: (+ mlet-7 mlet-11) and (+ y_1-5 mlet-3) is the corresponding residual code.

The auxiliary definition of loop-4 is introduced automatically by the specializer to avoid a non-terminating specialization. In the example, there is no danger of non-termination because the recursive calls only decompose the source expression. Hence, it is safe to turn off memoization for the function int by changing the first line of its definition to

(define-without-memoization (int exp env)

After constructing a new generating extension, we obtain a simpler residual program.
(define ($goal-1 values-1)
  (let* ((mlet-2 (cdr values-1))
         (mlet-3 (car values-1)))
    (lambda (y_1-4) (+ y_1-4 mlet-3))))

3.3  Cyclic

This example demonstrates specialization of imperative programs.

(define-data my-list (my-nil) (my-cons my-car my-cdr)) 
(define (main d)
  (let ((cycle (my-cons 1 (make-cell (my-nil)))))
    (cell-set! (my-cdr cycle) cycle)
    (zip d cycle)))
(define (zip d s)
  (if (null? d)
      (cons (cons (car d) (my-car s))
            (zip (cdr d) (cell-ref (my-cdr s))))))

The list cycle is completely static, but the cdr of cycle contains a reference to cycle itself. This cyclic list of ones is passed as an argument to the function zip which zips it together with a dynamic list d. Unrolling the dynamic list involves memoization, hence the specializer must memoize the cyclic structure passed as an argument to zip to avoid infinite specialization. Here is what happens.
> (define genext
    (cogen-driver (list "examples/cyclic.scm") '(main 1)))
effect analysis: fixpointing done
bta-solve done
> (p genext)
((define-data my-list (my-nil) (my-cons my-car my-cdr))
 (define (specialize-$goal)
   (specialize $goal '(main 1) (list 'x1)))
 (define (main d_2)
   (let ((cycle_1 (_ctor_memo 0
                              (0 0)
                              (_make-cell_memo 0
                                               (_ctor_memo 0
     (_message!_memo 0 (_s_t_memo 0 my-cdr cycle_1) cell-set! cycle_1)
     (zip d_2 cycle_1)))
 (define (zip d_1 s_1)
   (multi-memo 1 1 'zip-2 zip-2 #f '(1 0) (list d_1 s_1)))
 (define (zip-2 d_1 s_1)
   (_if 1
        (_op 1 null? d_1)
        (_lift 0 1 '())
        (_op 1
             (_op 1 cons (_op 1 car d_1) (_lift 0 1 (_s_t_memo 0 my-car s_1)))
             (zip (_op 1 cdr d_1)
                  (_s_t_memo 0 cell-ref (_s_t_memo 0 my-cdr s_1))))))
 (define ($goal d_2)
   (main d_2)))

The function _ctor_memo constructs the memoized representation of a constructor. Its first argument is the binding time of the structure itself, its second argument is the list of binding times of the components (all 0 in this case). _make-cell_memo constructs a memoized reference cell, the first argument is the binding time of the address and the next argument 3 is the unique label of the corresponding make-cell operation in the source program. _s_t_memo accesses or tests memoized data objects, the implementation handles them all uniformly.

The operation _define-data serves to transfer the datatype definition to the residual program.

To load this generating extension, we need to make the define-data operation available.

> ,open pgg-residual
Load structure pgg-residual (y/n)? y
cogen-ctors.scm ]
Newly accessible in user: (define-data)
> (load-program genext)
> (specialize-$goal)
'(main-2 x1)
> (p (get-residual-program))
((define (main-2 x-3)
   (define (zip-4 x-3)
     (let ((mlet-5 (null? x-3)))
       (if mlet-5
           (let* ((mlet-11 (car x-3))
                  (mlet-9 (cons mlet-11 1))
                  (mlet-13 (cdr x-3))
                  (mlet-15 (zip-4 mlet-13)))
             (cons mlet-9 mlet-15)))))
   (zip-4 x-3)))

The cyclic structure vanishes on specialization. The construction of the pair (x . 1) is implemented by (cons mlet-11 1).

3.4  Guide to the other examples

3.5  Specialization of modular programs

As an advanced feature, it is possible to encapsulate the generating extension in a module. We recap the example of the power function to illustrate it. In addition to the usual parameters for cogen-driver we need to specify a filename for the output.

> (cogen-driver (list "examples/power.scm") '(power 1 0) "/tmp/power1.scm")
bta-solve done
'((define (power x_1 n_1) (if (_op 0 = 0 n_1) (_lift 0 1 1) (_op 1 * x_1 (power x_1 (_op 0 - n_1 1))))) (define ($goal x_1 n_1) (power x_1 n_1)))

This command generates two files:

To use the generating extension from this module, we need to make Scheme48 aware of it.

> ,config,load /tmp/power1.config.scm

Now the system can load and compile the module, just by referencing it with its name.
> ,open power1
Load structure power1 (y/n)? y
[define-data cogen-ctors.scm]
[power1 /tmp/power1.scm]

Finally, we can specialize in the same way as before.
> (specialize $goal '($goal 1 0) '(x 0))
'($goal-1 x)
> (get-residual-program)
'((define ($goal-1 x-1) 1))

Section 4.10.1 in the reference part lists a number of options to gain more control over the module declaration.

3.6  Specialization with respect to indexed data

It is possible to split the static data into an indexed set of data fragments. The main catch is that only one particular indexed value is available to each single run of the specializer, the current world. The specializer can request arbitrary elements (worlds) from this set using a special construct. If the request concerns the current world then the specializer continues right away. Otherwise, it checks the memoization cache. If the requested world has already been seen in the past, it might be possible to resolve the request. Otherwise, the specializer generates a new memoization point which waits until the requested world becomes available to the specializer, possibly for the second time.

The most striking application for this feature is the separate compilation of modular programs by specializing an interpreter. In this application, the index values are the names of modules and the standard semantics of the special construct is to load the module’s text into memory.

An an example, we consider the compilation of a simple register machine language. Here is an example session.

> (load "examples/modint-examples.scm")
> (p module1)
((add (jz 1 copy)
      (decr 1)
      (incr 0)
      (jump add))
> (p module2)
((copy (jz 2 test)
       (incr 1)
       (decr 2)
       (jump copy))
 (test (jz 1 finis)
       (jump add)))

The main function of the interpreter for this register-machine language accepts four parameters, a function that maps a label to a module name, modulename-of, the entry label, name, the number of registers, nargs, and the initial contents of the registers, initial_args. The name and nargs inputs are known statically, the other inputs are dynamic.

> (define genext
    (cogen-driver '("examples/modint-base.scm" "examples/modint.scm")
                  '(main 1 0 0 1)))
interpret-type: #(type-all t #(type-app -> (#(type-app b ()) #(type-app -> (#(type-app b ()) #(type-app b ()) #(type-var t))) #(type-var t))))
interpret-type: #(type-all t #(type-var t))
bta-solve done
> ,open pgg-residual
> (writelpp genext "/tmp/modint0.scm")
> (load "/tmp/modint0.scm")
> (specialize-$goal 'add 2)
'(main-1 x1 x4)

Specialization stops right before loading the first module. So far, it generated code for transferring the input list into the registers:

> (p (get-residual-program))
((define (main-1 x-2 x-1)
   (let* ((mlet-3 (car x-1))
          (mlet-4 (cdr x-1))
          (mlet-5 (car mlet-4))
          (mlet-6 (cdr mlet-4))
          (mlet-7 (x-2 'add)))
     (jump-global-2 x-2 mlet-3 mlet-5))))

The call to jump-global-2 refers to code that will be generated as soon as the next module becomes available. This fact is signalled to the system via the continue function.

> (continue 'mod1 module1)

At any point between invocations of continue it is possible to suspend the state of specialization to a file. The corresponding command is

> (suspend "/tmp/suspended.scm")

Another, later session with pgg can resume this specialization after loading the generating extension and reading the suspended file using resurrect.

> (load "/tmp/modint0.scm")
> (load "examples/modint-examples.scm")
> (resurrect "/tmp/suspended.scm")
> (continue 'mod2 module2)
> (continue 'mod1 module1)

The last two calls to continue complete the specialization of the interpreter of modular register machine programs.

The file modint-mutual.scm contains a more sophisticated implementation that compiles each module only once. Here is a transcript:

> (define genext
    (cogen-driver '("examples/modint-base.scm" "examples/modint-mutual.scm")
                  '(main 0 1 0 1)))
interpret-type: #(type-all t #(type-app -> (#(type-app b ()) #(type-app -> (#(type-app b ()) #(type-app b ()) #(type-var t))) #(type-var t))))
interpret-type: #(type-app -> (#(type-app b ()) #(type-app b ())))
bta-solve done
> (writelpp genext "/tmp/regcompiler2.scm")
> (load "/tmp/regcompiler2.scm")
> (specialize-$goal exported-labels 3)
'(main-1 x2 x4)

Here is the startup code for the compiled program:

> (p (get-residual-program))
((define (main-1 x-2 x-1)
   (let* ((mlet-3 (car x-1))
          (mlet-4 (cdr x-1))
          (mlet-5 (car mlet-4))
          (mlet-6 (cdr mlet-4))
          (mlet-7 (car mlet-6))
          (mlet-8 (cdr mlet-6)))
     (case x-2
       ((add) (jump-2 mlet-3 mlet-5 mlet-7))
       ((finis) (jump-3 mlet-3 mlet-5 mlet-7))
       ((copy) (jump-4 mlet-3 mlet-5 mlet-7))
       (else (dyn-error "Unknown name"))))))

Here is the code for the first module:

> (continue 'mod1 module1)
> (p (get-residual-program))
((define (jump-2 mlet-3 mlet-2 mlet-1)
   (if (zero? mlet-2)
       (jump-4 mlet-3 mlet-2 mlet-1)
       (jump-2 (+ mlet-3 1) (- mlet-2 1) mlet-1)))
 (define (jump-3 mlet-3 mlet-2 mlet-1)

Here is the code for the second module:

> (continue 'mod2 module2)
> (p (get-residual-program))
((define (jump-5 mlet-3 mlet-2 mlet-1)
   (if (zero? mlet-2)
       (jump-3 mlet-3 mlet-2 mlet-1)
       (jump-2 mlet-3 mlet-2 mlet-1)))
 (define (jump-4 mlet-3 mlet-2 mlet-1)
   (if (zero? mlet-1)
       (jump-5 mlet-3 mlet-2 mlet-1)
       (jump-4 mlet-3 (+ mlet-2 1) (- mlet-1 1)))))

The input for this section, along with one more example, can be found in file examples/sample_modules_session.scm.

1 In partial evaluation, that is.