Henry Baker's Archive of Research Papers

NOTE: IF YOU CAN SUCCESSFULLY ACCESS THIS PAGE, THEN THE REST ARE ALSO ACCESSIBLE, BUT DUE TO NETCOM'S LOADING, YOU MAY HAVE TO TRY SEVERAL TIMES.
***********************************************************************
* 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

Mark Leone's language people

Linear Logic Bibliography

Lincoln's Linear Logics

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.