Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

gigamonkeys.com

Post reply on HN
Print view View original

91–100 of 125 posts

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

#91

Post by math-dev »

User23 wrote: post #67
math-dev wrote: post #54

Earlier quoted context omitted.

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://…

Thanks for sharing this link, very useful reading

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

#92

Post by dreamcompiler »

xdavidliu wrote: post #69
dragontamer wrote: post #47

Earlier quoted context omitted.

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

> only cdr is a pointer to a pointer.

This isn't really true either. Either half of a cons could contain a pointer or a direct value. Lisp makes the decision about pointers based on whether the value you're trying to store is small enough to fit there directly or not. And crucially, Lisp can tell the difference between a pointer and a value at runtime which means it will always do the right thing with whatever it finds.

This is why it gets dicey talking about pointers in Lisp: Pointers exist all over the place in Lisp but you have no direct control over them. That's the garbage collector's job.

Nothing in Lisp requires pointers in either half of a cons cell. There is a convention followed by the Lisp reader and printer that lists are represented with their head in the car and their remainder in the cdr of a cons cell, but the cons cells themselves don't care. Cons cells themselves know nothing about lists. They're just dumb 2-tuples with a car half and a cdr half. You're free to stick anything you want in either side. Each side holds 64 bits, and if you want to stick a string containing the Gettysburg address in the car [or cdr], Lisp will let you. (More specifically if you create this string Lisp will allocate a pointer for it, and it will then stick that pointer in the car.)

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

#93

Post by dreamcompiler »

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…

One example is queues: Lists are superior to vectors for queues that need to grow and shrink. It's easy to build an augmented list with an extra cons cell at the beginning that contains a pointer to both the first and last cons cells of the queue. This provides O[1] prepend, append, and push and pop operations. [Popping from the far end remains slow, which is why you typically push onto the far end and pop from the near end.]

Doing this with vectors is internally much messier and requires a lot of copying, which makes it slower, unless your queue is a circular buffer of fixed size.

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

#94

Post by lispm »

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…

> It's much easier to read code that uses named data structures.

That's why a bunch of large Lisp software was written with named data structures in the 70s/80s. They were called class, flavor, structure, frame, ... One can find a lot about that in the literature. Common Lisp was literally the first officially standardized object-oriented language, providing named classes and generic functions as building blocks.

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

#95

Post by lispm »

eyelidlessness wrote: post #81
dkarl wrote: post #51

Earlier quoted context omitted.

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…

In my experience, this is far less common in Clojure and far from idiomatic. The language’s core data structures and abstractions around them are all[1] based around `seq`, which is conceptually list-like in some respects. But among other distinctions (eg seq is presumed lazy by most APIs), it’s used to back various higher-level data structures, with various map structures in common use. There is an actual list type/…

In Clojure programs you'll see a lot more unidentified data (-> maps) than in object-oriented Lisp.

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

#96

Post by lispm »

dragontamer wrote: post #74
TheMagicHorsey wrote: post #68

Earlier quoted context omitted.

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?

In a lot of Lisp code, people don't bother to use that feature, and instead do a lot of (undocumented (sets of ((lists) that ) have some unknown) undefined structure) I never wrote Lisp code professionally, mostly just as a hobby for myself. It was all just dirty cons/cdr/car code. Given how generic lisp-lists are, they're really free form and could be anything. They are probably "too generic" for a lot of applicatio…

> A good, professional programmer probably should: 1. Start with the Lisp-lists as a prototype

Don't. Lisp since decades has a lot of different data types which are easy to use: vector/arrays, structures (-> records), classes, etc.

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

#97

Post by lispm »

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…

> But how is the output of a program containing a lisp macro for example.

The use of the macro gets expanded at compile time and the expanded code then gets compiled.

Lisp macros are designed in such a way that they are be expanded before runtime.

> evaluation at runtime

Evaluation at runtime does not mean the code gets not compiled.

The SBCL implementation of Common Lisp:

  * (let ((fn-code (quote (lambda (a)
                            (* a 42)))))  ;source of function as a list -> FN-CODE
    (let ((fn (eval fn-code)))            ; evaluation of that list FN-CODE ->eval-> FN
      (prog1
          (funcall fn 11)
        (disassemble fn))))
  ; disassembly for (LAMBDA (A))
  ; Size: 36 bytes. Origin: #x700568E8E4                        ; (LAMBDA (A))
  ; 8E4:       AA0A40F9         LDR R0, [THREAD, #16]           ; binding-stack-pointer
  ; 8E8:       4A0B00F9         STR R0, [CFP, #16]
  ; 8EC:       EA030CAA         MOV R0, R2
  ; 8F0:       8B0A80D2         MOVZ R1, #84
  ; 8F4:       3C9880D2         MOVZ TMP, #1217
  ; 8F8:       BE6B7CF8         LDR LR, [NULL, TMP]             ; SB-KERNEL:TWO-ARG-*
  ; 8FC:       DE130091         ADD LR, LR, #4
  ; 900:       C0031FD6         BR LR
  ; 904:       E00120D4         BRK #15                         ; Invalid argument count trap
  462
You'll see that EVAL at runtime compiles the code on-the-fly and in-memory to ARM64 machine code.

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

#98

Post by lispm »

terminalcommand wrote: post #72
dragontamer wrote: post #65

Earlier quoted context omitted.

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

I want to look at it to understand. But my guess is that this happens at runtime, doesn't it. If this happens at runtime, this means runtime evaluates the macro, lisp function is generated, generated lisp function is compiled and used.

Macros were invented such that macro expansion does NOT happen at runtime.

Lisp designers were implementing languages in the 70s which were used to develop whole operating systems for computers with less than one million instructions per second. With window systems, networking, etc.

A big part of the history of Lisp is how to design the language such that it is efficient AND/OR dynamic. Lots of people invented clever memory management, clever implementation techniques and adjusted the language for efficiency.

The first self-hosted Lisp compiler appeared already in 1962.

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

#99

Post by eyelidlessness »

lispm wrote: post #95
eyelidlessness wrote: post #81

Earlier quoted context omitted.

In my experience, this is far less common in Clojure and far from idiomatic. The language’s core data structures and abstractions around them are all[1] based around `seq`, which is conceptually list-like in some respects. But among other distinctions (eg seq is presumed lazy by most APIs), it’s used to back various higher-level data structures, with various map structures in common use. There is an actual list type/…

In Clojure programs you'll see a lot more unidentified data (-> maps) than in object-oriented Lisp.

As long as it Seqs it doesn’t matter! (Just kidding, this is why I found greener pastures of static types.)

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

#100

Post by lispm »

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…

> the same first/next semantics and performance as lists

How so?

Say we have a vector #(1 2 3 4) .

How do I get a vector with the first element removed? How do I get a vector with a element added?

(rest #(1 2 3 4)) -> #(2 3 4) (prepend 0 #(1 2 3 4)) -> #(0 1 2 3 4)

There are basically a few options to implement this:

a) allocate new vectors

b) implement growing/shrinking vectors

c) do something very clever internally, sharing vector memory

With cons cells this is simple. The possible drawbacks:

a) memory is fragmented into cons cells linking each other

b) lists may share memory

Post reply on HN