Samir Barjoud <·····@mindspring.com> writes:
> Why do (CAR NIL) and (CDR NIL) return NIL? Is this behavior purely
> historical, or is it by design?
i would say historical design. why do you ask? what would you like
for them to do? in many respects NIL represents `nothing'. so, if a
list has no CAR, then it would be appropriate for the `nothing' answer
to be given.
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
Don't Fear the Penguin!
Johan Kullstam <········@ne.mediaone.net> writes:
> Samir Barjoud <·····@mindspring.com> writes:
>
> > Why do (CAR NIL) and (CDR NIL) return NIL? Is this behavior purely
> > historical, or is it by design?
>
> i would say historical design. why do you ask? what would you like
> for them to do? in many respects NIL represents `nothing'. so, if a
> list has no CAR, then it would be appropriate for the `nothing' answer
> to be given.
If it were up to me, CAR and CDR would only accept conses as
arguments.
Consider the following code:
(LET ((E (CAR X)))
... ;; body: Do something with E and X
(SETF (CAR X) 'NEW-CAR))
If X is NIL on entry to the code, the body runs fine, but the SETF
will result in an error. However, the error is signaled at the
_wrong_ time. It should occur when the CAR of X is taken.
The code has an implicit assertion, that X is not NIL upon entry. It
could have been stated explicitly via (ASSERT X), but that is verbose
and unnecessary. I think an important part of LISP are the implicit
assertions you get everywhere you use primitives in your code. When
an invalid argument is passed to an outer function, the error will
always be caught by a _primitive_ (assuming an ASSERT is not present
"upstream"). The primitives _are_ the assertions.
A cons can be seen as a structure. If a function expects to receive a
valid instance of a structure, and is instead passed NIL (as a result
of some unexpected upstream behavior), an error will be signaled
whenever a slot of the instance is accessed. There is no need to
write code to check for the invalid situation, it is implied by the
slot accessor. Replace 'structure' with 'cons' and 'slot' with 'car'
in the preceding two sentences and they will be in error.
Whenever a function looses information, it should be viewed with
suspicion. (SETF I (TRUNCATE 5 2)) looses information, but it isn't a
function and it probably doesn't matter. CAR however, is a function,
and it is _functional_ (side-effect free). Moreover, CARs output
depends solely on its input. Thus, (CAR NIL) => NIL, and (CAR (CONS
NIL NIL)) => NIL does, in a sense, exhibit a questionable loss of
information.
The issue of CAR handling NIL can be generalized to one of "error
silencing". Functions that are designed to be responsible for
handling invalid inputs _silently_ are useful. It is a common naming
convention to suffix functions that are silent about error conditions
with "-SAFE". Functions such as CAR-SAFE and CADR-SAFE (which are
safe when passed any type of argument) are useful in that they
eliminate logic that would have been otherwise duplicated throughout a
program. But they are only useful when wrapped around lower-level
functions that signal errors. Otherwise, when other error handling
strategy is needed in the future, the function will have to be picked
apart.
I am curious about how often and in what types of situations the CAR
or CDR of NIL is taken. My guess is that it is not frequent. But all
in all it doesn't really matter, since NIL's true value is (nil . nil)
in probably every implementation that worries about performance. I
looked at the EMACS C code for CAR, and it specifically checks for
NIL, so I'm not sure anymore.
(concat
(mapcar #'1-
"J!lopx!uibu!FNBDT!jto(u!b!tqffe!efnpo-!cvu!J!dbo(u!cbe.npvui!tpnfuijoh!J!vtf!TPPP!nvdi!;*"))
You're reading this with EMACS, so `eval-last-sexp' the above.
--
Samir Barjoud
·····@mindspring.com
Samir Barjoud wrote:
> If it were up to me, CAR and CDR would only accept conses as
> arguments.
Then, you should use good names for that (eg: HEAD and TAIL).
CAR and CDR are historical, so is their semantics. I happen to like it,
but I'd also want other two functions working only on pairs.
Definitely, hijacking these two names for `clean' semantics is not appropriate.
Fernando Mato Mira wrote:
> Samir Barjoud wrote:
>
> > If it were up to me, CAR and CDR would only accept conses as
> > arguments.
>
> Then, you should use good names for that (eg: HEAD and TAIL).
> CAR and CDR are historical, so is their semantics. I happen to like it,
> but I'd also want other two functions working only on pairs.
> Definitely, hijacking these two names for `clean' semantics is not appropriate.
I might be wrong about this, but I believe that McCarthy originally defined
CAR and CDR only on pairs (aka conses in Common Lisp) [1]. I know for sure
that Section 1.2 of the Lisp 1.5 Programmer's Manual (August 1962) says that
the "CAR of an atomic symbol is undefined", and that "CDR is also undefined
if its argument is atomic" [2]. This tradition was preserved in MACC Lisp
for the Univac 1100 [3], Standard Lisp [4] and its derivatives, and remains
to this day in Scheme [5].
On the other hand, Appendix A of that very same Lisp 1.5 manual says that,
in the actual implementation as of August 1962,
The elementary functions CAR and CDR always have some sort of value
rather than giving an error diagnostic. A chain of CDRs applied to
an atomic symbol will allow one to search its property list.
Indiscriminate use of these functions past the atomic level will
result in non-list structure and may appear as lengthy or even
infinite garbage expressions if printed.
The Lisp 1.6 Reference Manual [6] says that
The CAR of a non-atomic S-expression is the first element of that
dotted pair. CAR of an atom is undefined and will usually cause
an illegal memory reference.
The CDR of a non-atomic S-expression is the second (and last) element
of that dotted pair. The CDR of an identifier is its property list....
So the Lisp 1.5 and 1.6 manuals alone describe three distinct semantics for
CAR and CDR, all of them incompatible with the semantics of today's Common
Lisp. The Lisp 1.6 semantics was preserved in CMU TOPS Lisp [7], but does
not seem to be popular today.
According to Guy Steele and Richard Gabriel [8], "MacLisp adopted from
Interlisp the convention that (CAR NIL) = (CAR NIL) = NIL". This tradition
was preserved in Lisp Machine Lisp, and remains to this day in Common Lisp.
From this history I suppose you could argue that Interlisp [9] was the system
that "hijacked" the names CAR and CDR. I don't think it is appropriate to
use a perjorative term like "hijack", however, because the behavior of CAR
and CDR on non-pairs has always varied between dialects of Lisp. So Common
Lisp's semantics for CAR and CDR would seem to have as much historical support
as Scheme's "cleaner" semantics.
[1] John McCarthy. Recursive functions of symbolic expressions. CACM 3(4),
April 1960, pages 184-195.
[2] John McCarthy, Paul W Abrahams, Daniel J Edwards, Timothy P Hart, and
Michael I Levin. LISP 1.5 Programmer's Manual, Second Edition. MIT
Press. The preface is dated August 17, 1962.
[3] MACC LISP Reference Manual for Univac 1100 Series Computers. Academic
Computing Center, University of Wisconsin - Madison, May 1975.
[4] J B Marti, A C Hearn, M L Griss, C Griss. Standard Lisp Report, First
Revision. University of Utah, UUCS-78-101, August 1978.
[5] Richard Kelsey, William Clinger, and Jonathan Rees [editors]. Revised^5
report on the algorithmic language Scheme. Journal of Higher Order and
Symbolic Computation, 11(1), 1998, pages 7-105. Also appears in ACM
SIGPLAN Notices 33(9), September 1998.
[6] Lisp 1.6 Reference Manual Number 90708 (incorporating SAILONS 28.2 and
41). Applied Logic Corporation, Princeton, New Jersey, 1969.
[7] Crispin S Perdue. TOPS LISP. CMU Department of Computer Science,
16 November 1978.
[8] Guy L Steele Jr and Richard P Gabriel. The evolution of Lisp. Preprints
of the Second ACM SIGPLAN History of Programming Languages Conference
(HOPL-II). ACM SIGPLAN Notices 28(3), March 1993, pages 231-270. [A
revised version of this paper was printed in the book version of the
conference proceedings, published by ACM.]
[9] Warren Teitelman. INTERLISP Reference Manual. BBN and Xerox, 1974.
Will
William D Clinger <····@ccs.neu.edu> writes:
> Fernando Mato Mira wrote:
> > [schemer-directed flame-bait]
> [thorough destruction of Mira's claim, including a bibliography]
Wow! I pity the fool who picks a fight with a language lawyer of your
caliber.
If I'm ever tried for the double-cdr of my ex-wife and her companion,
I want you on my dream team!
-al
Al Jay Petrofsky wrote:
> William D Clinger <····@ccs.neu.edu> writes:
> > Fernando Mato Mira wrote:
> > > [schemer-directed flame-bait]
> > [thorough destruction of Mira's claim, including a bibliography]
Gee. I flamed myself..
Anyway, here's the response I sent him yesterday. Maybe someone has
actually
used one of those things:
------------------------------------------------------------------------------------
>I might be wrong about this, but I believe that McCarthy originally
defined
>CAR and CDR only on pairs (aka conses in Common Lisp) [1]. I know for
sure
>that Section 1.2 of the Lisp 1.5 Programmer's Manual (August 1962) says
that
>the "CAR of an atomic symbol is undefined", and that "CDR is also
undefined
>if its argument is atomic" [2]. This tradition was preserved in MACC
Lisp
>for the Univac 1100 [3], Standard Lisp [4] and its derivatives, and
remains
>to this day in Scheme [5].
>
>On the other hand, Appendix A of that very same Lisp 1.5 manual says
that,
>in the actual implementation as of August 1962,
>
> The elementary functions CAR and CDR always have some sort of value
> rather than giving an error diagnostic. A chain of CDRs applied to
> an atomic symbol will allow one to search its property list.
> Indiscriminate use of these functions past the atomic level will
> result in non-list structure and may appear as lengthy or even
> infinite garbage expressions if printed.
>
>The Lisp 1.6 Reference Manual [6] says that
>
> The CAR of a non-atomic S-expression is the first element of that
> dotted pair. CAR of an atom is undefined and will usually cause
> an illegal memory reference.
But "undefined" means an implementation is free to do whatever it wants.
What was the actual value of (CAR NIL) and (CDR NIL) ?
From the above, it seems that 1.5 (and probably 1.6) would return
NIL for (CDR NIL). Maybe it was not enforced that you could not
add properties on NIL, but some convention emerged: "you are not supposed
to do so"?
-----------------------------------------------------------------------------------------
Also note that `extending' does not `hijack' (correct programs continue to
work).
`Restricting' does.
I don't think I destroyed the idea that (CAR NIL) = (CDR NIL) = NIL
has a long history. It's just that I suspected the answer was more
complicated, and I happened to have a few of the relevant references
sitting on my bookshelf, and I was curious about it myself.
Will
I think having a single generic null value for all classes isn't a bad idea.
Something along the lines of the null class being derived by every class, and
having a single instance whose fields it is illegal to access. In this
scenario, allowing access to any of the null instance's fields is a sure road
to ambiguity. Of course, sometimes it's appropriate to declare that the null
class is not derived from a particular class. This usually applies to classes
whose instances are indistinct (see "Equal Rights" by Baker), like numbers,
characters, booleans, etc.. Note that this does preclude having valid empty
values for a particular class, such as a string whose length is zero. Empty
values might often be identified with the null value.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
Andy Gaynor wrote:
> I think having a single generic null value for all classes isn't a bad idea.
> Something along the lines of the null class being derived by every class, and
> having a single instance whose fields it is illegal to access. In this
> scenario, allowing access to any of the null instance's fields is a sure road
> to ambiguity. Of course, sometimes it's appropriate to declare that the null
What fields?
/ null if x = null
|
CAR(x) / x[0] if x is a pair
\
| undefined otherwise
\
/ null if x = null
|
CDR(x) / x[1] if x is a pair
\
| undefined otherwise
\
[nobody prevents you to implement null as distiguished pair, of course]
Fairly insignificant typo fix. Updated below:
> Note that this doesn't preclude having valid empty values for a particular
^^^ insertion
> class, such as a string whose length is zero.
Fernando Mato Mira, ········@iname.com, wrote:
> What fields?
All the myriad fields from the classes from which the null class is derived, as
per the definition I gave, "the null class being derived by every class". Car,
cdr, length, the 917th character in a string, name, left-subtree, etc.
> / null if x = null
> |
> CAR(x) / x[0] if x is a pair
> \
> | undefined otherwise
> \
>
> [CDR similarly defined]
Would you make a special case of accessors for the otherwise non-special pair
class, or, more uniformly, would you define all accessors likewise? Suppose
vector-length or string-ref were defined similarly. The types of these fields
happen to be indistinct (in the sense that you can't distinguish one 69 from
another 69); having null pop up when one of these is required is anomalous.
When x's type is unknown, the possibility of these accessors returning null
would almost certainly inhibit optimization.
> nobody prevents you to implement null as distiguished pair, of course
Just to attempt to optimize car/cdr of null returning null? Depending on the
definition of the rest of the language and the implementation scheme, I can
easily envision this impairing class resolution, method dispatch, field access,
or other fundamental things.
Even outside of my contrived scenario and handwaving, it seems like a lot of
effort, with potential for performance degradation and definition anomalies,
just to accommodate something as trivial and questionable as defining that
accessors return null when called on null, or just those of the otherwise
non-special pair class.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
[ replying to comp.lang.lisp only
http://world.std.com/~pitman/pfaq/cross-posting.html ]
Andy Gaynor <······@mail.webspan.net> writes:
> > nobody prevents you to implement null as distiguished pair, of course
>
> Just to attempt to optimize car/cdr of null returning null?
Sure, why not? You can question why it's there but surely it's important
to make efficient given that it's there and it gets used. Indeed, if it
was there and NOT used, it's still important to make efficient because
CAR/CDR have to accomodate the possibility that it will get used whether
or not it actually is. Better not to make an extra test every time one
of these operators is called.
As to whether the definition should be changed, the issue is simple:
it's got a long tradition, it's used a lot, and it would be very expensive
to change. That pretty much ends it because the cost of coping is
well-understood and modest, whereas the cost of change is surely huge.
By contrast, I wouldn't advocate adding the capability to other datatyypes
and operators because there's no demonstrated need, because the cost of
maintaining the status quo is low, and changing things would introduce a
possibly severe implementation hurdle where none presently exists.
For more info on (X3)J13's charter, which specifically observes that cost
to the community is a more relevant consideration than aesthetics, you can
check out my unofficial online version of the charter at
http://world.std.com/~pitman/CL/x3j13-86-020.html
Kent M Pitman wrote:
> For more info on (X3)J13's charter, which specifically observes that cost
> to the community is a more relevant consideration than aesthetics, you can
> check out my unofficial online version of the charter at
> http://world.std.com/~pitman/CL/x3j13-86-020.html
I particularly like (j)
>:-I
Andy Gaynor wrote:
> Just to attempt to optimize car/cdr of null returning null? Depending on the
> definition of the rest of the language and the implementation scheme, I can
> easily envision this impairing class resolution, method dispatch, field access,
> or other fundamental things.
I see no problem. It's done all the time. Could you please be more specific? BTW,
it's not a lot of effort,
it's trivial.
One thing you can't do if you want this optimization is represent null as machine
zero. Comparison speed
difference can be considered negligible, although I guess it effectively reduces
your register set by one.
One could say the same about cache blocks and page pool, if there were no other
structures (in cons space, in the worst case) that are used over and over again,
otherwise 2[3,4] words for each. If you use zero for #f or 0, and another constant
for null, you `lose a register' anyway.
> Even outside of my contrived scenario and handwaving, it seems like a lot of
> effort, with potential for performance degradation and definition anomalies,
> just to accommodate something as trivial and questionable as defining that
> accessors return null when called on null, or just those of the otherwise
> non-special pair class.
It seems that the style I adopted was not sufficiently clear. The point is, you
should not think as CAR and CDR as accessors, but just as 2 funny functions, in the
same style as Ackerman's or whatever. They don't even need to be primitives. CL is
missing the pair accessors. Scheme got their name wrong.
> Could you please be more specific?
Here's a straightforward example which doesn't rely on the scenario presented.
In the most typical implementation style, resolving the class of an unknown
object requires less resources when it is an instance of a direct class at the
topmost level in the tag hierarchy than when it is an instance of an indirect
class. The reference might miss the cache. Although usually unlikely, it
might even cause a page fault. A point in favor of representing null directly.
Now that I think about it, this could pop up during garbage collection, a very
memory-intensive task.
> The point is, you should not think as CAR and CDR as accessors, but just as 2
> funny functions, in the same style as Ackerman's or whatever. They don't
> even need to be primitives. CL is missing the pair accessors. Scheme got
> their name wrong.
The history of their names suggests that they are accessors. Taking this at
face value, though, in the presence of accessors, I don't see the use of 'em
and the discussion is moot.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
Andy Gaynor wrote:
> > Could you please be more specific?
>
> Here's a straightforward example which doesn't rely on the scenario presented.
> In the most typical implementation style, resolving the class of an unknown
> object requires less resources when it is an instance of a direct class at the
> topmost level in the tag hierarchy than when it is an instance of an indirect
> class. The reference might miss the cache. Although usually unlikely, it
> might even cause a page fault. A point in favor of representing null directly.
> Now that I think about it, this could pop up during garbage collection, a very
> memory-intensive task.
And where's the problem? null is just an (address) constant. It _is_ represented
directly.
More importantly:
---------
heap
|
v
---------
free
--------- null
cons
|
v
--------
free
----------
^
|
stack
----------
if Null is the address of null (start of cons space):
(null? x) ----> (x == Null)
(pair? x) ----> (x < Null)
so for CAR and CDR:
if (x > Null)
error
else
return x[0]; // or 1. Map CAR and CDR to 0 and 1 in whatever order is best.
>
> > The point is, you should not think as CAR and CDR as accessors, but just as 2
> > funny functions, in the same style as Ackerman's or whatever. They don't
> > even need to be primitives. CL is missing the pair accessors. Scheme got
> > their name wrong.
>
> The history of their names suggests that they are accessors. Taking this at
> face value, though, in the presence of accessors, I don't see the use of 'em
> and the discussion is moot.
Well, obviously they are effectively readers on CL, given that nothing more
primitive exists (yet).
But if you think previous Lisps were confused, there're more friendly ways of going
about it, especially when the names are not
FIRST, PAIR-FIRST, HEAD, etc.
CAR and CDR are the implementation of an important lisp programming pattern:
(if (null? x)
null
(pair-first x))
(if (null? x)
null
(pair-second x))
The discussion is not moot. Why would I care otherwise? You should really take a
tour around the CMU repository sources to see
for yourself what a mess this creates. You could automatically replace all CARs and
CDRs for CL:CAR and CL:CDR, but the
efficiency issue does not go (I wouldn't be surprised to see at least a 10% hit in
performance just because of this). Not all the time you can go hacking the Scheme
implementation you use. And if you want to create a CL-friendly one, anything other
than
`CAR and CDR of null are undefined' in the RxRS is a bummer.
Just to clarify, you perspective seems to be oriented more towards a static
type system, idiosynchatically optimized, as opposed to a much more general
class system. We're working with a set of base assumptions that are similar
but not identical.
Fernando Mato Mira, ········@iname.com, wrote:
> [Null] _is_ represented directly.
As are all objects in a word-based object representation. Some directly
represent addresses of their values, referring to them indirectly. Just
setting tone.
> And where's the problem? null is just an (address) constant.
In this case, null is subject to the the baggage that comes with indirection.
Class resolution, garbage collection, swizzling, etc. Let's consider class
resolution. For speed and simplicity, let's assume a simple fixed tag tree,
free tag bits used for primary tag, say 2 bits. One of the primary tags has
reasonably small secondary tag, say 4 bits. For resolution speed, let's
consider x's entire tag at once. For code density, let's consult an explicit
tag/class mapping, an array, rather than encoding the mapping. We could check
to see if x is a reference before consulting the table, favoring indirect
objects over direct, or we could check the resulting value and take the
appropriate action, favoring direct objects over indirect. The latter is
logically better, relying on the table to direct the choice. Direct objects
can be resolved without the risk of a page fault. In fact, the likelihood of a
cache hit is probably higher. There are usually more bindings to and fields
containing direct objects than indirect, which is a coarsely favors the latter.
Empirical analysis is really required. Regardless, the average performance of
both approaches is very close, probably differing only in a cycle or two, but
it adds up. Let's consider garbage collection. During traversal, the tags of
everything encountered will be examined. Direct-tagged objects need be
considered no further. Indirect objects require further type-specific
processing. It's reasonable to assert that things as critical as an indirect
null value, the tag table, etc. are allocated in a stationary fashion, and so
their data will never be relocated, and so all the bindings to these values
will never need updating. However, we'll still have to determine how to handle
these unknown indirect objects when encountered. Enough. Some (but not all)
of this can be alleviated by playing tag games with the null and pair classes.
This is a Pandora's box, even with a static type system.
FM> The point is, you should not think as CAR and CDR as accessors, but just as 2
FM> funny functions, in the same style as Ackerman's or whatever. They don't
FM> even need to be primitives. CL is missing the pair accessors. Scheme got
FM> their name wrong.
Ag> The history of their names suggests that they are accessors. Taking this at
Ag> face value, though, in the presence of accessors, I don't see the use of 'em
Ag> and the discussion is moot.
FM> The discussion is not moot.
I meant moot in the sense that if they aren't defined to be raw accessors, it
doesn't really matter if they don't work as fast as raw accessors.
> You should really take a tour around the CMU repository sources to see for
> yourself what a mess this creates. You could automatically replace all CARs
> and CDRs for CL:CAR and CL:CDR, but the efficiency issue does not go (I
> wouldn't be surprised to see at least a 10% hit in performance just because
> of this).
In theory, the performance should be no worse. Something's up here, probably
implementation- or program-specific, perhaps assuming that ...
> CAR and CDR are the implementation of an important lisp programming pattern:
I think you're talking about the ability to use null implicitly as an
omnipresent end-of-proper-list sentinel. Well, folks get along just and very
nicely without it. In fact, it makes me uncomfortable to rely upon such a
disputed facet. As an alternative, explicit sentinels can certainly be used.
This is more consistent since accessors to non-pair linked structures won't
have the disputed behavior. It's also more general, since the null-sentinel
trick is unusable when null happens to be a valid value in the problem domain,
you know what I mean. Another good alternative is to use exception handlers.
So far, this hasn't been a Lisp pissing contest, which is grand. Lisp is like
pizza and sex: even when its bad, it's pretty damned good. But while I enjoy
debating the merits of various facets, such as the behavior of car and cdr
regarding null, I'm kind of deep in the weeds, gotta split.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
Andy Gaynor wrote:
[long tagging discussion elided]
Sorry, but I find that text very difficult to follow.
Can we start from the obvious assumption, that is, that you don't need to follow a
pointer to find out it's the null object, and see where do we lose?
[If you're putting headers on conses (yuck!), you certainly can use the one on null,
too, if that makes something better].
One little note regarding my previous diagram:
if you want to allocate objects in the stack, you obviously have to reverse the order
of `heap' and cons space, as well as reversing the orientation of cons space.
Fernando Mato Mira, ········@iname.com, wrote:
> Can we start from the obvious assumption, that is, that you don't need to
> follow a pointer to find out it's the null object, and see where do we lose?
Depending on the tagging hierarchy and the implementation of the tree, this
impairs resolution speed. The following code is reasonable enough (the "latter
approach" of my previous message):
inline object instance_class(object x)
{object entry = tag_map[x & 0x3f];
if (entry >= indirect_offset_limit)
then return(entry);
else return(*(x - indirect_offset_limit));}
Incidentally, this accomodates more than one indirect class. This may well be
free (do most stock processors have a load-with-register-offset instruction?
addressing mode?).
If null has special consideration in the tag hierarchy, nothing further need be
done -- it will enjoy a tag map hit. This is a tough call, but let's assume
that null is not treated specially. An explicit null test could be done first,
slowing down resolution for all unknown objects.
inline object instance_class(object x)
{if (x == the_null_value)
then {return(the_null_class);}
else {object entry = tag_map[x & 0x3f];
if (entry >= indirect_offset_limit)
then return(entry);
else return(*(x - indirect_offset_limit));}}
The test is better done in the consequent, slowing down resolution only for
indirect objects.
inline object instance_class(object x)
{object entry = tag_map[x & 0x3f];
if (entry >= indirect_offset_limit)
then return(entry);
then if (x == the_null_value)
then return(the_null_class);
else return(*(x - indirect_offset_limit));}
> If you're putting headers on conses (yuck!), you certainly can use the one
> on null, too, if that makes something better.
Whatever's cheapest. There are a *lot* of significant metrics and factors to
consider beyond raw cell count. Garbage collection (is a header justified
anyway?), the amount of live data (might a header-requiring non-copying
reclamation scheme be warranted, at least for older generations?), referential
locality (will the locality of reference lost by segregation adversely affect
performance?), class proliferation (are other explicitly-linked data types
cutting into pair/cons/whatever's action enough to diminish the expected return
of segregating pairs?), implementation simplicity (is it worth the trouble to
open "Pandora's box"?), escaping data (data might escape to the outside word;
will a more complex format be undesirable?), global attributes (for things like
ownership, protection, etc., is a header required anyway?), and more. Given my
biases (which include a large data model with sophisticated reclamation and a
high degree of type specialization), the arguments favoring the uniform
treatment of reference objects seem more compelling.
I don't mean to be rude by not commenting on the specific memory organization
you presented. Memory organization is influenced by so many factors that it's
hard to discuss in a relative vacuum.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
Andy Gaynor wrote:
[wasting a tag problem]
[adding one test problem]
Yes. I am aware of that. How do you tag null and pairs?
[BTW. Remember that you can have it any way you want if you:
1. Find two good names for PAIR-FIRST and PAIR-SECOND (with nice derivations into
the equivalents of CADAR, etc.)
2. Deprecate the use of C(A|D)+R.
Just to point out that the discussion is interesting, but it has really nothing to
do with whether
(CAR NIL) = (CDR NIL) = NIL
]
One thing that does seem to show is that #f != NIL is more evil than I thought,
implementation-wise
(register pressure might be dismissed, but tag space erosion on 32-bit
architectures..)
From: Fernando Mato Mira
Subject: The Usual Suspects (was: (CAR NIL))
Date:
Message-ID: <379C679F.D9BD5C07@iname.com>
Fernando Mato Mira wrote:
> Just to point out that the discussion is interesting, but it has really nothing to
> do with whether
> (CAR NIL) = (CDR NIL) = NIL
Note that fortunately, R5RS says "it is an error", not "an error is signalled".
Unfortunately, 1.3.2 - Error situations and unspecified behavior also says
"If such wording does not appear in the discussion of an error, them implementations
are not required to detect or report the error, though they are encouraged do to so"
So `unspecified' would still be a better choice.
> One thing that does seem to show is that #f != NIL is more evil than I thought,
> implementation-wise
Not that it really matters that much. What's really evil is not leaving the
equivalence of #f and null
unspecified.
Why did R5RS mess with this? IEEE compliance? (who really cares about _IEEE_ Scheme
anyway?)
Does not knowing prevent you from writing correct Scheme programs?
Fernando Mato Mira, ········@iname.com, wrote:
> [wasting a tag problem]
>
> Yes. I am aware of that. How do you tag null and pairs?
Momentarily aside, let's clarify "free tag bits". Usually, some bits are
insignificant when considering an address of a native word because the smallest
addressable entity is typically smaller than a native word. Specifically, the
number of free tag bits is the log_2 of the number of addressable entities per
word. Let's use these bits for tagging. Not only are they insignificant with
regard to the address, they can usually be stripped for "free" in addressing.
When accessing a known field of an object with an known tag, if tags are
stripped with an additive operation, ie, subtraction, the known tag subtraction
and the known constant addition fold together into one operation. Let's assume
that log(32/8)=2 is the case.
The competition around the highest levels of the tag hierarchy is pretty hot.
Integers should remain right up there on slot 00 so that pointer arithmetic
works smoothly, and because some stock architectures (SPARC? any others?) can
do 00-tagged integer arithmetic. However, we can push references down by one
bit, creating another slot of similar precision, and paying for that slot with
two-word alignment for both. This might waste perhaps 5%-15% of memory, but
the amount depends on lots of factors. (Can anyone comment on this for Common
Lisp/Scheme vs more type-prolific environments?) Anyway, all this blabbering
is just to demonstrate that, even at the highest levels in the tag tree, we can
often produce a tag slot if necessary. Spend it wisely.
In a class-prolific environment, I would represent null directly and wouldn't
distinguish pairs, perhaps something like
00 integer
01 whatever, perhaps misaligned-reference
10 reference
00011 null
00111 undefined
01011 end-of-stream
01111 boolean (false carries value 0, true carries ~0, all other bits set)
10011 latin-1 (8-bit character)
10111 unicode-1 (16-bit character)
11011 whatever
11111 whatever
Blowing an alignment bit for a couple high-level whatevers...
00 integer
001 whatever, perhaps misaligned-reference
101 whatever
010 reference
110 whatever
...
Completely aside, that misaligned-reference thing is something that just
occurred to me. For memory management, it would be nice to have a fixed limit
on object sizes. Here's one example: consider "Pointer Swizzling at Page Fault
Time", by Wilson and Kakkad, which boils down to virtual memory maintaining an
access barrier of protected, reserved-but-as-yet-unread pages. When an attempt
is made to access an object in the barrier, the page containing the object is
loaded and swizzled, and the barrier is pushed back by reserving pages to every
reference not already resident or in the barrier. Suppose an object has a
large "fan-out", that it is big and refers to things all over the place (a hash
table is a good example). This may push the barrier back a lot, soaking up
virtual address space, which must be reclaimed when exhausted. This pagewise
virtual memory reclamation is an expensive proposition. It would be nice to
defer it as long as possible. (Yet another demonstration of the value of
referential locality, upon which this swizzling scheme relies.)
Given a request to allocate a large object, suppose the allocator silently
broke it up and returned some indexing object, perhaps a btrees, perhaps with a
cache, and that this special object was tagged as a misaligned reference
instead of as a (normal) reference. Note that the difference between the tags
is one, that the misaligned reference tag is odd. Attempts to perform word
accesses through misaligned references will raise a misaligned access
exception/bus error/whatever. Only accesses to the smallest addressable units
known not to trap when so aligned must be disallowed when an object's model is
unknown, since they will silently produce erroneous results. The handler for
misaligned accesses is in cahoots with the allocator and completes requested
large object accesses. For base efficiency, but not actually necessary, the
class resolver should also not be impaired by trapping. Coincidentally, the
resolver posted in my last message would suffice as-is. Although not
necessary, the compiler should be made aware of the large object model. By
default, code is generated assuming the small object model. It will always
work, although exceptions will slow it down for large objects. Methods for
classes of objects known to be large can be written assuming the large model,
and methods for classes likely to have large instances could have a method
written for each model, chosen at run-time. Naw, I don't like the idea of an
explicit run-time check. Perhaps arrange to have an access occur right at the
start of the method's execution. If it traps, the handler checks to see if
there is a large object version of the code, designed by the compiler to repair
the state and continue. If no such method exists, the handler could simply
perform the access. It might even be brave enough to ask the compiler to
generate the required method. Just a thought. This whole approach is
type-orthogonal, has no run-time cost when objects are small, the run-time cost
can be mitigated by the compiler, and it doesn't rely upon consulting auxiliary
state (like tables). I'm going to leave off here. This is just too obvious.
Anybody have references?
> [adding one test problem]
That test, though, that's a problem. A small problem, but a problem.
> Just to point out that the discussion is interesting, but it has really
> nothing to do with whether
> (CAR NIL) = (CDR NIL) = NIL
Not so! The car/cdr/nil issue happens to be so fundamental that it bears on
many other fundamental issues.
> One thing that does seem to show is that #f != NIL is more evil than I
> thought, implementation-wise
> register pressure might be dismissed
I just won a bet, I *knew* false/null would come up! Personally, I think that
the concepts of nullness and falseness should be distinguished, but I certainly
acknowledge that arguments in favor of unifying null and false are very strong.
In any case, this is a separate issue and nowhere near as significant (with
respect to definition and implementation overhead) as car/cdr/nil. To the best
of my knowledge, the only real issue is the cost of comparison. Now, when the
a value's representation doesn't require many significant bits, it can be
represented as an immediate constant in comparison instructions. That's why I
discussed the values carried by false and true as I did, so that the very next
bit distinguishes them. (Without getting into a lot of unrelated details, I
might even be tempted to give false and true their own direct classes (and
tags) and derive them both from a boolean class.) When an object is a
reference to real data, it cannot be an immediate constant unless the address
is constant (fair enough, considering the critical values in question) and
refers to very very low memory. This may be difficult or impossible, depending
on the operating system (is this right?). Suppose the maximum immediate
comparison constant is 16 bits. We'd have to stash the object's data under the
2^16=64k mark for it to be embedded it in comparisons. Otherwise, we're stuck
with the unpalatable option of blowing a register for it. Appel's Green Book
shows that the expected return of increasing the number of general registers
for argument passing diminishes only at about 14 registers. Weigh this against
the amount of register-starved hardware out there. Another point in favor of
representing null and false (when distinct from null) directly.
> but tag space erosion on 32-bit architectures..)
This isn't usually a problem except at the very top of the tag hierarchy, at
the free tag bit levels. Modest secondary tags can be supported without
slowing things down. Can anyone supply a reasonable empirically-determined
cut-off? I'd guess that 6 bits is reasonable, maybe as high as 8.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net
From: Fernando Mato Mira
Subject: Re: (CAR NIL) [and a scheme for breaking up large objects]
Date:
Message-ID: <37A30E75.89875530@iname.com>
Just to point out I have to finish some things so I'm saving a detailed analysis of
this for the plane.
(I have to confront some `have it all' `idea' with this.)
Fernando Mato Mira wrote:
> One could say the same about cache blocks and page pool, if there were no other
> structures (in cons space, in the worst case) that are used over and over again,
> otherwise 2 overhead words for each.
But if you never do (car null) and (cdr null), you'll never have to access those words
(if you must in order to look at a type tag, that's your problem).
In article <·················@ccs.neu.edu>,
William D Clinger <····@ccs.neu.edu> wrote:
>According to Guy Steele and Richard Gabriel [8], "MacLisp adopted from
>Interlisp the convention that (CAR NIL) = (CAR NIL) = NIL". This tradition
>was preserved in Lisp Machine Lisp, and remains to this day in Common Lisp.
Maclisp and Lisp Machine Lisp also adopted Lisp 1.6's (CDR <symbol>)
returning the property list. This allowed "disembodied property lists" to
be used interchangeably with symbols; a disembodied plist is a cons whose
cdr contains the actual plist -- this initial cons is just a placeholder
that can be modified.
Common Lisp added GETF, which provided a way to use disembodied property
lists without wasting the extra cons, although they're no longer
first-class objects that can be passed around.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <·····················@burlma1-snr2>, Barry Margolin
<······@bbnplanet.com> wrote:
>Maclisp and Lisp Machine Lisp also adopted Lisp 1.6's (CDR <symbol>)
>returning the property list.
In UCI Lisp on the PDP10, symbols were just lists beginning with a special
flag, namely an address with all bits on. Therefore, not only could you
(CAR <symbol>)
to get this address, you could
(RPLACA <symbol> value) !!!
This was in the days of FEXPR's, i.e., user-defined functions that took
any number of unevaluated arguments, e.g.,
> (DF FOO (L) (PRINC "Hi!") (TERPRI) L)
FOO
> (FOO A B C)
Hi!
(A B C)
Put these together and you could do this:
> (RPLACA 'A 'FOO)
...
> A
Hi!
<property list of A>
The Lisp reader would read the atom A and find the interned symbol, but
when the result was passed to EVAL, it would see a list of the form (FOO
...) and call FOO. So typing an atom would execute code.
Kids these days have no idea what real Lisp programming means...
>Common Lisp added GETF, which provided a way to use disembodied property
>lists without wasting the extra cons, although they're no longer
>first-class objects that can be passed around.
I didn't understand this comment. I thought plists were just (indicator
val indicator val ...) lists that
(GETF plist indicator)
would retrieve from and
(SETF (GETF plist indicator) val)
would store to, destructively. Plist's can be passed around, can't they?
What makes them not first-class?
In article <·························@riesbeck.ils.nwu.edu>,
Chris Riesbeck <········@ils.nwu.edu> wrote:
>I didn't understand this comment. I thought plists were just (indicator
>val indicator val ...) lists that
>
> (GETF plist indicator)
>
>would retrieve from and
>
> (SETF (GETF plist indicator) val)
>
>would store to, destructively. Plist's can be passed around, can't they?
>What makes them not first-class?
What if the plist is empty? What do you pass around?
SETF of GETF isn't required to be destructive, so multiple pointers to the
same plist might not all be updated. Consider:
(setq plist1 (list 'key1 'val1 'key2 'val2))
(setq plist2 plist1)
(setf (getf plist1 'key3) 'val3)
plist1 => (key3 val3 key1 val1 key2 val2)
plist2 => (key1 val1 key2 val2)
Perhaps "first-class" was the wrong term. The point was that disembodied
property lists were used in a way that you could pass around a single
object that represented the list in such a way that you could have many
references to it and they would all see the update. When you get rid of
that level of indirection through a proxy, you lose that ability.
Similar things happen with association lists, but they tended not to be
used in the same way, because disembodied plists derived their usage
patterns from symbol plists. In the latter case the symbol acted as the
proxy.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Hi, can anyone teach me how to implement the following procedures in Schme?
1. Union of lists:
union returns the combination of 2 list with duplicates removed.
Example:
(union '(1 2 3 4) '(5 6 7 8))
=> (4 3 2 1 5 6 7 8)
(union '(1 2 2 1) '(3 4 1 8))
=> (2 3 4 1 8)
2. Structeq? :
this function will test the structural equality of two given lists. Two lists
are structurallly equal if they have the same list structure, although their atoms
may be different.
Example:
(structeq? '(a (b c ) (e f) ) '(t (g e) (s t)) ) => #t
(structeq? '(a b c) '(a (b c))) => #f
3. removeall:
This function will take two parameters, an atom and a list, that returns the
list with all occurrences, no matter how deep , of the given atom deleted. The
returned list cannot contain anything in place of the deleted atoms.
Example:
(removeall 'a '(a (c d ( a t))) ) => (c d t)
(removeall 't '(a (t d (a t))))) => (a (d a))
I will appreciated anyone's help on this functions. Thank you.
Sam Xie
On Sun, 01 Aug 1999 22:34:42 -0400, seamux <······@mediaone.net>
wrote:
>Hi, can anyone teach me how to implement the following procedures in Schme?
All of the problems you mentioned look like homework problems. All
could be made more general. With the possible exception of union,
none appear to have practical utility. I (and others here no doubt)
don't mind helping someone learn, but won't do someone else's
homework.
With that in mind, I offer the following helpful advice.
>1. Union of lists:
> union returns the combination of 2 list with duplicates removed.
Think clearly. Use recursion. (Hint: you don't need for-each.)
Look at scheme's built-in functions for list membership.
>2. Structeq? :
> this function will test the structural equality of two given lists. Two lists
>are structurallly equal if they have the same list structure, although their atoms
>may be different.
Look at the possible base cases for recursion:
* two pairs
* two non-pairs
* a pair and a non-pair
In what cases are each structurally equal?
>3. removeall:
> This function will take two parameters, an atom and a list, that returns the
>list with all occurrences, no matter how deep , of the given atom deleted. The
>returned list cannot contain anything in place of the deleted atoms.
This is still using recursion. You might try writing a function that
works on a flat list, then generalizing it to work on arbitrary pair
structures.
From: ······@andru.sonoma.edu
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <m2aesa19sr.fsf@andru.sonoma.edu>
I suggest reading the code for a normal delete function and a normal
append function. then read it again. once you really understand a
straight delete and append, you will be able to do these problems.
here are two sample implementations:
(define (delete elem list)
(if (null? list)
'()
(if (equal? elem (car list))
(delete elem (cdr list))
(cons (car list) (delete elem (cdr list)))
)
)
)
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))
)
)
best of luck,
andru
--
--------------------------------------------------------------------------
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| ······@andru.sonoma.edu | Textile imports from Provence, France |
--------------------------------------------------------------------------
From: Didier Vidal
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A5C4C7.898EF4E4@cybercable.fr>
seamux wrote:
> Hi, can anyone teach me how to implement the following procedures in Schme?
>
> 1. Union of lists:
> union returns the combination of 2 list with duplicates removed.
>
> Example:
>
> (union '(1 2 3 4) '(5 6 7 8))
> => (4 3 2 1 5 6 7 8)
> (union '(1 2 2 1) '(3 4 1 8))
> => (2 3 4 1 8)
>
> 2. Structeq? :
> this function will test the structural equality of two given lists. Two lists
> are structurallly equal if they have the same list structure, although their atoms
> may be different.
> Example:
> (structeq? '(a (b c ) (e f) ) '(t (g e) (s t)) ) => #t
> (structeq? '(a b c) '(a (b c))) => #f
>
> 3. removeall:
> This function will take two parameters, an atom and a list, that returns the
> list with all occurrences, no matter how deep , of the given atom deleted. The
> returned list cannot contain anything in place of the deleted atoms.
>
> Example:
>
> (removeall 'a '(a (c d ( a t))) ) => (c d t)
> (removeall 't '(a (t d (a t))))) => (a (d a))
>
> I will appreciated anyone's help on this functions. Thank you.
>
> Sam Xie
Here are some possible answers :
;;; union
;;; First : union is an operation on sets and sets can be represented
;;; by lists with no duplicates
;;; Ordered lists => complexity O(n)
;;; parameters : two ordered lists
;;; result : an ordered list
(define (union lst1 lst2)
(cond
((null? lst1) lst2)
((null? lst2) lst1)
((< (car lst1) (car lst2))
(cons (car lst1)
(union (cdr lst1) lst2)))
((= (car lst1) (car lst2))
(cons (car lst1)
(union (cdr lst1) (cdr lst2))))
(else
(cons (car lst2)
(union lst1 (cdr lst2))))))
;;; If the lists are not ordered : complexity in O(n^2)
(define (union lst1 lst2)
(cond
((null? lst1) lst2)
((null? lst2) lst1)
((member (car lst1) lst2)
(union (cdr lst1) lst2))
(else
(cons (car lst1)
(union (cdr lst1) lst2)))))
;;; structeq?
(define (structeq? lst1 lst2)
(if (pair? lst1)
(and (pair? lst2)
(structeq? (car lst1) (car lst2))
(structeq? (cdr lst1) (cdr lst2)))
(eq? lst1 lst2)))
;;; remove-all
(define (deep-remq x lst)
(cond
((null? lst) '())
((eq? x (car lst)) ; or another equality predicate
(deep-remq x (cdr lst)))
((pair? (car lst))
(cons (deep-remq x (car lst))
(deep-remq x (cdr lst))))
(else
(cons (car lst) (deep-remq x (cdr lst))))))
Didier Vidal
From: Didier Vidal
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A5E469.BFCE3784@cybercable.fr>
Didier Vidal wrote:
> seamux wrote:
>
> > Hi, can anyone teach me how to implement the following procedures in Schme?
> >
> > 1. Union of lists:
> > union returns the combination of 2 list with duplicates removed.
> >
> > Example:
> >
> > (union '(1 2 3 4) '(5 6 7 8))
> > => (4 3 2 1 5 6 7 8)
> > (union '(1 2 2 1) '(3 4 1 8))
> > => (2 3 4 1 8)
> >
> > 2. Structeq? :
> > this function will test the structural equality of two given lists. Two lists
> > are structurallly equal if they have the same list structure, although their atoms
> > may be different.
> > Example:
> > (structeq? '(a (b c ) (e f) ) '(t (g e) (s t)) ) => #t
> > (structeq? '(a b c) '(a (b c))) => #f
> >
> > 3. removeall:
> > This function will take two parameters, an atom and a list, that returns the
> > list with all occurrences, no matter how deep , of the given atom deleted. The
> > returned list cannot contain anything in place of the deleted atoms.
> >
> > Example:
> >
> > (removeall 'a '(a (c d ( a t))) ) => (c d t)
> > (removeall 't '(a (t d (a t))))) => (a (d a))
> >
> > I will appreciated anyone's help on this functions. Thank you.
> >
> > Sam Xie
>
> Here are some possible answers :
> ;;; union
>
> ;;; First : union is an operation on sets and sets can be represented
> ;;; by lists with no duplicates
>
> ;;; Ordered lists => complexity O(n)
> ;;; parameters : two ordered lists
> ;;; result : an ordered list
> (define (union lst1 lst2)
> (cond
> ((null? lst1) lst2)
> ((null? lst2) lst1)
> ((< (car lst1) (car lst2))
> (cons (car lst1)
> (union (cdr lst1) lst2)))
> ((= (car lst1) (car lst2))
> (cons (car lst1)
> (union (cdr lst1) (cdr lst2))))
> (else
> (cons (car lst2)
> (union lst1 (cdr lst2))))))
>
> ;;; If the lists are not ordered : complexity in O(n^2)
> (define (union lst1 lst2)
> (cond
> ((null? lst1) lst2)
> ((null? lst2) lst1)
> ((member (car lst1) lst2)
> (union (cdr lst1) lst2))
> (else
> (cons (car lst1)
> (union (cdr lst1) lst2)))))
>
> ;;; structeq?
> (define (structeq? lst1 lst2)
> (if (pair? lst1)
> (and (pair? lst2)
> (structeq? (car lst1) (car lst2))
> (structeq? (cdr lst1) (cdr lst2)))
> (eq? lst1 lst2)))
>
> ;;; remove-all
> (define (deep-remq x lst)
> (cond
> ((null? lst) '())
> ((eq? x (car lst)) ; or another equality predicate
> (deep-remq x (cdr lst)))
> ((pair? (car lst))
> (cons (deep-remq x (car lst))
> (deep-remq x (cdr lst))))
> (else
> (cons (car lst) (deep-remq x (cdr lst))))))
>
> Didier Vidal
I made a mistake in structeq? :
(define (structeq? lst1 lst2)
(if (pair? lst1)
(and (pair? lst2)
(structeq? (car lst1) (car lst2))
(structeq? (cdr lst1) (cdr lst2)))
(not (pair? lst2))))
sorry
From: Friedrich Dominicus
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A68570.95B4BE9@inka.de>
> >
> > ;;; First : union is an operation on sets and sets can be represented
> > ;;; by lists with no duplicates
> >
> > ;;; Ordered lists => complexity O(n)
> > ;;; parameters : two ordered lists
> > ;;; result : an ordered list
> > (define (union lst1 lst2)
> > (cond
> > ((null? lst1) lst2)
> > ((null? lst2) lst1)
> > ((< (car lst1) (car lst2))
> > (cons (car lst1)
> > (union (cdr lst1) lst2)))
> > ((= (car lst1) (car lst2))
> > (cons (car lst1)
are you sure this is correct? If I would have
'(1 1 2) and '(1 1 4)
woudn't the result be '( 1 1 2 4)
so one would be doubled
Regards
Friedrich
From: Didier Vidal
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A69E8C.319FB55E@cybercable.fr>
Friedrich Dominicus wrote:
> > >
> > > ;;; First : union is an operation on sets and sets can be represented
> > > ;;; by lists with no duplicates
> > >
> > > ;;; Ordered lists => complexity O(n)
> > > ;;; parameters : two ordered lists
> > > ;;; result : an ordered list
> > > (define (union lst1 lst2)
> > > (cond
> > > ((null? lst1) lst2)
> > > ((null? lst2) lst1)
> > > ((< (car lst1) (car lst2))
> > > (cons (car lst1)
> > > (union (cdr lst1) lst2)))
> > > ((= (car lst1) (car lst2))
> > > (cons (car lst1)
>
> are you sure this is correct? If I would have
> '(1 1 2) and '(1 1 4)
>
> woudn't the result be '( 1 1 2 4)
>
> so one would be doubled
>
> Regards
> Friedrich
I mentionned that sets should be represented as lists without duplicates.
In your exemple, you are not taking the union of to sets. You should first
specify what kind of objects you want to process with "union".
If they are sets (in the mathematical sense) the above program is correct,
[btw, you can remove duplicates with the following function :
(define (remove-duplicates lst)
(if (null? lst)
'()
(if (member (car lst) (cdr lst))
(remove-duplicates (cdr lst))
(cons (car lst) (remove-duplicates (cdr lst))))))
]
I suppose you meant to take the union on so-called "multisets" but (again)
how do you define it ?
Regards
Didier
From: Friedrich Dominicus
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A6DBAA.EEDB6C26@inka.de>
Didier Vidal wrote:
>
> I mentionned that sets should be represented as lists without duplicates.
> In your exemple, you are not taking the union of to sets. You should first
> specify what kind of objects you want to process with "union".
> If they are sets (in the mathematical sense) the above program is correct,
> [btw, you can remove duplicates with the following function :
Havn't you said somthing about sorted lists? But I may have overread
some pieces. And I was thinking of the original question no word about
sets there just lists so in this case I guess it won't work?
Regards
Friedrich
From: Didier Vidal
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A6E079.4FFD0BC8@cybercable.fr>
Friedrich Dominicus wrote:
> Didier Vidal wrote:
>
> >
> > I mentionned that sets should be represented as lists without duplicates.
> > In your exemple, you are not taking the union of to sets. You should first
> > specify what kind of objects you want to process with "union".
> > If they are sets (in the mathematical sense) the above program is correct,
> > [btw, you can remove duplicates with the following function :
>
> Havn't you said somthing about sorted lists? But I may have overread
> some pieces.
Yes, i have (just before first definition of union)
> And I was thinking of the original question no word about
> sets there just lists so in this case I guess it won't work?
It does not make sense to take the union of two lists.
Regards
Didier
From: Friedrich Dominicus
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A70F9F.4FCDD128@inka.de>
> It does not make sense to take the union of two lists.
You're right
Regards
Friedrich
seamux wrote...
>Hi, can anyone teach me how to implement
>the following procedures in Scheme?
someone could certainly implement them
for you
>1. Union of lists:
> union returns the combination of 2 lists
> with duplicates removed.
>Example:
>(union '(1 2 3 4) '(5 6 7 8))
> => (4 3 2 1 5 6 7 8)
why not (1 2 3 4 5 6 7 8)?
>(union '(1 2 2 1) '(3 4 1 8))
> => (2 3 4 1 8)
why not (1 2 3 4 8)?
[8<]
>3. removeall:
> This function will take two parameters, an
> atom and a list, and returns the list with all
> occurrences, no matter how deep, of the given
> atom deleted. The returned list cannot contain
> anything in place of the deleted atoms.
>Example:
>(removeall 'a '(a (c d (a t)))) => (c d t)
why not ((c d (t)))?
>(removeall 't '(a (t d (a t)))) => (a (d a))
why not (a (d (a)))?
>I will appreciated anyone's help on these functions.
>Thank you.
no problem
On Mon, 2 Aug 1999 04:37:36 +0100, CsO <···@mindless.com> posted:
>seamux wrote...
>>Hi, can anyone teach me how to implement
>>the following procedures in Scheme?
>
>someone could certainly implement them
>for you
>
>>1. Union of lists:
>> union returns the combination of 2 lists
>> with duplicates removed.
>>Example:
>>(union '(1 2 3 4) '(5 6 7 8))
>> => (4 3 2 1 5 6 7 8)
>
>why not (1 2 3 4 5 6 7 8)?
The choices of orderings are interesting; it would almost appear that
they assume a particular implementation that unravels the first from
the end.
>>(union '(1 2 2 1) '(3 4 1 8))
>> => (2 3 4 1 8)
>
>why not (1 2 3 4 8)?
>[8<]
Arguably, this, as well as the other union, represent unordered lists,
so that the result (1 2 3 4 8) is equivalent to (2 3 4 1 8).
Ordering is obviously just a sort away...
>>3. removeall:
>> This function will take two parameters, an
>> atom and a list, and returns the list with all
>> occurrences, no matter how deep, of the given
>> atom deleted. The returned list cannot contain
>> anything in place of the deleted atoms.
>>Example:
>>(removeall 'a '(a (c d (a t)))) => (c d t)
>
>why not ((c d (t)))?
That has the feeling of being a more correct answer.
Sticking in a call to a (flatten) function along the way would provide
the published results; it seems odd for (removeall) to do an implicit
flattening of the arguments when, in the (union) examples, there was
not the analagous situation of sorting the results.
>>(removeall 't '(a (t d (a t)))) => (a (d a))
>
>why not (a (d (a)))?
Indeed.
>>I will appreciated anyone's help on these functions.
I expect that the functions expected to be used to implement these
requirements very likely involve recursion in some way.
Hope that helps...
--
Rules of the Evil Overlord #58. "I will make sure I have a clear
understanding of who is responsible for what in my organization. For
example, if my general screws up I will not draw my weapon, point it
at him, say "And here is the price for failure," then suddenly turn
and kill some random underling."
········@hex.net- <http://www.ntlug.org/~cbbrowne/lsf.html>
I believe the order is not a issue, which means either (4 3 2 1 5 6 7 8)
or (1 2 3 4 5 6 7 8) will be Ok.
Here is my idea on how to implement this function, but I have problem to
implement in code, please help me out:
for example: lis1 is '(a b c) , lis2 is '(a b c d e), then their union
should be '( a b c d e)
Because (delete 'a '(a b c d e))=> (b c d e)
then (delete 'b '(b c d e)) => (c d e)
then (delete 'c '(c d e)) => (d e)
then (append '(a b c) '(d e) ) => (a b c d e) ; which is what we
want.
Can anyone implement this alorithem for me?
Christopher B. Browne wrote:
> On Mon, 2 Aug 1999 04:37:36 +0100, CsO <···@mindless.com> posted:
> >seamux wrote...
> >>Hi, can anyone teach me how to implement
> >>the following procedures in Scheme?
> >
> >someone could certainly implement them
> >for you
> >
> >>1. Union of lists:
> >> union returns the combination of 2 lists
> >> with duplicates removed.
> >>Example:
> >>(union '(1 2 3 4) '(5 6 7 8))
> >> => (4 3 2 1 5 6 7 8)
> >
> >why not (1 2 3 4 5 6 7 8)?
>
> The choices of orderings are interesting; it would almost appear that
> they assume a particular implementation that unravels the first from
> the end.
>
> >>(union '(1 2 2 1) '(3 4 1 8))
> >> => (2 3 4 1 8)
> >
> >why not (1 2 3 4 8)?
> >[8<]
>
> Arguably, this, as well as the other union, represent unordered lists,
> so that the result (1 2 3 4 8) is equivalent to (2 3 4 1 8).
>
> Ordering is obviously just a sort away...
>
> >>3. removeall:
> >> This function will take two parameters, an
> >> atom and a list, and returns the list with all
> >> occurrences, no matter how deep, of the given
> >> atom deleted. The returned list cannot contain
> >> anything in place of the deleted atoms.
> >>Example:
> >>(removeall 'a '(a (c d (a t)))) => (c d t)
> >
> >why not ((c d (t)))?
>
> That has the feeling of being a more correct answer.
>
> Sticking in a call to a (flatten) function along the way would provide
> the published results; it seems odd for (removeall) to do an implicit
> flattening of the arguments when, in the (union) examples, there was
> not the analagous situation of sorting the results.
>
> >>(removeall 't '(a (t d (a t)))) => (a (d a))
> >
> >why not (a (d (a)))?
>
> Indeed.
>
> >>I will appreciated anyone's help on these functions.
>
> I expect that the functions expected to be used to implement these
> requirements very likely involve recursion in some way.
>
> Hope that helps...
> --
> Rules of the Evil Overlord #58. "I will make sure I have a clear
> understanding of who is responsible for what in my organization. For
> example, if my general screws up I will not draw my weapon, point it
> at him, say "And here is the price for failure," then suddenly turn
> and kill some random underling."
> ········@hex.net- <http://www.ntlug.org/~cbbrowne/lsf.html>
On Mon, 02 Aug 1999 00:32:13 -0400, seamux <······@mediaone.net> posted:
>I believe the order is not a issue, which means either (4 3 2 1 5 6 7 8)
>or (1 2 3 4 5 6 7 8) will be Ok.
>Here is my idea on how to implement this function, but I have problem to
>implement in code, please help me out:
>for example: lis1 is '(a b c) , lis2 is '(a b c d e), then their union
>should be '( a b c d e)
>Because (delete 'a '(a b c d e))=> (b c d e)
> then (delete 'b '(b c d e)) => (c d e)
> then (delete 'c '(c d e)) => (d e)
> then (append '(a b c) '(d e) ) => (a b c d e) ; which is what we
>want.
>
>Can anyone implement this alorithem for me?
I think you've described it; you take the second list, make a copy,
and then loop through the elements of the first list, removing them
from the second list.
Then append the lists. A Wise Idea would be to repeat the process,
looping through List #2, removing its elements from a copy of list #1.
An alternative approach would be to append the lists together, sort,
then run through a filter function so as to remove extra instances of
any given element.
I believe that (mapcar function list1 list2) is likely to be the
function that you'll want to use to loop through the lists...
--
State opinions in the syntax of fact: "...as well as the bug in LMFS
where you have to expunge directories to get rid of files....."
-- from the Symbolics Guidelines for Sending Mail
········@ntlug.org- <http://www.ntlug.org/~cbbrowne/lsf.html>
Thank you for your help. I don't know how to use "mapcar" function, but I try
to code this using "for-each" function, but there is some logical error in my
code, because (delete x lis2) will not change lis2, for example,
(define x '(a b c))
(delete 'a x)=> (b c) ;
x=> (a b c) ; x did not change a bit
;;;;;;;;;;;;;; Here is my code;;;;;;;;;;;;;;;;;;;;;;;
(define (union lis1 lis2)
(for-each (lambda (x) (delete x lis2)) lis1)
(append lis1 lis2))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Your idea of append two list first, then loop through a filter function, is
very good. But I don't think we need to sort it. Because order does not
matter.
Which filter function do you think I should use, and how to loop though the
list?
Sam Xie
Christopher B. Browne wrote:
> On Mon, 02 Aug 1999 00:32:13 -0400, seamux <······@mediaone.net> posted:
> >I believe the order is not a issue, which means either (4 3 2 1 5 6 7 8)
> >or (1 2 3 4 5 6 7 8) will be Ok.
> >Here is my idea on how to implement this function, but I have problem to
> >implement in code, please help me out:
> >for example: lis1 is '(a b c) , lis2 is '(a b c d e), then their union
> >should be '( a b c d e)
> >Because (delete 'a '(a b c d e))=> (b c d e)
> > then (delete 'b '(b c d e)) => (c d e)
> > then (delete 'c '(c d e)) => (d e)
> > then (append '(a b c) '(d e) ) => (a b c d e) ; which is what we
> >want.
> >
> >Can anyone implement this alorithem for me?
>
> I think you've described it; you take the second list, make a copy,
> and then loop through the elements of the first list, removing them
> from the second list.
>
> Then append the lists. A Wise Idea would be to repeat the process,
> looping through List #2, removing its elements from a copy of list #1.
>
> An alternative approach would be to append the lists together, sort,
> then run through a filter function so as to remove extra instances of
> any given element.
>
> I believe that (mapcar function list1 list2) is likely to be the
> function that you'll want to use to loop through the lists...
>
> --
> State opinions in the syntax of fact: "...as well as the bug in LMFS
> where you have to expunge directories to get rid of files....."
> -- from the Symbolics Guidelines for Sending Mail
> ········@ntlug.org- <http://www.ntlug.org/~cbbrowne/lsf.html>
From: Lars Marius Garshol
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <wkemhm7m0m.fsf@ifi.uio.no>
* ······@mediaone.net
|
| for example: lis1 is '(a b c) , lis2 is '(a b c d e), then their
| union should be '( a b c d e)
|
| Because (delete 'a '(a b c d e))=> (b c d e)
This looks like a pretty awkward way to go, since it's not clear what
to delete from which list at any given point. Why not try to build a
new list that contains the elments that appear in both lists? This
sentence should be pretty easy to turn into an algorithm, no?
--Lars M.
* seamux wrote:
> 1. Union of lists:
> union returns the combination of 2 list with duplicates removed.
> Example:
> (union '(1 2 3 4) '(5 6 7 8))
> => (4 3 2 1 5 6 7 8)
> (union '(1 2 2 1) '(3 4 1 8))
> => (2 3 4 1 8)
Since you asked in comp.lang.lisp (to which I've restricted my reply),
here's an implementation of union in Common Lisp, which has quite good
performance for large sets, in particular it should be nearly linear
in the total number of elements. It does allocate a fair amount of
memory to do this.
For CMUCL with lists of integers in ascending order, the built-in
UNION is fairly obviously quadratic with length, but conses nothing it
needn't, while mine is basically linear, but conses a whole lot. This
is a reasonably good example of the kind of tradeoff you get between
naive implementations of sets-as-lists and more sophisticated ones
using hashtables.
(defun my-union (&rest sets)
(let ((tab (make-hash-table)))
(dolist (s sets (let ((union '()))
(maphash #'(lambda (k v)
(declare (ignore v))
(push k union))
tab)
union))
(dolist (e s)
(setf (gethash e tab) t)))))
--tim
From: Friedrich Dominicus
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37A56367.63B04012@inka.de>
seamux wrote:
This looks very much like homework for me. So I guess the idea is to do
that on you own. If you need some help with implementation, post some
code surely you will get some answers.
For now take a look at eg Structure and Interpretation of Computer
Programs or any other book about Scheme, you'll find some infos.
>
> Hi, can anyone teach me how to implement the following procedures in Schme?
>
> 1. Union of lists:
> union returns the combination of 2 list with duplicates removed.
>
> Example:
>
> (union '(1 2 3 4) '(5 6 7 8))
> => (4 3 2 1 5 6 7 8)
> (union '(1 2 2 1) '(3 4 1 8))
> => (2 3 4 1 8)
might look like
(define (add-element element-to-add a-list)
(if (not (memq element-to-add a-list))
(cons element-to-add a-list)
a-list))
(define (union l1 l2)
(let ((int-l1 l1))
(letrec
((internal-union
(lambda (l2)
(if (null? l2)
int-l1
(begin
(set! int-l1 (add-element (car l2) int-l1))
(internal-union (cdr l2)))))))
(internal-union l2))))
others or you surly found better solutions
Regards
Friedrich
Kent M Pitman wrote: [1999-08-03 04:01 +0000]
> Friedrich Dominicus <···················@inka.de> writes:
>
> > (define (add-element element-to-add a-list)
> > (if (not (memq element-to-add a-list))
> > (cons element-to-add a-list)
> > a-list))
>
> You'd almost think a function like this ought to have a name and
> be part of the standard language... It might be really handy in
> defining PUSHNEW, if your standard language had that, of course.
This (standard) function in Common Lisp has :TEST and :KEY arguments.
What would Scheme's way be of providing such capabilities?
Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
Abaci lignei --- programmatici ferrei.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Vassil Nikolov <········@poboxes.com> writes:
> Kent M Pitman wrote: [1999-08-03 04:01 +0000]
>
> > Friedrich Dominicus <···················@inka.de> writes:
> >
> > > (define (add-element element-to-add a-list)
> > > (if (not (memq element-to-add a-list))
> > > (cons element-to-add a-list)
> > > a-list))
> >
> > You'd almost think a function like this ought to have a name and
> > be part of the standard language... It might be really handy in
> > defining PUSHNEW, if your standard language had that, of course.
>
> This (standard) function in Common Lisp has :TEST and :KEY arguments.
> What would Scheme's way be of providing such capabilities?
>
Extend the RxRS to accept keyword arguments? And, since you are at
it, throw in structures, multi-dimensional arrays, and maybe
objects. :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
>>>>>"Marco" == Marco Antoniotti <·······@copernico.parades.rm.cnr.it> writes:
Marco> Vassil Nikolov <········@poboxes.com> writes:
>> This (standard) function in Common Lisp has :TEST and :KEY
>> arguments. What would Scheme's way be of providing such
>> capabilities?
Marco> Extend the RxRS to accept keyword arguments? And, since
Marco> you are at it, throw in structures, multi-dimensional
Marco> arrays, and maybe objects. :)
Well, since there is no package system in scheme, you could just use
ordinary symbols for keys. Having gotten used to the : for keywords, it isn't
as pretty, and of course one has to write the macros and stuff for
oneself; but its easily doable without adding to the report. Using
syntax-rules type macros one has to compromise a bit about the syntax,
too. But still.
Of course, the schemes that do add keyword arguments tend to follow
DSSSSSSSSL and add them to the end. I think this is done on purpose to
mess up my mind and corrupt my precious bodily fluids.
Here is a quick example. It has some rat in it, in that it doesn't do
allow-other-keys, nor optional arguments.
(define error ;; Not in R5RS.
(lambda what
(display what)
(err)))
(define unspecified (if #f #f)) ;; pointless
(define-syntax lambda/keys
(syntax-rules (keys)
((lambda/keys (required ...)
(keys (key value) ...)
body ...)
(lambda (required ... . keyword-arguments)
(let ((key value) ...)
(define (parse-keyword keyword val)
(case keyword
((key) (set! key val))
...
(else ;; no allow-other-keys.
(error "keyword not supported: " keyword))))
(do ((args keyword-arguments (cddr args)))
((null? args) unspecified)
(if (null? (cdr args))
(error "unpaired keyword arguments: " keyword-arguments)
(parse-keyword (car args) (cadr args))))
body ...)))))
(define identity (lambda (x) x))
(define adjoin
(lambda/keys (element list) ;; don't care about shadowing list
(keys (test eqv?) (key identity))
(let loop ((restlist list))
(cond
((null? restlist) (cons element list))
((test (key element) (key (car restlist))) list)
(else
(loop (cdr restlist)))))))
--
(define (cthulhu_fhthagn) ; Iver Odin Kvello, ·····@hfstud.uio.no
(call/cthulhu (lambda (destroy) ; Lambda, the Ultimate Horror
(if (stars-are-right? (now)) (destroy 'everything) (cthulhu_fhtagn)))))
From: Kent M Pitman
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <sfwk8rb31cu.fsf@world.std.com>
Marco Antoniotti <·······@copernico.parades.rm.cnr.it> writes:
> Vassil Nikolov <········@poboxes.com> writes:
>
> > Kent M Pitman wrote: [1999-08-03 04:01 +0000]
> >
> > > Friedrich Dominicus <···················@inka.de> writes:
> > >
> > > > (define (add-element element-to-add a-list)
> > > > (if (not (memq element-to-add a-list))
> > > > (cons element-to-add a-list)
> > > > a-list))
> > >
> > > You'd almost think a function like this ought to have a name and
> > > be part of the standard language... It might be really handy in
> > > defining PUSHNEW, if your standard language had that, of course.
> >
> > This (standard) function in Common Lisp has :TEST and :KEY arguments.
> > What would Scheme's way be of providing such capabilities?
> >
>
> Extend the RxRS to accept keyword arguments? And, since you are at
> it, throw in structures, multi-dimensional arrays, and maybe
> objects. :)
Well, I think the more Scheme-ish thing would be to make a function which
dispensed other functions. Probably they would not make it keyworded, but
rather positional. It would probably look like
(define (adjoin-dispenser tst ky)
(lambda (elemnt lst)
...))
And then you'd either do
((adjoin-dispenser equal? identity) new-guy some-respository)
or else
(define adjoin-using-equal (adjoin-dispenser equal? identity))
... (adjoin-using-equal new-guy some-respository) ...
Kent M Pitman wrote: [1999-08-04 17:24 +0000]
> > Vassil Nikolov <········@poboxes.com> writes:
[about ADJOIN]
> > > This (standard) function in Common Lisp has :TEST and :KEY arguments.
> > > What would Scheme's way be of providing such capabilities?
[...]
> Well, I think the more Scheme-ish thing would be to make a function which
> dispensed other functions. Probably they would not make it keyworded, but
> rather positional. It would probably look like
>
> (define (adjoin-dispenser tst ky)
> (lambda (elemnt lst)
> ...))
>
> And then you'd either do
>
> ((adjoin-dispenser equal? identity) new-guy some-respository)
>
> or else
>
> (define adjoin-using-equal (adjoin-dispenser equal? identity))
> ... (adjoin-using-equal new-guy some-respository) ...
Thank you, this is an answer exactly to my question.
Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
Abaci lignei --- programmatici ferrei.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
From: Kent M Pitman
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <sfwr9ljndo7.fsf@world.std.com>
Vassil Nikolov <········@poboxes.com> writes:
> Kent M Pitman wrote: [1999-08-04 17:24 +0000]
>
> > (define (adjoin-dispenser tst ky)
> > (lambda (elemnt lst)
> > ...))
> > And then you'd either do
> > ((adjoin-dispenser equal? identity) new-guy some-respository)
Btw, I didn't say but the thing I really don't like about this is
that the lack of keywords makes this hard to understand out of context.
It's obviously the case that Schemers could write a rest list and use
(adjoin-dispenser 'test equal? 'key identity)
and even then they could leave out arguments they didn't want, but
the language doesn't offer anything to encourage them to do it, which
means it will be too much trouble for some, too hard to remember
for others, and potentially irregularly done (e.g., varying in
calling details on a per-facility or per-author basis).
The thing I like about the Cl approach is that it acknowledges the
legitimate difficulty of remembering a fairly arbitrary ordering of a
bunch of args that are rarely all used at once, and that it provides
cues to help the uninitiated reader have a hint of what's going on.
It does create an implementation burden, though key calls can be
compiled efficiently with a little work. I'd rather the
implementation do that work once centrally, though, rather than users
doing it over and over again.
Consider how WRITE would be if it had to be expressed positionally,
for example, using the Scheme functional style. (It gets even weirder
when you have to curry out some that are not in contiguous order,
creating intermediate functions of fewer positional args ...)
I recall advice from long ago (I think it was Dick Waters who said it):
"A function that has more than 10 args has too few."
I have always interpreted this to mean that if there are this many to
remember, you will surely forget one. As such, positional is a bad idea
both for the caller, and for the person trying to design the perfect
ordering--nothing like having to upgrade positional code. Calls like
(apply foo x) ;Scheme
(apply #'foo x) ;CL
are real killers if FOO takes its args positionally and you've
just upgraded it to take a new third argument out of 9. And it's not
made any better by forcing all new args to go onto the end, since
that might feel really unnatural. Consider adding a "z" argument to
something that takes x and y coordinates as arg 1 and arg 2 followed
by other non-coordinate info with already-assigned arg positions.
Of course, this might make one inclined to use a single "location"
arg and to pass a cons or a struct, but that means potentially making
needless garbage...
Moral (IMO): Positional vs keyword is a choice that was meant to be
made at program writing time, not at language design time. You can force
choices to be made earlier (just look at how "well" C does with this
as a regular practice), but it may not actually side-effect the way
the world works in the way you wish it did. It might only make programs
harder to write. (No proof offered. Left to the reader.)
[Incidentally, regarding your date format, the US uses months and dates
flipped in many cases, and I strongly advocate 1999-Aug-04 17:24 +0000
if that's something whatever program you're using can live with. That
way no one is confused. Americans don't care about the order when
there is no ambiguity. Also, I don't know about you but I have a
terrible time with the months 08 and 09, which are a little like the 5
and 6 keys on the keyboard--too close to the place where you start
counting from the other end, and so I prefer never to use those months
by number for other reasons. For some reason, 06 and 07 don't bother
me, don't ask me why.]
From: Rob Warnock
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <7obk7f$26svu@fido.engr.sgi.com>
Kent M Pitman <······@world.std.com> wrote:
+---------------
| It's obviously the case that Schemers could write a rest list and use
| (adjoin-dispenser 'test equal? 'key identity)
+---------------
This is exactly what Elk [a Scheme] does with it's X binding. Sample code
clipped from a simple Xlib app:
(let* ((dpy (open-display))
(black (black-pixel dpy)) (white (white-pixel dpy))
(width (list-ref geom 0)) (height (list-ref geom 1))
(win (create-window 'parent (display-root-window dpy)
'width width 'height height
'x (list-ref geom 2) 'y (list-ref geom 3)
'background-pixel white
'border 0
'event-mask '(exposure)))
(gc (create-gcontext 'window win 'function 'xor
'background black 'foreground white))
...and-so-on... )
...the-main-app... )
There's a utility routine "apply-with-keywords" that matches the &rest list
with a pattern of required positional args (and their defaults), and then
calls the underlying primitive [written in C] with purely positional args.
E.g., for the "create-window" call above, the glue routine [with some added
annotations] is:
(define (create-window . args)
(apply-with-keywords
'create-window ; for error messages
xlib-create-window ; underlying primitive
; positional args required by underlying primitive:
'((parent) (x 0) (y 0) (width) (height) (border 2))
; table of additional permitted optionals:
'set-window-attributes set-window-attributes-slots
args))
Yes, a bit hacky, but once it's in place you *can* use keyword-style
calls pretty much anywhere they make sense...
+---------------
| and even then they could leave out arguments they didn't want, but
| the language doesn't offer anything to encourage them to do it, which
| means it will be too much trouble for some, too hard to remember
| for others, and potentially irregularly done (e.g., varying in
| calling details on a per-facility or per-author basis).
+---------------
Agreed. Had I not seen how Elk does it in its X binding, I probably
would have continued to avoid the "keyword" style. But now, having
been given one well-worked-out example...
-Rob
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA
Kent M Pitman <······@world.std.com> writes:
> [Incidentally, regarding your date format, the US uses months and dates
> flipped in many cases, and I strongly advocate 1999-Aug-04 17:24 +0000
> if that's something whatever program you're using can live with. That
> way no one is confused.
Except that you have hard coded your language (English) in your
format. I believe there is an ISO standard date format that goes
something like 1999:08:04:17:24. I don't know what they do about time
zones though.
--
Lieven Marchand <···@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
From: Robert Monfera
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <37AA07EE.A6DD0435@fisec.com>
Lieven Marchand wrote:
>
> Kent M Pitman <······@world.std.com> writes:
>
> > [Incidentally, regarding your date format, the US uses months and dates
> > flipped in many cases, and I strongly advocate 1999-Aug-04 17:24 +0000
> > if that's something whatever program you're using can live with. That
> > way no one is confused.
>
> Except that you have hard coded your language (English) in your
> format. I believe there is an ISO standard date format that goes
> something like 1999:08:04:17:24. I don't know what they do about time
> zones though.
To the analogy of the regrettable 'Hungarian coding', one could call it
Hungarian dating(?) with the notable exception that it _is_ the standard
there (e.g., 1999.aug.4. or 1999.08.04). And yes, being more
significant, family names are written first, Christian names last. The
land of dreams!
�dv!
Monfera Robert
99.08.05
Robert Monfera <·······@fisec.com> writes:
> Lieven Marchand wrote:
> >
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > [Incidentally, regarding your date format, the US uses months and dates
> > > flipped in many cases, and I strongly advocate 1999-Aug-04 17:24 +0000
> > > if that's something whatever program you're using can live with. That
> > > way no one is confused.
> >
> > Except that you have hard coded your language (English) in your
> > format. I believe there is an ISO standard date format that goes
> > something like 1999:08:04:17:24. I don't know what they do about time
> > zones though.
>
> To the analogy of the regrettable 'Hungarian coding', one could call it
> Hungarian dating(?) with the notable exception that it _is_ the standard
> there (e.g., 1999.aug.4. or 1999.08.04). And yes, being more
> significant, family names are written first, Christian names last. The
> land of dreams!
There are plenty of problems here.
First of all we should really be in 2752:08:06, :) but then that also
would have some problems. So here is the question of the day. Ho do
I write
(defun get-stardate () ... )
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
From: Eric Marsden
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <wziyafpdv0s.fsf@mail.dotcom.fr>
>>>>> "lm" == Lieven Marchand <···@bewoner.dma.be> writes:
kmp> [Incidentally, regarding your date format, the US uses months
kmp> and dates flipped in many cases, and I strongly advocate
kmp> 1999-Aug-04 17:24 +0000 if that's something whatever program
kmp> you're using can live with. That way no one is confused.
lm> Except that you have hard coded your language (English) in your
lm> format. I believe there is an ISO standard date format that goes
lm> something like 1999:08:04:17:24. I don't know what they do about
lm> time zones though.
International Standard ISO 8601 for numeric representations of date
and time:
1999-08-04 17:24+01:00
<URL:http://www.cl.cam.ac.uk/~mgk25/iso-time.html>
<URL:http://www.iso.ch/markete/8601.pdf>
--
Eric Marsden
It's elephants all the way down
From: Vassil Nikolov
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <7oeg2b$vtf$1@nnrp1.deja.com>
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
[on the value of CL keyword arguments]
I can only add that I am very happy with the fact that
CL has keyword arguments.
> [Incidentally, regarding your date format, the US uses months and
dates
> flipped in many cases, and I strongly advocate 1999-Aug-04 17:24
+0000
> if that's something whatever program you're using can live with.
That
> way no one is confused. [...]
You are quite right, and I always write the month in three letters
and not in two digits when I can.^1 Unfortunately, I can't do it
with the program I normally use (and I can't have a better one
in my particular circumstances). Sorry. (I could omit the date
at all, but I think it's nice to have it.)
__________
^1 not specifically because of the American ordering of mm/dd/yyyy
but because I believe it is generally easier and less error-prone
for people to comprehend
Anyway, yyyy-mm-dd is at least partly justified in being
language-independent (you don't want months in Bulgarian,
do you...) and also much easier to sort (doesn't require
special treatment both in implementing the comparison and
in specifying that such and such field is not just characters
but a date). (I suppose this is why such a format (or very
similar to that) was made standard by ISO for dates.)
(Note: I am posting this from a different place, using
Deja's WWW interface, so this particular message does not
have the date in this particular way.)
> Also, I don't know about you but I have a
> terrible time with the months 08 and 09, which are a little like the
5
> and 6 keys on the keyboard--too close to the place where you start
> counting from the other end, and so I prefer never to use those
months
> by number for other reasons. For some reason, 06 and 07 don't bother
> me, don't ask me why.]
6 and 7 are octal digits; 8 and 9 are the only decimal digits
that are not octal. (This explanation is very likely bogus,
but it saves me the desire to look for another one.)
--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
From: Kent M Pitman
Subject: Re: How to implement following procedures in Scheme?
Date:
Message-ID: <sfwu2qhwlzu.fsf@world.std.com>
Friedrich Dominicus <···················@inka.de> writes:
> (define (add-element element-to-add a-list)
> (if (not (memq element-to-add a-list))
> (cons element-to-add a-list)
> a-list))
You'd almost think a function like this ought to have a name and
be part of the standard language... It might be really handy in
defining PUSHNEW, if your standard language had that, of course.
On Sun, 01 Aug 1999 22:34:42 -0400, seamux <······@mediaone.net>
wrote:
>1. Union of lists:
>(union '(1 2 2 1) '(3 4 1 8))
> => (2 3 4 1 8)
What result do you get for (union '(3 4 1 8) '(1 2 2 1)) ?
For (union '(1 2) '(2 1) '(3 (4 1) 8)) ?
>3. removeall:
> (removeall 'a '(a (c d ( a t))) ) => (c d t)
> (removeall 't '(a (t d (a t))))) => (a (d a))
How did you get those answers? I got
((c d (t)))
and
(a (d (a)))
respectively.
Donald Welsh wrote:
> On Sun, 01 Aug 1999 22:34:42 -0400, seamux <······@mediaone.net>
> wrote:
>
> >1. Union of lists:
> >(union '(1 2 2 1) '(3 4 1 8))
> > => (2 3 4 1 8)
>
> What result do you get for (union '(3 4 1 8) '(1 2 2 1)) ?
it will get (3 4 1 8 2)
> For (union '(1 2) '(2 1) '(3 (4 1) 8)) ?
You will ge error message becaue union can only take 2 parameters.
>
>
> >3. removeall:
> > (removeall 'a '(a (c d ( a t))) ) => (c d t)
> > (removeall 't '(a (t d (a t))))) => (a (d a))
>
> How did you get those answers? I got
> ((c d (t)))
> and
> (a (d (a)))
> respectively.
You are correct. I was wrong on this.
On Tue, 03 Aug 1999 00:24:52 -0400, seamux <······@mediaone.net>
wrote:
>
>
>Donald Welsh wrote:
>
>> On Sun, 01 Aug 1999 22:34:42 -0400, seamux <······@mediaone.net>
>> wrote:
>>
>> >1. Union of lists:
(snippage)
>> What result do you get for (union '(3 4 1 8) '(1 2 2 1)) ?
>
>it will get (3 4 1 8 2)
I get (3 4 8 2 1).
>> For (union '(1 2) '(2 1) '(3 (4 1) 8)) ?
>
>You will ge error message becaue union can only take 2 parameters.
No. I wrote a generalized version.
Johan Kullstam <········@ne.mediaone.net> writes:
> Samir Barjoud <·····@mindspring.com> writes:
>
> > Why do (CAR NIL) and (CDR NIL) return NIL? Is this behavior purely
> > historical, or is it by design?
>
> i would say historical design. why do you ask? what would you like
> for them to do? in many respects NIL represents `nothing'. so, if a
> list has no CAR, then it would be appropriate for the `nothing' answer
> to be given.
No, the most appropriate would be to give an error or an exception.
Klaus Schilling
On 06 Jul 1999 17:45:59 +0200, Klaus Schilling <···············@home.ivm.de>
wrote:
>Johan Kullstam <········@ne.mediaone.net> writes:
>
>> Samir Barjoud <·····@mindspring.com> writes:
>>
>> > Why do (CAR NIL) and (CDR NIL) return NIL? Is this behavior purely
>> > historical, or is it by design?
>>
>> i would say historical design. why do you ask? what would you like
>> for them to do? in many respects NIL represents `nothing'. so, if a
>> list has no CAR, then it would be appropriate for the `nothing' answer
>> to be given.
>
>No, the most appropriate would be to give an error or an exception.
i disagree here... a car/cdr work on lists. an empty list is NIL,
the cdr of an empty list is an empty list (or NIL).
an empty list {'()} is NIL, but is NIL an empty list? once you answer this,
then you can as about the car/cdr aspect of NIL. the rest an empty list is
an empty list, the first of an empty list is NIL.
.
.
.
[1]> '()
NIL
[2]> (cdr '())
NIL
[3]> (cdr NIL)
NIL
[4]> (cdr '(a))
NIL
.
.
.
>Klaus Schilling
--
ray http://www.redrum.org
······@blade.redrum.org (ray canfield) writes:
> >No, the most appropriate would be to give an error or an exception.
>
> i disagree here... a car/cdr work on lists. an empty list is NIL,
> the cdr of an empty list is an empty list (or NIL).
But... Why should the CDR of an empty list be an empty list?
Applying CAR or CDR to the empty list could just as well signal an
error.
(Except for compatibility, of course. Here I'm talking about the
consistency of the hypothetical change.)
Hrvoje Niksic <·······@srce.hr> writes:
> ······@blade.redrum.org (ray canfield) writes:
>
> > >No, the most appropriate would be to give an error or an exception.
> >
> > i disagree here... a car/cdr work on lists. an empty list is NIL,
> > the cdr of an empty list is an empty list (or NIL).
>
> But... Why should the CDR of an empty list be an empty list?
tradition.
> Applying CAR or CDR to the empty list could just as well signal an
> error.
it could. it could also return a token meaning to the effect that the
object to which you apply CAR or CDR have no such part. you could
also check your arg with CONSP before taking a whack at it with CAR or
CDR. (CONSP NIL) => NIL (as in false).
in common-lisp the meaning of NIL covers the empty list, falsity, the
nothing concept, &c. NIL is horribly overloaded to mean all these
things (i think KMP would say it's punned). there was just this whole
CASE thread about matching NIL vs (NIL) and such. it's not always
perfect, but as long as it doesn't get in your way overmuch, who
cares?
> (Except for compatibility, of course. Here I'm talking about the
> consistency of the hypothetical change.)
of course you could define CAR and CDR differently. furthermore,
common-lisp is chock full of other cruft stemming from older
implementations (e.g., the order of GETHASH args as compared to AREF
&c). the reason common-lisp still works, is that this cruft doesn't
get in the way of actually making a program.
imho the language itself isn't particularly pretty. certainly the
*names* CAR and CDR are less than great. people keep trying to push
FIRST, SECOND, REST and friends. however, it just doesn't matter.
it's the flexible nature of the lisp syntax, power of macros, garbage
collection &c that make lisp work.
--
johan kullstam
Hrvoje Niksic <·······@srce.hr> writes:
> But... Why should the CDR of an empty list be an empty list?
Because, as a matter of practice, people are used to and comfortable with
taking this issue into account since it has been around for a long time
AND
because NIL commonly means "there was nothing here". It's a useful value
in that regard because it can be efficiently tested for. Why should
FIND-PACKAGE return NIL rather than signal an error as FIND-CLASS does?
Answer: because it's common to want some simple result that means "no".
(One could, of course, make CAR and CDR take :ERRORP keyword args, but
presumably some would consider that overkill.) The same claim can be made
about destructuring--that it's not always an error that one wants, and that
sometimes the ability to ask (nthcdr 10 x) and just get back NIL quickly
is better than the textual and runtime overhead [including, potentially,
the consing] of writing
(ignore-errors (cdr nil))
or
(handler-case (cdr nil)
(error () nil))
or perhaps things more baroque still. For example, I often write:
(if (cdr x) (cadr x))
I could write:
(if (and (consp x) (cdr x)) (cadr x))
Would that make my code clearer? Maybe. But you asked why one would do
this and the answer is that not everyone thinks that the extra call to
CONSP makes the code clearer. Some people think it just clutters things
and that such clutter makes things less clear.
Samir Barjoud <·····@mindspring.com> writes:
> Why do (CAR NIL) and (CDR NIL) return NIL? Is this behavior purely
> historical, or is it by design?
It's certainly historical. I vaguely recall hearing that it had come
from Interlisp. It was certainly well-established in Maclisp by time
I started using Lisp.
In Maclisp, NIL was represented by the machine number 0, so the CAR
and CDR operations (as implemented by the PDP10 HLRZ instruction
[which took Half Left to Right padding with Zeros, as in x,,y => 0,,x,
where x,,y is the left half of a 36-bit number being x and the right
half being y] and the HRRZ instructions [which did x,,y => 0,,y])
both took 0,,0 => 0,,0 so it was a natural. Also, testing NULL/NOT on
Maclisp was similarly easy and therefore handy to have be a 0 test.
Even in an implementation where 0 is not available as this value, it's
possible [and it's been done] to make NIL secretly be a cons that
points to itself in both car and cdr so it requires no extra instructions
to make car/cdr work on it, and then just to allocate it a different
type code so that you don't notice it's magic and you think it's a symbol.
It was both inexpensive and handy, since often one would otherwise end
up writing a lot of code that does
(if x (cdr x) nil)
and one might as well just write (cdr x) and pun on the effect of
the thing being either a cons or nil.
Other languages do similar things when they let you do math on
characters or boolean tests on integers. It's just exploiting an
accidental speed issue.
I'm ambivalent about whether flushing the capability would make the language
better. Certainly it would be massively incompatible so I would never
really seriously contemplate it in the standards context. But I also think
it's not 100% true that the langauge would be better even if compatibility
were not an issue and it could be freely changed back.
It's one of those things like aspirin that under present drug laws could
probably not be introduced into widespread use because of its many
side-effects but since people are using it so pervasively you just have
to kind of grin and bear it and say "maybe the public knows something
the regulatory agencies do not".
Kent M Pitman wrote:
> It was both inexpensive and handy, since often one would otherwise end
> up writing a lot of code that does
> (if x (cdr x) nil)
> and one might as well just write (cdr x) and pun on the effect of
> the thing being either a cons or nil.
"A Short Ballad Dedicated to Program Growth" by Ashwin Ram
(sorry, I don't have an URL, but it should be easy to find)
tells an interesting (and very funny!) case story related to this.
Arthur Lemmens <·······@simplex.nl> writes:
> "A Short Ballad Dedicated to Program Growth" by Ashwin Ram
> (sorry, I don't have an URL, but it should be easy to find)
> tells an interesting (and very funny!) case story related to this.
http://www.cs.uchicago.edu/~wiseman/humor/large-programs.html
http://elwoodcorp.com/alu/humor/large-programs.html