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

From: Patrick Li (patrickli.2001 at gmail.com)
Date: Mon Mar 21 13:49:37 EDT 2011

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.

  -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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110321/f3312211/attachment.html>

Posted on the users mailing list.