Re:How innovative is Clojure as a Lisp dialect from Lisp exp...
by kazinator on Monday January 07, 2019 @05:41AM
(#18844198)
I see now that this term was introduced in a 1986 paper about versioned, immutable data structures (Making Data Structures Persistent, Driscoll, Tarjan et al).
I'm well aware of the techniques, just not the word.
Interestingly, they were aware of the connection between their work and Lisp:
"The node-copying method
of
Section 2
can
be
modified
so
that
it is write-once
except for
access
pointers. The main
modification
is to
handle
inverse
pointers
as
discussed
in
Section
3.
The
write-once
property
is
important
for
certain kinds
of
memory technology.
Also,
it implies
that
any
data
structure
of
constant
bounded
in-degree
that
can
be
built
using
the augmented
LISP
primitives
cons,
cdr,
replaca,
and
replacd
can
be
simulated in linear
time using only
the pure
LISP
primitives
cons,
car,
and
cdr.
Thus
the result sheds light
on
the
power
of
purely
applicative
programming
languages."
Or, rather, it seems they were made aware by a reviewer:
"We
thank
Nick
Pippenger
for
noting
the
connection
between
write-once data
structures
and
the
power
of
pure
LISP."
(Good old Nick didn't go as far as to point out that rplaca and rplacd can introduce cycles, which cannot be constructed with cons over existing structure.)
Sadly, no reviewer similarly piped up about "persistent" being taken already for durable storage.
I'm well aware of the techniques, just not the word.
Interestingly, they were aware of the connection between their work and Lisp:
"The node-copying method of Section 2 can be modified so that it is write-once except for access pointers. The main modification is to handle inverse pointers as discussed in Section 3. The write-once property is important for certain kinds of memory technology. Also, it implies that any data structure of constant bounded in-degree that can be built using the augmented LISP primitives cons, cdr, replaca, and replacd can be simulated in linear time using only the pure LISP primitives cons, car, and cdr. Thus the result sheds light on the power of purely applicative programming languages."
Or, rather, it seems they were made aware by a reviewer:
"We thank Nick Pippenger for noting the connection between write-once data structures and the power of pure LISP."
(Good old Nick didn't go as far as to point out that rplaca and rplacd can introduce cycles, which cannot be constructed with cons over existing structure.)
Sadly, no reviewer similarly piped up about "persistent" being taken already for durable storage.