[racket] I've implemented a Scheme Interpreter. But it's too slow. Next step?

2011/3/21 Patrick Li <patrickli.2001 at gmail.com>:
> Thanks for all the suggestions! I'll look over those and see what's
> happening.
> I have profiled my code, and noticed that it spends most of the time in
> typechecking the arguments to the cons, car, and cdr primitives. I currently
> know of no simple way to eliminate those checks while still giving me
> relatively sane error messages for when things go wrong.

Which representation do you use? Maybe you can speed up the type checks,
by choosing a clever representation.

A common trick is to embed type information into the pointers.
In the representation used in the 1996 Scheme Workshop pointers to cons
cells contains 010 in their lower 3 bits. A type check is thus compiled
to a very fast and instruction.

http://www.cs.indiana.edu/eip/compile/back.html

-- 
Jens Axel Søgaard


>   -Patrick
>
> On Mon, Mar 21, 2011 at 1:39 PM, Vincent St-Amour <stamourv at ccs.neu.edu>
> wrote:
>>
>> David Kranz's dissertation has a lot of interesting material about
>> implementing closures efficiently.
>> http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf
>>
>> Andrew Appel's book Compiling with Continuations also covers similar
>> material.
>>
>> Vincent
>>
>> At Mon, 21 Mar 2011 12:42:07 -0400,
>> Patrick Li wrote:
>> >
>> > [1  <multipart/alternative (7bit)>]
>> > [1.1  <text/plain; ISO-8859-1 (7bit)>]
>> > Hello everyone,
>> >
>> > For educational purposes, I've implemented a simple Scheme interpreter
>> > in C,
>> > but it's way too slow at the moment. (eg. just macroexpanding and
>> > evaluating
>> > a function definition takes a few seconds.) I would like some advice on
>> > how
>> > to proceed next to get a adequately performing Scheme system.
>> >
>> > My goal is simply to get out of C as quickly as possible. ie. Get the
>> > basic
>> > forms and a macro system working which will allow me to write the rest
>> > of it
>> > in Scheme.
>> >
>> > So far this is what I have done:
>> >
>> > I wrote a simple Scheme interpreter in Scheme in continuation-passing
>> > style,
>> > so that I can get call/cc working.
>> >
>> > Then I basically just manually translated that code into C. So all
>> > continuations are heap allocated.
>> >
>> > How should I proceed from here? These are the options that I've come up
>> > with:
>> >
>> > (1) Optimize variable lookup. Currently the environment is represented
>> > as a
>> > list of key-value pairs. Variable lookup is done by searching through
>> > the
>> > list.
>> >
>> > (2) "Analyze" the code before evaluating it (ie. as in SICP). Ie. for an
>> > (if) form, it will determine that it is an if form during the analysis
>> > phase, so that at execution stage it won't have to repeatedly figure out
>> > what sort of form it is.
>> >
>> > (3) Write a very simple VM, and develop a simple byte-code compiler.
>> >  The
>> > problem here is that I don't really know how to deal with first-class
>> > continuations.
>> >
>> > Thanks for your help
>> >   -Patrick
>> > [1.2  <text/html; ISO-8859-1 (quoted-printable)>]
>> >
>> > [2  <text/plain; us-ascii (7bit)>]
>> > _________________________________________________
>> >   For list-related administrative tasks:
>> >   http://lists.racket-lang.org/listinfo/users
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>



-- 
--
Jens Axel Søgaard