[plt-scheme] Stylistic (I hope!) question regarding driver loop

At Sat, 21 Jan 2006 17:41:25 -0500, Felix Klock's PLT scheme proxy wrote:
> Robby: does the Scheme semantics you and Jacob did in PLT Redex have
> a gc-step? Do your examples run in that context? Perhaps that would
> help Greg see what is going on in your example programs.

It does not, neither does it have letrec (since letrec is defined as
derived form, in terms of let and set!). Probably looking at that
semantics is the wrong thing anyways, since it really helps when you
want to understand how lots of features come together and here we're
really only interested in a few.

So, I've put together a semantics for letrec (including gc'ing the
store), where letrec is reduced in a single step to the corresponding
let+set! (note that this is a reduction step, not a macro, but it still
helps understand what's going on, I believe). Here's the rule:

  (letrec ((x e1)) e1) --> (let ((x 0)) (begin (set! x e1) e2))

and set! is modeled with a global store, so the rewriting system
rewrites terms like this:

  ((store (x v) ...) e)

For example:

    ((store (x 1)) (+ (set! x (+ x x)) x))
--> ((store (x 1)) (+ (set! x (+ 1 x)) x))
--> ((store (x 1)) (+ (set! x (+ 1 1)) x))
--> ((store (x 1)) (+ (set! x 2) x))
--> ((store (x 2)) (+ 2 x))
--> ((store (x 2)) (+ 2 2))
--> ((store (x 2)) 4)

To avoid adding void, set!'s reduce to their right-hand-sides (after
doing the assignment) and letrec initializes its variable to 0.

I ran in the two examples from earlier, replacing define with a letrec
and grabbed screenshots:

http://people.cs.uchicago.edu/~robby/tmp/letrec-tail.png
http://people.cs.uchicago.edu/~robby/tmp/letrec-nontail.png

You can see that the first one makes a loop; this means that the
program runs foever, but it only visits a finite number of states, so
it doesn't allocate memory forever. In contrast, the second one
produces an infinite number of states, and they grown over time, so it
needs an infinite amount of storage.

If you want to see more examples yourself, or play around with it
somehow, look at letrec.ss in the examples directory of the version 1.2
of plt redex in planet. You'll need the latest nightly build (assume
the build succeeded last night) or to build from svn yourself.

Robby