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) ; returns last function result
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) is expression
Some example implementation:
defun walk(f is function, e is invocation, s is scope, initial-value)
reduce(f(_, s, _), f(e.function, s, initial-value), e.arguments)
defun walk(f is function, e is scopation, s is scope, initial-value)
reduce(f(_, e.scope, _), initial-value, e.body)
defun 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 e
invocation(new-function, new-arguments...)
defun 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 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:
defun free-variables(e is expression,
optional: s is scope = local-scope(),
vars is collection = stack())
walk(free-variables, e, s, vars)
defun 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
defun add-tracing(e is expression, s is scope)
walk(add-tracing, e, s)
;; This method adds tracing to a function invocation
defun 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 result = fcn( { ?temps &, }* )
write(*trace-output*,
" " + fcn + "(" { + ?temps + ", " }* +
") = " + result + "\n")
result`),
0, 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 or invocation, the result is suitable for use on the left-hand side of assignment. Complex expressions like conditionals are not allowed. The result is a list of three elements:
;; Returns [temporary-names, temporary-values, new-expression]
defun eval-once(expr is expression,
optional: scope is scope = get-local-compiler-scope()) is list
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)
defun remove-side-effects(expr is name or literal or quotation) expr
defun remove-side-effects(expr is invocation)
if walk(any-side-effects?, expr, scope, false)
walk(add-temporary, expr, scope)
else expr
defun add-temporary(e is literal or quotation, s is scope) e
defun 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
defun any-side-effects?(expr is name or literal or quotation, s is scope, x) x
defun any-side-effects?(expr is expression, s is scope, x) true
[temporary-names.bottom-up, temporary-values.bottom-up, new-expression]
Previous page Table of Contents Next page