<html><head><title>Henry Baker's Archive of Research Papers</title>
<link rev="made" href="mailto:hbaker1@pipeline.com">
</head>
<body>
<h1><b>Henry Baker's Archive of Research Papers</b></h1>
<tt><pre>
***********************************************************************
* If you see a reference in one of my html files that is _not_ *
* linked, and you know of a link address to the appropriate document, *
* please send me mail, and I will include the link in the document. *
* Thanks very much in advance. -- Henry Baker (hbaker1@pipeline.com)*
***********************************************************************
</pre></tt>
The documents contained in this directory are included by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a non-commercial basis. Copyright and
all rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the
explicit permission of the copyright holder.<p>
Most files are WWW hypertext ('html') or Gnu Gzip 'compressed' Postscript,
without fonts. They depend only on the usual Times, Helvetica,
Courier and Symbol fonts. They have been tested using both Mac
Ghostscript (for viewing) and the Apple Laserwriter (for printing).<p>
Files are generally in reverse chronological order.<p>
Please contact hbaker1@pipeline.com if you have any problems.
Click <a href="gratuitous.html">here</a> to access gratuitous
waste of bandwidth page<p>
<a href="./sigplannotices/">Garbage In/Garbage Out Columns from ACM Sigplan Notices</a><p>
<a href="http://www.dcs.gla.ac.uk/~pd/IWMM/iwmm.html">
IWMM'95 Home Page</a>
International Workshop on Memory Management 1995<p>
<a href="emacs/tetris.el">tetris.el</a>
My improved Emacs Tetris game<p>
<a href="quaternion/cornellcstr75-245.ps.gz">cornellcstr75-245.ps.gz</a>
<a href="quaternion/cornellcstr75-245.dvi.gz">cornellcstr75-245.dvi.gz</a>
"The Complexity of the Quaternion Product" by Howell & Lafon,
Cornell CS TR75-245, June 1975. Quaternion product in only <b>eight</b>
real multiplications.
(Original <a href="quaternion/cornellcstr75-245.tar.gz">cornellcstr75-245.tar.gz</a>
23 600dpi TIFF G4 pages, in gzipped tar file.)
Retyped and TeX formatted by Henry G. Baker, November, 1995; posted with the permission of Jean-Claude Lafon (jcl@mimosa.unice.fr).<p>
<a href="quaternion/stanfordaiwp79-salamin.ps.gz">stanfordaiwp79-salamin.ps.gz</a>
<a href="quaternion/stanfordaiwp79-salamin.dvi.gz">stanfordaiwp79-salamin.dvi.gz</a>
"Application of Quaternions to Computation with Rotations" by Eugene
Salamin, unpublished Working Paper, Stanford AI Lab., 1979.
The orthogonal matrix which performs a rotation by angle theta about axis
n is derived; the same rotation can be represented by a unit quaternion.
Lorenz transformations in relativity can be implemented with quaternions
whose elements are complex numbers.
Retyped and TeX formatted by Henry G. Baker, November, 1995; posted with the
permission of Eugene Salamin.<p>
<a href="hakmem/hakmem.html">Hypertext HAKMEM (MIT AI Memo 239)</a><p>
<a href="pdp-10/pdp-10.html">Hypertext PDP-10 Assembly Language Info</a><p>
<a href="http://www.cs.cmu.edu/Web/Groups/AI/html/cltl/cltl2.html">Common Lisp, the Language, 2nd Ed (CMU hypertext)</a><p>
<a href="ftp://ftp.cs.utexas.edu/pub/garbage">Paul Wilson's Garbage Collection Archive</a><p>
<a href="http://www.cs.cmu.edu/~mleone/language-research.html">Mark Leone's language people</a><p>
<a href="http://www.cs.cmu.edu/~carsten/linearbib/linearbib.html">Linear Logic Bibliography</a><p>
<a href="http://www.csl.sri.com/linear/sri-csl-ll.html">Lincoln's Linear Logics</a><p>
<a href="letters/letters.html">letters</a>
Various published and unpublished letters<p>
<a href="QuaternionRefs.txt">QuaternionRefs.txt</a>
Bibliography on Quaternions.<p>
<a href="FAQ-lat-long.txt">FAQ-lat-long.txt</a>
Computing Great Circle Distances from Latitudes and Longitudes.<p>
<a href="CheneyMTA.html">CheneyMTA.html (WWW hypertext)</a><br>
<a href="CheneyMTA.pdf">CheneyMTA.pdf (4 pages)</a>
"CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."
Draft of paper for comp.lang.scheme.c, Feb. 4, 1994. ACM
<cite>Sigplan Notices 30,</cite> 9 (Sept. 1995), 17-20. How to
translate Scheme into C by using continuation-passing style C
functions in such a way that tail recursions use bounded amounts of
storage, continuation capture is simple, and garbage collection is
precise. Includes a reference to <a href="cboyer13.c">cboyer13.c</a>,
in which the Gabriel Boyer Lisp benchmark is translated into C using
the methods of this paper.<p>
<a href="Use1Var.html">Use1Var.html (WWW hypertext)</a><br>
<a href="Use1Var.ps.gz">Use1Var.ps.gz (8 pages)</a>
"'Use-Once' Variables and Linear Objects--Storage Management,
Reflection and Multi-Threading". ACM <cite>Sigplan Notices 30,</cite>
1 (Jan. 1995), 45-52. A high-level discussion of 'linear' and
'non-linear' (traditional) names/variables/objects in programming
languages.<p>
<a href="LRefCounts.html">LRefCounts.html (WWW hypertext)</a><br>
<a href="LRefCounts.ps.gz">LRefCounts.ps.gz (6 pages)</a>
"Minimizing Reference Count Updating with Deferred and Anchored
Pointers for Functional Data Structures". ACM <cite>Sigplan Notices
29,</cite> 9 (September 1994), 38-43. Safe mechanisms for reducing
reference count updating overhead.<p>
<a href="ThermoGC.html">ThermoGC.html (WWW hypertext)</a><br>
<a href="ThermoGC.ps.gz">ThermoGC.ps.gz (6 pages)</a>
"Thermodynamics and Garbage Collection". ACM <cite>Sigplan Notices
29,</cite> 4 (April 1994), 58-63. An earlier version of this paper
was submitted to the OOPSLA'93 Garbage Collection Workshop. A garbage
collector is a <em>refrigerator</em>, thermodynamically speaking.<p>
<a href="ForthStack.html">ForthStack.html (WWW hypertext)</a><br>
<a href="ForthStack.ps.gz">ForthStack.ps.gz (10 pages)</a>
"Linear Logic and Permutation Stacks--The Forth Shall Be First". ACM
<cite>Computer Architecture News 22,</cite> 1 (March 1994), 34-43.
Linear objects and stack architectures (of a particular type) are an
excellent match. Compiling Lisp w/closures into Postscript; the Y
combinator in Postscript! Includes a rather complete bibliography of
stack architectures.<p>
<a href="LQsort.html">LQsort.html (WWW hypertext)</a><br>
<a href="LQsort.ps.gz">LQsort.ps.gz (6 pages)</a>
"A 'Linear Logic' Quicksort". ACM <cite>Sigplan Notices 29,</cite> 2
(February 1994), 13-18. Linear objects can be used to program
'in-place' Quicksorts functionally and efficiently.<p>
<a href="LBoyer.html">LBoyer.html (WWW hypertext)</a><br>
<a href="LBoyer.ps.gz">LBoyer.ps.gz (8 pages)</a>
"The Boyer Benchmark Meets Linear Logic". ACM <cite>Lisp Pointers
VI,</cite> 4 (October/December 1993), 3-10. 'Apples-to-apples' tests
of reference counting versus tracing garbage collection for the Lisp
'Boyer benchmark'.<p>
<a href="LFrpoly.html">LFrpoly.html (WWW hypertext)</a><br>
<a href="LFrpoly.ps.gz">LFrpoly.ps.gz (5 pages)</a>
"Sparse Polynomials and Linear Logic". ACM <cite>Sigsam Bulletin
27,</cite> 4 (December 1993), 10-14. How to do sparse polynomial
multiplication (the Lisp FRPOLY benchmark) functionally and
efficiently using linear objects.<p>
<a href="Gaussian.html">Gaussian.html (WWW hypertext)</a><br>
<a href="Gaussian.ps.gz">Gaussian.ps.gz</a>
"Complex Gaussian Integers for 'Gaussian Graphics'". ACM
<cite>Sigplan Notices 28,</cite>11 (November 1993), 22-27. Neat
things you can do if you index 2D graphical pixels using complex
numbers.<p>
<a href="ObjectIdentity.html">ObjectIdentity.html (WWW hypertext)</a><br>
<a href="ObjectIdentity.ps.gz">ObjectIdentity.ps.gz (26 pages)</a>
"Equal Rights for Functional Objects or, The More Things Change, The
More They Are the Same". ACM <cite>OOPS Messenger 4,</cite> 4
(October 1993), 2-27. Programming language <em>types</em> should
include the notion of whether an object is mutable or immutable.<p>
<a href="LimitedRoots.html">LimitedRoots.html (WWW hypertext)</a><br>
<a href="LimitedRoots.ps.gz">LimitedRoots.ps.gz (11 pages)</a>
"Safe and Leakproof Resource Management using Ada83 Limited Types".
ACM <cite>Ada Letters XIII,</cite> 5 (Sep/Oct 1993), 32-42. How to do
resource management and garbage collection <em>safely</em> 'on top of'
Ada, rather than 'underneath' (in the implementation).<p>
<a href="Encode.html">Encode.html (WWW hypertext)</a><br>
<a href="Encode.ps.gz">Encode.ps.gz (5 pages)</a>
"Strategies for the Lossless Encoding of Strings as Ada Identifiers".
ACM <cite>Ada Letters XIII,</cite> 5 (Sep/Oct 1993), 43-47.
Interesting ways to translate identifiers from one programming
language into another without losing readability or
distinguishability.<p>
<a href="Iterator.html">Iterator.html (WWW hypertext)</a><br>
<a href="Iterator.ps.gz">Iterator.ps.gz (9 pages)</a>
"Iterators: Signs of Weakness in Object-Oriented Languages". ACM
<cite>OOPS Messenger 4,</cite> 3 (July 1993), 18-25. If your language
<em>requires</em> iterators in order to get anything done, your
language's control structures are grossly deficient.<p>
<a href="LimitedRobbery.html">LimitedRobbery.html (WWW hypertext)</a><br>
<a href="LimitedRobbery.ps.gz">LimitedRobbery.ps.gz (5 pages)</a>
"How to Steal from a Limited Private Account--Why Mode IN OUT
Parameters for Limited Types Must be Passed by Reference". ACM
<cite>Ada Letters XIII,</cite> 3 (May/June 1993), 91-95. Passing IN
OUT parameters of limited type by copy-in, copy-out opens up a major
loophole in Ada's type safety, which can be closed only by requiring
that such parameters be passed by reference.<p>
<a href="YoungGen.html">YoungGen.html (WWW hypertext)</a><br>
<a href="YoungGen.ps.gz">YoungGen.ps.gz (3 pages)</a>
"'Infant Mortality' and Generational Garbage Collection". ACM
<cite>Sigplan Notices 28,</cite> 4 (April 1993), 55-57. The
intuitions behind 'generational garbage collectors' are sometimes not
well thought out.<p>
<a href="APLPerms.ps.gz">APLPerms.ps.gz (5 pages)</a>
"On the Permutations of a Vector Obtainable through the Restructure
and Transpose Operators of APL". ACM APL <cite>Quote Quad 23,</cite>
2 (December 1992), 27-31. Optimizations of APL 'restructure'
('reshape') and 'transpose' operators. This paper was written in
1974-1975.<p>
<a href="Inlines.html">Inlines.html (WWW hypertext)</a><br>
<a href="Inlines.ps.gz">Inlines.ps.gz (8 pages)</a>
"Inlining Semantics for Subroutines which are Recursive". ACM
<cite>Sigplan Notices 27,</cite> 12 (December 1992), 39-46. A
semantics for subroutine 'inlining' which handles recursive
subroutines and 'unrolls' tail-recursive loops.<p>
<a href="MetaCircular.html">MetaCircular.html (WWW hypertext)</a><br>
<a href="MetaCircular.ps.gz">MetaCircular.ps.gz (10 pages)</a>
"Metacircular Semantics for Common Lisp Special Forms". ACM
<cite>Lisp Pointers V,</cite> 4 (Oct-Dec 1992), 11-20. Expressing
various combinations of Common Lisp 'special forms' in terms of one
another.<p>
<a href="ReverseGC.html">ReverseGC.html (WWW hypertext)</a><br>
<a href="ReverseGC.ps.gz">ReverseGC.ps.gz (13 pages)</a>
"NREVERSAL of Fortune--the Thermodynamics of Garbage Collection".
<cite>Proc. Int'l Workshop on Memory Mgmt.,</cite> St. Malo, France,
Sept., 1992, Springer LNCS 637, 1992. How to build reversible Lisp
computers, which may generate less heat.<p>
<a href="BoyerB.html">BoyerB.html (WWW hypertext)</a><br>
<a href="BoyerB.ps.gz">BoyerB.ps.gz (2 pages)</a>
"The Boyer Benchmark at Warp Speed". ACM <cite>Lisp Pointers
V,</cite> 3 (Jul-Sep 1992), 13-14. Using 'memoization' to speed up
the Boyer benchmark.<p>
<a href="TriangB.html">TriangB.html (WWW hypertext)</a><br>
<a href="TriangB.ps.gz">TriangB.ps.gz (3 pages)</a>
"The Gabriel 'Triangle' Benchmark at Warp Speed". ACM <cite>Lisp
Pointers V,</cite> 3 (Jul-Sep 1992), 15-17. Using bit vectors and
memoization to speed up the Triangle benchmark.<p>
<a href="PuzzleB.html">PuzzleB.html (WWW hypertext)</a><br>
<a href="PuzzleB.ps.gz">PuzzleB.ps.gz (4 pages)</a>
"Speeding up the 'Puzzle' Benchmark a 'Bit'". ACM <cite>Lisp Pointers
V,</cite> 3 (Jul-Sep 1992), 18-21. Using bit vectors to speed up the
Puzzle benchmark.<p>
<a href="TakB.html">TakB.html (WWW hypertext)</a><br>
<a href="TakB.ps.gz">TakB.ps.gz (2 pages)</a>
"A Tachy 'TAK'". ACM <cite>Lisp Pointers V,</cite> 3 (Jul-Sep 1992),
22-23. Using memoization to speed up the TAK benchmark.<p>
<a href="Subtypep.html">Subtypep.html (WWW hypertext)</a><br>
<a href="Subtypep.ps.gz">Subtypep.ps.gz (23 pages)</a>
"A Decision Procedure for Common Lisp's SUBTYPEP Predicate". <cite>J.
Lisp and Symbolic Computation 5</cite>, 3 (Sept. 1992), 157-190. How
to eliminate the kludgery when implementing Common Lisp's 'subtypep'
function, by using bit vectors.<p>
<a href="LinearLisp.html">LinearLisp.html (WWW hypertext)</a><br>
<a href="LinearLisp.ps.gz">LinearLisp.ps.gz (10 pages)</a>
"Lively Linear Lisp--'Look Ma, No Garbage!'". ACM <cite>Sigplan
Notices 27,</cite> 8 (August 1992),89-98. How to implement a 'linear'
language efficiently through 'behind the scenes' hash consing.<p>
<a href="SigAda92Positions.html">SigAda92Positions.html (WWW hypertext)</a><br>
<a href="SigAda92Positions.ps.gz">SigAda92Positions.ps.gz (3 pages)</a>
"Ada9X Issues for AI Systems". Issues paper for Ada/AI/RT WG
Workshop, Summer '92 SigAda Meeting, June 24-25, 1992.<p>
<a href="BuriedStale.html">BuriedStale.html (WWW hypertext)</a><br>
<a href="BuriedStale.ps.gz">BuriedStale.ps.gz (9 pages)</a>
"The Buried Binding and Dead Binding Problems of Lisp 1.5". ACM
<cite>Lisp Pointers V,</cite> 2 (Apr-Jun 1992), 11-19. An early (1976)
discussion of the space requirements of function closures.<p>
<a href="CritLisp.html">CritLisp.html (WWW hypertext)</a><br>
<a href="CritLisp.ps.gz">CritLisp.ps.gz (18 pages)</a>
"Critique of DIN Kernel Lisp Definition". <cite>Lisp and Symbolic
Compututation 4,</cite> 4 (March 1992), 371-398. (Although nominally
about a European proposal for a standard Lisp, this paper talks about
Lisp capabilities in general.)<p>
<a href="NoMotionGC.html">NoMotionGC.html (WWW hypertext)</a><br>
<a href="NoMotionGC.ps.gz">NoMotionGC.ps.gz (5 pages)</a>
"The Treadmill: Real-Time Garbage Collection without Motion Sickness".
ACM <cite>Sigplan Notices 27,</cite> 3 (March 1992), 66-70. How to do
real-time garbage collection without copying.<p>
<a href="LazyAlloc.html">LazyAlloc.html (WWW hypertext)</a><br>
<a href="LazyAlloc.ps.gz">LazyAlloc.ps.gz (11 pages)</a>
"CONS Should not CONS its Arguments". ACM <cite>Sigplan Notices
27,</cite> 3 (March 1992), 24-34. How to <em>safely</em> allocate
stuff on the stack.<p>
<a href="AB-mod-N.html">AB-mod-N.html (WWW hypertext)</a><br>
<a href="AB-mod-N.pdf">AB-mod-N.pdf (4 pages)</a>
"Computing A*B (mod N) Efficiently in ANSI C". ACM <cite>Sigplan
Notices 27,</cite> 1 (January 1992), 95-98.<p>
<a href="PrecSched.html">PrecSched.html (WWW hypertext)</a><br>
<a href="PrecSched.ps.gz">PrecSched.ps.gz (5 pages)</a>
"Precise Instruction Scheduling without a Precise Machine Model". ACM
<cite>Computer Architecture News 19,</cite> 2 (December 1991), 4-8.<p>
<a href="OOAdaLetters.html">OOAdaLetters.html (WWW hypertext)</a><br>
<a href="OOAdaLetters.ps.gz">OOAdaLetters.ps.gz (12 pages)</a>
"Object-Oriented Programming in Ada83--Genericity Rehabilitated". ACM
<cite>Ada Letters XI,</cite> 9 (Nov/Dec 1991), 116-127. How to do
single inheritance OO programming in Ada83 using overloading and
generics.<p>
<a href="CacheCGC.html">CacheCGC.html (WWW hypertext)</a><br>
<a href="CacheCGC.ps.gz">CacheCGC.ps.gz (8 pages)</a>
"Cache-Conscious Copying Collectors". OOPSLA'91/GC'91 Workshop on
Garbage Collection.<p>
<a href="LPprogram.html">LPprogram.html (WWW hypertext)</a><br>
<a href="LPprogram.ps.gz">LPprogram.ps.gz (12 pages)</a>
"Structured Programming with Limited Private Types in Ada". ACM
<cite>Ada Letters XI,</cite> 5 (Jul/Aug 1991), 79-90. How to program
with Ada's 'limited' (assignment-less) types.<p>
<a href="CLOStrophobia.html">CLOStrophobia.html (WWW hypertext)</a><br>
<a href="CLOStrophobia.ps.gz">CLOStrophobia.ps.gz (12 pages)</a>
"CLOStrophobia: Its Etiology and Treatment". ACM <cite>OOPS Messenger
2,</cite> 4 (October 1991), 4-15. How to make the Common Lisp Object
System <em>safely</em> more efficient.<p>
<a href="Prag-Parse.html">Prag-Parse.html (WWW hypertext)</a><br>
<a href="Prag-Parse.ps.gz">Prag-Parse.ps.gz (14 pages)</a>
"Pragmatic Parsing in Common Lisp". ACM <cite>Lisp Pointers 4,</cite>
2 (Apr-Jun 1991), 3-15. If you have Common Lisp, you shouldn't need
to hack Unix 'lex' and 'yacc'.<p>
<a href="ShallowArrays.html">ShallowArrays.html (WWW hypertext)</a><br>
<a href="ShallowArrays.ps.gz">ShallowArrays.ps.gz (4 pages)</a>
"Shallow Binding Makes Functional Arrays Fast". ACM <cite>Sigplan
Notices 26,</cite> 8 (1991), 145-147. Single-threaded functional
arrays have O(1) update using 'shallow binding'.<p>
<a href="BitSearch.html">BitSearch.html (WWW hypertext)</a><br>
<a href="BitSearch.ps.gz">BitSearch.ps.gz (7 pages)</a>
"The Efficient Implementation of Common Lisp's SEARCH Function on
Bit-vectors". Unpublished April, 1991 memo on how byte-parallelism
can be utilized to achieve high-speed on searches for an unaligned
bit-substring within a bit-vector.<p>
<a href="Share-Unify.html">Share-Unify.html (WWW hypertext)</a><br>
<a href="Share-Unify.ps.gz">Share-Unify.ps.gz (9 pages)</a>
"Unify and Conquer (Garbage, Updating, Aliasing, ...) in Functional
Languages". <cite>Proc. 1990 ACM Lisp and Functional Programming
Conf.,</cite> Nice, France, June, 1990, 218-226. ML type inference
<em>already</em> generates pretty good sharing/aliasing information.<p>
<a href="TreeShadow.html">TreeShadow.html (WWW hypertext)</a><br>
<a href="TreeShadow.ps.gz">TreeShadow.ps.gz (12 pages)</a>
"Worlds in Collision: A Mostly Functional Model of Concurrency Control
and Recovery". Unpublished, 1990. Shallow binding and concurrency
control. Write-ahead and write-behind for database and transaction
recovery are simply various versions of shallow binding.<p>
<a href="TInference.html">TInference.html (WWW hypertext)</a><br>
<a href="TInference.ps.gz">TInference.ps.gz (26 pages)</a>
"The Nimble Type Inferencer for Common Lisp-84". Unpublished memo,
1990. Set-based type inference for pre-CLOS Common Lisp.<p>
<a href="Bitvectors.html">Bitvectors.html (WWW hypertext)</a><br>
<a href="Bitvectors.ps.gz">Bitvectors.ps.gz (15 pages)</a>
"Efficient Implementation of Bit-vector Operations in Common Lisp".
ACM <cite>Lisp Pointers 3,</cite> 2-4 (Apr-Jun 1990), 8-22. How to
implement bit vector operations efficiently.<p>
<a href="Micro-SPL.txt">Micro-SPL.txt</a>
"High Level Language Programs Run Ten Times Faster in Microstore",
with Clinton Parker, Nov. 1980. Short description of the performance
results from a compiler from a C-like language to the Xerox Alto
microcode. The following report gives more details.<p>
<a href="MicroSPL.ps.gz">MicroSPL.ps.gz (22 pages)</a>
"Micro SPL", with Clinton Parker, Synapse Computer Services Report,
Sept. 1979. Also Tech. Report 62, U. Roch. Comp. Sci. Dept.,
Feb. 1980. This document describes the Micro-SPL language and
compiler. The Micro-SPL compiler converts programs in Micro-SPL, a
high level programming language similar to C or Algol, directly into
microcode for the Xerox Alto minicomputer. The Micro-SPL compiler
generates microcode which is competitive with hand microcode, yet
takes only 30-50% as long to write and 10% as long to debug.
Micro-SPL generated microcode runs over ten times faster than an
equivalent BCPL program and perhaps half as fast as good hand written
microcode without losing the advantage of writing in a high level
language.<p>
<a href="RedundantID.html">RedundantID.html</a>
"A Source of Redundant Identifiers in PASCAL Programs". ACM
<i>Sigplan Notices 15,</i> 2 (February 1980), 14-16. Gratuitous
restrictions in programming languages cost time, money and conceptual
load on programmers.<p>
<a href="OptAlloc.html">OptAlloc.html (WWW hypertext)</a><br>
<a href="OptAlloc.ps.gz">OptAlloc.ps.gz (3 pages)</a>
"Optimizing Allocation and Garbage Collection of Spaces in MacLisp".
In Winston and Brown, eds. <cite>Artificial Intelligence: An MIT
Perspective.</cite> MIT Press, 1979. How to allocate the sizes of the
various spaces in 'big bag of pages' (BIBOP) garbage collection
systems.<p>
<a href="RealTimeGC.html">RealTimeGC.html (WWW hypertext)</a><br>
<a href="RealTimeGC.ps.gz">RealTimeGC.ps.gz (13 pages)</a>
"List Processing in Real Time on a Serial Computer",
<cite>Communications of the ACM 21,</cite> 4 (April 1978), 280-294.
Discusses copying garbage collection, incremental (real-time) garbage
collection, real-time reference counting, etc.<p>
<a href="ShallowBinding.html">ShallowBinding.html (WWW hypertext)</a><br>
<a href="ShallowBinding.ps.gz">ShallowBinding.ps.gz (7 pages)</a>
"Shallow Binding in Lisp 1.5", <cite>Communications of the ACM
21,</cite> 7 (July 1978), 565-569. An elegant 'tree-rerooting' model
for binding environments. It also works for a variety of other
"environment"-like mechanisms such as functional arrays for O(1)
update and write-ahead/write-behind mechanisms for database recovery.<p>
<a href="Futures.html">Futures.html (WWW hypertext)</a><br>
<a href="Futures.ps.gz">Futures.ps.gz (5 pages)</a>
"The Incremental Garbage Collection of Processes", with Carl Hewitt,
ACM <cite>Sigplan Notices 12,</cite> 8 (August 1977), 55-59. An early
discussion of the concept of 'futures' in a parallel functional
programming language. Naively uses 'reachability' for eliminating
garbage processes, which is now known to be insufficient in the
presence of shared cells with assignment.<p>
<a href="lingol/home.html">Lingol</a>
Access to 'lingol' directory. Papers re Vaughan Pratt's Lingol
natural language parsing system.<p>
Coming soon to a web near you:<p>
"Rabin's Proof of the Undecidability of the Reachability Set Inclusion
Problem of Vector Addition Systems". Computation Structures Group
Memo 79, Project MAC, MIT, July 1973.<p>
<a href="PetriNetLanguages.ps.gz">PetriNetLanguages.ps.gz (8 pages)</a>
"Petri Nets and Languages". Computation Structures Group Memo 68,
Project MAC, MIT, May 1972. Includes as an appendix "A Canonic Form
for Marked Graphs", which shows an elegant way to prove equivalence of
Marked Graphs (a subset of Petri Nets) by reducing them to a canonic
form.<p>
</body></html>