POS, OOFS, CL v Scheme, etc.

Henry G. Baker hbaker@netcom.com
Sun, 11 May 1997 07:52:02 -0700 (PDT)

I have been following these discussions, but have not participated in
any detail.  There are a lot of good ideas here -- keep up the good work!

Just a few thoughts.

As I have tried to point out in some of my papers, including 'Equal
Rights', I think that it is very important to provide _functional data
structures_ (read-only data structures) -- i.e., pairs, 'objects',
etc. -- in addition to the usual CL&Scheme objects with 'identity'.  The
major reason is a greater cleanliness of the language, and a greater
efficiency in implementation.

For example, every lisp cons cell in either CL or Scheme can be
mutated, making it a full-fledged object 'with identity', and
guaranteeing a heavyweight implementation when it comes to storing &
committing in an object-oriented database.  For the case of
_functional_ (read-only) cons cells, however, one can copy them at
will, and since they are guaranteed not to be mutated, there is a lot
less work to do in an OOFS/OODB.  I believe that Statice incorporates
such concepts, but they never made it back into the CL language

Given this goal, _neither_ 'standard' CL or Scheme will be acceptable,
but some extension supporting read-only data structures.  I believe
that the incorporation of an OOFS/OODB is so important, that it is
worth leaving the safe harbor of 'standards', and embarking on the
rougher seas of extensions.

Note that such read-only data structures also simplify the interaction
of more distributed systems, where the ability to pass functional
lists without having to worry about mutation becomes very important.

Two relevant papers:

ftp://ftp.netcom.com/pub/hb/hbaker/ObjectIdentity.html  (also .ps.Z)
ftp://ftp.netcom.com/pub/hb/hbaker/TreeShadow.html  (also .ps.Z)


The above recommendations regarding read-only data structures I am
very sure about.

I am less sure about recommending also the addition of
'linear'/'unique' data structures.  These are a kind of 'intersection'
of read-only and read-write data types, in that since they are linear,
it is impossible to tell (in the language itself) whether they are
implemented as read-only (copyable) or mutable data structures.

A number of distributed systems languages have successfully
incorporated linear types: NIL/Hermes, Janus ('logic language'),
Clean, etc.  These provide the ability to talk _directly_ about
_resources_ such as the 'token' in a token-passing system, or a
particular block of storage.  Since such things are inherently linear
-- it makes no sense to talk about 'copying' the block of storage
_itself_ -- linear types can naturally express this important

Once again, this idea can be incorporated into Lisp & Scheme, but
would require some extensions.

The major difficulty in incorporting linear types into Lisp/Scheme is
implementing the responsibility for correctly handling exceptions,
because a linear object _cannot_ be 'lost', but must be explicitly
destroyed by the programmer.  In a LispOS, however, exceptions must be
correctly handled in any case, so since we have no choice, we might as
well think about using linear objects.

If you are interested in learning more about linear types, consult
the following paper and its references:

ftp://ftp.netcom.com/pub/hb/hbaker/Use1Var.html  (also .ps.Z)


The above is 'food for thought'.

Henry Baker
www/ftp directory URL: