Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Question for lisp programmers:

Lisp code is lisp data, usually lists. Is there an advantage to code being lists over code being arrays?

Would macros be easier to write/faster to run?

You can assume that, in such a language (you could call it "arrap"), elements can be deleted from or inserted into arrays and that the arrays would grow and shrink as needed.

share|improve this question
2  
By that definition, an array is merely a list, and the difference is semantics of storage. –  greyfade Jul 9 '11 at 3:52
    
voting to send to SO, since this is pretty technical –  Paul Nathan Jul 9 '11 at 18:11
1  
Please explain how an array would be different from a list? –  user1249 Jul 10 '11 at 9:43

3 Answers 3

up vote 12 down vote accepted

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.

For example, this is a simple implementation of map and fold that take one list only:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)


Also, lists can share storage, but arrays cannot. Take this Scheme code for example:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Here, hello-world has the value (hello world) and goodbye-world has the value (goodbye world).

There is one important fact, though: in many Scheme implementations, the (world) part of both lists is actually shared. This sharing would be impossible for arrays.


Addendum: To answer compman's point that recursion is somehow "non-production-grade", in Scheme, all standard looping/iteration is done using tail recursion. Here's a tail-recursive version of map1, for example:

(define (map1 f l)
  (let loop ((r '())
             (l (reverse l)))
    (if (null? l) r
        (loop (cons (f (car l)) r) (cdr l)))))

or, even more simply using left-fold1:

(define (map1 f l)
  (left-fold1 (lambda (e r) (cons (f e) r))
              '() (reverse l)))

reverse is a Scheme built-in, but its implementation is equally trivial (and also uses iteration only):

(define (reverse l)
  (left-fold1 cons '() l))
share|improve this answer
4  
It's more than that: lists are defined recursively, which is why they're easy to deal with recursively. In other words, it's a structure that is sliced in a natural way. Compare that to arrays: there, you don't deal directly with the structure -- instead, you deal with an index. It's an important difference. (And BTW, HtDP uses lists and structs extensively for this reason.) –  Eli Barzilay Jul 9 '11 at 5:01
    
@Eli: +1 for putting a finger on what I was trying to allude to with the whole "cdring down a list" thing. –  Chris Jester-Young Jul 9 '11 at 5:22
    
A library, production-grade version of <code>map</code> could use iteration. –  compman Jul 10 '11 at 0:57
1  
@compman: It could, and it's trivial to write (just pair left-fold with reverse), but it detracts from the point of my post, which is that these sorts of things can't quite as easily be done with arrays. (Just for the record: in Scheme, iteration is done using tail recursion; Scheme has no goto primitive, other than continuations, and nobody does simple looping using continuations. So a "production-grade" map still won't be using indices.) –  Chris Jester-Young Jul 10 '11 at 1:31
1  
I wish we could mark favorite answers. –  Mark C Jul 29 '11 at 4:26

Insertion itself is O(1) at the beginning of the list.

(cons x '(world))

Inserts "x" at the beginning of the list containing world. If you have an array and you want to insert an element at the beginning, you have to shift everything over by one. Not so with lists!

share|improve this answer
1  
You'd have to create a new array and copy all the elements anyway, if you want to stay faithful to side-effect-free programming, because arrays cannot share structure. So "shifting everything over by one" is a bit of a red herring. :-) –  Chris Jester-Young Jul 9 '11 at 4:41
    
I'm also going to unofficially "accept" this answer as well. –  compman Aug 6 '11 at 23:47

Some lisps used to use a technique known as CDR coding fro list representation. This, essentially, replaces the CDR-half of the cell with the contents of the pointed-to cell, allowing you to represent a list with what's effectively an array of CAR pointers, while preserving list semantics (you can have part of a list CDR coded, share CDR-coded tails and other things that normal lists can handle)

However, efficient implementation of CDR coding requires hardware support, so it (as far as I understand) pretty much went out with dedicated Lisp machines.

As far as lisp-the-language-family is concerned, no, I don't think macros would be easier to write. At best, I think it would be no harder to write macros.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.