Live data from Hacker News

They Called It LISP for a Reason: List Processing (2005)

gigamonkeys.com

31–40 of 125 posts

Re: They Called It LISP for a Reason: List Processing (2005)

#31

Earlier quoted context omitted.

> Shared structure is overrated. Every MMU running a Unix with mmap probably disagrees!

You're right, I was imprecise. I meant specifically shared list structure in Lisp contexts, not shared structures in general. There's a fascination in the Lisp world for cons cells. Specifically the cell aspect. If you represent lists as: l = [x, [y, [z]]] Then you can implement car as l[0] and cdr as l[1]. If you require mutable cons cells, that's pretty much the only way to do it. Because if you want to set the car…

It seems you're suggesting making CDR into an O(N) operation. So for example ordinary list processing algorithms that take O(N) will now be O(N^2).

Anyway, these kind of weird arguments from people who don't get it have been proposed and shot down a million times before, and I'm not sure there's any value reiterating. I suggest anyone interested in Lisp (or any programming language, really) ignore weird HN critiques and just read a book, like the one linked here.

Re: They Called It LISP for a Reason: List Processing (2005)

#32
post #20

Earlier quoted context omitted.

> Yes, but cdr(vector(1, 2, 3)) throws an error in almost all lisp implementations. Which means you can’t use the classic algorithms on them, like map. What? MAP[1] works just fine with vectors and other sequence types. Are you somehow surprised that MAPCAR doesn't? The name makes it pretty obvious I'd think. I'm starting to think you just lack familiarity with the language that you're criticizing. [1] http://clhs.li…

Suppose Lisp were forced to abandon cons cells and could only use vectors to represent code. What's the disadvantage? My retort to you would be "I'm starting to think you like complexity for the sake of it," but debates are much more fun when we're both genuinely interested in the other's perspective.

Variable length vectors are observably more complex than 2-tuples. And forgive me, but you are giving me the impression that you are trolling rather than debating.

Suppose Lisp were forced to abandon cons cells and could only use SQL tables to represent code. What's the disadvantage?

Anyhow, by all means write your Python vector based Lisp dialect. It's no skin off my teeth. Maybe it really is superior and you'll be the next Rich Hickey.

Re: They Called It LISP for a Reason: List Processing (2005)

#33
post #21

It might be as it started, however since 1970 that the various dialects support all common data structures.

I wonder what the minimal set of data structures is that you can build all others out of. For example binary trees can be built with lists, SEXPs are proof of that. You can of course also make a (boxed) linked list out of an array of 2 pointers, with one element pointing to the value and the other to the next element. You can make arrays with just pointer arithmetic, sooooo... just pointers is enough? (I guess this can also be shown from the "other" direction, by pointing out that assembly has nothing but arithmetic and pointers)

You would also need various arithmetic operations, possibly up to hashing algorithms for hash tables/sets/bloom filters/etc. I would love to know if anyone can point me to an article or something describing the minimal set of operations needed to construct any data structure.

Re: They Called It LISP for a Reason: List Processing (2005)

#34
Can anyone link a screencast of doing Common Lisp with all its cool interactive features? (REPL-driven, SLY/SLIME, restarts, etc) and I mean doing real small projects not just simply touting how cool lisp is or talking about (+ 2 3) and C-c C-c

I tried searching on YouTube but didn't find anything particularly unique.

Re: They Called It LISP for a Reason: List Processing (2005)

#35

Can anyone link a screencast of doing Common Lisp with all its cool interactive features? (REPL-driven, SLY/SLIME, restarts, etc) and I mean doing real small projects not just simply touting how cool lisp is or talking about (+ 2 3) and C-c C-c I tried searching on YouTube but didn't find anything particularly unique.

I remember https://adeht.org/casts/new-project.html

For larger projects I remember youtube videos for Diablo and Minecraft clones.

Re: They Called It LISP for a Reason: List Processing (2005)

#36
The real elegance of Lisp is that malloc() has been renamed to (cons) and everyone feels smarter about it.

I jest a little bit, but that's really the fundamental thing about list-processing. For most code, you don't really care about runtime, and you really just need "a data structure that probably can solve the problem", and the (cons) based list of car and cdr solves it.

List processing itself is an elegant technique: a garbage collector tuned for exactly (cons) (2-element "items" that have a car-and-cdr, and the cdr is usually a pointer to another cons), is small, simple, elegant to implement, and works for almost any problem imaginable.

Maybe not as fast as a properly designed specific data-structure, but it will work. On top of that, Lisp has all kinds of shortcuts to make list processing easier to type.

---------

Getting a basic implementation of whatever project you're doing in cars-and-cdrs in (cons) is more important anyway for learning about your problem. Choosing a data-structure too early can hamper your understanding and bias you towards a possibly inefficient solution.

Knuth tries to explain the topic in his "binary trees representation of trees" subject, and notes that pointers to (two pointers) elegantly solves a wide variety of problems. Whether you wanna see them as binary trees, Lisp-lists, or graphs or even collections of malloc'd() nodes, it doesn't really matter. Its the flexibility of this data-structure that is incredible.

EX: the "left" child is "down a level", and the "right" child is "next sibling". Therefore, binary trees can represent any tree, and if allowed to loop, I'm sure the cons / binary tree node can be forced into working with graphs.

Re: They Called It LISP for a Reason: List Processing (2005)

#37

Shared structure is overrated. The cases where you need a tree-like mutable structure are vanishingly small in modern times. Mostly it boils down to "just use hash tables." This isn't just a dismissive observation. It's the heart of why Lisp is so hard to implement. When I ignored mutable cons cells, I realized I could just implement bel in Python by using actual Python lists. t = True nil = None def car(l): if l: re…

> Shared structure is overrated. The cases where you need a tree-like mutable structure are vanishingly small in modern times. Mostly it boils down to "just use hash tables."

So confused by this. Shared, tree-like, and mutable seem pretty orthogonal to me.

Sure, I'll forgo mutable structure. And since I don't mutate, I can safely share structure. But I don't want O(n) update operations, so I'd better make my hash tables use a tree-shaped data structure:

https://en.wikipedia.org/wiki/Hash_array_mapped_trie

Re: They Called It LISP for a Reason: List Processing (2005)

#38

Earlier quoted context omitted.

I fail to see why mutable cons cells has anything to do with the difficulty of implementing Lisp. @dataclass class Cons: car: Any cdr: Any You can define a nice printer or reader for it if you want, but mutability doesn't seem to be a hindrance in implementation.

You can, but then none of the Python libraries that expect Python lists can use your Cons as a list. I tried. It sucks. The conversion becomes a problem all over the place. isinstance(Cons(nil, nil), list) will fail, for example. I posted a more thorough answer here: https://news.ycombinator.com/item?id=33194570

Python...Python...Python...

I think I see where your problem actually is.

Re: They Called It LISP for a Reason: List Processing (2005)

#39

Earlier quoted context omitted.

Great write-up (and that's from someone first doing Lisp in 1987, then lots of Scheme and tons of Mathematica, as well as all the compiled things)

Incidentally, it wasn’t my idea. It was Scott Bell’s. I’m not sure if he thought of it or got it from somewhere else, but it’s wonderfully effective. If you want to try it out for yourself, give Lumen a spin: https://github.com/sctb/lumen His Postgres FFI is the prettiest lisp FFI you’ll ever see. https://github.com/sctb/motor/blob/master/pq.l

Thanks!

Re: They Called It LISP for a Reason: List Processing (2005)

#40
Yes, this is the lovely elegance that comes out of building out of a nice re-composable underlying concept. I still find it hard all these years later to fully wrap my head around building programs in this style, but I adore the fact that it exists.

FWIW I feel like RelationalAI, in their "Rel" language, has done for n-ary (database) relations what Lisp&Scheme did for lists. Something I had pondered myself for years and kind of grasped at but never really got, and I think they've done it. It's really quite elegant, worth checking out:

https://docs.relational.ai/rel/intro/overview

E.g.

"The constants true and false are also relations, of arity 0. There are only two of these: false is {} (the empty relation with arity 0), and true is {()}, that is, the relation with one empty tuple (arity 0 and cardinality 1)."

and

"In Rel, a single elements is identified with a relation of arity 1 and cardinality 1. For example, the number 7 is the same as the relation {(7)}"

This lets them do clever things like use relational cross-product ("," operator) kind of like Lisp's `cons` to build tuples, so:

  (1, 2, 3) 
builds the relation

  {(1,2,3)} from {(1)}, {(2)}, {(3)}. 
And also the same operator can be used for filtering because "false" and "true" likewise evaluate to relations, so crossproducting them acts like a "where" clause, so:

  def myelements = 1; 2; 3; 4; 5; 6; 7; 8; 9
  def output(x) = myelements(x), x > 3, x 
^ "filters" myelements to return the values in the relation that are greater than 3 and less than 7.

And it also works as a pure cross-product operator, of course, for when you need that.

It's the same kind of elegant composability you get from Lisp, but with a maybe semantically richer datatype and a richer set of (relational algebraic) operations.

Post reply on HN