11 ms·

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

115 points by susam 4y ago

georgeoliver 4y ago
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 4y ago
  I’ve been meaning to read Practical Common Lisp for some time. Would you recommend this even for complete beginners to Lisp?
  - f1shy 4y ago
    That is THE book I would recommend for beginners.
  - User23 4y ago
    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.
  - georgeoliver 4y ago
    Yes I would! I think it was the first complete book I read while learning CL.
  - abudabi123 4y ago
    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 4y ago
      I'm assuming you mean Touretzky's Common Lisp: A Gentle Introduction to Symbolic Computation — http://www.cs.cmu.edu/~dst/LispBook/index.html http://www.cs.cmu.edu/~dst/LispBook/index.html — which, yes, is a wonderful book for a complete beginner.
  - dan-robertson 4y ago
    I read it around 10 years ago without knowing any lisp and got on ok.
  - G3rn0ti 4y ago
    Two prehensile toes up! ;)
  - scottomyers 4y ago
    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.
sillysaurusx 4y ago
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 https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.
- jjtheblunt 4y ago
  > Shared structure is overrated. Every MMU running a Unix with mmap probably disagrees!
  - sillysaurusx 4y ago
    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.
pjmlp 4y ago
It might be as it started, however since 1970 that the various dialects support all common data structures.
- taeric 4y ago
  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.
- WJW 4y ago
  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 4y ago
    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.
  - openfuture 4y ago
    Maybe I am starting to spam the thread a bit here but I think the answer is canonical S-expressions, but proving that to be the case is more tricky than it looks although it is also kinda obvious from the surface level; vectors in s-expressions. But yeah the real answer is lambda calculus, see lambda lisp and justine.lol
ducktective 4y ago
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.
- gaul_praham 4y ago
  I remember https://adeht.org/casts/new-project.html https://adeht.org/casts/new-project.html For larger projects I remember youtube videos for Diablo and Minecraft clones.
- johan_felisaz 4y ago
  I would recommend this: https://m.youtube.com/user/CBaggers/featured 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 ...
dragontamer 4y ago
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 4y ago
  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 4y ago
cmrdporcupine 4y ago
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 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.
- openfuture 4y ago
  Very interesting! thanks for this. The n-ary relations are bipartite graphs, one partition in the graph is the relations (hyperedges). This is /the/ universal (turing machine) theorem of computing. By the way, check out datalisp.is, I think we should re-encode the web :)
eduction 4y ago
>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?
- terminalcommand 4y ago
  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.
  - openfuture 4y ago
    Forth is also homoiconic (arguably more so than lisp) and it can be thought of as being purely vectors.
    - terminalcommand 4y ago
      Forth's homoiconicity seems to be disputed: https://wiki.c2.com/?HomoiconicityClassification https://wiki.c2.com/?HomoiconicityClassification
      - openfuture 4y ago
        You could see forth as just netstrings recursively. You evaluate the outermost netstring by unquoting and then doing a forth over the netstrings it contains.
kragen 4y ago
I'm seeing a lot of people sort of dismissing the usefulness of lists without really understanding why Lisp is important: aren't vectors and hash maps better? Isn't CONS just malloc()? Doesn't Forth solve the problem that low-level languages like C are inflexible? — ⁂ — The first thing to understand is that Lisp invented functional programming. (Seibel's chapter mentions this, of course.) The functional-programming approach is to define your procedures recursively rather than iteratively; this began in Lisp but is now central to a number of other languages, like Haskell, OCaml, and F#. For certain fields, like symbolic algebra and compilers, this approach makes many difficult problems trivial. Even outside those fields, pervasive immutability often has many benefits, eliminating large classes of bugs, greatly simplifying problems like undo and thread-safety, and dramatically reducing the runtime cost of garbage collection. However, recursively defined linked data structures tend to use more space, and they're not very cache-friendly, and sometimes those are more important considerations. To define your procedures recursively, it's very helpful to define your data types recursively. Recursively-defined lists (for example, "a list of Ts is either the empty list of Ts or a T followed by a list of Ts") support this recursive, immutable approach to programming. Other kinds of recursive structures do, too; Haskell and ML dialects tend to use application-specific sum types at least as much as general-purpose lists, and I like that style better. It has most of the same advantages and disadvantages. STL-style vectors do not support a recursive style of programming. They support an iterative, imperative approach to programming. If you use that other approach to programming exclusively, you will not understand why anyone would want to primarily use linked lists. And occasionally you will be confronted with problems that are very difficult for you to solve, problems which would have been trivial with a recursive approach, and you will not realize that you are doing a hundred times more work to solve them than you need to. SICP is full of examples. — ⁂ — The second thing about Lisp is that it has orthogonal serialization and deserialization: PRINT and READ. This mechanism is sometimes, though not always, adequate for debug logging, saving and loading application state, configuration files, and networking. Modern Lisps like Clojure generally extend those to arbitrary data structures, not just lists and atoms, but it's especially easy to implement if you only have lists and atoms; it's about 30 lines of Forth, for example¹. This is of course not unique to Lisp anymore; Java, Python, Tcl, Golang, and many other languages have ways to do it. Orthogonal deserialization of lists is not really an optional extra, since you use it to parse Lisp programs, too. And you need the serialization to print lists in the REPL, anyway. — ⁂ — The third thing about Lisp is that it supports metaprogramming very well. This takes lots of forms; compile-time macros are a common one, and they give you enormous flexibility to extend Lisps into domain-specific languages, though they're probably used even more often to hack around inadequately optimized compilers. EVAL answers many requirements for runtime flexibility, though there are times when it is too powerful. As with serialization and deserialization, these metaprogramming facilities mostly just fall out of the Lisp design; they require minimal or no extra code in a Lisp interpreter. — ⁂ — Historically speaking Lisp had a lot of other advantages: for a long time it was the only garbage-collected language, the only dynamically-typed language, the only language with EVAL, the only language with higher-order functions, and so on, and so for many years it was by far the best language for the things that you would do in JS, Python, Ruby, Lua, or OCaml today. JS, Python, Ruby, Lua, and OCaml are better for some of those things, and for many purposes they adequately support the functional, recursive, immutable approach to programming that Lisp pioneered. Still, it might be easier to learn it in Lisp. — ⁂ — Lisp is sort of a minimal core of functional programming. In a decent low-level language like C or Forth, you can build a Lisp with an interactive functional programming environment with dynamic typing, orthogonal serialization and deserialization, an interactive interpreter, garbage collection, and extensive metaprogramming capabilities, in under 1000 lines of code, and the only data structure you need to do it is cons. (It's not quite as simple as you might think from reading the "Maxwell's Equations of Software" in the Lisp 1.5 manual; those gloss over READ, PRINT, decimal conversion, arithmetic, symbol interning, the garbage collector, and user interaction, so you end up with significantly more code in a low-level language² where you have to implement those. But it's still days of work, not weeks.) That doesn't mean Lisp is the only way to do functional programming, or even the best one. Quite apart from implementation questions, you might reasonably prefer the ML approach, with its strong static type checking; or the Haskell approach, which also features laziness; or the Clojure approach, which includes first-class persistent finite maps and integer-indexed "vectors"; or again the Clojure approach, where every operation supports ad-hoc polymorphism; or the Tcl approach, where everything is a string; or the Q approach, where your code defines term-rewriting rules rather than functions; or the Prolog approach, where you have not only list processing but lists that can contain uninstantiated logic variables; or the KANREN approach, which generalizes functional programming to full-on relational programming; or the Bicicleta approach, where you program directly in a side-effect-free ς-calculus, overriding methods instead of passing parameters; and many other approaches that haven't been thought of yet. But if you're thinking of Forth as an alternative to Lisp, or STL vectors as an alternative to Lisp lists, and in general rather than in a particular case, you just haven't understood the Lisp approach to problem solving at all. And when you do, it's going to be awesome. ______ ¹ http://canonical.org/~kragen/sw/dev3/readprint.fs http://canonical.org/~kragen/sw/dev3/readprint.fs ² https://www.mail-archive.com/kragen-hacks@canonical.org/msg00164.html https://www.mail-archive.com/kragen-hacks@canonical.org/msg0...
buggythebug 4y ago
Enough with LISP - no one cares
- kazinator 4y ago
  110 points, 85 comments.
- lispm 4y ago
  Let's go on with Lisp instead.

115 points by susam 4y ago

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 4y ago
I’ve been meaning to read Practical Common Lisp for some time. Would you recommend this even for complete beginners to Lisp?
- f1shy 4y ago
  That is THE book I would recommend for beginners.
- User23 4y ago
  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.
- georgeoliver 4y ago
  Yes I would! I think it was the first complete book I read while learning CL.
- abudabi123 4y ago
  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 4y ago
    I'm assuming you mean Touretzky's Common Lisp: A Gentle Introduction to Symbolic Computation — http://www.cs.cmu.edu/~dst/LispBook/index.html http://www.cs.cmu.edu/~dst/LispBook/index.html — which, yes, is a wonderful book for a complete beginner.
- dan-robertson 4y ago
  I read it around 10 years ago without knowing any lisp and got on ok.
- G3rn0ti 4y ago
  Two prehensile toes up! ;)
- scottomyers 4y ago
  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.

sillysaurusx 4y ago

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 https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.

jjtheblunt 4y ago
> Shared structure is overrated. Every MMU running a Unix with mmap probably disagrees!
- sillysaurusx 4y ago
  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.

pjmlp 4y ago

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

taeric 4y ago
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.
WJW 4y ago
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 4y ago
  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.
- openfuture 4y ago
  Maybe I am starting to spam the thread a bit here but I think the answer is canonical S-expressions, but proving that to be the case is more tricky than it looks although it is also kinda obvious from the surface level; vectors in s-expressions. But yeah the real answer is lambda calculus, see lambda lisp and justine.lol

ducktective 4y ago

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.

gaul_praham 4y ago
I remember https://adeht.org/casts/new-project.html https://adeht.org/casts/new-project.html For larger projects I remember youtube videos for Diablo and Minecraft clones.
johan_felisaz 4y ago
I would recommend this: https://m.youtube.com/user/CBaggers/featured 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 ...

dragontamer 4y ago

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 4y ago
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 4y ago

cmrdporcupine 4y ago

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 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.

openfuture 4y ago
Very interesting! thanks for this. The n-ary relations are bipartite graphs, one partition in the graph is the relations (hyperedges). This is /the/ universal (turing machine) theorem of computing. By the way, check out datalisp.is, I think we should re-encode the web :)

eduction 4y ago

>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?

terminalcommand 4y ago
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.
- openfuture 4y ago
  Forth is also homoiconic (arguably more so than lisp) and it can be thought of as being purely vectors.
  - terminalcommand 4y ago
    Forth's homoiconicity seems to be disputed: https://wiki.c2.com/?HomoiconicityClassification https://wiki.c2.com/?HomoiconicityClassification
    - openfuture 4y ago
      You could see forth as just netstrings recursively. You evaluate the outermost netstring by unquoting and then doing a forth over the netstrings it contains.

kragen 4y ago

I'm seeing a lot of people sort of dismissing the usefulness of lists without really understanding why Lisp is important: aren't vectors and hash maps better? Isn't CONS just malloc()? Doesn't Forth solve the problem that low-level languages like C are inflexible? — ⁂ — The first thing to understand is that Lisp invented functional programming. (Seibel's chapter mentions this, of course.) The functional-programming approach is to define your procedures recursively rather than iteratively; this began in Lisp but is now central to a number of other languages, like Haskell, OCaml, and F#. For certain fields, like symbolic algebra and compilers, this approach makes many difficult problems trivial. Even outside those fields, pervasive immutability often has many benefits, eliminating large classes of bugs, greatly simplifying problems like undo and thread-safety, and dramatically reducing the runtime cost of garbage collection. However, recursively defined linked data structures tend to use more space, and they're not very cache-friendly, and sometimes those are more important considerations. To define your procedures recursively, it's very helpful to define your data types recursively. Recursively-defined lists (for example, "a list of Ts is either the empty list of Ts or a T followed by a list of Ts") support this recursive, immutable approach to programming. Other kinds of recursive structures do, too; Haskell and ML dialects tend to use application-specific sum types at least as much as general-purpose lists, and I like that style better. It has most of the same advantages and disadvantages. STL-style vectors do not support a recursive style of programming. They support an iterative, imperative approach to programming. If you use that other approach to programming exclusively, you will not understand why anyone would want to primarily use linked lists. And occasionally you will be confronted with problems that are very difficult for you to solve, problems which would have been trivial with a recursive approach, and you will not realize that you are doing a hundred times more work to solve them than you need to. SICP is full of examples. — ⁂ — The second thing about Lisp is that it has orthogonal serialization and deserialization: PRINT and READ. This mechanism is sometimes, though not always, adequate for debug logging, saving and loading application state, configuration files, and networking. Modern Lisps like Clojure generally extend those to arbitrary data structures, not just lists and atoms, but it's especially easy to implement if you only have lists and atoms; it's about 30 lines of Forth, for example¹. This is of course not unique to Lisp anymore; Java, Python, Tcl, Golang, and many other languages have ways to do it. Orthogonal deserialization of lists is not really an optional extra, since you use it to parse Lisp programs, too. And you need the serialization to print lists in the REPL, anyway. — ⁂ — The third thing about Lisp is that it supports metaprogramming very well. This takes lots of forms; compile-time macros are a common one, and they give you enormous flexibility to extend Lisps into domain-specific languages, though they're probably used even more often to hack around inadequately optimized compilers. EVAL answers many requirements for runtime flexibility, though there are times when it is too powerful. As with serialization and deserialization, these metaprogramming facilities mostly just fall out of the Lisp design; they require minimal or no extra code in a Lisp interpreter. — ⁂ — Historically speaking Lisp had a lot of other advantages: for a long time it was the only garbage-collected language, the only dynamically-typed language, the only language with EVAL, the only language with higher-order functions, and so on, and so for many years it was by far the best language for the things that you would do in JS, Python, Ruby, Lua, or OCaml today. JS, Python, Ruby, Lua, and OCaml are better for some of those things, and for many purposes they adequately support the functional, recursive, immutable approach to programming that Lisp pioneered. Still, it might be easier to learn it in Lisp. — ⁂ — Lisp is sort of a minimal core of functional programming. In a decent low-level language like C or Forth, you can build a Lisp with an interactive functional programming environment with dynamic typing, orthogonal serialization and deserialization, an interactive interpreter, garbage collection, and extensive metaprogramming capabilities, in under 1000 lines of code, and the only data structure you need to do it is cons. (It's not quite as simple as you might think from reading the "Maxwell's Equations of Software" in the Lisp 1.5 manual; those gloss over READ, PRINT, decimal conversion, arithmetic, symbol interning, the garbage collector, and user interaction, so you end up with significantly more code in a low-level language² where you have to implement those. But it's still days of work, not weeks.) That doesn't mean Lisp is the only way to do functional programming, or even the best one. Quite apart from implementation questions, you might reasonably prefer the ML approach, with its strong static type checking; or the Haskell approach, which also features laziness; or the Clojure approach, which includes first-class persistent finite maps and integer-indexed "vectors"; or again the Clojure approach, where every operation supports ad-hoc polymorphism; or the Tcl approach, where everything is a string; or the Q approach, where your code defines term-rewriting rules rather than functions; or the Prolog approach, where you have not only list processing but lists that can contain uninstantiated logic variables; or the KANREN approach, which generalizes functional programming to full-on relational programming; or the Bicicleta approach, where you program directly in a side-effect-free ς-calculus, overriding methods instead of passing parameters; and many other approaches that haven't been thought of yet. But if you're thinking of Forth as an alternative to Lisp, or STL vectors as an alternative to Lisp lists, and in general rather than in a particular case, you just haven't understood the Lisp approach to problem solving at all. And when you do, it's going to be awesome. ______ ¹ http://canonical.org/~kragen/sw/dev3/readprint.fs http://canonical.org/~kragen/sw/dev3/readprint.fs ² https://www.mail-archive.com/kragen-hacks@canonical.org/msg00164.html https://www.mail-archive.com/kragen-hacks@canonical.org/msg0...

buggythebug 4y ago

Enough with LISP - no one cares

kazinator 4y ago
110 points, 85 comments.
lispm 4y ago
Let's go on with Lisp instead.