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

101–110 of 125 posts

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

#101

Post by lispm »

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

It's just that since decades Lisp implementations don't do this, since most implementors don't see it providing much advantage (in speed or size) and it complicates the implementation.

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

#103

Post by sillysaurusx »

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

Incidentally, that link proves the point:

> In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation of the store. This problem is typically avoided by using CDR coding only on immutable data structures.

This is exactly what I've been saying. Thank you for providing a formal reference to the idea.

(I'm a bit confused how we wound up talking past each other, since my original proposal was identical to CDR coding on immutable cons cells.)

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

#104

Post by terminalcommand »

lispm wrote: post #98
terminalcommand wrote: post #72

Earlier quoted context omitted.

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…

I am not saying lisp is not performative. I am still not sold, I will make my own experiments and report back.

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

#105

Post by f1shy »

sillysaurusx wrote: post #25
f1shy wrote: post #22

Earlier quoted context omitted.

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 > and the variant can be a function, number (literal) or a variable.

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: https://gist.github.com/shawwn/63e0f010479efd95ebffdf2108645... 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.…

Not jet. I'm working with a friend. Even though the code is in github, is still private, until we have a first working version.

What I'm doing is an extremely simple evaluator, which can do what is required for PDDL: basic arithmetic, logic operators and IF.

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

#106

Post by terminalcommand »

dreamcompiler wrote: post #89
terminalcommand wrote: post #48

Earlier quoted context omitted.

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

Forth can be interpreted but it can also be compiled in at least two or three different ways. Forth is unique in that its interpreter can look (and perform) a lot like compiled code. Let's say you have a list of assembly language function names FOO, BAR, BAZ, etc. Each name stands for the starting memory address of that function. Each function ends with a standard RET instruction. At address PROGRAM, you store the li…

Thank you, I didn't know about the jsr instruction. I always imagined forth does this somehow with jmps.

Another main difference from true compiled code is that your entire program consists of subroutine calls. There are no inline instructions and a main function.

I've got a lot of reading to do on this. "Indirect jsr", I'll experiment with this.

Okay I'm convinced, forth is not interpreted when it's compiled to threaded code :). There is no main loop that reads instructions and dispatches them dynamically, the program flow is linear with subroutine calls stacked under each other.

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

#107

Post by terminalcommand »

dragontamer wrote: post #77
terminalcommand wrote: post #72

Earlier quoted context omitted.

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.

> But my guess is that this happens at runtime, doesn't it Macros would be evaluated at compile-time (or arguably _right before_ compile time).

How can you evaluate a complex macro at compile-time if you are doing AoT compilation? Lisp macros are not like C macros where simple substitution would suffice, they need to be evaluated.

I found my exact question on stackoverflow: https://stackoverflow.com/questions/7072980/how-do-you-compi...

The answers on SO are still not clear to me, some people say the macros can be evaluated at compile time, some say that the runtime needs to include some kind of interpreted to run macros. Some say incremental compilation is key to understand how macros get evaluated at compile time.

I will run experiments on this.

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

#108

Post by terminalcommand »

lispm wrote: post #97
terminalcommand wrote: post #66

Earlier quoted context omitted.

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

You are dissasembling inside the interpreter. Interpreter already reads, evaluates before generating the assembly code. How does EVAL work if the entire program is compiled AoT?

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

#109

Post by lispm »

terminalcommand wrote: post #108
lispm wrote: post #97

Earlier quoted context omitted.

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

You are dissasembling inside the interpreter. Interpreter already reads, evaluates before generating the assembly code. How does EVAL work if the entire program is compiled AoT?

> You are dissasembling inside the interpreter.

What you see is no interpreter. It's an interactive interface, reading code, compiling it, executing it, printing the result.

There is by default no interpreter. Everything is compiled in SBCL.

A Lisp system typically includes an on-board compiler and/or interpreter.

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

#110

Post by erik_seaberg »

terminalcommand wrote: post #107
dragontamer wrote: post #77

Earlier quoted context omitted.

> But my guess is that this happens at runtime, doesn't it Macros would be evaluated at compile-time (or arguably _right before_ compile time).

How can you evaluate a complex macro at compile-time if you are doing AoT compilation? Lisp macros are not like C macros where simple substitution would suffice, they need to be evaluated. I found my exact question on stackoverflow: https://stackoverflow.com/questions/7072980/how-do-you-compi... The answers on SO are still not clear to me, some people say the macros can be evaluated at compile time, some say that the…

A compiled Lisp program might not be able to eval a list or load a source file, for the same reason a packaged jar generally won’t contain a copy of the Java compiler. I think eval-when controls which macro definitions (if any) need to be available at runtime, rather than being expanded away while compiling functions.
Post reply on HN