Csc 4330/6330, Programming Language Concepts (Summer 2020)
Method to evaluate a let-expression
Consider a let-expression, (let ((x1 e1)(x2 e2)...(xn en)) e). The evaluation of this let-expression is defined as follows:evalNum((let ((x1 e1)(x2 e2)...(xn en)) e)) = evalNum(substitute(xn,evalNum(en),substitute(xn-1,evalNum(en-1)...,substitute(x1,evalNum(e1),e)...)))
In other words, start with e, substitute x1 by evalNum(e1) in e to get a new expression e', then substitute x2 by evalNum(e2) in e' to get e'', and so on.
The substitute function, substitute(x,v,e), recursively traverses the expression data structure for e all the way down to the leaves of the tree structure and replaces x by v at the lowest levels of the tree. The only time the substitute function gets blocked from going down the expression tree is when it encounters a nested let-expression containing the same variable. Whether it gets blocked or not by a nested let-expression, the substitution is applied to the value part of the name-value pair in the nested let-expression.