Transcript SECD Machine - Department of Computer Science

CS321 Functional Programming 2
The SECD Machine
The SECD machine has become a classic way of implementing
functional languages. It is based on an automaton designed
by Peter Landin in the early sixties.
As with the Combinator approach it assumes that the program is
expressed as a λ-expression which is one of
•
A variable
•
An abstraction (bound variable part and body)
•
An application (operator and operand)
© JAS 2005
6-1
CS321 Functional Programming 2
The SECD machine uses four stacks. These are
The Stack which is used to store the partial results of
evaluating an expression, and which will hold the final
result of the machine's execution.
The Environment which consists of a series of pairs that give
values to the free variables of an expression; the value of a
constant in any environment being that constant. The first
element of any pair is an identifier and the second element
is the associated value.
The Control which stores the expression that is being
evaluated.
The Dump which is used to store copies of the four stacks
whilst a sub-function is being evaluated.
© JAS 2005
6-2
CS321 Functional Programming 2
We can now present an outline algorithm for the
implementation of the SECD machine. Since the design
was intended to be used for implementation on a
conventional sequential machine it is appropriate to present
the algorithm in a sequential style.
© JAS 2005
6-3
CS321 Functional Programming 2
WHILE
there is an expression to be evaluated C is not empty
OR
there is a suspended computation to be resumed D is not empty
DO
IF the evaluation of the current expression is complete
C is empty
THEN resume the last suspended computation with the
newly computed value on S
remember the value on S;
recover S,E,C,D from D;
push the value from the old S onto S
ELSE
© JAS 2005
6-4
CS321 Functional Programming 2
CASE
OF
the next expression to be evaluated
top of C
identifier:
push value of this identifier onto S and pop C
find value of identifier in E;
push it onto S;
pop C
λ-exp:
push the appropriate closure onto S and pop C
push the triple (body, bvpart, E) onto S;
pop C
© JAS 2005
6-5
CS321 Functional Programming 2
application:
replace top of C by the expressions representing this
application
pop C;
push the ap operator onto C;
push the operator to be applied onto C;
push the operand onto C
© JAS 2005
6-6
CS321 Functional Programming 2
ap:
cause the operator on S to be applied to the operand below it
IF hd(S) is a closure
THEN push 4-tuple (tail(tail(S)),E,(tail(C),D) onto D;
push body of closure onto new empty C;
make E the environment from closure prefixed by
pair associating bvpart of closure with hd(tail(S));
create a new empty S
ELSE { the operator is a primitive function }
pop C;
find result of applying hd(S) to hd(tail(S));
pop S twice;
push result onto S
ENDC
© JAS 2005
6-7
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
E
C
D
(λx.λy.+xy) 3 4
ap
© JAS 2005
6-8
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
4
E
C
D
cl(λy.+xy,x,())
(λx.λy.+xy) 3
ap
© JAS 2005
6-9
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
E
cl(λy.+xy,x,())(x,3)
C
λy.+xy
D
(
,(),
,())
3
4
ap
ap
© JAS 2005
6-10
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
E
cl(+xy,y,(x,3)) (x,3)
C
λy.+xy
© JAS 2005
D
( 4 ,(), ap ,())
6-11
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
E
4
C
(y,4)
+ ap
x y
D
((),(),(),())
cl(+xy,y,(x,3)) (x,3)
© JAS 2005
6-12
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
4
3
E
C
+ x y
(y,4)
D
((),(),(),())
(x,3)
ap
© JAS 2005
6-13
CS321 Functional Programming 2
An example evaluation – (λx.λy.+xy) 3 4
S
E
7
+
(y,4)
3
(x,3)
C
D
((),(),(),())
4
ap
ap
© JAS 2005
6-14
CS321 Functional Programming 2
The SECD machine implements eager (applicative order)
evaluation since it evaluates the arguments first. The evluation of
the body of the function is delayed by the closure mechanism.
A lazy SECD machine can be defined by introducing the concept
of a suspension.
Primitive functions may be regarded as strict, but other functions
are lazy so their parameters are saved as a suspension which
consists of the unevaluated parameter and the environment in
which it is to be evaluated.
© JAS 2005
6-15
CS321 Functional Programming 2
The evaluation algorithm needs to add an extra case for a
suspended computation, and also modify the actions
required for an application and an ap operator.
We will consider first the modification for the application
case:
application:
replace top of C by the expressions representing this application
pop C; push the ap operator onto C;
push the operator to be applied onto C;
pushoperand
the operand
onto C
IF
is function
THEN push operand onto C
ELSE create suspension – push pair (operand, E) onto S
© JAS 2005
6-16
CS321 Functional Programming 2
When evaluating the ap operator we have another option to
consider:If the operator is a closure, or has its necessary operands then
the actions are as before.
If the operator is a strict primitive function and its operand is
a suspension we need to create a new set of stacks to
evaluate the suspension.
push the 4-tuple (S,E,C,D) onto D;
push the sp operator onto C;
push the body of the suspension onto C;
push the environment of the suspension onto E;
create a new empty S
© JAS 2005
6-17
CS321 Functional Programming 2
Finally we need to be able to evaluate the sp operator when it
is at the top of the C stack.
This involves resuming the last incomplete suspended
computation with all references to the completed
suspension replaced by the computed value.
remember hd(S);
recover S, E, C and D from hd(D);
throughout S and E replace all occurrences of the
suspension that is hd(tl(S)) by what was hd(S)
© JAS 2005
6-18
CS321 Functional Programming 2
Consider an example evaluation using the standard eager machine
S
E
(y,6)
(y,6)
6
(y,6)
6,cl(4,x,((y,6))
(y,6)
(y,6),(x,6)
4
(y,6),(x,6)
4
(y,6)
© JAS 2005
C
D
(λx.4) y
ap, (λx.4), y
ap, (λx.4)
ap
4
((),(y,6),(),())
((),(y,6),(),())
6-19
CS321 Functional Programming 2
The same example evaluation using a lazy machine
S
E
(y,6)
(y,6)
C
(λx.4) y
ap, (λx.4)
su(y,(y,6))
su(y,(y,6)),
cl(4,x,((y,6))
(y,6)
ap
(y,6),(x,su(y,(y,6))) 4
4
(y,6),(x,su(y,(y,6)))
4
(y,6)
© JAS 2005
D
((),(y,6),(),())
((),(y,6),(),())
6-20