# source:project/wiki/eggref/4/scheme0-pe@30721

Last change on this file since 30721 was 30721, checked in by Ivan Raikov, 7 years ago

scheme0-pe initial documentation

File size: 6.4 KB
Line
1[[tags: egg]]
2[[toc:]]
3
4== scheme0-pe
5
6=== Introduction
7
8The {{scheme0-pe}} egg is a variant of the {{Scheme0}} partial
9evaluator adapted for Chicken. {{Scheme0}} is a first-order pure
10subset of Scheme described in the book [[Partial Evaluation and
11Automatic Program Generation|http://www.itu.dk/people/sestoft/pebook/pebook.html]].
12
13=== Notation
14
15The following notation is used in this documentation:
16
17; {{program}} : is a plain {{Scheme0}} program
18; {{annprogram}} : is an annotated (two-level) {{Scheme0}} program
19; {{sdpattern}} : is a tuple of argument binding times {{S}} and {{D}}
20; {{division}} : is a possibly polyvariant division
21; {{staticinputs}} : is a tuple of static argument values
22
23
24=== Procedures
25
26
27<procedure>monodiv program sdpattern</procedure>
28
29Does a monovariant binding time analysis of the subject program
30program, given the binding times sdpattern of its goal
31function. Returns the resulting monovariant division.
32
33<procedure>polydiv program sdpattern</procedure>
34
35Similar to {{monodiv}}, but does a polyvariant binding time
36analysis. Returns the resulting polyvariant division.
37
38<procedure>annotate program division</procedure>
39
40Annotates the {{Scheme0}} program according to the monovariant or
41polyvariant division. May make several copies of each function for a
42polyvariant division. Returns the annotated two-level {{Scheme0}}
43program or reports that division is not congruent.
44
45<procedure>monotate program sdpattern</procedure>
46
47Does monovariant binding time analysis and an- notation of program
48given the binding times sdpattern of its goal function.  Returns the
49annotated two-level {{Scheme0}} program.
50
51<procedure>polytate program sdpattern</procedure>
52
53Similar to {{monotate}} but performs polyvariant binding time analysis and
54annotation. Returns the annotated two-level {{Scheme0}} program.
55
56<procedure>spec annprogram staticinputs</procedure>
57
58Specializes the annotated annprogram with respect to the list
59{{staticinputs}} of static argument values. Returns the residual {{Scheme0}}
60program.
61
62<procedure>monope program sdpattern staticinputs</procedure>
63
64Does a monovariant binding time analysis and annotation of program,
65then specializes it with respect to the given static inputs
66{{staticinputs}}. Returns the residual {{Scheme0}} program.
67
68<procedure>polype program sdpattern staticinputs</procedure>
69
70Similar to {{monope}} but does polyvariant binding time analysis and
71annotation. Returns the residual {{Scheme0}} program.
72
73<procedure>make f program</procedure>
74
75Converts program from {{Scheme0}} to Scheme and defines a Scheme
76function f to invoke the converted program. Returns the name f.  Side
77effect: Defines function f. This is for executing residual {{Scheme0}}
78programs.
79
80<procedure>scheme program</procedure>
81
82Converts program from {{Scheme0}} to Scheme, possibly renaming
83functions. Returns a list of Scheme function definitions. This is for
84studying residual Scheme0 programs.
85
86
87=== Representation of Scheme0 programs
88
89A program must have at least one definition, and function definitions
90may have zero or more arguments.
91
92 program ::= (def ... def)
93
94 def ::= (define (funcname var ... var) exp)
95
96 exp ::= ()
97 | number
98 | var
99 | (quote S-expression)
100 | (if exp exp exp)
101 | (call funcname exp ... exp)
102 | (op basefunction exp ... exp)
103
104Variables are Scheme symbols, that is, non-numeric atoms different
105from ().  Function names may also be simple Scheme symbols, but in
106residual programs, a function name is a pair {{(annotatedname
107. staticvalues)}} of an annotated function name and the values of the
108function's static arguments for this variant. Annotated function names
109are those found in the annotated subject programs given to the
110specializer.
111
112=== Representation of two-level Scheme0 programs
113
114
115 program ::= (def ... def)
116
117 def ::= (define (funcname (var ... var) (var ... var)) exp)
118
119 exp ::= ()
120 | number
121 | var
122 | (quote S-expression)
123 | (ifs exp exp exp)
124 | (ifd exp exp exp)
125 | (calls funcname (exp ... exp) (exp ... exp))
126 | (calld funcname (exp ... exp) (exp ... exp))
127 | (ops basefunction exp ... exp)
128 | (opd basefunction exp ... exp)
129 | (lift exp)
130
131A variable is a Scheme symbol as above, but a function name must have
132the form: {{((f . dynvaroccs) . sdpattern)}}.
133
134Here {{f}} is a function name from the {{Scheme0}} subject program;
135{{dynvaroccs}} is a list of the number of occurrences of {{f}}'s
136dynamic parameters; and {{sdpattern}} describes the binding times of
137the parameters of this variant of {{f}}. Thus {{f}} is a Scheme
138symbol; {{dynvaroccs}} is a list of 0, 1, or 2, where 2 represents any
139number greater than 1; and {{sdpattern}} is a list of {{S}} and {{D}}.
140
141The {{sdpattern}} component is used to distinguish the binding time
142variants of {{f}} and is present also in monovariantly annotated
143programs. The {{dynvaroccs}} component is used to avoid unfolding
144static calls to {{f}} when this may cause duplication of a non-trivial
145non-variable dynamic argument expression. This component could in
146principle be computed during specialization, in which case it need not
147be part of the function name, but this would incur unnecessary
148recomputation, so we choose to compute it when annotating the program.
149
150=== Examples
151
152 (use scheme0-pe)
153
154 (define ack '(
155   (define (ack m n)
156     (if (op equal? m 0) (op + n 1)
157        (if (op equal? n 0)
158            (call ack (op - m 1) 1)
159            (call ack (op - m 1) (call ack m (op - n 1)))))
160   )))
161
162 (pp (scheme ack))
163 (pp (scheme (monope ack '(S D) '(4))))
164
165
166=== Authors
167
168The Scheme0 partial evaluator is described in Chapter 5 and Appendix A
169of the book:
170
171 N.D. Jones, C.K. Gomard, and P. Sestoft,
172 Partial Evaluation and Automatic Program Generation.
173 Prentice Hall International, June 1993.  xii + 415 pages. ISBN 0-13-020249-5.
174
175Available from http://www.itu.dk/people/sestoft/pebook/pebook.html
176
177=== Version
178
179; 1.0 : Initial version
180
182
183 This program is free software; you can redistribute it and/or
184 modify it under the terms of the GNU General Public License