In the SECD Machine how does "rap" work?

Question

I am writing a simulator of the SECD machine in C# guided by the description on Wikipedia. I have the basic operations completed, but I am not sure how to implement the rap instruction.

At Wikipedia it says about rap:

rap works like ap, only that it replaces an occurrence of a dummy environment with the current one, thus making recursive functions possible

And for ap it says:

ap pops a closure and a list of parameter values from the stack. The closure is applied to the parameters by installing its environment as the current one, pushing the parameter list in front of that, clearing the stack, and setting C to the closure's function pointer. The previous values of S, E, and the next value of C are saved on the dump.

Here is my implementation of ap

    public void ap() 
    { 
        Push(S, ref D); 
        Push(E, ref D); 
        Push(C, ref D); 
        List closure = Pop(ref S);
        List paramlist = Pop(ref S);
        E = closure.Tail;
        Push(paramlist, ref E);
        C = closure.Head;
        S = List.Nil;
    }

Note that List is my implementation of a Lisp style "cons" cell.

What confuses me is exactly how rap differs from ap? For example what exactly happens to the environment register (E)? I find the Wikipedia definition a bit ambiguous, and haven't been able to find anything else that explains it well.

Fraya

Answer 1

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

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:

S	E	C	D	S'	E'	C'	D'
((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.

Arnoldarnoldo

Answer 2

You should really pick up a copy of Peter Henderson's wonderful little book "Functional Programming Application and Implementation". In it he meticulously describes and builds an SECD machine and Lispkit Lisp.

Needle

For reference, here's a complete SECD machine in ~100 lines of F# and then a compiled LispKit Lisp and tests in about another 100. github.com/AshleyF/Lispkit/blob/master/Program.fs – Needle

Answer 3

In addition to the excellent accepted answer, I wanted to provide more of an explanation of why rap is required.

The environment (the E in SECD) stores all of the persisted entities (functions, constants, variables, etc.). E is essentially a stack of lists. Things in E are loaded onto the stack S and then executed or used by commands in C. Everything in E is given an id so that it can be referenced later. This ID is typically a tuple (x,y), where x represents the location of the list on the stack, and y represents a position in that list.

In a typical function call, a new list is pushed on E and now any local variables can have IDs like (|E|, y), where |E| denotes the size of E. This is very problematic for recursive functions, however, because the stack size grows with each function call so there is no way to assign the local variables usable IDs.

To solve this problem, rap does most of the things ap does, but instead of pushing a new list onto the environment stack, it replaces whatever is at the head of the E with the new environment list.

Adjudication