Syntactic Abstraction in Scheme

Robert Hieb?, R. Kent Dybvig, and Carl Bruggeman
dyb or [email protected]

Indiana University Computer Science Department
Technical Report #355

June 1992
(Revised July 3, 1992)

Abstract

Naive program transformations can have surprising effects due to the interaction between introduced identifier references and previously existing identifier bindings, or between introduced bindings and previously existing references. These interactions can result in the inadvertent binding, or capturing, of identifiers. A further complication results from the fact that the transformed program may have little resemblance to the original program, making correlation of source and object code difficult. We address both the capturing problem and the problem of source-object code correlation. Previous approaches to the capturing problem have been both inadequate and overly restrictive, and the problem of source-object code correlation has been largely unaddressed. Our approach is based on a new algorithm for implementing syntactic transformations along with a new representation for syntactic expressions. It allows the programmer to define program transformations using an unrestricted, general-purpose language, while at the same time it helps the programmer avoid capturing problems and maintains a correlation between the original code and the transformed code.

1 Introduction

A fundamental problem with most Lisp macro systems is that they do not respect lexical scoping. When one expression is substituted for another, apparent bindings can be shadowed, resulting in unintended capture of variable references. This is the source of many serious and difficult to find bugs. This problem was first addressed by Kohlbecker, Friedman, Felleisen, and Duba [15], who proposed a hygiene condition for macros and a macro-expansion algorithm that enforces this condition. Unfortunately, the KFFD algorithm increases the computational complexity of the macro expansion process.

An additional problem of equal practical importance is that Lisp macro systems cannot track source code through the macro-expansion process. In order for the compiler, run-time system, and debugger to communicate with the programmer in terms of the original program, it is necessary to be able to reliably correlate source code and macro-expanded code. This source-object correlation problem has been addressed by optimizing compiler writers [13, 6, 18]. However, if the macro ?Robert Hieb died in an automobile accident on April 30, 1992