Arc Forumnew | comments | leaders | submitlogin
3 points by map 6109 days ago | link | parent

--- quote

Can I do (push obj lst 2)? (push obj lst -4)?

--- /quote

Yes, NewLisp:

  > (set 'x '(2 4 6))
  (2 4 6)
  > (push 3 x 1)
  3
  > x
  (2 3 4 6)
  > (push 5 x -2)
  5
  > x
  (2 3 4 5 6)
The next test indicates that appending to the end of a list is just as fast as pushing to the beginning of a list (times are in milliseconds).

Add at the beginning of the list:

  > (set 'x '(2))
  (2)
  > (time (push 8 x) 99000)
  40
  > (x 0)
  8
  > (x -1)
  2
Add at the end of the list:

  > (set 'x '(2))
  (2)
  > (time (push 8 x -1) 99000)
  40
  > (x -1)
  8
  > (length x)
  99001
Don't ask me how Lutz did it. (Maybe he keeps a pointer to the end of the list?) I think that lists in NewLisp aren't quite the same as lists in Common Lisp. Lutz wrote:

The concept of a 'cons cell' is about details of early LISP implementations (CPU registers, etc). newLISP also has a basic cell structure which can be linked to a list but has no concept of a dotted pair. When have you last seen a dotted pair used in a real world program? newLISP has 'cons' but it works differently,

By the way, it would be nice if Arc let you get the last element with -1, as NewLisp does:

  arc> ('(2 3 4) -1)
  Error: "list-ref: expects type <non-negative exact
  integer> as 2nd argument, given: -1;
  other arguments were: (2 3 4 . nil)"


2 points by absz 6108 days ago | link

Huh. That (in my humble opinion) is a terribly misnamed function (push already has a specific meaning; what about ins, for insert, which is what it actually does?), but certainly a very useful one.

I'd be curious to see what (time (push 8 x 4)) looks like: is that also constant-time? What sort of data structure is newLISP using, if not a linked list? Linked list + end pointer, perhaps--but wouldn't that break on a push? Ah well. I (unfortunately) don't really have time to construct an in-depth analysis, but I'm still curious.

I'm not sure why the Anarki won't let you do ('(2 3 4) -1); it would indeed be useful. Mayhap there are efficiency concerns? Negative indexing works in cut.

-----

3 points by map 6108 days ago | link

In Ruby, push appends to a list; unshift prepends:

  E:\>irb --prompt xmp
  lst = [3,4,5]
      ==>[3, 4, 5]
  lst.push( 6 )
      ==>[3, 4, 5, 6]
  lst.unshift( 2 )
      ==>[2, 3, 4, 5, 6]
  lst.pop
      ==>6
  lst.shift
      ==>2
  lst
      ==>[3, 4, 5]
  lst << 6
      ==>[3, 4, 5, 6]
  lst += [7]
      ==>[3, 4, 5, 6, 7]
  lst
      ==>[3, 4, 5, 6, 7]
NewLisp can insert in the midst of the list just as fast.

  > (set 'x '(0 1 2 3 4 5 6))
  (0 1 2 3 4 5 6)
  > (time (push 8 x 4) 99000)
  50
  > (set 'x '(0 1 2 3 4 5 6))
  (0 1 2 3 4 5 6)
  > (time (push 8 x 4) 99000)
  40
  > (set 'x '(2))
  (2)
  > (time (push 8 x) 99000)
  40
Ruby has the opposite problem from conventional Lisp: it appends quickly, but prepends slowly:

  t = Time.now; a=[2]; 99_000.times{ a.push( 8 ) }; p Time.now - t
  0.14
      ==>nil
  t = Time.now; a=[2]; 99_000.times{ a.unshift( 8 ) }; p Time.now - t
  70.902
      ==>nil
  t = Time.now; a=[0,1,2,3,4]; 99_000.times{ a.insert(2, 8) }; p Time.now - t
  73.346
That's 73 seconds! NewLisp can insert in a list 1800 times as fast as Ruby can!

-----

1 point by absz 6108 days ago | link

Right. In Ruby, pushing, unshifting, and spliceing are all different operations, as they should be. Meaningful names are important.

It's not quite as fast to insert in the middle, but much faster than it should be. This would, to me, imply that newLISP isn't even using linked lists at all, but is instead using some form of array, which is decidedly unLispy. If that is the case (if, I say), then of course this will only work with "one reference only", as you can't construct lists which share cdrs; "one reference only" being an awful idea, I would consider the speed a fair tradeoff.

-----