Scheme partial evaluator Similix ftp-available

-----------------------------------------------------
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: anders@diku.dk
--

Return to the comp.compilers page.
Search the comp.compilers archives again.