Issue: WITH-DYNAMIC-EXTENT (Version 1)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

I got tired of having this lone piece of paper sitting on my desk with no
electronic version, so finally typed it in. Please encourage people who
submit hardcopy cleanup items to follow them up with electronic mail!

Please don't take my having done the typing as an endorsement; my commentary
will come under separate cover.
 -kmp

-----
Issue:	      WITH-DYNAMIC-EXTENT
References:   CLtL p. 39, p. 162
Category:     ENHANCEMENT
Edit History: 9-Oct-88, Version 1 by Jim Allard

Problem Description:

Users of Common Lisp cannot write programs which explicitly perform their
own memory management and do not rely on a garbage collector.

Proposal:

Introduce two new macros: WITH-DYNAMIC-EXTENT and WITH-INDEFINITE-EXTENT.

Add to the end of chapter 9, p. 162, the new section "Extent Declarations".

"By default, data objects within Common Lisp programs have indefinite extent
and so continue to exist as long as a possibility of reference to them exists.
Implementations are free to reclaim (garbage collect) any objects for which it
can be proven that no possible references exist. The following macros provide
programmers the ability to declare extra information about the extent of data
objects.

	with-dynamic-extent {form}*

The forms of the body are executed as an implicit PROGN and the values of the
last form in the body are returned. This macro declares that the objects
created within the dynamic extent of the body forms (but which are not further
nested within WITH-INDEFINITE-EXTENT forms) have dynamic extent, and may be
reclaimed on exit from this form. Note that the extent of any object created
within the dynamic extent of a further nested WITH-DYNAMIC-EXTENT form is
determined by the deepest nested call. This macro represents a guarantee by the
programmer that no objects created within the body will be referenced outside of
the body. The behavior of a reference to one of these objects outside the
dynamic extent is undefined.

	with-indefinite-extent {form}*

The forms of the body are executed as an implicit PROGN and the values of the
last form in the body are returned. This macro declares that the objects
created within the dynamic extent of the body forms (but which are not further
nested within WITH-DYNAMIC-EXTENT forms) have indefinite extent, and so may only
be reclaimed when it can be proven that no references exist to these objects.
This is the default behavior."

Add to p.39 after "The important scope and extent rules of Common Lisp follow:"

"* Data objects have indefinite extent, except when created within the dynamic
extent of a WITH-DYNAMIC-EXTENT form, in which case they may have dynamic
extent."

Rationale:

Lisp has always had automatic memory management as one of its features,
shielding the programmer from issues of memory usage and reclamation and
treating the machine as an abstraction. Several sophisticated garbage collection
techniques have been developed which lessen the impact of memory management on
performance. However, the wait times and larger memory requirements imposed by
garbage collection in most implementations of Lisp are still two of the biggest
practical problems faced when fielding Lisp programs. The problem becomes even
more serious when attempting to write real-time applications in Lisp.

Most widely used computer languages today require programmers to manage
their own data structures. In Common Lisp this is not currently
possible, since implementations are free to cons and discard objects at
will. This is especially true of the arithmetic functions. Most
implementations happen to be good about not unnecessarily consing, and
with careful use of a subset of Common Lisp, one can resource manage all
objects other than numbers. With the addition of these two macros and
mutation operations for the required subtypes of number, it becomes
possible to write garbage-free Lisp code.

Even in those applications where all garbage will not be eliminated,
optimization of specific parts of a program which are known to be producers of
large temporary data structures can greatly increase overall performance.

Current Practice:

Many vendors currently supply some form of facility which will reclaim allocated
memory outside of normal garbage collection. On Lisp machines, the temporary
are facility provides the ability to clear a region of memory on command. Some
vendors of Lisps for conventional architectures have produced the above facility
for customers who have requested it.  Some vendors have used it themselves in
their own compiler programs.  The response to this problem in general has been
to improve garbage collector performance rather than provide facilities to
reduce or eliminate the need for them. Users of Common Lisp have either
resigned themselves to the performance needs of the garbage collector, have
tried to tailor their garbage creation patterns to best fit the existing garbage
collector, or have ported to other languages, such as C, which support explicit
memory management. This facility would be an added tool for the second
approach, tailoring garbage creation patterns.

Adoption Cost:

Since the facility is a declaration, Common Lisp vendors may choose to not
implement any portion of this facility, and have the macros expand as PROGNs.
Vendors also have the choice of determining which types of Lisp objects
could have dynamic extent. Those vendors who already have an areas-like
facility would not have significant additional work to do in the object
allocation facilities. If a system depends upon keeping objects of different
types within different pages, then the task is somewhat complicated, but most
vendors can use an implementation where dynamic extent objects are allocated
into a special region of memory whose allocation pointer is reset on exit from
WITH-DYNAMIC-EXTENT back to where it was on entry to the form. Garbage
collectors may have to be modified to scan this region for pointers, but should
not evacuate it. Vendors will also have to evaluate how each type with dynamic
extent would affect other facilities in the system. See the discussion for more
details.

Benefits:

This facility allows programmers to exert greater control over the garbage
creation properties of their programs. Though automatic memory management is
one of the nicest facilities for programmers in Lisp, the performance penalty of
garbage collection is one of the biggest barriers to end user acceptance of Lisp
programs. Though improvements have been made in garbage collector technology in
the 80's, not all vendors will be able to adopt these techniques, and not all
application programmers will be able to accept even the modest loss of
performance imposed by modern garbage collection methods. The reclamation of
garbage objects at or near the source of their creation makes it possible to
reduce or eliminate this problem.

Conversion Cost:

Since this is a new facility, no currently existing Common Lisp code would be
affected.

Aesthetics:

Questionable. Though the facility fits well as an added type of extent for Lisp
objects, it can be rightly criticized as a dangerous facility when used
incorrectly. However, it does directly address a problem of garbage creation in
an efficient and consistent manner. This facility can cause data corruption in
much the same way as an incorrect type declaration. Though we do not want to
offer users invitations to hang themselves, we also do not need to treat them
like children.

Discussion:

This facility needs to be discussed in terms of the CLtL functions which mutate
data structures or cache consed data and depend on those values later on. The
problems which can arise here should be addressed per implementation by choosing
which types of objects may have dynamic extent, and choosing which operations
should signal errors when performed within a dynamic extent context.

The facilities for which this system does not have an obvious meaning are the
following: hash table mutation, readtable mutation, package mutation, stream
operations, random number generation, error signalling, and defining forms which
have side effect upon the environment. The following example illustrates the
problems which can arise in given facilities.

Say we have an implementation where streams and strings are allowed to have
dynamic extent. A user wishes to write a program which reads and processes
files. The user wants the file access portion of the program to not create
garbage and not require large amounts of memory. The user's program takes on
the following structure.

(defun process-file (pathname)
  (with-dynamic-extent
    (with-open-file (input pathname)
      (block read-file
	(loop
	  (with-dynamic-extent
	    (let ((line? (read-line input nil nil)))
	      (if (null line?) (return-from read-file nil))
	      (with-indefinite-extent
		;; Process this line
		))))))))

In PROCESS-THIS-FILE the user wants the extent of the stream in INPUT to be
bounded within the outermost call to WITH-DYNAMIC-EXTENT. The extent of each
line of the file should be bounded within each pass through the body of the
LOOP.

Where this program could run into problems is within the call to READ-LINE. If
the stream object is mutated such that a pointer is maintained to an object
created within the call to READ-LINE, and that created object has dynamic
extent, then on exit from WITH-DYNAMIC-EXTENT in the body of this loop the
stream will have been corrupted.

Several approaches may be taken within an implementation to address this
problem. READ-LINE (and other stream mutation operations) could be written to
perform its mutations so that no objects with dynamic extent are created. This
could be done by using data which is immediate, such as immediate fixnums for
current-position-in-file counters. The portions of READ-LINE which could create
such objects, such as input buffer creation code, could themselves be wrapped
with WITH-INDEFINITE-EXTENT forms and allow these objects to be subject to
garbage collection. Another approach is to resource manage any supplemental
structures, again wrapping the creation point with WITH-INDEFINITE-EXTENT, but
recycling these objects for reuse on stream close such that no actual garbage is
created.

Another approach for an implementation is to declare that the use of READ-LINE,
or any other system object mutating function, within a dynamic extent context
should be an error.

The point of the facility is to allow implementations to provide some means for
users to more explicitly manage memory requirements within an application. The
choice of which facilities should be affected and how smoothly it should
integrate with the rest of the system is up to each vendor. Defining the
facility in this way means that programs which use it will have to be tailored
to work within different Lisp implementation, as is the case now with producing
executable program images. However, the inclusion of these forms in the
language does present implementors with an invitation to provide their users
with some method of memory use optimization, which is sorely needed.