5 ms·

Because the Lambda calculus is, in large part, rather messy to implement when it comes to physical computing. When we look at what computation is, physically,

by imode 8y ago

Because the Lambda calculus is, in large part, rather messy to implement when it comes to physical computing. When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. Anything involving trees/terms in general seems to be rather messy in terms of physical computation, because there's no straightforward way to represent a manipulatable tree regardless of the medium. Part of the reason TM-like computing devices sprung up is because strings, i.e linear sequences of symbols, are surprisingly easy to represent and manipulate physically. Turing himself appealed to physical intuition in his original paper. Just my thoughts as a person who's tried to bootstrap his own LC-based computing environment. I did succeed, but I'm not entirely happy with the results.

gnulinux 8y ago
I'm under the impression that LC is closer to how humans think of computation, and it seems that even though it's easier to implement TM as a bare-metal machine, isn't it a trade-off? If humans mostly produce LC-like high-level code, then compile them to TM-like machine code, wouldn't it be better at some point to produce LC-like machines? Because even though they're slower at face value, wouldn't it be faster on "human software". This comment assumes 'humans mostly produce LC-like high-level code', but I think this is valid; other than C, I cannot think of a language in which programmers don't use lambdas, higher-order functions ubiquitously. It seems like our CPUs are optimized for C, but I'm curious how would it change if we optimize them for javascript, python or haskell...
- imode 8y ago
  Here's a test: do you think in terms of step-by-step instructions to solve a process? There are ways of composing Turing Machines much like composing functions to yield higher abstraction levels in the Lambda Calculus. It comes in the form of building up larger forms of instructions out of simpler machines. I don't think humans think in a LC-like manner, I think we think compositionally: small parts make up big parts, use the parts you make to make bigger parts. Whether those come in the form of a physical machine or an applicative system doesn't matter, what matters is how you string primitives together. Check this[1] out. This walks you through building up a more usable language out of the rough-and-ready Turing Machine. There are many ways to go about this idea of composition, but this is a good introduction. https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30d62dafb6edfcfb9121ced906116.pdf https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30...
  - gnulinux 8y ago
    I disagree with what you're suggesting. It's tempting to think humans think procedurally, because that's how we study algorithms. I think this is very misleading. Algorithm is an abstraction of a step-by-step process; studying algorithms in an applicative fashion would be harder simply because they're different sort of things (algorithm is abstracted out of something else). Computation, on the other hand, is a larger category where you're not interested in a particular algorithm in isolation; instead, you have N algorithms and M data. Your hypothesis doesn't pass any test, if you look at most of the code written today, this very minute, you'll see that it is mostly written in LC-like manner. I'm also not suggesting it is purely applicative, but most PLs seem to be a cross between two models, LC getting more traction recently (look at programming languages I listed above). Compare how popular C was a few decades ago vs now. Our web browsers' native language is javascript, which is essentially lisp in a C-suit, and people started using the same language on desktop and even in embedded devices. Where is C, Fortran, Algol?
    - imode 8y ago
      If you can't define an algorithm as a step-by-step process, what can you define it as? That's the whole point: it is a process, manifested as sets of discrete steps, towards an end result by following sets of rules. Lambda Calculus, Turing Machines, etc. are no different in this regard. One has its steps realized in reduction and substitution rules, the other has its steps realized in movements of the head and manipulations of the tape. You'll need more to disprove my hypothesis. All software is built compositionally, up from smaller pieces. It's why we commonly refer to everything as a "software stack": we can reason about smaller making up larger. If you examine most of the code written today, this very minute, you'll see it's compositional, in the way that larger codebases are built from components. Neither LC or TMs are "natural ways of thought", they're mechanisms. Turns out that TMs won out not only because they admit an easy physical implementation, but also because they're compositional. I can wire up two TMs and get them to perform operations in sequence, perform conditional branching, etc. JavaScript is hardly Lisp in a C-suit, but that's beside the point, because C is pretty terrible (despite it being my favorite) regardless of what paradigm you choose. I'm not going to devote much of this comment towards that. All software is compositional, regardless of the medium, and all computation is purely mechanical, regardless of the model of computation, because unless you want to stare at a lambda expression and infer the value, you need to perform some kind of step-wise reduction. That, after all, was Church's point.
white-flame 8y ago
Cons-based tree data structures have little to do with data processing in Lisp. Specifically, it is a compile time feature (which is available at runtime, too) that source code is contained in these structures in a sort of AST gives it its metaprogramming capabilities. The runtime data crunching, GC, and optimization techniques aren't substantially different from other modern dynamic (or semi-dynamic) languages, though Lisp tends to have more features (dynamic bindings, complex numbers, in-language macros, etc). Cons cells at runtime are usually used as plain linked lists, as any dynamic list/array would be in other languages.
- rjsw 8y ago
  On a related note, the SPEC CINT92 benchmark suite included running a tree walking algoritm in interpreted XLISP. I have no idea what the benchmark author thought it demonstrated.
- 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.
chriswarbo 8y ago
> When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. I don't think that's the case at all. We see sequential TM-like processes when we look at mainstream electronic computers, but that's kind of a circular argument. When we look at physical processes in general, the computations they're performing tend to be massively parallel. Pure computation (e.g. lambda calculus, and especially combinatory logic) is well suited to running on massively parallel circuitry (e.g. https://en.wikipedia.org/wiki/Graph_reduction_machine https://en.wikipedia.org/wiki/Graph_reduction_machine ). It's perhaps also worth mentioning that such languages can be interpreted as (descriptions of) circuitry! E.g. see http://conal.net/papers/compiling-to-categories http://conal.net/papers/compiling-to-categories

by imode 8y ago

gnulinux 8y ago

I'm under the impression that LC is closer to how humans think of computation, and it seems that even though it's easier to implement TM as a bare-metal machine, isn't it a trade-off? If humans mostly produce LC-like high-level code, then compile them to TM-like machine code, wouldn't it be better at some point to produce LC-like machines? Because even though they're slower at face value, wouldn't it be faster on "human software". This comment assumes 'humans mostly produce LC-like high-level code', but I think this is valid; other than C, I cannot think of a language in which programmers don't use lambdas, higher-order functions ubiquitously. It seems like our CPUs are optimized for C, but I'm curious how would it change if we optimize them for javascript, python or haskell...

imode 8y ago
Here's a test: do you think in terms of step-by-step instructions to solve a process? There are ways of composing Turing Machines much like composing functions to yield higher abstraction levels in the Lambda Calculus. It comes in the form of building up larger forms of instructions out of simpler machines. I don't think humans think in a LC-like manner, I think we think compositionally: small parts make up big parts, use the parts you make to make bigger parts. Whether those come in the form of a physical machine or an applicative system doesn't matter, what matters is how you string primitives together. Check this[1] out. This walks you through building up a more usable language out of the rough-and-ready Turing Machine. There are many ways to go about this idea of composition, but this is a good introduction. https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30d62dafb6edfcfb9121ced906116.pdf https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30...
- gnulinux 8y ago
  I disagree with what you're suggesting. It's tempting to think humans think procedurally, because that's how we study algorithms. I think this is very misleading. Algorithm is an abstraction of a step-by-step process; studying algorithms in an applicative fashion would be harder simply because they're different sort of things (algorithm is abstracted out of something else). Computation, on the other hand, is a larger category where you're not interested in a particular algorithm in isolation; instead, you have N algorithms and M data. Your hypothesis doesn't pass any test, if you look at most of the code written today, this very minute, you'll see that it is mostly written in LC-like manner. I'm also not suggesting it is purely applicative, but most PLs seem to be a cross between two models, LC getting more traction recently (look at programming languages I listed above). Compare how popular C was a few decades ago vs now. Our web browsers' native language is javascript, which is essentially lisp in a C-suit, and people started using the same language on desktop and even in embedded devices. Where is C, Fortran, Algol?
  - imode 8y ago
    If you can't define an algorithm as a step-by-step process, what can you define it as? That's the whole point: it is a process, manifested as sets of discrete steps, towards an end result by following sets of rules. Lambda Calculus, Turing Machines, etc. are no different in this regard. One has its steps realized in reduction and substitution rules, the other has its steps realized in movements of the head and manipulations of the tape. You'll need more to disprove my hypothesis. All software is built compositionally, up from smaller pieces. It's why we commonly refer to everything as a "software stack": we can reason about smaller making up larger. If you examine most of the code written today, this very minute, you'll see it's compositional, in the way that larger codebases are built from components. Neither LC or TMs are "natural ways of thought", they're mechanisms. Turns out that TMs won out not only because they admit an easy physical implementation, but also because they're compositional. I can wire up two TMs and get them to perform operations in sequence, perform conditional branching, etc. JavaScript is hardly Lisp in a C-suit, but that's beside the point, because C is pretty terrible (despite it being my favorite) regardless of what paradigm you choose. I'm not going to devote much of this comment towards that. All software is compositional, regardless of the medium, and all computation is purely mechanical, regardless of the model of computation, because unless you want to stare at a lambda expression and infer the value, you need to perform some kind of step-wise reduction. That, after all, was Church's point.

white-flame 8y ago

Cons-based tree data structures have little to do with data processing in Lisp. Specifically, it is a compile time feature (which is available at runtime, too) that source code is contained in these structures in a sort of AST gives it its metaprogramming capabilities. The runtime data crunching, GC, and optimization techniques aren't substantially different from other modern dynamic (or semi-dynamic) languages, though Lisp tends to have more features (dynamic bindings, complex numbers, in-language macros, etc). Cons cells at runtime are usually used as plain linked lists, as any dynamic list/array would be in other languages.

rjsw 8y ago
On a related note, the SPEC CINT92 benchmark suite included running a tree walking algoritm in interpreted XLISP. I have no idea what the benchmark author thought it demonstrated.
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.

chriswarbo 8y ago

> When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. I don't think that's the case at all. We see sequential TM-like processes when we look at mainstream electronic computers, but that's kind of a circular argument. When we look at physical processes in general, the computations they're performing tend to be massively parallel. Pure computation (e.g. lambda calculus, and especially combinatory logic) is well suited to running on massively parallel circuitry (e.g. https://en.wikipedia.org/wiki/Graph_reduction_machine https://en.wikipedia.org/wiki/Graph_reduction_machine ). It's perhaps also worth mentioning that such languages can be interpreted as (descriptions of) circuitry! E.g. see http://conal.net/papers/compiling-to-categories http://conal.net/papers/compiling-to-categories