Mon, 9 Sep 91 13:41:28 GMT

Related articles |
---|

Scheme partial evaluator Similix ftp-available anders@diku.dk (1991-09-09) |

Newsgroups: | comp.compilers |

From: | anders@diku.dk (Anders Bondorf) |

Keywords: | Scheme, FTP, optimize |

Organization: | Department of Computer Science, U of Copenhagen |

Date: | Mon, 9 Sep 91 13:41:28 GMT |

-----------------------------------------------------

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.