*********************************************************************** * 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 (hbaker@netcom.com) * ***********************************************************************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.
Most files are WWW hypertext ('html') or Unix '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).
Files are generally in reverse chronological order.
Please contact hbaker@netcom.com if you have any problems. Click here to access gratuitous waste of bandwidth page
Garbage In/Garbage Out Columns from ACM Sigplan Notices
IWMM'95 Home Page International Workshop on Memory Management 1995
cornellcstr75-245.ps.gz cornellcstr75-245.dvi.gz "The Complexity of the Quaternion Product" by Howell & Lafon, Cornell CS TR75-245, June 1975. Quaternion product in only eight real multiplications. (Original cornellcstr75-245.tar.gz 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).
stanfordaiwp79-salamin.ps.gz stanfordaiwp79-salamin.dvi.gz "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.
Hypertext HAKMEM (MIT AI Memo 239)
Hypertext PDP-10 Assembly Language Info
Common Lisp, the Language, 2nd Ed (CMU hypertext)
Paul Wilson's Garbage Collection Archive
letters Various published and unpublished letters
QuaternionRefs.txt Bibliography on Quaternions.
FAQ-lat-long.txt Computing Great Circle Distances from Latitudes and Longitudes.
CheneyMTA.html (WWW hypertext)
CheneyMTA.ps.Z (4 pages)
"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
Sigplan Notices 30, 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 cboyer13.c,
in which the Gabriel Boyer Lisp benchmark is translated into C using
the methods of this paper.
Use1Var.html (WWW hypertext)
Use1Var.ps.Z (8 pages)
"'Use-Once' Variables and Linear Objects--Storage Management,
Reflection and Multi-Threading". ACM Sigplan Notices 30,
1 (Jan. 1995), 45-52. A high-level discussion of 'linear' and
'non-linear' (traditional) names/variables/objects in programming
languages.
LRefCounts.html (WWW hypertext)
LRefCounts.ps.Z (6 pages)
"Minimizing Reference Count Updating with Deferred and Anchored
Pointers for Functional Data Structures". ACM Sigplan Notices
29, 9 (September 1994), 38-43. Safe mechanisms for reducing
reference count updating overhead.
ThermoGC.html (WWW hypertext)
ThermoGC.ps.Z (6 pages)
"Thermodynamics and Garbage Collection". ACM Sigplan Notices
29, 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 refrigerator, thermodynamically speaking.
ForthStack.html (WWW hypertext)
ForthStack.ps.Z (10 pages)
"Linear Logic and Permutation Stacks--The Forth Shall Be First". ACM
Computer Architecture News 22, 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.
LQsort.html (WWW hypertext)
LQsort.ps.Z (6 pages)
"A 'Linear Logic' Quicksort". ACM Sigplan Notices 29, 2
(February 1994), 13-18. Linear objects can be used to program
'in-place' Quicksorts functionally and efficiently.
LBoyer.html (WWW hypertext)
LBoyer.ps.Z (8 pages)
"The Boyer Benchmark Meets Linear Logic". ACM Lisp Pointers
VI, 4 (October/December 1993), 3-10. 'Apples-to-apples' tests
of reference counting versus tracing garbage collection for the Lisp
'Boyer benchmark'.
LFrpoly.html (WWW hypertext)
LFrpoly.ps.Z (5 pages)
"Sparse Polynomials and Linear Logic". ACM Sigsam Bulletin
27, 4 (December 1993), 10-14. How to do sparse polynomial
multiplication (the Lisp FRPOLY benchmark) functionally and
efficiently using linear objects.
Gaussian.html (WWW hypertext)
Gaussian.ps.Z
"Complex Gaussian Integers for 'Gaussian Graphics'". ACM
Sigplan Notices 28,11 (November 1993), 22-27. Neat
things you can do if you index 2D graphical pixels using complex
numbers.
ObjectIdentity.html (WWW hypertext)
ObjectIdentity.ps.Z (26 pages)
"Equal Rights for Functional Objects or, The More Things Change, The
More They Are the Same". ACM OOPS Messenger 4, 4
(October 1993), 2-27. Programming language types should
include the notion of whether an object is mutable or immutable.
LimitedRoots.html (WWW hypertext)
LimitedRoots.ps.Z (11 pages)
"Safe and Leakproof Resource Management using Ada83 Limited Types".
ACM Ada Letters XIII, 5 (Sep/Oct 1993), 32-42. How to do
resource management and garbage collection safely 'on top of'
Ada, rather than 'underneath' (in the implementation).
Encode.html (WWW hypertext)
Encode.ps.Z (5 pages)
"Strategies for the Lossless Encoding of Strings as Ada Identifiers".
ACM Ada Letters XIII, 5 (Sep/Oct 1993), 43-47.
Interesting ways to translate identifiers from one programming
language into another without losing readability or
distinguishability.
Iterator.html (WWW hypertext)
Iterator.ps.Z (9 pages)
"Iterators: Signs of Weakness in Object-Oriented Languages". ACM
OOPS Messenger 4, 3 (July 1993), 18-25. If your language
requires iterators in order to get anything done, your
language's control structures are grossly deficient.
LimitedRobbery.html (WWW hypertext)
LimitedRobbery.ps.Z (5 pages)
"How to Steal from a Limited Private Account--Why Mode IN OUT
Parameters for Limited Types Must be Passed by Reference". ACM
Ada Letters XIII, 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.
YoungGen.html (WWW hypertext)
YoungGen.ps.Z (3 pages)
"'Infant Mortality' and Generational Garbage Collection". ACM
Sigplan Notices 28, 4 (April 1993), 55-57. The
intuitions behind 'generational garbage collectors' are sometimes not
well thought out.
APLPerms.ps.Z (5 pages) "On the Permutations of a Vector Obtainable through the Restructure and Transpose Operators of APL". ACM APL Quote Quad 23, 2 (December 1992), 27-31. Optimizations of APL 'restructure' ('reshape') and 'transpose' operators. This paper was written in 1974-1975.
Inlines.html (WWW hypertext)
Inlines.ps.Z (8 pages)
"Inlining Semantics for Subroutines which are Recursive". ACM
Sigplan Notices 27, 12 (December 1992), 39-46. A
semantics for subroutine 'inlining' which handles recursive
subroutines and 'unrolls' tail-recursive loops.
MetaCircular.html (WWW hypertext)
MetaCircular.ps.Z (10 pages)
"Metacircular Semantics for Common Lisp Special Forms". ACM
Lisp Pointers V, 4 (Oct-Dec 1992), 11-20. Expressing
various combinations of Common Lisp 'special forms' in terms of one
another.
ReverseGC.html (WWW hypertext)
ReverseGC.ps.Z (13 pages)
"NREVERSAL of Fortune--the Thermodynamics of Garbage Collection".
Proc. Int'l Workshop on Memory Mgmt., St. Malo, France,
Sept., 1992, Springer LNCS 637, 1992. How to build reversible Lisp
computers, which may generate less heat.
BoyerB.html (WWW hypertext)
BoyerB.ps.Z (2 pages)
"The Boyer Benchmark at Warp Speed". ACM Lisp Pointers
V, 3 (Jul-Sep 1992), 13-14. Using 'memoization' to speed up
the Boyer benchmark.
TriangB.html (WWW hypertext)
TriangB.ps.Z (3 pages)
"The Gabriel 'Triangle' Benchmark at Warp Speed". ACM Lisp
Pointers V, 3 (Jul-Sep 1992), 15-17. Using bit vectors and
memoization to speed up the Triangle benchmark.
PuzzleB.html (WWW hypertext)
PuzzleB.ps.Z (4 pages)
"Speeding up the 'Puzzle' Benchmark a 'Bit'". ACM Lisp Pointers
V, 3 (Jul-Sep 1992), 18-21. Using bit vectors to speed up the
Puzzle benchmark.
TakB.html (WWW hypertext)
TakB.ps.Z (2 pages)
"A Tachy 'TAK'". ACM Lisp Pointers V, 3 (Jul-Sep 1992),
22-23. Using memoization to speed up the TAK benchmark.
Subtypep.html (WWW hypertext)
Subtypep.ps.Z (23 pages)
"A Decision Procedure for Common Lisp's SUBTYPEP Predicate". J.
Lisp and Symbolic Computation 5, 3 (Sept. 1992), 157-190. How
to eliminate the kludgery when implementing Common Lisp's 'subtypep'
function, by using bit vectors.
LinearLisp.html (WWW hypertext)
LinearLisp.ps.Z (10 pages)
"Lively Linear Lisp--'Look Ma, No Garbage!'". ACM Sigplan
Notices 27, 8 (August 1992),89-98. How to implement a 'linear'
language efficiently through 'behind the scenes' hash consing.
SigAda92Positions.html (WWW hypertext)
SigAda92Positions.ps.Z (3 pages)
"Ada9X Issues for AI Systems". Issues paper for Ada/AI/RT WG
Workshop, Summer '92 SigAda Meeting, June 24-25, 1992.
BuriedStale.html (WWW hypertext)
BuriedStale.ps.Z (9 pages)
"The Buried Binding and Dead Binding Problems of Lisp 1.5". ACM
Lisp Pointers V, 2 (Apr-Jun 1992), 11-19. An early (1976)
discussion of the space requirements of function closures.
CritLisp.html (WWW hypertext)
CritLisp.ps.Z (18 pages)
"Critique of DIN Kernel Lisp Definition". Lisp and Symbolic
Compututation 4, 4 (March 1992), 371-398. (Although nominally
about a European proposal for a standard Lisp, this paper talks about
Lisp capabilities in general.)
NoMotionGC.html (WWW hypertext)
NoMotionGC.ps.Z (5 pages)
"The Treadmill: Real-Time Garbage Collection without Motion Sickness".
ACM Sigplan Notices 27, 3 (March 1992), 66-70. How to do
real-time garbage collection without copying.
LazyAlloc.html (WWW hypertext)
LazyAlloc.ps.Z (11 pages)
"CONS Should not CONS its Arguments". ACM Sigplan Notices
27, 3 (March 1992), 24-34. How to safely allocate
stuff on the stack.
AB-mod-N.html (WWW hypertext)
AB-mod-N.ps.Z (4 pages)
"Computing A*B (mod N) Efficiently in ANSI C". ACM Sigplan
Notices 27, 1 (January 1992), 95-98.
PrecSched.html (WWW hypertext)
PrecSched.ps.Z (5 pages)
"Precise Instruction Scheduling without a Precise Machine Model". ACM
Computer Architecture News 19, 2 (December 1991), 4-8.
OOAdaLetters.html (WWW hypertext)
OOAdaLetters.ps.Z (12 pages)
"Object-Oriented Programming in Ada83--Genericity Rehabilitated". ACM
Ada Letters XI, 9 (Nov/Dec 1991), 116-127. How to do
single inheritance OO programming in Ada83 using overloading and
generics.
CacheCGC.html (WWW hypertext)
CacheCGC.ps.Z (8 pages)
"Cache-Conscious Copying Collectors". OOPSLA'91/GC'91 Workshop on
Garbage Collection.
LPprogram.html (WWW hypertext)
LPprogram.ps.Z (12 pages)
"Structured Programming with Limited Private Types in Ada". ACM
Ada Letters XI, 5 (Jul/Aug 1991), 79-90. How to program
with Ada's 'limited' (assignment-less) types.
CLOStrophobia.html (WWW hypertext)
CLOStrophobia.ps.Z (12 pages)
"CLOStrophobia: Its Etiology and Treatment". ACM OOPS Messenger
2, 4 (October 1991), 4-15. How to make the Common Lisp Object
System safely more efficient.
Prag-Parse.html (WWW hypertext)
Prag-Parse.ps.Z (14 pages)
"Pragmatic Parsing in Common Lisp". ACM Lisp Pointers 4,
2 (Apr-Jun 1991), 3-15. If you have Common Lisp, you shouldn't need
to hack Unix 'lex' and 'yacc'.
ShallowArrays.html (WWW hypertext)
ShallowArrays.ps.Z (4 pages)
"Shallow Binding Makes Functional Arrays Fast". ACM Sigplan
Notices 26, 8 (1991), 145-147. Single-threaded functional
arrays have O(1) update using 'shallow binding'.
BitSearch.html (WWW hypertext)
BitSearch.ps.Z (7 pages)
"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.
Share-Unify.html (WWW hypertext)
Share-Unify.ps.Z (9 pages)
"Unify and Conquer (Garbage, Updating, Aliasing, ...) in Functional
Languages". Proc. 1990 ACM Lisp and Functional Programming
Conf., Nice, France, June, 1990, 218-226. ML type inference
already generates pretty good sharing/aliasing information.
TreeShadow.html (WWW hypertext)
TreeShadow.ps.Z (12 pages)
"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.
TInference.html (WWW hypertext)
TInference.ps.Z (26 pages)
"The Nimble Type Inferencer for Common Lisp-84". Unpublished memo,
1990. Set-based type inference for pre-CLOS Common Lisp.
Bitvectors.html (WWW hypertext)
Bitvectors.ps.Z (15 pages)
"Efficient Implementation of Bit-vector Operations in Common Lisp".
ACM Lisp Pointers 3, 2-4 (Apr-Jun 1990), 8-22. How to
implement bit vector operations efficiently.
Micro-SPL.txt "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.
MicroSPL.ps.Z (22 pages) "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.
RedundantID.html "A Source of Redundant Identifiers in PASCAL Programs". ACM Sigplan Notices 15, 2 (February 1980), 14-16. Gratuitous restrictions in programming languages cost time, money and conceptual load on programmers.
OptAlloc.html (WWW hypertext)
OptAlloc.ps.Z (3 pages)
"Optimizing Allocation and Garbage Collection of Spaces in MacLisp".
In Winston and Brown, eds. Artificial Intelligence: An MIT
Perspective. MIT Press, 1979. How to allocate the sizes of the
various spaces in 'big bag of pages' (BIBOP) garbage collection
systems.
RealTimeGC.html (WWW hypertext)
RealTimeGC.ps.Z (13 pages)
"List Processing in Real Time on a Serial Computer",
Communications of the ACM 21, 4 (April 1978), 280-294.
Discusses copying garbage collection, incremental (real-time) garbage
collection, real-time reference counting, etc.
ShallowBinding.html (WWW hypertext)
ShallowBinding.ps.Z (7 pages)
"Shallow Binding in Lisp 1.5", Communications of the ACM
21, 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.
Futures.html (WWW hypertext)
Futures.ps.Z (5 pages)
"The Incremental Garbage Collection of Processes", with Carl Hewitt,
ACM Sigplan Notices 12, 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.
Lingol Access to 'lingol' directory. Papers re Vaughan Pratt's Lingol natural language parsing system.
Coming soon to a web near you:
"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.
PetriNetLanguages.ps.Z (8 pages) "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.