The PGG System---User Manual

Peter Thiemann
Universität Freiburg
thiemann@informatik.uni-freiburg.de






1   Introduction

The PGG system is a partial evaluation system for the full Scheme language as defined in the R5RS report [19]. It has the following features As a non-feature, the system does not have a post-processor. This manual does not contain explanatory material about offline partial evaluation. Section 7.1 gives some pointers to relevant literature.



2   Installation

To use the system, you first have to install the Scheme48 system [20], which is available from Richard Kelsey's homepage . The current version is 0.53; PGG has been known to work with versions ³ 0.42.

Once you have installed Scheme48, unpack the distribution file by 
hanauma> mkdir pgg-1.1
hanauma> cd pgg-1.1 
hanauma> zcat <PATH_TO>pgg-1.1.tar.gz | tar xvf -
(with hanauma> being the shell's prompt) This creates the directory pgg-1.1 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: 
hanauma> cd pgg-1.1
hanauma> 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 cogen-specialize pp"; \
 echo ",collect"; \
 echo ",dump pgg.image \"(PGG-1.1 made by $LOGNAME `date`)\"";
 echo ",exit" )  | scheme48 -h 10000000
Welcome to Scheme 48 0.51 (made by pjt on Wed Jun 24 08:54:28 BST 1998).
Copyright (c) 1993, 1994 by Richard Kelsey and Jonathan Rees.
Copyright (c) 1996 by NEC Research Institute, Inc.
Please report bugs to scheme-48-bugs@martigny.ai.mit.edu.
Type ,? (comma question-mark) for help.
> Will compile some calls in line
> genext-packages.scm
pgg-packages.scm

Undefined: (anf-specializer anf-specializer-interface)
> [pp /usr/local/lib/scheme48/big/pp.scm]
[auxiliary auxiliary.scm]
[cogen-gensym cogen-gensym.scm]
[cogen-boxops cogen-boxops.scm]
[cogen-globals cogen-globals.scm]
[cogen-specialize cogen-specialize.scm]
[cogen-library cogen-library.scm]
[shift-reset shift-reset.scm]
[cogen-residual cogen-residual.scm]
[cogen-completers cogen-completer.scm]
[cogen-record cogen-record.scm]
[cogen-memo-standard cogen-memo-standard.scm]
[pgg-library cogen-direct-anf.scm]
[define-data cogen-ctors.scm]
[pgg-residual]
> [cogen-env cogen-env.scm]
[cogen-macro cogen-macro.scm]
[cogen-abssyn cogen-abssyn.scm]
[cogen-scheme cogen-scheme.scm]
[cogen-labset cogen-labset-bylist.scm]
[cogen-bta cogen-effect.scm cogen-eq-flow.scm
Undefined: (parse-type desc-np desc-nc desc-nt desc-type btann)
]
[cogen-typesig cogen-typesig.scm]
[cogen-oca cogen-oca.scm]
[cogen-construct-genext cogen-construct-genext.scm]
[cogen-skeleton cogen-skeleton.scm]
[cogen-terminate cogen-terminate.scm]
[pgg cogen-driver.scm]
> > > Before: 2377611 words free in semispace
After:  3560836 words free in semispace
> Writing pgg.image
> 20.221u 0.572s 0:24.01 86.5%  103+50335k 0+90io 27pf+0w
hanauma>
Do not worry about the Undefined: messages, they result from mutually recursive modules.

Next time you want to use PGG, type 
hanauma> 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 heapsize which might have to be increased when dealing with larger programs. The pgg.image file 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)
      1
      (* 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-run
bta-solve
bta-solve done
'((define (power x_1 n_1) (_if 0 1 (_op 0 = '0 n_1) (_lift ...
>
PGG's answer is the corresponding generating extension. Pretty printing yields: 
(define (power x_1 n_1)
   (_if 0 1
        (_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-run
bta-solve
bta-solve done
> (load-program genext)
>
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")
/tmp/power-10.scm 
>
This 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. The specialize function takes as parameters the binding-time skeleton '($goal 1 0) and an argument template '(ignored 0). The binding-time skeleton names the entry point and lists the binding times. The argument template lists all arguments, one for each binding time in the skeleton. The arguments corresponding to non-zero binding times must be symbols, because they serve as stubs for variable names. The arguments corresponding to zero binding times serve as the static inputs. 
> (specialize $goal '($goal 1 0) '(ignored 0))
'($goal-1 ignored)
> *residual-program*
'((define ($goal-1 ignored-1) 1))
>
The specializer responds with the call template for the residual program, '($goal-1 ignored), indicating that $goal-1 is the entry point of the residual program and that it takes one parameter. The specializer puts the residual program in variable *residual-program*, for further examination, compilation, or to save it to a file.

Here is a more interesting run, specializing power for n=4. 
> (specialize $goal '($goal 1 0) '(x 4))
'($goal-1 x)
> (p *residual-program*)
(define ($goal-1 x-1)
  (let* ((mlet-5 (* x-1 1))
         (mlet-4 (* x-1 mlet-5))
         (mlet-3 (* x-1 mlet-4)))
    (* x-1 mlet-3)))
(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. Given an appropriate declaration as in the file "examples/pure-arith.scm", 
(define-primitive * - pure)
Now we can say 
> (define genext
>   (cogen-driver (list "examples/power.scm"
>                       "examples/pure-arith.scm") '(power 1 0)))
...
> (load-program genext)
> (specialize $goal '($goal 1 0) '(x 4))
and PGG generates the expected code: 
(define ($goal-1 x-1)
  (* x-1 (* x-1 (* x-1 (* x-1 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.

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))
             args))
    (cond
     ((constant? exp)
      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))))
     (else
      (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-run
bta-solve
bta-solve done
>
To load this generating extension, we need to load the define-data operation from module pgg-residual. 
> ,open pgg-residual
Load structure pgg-residual (y/n)? y
[pgg-residual
cogen-ctors.scm ]
Newly accessible in user: (define-data)
> (load-program genext)
> (specialize $goal '($goal 0 0 1) '(5 () values))
'($goal-1 values)
> (p *residual-program*)
((define ($goal-1 values-1) 5))
32
> (specialize $goal '($goal 0 0 1) '((+ x y) (x y) values))
'($goal-1 values)
> (p *residual-program*)
((define ($goal-1 values-1)
   (let* ((mlet-2 (cdr values-1))
          (mlet-3 (car values-1))
          (mlet-4 (cdr mlet-2))
          (mlet-5 (car mlet-2)))
     (+ mlet-3 mlet-5))))
26
> (specialize $goal '($goal 0 0 1) '((lambda (x) (+ x y)) (y) values))
'($goal-1 values)
> (p *residual-program*)
((define ($goal-1 values-1)
   (define (loop_2-3-2 mlet-3-1)
     (lambda (y_1-2)
       (+ y_1-2 mlet-3-1)))
   (let* ((mlet-2 (cdr values-1))
          (mlet-3 (car values-1)))
     (loop_2-3-2 mlet-3))))
28
>
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-3 mlet-5) and (+ y_1-2 mlet-3-1) is the corresponding residual code.

We can get rid of the auxiliary definition of loop_2-3-2 by turning off memoization for the function int. We just change the first line of its definition to 
(define-without-memoization (int exp env)
  ...)
After constructing a new generating extension, we obtain a satisfactory 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)))
bta-run
effect analysis: fixpointing done
bta-solve
bta-solve done
> (p genext)
((define-data
   my-list
   (my-nil)
   (my-cons my-car my-cdr))
 (define (main d_2)
   (let ((cycle_1
           (_ctor_memo 0 (0 0)
             my-cons
             1
             (_make-cell_memo 0 3 0 (_ctor_memo 0 () my-nil)))))
     (_cell-set!_memo 0
       (_s_t_memo 0 my-cdr cycle_1)
       cycle_1)
     (zip d_2 cycle_1)))
 (define (zip d_1 s_1)
   (multi-memo 1 'zip-4 zip-4 '(1 0) (list d_1 s_1)))
 (define (zip-4 d_1 s_1)
   (_if 1 1
        (_op 1 null? d_1)
        (_lift 0 1 '())
        (_op 1
             cons
             (_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)
   (begin
     (_op 0 _define_data '(my-list (my-nil) (my-cons my-car my-cdr)))
     (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
[pgg-residual
cogen-ctors.scm ]
Newly accessible in user: (define-data)
> (load-program genext)
> (specialize $goal '($goal 1) '(x))
'($goal-1 x)
> (p *residual-program*)
((define ($goal-1 x-1)
   (define (zip-4-2 x-1-1)
     (let ((mlet-2 (null? x-1-1)))
       (if mlet-2
         '()
         (let* ((mlet-5 (car x-1-1))
                (mlet-4 (cons mlet-5 1))
                (mlet-6 (cdr x-1-1))
                (mlet-7 (zip-4-2 mlet-6)))
           (cons mlet-4 mlet-7)))))
   (zip-4-2 x-1)))
The cyclic structure vanishes on specialization. The construction of the pair (x . 1) is implemented by (cons mlet-5 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-run
bta-solve
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
/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)
> *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")
examples/modint-examples.scm
> (p module1)
((add (jz 1 copy)
      (decr 1)
      (incr 0)
      (jump add))
 (finis))
> (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)))
bta-run
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
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 *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")
#t
> (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)))
bta-run
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
bta-solve done
> (writelpp genext "/tmp/regcompiler2.scm")
> (load "/tmp/regcompiler2.scm")
/tmp/regcompiler2.scm
> (specialize-$goal exported-labels 3)
'(main-1 x2 x4)
Here is the startup code for the compiled program: 
> (p *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 *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)
   mlet-3))
Here is the code for the second module: 
> (continue 'mod2 module2)
> (p *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.

4   Reference manual

4.1   Notation

The syntax definition uses an extended BNF where all symbols are terminals, except

4.2   Type system

The type system is the system of simple types with a type and recursion. The type language comprises the types The PGG system performs type inference for this system using Henglein's algorithm [14]. Due to the presence of recursive types, the result of the type inference is a graph where each node is annotated with a type constructor.

4.3   Binding-time analysis

The binding-time analysis assigns a binding-time to each node in the type graph and ensures that the binding-time assignment is well-formed. Wellformedness of such a binding-time assignment B means that the annotation on a type node is always less than or equal to the annotations on the direct descendants of that node. A node of type is well-formed if it assumes the maximum possible binding time (it is kept dynamic throughout all stages of specialization). That means that potential type clashes are postponed to the last stage of running the program.

The binding-time analysis inserts a lift-expression on top of each expression of basic type that occurs as A lift-expression injects a value computed at specialization time into the residual program.

4.4   Primitive operations

For primitive operations, the binding time analysis imposes a second set S of binding-time annotations on the nodes of the type graph. The well-formedness criterium for them has two aspects. First, the S annotation is always greater than or equal to the B annotation. Second, the S annotation of a node is greater than or equal to the S annotations of each direct descendant node in the type graph. For each expression that performs a primitive operation, the specializer requires that all arguments are leveled. That is, the binding time analysis enforces that the S and B annotations of all arguments are equal. In consequence, all argument computations take place at the same binding time (see [31]).

This restriction makes it safe to allow primitive operations to have functions as arguments.

4.5   Representation analysis

PGG performs a representation analysis that assigns to each node in the type graph yet another binding time M. The M annotation of a type is wired in such a way that it reflects the maximum level +1 at which expressions of that type will be subject to memoization, 0 if they are never memoized. For example, an expression of a type with an M value of 0 will never be memoized. All those expressions will use the standard representation of values of that type. If the B annotation is zero and the M value is greater than zero, the memoized representation will be used, which incurs a runtime overhead. The general condition is that expressions with B<M use the memoized representation and the others use the standard representation.

Unfortunately, there is a catch: if a type is memoized and at the same time required to be leveled then the type must assume the maximum binding time. This is, because primitive operations cannot deal with the memoized representation. The catch is that we now have a cyclic dependency: B implies the placement of memoization points, which implies a setting of M, which implies a deteriorated setting of B, which implies the placement of more memoization points, and so on.

4.6   Memoization

PGG automatically inserts memoization points on top of dynamic conditionals and on top of dynamic lambdas. However, this only happens if the branches of the dynamic conditional or the body of the dynamic lambda contains a control transfer at specialization time, i.e., a static function call. Furthermore, if several of these are nested in an expression, only the outermost receives a memoization point. This is a slight refinement of the standard strategy [3, 2].

It is possible to turn this feature off for a given function by defining it using define-without-memoization (see 4.9.1). In any case, memoization points can be defined and inserted manually (see 4.9.5).

4.7   Special operators

4.7.1   eval

The binding-time analysis and the specializer treat eval specially. The binding-time analysis enforces that the argument of eval is leveled. The result type is also leveled and it may have any binding time that is greater than or equal to the argument's binding time.

If the binding times are equal then the eval function is called at the specified level. If the binding times differ by one then the specializer simply drops the static argument value into the residual program. Otherwise, the specializer preserves the static argument for the next level and decrements the binding-time difference.

4.7.2   apply

If a function is declared as the apply function (see 4.9.4) then the specializer uses a special postprocessor that transforms expressions of the form 
(apply f (cons x1 (cons x2 (cons x3 ...))))
into 
(f x1 x2 x3 ...)
To this end, it is necessary to declare cons as pure (see 4.9.4).

4.8   Predefined operators

These operators can be used in source programs.

The module cogen-boxops exports the following operators that manipulate references (boxed values): 
(make-cell exp)
allocates a new mutable reference cell which initially contains the value of exp. Returns the reference to the new cell. 
(cell-ref exp)
returns the value stored in the referenced cell if exp evaluates to a reference. 
(cell-set! exp1 exp2)
stores the value of exp2 in the cell referenced by exp1 provided this value is a reference. The return value is unspecified.

4.9   Directives

The directives are only allowed at the top-level of a source program.

4.9.1   define-without-memoization

D ::= (define-without-memoization (P V*) D0* E*)
  |   (define-without-memoization P E)
Define procedure P. The specializer does not to automatically insert memoization points in the body of P.

4.9.2   define-data

D ::= (define-data TC (C Ci*)+)
  |   (define-data TC hidden (C Ci*)+)
Define the algebraic datatype TC with constructors C and selectors Ci. In addition, constructor test operations C? are defined. The name TC is used during type checking to check for equality of types.

For example, the declaration 
(define-data list
  (nil)
  (cons car cdr))
defines the constructors nil (nullary) and cons binary, the constructors tests nil? and cons?, and the selectors car and cdr.

The binding-time analysis considers algebraic datatypes as partially static, i.e., the arguments of a constructor can have a different (higher) binding time than the constructor itself. In such cases, the specializer performs arity raising when appropriate. The constructors, selectors, and test operations are binding-time polyvariant, i.e., each use of such an operation may have a different binding-time pattern.

The second form of define-data declares a datatype whose elements are ignored by the memoization mechanism. This is a potentially dangerous feature because it can change the meaning of a program during specialization by cheating the memoization mechanism.

4.9.3   define-type

D ::= (define-type (P B*) B)
Declares the arity of primitive operation P. The actual values of the Bs are currently ignored.

Example: 
(define-type (cons * *) *)
declares the operator cons of arity 2.

A variable which is declared as an operator but does not occur at operator position in an expression is eta-expanded by the frontend according to its declaration.

4.9.4   define-primitive

D ::= (define-primitive O T [dynamic|error|opaque|pure|apply])
Declares the operator O of type T with an optional property.

The parameter T declares the type of the operator. It can be either -, indicating that the type of O is not restricted, or it can specify a polymorphic type for O. The grammar is as follows: 
T  ::=  - | T0
T0 ::=  (all TV T0) | (rec TV T0) | (TC T0*) | TV
Here, TV stands for a type variable (an arbitrary symbol) and TC stands for a type constructor (an arbitrary symbol). The syntax, (all TV T0), declares that variable TV is all-quantified in T0, like " alpha.t0. The syntax, (rec TV T0), declares a recursive type, like µa.t0. The remaining cases are type constructor application and occurrence of a type variable. For convenience, the function type constructor, ->, is treated specially. Writing (-> t1 ... tn t0) declares a Scheme function that takes n parameters (n ³ 0) and delivers a result of type t0. The properties dynamic, error, opaque are synonyms. Each of them forces the binding time of O to be dynamic. The remaining properties advise the specializer what to do when it residualizes the operator. The pure property states that the operator does not have side effects. Instead of creating a let-binding for the expression (O V*), the specializer will treat it as a value, potentially discarding or duplicating the expression. The apply property states that the operator O is the apply function as defined in the Scheme standard.

4.9.5   define-memo

D ::= (define-memo M Number [Active])
  |   (define-memo M Number 'deferred)
Defines M as a unary operator indicating a memoization point at level Number. This is also the binding time of the memoization point. For two-level specialization this number is 1. Useful in connection with define-without-memoization. The optional parameter Active defines the minimum level of specialization at which the specialization point is active. The default is 0, that is, the specialization point is always active. Useful in connection with multi-level specialization if the same program is specialized with different levels.

Both parameters, Number and Active may be integer expressions using the free variable max-level, which is bound to the maximum binding-time presently in use.

Example: Similix defines the operator _sim-memoize as an indicator for memoization points. To achieve the same behavior in PGG requires the following declaration. 
(define-memo _sim-memoize 1)
The second form of the directive declares an operator to construct deferred memoization points. An applied occurrence of a deferred memoization point has the form 
(M V E)
When specialization hits upon a deferred memoization point, it extracts the static skeleton and looks it up in a secondary cache. Just as with standard memoization points, it creates a function call to a specialized version of E. The difference is that the specialization of E depends on a future value of V, so it must be deferred until the value of V becomes available.

4.9.6   load

D ::= (load Filename)
includes the contents of the file named by the string Filename into the program. The included file may contain additional loads, without limit on the nesting level. The Filename argument is always interpreted relative to the current directory that Scheme48 is running in.

4.9.7   begin

D ::= (begin D*)
As in Scheme, top-level definitions may appear nested inside a begin. This is handy if a macro is to expand to more than one definition.

4.10   Commands

This section summarizes the available top-level commands of the PGG system.

4.10.1   Creating a generating extension

The main entry point of the system is the function cogen-driver. It takes the following parameters 
(cogen-driver InputSpec BindingTimeSkeleton)
where A binding time is a non-negative integer, with 0 denoting static. The PGG system assumes that the binding time of the result of the main function is the maximum of 1 and the binding times of the function's parameters, i.e., the BindingTimeSkeleton.

The result of calling cogen-driver is a generating extension, i.e., a list of Scheme definitions that can be loaded and run.

This function is defined in module pgg. If it is not accessible try 
> ,open pgg
at the top-level Scheme48 prompt.

A number of optional parameters may be specified after the BindingTimeSkeleton argument. They allow the generation of the generating extension as a Scheme48 module. The following options are recognized.

4.10.2   Running a generating extension

The function specialize is the human interface to running a generating extension. It has two forms. 
(specialize GenextMain BindingTimeSkeleton ARGS)
and 
(specialize BindingTimeSkeleton ARGS NEW-GOAL)
where The result is a call template for the specialized function, a list consisting of the name of the function and of names of the arguments. The residual program is left in the variable *residual-program*. It is a list of Scheme definitions. Furthermore, the variable *support-code* contains additional code, for example data definitions that are necessary to run the specialized program.

If the returned call template has the form 
'(multi-memo Level 'Goal Goal Bts Args)
then we have done one step of a multi-level specialization [13]. It means that the residual program is again a generation extension where Level is a number, Goal is the name of the entry point, Bts are the binding times of the arguments, and Args is a list of symbols of the same length. It can be loaded as usual and specialized again with specialize by constructing the BindingTimeSkeleton from Goal and Bts.

This function is defined in module pgg-residual. If it is not accessible try 
> ,open pgg-residual
at the top-level Scheme48 prompt.

4.10.3   Continuing a specialization

The function continue continues a specialization that has been suspended at a deferred memoization point. 
(continue Name Arg)
The parameter Name identifies the index that the specialization waits for. It is used to match the index value in pending deferred memoization points. The example in Section 3.6 uses the string "mods" for this purpose.

The parameter Arg is the indexed value. This is a value of base type and its representation is completely up to the programmer. The example in Section 3.6 uses the empty list to indicate an empty world.

4.10.4   Suspend a deferred specialization

The function suspend writes the current memoization cache and the cache of deferred specializations to a file. 
(suspend Filename)
The Filename parameter indicates the name of the file in which the memoization cache and the deferred cache are stored.

4.10.5   Resurrect a deferred specialization

The function resurrect installs a memoization cache and deferred cache from a file. It sets up the system to continue a previously suspended specialization. 
(resurrect Filename)
The Filename parameter indicates the name of the file in which the memoization cache and the deferred cache are stored.

Returns #t if the file was successfully read. Otherwise, it returns #f.

4.11   Settable options

These options are accessible in module cogen-globals except where otherwise noted. Some of them only make sense for programmers who want to use the frontend separately.

4.12   Utilities

Pretty printing is available through function p in module pretty-print. The function takes one parameter, the expression that is to be pretty-printed.

The function (writelpp LIST FILE) writes the list LIST to file FILE applying the pretty printer to each element of the list. It is defined in module auxiliary.

The contents of modules are generally available by typing 
> ,open Modulename
to the top-level command line interpreter of Scheme48.

5   Differences to Scheme

PGG assumes a declarative semantics: the order of a sequence of top-level definitions does not matter, even if they are spread over several files.

PGG implements R5RS macros with the restriction that macros defined by let-syntax and letrec-syntax cannot expand to macro definitions.

6   Reading a generating extension

For debugging purposes it is sometimes helpful to read the generating extension, because it is a representation of the binding-time annotated program. Besides standard Scheme constructs it contains the following kinds of expressions, most of which are implemented as macros in module pgg-library. The semantics of the ellipsis ... is the same as in the syntax-rules patterns of Scheme [19], zero or more repetitions of the preceding item. The list is sorted alphabetically.

7   Technical background

7.1   Partial evaluation in general

Good starting points for the study of partial evaluation are Jones, Gomard, and Sestoft's textbook [18], Consel and Danvy's tutorial notes [6], Mogensen and Sestoft's encyclopedia chapter [23], and Gallagher's tutorial notes on partial deduction [12]. Further material can be found in the proceedings of the Gammel Avernæs meeting (PEMC) [1, 11], in the proceedings of the ACM conferences and workshops on Partial Evaluation and Semantics-Based Program Manipulation (PEPM) [15, 4, 25, 27, 24, 5, 8], and in special issues of various journals [16, 17, 21, 28]. A comprehensive volume on partial evaluation appeared in the Lecture Notes of Computer Science series [9]. Sestoft maintains an online bibliography [26].

The above paragraph is taken from the introduction to the 1998 Symposium on Partial Evaluation [10] which is a collection of concise articles characterizing the state of the art, stating challenging problems, and outlining promising directions for future work in partial evaluation.

7.2   Directly related publications

The following publications explain various parts of the PGG system.

7.3   Structure of the implementation

The frontend of PGG is similar to the frontend of a Scheme compiler.

The first pass renames all variables, expands macros, expands backquotes, transforms named lets to letrecs, and collects mutable variables. The second pass performs assignment conversion, eliminating all (set! v e) operations in favor of (cell-set! v e'), replacing all uses of v by (cell-ref v), and changing the definition of v accordingly. The third pass performs lambda lifting. The fourth pass transforms to abstract syntax and performs eta expansion.

The next phase is binding-time analysis. It consists of type inference, effect analysis (if cell-set! and friends have been used), construction of the binding-time constraints, solution of the constraints, and the introduction of memoization points.

Finally, the backend produces the generation extension.

8   Known problems

Acknowledgments

Most parts of the system have been developed while the author was at Tübingen University. Special thanks to Michael Sperber for unwaveringly testing the system, pushing it to its limits, suggesting new features, finding many problems (as well as some surprising features), and supplying some bug fixes. Thanks also to Simon Helsen and Frank Knoll who suffered through various versions of the system.

References

[1]
Dines Bjørner, Andrei P. Ershov, and Neil D. Jones, editors. Partial Evaluation and Mixed Computation, Amsterdam, 1988. North-Holland.

[2]
Anders Bondorf. Automatic autoprojection of higher order recursive equations. Science of Computer Programming, 17:3--34, 1991.

[3]
Anders Bondorf and Olivier Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming, 16(2):151--195, 1991.

[4]
Charles Consel, editor. Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation PEPM '92, San Francisco, CA, June 1992. Yale University. Report YALEU/DCS/RR-909.

[5]
Charles Consel, editor. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '97, Amsterdam, The Netherlands, June 1997. ACM Press.

[6]
Charles Consel and Olivier Danvy. Tutorial notes on partial evaluation. In Proc. 20th Annual ACM Symposium on Principles of Programming Languages, pages 493--501, Charleston, South Carolina, January 1993. ACM Press.

[7]
Olivier Danvy. Semantics-directed compilation of nonlinear patterns. Information Processing Letters, 37(6):315--322, March 1991.

[8]
Olivier Danvy, editor. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '99, San Antonio, Texas, January 1999. To appear.

[9]
Olivier Danvy, Robert Glück, and Peter Thiemann, editors. Dagstuhl Seminar on Partial Evaluation 1996, volume 1110 of Lecture Notes in Computer Science, Schloß Dagstuhl, Germany, February 1996. Springer-Verlag.

[10]
Olivier Danvy, Robert Glück, and Peter Thiemann, editors. 1998 Symposium on Partial Evaluation, volume 30 of ACM Computing Surveys. ACM Press, September 1998.

[11]
Andrei P. Ershov, Dines Bjørner, Yoshihiko Futamura, K. Furukawa, Anders Haraldsson, and William Scherlis, editors. Special Issue: Selected Papers from the Workshop on Partial Evaluation and Mixed Computation, 1987 (New Generation Computing, vol. 6, nos. 2,3). Ohmsha Ltd. and Springer-Verlag, 1988.

[12]
J. Gallagher. Tutorial on specialisation of logic programs. In Schmidt [25], pages 88--98.

[13]
Robert Glück and Jesper Jørgensen. Efficient multi-level generating extensions for program specialization. In Doaitse Swierstra and Manuel Hermenegildo, editors, International Symposium on Programming Languages, Implementations, Logics and Programs (PLILP '95), volume 982 of Lecture Notes in Computer Science, pages 259--278, Utrecht, The Netherlands, September 1995. Springer-Verlag.

[14]
Fritz Henglein. Efficient type inference for higher-order binding-time analysis. In John Hughes, editor, Proc. Functional Programming Languages and Computer Architecture 1991, volume 523 of Lecture Notes in Computer Science, pages 448--472, Cambridge, MA, 1991. Springer-Verlag.

[15]
Paul Hudak and Neil D. Jones, editors. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '91, New Haven, CT, June 1991. ACM. SIGPLAN Notices 26(9).

[16]
Journal of Functional Programming 3(3), special issue on partial evaluation, July 1993. Neil D. Jones, editor.

[17]
Journal of Logic Programming 16 (1,2), special issue on partial deduction, 1993. Jan Komorowski, editor.

[18]
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.

[19]
Richard Kelsey, William Clinger, and Jonathan Rees. Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7--105, 1998. Also appears in ACM SIGPLAN Notices 33(9), September 1998. Available electronically as .

[20]
Richard A. Kelsey and Jonathan A. Rees. A tractable Scheme implementation. Lisp and Symbolic Computation, 7(4):315--335, 1995.

[21]
Lisp and Symbolic Computation 8 (3), special issue on partial evaluation, 1995. Peter Sestoft and Harald Søndergaard, editors.

[22]
Julia L. Lawall and Peter Thiemann. Sound specialization in the presence of computational effects. In Proc. Theoretical Aspects of Computer Software, volume 1281 of Lecture Notes in Computer Science, pages 165--190, Sendai, Japan, September 1997. Springer-Verlag.

[23]
Torben Æ. Mogensen and Peter Sestoft. Partial evaluation. In Allen Kent and James G. Williams, editors, Encyclopedia of Computer Science and Technology, volume 37, pages 247--279. Marcel Dekker, 270 Madison Avenue, New York, New York 10016, 1997.

[24]
William Scherlis, editor. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '95, La Jolla, CA, June 1995. ACM Press.

[25]
David Schmidt, editor. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '93, Copenhagen, Denmark, June 1993. ACM Press.

[26]
Peter Sestoft. Bibliography on partial evaluation. Available through URL ftp://ftp.diku.dk/pub/diku/dists/jones-book/partial-eval.bib.Z.

[27]
Peter Sestoft and Harald Søndergaard, editors. Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation PEPM '94, Orlando, Fla., June 1994. University of Melbourne, Australia. Technical Report 94/9, Department of Computer Science.

[28]
Theoretical Computer Science, special issue on partial evaluation, 1998. Charles Consel, editor.

[29]
Peter Thiemann. Cogen in six lines. In R. Kent Dybvig, editor, Proc. International Conference on Functional Programming 1996, pages 180--189, Philadelphia, PA, May 1996. ACM Press, New York.

[30]
Peter Thiemann. Implementing memoization for partial evaluation. In Herbert Kuchen and Doaitse Swierstra, editors, International Symposium on Programming Languages, Implementations, Logics and Programs (PLILP '96), volume 1140 of Lecture Notes in Computer Science, pages 198--212, Aachen, Germany, September 1996. Springer-Verlag.

[31]
Peter Thiemann. Towards partial evaluation of full Scheme. In Gregor Kiczales, editor, Reflection'96, pages 95--106, San Francisco, CA, USA, April 1996.

[32]
Peter Thiemann. Correctness of a region-based binding-time analysis. In Proc. Mathematical Foundations of Programming Semantics, Thirteenth Annual Conference, volume 6 of Electronic Notes in Theoretical Computer Science, page 26, Pittsburgh, PA, March 1997. Carnegie Mellon University, Elsevier Science BV. URL: .

Index

1
In partial evaluation, that is.
This document was translated from LATEX by HEVEA.