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

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

#61

Post by openfuture » Thu, Oct 13, 2022, 11:17 PM UTC

terminalcommand wrote: post #43

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.

Forth is also homoiconic (arguably more so than lisp) and it can be thought of as being purely vectors.

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

#62

Post by openfuture » Thu, Oct 13, 2022, 11:19 PM UTC

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

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 :)

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

#63

Post by openfuture » Thu, Oct 13, 2022, 11:23 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…

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

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

#64

Post by Jtsummers » Thu, Oct 13, 2022, 11:27 PM UTC

terminalcommand wrote: post #58

Jtsummers wrote: post #56

Earlier quoted context omitted.

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…

This is exactly what I'm talking about. Go is a statically typed C-like compiled language. It can convert the code much or less in its entirety to machine code. Lisp and forth on the other hand cannot, I think. They need some kind of interpretation at runtime to function so dynamically. If this is not the case, please prove me wrong. The distinction between compile time vs run time bugs me a lot. I think it is easier…

Lisp can be ahead of time compiled, being dynamically typed doesn't impact that. It does impact what gets generated by the compiler. Compiled CL code is usually "generic", it has logic inside that helps it dispatch based on the dynamic types during the runtime but this is not interpretation (in the sense meant by TCL, Python, and others). You can also specify the types and a compiler can, optionally, make (or use) more specific code which should error on a type mismatch but can run faster if you give it the correct, restricted types.

As to your speechlessness regarding compiled Lisp, here's a quick example:

  CL-USER> (defun foo (n)
             (+ 1 n))
  FOO
  CL-USER> (disassemble #'foo)
  ; disassembly for FOO
  ; Size: 35 bytes. Origin: #x53641724                          ; FOO
  ; 24:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
  ; 28:       488945F8         MOV [RBP-8], RAX
  ; 2C:       BF02000000       MOV EDI, 2
  ; 31:       488BD3           MOV RDX, RBX
  ; 34:       FF14250001A052   CALL QWORD PTR [#x52A00100]      ; SB-VM::GENERIC-+
  ; 3B:       488B5DF0         MOV RBX, [RBP-16]
  ; 3F:       488BE5           MOV RSP, RBP
  ; 42:       F8               CLC
  ; 43:       5D               POP RBP
  ; 44:       C3               RET
  ; 45:       CC10             INT3 16                          ; Invalid argument count trap
  NIL
  CL-USER>

(SBCL was used for the above)

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

#65

Post by dragontamer » Thu, Oct 13, 2022, 11:45 PM UTC

terminalcommand wrote: post #55

dragontamer wrote: post #50

Earlier quoted context omitted.

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). T…

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.

Macros just is code that transform a (list) data structure into (another different list), and then feeds (another different list) into the compiler (rather than the original (list) going into the compiler: how things happen without macros).

You can see how these things happen in like, Chicken Scheme (R5RS Scheme to C compiler).

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

#66

Post by terminalcommand » Thu, Oct 13, 2022, 11:46 PM UTC

Jtsummers wrote: post #64

terminalcommand wrote: post #58

Earlier quoted context omitted.

This is exactly what I'm talking about. Go is a statically typed C-like compiled language. It can convert the code much or less in its entirety to machine code. Lisp and forth on the other hand cannot, I think. They need some kind of interpretation at runtime to function so dynamically. If this is not the case, please prove me wrong. The distinction between compile time vs run time bugs me a lot. I think it is easier…

Lisp can be ahead of time compiled, being dynamically typed doesn't impact that. It does impact what gets generated by the compiler. Compiled CL code is usually "generic", it has logic inside that helps it dispatch based on the dynamic types during the runtime but this is not interpretation (in the sense meant by TCL, Python, and others). You can also specify the types and a compiler can, optionally, make (or use) mo…

I know that lisp compilers compile compute heavy trivial functions directly to machine code. But how is the output of a program containing a lisp macro for example. Let's say define a lisp macro don't call it and generate its assembly. What is the machine code output? This is the part I'm speechless about.

"The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written.

We need to generate an example of something we can't do in C, something which requires evaluation at runtime.

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

#67

Post by User23 » Thu, Oct 13, 2022, 11:51 PM UTC

math-dev wrote: post #54

sillysaurusx wrote: post #23

Earlier quoted context omitted.

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.

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)

And some Lisp implementations optimize some cons lists into vectors. The technique is called CDR encoding[1]. It's my understanding that at least the latest generation of modern CPUs actually have optimized instructions for tagged 64 bit pointers too, so this can be implemented efficiently on current hardware just as it was on Lisp machines! Of note though is that mutability complicates things, as usual.

[1] https://en.wikipedia.org/wiki/CDR_coding

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

#68

Post by TheMagicHorsey » Thu, Oct 13, 2022, 11:54 PM UTC

dkarl wrote: post #51

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…

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, an…

I haven't used Lisp in years, but isn't it very easy to just name the list members by defining a structure ... thus making your use/purpose of the list elements quite transparent?

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

#69

Post by xdavidliu » Thu, Oct 13, 2022, 11:54 PM UTC

dragontamer wrote: post #47

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…

> Pointers to TWO pointers (first pointer is named car, and the 2nd pointer is named cdr).

This is not true; only cdr is a pointer to a pointer. car is a pointer to a value. For example, if x is (1 2), then (car x) is a pointer to the value 1, while (cdr x) is a pointer to the list (2), so only the latter is "to a pointer".

> convert your C code into a vector or a hash-map.

nit: C has neither vectors nor hash-maps, neither builtin nor part of any standard library.

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

#70

Post by [deleted] » Thu, Oct 13, 2022, 11:54 PM UTC

terminalcommand wrote: post #66

Jtsummers wrote: post #64

Earlier quoted context omitted.

Lisp can be ahead of time compiled, being dynamically typed doesn't impact that. It does impact what gets generated by the compiler. Compiled CL code is usually "generic", it has logic inside that helps it dispatch based on the dynamic types during the runtime but this is not interpretation (in the sense meant by TCL, Python, and others). You can also specify the types and a compiler can, optionally, make (or use) mo…

I know that lisp compilers compile compute heavy trivial functions directly to machine code. But how is the output of a program containing a lisp macro for example. Let's say define a lisp macro don't call it and generate its assembly. What is the machine code output? This is the part I'm speechless about. "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Plus…

[deleted]