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

I am reading through Dybvig's thesis and it's very clearly written and
helpful. (I only hope my own thesis is as useful to someone in the future).

Jens's tip will help a lot. I have a very stupid representation for all my
values right now. Perhaps making it slightly more clever will give me the
enough speed up to not worry about performance anymore.

And, now that I check, yes I am in fact type-checking the list structure
during variable lookup, which is completely unnecessary. That might be why
the profiler is telling me that all the overhead is coming from
typechecking. Thank you!

  -Patrick

On Mon, Mar 21, 2011 at 2:43 PM, Jens Axel Søgaard <jensaxel at soegaard.net>wrote:

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