2 ms·

The problem is all of this relies on a representation of the data structure you're manipulating. What exactly is the structure that a Lisp machine is manipulati

by imode 8y ago

The problem is all of this relies on a representation of the data structure you're manipulating. What exactly is the structure that a Lisp machine is manipulating? The basis of Lisp is the Lambda Calculus, and a generalization of that gets you term rewriting. Both the basis and the generalization of Lisp admit to requiring a tree (or a graph, in the case of Cons-cells) to get on with the computations, because that's the "state" that you're working with. The problem is that while these things in the minds of humans are pretty easy to work with, implementing them physically has you rely on things like the RAM model, which, while pretty far away from the Turing Machine, still has machine-like qualities. That's my argument. We can't really build "Lisp Machines", we can build "Random Access Machines with Lisp Interfaces", because there's no physically implementable version of a tree or graph memory outside of linking randomly-accessible cells.

chriswarbo 8y ago
> implementing them physically has you rely on things like the RAM model Not at all. In fact, electronic circuitry is quite similar to "LC style" programming, for example we can think of both as a sort of "pipeline for data to flow through". On the other hand, Turing machines, RAM machines, etc. aren't particularly well suited to being implemented electronically. We end up introducing clock signals, addressing schemes, etc. and it all ends up very complicated, slow and power hungry. I think the only reason we put up with it at all is because electronics, especially ICs, are so incredibly small and fast to begin with, that these inefficiencies aren't too noticable at the human scale.
kazinator 8y ago
The basis of Lisp isn't lambda calculus. Lambda calculus doesn't have a concept of its own expressions being data manipulated by lambda calculus. There is no quote operator in lambda calculus. All the terms in lambda calculus are functions; there are no conses, symbols, numbers, strings, nothing. (Immutable) cons cells can be simulated in lambda calculus using functions. This being in the sense that functions resembling cons, car and cdr can be expressed such that car(cons(x, y)) = x, and cdr(cons(x, y)) = y. Lisp arises from the realization that expressions built out of trees that consist of pairs can be executed using an eval function, in a way that incorporates some concepts from lambda calculus, such as anonymous functions.
- chewxy 8y ago
  > Lambda calculus doesn't have a concept of its own expressions being data manipulated by lambda calculus. There is no quote operator in lambda calculus. McCarthy himself noted this about Lambda Calculus and came up with EVAL. In fact several people have also noticed this. They simply shrugged and delta-ruled all the things.
white-flame 8y ago
I have no idea how any of that is unique to Lisp or lambda calculus. If you want a tree or graph structure in another language, you'll have random access of nodes in memory, too. If you want to manually optimize such a linked data structure on top of an array of node structs using offsets, or hash tables, or whatever, you can do that in Lisp or any other language as well. Any form of non-serialized memory access will penalize you in today's memory heirarchies, no matter the language. Care can be taken in any language to have cache-aligned data structures and preprocessing to attempt to linearize the most common access patterns, usually with preallocated arrays. But generally that level of fine-grained microoptimization isn't needed, and basic data structure best practices are language-agnostic.

by imode 8y ago

chriswarbo 8y ago

> implementing them physically has you rely on things like the RAM model Not at all. In fact, electronic circuitry is quite similar to "LC style" programming, for example we can think of both as a sort of "pipeline for data to flow through". On the other hand, Turing machines, RAM machines, etc. aren't particularly well suited to being implemented electronically. We end up introducing clock signals, addressing schemes, etc. and it all ends up very complicated, slow and power hungry. I think the only reason we put up with it at all is because electronics, especially ICs, are so incredibly small and fast to begin with, that these inefficiencies aren't too noticable at the human scale.

kazinator 8y ago

The basis of Lisp isn't lambda calculus. Lambda calculus doesn't have a concept of its own expressions being data manipulated by lambda calculus. There is no quote operator in lambda calculus. All the terms in lambda calculus are functions; there are no conses, symbols, numbers, strings, nothing. (Immutable) cons cells can be simulated in lambda calculus using functions. This being in the sense that functions resembling cons, car and cdr can be expressed such that car(cons(x, y)) = x, and cdr(cons(x, y)) = y. Lisp arises from the realization that expressions built out of trees that consist of pairs can be executed using an eval function, in a way that incorporates some concepts from lambda calculus, such as anonymous functions.

chewxy 8y ago
> Lambda calculus doesn't have a concept of its own expressions being data manipulated by lambda calculus. There is no quote operator in lambda calculus. McCarthy himself noted this about Lambda Calculus and came up with EVAL. In fact several people have also noticed this. They simply shrugged and delta-ruled all the things.

white-flame 8y ago

I have no idea how any of that is unique to Lisp or lambda calculus. If you want a tree or graph structure in another language, you'll have random access of nodes in memory, too. If you want to manually optimize such a linked data structure on top of an array of node structs using offsets, or hash tables, or whatever, you can do that in Lisp or any other language as well. Any form of non-serialized memory access will penalize you in today's memory heirarchies, no matter the language. Care can be taken in any language to have cache-aligned data structures and preprocessing to attempt to linearize the most common access patterns, usually with preallocated arrays. But generally that level of fine-grained microoptimization isn't needed, and basic data structure best practices are language-agnostic.