CC and SCC Machine
An obvious inefficiency of our first textual machine is the repeated traversal of the expression tree to find the redex. After each reduction step, it starts over again from the root node. We really don’t have to do this, because the next redex is often the reduction result of current redex, or at least, closes to the current one. Let’s consider the evaluation of the following expression:
(+ ((lambda x (lambda y y) x) 1) 1) => (+ ((lambda y y) 1) 1) => (+ 1 1) => 2
The redex for each step is underlined. In the first two steps, the redex for next step is just the evaluation result of the current redex. And in the third step, the next redex is the parent expression of the result of previous step. Actually, we can identify the next redex by checking the result of current one or its parent for every expression. Suppose the evaluation result of a redex is an application, if either of its children is not a value, the non-value child expression will be the next redex. Otherwise, the result itself will be the next one. Suppose the result is a value, its parent or the other child will probably be the next redex. We didn’t do this kind of checking in the textual machine, because we only had the complete expression as our machine state, and the machine were not aware of the result and its parent. Though this could be obtained in the implementation, from the model view, the machine does only know the complete expression. So in this post, two new machines using the strategy will be defined to improve the efficiency.
CC Machine
According to the discussion above, if the textual machine knows the redex and its parent, it can easily decide what the next redex is, rather than traversing the entire expression tree again. To keep it running until getting the final result, not just the parent of the redex, but also the parent’s parent should be recorded. The redex is the machine currently interested in, and it is called control string. Except the redex, the other part of the expression is called evaluation context, from which all the parents can be obtained. The two elements are paired together to form the machine’s state. So this machine is called CC machine. Combining the control string and context yields the complete expression, which is the state of the previous machine. I’d like to call the complete expression as program. Initially, the program is the control string, and the context is empty. The termination condition of this machine is when the control string is a value and context is empty. Here is the reduction rules for this machine:
1) If the control string is a value(identifier, constant or abstraction), remove its parent from the context, and set the parent as control string;
2) If the control string is an application or primitive, and at least one of its children is not a value, put itself into the context and set the non-value child as control string;
3) If the control string is an application or primitive, and both of its children are values, perform reductions on it and set the result as control string.
To find the first redex, we still need to traverse the expression tree, but the traversed nodes should be remembered in the context. Since only the parent of control string is interested for each step, and from each traversed parent, we can navigate to any part of the program, I use a FILO(First-In-Last-Out) list of the traversed nodes to represent the context(Actually, we don’t need such kind of data structure if a pointer to parent node is added to each node, but this requires changes to the parser, so I don’t choose this option). From the implementation view, the machines perform evaluations by popping and pushing control string into or from the context to find the redex. Here is the definition for machine state and the context:
1 // file: cc_machine.h
2 /* Use a LIFO list to represent the context. */
3 typedef struct contextStruct {
4 TreeNode * expr;
5 struct contextStruct * next;
6 } Context;
7
8 /* Machine state is a pair of control string and the context. */
9 typedef struct stateStruct {
10 TreeNode * controlStr;
11 Context * context;
12 } State;
From the reductions rules, we can easily derive the actions on context:
1) If the control string is a value, pop the head node from the list and set the node as control string;
2) If the control string is an application or primitive, and at least one of its children is not a value, push it into the head of the list and set the non-value child as control string;
3) If the control string is an application or primitive, and both of its children are values, perform reductions on it and set the result as control string and no action for context.
Here is the listing of code:
1 // file: eval.c
2 TreeNode * evaluate(TreeNode *expr) {
3 State * state = cc_newState();
4 state->controlStr = expr;
5
6 Context * ctx = NULL;
7 while(!cc_canTerminate(state)) {
8 if(isValue(state->controlStr)) {
9 // pop an expression from the context
10 state->controlStr = state->context->expr;
11 ctx = state->context;
12 state->context = state->context->next;
13 cc_deleteContext(ctx);
14 ctx = NULL;
15 }else {
16 if(!isValue(state->controlStr->children[0])
17 || !isValue(state->controlStr->children[1])) {
18 // push the current expression into context
19 ctx = cc_newContext();
20 ctx->expr = state->controlStr;
21 ctx->next = state->context;
22 state->context = ctx;
23 if(!isValue(state->controlStr->children[0])) {
24 state->controlStr = state->controlStr->children[0];
25 }else {
26 state->controlStr = state->controlStr->children[1];
27 }
28 } else { // evaluate control string
29 if(state->controlStr->kind==AppK) {
30 if(state->controlStr->children[0]->kind==ConstK) {
31 fprintf(errOut, "Error: cannot apply a constant to any argument.\n");
32 fprintf(errOut, "\t\t");
33 printExpression(state->controlStr,errOut);
34 cc_cleanup(state);
35 return NULL;
36 }else if(state->controlStr->children[0]->kind==IdK) {
37 // find function from builtin and standard library
38 TreeNode* fun = resolveFunction(state->controlStr->children[0]->name);
39 if(fun==NULL) {
40 fprintf(errOut, "Error: %s is not a predefined function.\n", state->controlStr->children[0]->name);
41 cc_cleanup(state);
42 return NULL;
43 }
44 deleteTree(state->controlStr->children[0]);
45 state->controlStr->children[0] = fun;
46 } else {
47 TreeNode *tmp = betaReduction(state->controlStr);
48 if(state->context!=NULL) {
49 if(state->context->expr->children[0]==state->controlStr) {
50 state->context->expr->children[0] = tmp;
51 }else {
52 state->context->expr->children[1] = tmp;
53 }
54 }
55 state->controlStr = tmp;
56 }
57 }else if(state->controlStr->kind==PrimiK) {
58 // only perform primitive operation if operands are constants
59 if(state->controlStr->children[0]->kind==ConstK
60 && state->controlStr->children[1]->kind==ConstK) {
61 TreeNode* tmp = evalPrimitive(state->controlStr);
62 if(state->context!=NULL) {
63 if(state->context->expr->children[0]==state->controlStr) {
64 state->context->expr->children[0] = tmp;
65 } else {
66 state->context->expr->children[1] = tmp;
67 }
68 }
69 deleteTree(state->controlStr);
70 state->controlStr = tmp;
71 } else {
72 fprintf(errOut, "Error: %s can only be applied on constants.\n", state->controlStr->name);
73 cc_cleanup(state);
74 return NULL;
75 }
76 }else {
77 fprintf(errOut,"Error: Cannot evaluate unkown expression kind.\n");
78 cc_cleanup(state);
79 return NULL;
80
81 }
82 }
83 }
84 #ifdef DEBUG
85 // print intermediate steps
86 if(!cc_canTerminate(state)) {
87 fprintf(out,"-> ");
88 printExpression(cc_getProgram(state),out);
89 fprintf(out,"\n");
90 }
91 #endif
92 }
93
94 TreeNode* result = state->controlStr;
95 cc_deleteState(state);
96 return result;
97 }
Let’s try it:
$ ./main Welcome to Lambda Calculus Evaluator. Press Ctrl+C to quit. > (lambda x x) (lambda y y) 1 -> (lambda x x) (lambda y y) 1 -> (lambda y y) 1 -> (lambda y y) 1 -> 1
SCC Machine
Examining the reduction steps at the end of the last section, step 2 and 3 are the same. That’s because after step 2, the control string is (lambda y y) and the context is the parent of it. Based on the rules, the machine pops the parent and set it as control string. The machine state is changed but not actual reduction is performed on the program, so the program for both steps are the same. After that, beta-reduction is performed on the control string. Actually, we only have two possible actions after step 2: performing beta-reduction or primitive evaluation on the parent node or setting the other child as control string. We can simplify the process by checking the parent node so those two steps can be combined into one. Rule 1) of the CC machine is now revised to:
1’) If the control string is a value and the other child of its parent is a value too, remove its parent from the context, perform reductions to it and set the result as control string. Otherwise, set the other child as control string.
The code needs only simple changes, so I won’t duplicate it here. Here is the evaluation steps for the same expression, and the duplicated step is gone:
$ ./main Welcome to Lambda Calculus Evaluator. Press Ctrl+C to quit. > (lambda x x) (lambda y y) 1 -> (lambda x x) (lambda y y) 1 -> (lambda y y) 1 -> 1
Compared to CC machine, SCC machile always has less steps. All the code is available at here.