In SECD Machine, how does rap work?

Question

I am writing a SECD machine simulator in C #, a managed description on Wikipedia . I have basic operations, but I'm not sure how to implement the rap instruction.

Wikipedia talks about rap :

rap works like ap only because it replaces the dummy environment with the current one, which makes recursive functions possible

And for ap it says:

ap returns a closure and a list of parameter values ​​from the stack. Closing is applied to the parameters, setting its environment as the current one, dragging the list of parameters before it, clearing the stack and setting C to the index of the closing function. The previous values ​​of S, E and the next value of C are saved on the dump.

Here is my ap implementation

  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; } 

Please note that List is my implementation of the "cons" Lisp cell.

What bothers me how different is rap from ap ? For example, what exactly happens with the environment register (E)? I find the definition of Wikipedia a bit ambiguous and could not find anything that explains it well.

Answer 1

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

The AP command is used to compile the let binding, while the RAP command is used to compile the letrec binding.

'letrec' is different from 'let' because you can “see” the environment in which the recursive function is defined so that you can call it recursively (for example, you define the function “factorial” and you can name it in the body of the function )

RAP modifies the environment by calling rplaca (similar to setcar! In Scheme). In the previous DUM instruction, a “dummy” machine is added 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 look like this:

  ((c'.e ') vs) e (AP.c) d =>
 NIL (v.e ') c' (se cd)

 ((c'.e ') vs) (? .e) (RAP.c) d =>
 NIL (setcar! E ', v) c' (se cd)

See also SECD Repeat and Lisp Power , citing:

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

and

When I tried to implement RAP in Erlang, I got stuck because there are no destructive operations in the lists. Not in the standard API, and it seems not in the system API. So, Erlang SECD looks beautiful, only it does not start.

Answer 2

You really have to pick up a copy of Peter Henderson’s wonderful book, The Application and Implementation of Functional Programming. In it, he carefully describes and builds the SECD machine and Lispkit Lisp.

Answer 3

In addition to the excellent accepted answer, I would like to give more explanations why rap is required.

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

In a typical function call, a new list is pressed on E , and now any local variables can have identifiers of the type (|E|, y) , where |E| denotes size E This is very problematic for recursive functions, however, since the stack size grows with every function call, it is therefore impossible to assign identifiers for the local variables used.

To solve this problem, rap does most of the things ap does, but instead of dragging the new list onto the environment stack, it replaces everything that is in chapter E with the new environment list.