From: Jack Waugh
Subject: Importance of REPLACA, REPLACD, and the like?
Date:
Message-ID: <22@citcom.UUCP>
Is it possible to solve serious programming applications
with LISP without using replacement operators? To put it
another way, could a list be implemented in any other way
than as a chain of cons nodes? This is a novice type question,
so please don't reply publicly.
From: Silver
Subject: Re: Importance of REPLACA, REPLACD, and the like?
Date:
Message-ID: <13278@topaz.rutgers.edu>
> Is it possible to solve serious programming applications with LISP
> without using replacement operators? To put it another way, could a
> list be implemented in any other way than as a chain of cons nodes?
> This is a novice type question, so please don't reply publicly.
Not nearly so novice as you think. Any thoughts on alternative
structures/paradigms?
name: Andy Gaynor (Silver)
uucp: {ames, cbosgd, harvard, moss, seismo}!rutgers!topaz.rutgers.edu!gaynor
arpa: ······@topaz.rutgers.edu
icbm: 40 34 N / 74 45 W
From: Bart Massey
Subject: Re: Importance of REPLACA, REPLACD, and the like?
Date:
Message-ID: <6601@reed.UUCP>
In article <·····@topaz.rutgers.edu> ······@topaz.rutgers.edu (Silver) writes:
> > Is it possible to solve serious programming applications with LISP
> > without using replacement operators? To put it another way, could a
> > list be implemented in any other way than as a chain of cons nodes?
> > This is a novice type question, so please don't reply publicly.
>
> Not nearly so novice as you think. Any thoughts on alternative
> structures/paradigms?
At Reed college we are currently doing almost all of our lisp
programming in an in-house dialect which supports neither destructive
list functions nor dotted pairs. The internal form of lists is a
lispval car, and a pure-pointer cdr. This greatly increases the
efficiency of the language, effectively making the replacement
operations and dotted-pair notation unnecessary (all we could ever
figure out that they were good for was efficiency anyway, and whatever
they gained in efficiency they lost in verifiability and
understandability.)
We have written several substantial applications in this lisp (e.g. a
UNIX shell, an LL(1) parse table generator) and never once missed the
features we left behind.
In case anyone is interested, the following major changes in the
language were also implemented, and have proven useful:
- Elimination of eq: Using a properly written version of equal, eq is
the first thing to happen anyhow, and we've never encountered a
situation where knowing that two lists were non-eq is "good enough".
- Functions as first class lispvals: We eliminated the seperate
"function cell" in favor of scheme-style first class functions. Seems
like a big win in every way.
- No intrinsic property lists: There's a fairly efficient prop-list
emulation package, but we use it mostly for porting outside code, and
encourage programmers to avoid prop-lists. It's always trivial, when
writing the code, to work around them, and it's yet another extra cell
per atom to be avoided, in addition to often making the code more confusing.
All of the above-mentioned features have been uniformly good
experiences for us. Benefits we expected and received include:
- It's really much harder to write twisty, unreadable lisp code, so we
can generally read other folks' code easier.
- It's much easier to teach the language to novices, as things are
much more uniform and the internals are much better hidden.
- It's much easier to redesign the internals, as they don't need to
affect the externals very much.
We will probably distribute this lisp soon. Your comments and
suggestions are welcome.
Bart Massey
UUCP: ..tektronix!reed!bart
From: David M. Neves
Subject: Re: Importance of REPLACA, REPLACD, and the like?
Date:
Message-ID: <3927@spool.WISC.EDU>
In article <····@reed.UUCP> ····@reed.UUCP (Bart Massey) writes:
>At Reed college we are currently doing almost all of our lisp
>programming in an in-house dialect which supports neither destructive
>list functions nor dotted pairs.
...
>In case anyone is interested, the following major changes in the
>language were also implemented, and have proven useful:
>
>- Elimination of eq: Using a properly written version of equal, eq is
>the first thing to happen anyhow, and we've never encountered a
>situation where knowing that two lists were non-eq is "good enough".
>
I can construct such a situation. Imagine a list of lists. You want
to find out if a list you have a pointer to is contained within that
list (i.e. MEMBER). You want to use EQ as the comparison function for
efficiency -- especially if the first few characters of the non eq
lists are the same as the one you are looking for.
e.g.
look for (a b c) object in
List: ( (a b z) (a b a) (a b c d) (a b q) (a b r) (a b c) )
David Neves, Computer Sciences Department, University of Wisconsin-Madison
Usenet: {allegra,heurikon,ihnp4,seismo}!uwvax!neves
Arpanet: ·····@cs.wisc.c.cN
From: Bart Massey
Subject: Re: EQ and EQUAL (Warning: *TOO LONG* :-) (Re: Importance of REPLACA, REPLACD, and the like?)
Date:
Message-ID: <6638@reed.UUCP>
In article <····@spool.WISC.EDU> ·····@ai.WISC.EDU (David M. Neves) writes:
> In article <····@reed.UUCP> ····@reed.UUCP (Bart Massey, me) writes:
> >At Reed college we are currently doing almost all of our lisp
> >programming in an in-house dialect which supports neither destructive
> >list functions nor dotted pairs.
> ...
> >In case anyone is interested, the following major changes in the
> >language were also implemented, and have proven useful:
> >
> >- Elimination of eq: Using a properly written version of equal, eq is
> >the first thing to happen anyhow, and we've never encountered a
> >situation where knowing that two lists were non-eq is "good enough".
I've gotten several replies already to this statement, so I thought
I'd try to give a little more background and detail about what I meant...
There are three explicit Reed Lisp design goals that are relevant to
this question. These are:
-- Lisp should be easy for non-lisp-programmers, and non-programmers,
to learn and to read.
-- The internal operation of a lisp interpreter/compiler should, as
much as possible, be hidden from the user, for the convenience of the
implementor as well as the user himself.
-- Efficiency is unimportant up to a constant. I'm not sure how to
put this clearly... If the language is designed in such a way as to
force certain algorithms to be higher "order" or to take more than an
"order of magnitude" longer to run, the design should be reconsidered.
If, on the other hand, a language design change would allow algorithms
to run a "small constant" amount faster, it should not be implemented
unless there are other compelling reasons for it. This still isn't
very well said, but I think you can appreciate what I mean...
> I can construct such a situation. Imagine a list of lists. You want
> to find out if a list you have a pointer to is contained within that
> list (i.e. MEMBER). You want to use EQ as the comparison function for
> efficiency -- especially if the first few characters of the non eq
> lists are the same as the one you are looking for.
>
> e.g.
> look for (a b c) object in
> List: ( (a b z) (a b a) (a b c d) (a b q) (a b r) (a b c) )
Yep, this is the classic case. Let's look at a little different one,
just for the sake of clarity:
look for (a b c) in target
( (a b c d) (a b c) (a b c d) (a b c) )
OK, here's what I'm thinking when I see this:
Do I know that both instances of (a b c) in target are the same
pointer? If not, is this a problem? (In other words, do I really want
to look for (a b c) in target, or for a *specific* (a b c)?) There
are two cases:
I) I want *any* (a b c). This is by *far* the most common
case in my (admittedly somewhat limited) experience. In this case, I
can still use eq, but I have several problems:
I must be very careful that I don't insert (a b c)
into target in any way except by inserting the appropriate pointer.
Anyone trying to read or debug my code must also be very
careful that I have done so. This is generally non-trivial.
I must understand the internals of my implementation
*very well* to insure to myself that I am always putting the proper
pointer in. Such details actually vary a great deal from
implementation to implementation, so I must write for a specific
interpreter.
Case II) I am only interested in finding my pointer. I don't
really care that it happens to be pointing to the list (a b c). This
is the case which I have never seen occur in practice, and have a hard
time thinking of an example of. Cases that *look* like this
generally look that way because the programmer has spent time
trying to figure out where his (a b c)s are.
With respect to the three design goals stated above, I suspect it is
now clear why we didn't implement eq. It makes lisp harder to
understand, the code harder to read, is implementation dependent.
Finally, note what kind of efficiency increase you get from its use in
the above example.
In compiled lisp, you get effectively a factor of 5, during this one
line of code, because you are doing 5 comparisons (the list and four
of its elements) in the equal version, to each single test (the list)
in the eq version. But note that these 5 comparisons are
approximately 20 machine instructions (5 compares, 5 cdrs, and a
(machine-level) recursion), versus the single machine instruction of
eq. The overhead of executing compiled lisp code effectively swamps
this gain in all but the largest of cases, and thus you're not likely
to be able to measure the speedup in a piece of real code.
The interpreted case is even worse. Ours is a fast lisp
interpreter -- approximately 2-10 times as fast as Franz. In our
lisp, an equal on even a 1000 element deeply recursive list with all
but the last element succeeding is completely swamped by the overhead
of the eval associated with executing the equal, in spite of the fact
that much of our speed advantage is due to a very fast eval.
I hope this clarifies why we left eq out of our lisp
interpreter. My friends and I are awfully fond of the concept of
"fast enough", and "The Law Of Virtual Efficiency: A "Real Programmer"
will spend a week to save the user 10 seconds over the life of the
program."
But then again, what do we know??? Precious little! Please send
replies to me, I will summarize. BTW, thanks much for all the
flattering and interested responses I've received so far! This was
the first net article I'd posted in a long time that I didn't receive
*a single flame* about!! Some useful criticisms, but no flames! How
very pleasant!...
Bart the Long-Winded :-)
From: Christopher A. Welty
Subject: Re: EQ and EQUAL
Date:
Message-ID: <290@nysernic>
In article <····@reed.UUCP> ····@reed.UUCP (Bart Massey) writes:
> ...
> I) I want *any* (a b c). This is by *far* the most common
>case in my (admittedly somewhat limited) experience. In this case, I
It is true that this is more common.
>
> I must understand the internals of my implementation
>*very well* to insure to myself that I am always putting the proper
>pointer in. Such details actually vary a great deal from
>implementation to implementation, so I must write for a specific
>interpreter.
>
Well, this is not really all true. If you just understand the
way LISP is supoosed to work, and you are using a more standard form
of LISP, there are certain things that are guaranteed to work in a
certain way. Of course you are changing this guarantee. I have
written portable LISP code using complex pointer manipulations.
>
> Case II) I am only interested in finding my pointer. I don't
>really care that it happens to be pointing to the list (a b c). This
>is the case which I have never seen occur in practice, and have a hard
>time thinking of an example of.
There are applications of this in practice. They are not
examples that are easy to think of, nor are they simple enough to
explain briefly, but they come up when doing very large real
applications in LISP. Being able to get to your pointers is very
important. Why do you think C is so popular? Because pointers are
very useful and allow you to do flexible things. Sure, some people
view them as "too low level" for a language that is supposed to
support high level abstractions. And using this apprach can sometimes
make *code* less readable. [Of course, if programmers were taught
earlier on how to correctly DOCUMENT code as they are writing it, this
wouldn't be a problem, and we wouldn't have to worry about making
computer languages that read like english (COBOL was an attempt at
this).] Hardware, however, has not gotten fast enough that
programmers can afford to write LISP code that is not
efficient...
Don't get me wrong this is not a flame. I use LISP quite a
lot, I teach it, I think it's a great language with a lot of great
ideas. I think it will be around for a long time. But there are some
SERIOUS problems with using it for real work, and you have proposed
good ideas for helping it past some of its major problems, this is
good! But don't eliminate important elements of the language because
you can't think of an example of how it could be used. If it's there,
SOMEONE must be using it!
Christopher Welty - Asst. Director, RPI CS Labs
······@cs.rpi.edu ...!seismo!rpics!weltyc
From: Robert Stanley
Subject: Re: EQ and EQUAL
Date:
Message-ID: <1205@cognos.UUCP>
In article <···@nysernic> ······@nic.nyser.net (Christopher A. Welty) writes:
>...Why do you think C is so popular? Because pointers are
>very useful and allow you to do flexible things. Sure, some people
>view them as "too low level" for a language that is supposed to
>support high level abstractions....
Until we get much more powerful computing systems out in the field, remembering
that the lag to plain old boring commercial DP in the field is about 15 years,
all persons writing 'real' applications will at some point be obsessed by
efficiency. Further, human nature tends to leave us doing things the way we've
always done them. How long has it taken for the concept of GOTO-less programs
to reach grunt level? Has it? It will take a long time to wean programmers
from pointers, even if there is an adequate alternative. Adequate of course is
a mutable measurement, depending on local context.
>...But don't eliminate important elements of the language because
>you can't think of an example of how it could be used. If it's there,
>SOMEONE must be using it!
Not so at all. Nearly everything in large-scale software is prey to creeping
featurism, and the 'it seemed like a good idea at the time' syndrome. Tools,
in which I include all programming languages, are no exception to this. I can
name at least one heavy-duty bug that remained undetected for years for each of
several different language implementations. Undetected for years means that
the feature was essentially unused. We are suffering from the legacy of
solutions in search of a problem, and I welcome initiatives that offer a
departure from this sorry state of affairs.
The key issue is not to remove a feature from the language without providing a
way of simulating it. If there are large cries from users that the only way to
do something is too slow/clumsy/impractical/etc. then is the time to take note
and introduce release two.
--
Robert Stanley Compuserve: 76174,3024 Cognos Incorporated
uucp: decvax!utzoo!dciem!nrcaer!cognos!roberts 3755 Riverside Drive
or ...nrcaer!uottawa!robs Ottawa, Ontario
Voice: (613) 738-1440 - Tuesdays only (don't ask) CANADA K1G 3N3
I view two objects that are otherwise EQUAL, but not EQ as having
different "timestamps". The two objects look the same, but they are
different because two different place/time's created them. Hash-tables on
symbols and the like add some texture to this model by allowing two
different creation place/time's to point to the same object (this is the
case for symbols in particular, often subsets of the numbers, etc), which is
useful only if done in a predictable (easy to understand) way.
Conceptually, these pointers often act as keys for various searches (MEMQ,
ASSQ, or homebrew tree searches). Also, since when one is destructively
modifying a tree (copying entire trees to modify one piece can sometimes be
(1) prohibitly time-expensive (2) eats cons cells and causes the garbage
collector to be called more often and (3) isn't necessarily more
understandable, and often requires more code to support) one's invariants
have a lot of EQ's of subtrees in them. Having a close correspondance
between one's invariants and the actual code being written makes life more
pleasant, easier, and the code easier to read and understand.
While appealing intuitively, your concept of efficiency is horrifying.
Roughly, your MEMQ search is order N, while the equivalent MEMBER search
(for the example given) is order N squared (roughly, I said). For the small
N in your examples, N squared minus N isn't very large and IS negligible.
But what about large N? How about N = 1000? 1000000? Just eight times
slower means what could have taken 1 hour now takes 8 hours! Try using a
300 BAUD terminal and a 9600 BAUD terminal to print a long file. What takes
a minute on the 9600 BAUD terminal takes over half an hour on the 300 BAUD
terminal. Even small factors can add up.
What you've done by removing EQ is to remove an opportunity for writing
more efficient programs, WITHOUT REPLACING IT WITH SOMETHING EQUIVALENT OR
BETTER! *THIS* is why people mutter and flame about your LISP being a "toy"
language or "fundamentally brain damaged". You've shut out whole classes of
large programs without providing any alternative.
Now, I don't have an alternative. I think the equivalence classes
introduced by pointers on objects by creation times and hash-tables is an
essential aspect of LISP-like languages. My programming style is such that
correctness is natural, obvious, and automatic once you understand the
paradigm -- I have never had problems with objects not being EQ when they
should or EQ when they shouldn't be (nor have I had to think about it much).
I don't even think I've used EQUAL in a long time. Your challenge is to
change my mind by providing a faster or a equal but more elegant
alternative. You can't change my mind by taking it away, for I simply won't
use your language.
By the way, you're stuck with von Neumann architectures for the next
decade at least. I realize my pointer semantics are ugly and unneccessary
on certain non-standard architectures where efficient alternatives exist.
In the meantime, my pointer semantics are explicit in my programs because I
haven't yet built optimizing compilers that understand it well enough to
allow it to be implicit (and possibly non-existant on appropriate
architectures). I'm trying though.
- - - - - - - - - - - - - - - - - - - - - - - - - -
If you want to bend your mind thinking about other things, consider the
idea of HASH-CONS. HASH-CONS on a particular pair of values always returns
the same cons cell. What does this allow you to do? What problems does it
solve? What problems does it create? Should you be able to RPLACA and
RPLACD a cell cell produced by HASH-CONS?
But thats trivia (and possibly bogus). If you are really concerned about
good language design for LISP, look into SCHEME where you have lexical
scoping for identifiers, first class functions (can be passed as arguments
as well as returned as values), and many other goodies. Other functional
languages (like ML, f'instance) are worth looking into. Here you are
talking major overhaul of the entire language, not nit picking certain
aspects.
Like the man said, its good that you are thinking about these things, but
don't get bogged down.
Your goal as a language designer should be to allow the programmer to do
what he wants, but to give him the best, cleanest, and simplest tools for
doing that. You might change HOW he does what he wants, but never WHAT he
wants. If you start trying to dictate what he wants to do, you've just
murdered your language, because the programmer's just going to get pissed
off, and go to a more pleasant language at his first opportunity.
From: ······@iaoobelix.UUCP
Subject: Re: Importance of REPLACA, REPLACD, and - (nf)
Date:
Message-ID: <6900008@iaoobelix.UUCP>
[ National lineeater week... ]
In some cases, list creation can be optimized not to create a number of single
conses but one large vector which comprises a piece of the entire list (this
technique is usually referred to as CDR-Coding). The Symbolics manuals will
probably give you some hints on that.
An alternative representation of arbitrary n-ary structures (i.e. structures
holding n components) is possible with closures. Closures provide a
well-defined interface to a somehow opaque data structure (see various LISP
introductions or the FranzLISP Manual for an explanation).
Juergen Wagner, (USENET) ...seismo!unido!iaoobel!wagner
("Gandalf") Fraunhofer Institute IAO, Stuttgart
From: James Larus
Subject: Re: Importance of REPLACA, REPLACD, and - (nf)
Date:
Message-ID: <19747@ucbvax.BERKELEY.EDU>
Luddy Harrison (of the Center for Supercomputing Research &
Development at the Univ. of Illinois) has done some very nice work on
using vector-like structures to store lists. The purpose of this work
is to make fast, concurrent reduction operations possible on
multiprocessors. It has other advantages in that certain common
operations, such as APPEND, become very fast and efficient. It's main
disadvantage is that RPLACA and RPLACD are outlawed because they screw
up the structure-sharing. Luddy argues that a lot of cases in which
these operations were previously necessary for efficiency reasons are
not as important, i.e., NCONC is unnecessary when APPEND is almost
constant-time.
There is a paper in the 1986 Parallel Processing Conf. and a couple of
tech. reports on this work.
/Jim
From: Jack Orenstein
Subject: cdr encoding (was Re: Importance of REPLACA, REPLACD)
Date:
Message-ID: <17815@cca.CCA.COM>
In article <·····@ucbvax.BERKELEY.EDU> ·····@paris.Berkeley.EDU(James Larus) writes:
>Luddy Harrison ... has done some very nice work on
>using vector-like structures to store lists. ...
>Certain common operations, such as APPEND, become very fast and efficient.
>It's main disadvantage is that RPLACA and RPLACD are outlawed because they
>screw up the structure-sharing. ...
I can see why RPLACD causes trouble, but why RPLACA? Suppose that P
is a pointer to a "cell" in the middle of some list represented by
a vector. P actually points to the location of the car (i.e. one
of the vector components). (RPLACD P ...) won't work because the
cdr field is at the next location in physical memory. (RPLACA P ...)
just updates the contents of the vector component.
If C is an ordinary cell, then I don't see why (RPLACA C P) or
(RPLACD C P) would cause any trouble.
Am I missing something?
Jack Orenstein
From: James Larus
Subject: Re: cdr encoding (was Re: Importance of REPLACA, REPLACD)
Date:
Message-ID: <19760@ucbvax.BERKELEY.EDU>
In article <·····@cca.CCA.COM> ····@CCA.CCA.COM.UUCP (Jack Orenstein) writes:
>In article <·····@ucbvax.BERKELEY.EDU> ·····@paris.Berkeley.EDU(James Larus) writes:
>>Luddy Harrison ... has done some very nice work on
>>using vector-like structures to store lists. ...
>>Certain common operations, such as APPEND, become very fast and efficient.
>>It's main disadvantage is that RPLACA and RPLACD are outlawed because they
>>screw up the structure-sharing. ...
>
>I can see why RPLACD causes trouble, but why RPLACA? Suppose that P
>is a pointer to a "cell" in the middle of some list represented by
>a vector. P actually points to the location of the car (i.e. one
>of the vector components). (RPLACD P ...) won't work because the
>cdr field is at the next location in physical memory. (RPLACA P ...)
>just updates the contents of the vector component.
>
>If C is an ordinary cell, then I don't see why (RPLACA C P) or
>(RPLACD C P) would cause any trouble.
>
>Am I missing something?
Yes, but it is not your fault. I didn't explain Luddy's idea fully
enough to do it justice. His scheme stores the number of elements in
a list along with a pointer to the list (the number is important for
scheduling multiprocessors tasks). Suppose I have two lists:
(setq A (list 1 2 3))
(setq B (list 4 5 6))
The are roughly represented:
A: list, 3 --> |1|2|3|
B: list, 3 --> |4|5|6|
Now, suppose I do (setq C (append A B)), I end up with the following 2
(not 3!) structures:
A: list, 3 --|
|--> |1|2|3|--|
C: list, 6 --| |
|
|
B: list, 3 ---------------|--> |4|5|6|
I can't really do it just without better drawings. Needless to say,
you can see that because of the large amount of sharing that results,
any RPLACA or RPLACD can affect other, unrelated lists. The sharing
has many advantages for the intended uses of these structures and
side-effect-producing operations like RPLACA just produce headaches on
multiprocessors, so the best course is to outlaw them.
/Jim
From: Joe Weening
Subject: Re: cdr encoding (was Re: Importance of REPLACA, REPLACD)
Date:
Message-ID: <8052@labrea.STANFORD.EDU>
Actually, in [1, p. 38] Harrison says
"While the operation RPLACA is no different to perform using our
representation than when using a conventional one, the increased
level of sublist sharing causes a concomitant increase in the
likelihood of RPLACAing a shared cell, and makes it practically
impossible to give a precise semantic definition of the construct.
... Nevertheless, because it is so straightforward to perform the
operation itself using our representation, further investigation
is needed to decide if RPLACA can be incorporated in an orderly
way."
I tend to disagree with the first part of this, at least in the case
of a single-process program (or a list structure known to be accessed
by only a single process). In this case, I think techniques such as
developed in [2] can be used to adequately define the semantics, and
there may be cases where RPLACA is of some use.
Of course, if you want RPLACA to have the exact same semantics as with a
conventional pointer-based list representation, there will be problems.
But I suspect that this is rarely needed.
RPLACD is another story. Here again I think it could be implemented with
a well-defined semantics, but the resulting operation would be much less
useful than the conventional RPLACD, as Harrison points out, and to do the
standard RPLACD is quite difficult with this representation.
Since this representation was designed for a parallel Lisp, and the parallel
semantics of RPLACA and RPLACD will make them much less useful than the
serial forms, I can see why he chose to remove them from the language.
Joe Weening
[1] W. L. Harrison, "Compiling Lisp for Evaluation of a Tightly Coupled
Multiprocessor", Center for Supercomputing Research and Development Report
No. 565, Urbana, Ill., March 1986.
[2] I. A. Mason, "The Semantics of Destructive Lisp", Center for the Study
of Language and Information Lecture Notes No. 5, Stanford, Ca., 1986.
From: Alex Colvin
Subject: Re: cdr encoding (was Re: Importance of REPLACA, REPLACD)
Date:
Message-ID: <1792@uvacs.CS.VIRGINIA.EDU>
There are uses for infinite (cyclic) list structures. Many of these
can be constructed by something like a set of simultaneous recursive
equations (see [1,2]), in much the same way that LABELS defines a set
of mutually recursive functions.
For example, an infinite list of 'T is
(LABELS ( (lotsa-t (cons T lotsa-t))
)
...don't try to print it
)
+------+
lotsa-t --+->| T | ----+
| +------+ |
+------------+
a somewhat more tangled version
(LABELS ( (a (list b c))
(b (list c a))
(c (list a b))
)
...
)
+------------------+
| |
| +---+ +---+ |
a --+->|+|+---->|+|/| |
+|--+ +|--+ |
| | |
+---|--------+ |
| v |
| +---+ +---+ |
b +-|->|+|+---->|+|/| |
| | +|--+ +|--+ |
+-|---|----+ +-----+
| | | |
| v +---+ |
| +---+ +|--+ |
c --+->|+|+---->|+|/| |
+|--+ +---+ |
| |
+--------------+
You get the idea that these definitions are easier to follow than any
chain of RPLACs.
In particular, what you expect of (labels ((c (list a b)) remains true.
[1]
P. J. Landin.
"A Correspondence between ALGOL 60 and Church's Lambda-Notation: Part I"
Comm. ACM 8(2), February 1965.
Defines LET REC as a mutually recursive LET.
[2]
Morris & Schwarz. "Computing Cyclic List Structures". Proc. 1980 LISP
Conference.
Shows how to apply this to mutually recursive lists.
What's nice is that the same implementation will work for both data and
function recursion.
From: Alex Colvin
Subject: Re: cdr encoding (was Re: Importance of REPLACA, REPLACD)
Date:
Message-ID: <1793@uvacs.CS.VIRGINIA.EDU>
Someone once (1980 LISP conference) used the term "Heraclitean"
constructor for CONS. Heraclitus, you recall, was the pre-Socratic who
"you can't step in the same * twice!" Two CONS calls with EQ
arguments, are not EQ. I suppose the other (mathematically functional)
version would be a Platonic constructor.
>/* Written 4:13 pm Jul 18, 1987 by ·······@Gang-of-Four.Stanford.EDU in uicsrd:comp.lang.lisp */
>
>I tend to disagree with the first part of this, at least in the case
>of a single-process program (or a list structure known to be accessed
>by only a single process). In this case, I think techniques such as
>developed in [2] can be used to adequately define the semantics, and
>there may be cases where RPLACA is of some use.
>
>Of course, if you want RPLACA to have the exact same semantics as with a
>conventional pointer-based list representation, there will be problems.
>But I suspect that this is rarely needed.
>
> Joe Weening
It feels odd to argue *against* possible uses for this representation;
nevertheless, here is a pathological use of RPLACA, to illustrate the
problem:
...
(SET! X '(A B C D E))
(IF CONDITION1 (SET! S (APPEND X R))
(SET! Y (APPEND X X))
(RPLACA X 'OOPS)
...
If CONDITION1 is true (and R non-null), then after this sequence,
Y = (A B C D E OOPS B C D E); else, Y = (OOPS B C D E OOPS B C D E).
(Y will consist of 5 cells, and will have a length of 10.)
In short, in the presence of RPLACA and RPLACD, APPEND appears to have
side-effects, and RPLACA appears to affect two elements of a
non-circular list. Note also that the garbage collector affects sharing:
after S and Y are reclaimed, APPENDing to X may again result in sharing with X.
Probably one could make a rule such as "(RPLACA X Y) is undefined
if the cell X has ever been involved in an APPEND operation;" this may
be the sort of alteration to the semantics that Joe has in mind.
As was mentioned before, omitting the RPLAC operations is, for us, part of
a strategy of parallelization and compilation.
-Luddy Harrison
Jim has hit the nail on the head. The storage scheme does not
make RPLACA difficult to perform, but the increase in sublist sharing makes
it difficult to give it a precise meaning. Whereas with conventional list
representations, the sharing that results from an APPEND operation is
apparent, using the representation I've proposed the sharing that results
is in part a function of previous APPEND operations. For instance,
in the code fragment
...
(IF CONDITION1 (SET! A (APPEND B C)))
(IF CONDITION2 (SET! D (APPEND B E)))
...
D and B may wind up sharing all of the cells in B's top level, if
CONDITION1 is false; that is, if (APPEND B C) does not occur. If
(APPEND B C) occurs, then A and B will wind up sharing all of the cells
in B's top level. It seemed unreasonable to expect a user to be able
to sort out who was sharing what with whom, and so we ended by declaring the
representation unfit for use with RPLACA as well as RPLACD.
Another way of looking at it, as Jim pointed out, is that if RPLACA and RPLACD
are making the life of the parallelizer (human or automatic) miserable, then
why not lop them off, and take full advantage of the immutability of cons cells
by increasing storage efficiency, providing for fast (parallel) access to top
level cells, allowing recurrences over lists to be solved in parallel,
etc? (In the lisp system we're currently developing, there are lots of
other mutable objects: structures, variables, hashtables, etc., so the loss
of expressive power is relatively minor.)
--
Luddy Harrison, Center for Supercomputing R&D, U of IL at Champaign-Urbana
UUCP: {ihnp4,seismo,pur-ee,convex}!uiucdcs!uicsrd!harrison
ARPANET: ···············@a.cs.uiuc.edu
CSNET: ···············@uiuc.csnet
BITNET: ········@uicsrd.csrd.uiuc.edu or ········@uicsrd
From: Timothy L. Davis
Subject: Re: Importance of REPLACA, REPLACD, and - (nf)
Date:
Message-ID: <1162@bloom-beacon.MIT.EDU>
{}
I think the style & "readability" wins of "writing out the parse tree", which
is really what lisp syntax is all about, could be combined with less esoteric
data structures, a la C's malloc() and free(), to produce VERY optimized
code. There should be no need for run-time garbage collection.
Does anyone know if it is possible to write a lisp (or SCHEME)
pre-processor which will eliminate the need for garbage collection by
inserting (free ..) in the approprate places? A starting point would be
lexically-scoped Scheme, no side-effects, and no global or fluid bindings.
If that is too hard (or proven impossible), how about a pre-processor to add
>most< of the needed (free ...) statements, so that the garbage collector need
not hardly ever be called? The compiler could even flag unfreeable variables
and let the programmer specify their disposal explicitly.
I know many of the lisp hackers out there may think I don't understand the lisp
philosophy; I do, but let's leave garbage collection to rapid prototyping,
and develop good compilers to automatically transform those prototypes into
the products (software, parallel-ware, VLSI, etc.) of the future.
Tim Davis ······@athena.mit.edu
60 Wadsworth #19A ...mit-eddie!mit-athena!tdavis
Cambridge, MA 02142