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

111–120 of 125 posts

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

#111

Post by terminalcommand »

lispm wrote: post #109
terminalcommand wrote: post #108

Earlier quoted context omitted.

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.

REPL is the interpreter isn't it? When you type the code into sbcl you are using the REPL which is the interpreter.

Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?

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

#112

Post by lispm »

terminalcommand wrote: post #111
lispm wrote: post #109

Earlier quoted context omitted.

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

REPL is the interpreter isn't it? When you type the code into sbcl you are using the REPL which is the interpreter. Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?

REPL is a Read Eval Print Loop, which is a way to interact with a Lisp runtime. This is independent on how EVAL is implemented. A bunch of Lisp systems implement EVAL with an incremental compiler.

An interpreter is a Lisp feature where code gets interpreted from source at runtime. Some implementations have one, some don't, some only have an interpreter, some only have a compiler, some have several compilers, some have both.

> running sbcl without the REPL and produce an executable binary file

The executable binary file in SBCL always includes the compiler.

REPL: a user interface to execute Lisp code. Reads s-expressions, evaluates them and prints the results as s-expressions.

EVAL: the interface to execute code. A function.

Interpreter: an implementation of Lisp which interprets source code.

Byte Code Interpreter: an implementation of Lisp which interprets byte code instructions.

Compiler: an implementation of Lisp which can compile code to a) byte code, b) C code, c) machine code

In-memory compiler: an implementation of Lisp where the compiler does not create files, but writes the executable code directly to RAM

Whole-Program compiler: an implementation of Lisp, which only compiles whole programs and creates executables -> rare, but various examples exists

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

#113

Post by dreamcompiler »

terminalcommand wrote: post #106
dreamcompiler wrote: post #89

Earlier quoted context omitted.

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

Exactly. And there are many other inline instructions (e.g. for doing arithmetic etc) but I didn't show them here. Any instruction the CPU supports can be present in a Forth program. In a compiled Forth, words can be specified as a list of calls to other Forth words or as raw assembly instructions, or both.

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

#114

Post by terminalcommand »

erik_seaberg wrote: post #110
terminalcommand wrote: post #107

Earlier quoted context omitted.

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.

From my conversation with lispm above, I discovered that each binary SBCL produces includes the compiler as well. This is what is meant by incremental compilation I get it.

When I first heard the term incremental compilation, I thought of a process like going through the ast couple of times and evaluating expressions. This wasn't what it meant. Now it makes sense. You include the lisp compiler in each binary. For parts you cannot evaluate at compile time, you compile at runtime, just like a JIT.

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

#115

Post by terminalcommand »

Jtsummers wrote: post #75
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. I think you have a fundamental confusion about when and where macros are applied. In a compiled CL implementation, macros are expanded prior to compilation. The code will be exactly the same as if there was no macro involved. If you want to see what that might look like take the function body of this simple function: (defun bar (filename) (with…

From my conversation with lispm, I discovered that each binary sbcl produces includes the lisp compiler. That means for evaluating expressions that cannot be determined at runtime, SBCL does some kind of JIT compilation.

I think this is called incremental compilation: https://en.wikipedia.org/wiki/Incremental_compiler

Now it makes sense, SBCL requires a complete compiler embedded in the runtime. Runtime is small enough that you don't care for it.

Okay I agree that lisp can be compiled. You just need a clever runtime being able to dynamically compile parts at runtime. If there are lisp implementations that do not require embedding either a compiler or an interpreter in the runtime, I'd doubt their expressiveness.

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

#116

Post by terminalcommand »

lispm wrote: post #112
terminalcommand wrote: post #111

Earlier quoted context omitted.

REPL is the interpreter isn't it? When you type the code into sbcl you are using the REPL which is the interpreter. Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?

REPL is a Read Eval Print Loop, which is a way to interact with a Lisp runtime. This is independent on how EVAL is implemented. A bunch of Lisp systems implement EVAL with an incremental compiler. An interpreter is a Lisp feature where code gets interpreted from source at runtime. Some implementations have one, some don't, some only have an interpreter, some only have a compiler, some have several compilers, some hav…

Thank you for taking the time to explain. I now get it. SBCL includes the compiler in each binary and this is called incremental compiling. That explains the expressiveness. It is kind of like a JIT when needed. Compile everything you can AoT, leave dynamic parts to runtime compilation. It makes perfect sense. Thanks .

I guess the difference is that in an interpreter you don't go down to assembly, you parse and run stuff. The moment you cross the line to generate bytecode/machine code or transpile into a different language you get a compiler.

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

#117

Post by terminalcommand »

dreamcompiler wrote: post #113
terminalcommand wrote: post #106

Earlier quoted context omitted.

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

Exactly. And there are many other inline instructions (e.g. for doing arithmetic etc) but I didn't show them here. Any instruction the CPU supports can be present in a Forth program. In a compiled Forth, words can be specified as a list of calls to other Forth words or as raw assembly instructions, or both.

Thank you for the explanation. Wow, these were questions stuck in my mind for a long time. Things make sense now.

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

#118

Post by [deleted] »

terminalcommand wrote: post #104
lispm wrote: post #98

Earlier quoted context omitted.

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.

[deleted]

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

#119

Post by dragontamer »

kaveh808 wrote: post #76
dragontamer wrote: post #74

Earlier quoted context omitted.

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…

My gut feeling is that this hasn't been true for a long time, unless you're really implementing a small test. Even then, using CLOS is quicker than deciding that "CDDR" refers to attribute "X". Modern CL is referred to as a multi-paradigm language, and I almost always start a project by starting with "defclass" and "defmethod" like in any OO language.

I think this was one of the big differences from Scheme vs CL.

Scheme, especially R5RS which is what I played around with the most, was about purity and simplicity. It wasn't really a practical/pragmatic language (though practical Schemes existed, like Racket), it was almost a "group study" in functional programming and greater programming concepts.

Common Lisp of course, was a practical/pragmatic language from the start. So of course you use vectors / hash maps / object-oriented programming.

-------

That being said, I fondly remember a lot of my scheme code, even if it was a bit quick-and-dirty. Its a paradigm that clearly works for a ton of problems.

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

#120

Post by xdavidliu »

dreamcompiler wrote: post #92
xdavidliu wrote: post #69

Earlier quoted context omitted.

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

> Nothing in Lisp requires pointers in either half of a cons cell.

You are definitely right about that, but the initial claim was made about "Lisp list", for which cdr is certainly a pointer. I would expect that when we refer to "Lisp lists", we certainly don't include things like (cons 1 2)

Post reply on HN