Programming Language for Old Timers


by David A. Moon
February 2006 .. September 2008

Comments and criticisms to dave underscore moon atsign alum dot mit dot edu.


Previous page   Table of Contents   Next page


Code Walking

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