ternary cons?
D Herring
parts? I haven't thought much about a good printable representation;
but this seems like it could be a convenient multi-use structure.
- binary trees
- doubly-linked lists
- list variants like (a b (c d nil))
- rdf triples
...
It might also lay out nicely on stock hardware. Each "tcons" would
occupy four words: the first for tag bits and the others for values.
Didn't find anything in a quick search; thought I'd ask here.
Thanks,
Daniel
Pascal J. Bourguignon
> Have any lisp dialects experimented with a cons cell having three
> parts?
Yes. But this presents some difficulties.
(defstruct (tons (:constructor tons (a m d))) a m d)
(defun tar (x) (tons-a x)) (defun (setf tar) (v x) (setf (tons-a x) v))
(defun tmr (x) (tons-m x)) (defun (setf tmr) (v x) (setf (tons-m x) v))
(defun tdr (x) (tons-d x)) (defun (setf tdr) (v x) (setf (tons-d x) v))
;; Exercise for the reader #1: write the macrology required to generate
;; t...r accessors:
;; (defun taar (x) (tar (tar x)))
;; (defun tmmr (x) (tmr (tmr x)))
(defun tist (&rest elements)
(cond
((null elements) nil)
((null (rest elements)) (tons (first elements) nil nil))
(t (tons (first elements) (second elements)
(apply (function tist)
(rest (rest elements)))))))
(tist 1 2 3 4 5)
--> #<TONS :A 1 :M 2 :D #<TONS :A 3 :M 4 :D #<TONS :A 5 :M NIL :D NIL>>>
> I haven't thought much about a good printable representation;
> but this seems like it could be a convenient multi-use structure.
Well, obviously:
(defmethod print-object ((tist tons) stream)
(princ "(" stream)
(loop :for sep = "" :then " "
:for current = tist :then (tdr current)
:while (typep current 'tons)
:do (princ sep stream)
(prin1 (tar current) stream)
(princ " " stream)
(prin1 (tmr current) stream)
:finally (when current
;; a dotted tist!
(princ " . " stream)
(prin1 current stream)))
(princ ")" stream)
tist)
;; Exercise for the reader #2: write a reader macro for #\( to read lists
;; made of tonses instead of conses.
;; Exercise for the reader #3: provide the required functions to be able
;; to evaluate and compile forms read as tons lists (tists).
But then, we observe the first difficulty:
(tist 1 2 3 4 5)
--> (1 2 3 4 5 NIL)
How do we mark the difference between a nil inside the list and a nil
that terminates the list. More precisely, the problem is that we
consider nil in the tmr to be an element, and only nil in the tdr to be
the end of the list. But if the list is of odd length, then we have
two nils in the last tons.
The conclusion is that we will need a different token to mark the end of
the list made of tonses, if we want to be able to put nils in the lists
made of them.
> - binary trees
> - doubly-linked lists
> - list variants like (a b (c d nil))
> - rdf triples
> ...
>
> It might also lay out nicely on stock hardware. Each "tcons" would
> occupy four words: the first for tag bits and the others for values.
But lists made of conses alsy lay out nicely on stock hardware. Each
triplet occupy four words too: (a . (m . d))
> Didn't find anything in a quick search; thought I'd ask here.
Given that you can easily implement your own tonses in lisp, you can
have the fun yourself.
I'll mention that clisp has a compilation option to add a field to each
conses, which can be used to some nice effects. But AFAIK, it's rarely
used.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Barry Margolin
D Herring <dher...@at.tentpost.dot.com> wrote:
> Have any lisp dialects experimented with a cons cell having three
> parts? I haven't thought much about a good printable representation;
> but this seems like it could be a convenient multi-use structure.
MACLISP had a generalization of conses called "hunks", that could be up
to 512 elements in size. See
http://maclisp.info/pitmanual/hunks.html
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Rob Warnock
+---------------
| D Herring <dher...@at.tentpost.dot.com> writes:
| > Have any lisp dialects experimented with a cons cell having three
| > parts?
|
| Yes. But this presents some difficulties.
| (defstruct (tons (:constructor tons (a m d))) a m d)
| (defun tar (x) (tons-a x)) (defun (setf tar) (v x) (setf (tons-a x) v))
| (defun tmr (x) (tons-m x)) (defun (setf tmr) (v x) (setf (tons-m x) v))
| (defun tdr (x) (tons-d x)) (defun (setf tdr) (v x) (setf (tons-d x) v))
+---------------
And some possibilities as well. See "Naggum quads",
recapitulated/summarized here [from a 2004 thread]:
http://smuglispweeny.blogspot.com/2009/06/i-feel-naggum-rip-coming-on-quads.html
I Feel A Naggum (RIP) Coming On: Quads
Kenny Tilton
Friday, June 26, 2009
Very like Pascal tonses, but with prefix Q instead of T, and
A/B/C/D for the interior letters instead of A/M/D. That is,
QAR, QBR, QCR, & QDR [and (SETF QAR), etc.].]
The conventional slot usage with quads [especially when walking
SGML-like DOM structures] is:
QAR - Element type
QBR - Back (parent) link
QCR - Element content
QDR - Next element in list
Notice that [with adequate macrology to generate the conbimations] the
usual combinations of interior letters make sense [well, some of them!]:
QADR - Type of the next element at the same level
QBBR - Two levels "up" from here.
And so on.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403
Xah Lee
Haines, E. C., The TREET List Processing Language. M.S. Thesis, MIT,
Cambridge, Mass., August 1964. Also SR-133, The MITRE Corporation,
Bedford, Mass., April 1965.
〈Programing Language: Fundamental Problems of Lisp〉
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
Xah
Toby Thain
https://groups.google.com/d/msg/alt.folklore.computers/ocLEir5Gfzw/PQQeUp59IbYJ
RG
rp...@rpw3.org (Rob Warnock) wrote:
Why stop at four? We have this handy dandy invention called "numbers".
So we can generalize from T and Q to N. N1R is CAR, N2R is CADR, NnR is
CA[D]^nR and NNR is CDR. Adding alphabetics to the mix gets you up to
36 elements. And if that's not enough there's always unicode.
(And no, I'm not being serious, just in case you were wondering. CONS
cells with more than two elements are isomorphic to vectors. So just
use vectors. Duh.)
rg
Chris Riesbeck
> In article<it95nk$nl1$1...@dont-email.me>,
> D Herring<dher...@at.tentpost.dot.com> wrote:
>
>> Have any lisp dialects experimented with a cons cell having three
>> parts? I haven't thought much about a good printable representation;
>> but this seems like it could be a convenient multi-use structure.
>
> MACLISP had a generalization of conses called "hunks", that could be up
> to 512 elements in size. See
>
> http://maclisp.info/pitmanual/hunks.html
>
CDC machines in the 70s had 60 bit words and 18 bit addresses and CDC
Lisp had cons cells with CAR, CDR and CSR. I used their Lips, but not
CSR, for a year but don't remember it showing up in printing. Don't know
if any CDC Lisp manuals are around but this is briefly described at
http://www.mschaef.com/blog/tech/lisp/car-cdr.html
Thomas A. Russ
> MACLISP had a generalization of conses called "hunks", that could be up
> to 512 elements in size. See
>
> http://maclisp.info/pitmanual/hunks.html
Ah yes, the good old CXR.
IIRC these were used mostly until vectors and arrays entered the
language. Once you had vectors, the use case for hunks went away.
--
Thomas A. Russ, USC/Information Sciences Institute
Barry Margolin
t...@sevak.isi.edu (Thomas A. Russ) wrote:
> Barry Margolin <bar...@alum.mit.edu> writes:
>
> > MACLISP had a generalization of conses called "hunks", that could be up
> > to 512 elements in size. See
> >
> > http://maclisp.info/pitmanual/hunks.html
>
> Ah yes, the good old CXR.
>
> IIRC these were used mostly until vectors and arrays entered the
> language. Once you had vectors, the use case for hunks went away.
I think MACLISP already had arrays, but they weren't first-class. When
you created an array, you had to use it like a function name. So hunks
were used when first-class objects were needed. For instance, they were
used to implement DEFSTRUCT.
Xah Lee
> In article <yNOdnbe87rEarGXQnZ2dnUVZ_h-dn...@speakeasy.net>,
> r...@rpw3.org (Rob Warnock) wrote:
>
>
>
>
>
> > Pascal J. Bourguignon <p...@informatimago.com> wrote:
> > +---------------
> > | > Have any lisp dialects experimented with a cons cell having three
> > | > parts?
> > |
> > | Yes. But this presents some difficulties.
> > | (defstruct (tons (:constructor tons (a m d))) a m d)
> > | (defun tar (x) (tons-a x)) (defun (setf tar) (v x) (setf (tons-a x) v))
> > | (defun tmr (x) (tons-m x)) (defun (setf tmr) (v x) (setf (tons-m x) v))
> > | (defun tdr (x) (tons-d x)) (defun (setf tdr) (v x) (setf (tons-d x) v))
> > ...[trimmed]...
> > +---------------
>
> > And some possibilities as well. See "Naggum quads",
> > recapitulated/summarized here [from a 2004 thread]:
>
if we say that cons cell more than 2 elements are isomorphic to
vectors (which is practically true without being picky), than we could
also say cons cell of 2 elemests are just vectors of 2 elements (which
i also believe). Thus, cons are not needed. (which is true in all
modern langs, i think including clojure and newlisp, but am not sure
there)
Xah
Marco Antoniotti
> On Jun 15, 10:16 am, RG <rNOS...@flownet.com> wrote:
> > In article <yNOdnbe87rEarGXQ...@speakeasy.net>,> wrote:
> > > +---------------
Yep. And besides, who needs 32 and 64 bits integers (or 42 bits integers) when you can have Z?
Cheers
--
MA
Xah Lee
you need those for efficiency reasons. But i suppose some modern lang
also transparently optimize it away. i.e. the lang doesnt have int or
long or double such computer engineering byproduct shit, it just have
real numbers or complex numbers, yet your code is no less efficient
than lang with explicit long double etc types. e.g. Mathematica, and i
think Haskell or other may also approach.
Xah
Marco Antoniotti
> On Jun 16, 12:39 am, Marco Antoniotti <mar...@gmail.com> wrote:
> > On Thursday, June 16, 2011 5:28:56 AM UTC+2, Xah Lee wrote:
> > > > In article <yNOdnbe87...@speakeasy.net>,
> > > > r....@rpw3.org (Rob Warnock) wrote:
> >
> > > > > Pascal J. Bourguignon
> > > wrote:
> > > > > +---------------
And you should think CL as well in this respect: (fact 13) in CL works "as expected" on a 32bit architecture.
Cheers
--
MA
Ankur
> cons cell of 2 elemests are just vectors of 2 elements. [...]
> Thus, cons are not needed. (which is true in all
> modern langs, i think including clojure and newlisp, but am not sure
> there)
Your arguments against cons basically boil down to
"I don't understand it", which is not very convincing.
--
Ankur
Marco Antoniotti
I think more along the lines of "they are old". Apart from that, Mathematca, deep deep down uses conses (or at least it did some time ago). Plus, the ':' Haskell constructor is essentially CONS (modulo the typing machinery), as is the much much older ./2 Prolog term constructor.
Cheers
--
MA
z
news:766c6e91-d2a8-4119...@r35g2000prj.googlegroups.com:
> if we say that cons cell more than 2 elements are isomorphic to
> vectors (which is practically true without being picky), than we could
> also say cons cell of 2 elemests are just vectors of 2 elements (which
> i also believe). Thus, cons are not needed. (which is true in all
One difference between a cons cell and a vector of 2 elements is that the
vector of 2 elements has a length of 2, but the length of a cons cell is
the length of the list it participates in.
Even if the differences between cons cells and vectors of 2 elements seem
like minor differences, they're important, and are extensively relied on.
Ternary cons etc. are not important because they're not relied on in such a
way that they can't simply be replaced by vectors.
x
> you need those for efficiency reasons. But i suppose some modern lang
> also transparently optimize it away. i.e. the lang doesnt have int or
> long or double such computer engineering byproduct shit, it just have
> real numbers or complex numbers, yet your code is no less efficient
> than lang with explicit long double etc types. e.g. Mathematica, and i
> think Haskell or other may also approach.
An array of a billion numbers that will always be integers between 0 and
100, is one example of why you need different types of numbers. How can
the compiler optimize it unless it can predict the numbers will always be
between 0 and 100? The only way it can predict that is if you tell it.
And telling it is the same thing as declaring a type for the numbers.
D Herring
> Pascal J. Bourguignon<p...@informatimago.com> wrote:
> +---------------
> | D Herring<dher...@at.tentpost.dot.com> writes:
> |> Have any lisp dialects experimented with a cons cell having three
> |> parts?
> |
> | Yes. But this presents some difficulties.
> | (defstruct (tons (:constructor tons (a m d))) a m d)
> | (defun tar (x) (tons-a x)) (defun (setf tar) (v x) (setf (tons-a x) v))
> | (defun tmr (x) (tons-m x)) (defun (setf tmr) (v x) (setf (tons-m x) v))
> | (defun tdr (x) (tons-d x)) (defun (setf tdr) (v x) (setf (tons-d x) v))
> ...[trimmed]...
> +---------------
>
> And some possibilities as well. See "Naggum quads",
> recapitulated/summarized here [from a 2004 thread]:
>
> http://smuglispweeny.blogspot.com/2009/06/i-feel-naggum-rip-coming-on-quads.html
> I Feel A Naggum (RIP) Coming On: Quads
> Kenny Tilton
> Friday, June 26, 2009
>
> Very like Pascal tonses, but with prefix Q instead of T, and
> A/B/C/D for the interior letters instead of A/M/D. That is,
>
> The conventional slot usage with quads [especially when walking
> SGML-like DOM structures] is:
>
> QAR - Element type
> QBR - Back (parent) link
> QCR - Element content
> QDR - Next element in list
Thanks to everyone for the information so far. This post was the type
of thing I'm looking for. Something that establishes "standard" the
uses for a "building-block structure" other than a two-cell cons.
It looks like this never really caught on. I wonder why. CONS was
good enough? TONS was slightly less efficient? Doubly-linked lists
were hindering GC and broke list splicing? Another reason?
- Daniel
Xah Lee
like, when a man doesn't know anything about computers, and he tells
you YOUR software sucks, and it really is true.
Xah
Pascal J. Bourguignon
> It looks like this never really caught on. I wonder why. CONS was
> good enough? TONS was slightly less efficient? Doubly-linked lists
> were hindering GC and broke list splicing? Another reason?
The reason is that CONS are more elementary. They are the simpliest
structure from which all the other structures can be built from.
(defstruct (tons (:type list) (:constructor tons (a m d))) a m d)
(tons 1 2 3) --> (1 . (2 . (3 . NIL)))
or:
(defun tons (a m d) (cons a (cons m d)))
(tons 1 2 3) --> (1 . (2 . 3))
therefore there's no need for anything else. Just atoms and conses.
Ankur
> Your arguments against cons basically boil down to
> "I don't understand it", which is not very convincing.
* Xah Lee <xah...@gmail.com>
> like, when a man doesn't know anything about computers, and he tells
> you YOUR software sucks, and it really is true.
Only if men who know nothing about computers are the target audience.
When something is hard to understand, yes it might be unnecessarily
complex; but it could just be that the concept is new to you, so
it is up to you to understand it.
C wouldn't be better off without pointers.
--
Ankur
TheFlyingDutchman
> if we say that cons cell more than 2 elements are isomorphic to
> vectors (which is practically true without being picky), than we could
> also say cons cell of 2 elemests are just vectors of 2 elements (which
> i also believe). Thus, cons are not needed. (which is true in all
> modern langs, i think including clojure and newlisp, but am not sure
> there)
>
What is the discriminator(s) for whether or not a language is modern?
Clojure does not have cons cells or any similar discrete node type.
Surprisingly, it did name the function to prepend an element to data
structures that implement the ISeq interface (referred to as a
sequences) "cons".
Thomas A. Russ
> An array of a billion numbers that will always be integers between 0 and
> 100, is one example of why you need different types of numbers. How can
> the compiler optimize it unless it can predict the numbers will always be
> between 0 and 100? The only way it can predict that is if you tell it.
> And telling it is the same thing as declaring a type for the numbers.
Well, yes at some level.
But the type for the numbers doesn't have to be built in to the
language. In fact, the Lisp ability to declare the range of the
integers allows the implementation to pick a suitable underlying
representation based on information from the domain itself.
Floating point is trickier because there is not just range but precision
involved as well.
(There are also a few other languages that allow specification of
integer (and other?) ranges.)
D Herring
> D Herring<dher...@at.tentpost.dot.com> writes:
>> It looks like this never really caught on. I wonder why. CONS was
>> good enough? TONS was slightly less efficient? Doubly-linked lists
>> were hindering GC and broke list splicing? Another reason?
>
> The reason is that CONS are more elementary. They are the simpliest
> structure from which all the other structures can be built from.
> therefore there's no need for anything else. Just atoms and conses.
But bigger atoms may have several benefits in the molecular sense.
The two-cell cons structure spawned a large ecosystem of traversal and
query functions. This gives cons cells their great flexibility, their
frequent preference over a similarly-sized struct or array, and the
endurance of car/cdr against contenders like first/rest.
It seems possible that doubly-linked lists are rather rare in lisp
because their benefit is low compared to the complexity of a cons
implementation; but the cons implementation is simple enough that
everybody rolls their own and none became standard.
Would a tons ecosystem contain a significantly larger set of standard
traversal and query functions? So far, I've gotten a couple good
leads on where others have taken the idea.
I have a soft spot for exploring "simple and obvious things" for a
depth of understanding and to make sure I'm not in a rut (scientific
term: local optimum).
Later,
Daniel
Xah Lee
> * Ankur <an...@lipidity.com> wrote:
> > Your arguments against cons basically boil down to
> > "I don't understand it", which is not very convincing.
>
> * Xah Lee <xah...@gmail.com>
>
> > like, when a man doesn't know anything about computers, and he tells
> > you YOUR software sucks, and it really is true.
>
> Only if men who know nothing about computers are the target audience.
like, when a programer doesn't know anything about compilers, and he
tells you YOUR language sucks, and it really is true.
Xah
Xah Lee
this is what bugs me about “hacker” idiots.
those who see the idiocy of cons, stay quite, or at best, hint that
it's just the way it was.
while, u have a gaggle of idiots forwardly defending the glory of
cons.
it's a funny thing. y'know, when cons doesn't exist in all modern
langs, even new lisps (clojure, newLisp), it doesn't seem to mean
anything to these old lisp idiots.
btw, does arc lisp do cons? also, i don't know about Qi lisp. It would
be interesting to know. (but no, am not really interested to take the
trouble to find out. All i wanna do is call Common Lisper idiots.)
Common Lispers in general are idiots, of high order. (well, more
precisely: the common lispers who hangs in comp.lang.lisp. Actually,
more precisely: just a handful of them vocal common lisp fanatics.
Actually, the few that cries me troll seems to have decreased over the
years. In fact if you look at this tread, it seems to be just a few
who are having a crisis over con, and only ONE actually directly
attacking me per se. So am not sure why am i complaining. O, but the
cons is a major issue to me. I think i really like to stamp out this
cons myth. Stamp it out. So, i would like to encourage you all
lispers... whenever someone brings cons up again, in some ignorant
way, or excited way, give their ass a forceful kick. (in 5 years, if
lisp are still alive, and cons use died off, u should thank one Xah
Lee.))
here's what i like to see happen in comp.lang.lisp community. When
someone ignorant or newb started to blurt out excitedly about cons
(mostly due to massive old literature), you should dully tell them:
Avoid it if you can. It's old. Not applicable today.
y'know? cons is one of those identity thing about lisp, alone with
parens. That's why it's a hot button. It perennially comes up. It's
like emacs's *scratch* buffer or its use of Ctrl+c and Ctrl+x. It's a
identity crisis. Like, if u r the only one in town with blue hair, and
it comes to pass that blue hair is bad, then you really can't accept
it. It's like, hair color would become the only thing to judge a
person.
fuck common lispers.
Xah
Ankur
> When someone[...] started to blurt out excitedly about cons
> [...] you should dully tell them:
> Avoid it if you can. It's old. Not applicable today.
Are you talking about cons the structure, the term, or the function?
> It's a identity crisis.
> fuck common lispers.
It seems like you do this to feel superior, or do you think you are
the only one who is sane?
--
Ankur
ok
> > fuck common lispers.
>
> It seems like you do this to feel superior, or do you think you are
> the only one who is sane?
[OT]
Xah is like a flea on a dog, claiming that the dog is his personal
property.
We all behave more or less the same -- in some not-so-obvious
context...
Norbert_Paul
Xah Lee wrote:
> fuck common lispers.
Pascal J. Bourguignon
> Xah Lee wrote:
>> fuck common lispers.
> Go away!
It's called a killfile. Put:
(gnus-kill "From" "xahlee")
(gnus-expunge "X")
in ~/News/KILL
Norbert_Paul
I learned it here in this group ;)
Hraban Luyat
Thank you for questioning the fundamentals. I like your approach.
Summarising this conversation, I think we can conclude the following: In essence, conses are nice not because of their implementation per se, or even inherently because of their own semantics, but because of the conventions that surround them. Saying that conses are just two-element vectors is talking about implementation. Saying no, they are not, e.g.: the length, that is their interpretation. Basically, the point is whether the context of a cons is part of the definition.
No need for confrontation, we can just say conses can be defined both ways and then specify which definition we refer to when talking about them. And you, I think, were talking about the latter definition: the context and conventions are part of your definition of conses, the way they are used for linked lists and trees. If not, please correct me.
So, we have the singly linked list and the tree, and we have an elegant implementation using nothing but these two-element tuples. What other datastructures are much used, and how? What would be the most elegant solution for them? You mentioned a few. Are 3-element tuples really the best idea for them?
I think that saying "what could we do with 3-element tuples" is the wrong way to go at it. It would be a lot more gratifying to look at some powerful, common and versatile datastructures, and common algorithms on those structures that, together, dictate a common usage pattern. Then we can try to distill an elegant implementation, as simple as possible. Once we have a new elegant implementation for those datastructures, we compare that to existing implementations, and then we can hopefully compare the benefits and drawbacks and conclude whether or not it is worth it.
Let us be honest, is the extreme simplicity of the cons not a major part of its success? I like to think that this is where both definitions meet and coexist in peace :)
I am interested in your opinion and the set of datastructures + usage patterns that benefit from a simple implementation.
Greetings,
Hraban Luyat
vlionix
> fuck common lispers.
> Xah
That's not constructive. Maybe you should go somewhere else.
Xah Lee
│ * Xah Lee 〔xah…@gmail.com〕
│
│ │ When someone[…] started to blurt out excitedly about cons
│ │ […] you should dully tell them:
│ │ Avoid it if you can. It's old. Not applicable today.
│
│ Are you talking about cons the structure, the term, or the function?
│ │ It's a identity crisis.
│ │ fuck common lispers.
│
│ It seems like you do this to feel superior, or do you think you are
│ the only one who is sane?
i've written my reasons. Of the interested parties, please you peruse
of it:
〈Programing Language: Fundamental Problems of Lisp〉
xahlee.org/UnixResource_dir/writ/lisp_problems.html
〈Programing Language: Why Lisp Do Not Have a Generic Copy-List
Function〉
xahlee.org/UnixResource_dir/writ/lisp_equal_copy_list.html
〈Lisp's List Problem〉
xahlee.org/emacs/lisp_list_problem.html
〈Xah Lee's Computing Experience (Impression Of Lisp from Mathematica)〉
xahlee.org/PageTwo_dir/Personal_dir/xah_comp_exp.html
Xah
Ankur
> When someone[…] started to blurt out excitedly about cons[…]
I don’t think that is very likely.
> │ │ It's a identity crisis.
> │ │ fuck common lispers.
> i've written my reasons. Of the interested parties, please you peruse
> of it:
I had read those articles before, but I read them again. Still no good explanation.
But I found the “why we have cons” thread in the scheme group,
and I think I see what your issue is now.
Unfortunately (for you) and contrary to popular belief, CL is designed
for programmers, not mathematicians. If you want to insulate yourself
from details, then stick to Mathematica – no reason to rant about lisp.
--
Ankur
Marco Antoniotti
... and deep deep down, let's remember, Matemathica was built upon 'Cons' (and probably still is).
Cheers
--
MA
fortunatus
> It seems possible that doubly-linked lists are rather rare in lisp
> because their benefit is low compared to the complexity of a cons
> implementation; but the cons implementation is simple enough that
> everybody rolls their own and none became standard.
I miss doubly-linked-lists. When I am working in Lisp and I would
like to have bidirectional traversal and easier list editing, I build
a backwards list as I go down the original list data, that makes the
back-links available as I go.
I was really surprised when I learned that Lisp fundamentally supports
singly-linked lists and not doubly-linked lists.
I was writing cons cells in my C code since college for general list
handling. I didn't know the term "cons"; I called the cells "llu" for
"linked list unit". Early on I adopted doubly-linked 3-slot cells as
my basic level of linked list construction becaue I felt the list
editing operations were more efficient and "regular".
So now I work a lot in Lisp, and while I have language support for
most list operations I need -- and I do appreciate that -- I find I
still "roll my own" with regard to doubly-linked functionality!
Has anyone offerred a CL package for doubly-linked functionality?
Perhaps on one hand similar to Pascal's example, or on another hand
(Nth hand?) something like a set of my own back-list building
algorithms?
Pascal J. Bourguignon
> Has anyone offerred a CL package for doubly-linked functionality?
Of course. There are tons of libraries with this abstract data type.
For example: com.informatimago.common-lisp.cesarum.dll
(ql:quickload :com.informatimago.common-lisp.cesarum)
(use-package :com.informatimago.common-lisp.cesarum.dll)
(let ((dist (dll 1 2 3)))
(dll-append dist (dll (dll-first dist))) ; O(1)
(dll-insert dist (dll-node-nth 2 dist) 4)
(dll-contents dist))
--> (1 2 3 4)
Actually, I just found a bug, so:
1- com.informatimago.common-lisp.cesarum is "maintained"!
2- you may get the latest from https://gitorious.org/com-informatimago/
(or you may wait for quicklisp to upgrade, but I don't know if it's
done automatically or often).
> Perhaps on one hand similar to Pascal's example, or on another hand
> (Nth hand?) something like a set of my own back-list building
> algorithms?
DLLs have the big inconvenient that you cannot share structure. If you
use DLLs, you will cons a lot more (granted, with 24 GB of RAM, I can
cons a lot more than people could when lisp was invented, but still).
What you must realize that there is actually no list in lisp.
http://groups.google.com/group/comp.lang.lisp/msg/61a6e3354faf17ba
This is what makes it so good at list processing.
(There's no I/O in C, that's what makes it so good at I/O processing).
Marco Antoniotti
>
> What you must realize that there is actually no list in lisp.
Why, o why, art thou feeding trolls! :)
Cheers
--
MA
D Herring
> Let us be honest, is the extreme simplicity of the cons not a major part of its success? I like to think that this is where both definitions meet and coexist in peace :)
>
> I am interested in your opinion and the set of datastructures + usage patterns that benefit from a simple implementation.
Thanks for your reply. I wasn't sure how to respond. I agree that
the simple yet flexible interface of cons is a key to its popularity.
The std::pair in C++, while conceptually similar, is infrequently
used, IMO because its interface is complicated by templates.
The simplicity of implementation was also helpful to the success of
cons. Complicated things often run slowly, are hard to get right and
understand, take a long time to spread across implementations, etc.
However I'm not sure implementation simplicity is a long-term
requirement. For example, finger trees are catching on as a
multipurpose data structure, hash tables are everywhere, etc.
"2-3 trees" use both ternary and quinary structures.
I'm curious whether there is a useful generalization of the cons
ecosystem to other structures of small prime size. Don't have any
solid answers though.
- Daniel
Robert Maas, http://tinyurl.com/uh3t
> those who see the idiocy of cons
Huh? CONS is a really good idea, more later below.
> stay quite
Huh?? Do you have any understanding that "quite" and "quiet" are
entirely different words with majorly different meanings?
> u have a gaggle of idiots forwardly defending the glory of cons.
That seems to be a "straw man".CONS isn't glorious, it's merely
useful in a major practical way, more later below.
> when cons doesn't exist in all modern langs
Do you mean the structure-type exists but with a different name, or
that such a type of structure isn't at all implemented in the
language? More later below.
> All i wanna do is call Common Lisper idiots.
Who is Common Lisper?? How can one person be called *idiots* (plural)??
> Common Lispers in general are idiots, of high order. (well, more
> precisely: the common lispers who hangs in comp.lang.lisp.
> Actually, more precisely: just a handful of them vocal common
> lisp fanatics. Actually, the few that cries me troll seems to
> have decreased over the years.
WTF do you mean by "cries me troll"? Until you learn correct
English, I suggest you hire somebody to proofread anything you plan
to post, to work with you to figure out how to express in English
what you intend to say.
But even with your bad English, it's clear that you are
wishy-washy. You need to figure out what you mean to say, and say
*that*, rather than say something you don't mean to say, then
correct it to something else you don't want to say, then correct it
again.
So anyway, your post sounds like a "troll", calling people bad
names without any justification for such calling.
> I think i really like to stamp out this cons myth.
I've never heard of the "cons myth". Please post a link to it so
that I can read it once and make comments on it.
> in 5 years, if lisp are still alive, and cons use died off, u
> should thank one Xah Lee.
CONS will still be useful in 5 years, so there's no way use of it will
die off, so you aren't going to be thanked. (And if somehow the
usefulness of CONS were somehow forcibly eradicated from the world,
such as by some despot, you wouldn't be thanked, you'd be tarred and
feathered.) More later below.
> here's what i like to see happen in comp.lang.lisp community.
> When someone ignorant or newb started to blurt out excitedly
> about cons (mostly due to massive old literature), you should
> dully tell them: Avoid it if you can. It's old. Not applicable
> today.
Are you complaining that you don't like the name, or you don't like
the functionality? If the former, what alternate name would you
propose? If the latter, see more later below as to why the
functionality of CONS is still valuable and will remain valuable
for a long time.
> cons is one of those identity thing about lisp,
That isn't grammatically correct, and even with grammatical
corrections it doesn't make sense.
> alone with parens.
How can anyone be alone when parens are there to hug you? Perhaps
you have no understanding of the difference between "along" and "alone".
> It's like emacs's *scratch* buffer
Given that any buffer created in EMACS stays around forever, and
it's a pain to have hundreds of random buffers appear and clutter
the list of buffers, it's a reasonable trade-off that a whole bunch
of various features use a single shared *scratch* for their
temporary work-space instead of each creating a separate buffer.
What do *you* think is wrong with having a place to use as scratch
space for a whole slew of different operations within EMACS?
> fuck common lispers.
I'm going to consider that a sexual assault and report you to
InterPol for arrest and prosecution.
As promised above ("more later"), it's now "later", and here is "more":
Linked lists are a very useful type of intentional storage
structure. If you don't understand why, you need to study
first-year computer science. Consequently, the unit cell used to
build linked lists is a very useful implementational storage
structure. Thus it's good to have such two-part cells built into a
programming language.
Trees are very useful types of intentional storage structures. If
you don't understand why, you need to study first-year computer
science. Consequently, the unit cells used to build trees are
useful types of storage structure. Now you could have a different
type of built-in cell for each different type of tree you might
build. But then you could build *only* the types of trees that used
the types of cells you had available. You couldn't build *other*
types of trees that required other types of cells, at least not by
the same easy mechanism of simply using the built-in cells directly
as the nodes of the trees. The alterative is not to require that
the unit cell of a tree be a built-in (implementational) data type,
but rather to emulate such a tree-cell using some other more
primitive cell type. Since CONS cells are already available (per
the previous paragraph), they might as well be used as the base for
building tree-cells. For example, if you needed a tree-cell which
has fields [left right depth] you could implement that as (depth .
(left . right)), while if you needed a tree-cell which has fields
[left right count] you could implement that as (count . (left .
right)), and if you needed a tree-cell which has fields [left right
count depth] you could implement that as (count . (depth . (left .
right))), etc.
Thus having CONS cells implemented allows ordinary application/library
programmers to implement linked lists and a wide variety of trees too.
This allows Lisp to be used for agile development, i.e. "just do it"
quickly without a lot of getting-started overhead.
Note, if you don't understand the difference between an
implementational datatype and an intentional datatype, let me know.
(Hint: The TYPE-OF function tells the implementational datatype.)
Robert Maas, http://tinyurl.com/uh3t
> What you must realize that there is actually no list in lisp.
That's not quite correct. What you should say is that in Lisp:
list is an intentional datatype, not an implementational datatype.
There is nothing in Lisp which when passed to TYPE-OF will return
LIST. But there are a whole bunch of functions that deal with LIST
as an intentional datatype (APPEND REVERSE MEMBER LENGTH FIND
POSITION COUNT etc.)
> This is what makes it so good at list processing.
Caveat: If you want to be able to share tails, but you don't need
to share non-tail segments, then linked lists (as implemented in
Lisp as daisy chains of CONS cells) are appropriate. But if you
want to be able to share arbitrary segments, linked lists won't do
the job, you'll need some other kind of structure such as
self-balancing binary search trees instead.
Thus for *some* types of list processing, Lisp is very good, using
its built-in linked-list intentional datatype (per library of
functions to deal with that intentional datatype). But for other
types of list processing, Lisp is good for a different reason, that
self-balancing binary search trees can be easily defined via CONS
cells, thus it's relatively easy to build a library for such a new
intentional datatype to support those other forms of list processing.
Example: You want to start with a list, then make incremental
changes to the list, adding new elements, removing elements,
appending or inserting other lists, chopping out segments, etc.,
and while doing this you want to maintain a log of *each* state in
this process, sharing as much structure as possible between
adjacent states in this sequence. You even want to fork the
sequence, having alternate branches of edit-sequences, sharing as
much structure as possible between each branch point and each of
the next edit results per the various branches from that point.
Self-balancing binary search trees with non-destructive edit
operations that share structure between original and edit-result,
will allow all that. (And all that is easy to implement in Lisp,
using CONS as the basic building block for structures.)
Side remark: Any intentional datatype in Lisp can be converted to
an implementational datatype by wrapping it with a CLOS class. But
then if you want to keep all past states of a sequence of edits you
must do a shallow clone of the current object before doing any edit
operation, so that the original object won't be modified, only the
clone will be modified, so after the edit the original object has
the old state and the newly-cloned+edited object will have the new
state, yet as before as much structure as possible will be shared
between the old object and the edit-result object.
Pascal J. Bourguignon
writes:
>> Common Lispers in general are idiots, of high order. (well, more
>> precisely: the common lispers who hangs in comp.lang.lisp.
>> Actually, more precisely: just a handful of them vocal common
>> lisp fanatics. Actually, the few that cries me troll seems to
>> have decreased over the years.
>
> WTF do you mean by "cries me troll"? Until you learn correct
> English, I suggest you hire somebody to proofread anything you plan
> to post, to work with you to figure out how to express in English
> what you intend to say.
Robert, the reason why the few who call Xah Lee "troll" seems to
decrease, is only because they have fill-filed him. I'd advise you to
do the same, to avoid losing your time and ours.
fortunatus
wrote:
> Robert, the reason why the few who call Xah Lee "troll" seems to
> decrease, is only because they have fill-filed him. I'd advise you to
> do the same, to avoid losing your time and ours.
I don't kill-file Xah; sometimes he's great. I just take the good and
skip over the bad.
For sure it makes no sense to spend so much "bandwidth" indulging in a
"proper" (though clearly argumentatively motivated) criticism of Xah -
we've all tried it and it gets old...
Vend
> ... and deep deep down, let's remember, Matemathica was built upon 'Cons' (and probably still is).
Is it?
Vend
http://tinyurl.com/uh3t) wrote:
> Linked lists are a very useful type of intentional storage
> structure. If you don't understand why, you need to study
> first-year computer science. Consequently, the unit cell used to
> build linked lists is a very useful implementational storage
> structure. Thus it's good to have such two-part cells built into a
> programming language.
List datatypes are included in most modern languages, which usually
offer multiple implementations (linked list and auto-resizing vector).
I think that exposing the linked list cell type (the cons cell) as a
primitive type is too low-level.
In lisp, you can arrange cons cells in so called "improper" lists or
in circular lists. Most standard library functions will break on
those.
> Trees are very useful types of intentional storage structures. If
> you don't understand why, you need to study first-year computer
> science. Consequently, the unit cells used to build trees are
> useful types of storage structure. Now you could have a different
> type of built-in cell for each different type of tree you might
> build. But then you could build *only* the types of trees that used
> the types of cells you had available. You couldn't build *other*
> types of trees that required other types of cells, at least not by
> the same easy mechanism of simply using the built-in cells directly
> as the nodes of the trees. The alterative is not to require that
> the unit cell of a tree be a built-in (implementational) data type,
> but rather to emulate such a tree-cell using some other more
> primitive cell type. Since CONS cells are already available (per
> the previous paragraph), they might as well be used as the base for
> building tree-cells. For example, if you needed a tree-cell which
> has fields [left right depth] you could implement that as (depth .
> (left . right)), while if you needed a tree-cell which has fields
> [left right count] you could implement that as (count . (left .
> right)), and if you needed a tree-cell which has fields [left right
> count depth] you could implement that as (count . (depth . (left .
> right))), etc.
That's what user-defined structure types are for. Using conses that
way is ugly and error-prone.
> Thus having CONS cells implemented allows ordinary application/library
> programmers to implement linked lists and a wide variety of trees too.
> This allows Lisp to be used for agile development, i.e. "just do it"
> quickly without a lot of getting-started overhead.
Many dynamically typed languages allow implicit type definitions.
> Note, if you don't understand the difference between an
> implementational datatype and an intentional datatype, let me know.
> (Hint: The TYPE-OF function tells the implementational datatype.)
The more different are the implementational and the intentional
datatypes, the less typed the language is, the more errors will go
undetected.
As an extreme example consider un(i)typed languages: they will never
rise a type exception because they have just one implementational
type, but programming in these languages is difficult because the
programmer gets no help from the language in avoiding intentional type
errors.
Marco Antoniotti
> On Jun 21, 10:18 am, Marco Antoniotti <mar...@gmail.com> wrote:
>
> > ... and deep deep down, let's remember, Matemathica was built upon 'Cons' (and probably still is).
>
> Is it?
I don't know. It was for sure. The way (for you: I don't care) to find out is to look deep down at the "interface" stuff with the operating system and the communication infrastructure with other Matemathica kernels. It was there where I found out many years ago. Things may have changed, but, as I said, who cares!
Cheers
--
Marco
P. Taine
>On Jun 25, 6:31 pm, seeWebInst...@rem.intarweb.org (Robert Maas,
>http://tinyurl.com/uh3t) wrote:
>
>> Linked lists are a very useful type of intentional storage
>> structure. If you don't understand why, you need to study
>> first-year computer science. Consequently, the unit cell used to
>> build linked lists is a very useful implementational storage
>> structure. Thus it's good to have such two-part cells built into a
>> programming language.
>
>List datatypes are included in most modern languages, which usually
>offer multiple implementations (linked list and auto-resizing vector).
>I think that exposing the linked list cell type (the cons cell) as a
>primitive type is too low-level.
>
>In lisp, you can arrange cons cells in so called "improper" lists or
>in circular lists. Most standard library functions will break on
>those.
>
Certinaly not properly written ones. CL has a notation for reading and writing
both shared substructure and circular lists. It has been a long time since I
was programming, so I haven't explored the behaviour of implimentations. In the
last LISP I used, and help build all basic fuctions (EQUAL, COPY, etc.) were
perfectly happy with circularity and shared substructure, and in EQUAL had
variants, one which tested for equality under access-only operations and one
which tested for equality under updating operations.
Of course this wasn't a "common" LISP. See "Experiance with an Uncommon LISP",
reference [2] in the silver book.
A handy function for feeding constants to a MAPx operations was (and still is)
(defun lotsof (&rest l) (setf (cdr (last l)) l))
Just don''t use it for ALL the arguments!
Vend
> On Thu, 30 Jun 2011 05:54:09 -0700 (PDT), Vend <ven...@virgilio.it> wrote:
> >On Jun 25, 6:31 pm, seeWebInst...@rem.intarweb.org (Robert Maas,
> >http://tinyurl.com/uh3t) wrote:
>
> >> Linked lists are a very useful type of intentional storage
> >> structure. If you don't understand why, you need to study
> >> first-year computer science. Consequently, the unit cell used to
> >> build linked lists is a very useful implementational storage
> >> structure. Thus it's good to have such two-part cells built into a
> >> programming language.
>
> >List datatypes are included in most modern languages, which usually
> >offer multiple implementations (linked list and auto-resizing vector).
> >I think that exposing the linked list cell type (the cons cell) as a
> >primitive type is too low-level.
>
> >In lisp, you can arrange cons cells in so called "improper" lists or
> >in circular lists. Most standard library functions will break on
> >those.
>
> Certinaly not properly written ones. CL has a notation for reading and writing
> both shared substructure and circular lists. It has been a long time since I
> was programming, so I haven't explored the behaviour of implimentations. In the
> last LISP I used, and help build all basic fuctions (EQUAL, COPY, etc.) were
> perfectly happy with circularity and shared substructure, and in EQUAL had
> variants, one which tested for equality under access-only operations and one
> which tested for equality under updating operations.
If they are designed to be safe with improper and circular lists then
they need to perform extra runtime checks.
Xah Lee
enjoyable reading, even for those who hate me, but meanwhile, also
clearly exposes the varied exceeding phantasmagorical idiocies of one
Pascal J Bourguignon and Robert Mass.
however, it will take me at least 4 hours to compose such a post, and
more likely 8 hours. Instead, i happened to write rant today on HTML5,
and i dedicate this piece to Pascal & Mass exemplary tech geeking
idiots.
〈Are You Intelligence Enough to Understand HTML5?〉
xahlee.org/UnixResource_dir/writ/html5_vs_intelligence.html
------------------------------------------
Are You Intelligence Enough to Understand HTML5?
Xah Lee, 2011-07-03
--------------
Q: Are you intelligent?
Check. I have SAT score of {600/verbal, 660/math} to prove it. Was a
member of Mensa in ~1992. (I exited Mensa because i didn't want to pay
annual membership fee.)
--------------
Q: Do you have years of experience working with HTML?
Check. My website xahlee.org is 5 thousand pages of hand-crafted html,
started in 1997. More than three thousand of those pages are written,
typed, word by word, tag by tag, in a text editor. They are strictly
correct, passing W3C's HTML validator.
--------------
Q: Do you have good understanding of mathematical logic?
Check. I have studied math for over a decade, and am especially
interested in formal logic. I've written several articles about it. By
Luck, I've also done a stint as a lecturer for graduate math students
on math visualization programing. (See: Math Notations, Computer
Languages, and the “Form” in Formalism.)
--------------
Q: So, you are reading HTML5 spec — the EZ edition for web authors.
For example, there's this subsection on content models: HTML5 Content
models @ dev.w3.org. Do you understand it?
No.
--------------
Q: Do you read Slashdot, Reddit, Hacker News regularly, and you are
well acquainted with bleeding-edge practices of programing, and your
peers respectfully refer you as a hacker? You often help others with
stern advices of HTML semantics vs representation, about big O of
algorithms and Turing-complete of languages, about proper software
engineering practices such as {design patterns, unit testing, eXtreme
Programing}, and encourage others to read docs such as RFC and wisdoms
such as the unix philosophy, for a world of better software?
No, YOU are half-assed moron, the mud in a puddle, the foam in a
pisspot, the refuse in cesspit. You are a scumbag — a bag that gathers
scum, and won't stop at that.
Go shove your unit testing, your “patterns”, your UML, your eXtreme
Programing, your big O turing-complete verbiage into ya ass. Shove
your perl sigil more than one way. Pythonic your face. Unix philosophy
your pipe. Insert your lisp cons in your colon, tail recursion your
hindquarters. Roll your emacs vi command-line interface gospels in
your scrotum. Go spit your drivels in your mom's pussy. Fuck you.
That's is, “F” “U” “C” “K” “Y” “O” “U” — Fuck YOU!
Suggested Further Readings:
• HTML5 Doctype, Validation, X-UA-Compatible, and Why Do I Hate
Hackers
• HTML6: Your JSON and SXML Simplified
• Why Software Suck
• The Tech Geekers & Software Engineering
• IT Industry Predicament
• The Nature of the Unix Philosophy
Xah
Antony
> Go shove your unit testing, your “patterns”, your UML, your eXtreme
> Programing, your big O turing-complete verbiage into ya ass. Shove
> your perl sigil more than one way. Pythonic your face. Unix philosophy
> your pipe. Insert your lisp cons in your colon, tail recursion your
> hindquarters. Roll your emacs vi command-line interface gospels in
> your scrotum.
I am still LOL :)
Wonderful summary of the software engineering industry status quo :)
-Antony
PS: I think 'scrotum' is mis-spelled, should be 'scrum'