They Called It LISP for a Reason: List Processing (2005) • Hacker News Board

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

#41

Post by eduction » Thu, Oct 13, 2022, 8:46 PM UTC

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

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

#42

Post by terminalcommand » Thu, Oct 13, 2022, 9:19 PM UTC

dragontamer wrote: post #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 techniq…

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.

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

#43

Post by terminalcommand » Thu, Oct 13, 2022, 9:30 PM UTC

eduction wrote: post #41

>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 list…

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.

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

#44

Post by tmtvl » Thu, Oct 13, 2022, 9:30 PM UTC

WJW wrote: post #33

pjmlp wrote: 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 c…

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.

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

#45

Post by johan_felisaz » Thu, Oct 13, 2022, 9:34 PM UTC

ducktective wrote: post #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.

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

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

#46

Post by pyinstallwoes » Thu, Oct 13, 2022, 9:52 PM UTC

terminalcommand wrote: post #42

dragontamer wrote: post #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 techniq…

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 e…

Forth solves this.

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

#47

Post by dragontamer » Thu, Oct 13, 2022, 9:55 PM UTC

eduction wrote: post #41

>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 list…

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

     
     Start of a paragraph 
     Second paragraph  but some of it is bold 
    

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

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

#48

Post by terminalcommand » Thu, Oct 13, 2022, 10:01 PM UTC

pyinstallwoes wrote: post #46

terminalcommand wrote: post #42

Earlier quoted context omitted.

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 e…

Forth solves this.

Forth is still interpreted. Forth's genius is that it's interpreter is so tiny that it fits as a runtime.

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

#49

Post by 7thaccount » Thu, Oct 13, 2022, 10:02 PM UTC

pyinstallwoes wrote: post #46

terminalcommand wrote: post #42

Earlier quoted context omitted.

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 e…

Forth solves this.

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.

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

#50

Post by dragontamer » Thu, Oct 13, 2022, 10:03 PM UTC

terminalcommand wrote: post #48

pyinstallwoes wrote: post #46

Earlier quoted context omitted.

Forth solves this.

Forth is still interpreted. Forth's genius is that it's interpreter is so tiny that it fits as a runtime.

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.