Lpl: A Generalized List Processing Language

The paper describes LFL, a generalized list processing language. LFL allows the user to define multiple cell structures and cell sizes at runtime, thereby allowing nonhomogeneous list structures. The paper examines the problems associated with list tracing in systems allowing multiple cell-types. Complex list tracing during garbage collection in LFL is avoided: (1) by creating a doubly-linked super list of all allocated cells and (2) by using a reference count scheme. No marking phase is required for garbage collection. The problem of developing insertion and deletion procedures for lists with cells having multiple types of pointer structures is discussed and LFL solutions are given. LPL statements can handle singly-linked, doubly-linked, left-right-linked, and some multi-linked pointer structures automatically. The design philosophy and the data organization for LPL are discussed in detail. Examples of the definition of cell structures are given, and all of the LPL list manipulation and creation statements arc examined and discussed.