Previous page Table of Contents Next page
Code walking means traversing a P-expression tree of already-parsed source code and either collecting information about the code or applying transformations to the code. This is a common operation among more advanced Lisp macros.
In Lisp, code walking requires ad hoc code to understand every "special form." This is unmodular, error-prone, and a waste of time.
As always, the solution to this type of problem is object orientation. In PLOT there is a well-defined, object-oriented interface to P-expressions, scopes, and definitions. This is one reason why objects are better than S-expressions as a representation for program source code.
The Code Walking protocol consists of two variants of the walk function. Every type of expression implements this protocol. Users writing code walkers can simply call this function. Both variants of walk take a function as their first argument and apply it to each subexpression of the expression given as the second argument. The third argument is the scope for looking up name references in that expression.
Collecting code walk is essentially a reduce operation over all subexpressions of a given expression. The function is applied to a subexpression, the scope for name references in that subexpression, and a current value. The function returns the new value.
require walk(f is function, e is expression, s is scope,
initial-value is anything,
result: new-value)
Replacing code walk applies the function to each subexpression and the scope for name references in that subexpression. The function returns a replacement subexpression. The original expression is copied as needed, it is not modified.
require walk(f is function, e is expression, s is scope,
result: new-expression is expression)
Some example implementation:
def walk(f is function, e is invocation, s is scope, initial-value)
reduce(f(_, s, _), f(e.function, s, initial-value), e.arguments)
def walk(f is function, e is scopation, s is scope, initial-value)
reduce(f(_, e.scope, _), initial-value, e.body)
def walk(f is function, e is invocation, s is scope)
def new-function = f(e.function, s)
def new-arguments = map(f(_, s), e.arguments)
if new-function eq e.function and every?(eq, new-arguments, e.arguments)
e
else
with-source-location source-location(e)
invocation(new-function, new-arguments...)
def walk(f is function, e is scopation, s is scope)
def new-body = map(f(_, e.scope), e.body)
if every?(eq, new-body, e.body)
e
else
with-source-location source-location(e)
scopation(e.scope, new-body...)
Some example uses of code walking (these are not part of PLOT):
To find all free "variable" references within an expression:
def free-variables(e is expression,
optional: s is scope = local-scope(),
vars is collection = stack())
walk(free-variables, e, s, vars)
def free-variables(e is name,
optional: s is scope = local-scope(),
vars is collection = stack())
if lookup(s, e) or member?(e, vars) then vars
else add(e, vars)
To trace all function calls within an expression, just stick trace in front of the expression:
defmacro trace ?expr =>
add-tracing(expr, get-local-compiler-scope())
;; Default method just walks over subexpressions
def add-tracing(e is expression, s is scope)
walk(add-tracing, e, s)
;; This method adds tracing to a function invocation
def add-tracing(e is invocation, s is scope)
def fcn = add-tracing(e.function, s)
def args = map(walk(add-tracing, _, s),
e.arguments)
def macro-context = unique-macro-context()
def temps = for n from 1 to args.length
collect name(#"temp-?n", macro-context)
parse-expression(token-stream(
`do
def fcn = ?fcn
{ def ?temps = ?args & ^ }*
def results = values-list(fcn( { ?temps &, }* ))
write(*trace-output*,
" " + fcn + "(" { + ?temps }* +
") = " + results + "\n")
values(results...)`),
false, true)
eval-once defines temporary variables so an expression can be used more than once without repeating side-effects more than once. If the expression is a name, slot-reference, or invocation, the result is suitable for use on the left-hand side of assignment. Complex expressions like conditionals are not allowed.
def eval-once(expr is expression,
optional: scope is scope = get-local-compiler-scope()
result: temporary-names, temporary-values, new-expression)
def macro-context = unique-macro-context()
def temporary-number := 1
def temporary-names = stack()
def temporary-values = stack()
def new-expression = remove-side-effects(expr)
def remove-side-effects(expr is name or literal or quotation) expr
def remove-side-effects(expr is invocation or slot-reference)
if walk(any-side-effects?, expr, scope, false)
walk(add-temporary, expr, scope)
else expr
def add-temporary(e is literal or quotation, s is scope) e
def add-temporary(e is expression, s is scope)
def temp = name(#"temp-?temporary-number", macro-context)
temporary-number := temporary-number + 1
temporary-names.push := temp
temporary-values.push := e
temp
def any-side-effects?(expr is name or literal or quotation, s is scope, x) x
;; slot-reference could have side-effects if slot is virtual, assume the worst
def any-side-effects?(expr is expression, s is scope, x) true
values(temporary-names.bottom-up, temporary-values.bottom-up, new-expression)
Previous page Table of Contents Next page