3 ms·

OK, I'll jeer: I'm a big fan of [McCarthy60], but everything-is-a-list implicitly introduces order, and the 21st century ought to explicitly accommodate the uno

OK, I'll jeer: I'm a big fan of [McCarthy60], but everything-is-a-list implicitly introduces order, and the 21st century ought to explicitly accommodate the unordered as well. (there ought not be any is-more-basic-than relation between ordered and unordered)

sillysaurusx 3y ago
I agree! That’s actually not a jeer, it’s one of my main criticisms of lisp. You don’t need lists to have lisp. In many respects it works better without them; https://github.com/sctb/lumen https://github.com/sctb/lumen proves it, since hash tables and arrays are the fundamental data structure. They have to be, because that’s the only way lumen can run in JS or Lua. Every time I can’t delete the first element of a list in lisp (I.e. del x[0] in the python sense) I get annoyed with racket. The reason I look past it is because the benefits are so good that they outweigh the annoyances. I wouldn’t trade it away.
- deleted 3y ago
  [deleted]
- cess11 3y ago
  Or do you specifically mean that you want to free memory where the first cell is without waiting for GC or similar? $ pil + : (cdr '(1 2 3)) -> (2 3) :
  - sillysaurusx 3y ago
    Answered in a sibling comment just now: https://news.ycombinator.com/item?id=39815471 https://news.ycombinator.com/item?id=39815471 (Sorry for not being clearer to begin with. I realized as I was falling asleep that it would cause some confusion.)
- zelphirkalt 3y ago
  Insisting on a single linked lists as the fundamental data structure is not necessary, that much I agree, but I would say, if you need del x[5], then in some cases you should not be using a list, but potentially a persistent data structure/PFD. This is an area that Lisps should invest in: Batteries included for good functional data structures.
- eggy 3y ago
  Try April (Array Programming Reimagined In Lisp)[0] then. Sorry, I am both an array language and Lisp fan for many years. You use Lisp for all of its goodness, and drop into APL to do numerics and array work in a language better suited for the problem at hand. Hmm, maybe a marriage between Gerbil and J -> Jerbil! I've been a fan of Gambit for a long time too. Love to see it being utilized this way. [0] https://github.com/phantomics/april https://github.com/phantomics/april
- jimbokun 3y ago
  What is the case where you would prefer “del x[0]” over “cdr”? Isn’t this just the difference between mutable and persistent data structures?
  - sillysaurusx 3y ago
    x = [42, 99] y = x del x[0] y[0] ; 99 This is impossible in traditional Lisp, and it’s the source of many of my frustrations. It’s why you can write an algorithm to destructively modify a list at any point — except index zero. The head of the list is the thing that’s used as a reference to the list. This doesn’t happen in Python; it’s why you can have empty arrays set to x and y, push a value onto x, and see it at y.
    - tonyg 3y ago
      (define (snip! x) (set-car! x (cadr x)) (set-cdr! x (cddr x)) x) ?
      - tmtvl 3y ago
        Won't work, errors on a single-element list. I think the solution would be the same as it is in CL: to just use vectors.
    - cess11 3y ago
      Pretty sure you can do this in CL but I'm short on time so I'm not going to figure it out right now. Most of the time I try to get rid of variable names so it seems somewhat strange to invent more than one pointing to the same data structure in RAM, but I'm a simple person that gets confused easily.
      - tmtvl 3y ago
        With adjustable arrays it's easy: (defun vector-delete! (vector index) "Delete the element at INDEX from the given VECTOR. Destructively modifies the vector. The vector must have a fill-pointer. This is not thread-safe, use at your own risk. Examples: (let* ((x (make-array 4 :fill-pointer 4 :initial-contents '(1 2 3 4))) (y x)) (vector-delete! x 0) y) ;; => #(2 3 4)" (declare (type (Integer 0 *) index) (type Vector vector)) (assert (array-has-fill-pointer-p vector)) (let ((l (length vector))) (assert (< index l)) (let ((removed-element (aref vector index))) (loop :for i :from (1+ index) :below l :do (setf (aref vector (1- i)) (aref vector i))) (decf (fill-pointer vector)) removed-element))) (Granted, it could be done in 6 lines of code, but I'm already cringing at not providing a continuation when calling it with an out-of-bounds index)
- chubot 3y ago
  How do you prevent common Lisp idioms from being quadratic in that case? I noticed this about Norvig's toy Lispy: https://norvig.com/lispy.html https://norvig.com/lispy.html It implements cdr as mylist[1:] So if you recurse on a list with cdr, then you will get mylist[1:] mylist[2:] ... mylist[n:], which is a quadratic algortihm
sph 3y ago
This is actually very good insight that makes me pause and ponder about its implications. Do you know any in depth research/paper on this topic? Ordered data types are core to computers actually: arrays, heck even the memory itself. I always thought the list to be the most fundamental construct, but outside the neat world of computer, the real world is mostly unordered. Order is artificial, is indeed often not a given.
- lou1306 3y ago
  > Ordered data types are core to computers actually: arrays, heck even the memory itself Has this been actually true in the last, say, two decades? Or is just a thin veneer to make your highly concurrent machine look like a PDP-11? Right now order seems to be somewhat important only when it comes to cache optimization: if you stick thing that belong together close to each other you end up with fewer cache misses.
  - brabel 3y ago
    For performance, you really want to have cache locality, which means storing data in contiguous regions of memory, which is what an array does.
    - cmrdporcupine 3y ago
      I mean, within 4k (or 1MB I guess if bigpages) pages, sure. But my understanding is that the OS & VMM & TLB aren't going to guarantee anything about physical address continuity -- even if the virtual addresses are contiguous -- are they?

sillysaurusx 3y ago

I agree! That’s actually not a jeer, it’s one of my main criticisms of lisp. You don’t need lists to have lisp. In many respects it works better without them; https://github.com/sctb/lumen https://github.com/sctb/lumen proves it, since hash tables and arrays are the fundamental data structure. They have to be, because that’s the only way lumen can run in JS or Lua. Every time I can’t delete the first element of a list in lisp (I.e. del x[0] in the python sense) I get annoyed with racket. The reason I look past it is because the benefits are so good that they outweigh the annoyances. I wouldn’t trade it away.

deleted 3y ago
[deleted]
cess11 3y ago
Or do you specifically mean that you want to free memory where the first cell is without waiting for GC or similar? $ pil + : (cdr '(1 2 3)) -> (2 3) :
- sillysaurusx 3y ago
  Answered in a sibling comment just now: https://news.ycombinator.com/item?id=39815471 https://news.ycombinator.com/item?id=39815471 (Sorry for not being clearer to begin with. I realized as I was falling asleep that it would cause some confusion.)
zelphirkalt 3y ago
Insisting on a single linked lists as the fundamental data structure is not necessary, that much I agree, but I would say, if you need del x[5], then in some cases you should not be using a list, but potentially a persistent data structure/PFD. This is an area that Lisps should invest in: Batteries included for good functional data structures.
eggy 3y ago
Try April (Array Programming Reimagined In Lisp)[0] then. Sorry, I am both an array language and Lisp fan for many years. You use Lisp for all of its goodness, and drop into APL to do numerics and array work in a language better suited for the problem at hand. Hmm, maybe a marriage between Gerbil and J -> Jerbil! I've been a fan of Gambit for a long time too. Love to see it being utilized this way. [0] https://github.com/phantomics/april https://github.com/phantomics/april
jimbokun 3y ago
What is the case where you would prefer “del x[0]” over “cdr”? Isn’t this just the difference between mutable and persistent data structures?
- sillysaurusx 3y ago
  x = [42, 99] y = x del x[0] y[0] ; 99 This is impossible in traditional Lisp, and it’s the source of many of my frustrations. It’s why you can write an algorithm to destructively modify a list at any point — except index zero. The head of the list is the thing that’s used as a reference to the list. This doesn’t happen in Python; it’s why you can have empty arrays set to x and y, push a value onto x, and see it at y.
  - tonyg 3y ago
    (define (snip! x) (set-car! x (cadr x)) (set-cdr! x (cddr x)) x) ?
    - tmtvl 3y ago
      Won't work, errors on a single-element list. I think the solution would be the same as it is in CL: to just use vectors.
  - cess11 3y ago
    Pretty sure you can do this in CL but I'm short on time so I'm not going to figure it out right now. Most of the time I try to get rid of variable names so it seems somewhat strange to invent more than one pointing to the same data structure in RAM, but I'm a simple person that gets confused easily.
    - tmtvl 3y ago
      With adjustable arrays it's easy: (defun vector-delete! (vector index) "Delete the element at INDEX from the given VECTOR. Destructively modifies the vector. The vector must have a fill-pointer. This is not thread-safe, use at your own risk. Examples: (let* ((x (make-array 4 :fill-pointer 4 :initial-contents '(1 2 3 4))) (y x)) (vector-delete! x 0) y) ;; => #(2 3 4)" (declare (type (Integer 0 *) index) (type Vector vector)) (assert (array-has-fill-pointer-p vector)) (let ((l (length vector))) (assert (< index l)) (let ((removed-element (aref vector index))) (loop :for i :from (1+ index) :below l :do (setf (aref vector (1- i)) (aref vector i))) (decf (fill-pointer vector)) removed-element))) (Granted, it could be done in 6 lines of code, but I'm already cringing at not providing a continuation when calling it with an out-of-bounds index)
chubot 3y ago
How do you prevent common Lisp idioms from being quadratic in that case? I noticed this about Norvig's toy Lispy: https://norvig.com/lispy.html https://norvig.com/lispy.html It implements cdr as mylist[1:] So if you recurse on a list with cdr, then you will get mylist[1:] mylist[2:] ... mylist[n:], which is a quadratic algortihm

sph 3y ago

This is actually very good insight that makes me pause and ponder about its implications. Do you know any in depth research/paper on this topic? Ordered data types are core to computers actually: arrays, heck even the memory itself. I always thought the list to be the most fundamental construct, but outside the neat world of computer, the real world is mostly unordered. Order is artificial, is indeed often not a given.

lou1306 3y ago
> Ordered data types are core to computers actually: arrays, heck even the memory itself Has this been actually true in the last, say, two decades? Or is just a thin veneer to make your highly concurrent machine look like a PDP-11? Right now order seems to be somewhat important only when it comes to cache optimization: if you stick thing that belong together close to each other you end up with fewer cache misses.
- brabel 3y ago
  For performance, you really want to have cache locality, which means storing data in contiguous regions of memory, which is what an array does.
  - cmrdporcupine 3y ago
    I mean, within 4k (or 1MB I guess if bigpages) pages, sure. But my understanding is that the OS & VMM & TLB aren't going to guarantee anything about physical address continuity -- even if the virtual addresses are contiguous -- are they?