Arc Forumnew | comments | leaders | submitlogin
4 points by shader 2521 days ago | link | parent

Here's a rather radical question: Why do lists need to be nil terminated at all? Why couldn't we have the normal (a b) notation mean (a . b), and (a b c) mean (a . (b . c)), etc. Then redefine 'car and 'cdr so that they handle atoms: car of atom is itself, and cdr of atom is nil. That way car and cdr never fail on atoms, and map etc. still terminate properly on lists.

The only bad side effect would be lack of explicit rest args; all functions would by default have a rest arg. However, since lists are no longer specially terminated, the last arg wouldn't necessarily be wrapped in a list if the function was called with the proper number of args.

I know I'm questioning half a century of lisp convention; what painfully obvious flaw am I missing here?



2 points by rocketnia 2521 days ago | link

I've actually heard that suggestion before, somewhere. * searches for it*

Oh, it's a misinterpretation I had of something on the newLISP page:

http://www.newlisp.org/index.cgi?page=Differences_to_Other_L...

  ;; Common Lisp and Scheme
  (cons 'a 'b) => (a . b)   ; a dotted pair
  
  [a | b]
  
  ;; newLISP
  (cons 'a 'b) => (a b)     ; a list
  
  [ ]
   \ 
   [a] -> [b]
Now that I read it again, it's totally not referring to the notation. What it means is most clearly stated at http://www.newlisp.org/downloads/newlisp_manual.html#nil_and...:

The cons of two atoms in newLISP does not yield a dotted pair, but rather a two-element list. [...] There is no dotted pair in newLISP because the cdr (tail) part of a Lisp cell always points to another Lisp cell and never to a basic data type, such as a number or a symbol.

So it's just a matter of not having programmer-managed cons cells. Nothing to see here....

---

Back to your idea, what happens if you have the syntax (a b c (d e f))? Isn't that indistinguishable from (a b c d e f)? Would alists have to be explicitly written as ((a 1) (b 2) (c 3) nil)?

-----

1 point by shader 2521 days ago | link

Good question.

I suppose that a list at the end of a list would have to be paired with nil, so (a b c (d e f)) would actually be the list (a b c (d e f) nil), but that should be possible to handle at the reader/'list level, and wouldn't make much of a difference in the use of the code. If that simple change is made, then your alist example shouldn't need to be explicitly terminated.

-----

1 point by akkartik 2521 days ago | link

If we're relying on reader magic, what's the benefit of making atoms rather than lists nil-terminated?

It seems kinda futzy for the last element to be nil sometimes but not others.

-----

1 point by shader 2521 days ago | link

Yes, it does seem kind of fuzzy. And I doubt it would actually be the reader doing that, more likely the 'list function would be the source for the extra nils

However, you need some way to distinguish between a list in the car, and the next element in a chain. The only way to do that is to have it be in the car of a cons cell, and the only way to do that is to have something else in the cdr. If you don't have anything after the list, you have to fill it with nil.

-----

5 points by rocketnia 2521 days ago | link

The only way to do that is to have it be in the car...

Actually, you could have a special symbol '! in the car in order to identify that the cdr is actually supposed to be the last element. Then (a b c (d e f)) is represented as (a . (b . (c . (! . (d . (e . f)))))), i.e. (a b c ! d e f). Banged lists. ;)

In fact, having the symbol be a colon might even make it a nice optional style:

  (accum acc
    (each x args
      (acc (* 2 x))))
  
  (accum acc :
     each x args :
       acc : * 2 x)    ; reminiscent of Arc's (acc:* 2 x)
It's just that you never get to observe the ': from within code. There might be gotchas when generating code, too: The expression (quote : ) would evaluate to nil, huh? XD

-----

3 points by evanrmurphy 2521 days ago | link

Dear rocketnia,

Some of your ideas are very bizarre. I mean this as a compliment. Please keep 'em coming. :)

Regards, evanrmurphy

-----

3 points by akkartik 2521 days ago | link

Scheme flags an error on car/cdr of nil. Common lisp doesn't. Now you're suggesting doing this for all atoms. I like this because it loosens another constraint I hadn't even noticed. (http://arclanguage.org/item?id=13414)

-----

2 points by shader 2517 days ago | link

I think in the end just extending car/cdr to support atoms would still be useful, but changing lists to being nil terminated only some of the time would likely be too inconsistent and/or buggy to risk. It would save some space, but on the whole doesn't really improve much.

-----

3 points by evanrmurphy 2521 days ago | link

Very interesting and radical indeed! ^_^

This is reminiscent of a comment at the bottom of arc.arc:

  ; solution to the "problem" of improper lists: allow any atom as a list
  ;  terminator, not just nil.  means list recursion should terminate on 
  ;  atom rather than nil, (def empty (x) (or (atom x) (is x "")))
It also reminds me of a feature in PicoLisp: symbols evaluate to nil by default instead of raising an undefined variable error.

-----