[Prev][Next][Index][Thread]

ftpable papers on computing with linear variables/objects



I have recently set up an ftp directory in which I have placed most of my
recent papers, including a number which discuss computational experiments
with a 'linear' dialect of Lisp.

I don't consider myself a fire-breathing theoretician, so please don't
criticize my descriptions of 'linear' things too harshly.

(BTW: I can guarantee that there are _no_ turnstiles in any of my
papers.  Among other reasons, I don't believe that any of my fonts
even _have_ turnstiles.)

Below is a fragment of my ftp README file:

----------

"'Use-Once' Variables and Linear Objects--Storage Management,
Reflection and Multi-Threading".  Submitted to ACM Sigplan Notices,
September, 1994.  [Use1Var.ps.Z] A high-level discussion of 'linear'
and 'non-linear' (traditional) names/variables/objects in programming
languages.

"Minimizing Reference Count Updating with Deferred and Anchored
Pointers for Functional Data Structures".  ACM Sigplan Notices 29, 9
(September 1994), 38-43. [LRefCounts.ps.Z] Safe mechanisms for
reducing reference count updating overhead using some linear ideas.

"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.  [ThermoGC.ps.Z] A
garbage collector is a _refrigerator_, thermodynamically speaking.

"Linear Logic and Permutation Stacks--The Forth Shall Be First".  ACM
Computer Architecture News 22, 1 (March 1994), 34-43.
[ForthStack.ps.Z] 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.

"A 'Linear Logic' Quicksort".  ACM Sigplan Notices 29, 2 (February
1994), 13-18. [LQsort.ps.Z] Linear objects can be used to program
'in-place' Quicksorts functionally and efficiently.

"The Boyer Benchmark Meets Linear Logic".  ACM Lisp Pointers VI, 4
(October/December 1993), 3-10. [LBoyer.ps.Z] 'Apples-to-apples' tests
of reference counting versus tracing garbage collection for the Lisp
'Boyer benchmark'.

"Sparse Polynomials and Linear Logic".  ACM Sigsam Bulletin 27, 4
(December 1993), 10-14. [LFrpoly.ps.Z] How to do sparse polynomial
multiplication (the Lisp FRPOLY benchmark) functionally and
efficiently using linear objects.

"Safe and Leakproof Resource Management using Ada83 Limited Types".
ACM Ada Letters XIII,5 (Sep/Oct 1993), 32-42.  [LimitedRoots.ps.Z] How
to do resource management and garbage collection _safely_ 'on top of'
Ada, rather than 'underneath' (in the implementation).  [Limited types
in Ada were an early attempt at linear types.]

"NREVERSAL of Fortune--the Thermodynamics of Garbage Collection".
Proc. Int'l Workshop on Memory Mgmt., St. Malo, France, Sept., 1992,
Springer LNCS 637, 1992.  [ReverseGC.ps.Z] How to build reversible
Lisp computers, which may generate less heat.

"Lively Linear Lisp--'Look Ma, No Garbage!'".  ACM Sigplan Notices
27,8 (August 1992),89-98.  [LinearLisp.ps.Z] How to implement a
'linear' language efficiently through 'behind the scenes' hash
consing.

"Structured Programming with Limited Private Types in Ada".  ACM Ada
Letters XI,5 (Jul/Aug 1991), 79-90.  [LPprogram.ps.Z] How to program
with Ada's 'limited' (assignment-less) types.

"Shallow Binding Makes Functional Arrays Fast".  ACM Sigplan Notices
26,8 (1991), 145-147. [ShallowArrays.ps.Z] Single-threaded functional
arrays have O(1) update using 'shallow binding'.

"Unify and Conquer (Garbage, Updating, Aliasing, ...) in Functional
Languages".  Proc. 1990 ACM Lisp and Functional Programming Conf.,
Nice, France, June, 1990, 218-226.  [Share-Unify.ps.Z] traditional ML
type inference _already_ generates pretty good sharing/aliasing
information.

"Worlds in Collision: A Mostly Functional Model of Concurrency Control
and Recovery", 1990.  [TreeShadow.ps.Z] Shallow binding and
concurrency control.  Write-ahead and write-behind for database and
transaction recovery are simply various versions of shallow binding.

"Shallow Binding in Lisp 1.5", Communications of the ACM 21,7 (July
1978), 565-569.  [ShallowBinding.ps.Z] 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.

-- 
      Henry Baker
      Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.