Henry Baker's www/ftp directory: ftp.netcom.com:/pub/hb/hbaker/home.html Please note that you can now access this archive more easily using the World-Wide Web. Just use the WWW address ftp://ftp.netcom.com/pub/hb/hbaker/home.html 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. This directory contains references to some papers of Henry G. Baker. Unix 'compressed' versions of Postscript files in this directory are noted in square brackets -- e.g., "[foo.ps.Z]". Most do not have 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). Please contact hbaker@netcom.com if you have any problems with these files. Various published and unpublished letters to the editors are stored in the directory './letters'. Bibliography on Quaternions. [QuaternionRefs.txt] "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." ACM Sigplan Notices 30, 9 (Sept. 1995), 17-20. How to do accurate GC and tail-calling in C. "'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. 8 pages. [Use1Var.ps.Z] "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. 6 pages. [LRefCounts.ps.Z] "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. 6 pages. [ThermoGC.ps.Z] "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. 10 pages. [ForthStack.ps.Z] "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. 6 pages. [LQsort.ps.Z] "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'. 8 pages. [LBoyer.ps.Z] "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. 5 pages. [LFrpoly.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. 10 pages. [Gaussian.ps.Z] "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. 26 pages. [ObjectIdentity.ps.Z] "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). 11 pages. [LimitedRoots.ps.Z] "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. 5 pages. [Encode.ps.Z] "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. 9 pages. [Iterator.ps.Z] "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. 5 pages. [LimitedRobbery.ps.Z] "'Infant Mortality' and Generational Garbage Collection". Sigplan Notices 28,4 (April 1993), 55-57. The intuitions behind 'generational garbage collectors' are sometimes not well thought out. 3 pages. [YoungGen.ps.Z] "On the Permutations of a Vector Obtainable through the Restructure and Transpose Operators of APL". APL Quote Quad 23,2 (December 1992), 27-31. Optimizations of APL 'restructure' ('reshape') and 'transpose' operators. This paper was written in 1974-1975. 5 pages. [APLPerms.ps.Z] "Inlining Semantics for Subroutines which are Recursive". Sigplan Notices 27,12 (December 1992), 39-46. A semantics for subroutine 'inlining' which handles recursive subroutines and 'unrolls' tail-recursive loops. 8 pages. [Inlines.ps.Z] "Less Complex Elementary Functions". ACM Sigplan Notices 27,11 (November 1992), 15-16. Complex elementary functions separated into their real and imaginary parts. "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. 10 pages. [MetaCircular.ps.Z] "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. 13 pages. [ReverseGC.ps.Z] "The Boyer Benchmark at Warp Speed". ACM Lisp Pointers V,3 (Jul-Sep 1992), 13-14. Using 'memoization' to speed up the Boyer benchmark. 2 pages. [BoyerB.ps.Z] "The Gabriel 'Triangle' Benchmark at Warp Speed". Lisp Pointers V,3 (Jul-Sep 1992), 15-17. Using bit vectors and memoization to speed up the Triangle benchmark. 3 pages. [TriangB.ps.Z] "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. 4 pages. [PuzzleB.ps.Z] "A Tachy 'TAK'". ACM Lisp Pointers V,3 (Jul-Sep 1992), 22-23. Using memoization to speed up the TAK benchmark. 2 pages. [TakB.ps.Z] "A Decision Procedure for Common Lisp's SUBTYPEP Predicate". J. Lisp and Symbolic Computation 5 (1992), 155-188. How to eliminate the kludgery when implementing Common Lisp's 'subtypep' function, by using bit vectors. 23 pages. [Subtypep.ps.Z] "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. 10 pages. [LinearLisp.ps.Z] "Ada9X Issues for AI Systems". Issues paper for Ada/AI/RT WG Workshop, Summer '92 SigAda Meeting, June 24-25, 1992. 3 pages. [SigAda92Positions.ps.Z] "The Buried Binding and Dead Binding Problems of Lisp 1.5". Lisp Pointers V,2 (Apr-Jun 1992), 11-19. An early (1976) discussion of the space requirements of function closures. 9 pages. [BuriedStale.ps.Z] "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.) 18 pages. [CritLisp.ps.Z] "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. 5 pages. [NoMotionGC.ps.Z] "CONS Should not CONS its Arguments". ACM Sigplan Notices 27,3 (March 1992), 24-34. How to _safely_ allocate stuff on the stack. 10 pages. [LazyAlloc.ps.Z] "Computing A*B (mod N) Efficiently in ANSI C". ACM Sigplan Notices 27,1 (January 1992), 95-98. 4 pages. [AB-mod-N.ps.Z] "Precise Instruction Scheduling without a Precise Machine Model". ACM Computer Architecture News 19,2 (December 1991), 4-8. 5 pages. [PrecSched.ps.Z] "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. 12 pages. [OOAdaLetters.ps.Z] "Cache-Conscious Copying Collectors". OOPSLA'91/GC'91 Workshop on Garbage Collection. 8 pages. [CacheCGC.ps.Z] "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. 12 pages. [LPprogram.ps.Z] "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. 12 pages. [CLOStrophobia.ps.Z] "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'. 14 pages. [Prag-Parse.ps.Z] "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'. 4 pages. [ShallowArrays.ps.Z] "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. 7 pages. [BitSearch.ps.Z] "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. 9 pages. [Share-Unify.ps.Z] "Worlds in Collision: A Mostly Functional Model of Concurrency Control and Recovery", 1990. Shallow binding and concurrency control. Write-ahead and write-behind for database and transaction recovery are simply various versions of shallow binding. 12 pages. [TreeShadow.ps.Z] "The Nimble Type Inferencer for Common Lisp-84", 1990. Set-based type inference for pre-CLOS Common Lisp. 26 pages. [TInference.ps.Z] "The NIMBLE Project--An Applications Compiler for Real-Time Common Lisp". Proc. InfoJapan'90 Int'l. Conf. on Info. Tech., Oct. 1-5,1990. "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. 15 pages. [Bitvectors.ps.Z] "The NIMBLE Project--Real-Time Common Lisp for Embedded Expert Systems Applications". Proc. 1989 AIAA Computers in Aerospace Conf. "Complex Polynomial Factoring". Unpublished memo, July 1986. Musings about efficient factoring of polynomials with complex coefficients. [Polyroots.ps.Z] "High Level Language Programs Run Ten Times Faster in Microstore", with Clinton Parker, Nov. 1980. [Micro-SPL.ascii] 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. "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. 22 pages. [MicroSPL.ps.Z] "A Source of Redundant Identifiers in PASCAL Programs". ACM Sigplan Notices 15, 2 (Feb. 1980), 14-16. Silly language restrictions cost time, money and conceptual load for programmers. "Optimizing Allocation and Garbage Collection of Spaces in MacLisp". In Winston and Brown, ed. 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. 3 pages. [OptAlloc.ps.Z] "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. 13 pages. [RealTimeGC.ps.Z] "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. 7 pages. [ShallowBinding.ps.Z] "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. 5 pages. [Futures.ps.Z] "Laws for Communicating Parallel Processes", with Carl Hewitt, IFIP 77 Proc., North-Holland. "A New Lingol System". Unpublished memo, April, 1977. Discusses the improvements made to Vaughan Pratt's Lingol natural language parsing system to better handle morphological decomposition of words, irregular verbs and nouns, subject-predicate agreement, etc. 8 pages. [lingol/NLingol.ps.Z] "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. "Petri Nets and Languages". Computation Structures Group Memo 68, Project MAC, MIT, May 1972.