[HN Gopher] They Called It LISP for a Reason: List Processing (2... ___________________________________________________________________ They Called It LISP for a Reason: List Processing (2005) Author : susam Score : 97 points Date : 2022-10-11 12:02 UTC (2 days ago) (HTM) web link (gigamonkeys.com) (TXT) w3m dump (gigamonkeys.com) | pjmlp wrote: | It might be as it started, however since 1970 that the various | dialects support all common data structures. | WJW wrote: | 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. | tmtvl wrote: | NAND gates? | | For those who haven't checked either nandgame or nand2tetris | out, I would recommend them as fun little diversions in | boolean logic and computer architecture. | taeric wrote: | I think the point to take home here is that LISP has a rich set | of functions and building blocks around lists. Indeed, if you | have something you want to do to a list, that function probably | already exists. | | Contrasted with many other languages that are catching up, but | sometimes have surprising amount of boilerplate to process | data. | dragontamer wrote: | 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. | terminalcommand wrote: | Nah, I don't agree with this. Lisp is inherently dynamic, there | is much more going on than just automatic garbage collection. | | To achieve the same-level of expressiveness in C you need to | craft an interpreter, dynamic memory allocation doesn't cut it. | | I once wrote a simple linked list library in C to achieve lisp | like functions, things got complex very quickly. I still dream | of writing a garbage collector for it and evolve it to a lisp | like state. | | Like Greenspun said, I believe any sufficiently complicated C | or Fortran program contains an ad hoc, informally-specified, | bug-ridden, slow implementation of half of Common Lisp. | pyinstallwoes wrote: | Forth solves this. | terminalcommand wrote: | Forth is still interpreted. Forth's genius is that it's | interpreter is so tiny that it fits as a runtime. | pyinstallwoes wrote: | This is wrong. | | Because of the way pointers are used, Forth is both | compiled and not compiled. | | > After the fetch and store operations are redefined for | the code space, the compiler, assembler, etc. are | recompiled using the new definitions of fetch and store. | This effectively reuses all the code of the compiler and | interpreter. Then, the Forth system's code is compiled, | but this version is stored in the buffer. The buffer in | memory is written to disk, and ways are provided to load | it temporarily into memory for testing. When the new | version appears to work, it is written over the previous | version. | terminalcommand wrote: | What is the difference between a runtime and an | interpreter? I still believe forth is interpreted. Forth | uses a small set of functions in assembly as its | runtime/interpeter. | | Your quote looks like its about bootstrapping the Forth | ecosystem. After writing fetch and store operations in | native assembly, you can bootstrap the forth system that | is logical. This is the way Chuck Moore first used Forth | anyways. He had no interpreter/compiler back than, he | wrote some functions to aid him circumvent assembly and | make his code portable. It is genius, but I think it's | still interpreted. | | You can compile python to bytecode and run it in python's | vm, does this mean your python code is compiled. IMHO no, | it is compiled for the python vm and python vm interprets | it. Same thing applies to Forth. | | Forth is interpreted, even if you compile and package it | in a standalone executable binary. | Jtsummers wrote: | An interpreter interprets, typically either a byte code | or textual representation version of a program or some | other intermediate form (for instance, parsing to an AST | and then evaluating/interpreting that versus line-by-line | or token-by-token). A runtime could include an | interpreter, but doesn't have to. Go includes its own | runtime which handles things like scheduling goroutines | and garbage collection, but it is not interpreted nor | does it include an interpreter. | dragontamer wrote: | There are many lisps that are not interpreted, but are | instead compiled. | | The beauty of the lisp language is that it doesn't care | about interpreted vs compiled vs whatever. Its just the | true elegance of "everything is a (lisp) list" (which is | probably the wrong word. The truth of the matter is that | "everything is a graph" and lisp-lists are really just a | universal building block that can represent arbitrary | graphs). | | The important gadgets are: | | 1. Universal garbage collection (allowing you to ignore | free() issues and simplify code) | | 2. Pointer to (two pointers). That is, car-and-cdr. | | That's it. Everything else flows from these two things. | terminalcommand wrote: | That is true, but some sort of a runtime bordering on | being an interpreter needs to exist doesn't it. Because | my brain cannot comprehend how you can do metaprogramming | with macros etc. with static code. | | My opinion was that the compiled lisps precompile as much | as possible (calculations etc.) into assembly and leave | bits they can't compile intact, that's what make them | fast. | 7thaccount wrote: | Yeah. It seems to get overlooked a lot. Forth clicked for | me easier than Lisp. It still requires you to build out a | lot unless you build it on top of higher level languages. | | Great username btw. | dkarl wrote: | I think building everything out of conses held Lisp back. It | was possible, and it was deemed to be elegant, so people went | too far with it. YMMV since my adventures with Lisp were around | twenty years ago, but reading code, you'd see somebody | constructing a list with a bunch of nested lists inside it, or | some other complicated structure with conses, and you'd have no | idea what it was or how they intended to use it, and you'd just | have to read the code until you figured it out. It's much | easier to read code that uses named data structures. | | Of course in Lisp your code _can_ and _should_ have clearly | named functions that encapsulate your use of conses to build | data structures, but casually violating that encapsulation, or | better yet doing without encapsulation at all, just playing | with conses, was the cool way to do it, the way you programmed | if you had even a little bit of swagger. That was fun as long | as feeling smart about the fact that I could do it outweighed | feeling annoyed at everyone else doing it, but in the end, the | feeling of smartness faded and the feeling of annoyance | remained. | sillysaurusx wrote: | 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: return l[0] | assert car(nil) == nil assert car([]) == nil | assert car([1]) == 1 assert car([[1]]) == [1] | assert car(car([[1]])) == 1 assert car(car([(1, 2)])) == | 1 def sequence(x): return isinstance(x, | (list, tuple)) def cdr(l): if l: | if v := l[1:]: if v[0] == ".": | if sequence(l): if len(l) == 3 and | l[1] == ".": return l[2] | return v assert cdr(nil) == nil assert | cdr([]) == nil assert cdr([1]) == nil assert | cdr([1, ".", 2]) == 2 assert cdr((1, 2, 3)) == (2, 3) | assert cdr("foo") == "oo" def join(x=nil, y=nil): | if sequence(y): return [x, *y] return | [x, ".", y] assert join(nil, nil) == [nil] | assert join(1, 2) == [1, ".", 2] assert join(1, '"foo"') | == [1, ".", '"foo"'] | | Presto, now you have car, cdr, and join (cons) in Python. | | This works (and works very well). You can build lists with Lisp | and then pass them off to other Python libraries -- after all, | they're just lists. And in the rare case where you care about | mutating cons cells, you can just use a dict instead. | | EDIT: See https://news.ycombinator.com/item?id=33194570 for a | more thorough explanation of why mutable cons cells are | problematic. | reikonomusha wrote: | 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. | sillysaurusx wrote: | 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 | Turing_Machine wrote: | Python...Python...Python... | | I think I see where your problem actually is. | phoe-krk wrote: | This isn't a case of Lisp being hard to implement, this is | a case of trying to make your Lisp work with Python | language idiosyncrasies. These two issues have close to | nothing to do with one another. | lispm wrote: | > It's the heart of why Lisp is so hard to implement. | | Lisp is hard to implement? The list processing core is very | small and relatively easy to implement. | mrkeen wrote: | > 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 | taeric wrote: | Shared mutable state is an odd focus here. The point isn't that | a cons cell is some magical thing. The point is that LISP gives | you a ton of things that it already knows how to do. | | Other languages have started catching up with massive standard | libraries. But... LISP has been there for a long time. | jjtheblunt wrote: | > Shared structure is overrated. | | Every MMU running a Unix with mmap probably disagrees! | sillysaurusx wrote: | 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 of | cdr(l), how do you do it? You can just do | cdr(l)[0] = t | | Because that's the same as l[1][0] = t | | Which of course makes the list become l = | [x, [t, [z]]] | | But this sucks. It's always sucked, and Lispers go out of | their way to ignore the fact that it sucks. I wince at having | such a dismissive attitude here, but it's been the source of | _years_ of frustrations. | | It's a frustration because if Lisp had been implemented using | vectors and hash tables instead, it'd be in a far stronger | position today. Everyone uses vectors. Vectors are [1, 2, 3, | 4] ... Plain old arrays! In fact, I used vectors in the above | examples, and didn't even have to explain what they were. | Everyone knows and understands arrays. | | Lisp can work fine with vectors, _if_ you drop the | requirement of mutable cons cells. Because l becomes: | l = [x, y, z] | | And cdr(l) becomes l[1:], so cdr(l) returns [y, z] -- an | entirely new vector containing y and z. | | This might seem like nonsense, but in practice it's not. In | practice, you're rarely building lists containing hundreds of | thousands of elements. Usually it's much smaller lists | contained in other structures, like hash tables. | | And when the lists are small, you really don't care about | creating new lists. The fact that cdr(l) returns a copy of l | minus the first element is inconsequential. You'll ~never | experience a slowdown. | | And the gains are massive. You get to interface with all your | native libraries _using lisp algorithms_. You don 't have to | convert from "lisp lists" to "python lists" or "javascript | lists" or anything else. They're just arrays. | f1shy wrote: | Without having any idea of this, right now I'm facing the | problem of making a PDDL compiler (which is basically Lisp) | in C++ , and this was the way I took. Lists are just | std::vectors<std::variant>> and the variant can be a | function, number (literal) or a variable. | sillysaurusx wrote: | No way! Is the code available anywhere? I was messing | around with this idea too but didn't have the time. | That's fantastic. :) | | std::variant is really tricky, mostly because of C++'s | type system. I went with std::any. My attempt is here: ht | tps://gist.github.com/shawwn/63e0f010479efd95ebffdf210864 | 5... | | I'd love to see your code and compare notes! Mine is | pretty crummy; I'm not sure there are any worthwhile | ideas in it. Did you have much trouble with the | std::variant route? | jjtheblunt wrote: | 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) | sillysaurusx wrote: | 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 | jjtheblunt wrote: | Thanks! | cnasc wrote: | > if Lisp had been implemented using vectors and hash | tables instead | | Sounds a lot like Clojure | User23 wrote: | Lisp has had vectors and hash tables considerably longer | than Python has existed. | | It's a general purpose language, and any competent Lisper | uses the right data structure for the job. As it happens, | the cons tree (not a list, a tree!) is the right data | structure for representing Lisp code. It's not necessarily | the right data structure for representing other non-code | data that Lisp code is working with. | sillysaurusx wrote: | 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. | | It's worth considering carefully why you feel cons cells | are so important for lisp code. Nested vectors are trees. | Why not represent (define (foo x) x) | | as [define, [foo, x], x] ? | User23 wrote: | > 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.lisp.se/Body/f_map.htm | sillysaurusx wrote: | 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. | User23 wrote: | 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. | math-dev wrote: | cons is a recursive data structure. it's not discussed | much here in the comments, but a lot of its useability | comes from that fact - you can write elegant recursive | algorithms with cons as your data structure | | with vectors that doesn't work UNLESS you add a bit of | overhead (which most optimising programs may do since for | many cases vectors can be more performant) | creepycrawler wrote: | 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. | georgeoliver wrote: | One of the best programming books (for any language) ever written | IMO. Seibel has a knack for clear, readable but still technical | prose that's all too rare unfortunately. | cepher wrote: | I've been meaning to read Practical Common Lisp for some time. | Would you recommend this even for complete beginners to Lisp? | georgeoliver wrote: | Yes I would! I think it was the first complete book I read | while learning CL. | scottomyers wrote: | Practical Common Lisp is a fantastic read, but Common Lisp: A | Gentle Introduction to Symbolic Computation gets my vote as | the best book for Common Lisp beginners. Working through it | was a joy. | G3rn0ti wrote: | Two prehensile toes up! ;) | abudabi123 wrote: | I recommend the gentle introduction to Lisp book for the | complete beginner. | | The chapter on files in the Practical Common Lisp book wasn't | complete enough for me to read a one line file of 800MB which | is part of the Harvard Library Open Metadata archived set. | parenthesis wrote: | I'm assuming you mean Touretzky's _Common Lisp: A Gentle | Introduction to Symbolic Computation_ -- | | http://www.cs.cmu.edu/~dst/LispBook/index.html | | -- which, yes, is a wonderful book for a complete beginner. | f1shy wrote: | That is THE book I would recommend for beginners. | dan-robertson wrote: | I read it around 10 years ago without knowing any lisp and | got on ok. | User23 wrote: | It's a fine first book. I'd certainly recommend it. | | I don't recall if it has instructions on getting a dev env up | and running, but if it does I imagine they're out of date. | Emacs with Sly or SLIME is what I've used, but I believe | there are viable options for proper interactive development | in vim and vs code among others. | | If you just use a basic editor and paste code into a repl in | a terminal you won't be getting the experience most Lispers | do. | ducktective wrote: | 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. | johan_felisaz wrote: | I would recommend this: | https://m.youtube.com/user/CBaggers/featured | | This is a _real_ project, this guy wrote a compiler, to convert | common lisp to GLSL (I 'm not talking about a simple DSL with | code generation, but also type checking and so on). | | In his Livestreams, he usually try to implement a specific 3D | feature (like triplanar mapping, the Phong of lighting, ...). | | Everything is done in a single window, with the program being | recompiled while running, pure lisp style. | | He is on a hiatus right now though with livestreams, but there | is plenty of material already to watch ... | gaul_praham wrote: | I remember https://adeht.org/casts/new-project.html | | For larger projects I remember youtube videos for Diablo and | Minecraft clones. | cmrdporcupine wrote: | 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 < 7 | | ^ "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. | eduction wrote: | >lists are an excellent data structure for representing any kind | of heterogeneous and/or hierarchical data | | I found this a really curious statement. Linked lists made sense | given the limitations in compute when LISP was invented (~1958) | but how are vectors not a superior solution in every way, when | available? | | Vectors give you fast random access and fast append plus the same | first/next semantics and performance as lists and the same | ability to form trees. Pretty much the only thing lists are | better at is prepend (which in my experience is much less useful | than append). | | Then for truly heterogeneous data you probably want hash maps as | well, which, if you want something associative rather than | sequential, are in a class all their own. | | What am I missing? | dragontamer wrote: | Lisp lists aren't linked lists. Pointers to TWO pointers (first | pointer is named car, and the 2nd pointer is named cdr). | | The realization that (cons) / Lisp-lists / car-and-cdr give is | that you can represent arbitrary graphs (!!!) with car / cdr / | cons, leading to a truly universal data-structure. | | Not necessarily an _efficient_ datastructure mind you, but a | universal one. | | ------ | | So really, Lisp-lists are just the "try to represent your | problem as a graph" and it really works 99% of the time, | because graphs are just so flexible of a concept. | | For example, take the HTML of this webpage. <DOCTYPE> <blah | blah blah> and all that. Its pretty obvious how to convert it | into an equivalent (DOCTYPE (blah blah blah) (p) ...) kind of | structure. | | Now try to do the same with vectors and hashmaps. You can't. | You need to create a concept of vectors-of-vectors and | hashmaps-of-hashmaps with arbitrary amount of depth. | | ----------- Example HTML to think about | <div> <p> Start of a paragraph </p> <p> Second | paragraph <b> but some of it is bold</b> </p> </div> | (div (p "Start of a paragraph") (p "Second paragraph" (b " but | some of it is bold"))) | | Lisp itself is written in the form of Lisp-lists. The entirety | of your programming code _IS_ a list, proving how truly | universal this data-structure is. | | You can't convert your C code into a vector or a hash-map. It | just doesn't make sense. Meanwhile, all of lisp is a list, | including the code. | terminalcommand wrote: | In homoiconic languages like lisp I think you'd need more | flexibility than vectors. | | What if you need to remove an item for example, do you need to | shift all remaining items to keep order or mark the removed | section with Xs so that the cursor jumps to the next data item. | | You need to be able to randomly access bits and pieces to form | a network. ___________________________________________________________________ (page generated 2022-10-13 23:00 UTC)