-----------------------------------------------------
-----------------------------------------------------
Self-applicable partial evaluator for a Scheme subset
Similix
available via anonymous ftp
-----------------------------------------------------
-----------------------------------------------------
The partial evaluator Similix developed at DIKU, University of
Copenhagen, Denmark, is now available via anonymous ftp.
-----------------------------------------------------------------------------
Partial Evaluation
------------------
Partial evaluation has been a rapidly growing area within the last
decade, as recently seen at the ACM-SIGPLAN/IFIP Symposium on Partial
Evaluation and Semantics-Based Program Manipulation (Yale University,
New Haven, Connecticut, June 17-19 1991), and at the Conference on
Functional Programming Languages and Computer Architecture (Harvard
University, Cambridge, Massachusetts, August 28-30, 1991).
Partial evaluation transforms programs with incomplete input data:
when given a source program p and a part of its input s, a partial
evaluator mix generates a so-called residual program p_s by
specializing p with respect to s. Partial evaluation is also referred
to as program specialization. When applied to the remaining input d,
the residual program gives the same result as the source program would
when applied to the complete input:
p(s,d) = p_s(d) where p_s = mix(p,s)
The main point in partial evaluation is one of efficiency: running the
residual program p_s can be much faster than running the source
program p. Instead of running p(s,d), it may therefore be worthwhile
first to generate p_s and then apply it to d. The partial evaluator
knows p and s and is therefore able to perform those of p's
computations that depend only on s. Program p_s is thus more efficient
than program p: it need not perform the computations that depend only
on s --- these have already been performed at partial evaluation time.
Some partial evaluators are self-applicable: we can use the partial
evaluator to optimize itself. We may thus generate p_s in an
alternative and more efficient way:
p_s = mix_p(s) where mix_p = mix(mix,p)
mix_p is a "program generator": given a value s for p's first input,
mix_p constructs program p_s (more efficiently than mix itself).
We may even go one step further: we can specialize mix with respect to
itself! This is done as follows:
mix_mix = mix(mix,mix)
We can then generate mix_p in a faster way by applying mix_mix:
mix_p = mix_mix(p)
Applications:
-------------
A well-known particular application of partial evaluation is automatic
compiler generation from interpreters: write an interpreter for a
programming language L and give it as input to the program mix_mix.
The result is a compiler from L to the language T that the specialized
programs generated by mix are written in.
Partial evaluation has been used for many other applications, for
instance:
-- optimizing neural networks;
-- optimizing computer graphics (ray-tracing);
-- optimizing numerical computations;
-- generating efficient pattern matchers;
-- generating parsers from grammars;
-- generating DFAs from regular expressions.
-----------------------------------------------------------------------------
General Description of Similix
------------------------------
Similix is an autoprojector (self-applicable partial evaluator) for a
higher order subset of the strict functional language Scheme. Similix
handles programs with user defined primitive abstract data type
operators which may process global variables (such as input/output
operators).
Similix is automatic, that is, no user annotations (such as unfolding
information) are required. Similix guarantees not to duplicate nor to
discard computations (discarding may change termination properties of
residual programs).
Because it handles higher order programs, Similix is well-suited for
partially evaluating for instance interpreters that use environments
represented as functions, and interpreters written in continuation
passing style. And since Similix is self-applicable, stand-alone
compilers can be generated from interpreters.
-------------------------------------
The Similix binding time debugger (developed by Christian Mossin)
gives information to the user to help rewriting source programs in
order to obtain better results by partial evaluation. Such rewritings
are often called "binding time improvements". The binding time
debugger is thus a tool for aiding manual binding time improving.
-----------------------------------------------------------------------------
The current distribution should enable you to run Similix on
Chez Scheme (version 2.0.3, 3.1, or 3.2)
[Cadence Research Systems, 1989]
and on
T (version 3.1 (13), Sun4/SPARC version)
[Yale University, 1989].
T is public domain.
Similix is is written in pretty much standard Scheme, so it should not
be too difficult to port it to other Scheme systems (earlier versions
of Similix have been ported to other Scheme systems).
How to ftp Similix:
-----------------------------------------------------------------------------
ftp ftp.diku.dk
login: anonymous
password: <your full e-mail address>
binary
hash
cd misc
get Similix.tar.Z
bye
-----------------------------------------------------------------------------
To decode the file Similix.tar.Z, run
uncompress < Similix.tar.Z | tar xvpf -
A directory named
Similix
then appears. Now read the file README in the Similix directory.
Best regards,
Anders Bondorf
DIKU, Department of Computer Science
University of Copenhagen
Universitetsparken 1
DK-2100 Copenhagen \O
Denmark
e-mail: ······@diku.dk
-----------------------------------------------------------------------------