Home » forums » LtU Forum

SECD Machine - RAP?

I started writing a toy implementation of the SECD implementation based on the description at Wikipedia but I'm stuck at the RAP instruction. I can't figure out how to implement it. I've asked on StackOverflow.com but no responses. I've looked at Olivier Danvy's deconstruction of the SECD machine but I can't relate it to the more imperative description on Wikipedia (maybe my understanding of ML is just too weak).

Is RAP just the tail-recursive version of the apply function? If so then I get it, but the description sounds like something else. Thanks in advance!

By cdiggins at 2011-10-02 01:40 | LtU Forum | previous forum topic | next forum topic | other blogs | 9097 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

SECD is not tail recursive,

SECD is not tail recursive, although you can build a tail recursive SECD machine (PDF).

The AP instruction is used to compile a 'let' binding whereas the RAP instruction is used to compile a 'letrec' binding.

'letrec' is different from 'let' because you can 'see' the environment where the recursive function is defined, so that you can call it recursively (so, for instance, you define a 'factorial' function and you can call it in the body of the function).

RAP modifies the environment by calling rplaca (similar to setcar! in Scheme). A previous DUM instruction adds a "dummy" car to the environment (which is never used), and RAP removes this "dummy" 'car' in the environment and replaces it with the appropriate one.

State transitions are like so:

((c'.e')v.s) e               (AP.c)  d         =>
NIL          (v.e')          c'      (s e c.d)

((c'.e')v.s) (?.e)           (RAP.c) d         =>
NIL          (setcar! e',v)  c'      (s e c.d)

See also Revisiting SECD and the power of Lisp, quoting:

The RAP instruction is used to support recursive function calls and works by replacing a previously created dummy environment on the stack, called OMEGA, by one which contains all the functions that are visible in the recursive scope. The specification uses RPLACA to denote that replacement operation, and that is what we used in our Lisp implementation of SECD, too: ...

and

When trying to implement RAP in Erlang, I got stuck because there are no destructive operations on lists. Not in the standard API, and seemingly not in the system API either. So, the Erlang SECD looks nice, only it does not run.

Posted in Stackoverflow too.

By vieiro at Sun, 2011-10-02 06:32 | login or register to post comments

Now that's an answer

(I apologize for my own zero-content contribution to this discussion, as this comment is really a meta-statement, following up on a previous recent discussion on LtU). My favourite LtU is the one where something like 70% of the answers are like the one above. If you wish to discuss this particular statement of mine, please do it on the original thread and not here!

By Jacques Carette at Sun, 2011-10-02 13:37 | login or register to post comments

Prototypical LtU comment?

It's a great answer, sure, but I think it's wrong to expect that 70% of comments are going to be of the form "here is the right answer to the well posed question you asked." This isn't language-overflow. The format of LtU (which you well know, having been here much longer than I have) is that someone posts a link to an interesting article along with some editorial commentary intended to spur discussion. Questions posed in that commentary, if present at all, are often open ended in nature and not seeking a specific answer.

For that reason, I don't think the grandparent post should be taken as the exemplar of good posting. The most interesting discussion to me typically surrounds recently published articles, providing links to other work, adding context that makes the article more accessible and asking good questions. Such discussion is typically not in question/answer form.

I take your point on the signal/noise ratio, but remember the numerator is as important as the denominator. Maybe it's because the noise has driven good people away, but too often these calls for better posts just lead to cricket noises and tumbleweed. They would probably work better if accompanied by a surge in high quality articles and commentary.

I'll pass along the "do as I say, not as I do" admonishment that none of this belongs here to the next responder: replies should go here. :)

By Matt M at Mon, 2011-10-03 12:00 | login or register to post comments

Great answer, thank you very

Great answer, thank you very much.

By cdiggins at Sun, 2011-10-02 23:52 | login or register to post comments

xref

SECD in hardware

By el-vadimo at Sun, 2011-10-02 23:28 | login or register to post comments