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

Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

woodrush.github.io

Post reply on HN
Print view View original

11–20 of 101 posts

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#11

Post by lisper »

tromp wrote: post #7

As author of the Binary Lambda Calculus (BLC), I find this quite fascinating. It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. I'm still reading the document, but one thing that caught my eye is the List encoding with cons and nil, which is claimed to be a Mogensen-Scott one. Rather, cons \x\y\c. c x…

> It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits.

That's hardly a fair comparison. LambdaLisp includes a ton of features that BLC and BF do not.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#12

Post by lisper »

zentr1c wrote: post #5
smitty1e wrote: post #3

> Here is a PDF showing its entire lambda term, which is 42 pages long: Elsewhere, Douglas Adams smiles.

This

Hm, I wonder if the authors fine-tuned the feature set (and font size!) to achieve this outcome :-)

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#13

Post by lisper »

actually_a_dog wrote: post #6

This is undoubtedly cool, but I'd be really impressed if it wasn't stupidly slow. (I'm not saying it is stupidly slow, because I haven't had a chance to run it, just that I'd be impressed if it wasn't.)

I haven't tried it either, but I would not bet my life savings on it being slow. I tried something similar to this a few years ago (see my top-level comment for a pointer) and was amazed at how fast it turned out to be.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#14

Post by somewhereoutth »

lisper wrote: post #10
somewhereoutth wrote: post #9

Lambda calculus is mathematically foundational in a way that Lisp of course isn't. The question is what does Lisp give us as an interpretation of those foundations? Or does it admit issues that might be unhelpful? (Are macros a good thing?)

Let's not sell Lisp short here. LC might be mathematically foundational, but I think it's fair to say that Lisp is computationally foundational. Mathematics and computation are related, of course, but they are not identical. Computation is the study of mechanical processes for doing math. As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine is important…

I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?)

I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up)

LC is basically a rewrite engine, so I'm not sure it would be so hard to implement? Probably some plastic bags, in two colours, paper scraps, and a marker pen would do it? (Edit - one colour bag would need 2 ordered compartments - or if you really have lots of spare time you could build it all with just plain bags and some set theory) However as you say perhaps Lisp is a better abstraction over the Turing tape (yuck).

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#15

Post by somewhereoutth »

smitty1e wrote: post #3

> Here is a PDF showing its entire lambda term, which is 42 pages long: Elsewhere, Douglas Adams smiles.

Ah but this is where it becomes interesting! Because we can then guage how much work this abstraction is doing for us - and indeed whether or not it might stray from the 'one true path' (whatever that might be)

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#16

Post by lisper »

somewhereoutth wrote: post #14
lisper wrote: post #10

Earlier quoted context omitted.

Let's not sell Lisp short here. LC might be mathematically foundational, but I think it's fair to say that Lisp is computationally foundational. Mathematics and computation are related, of course, but they are not identical. Computation is the study of mechanical processes for doing math. As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine is important…

I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is ba…

> I would disagree that computation is process for doing math

Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be written down by a machine."

> specifically that for operating over a discrete state space.

Sorry, but you are mistaken about that too. Analog computers and quantum computers are computers but they do not operate over discrete state spaces. They are, however, machines.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#17

Post by somewhereoutth »

lisper wrote: post #16
somewhereoutth wrote: post #14

Earlier quoted context omitted.

I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is ba…

> I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine ." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be writ…

I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right.

Per analog and quantum, indeed, and they are also mathematics.

I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#18

Post by lisper »

somewhereoutth wrote: post #17
lisper wrote: post #16

Earlier quoted context omitted.

> I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine ." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be writ…

I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right. Per analog and quantum, indeed, and they are also mathematics. I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.

What can I say? You are mistaken. Computation is as much about physics as it is about math. It is the study of what can actually be done in this universe with real hardware (including human brains). If you doubt this, read the opening paragraph of this paper:

https://www.scottaaronson.com/papers/pnp.pdf

The only reason that P=NP? matters at all (let alone why it is a foundational question) is because the theory of computation concerns itself with what can be done with actual physical hardware in actual physical time.

> Per analog and quantum, indeed, and they are also mathematics.

No, they aren't. Analog computers are machines. Quantum computers are machines (or at least they will be if we ever actually manage to build one). We can describe the behavior of these machines mathematically, but that is not why they matter. They matter because we can actually build them.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#19

Post by quickthrower2 »

actually_a_dog wrote: post #6

This is undoubtedly cool, but I'd be really impressed if it wasn't stupidly slow. (I'm not saying it is stupidly slow, because I haven't had a chance to run it, just that I'd be impressed if it wasn't.)

It has to be slow. Multiplication will be O(N^2)!

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#20

Post by contravariant »

Here I was wondering what a lambda expression implementing lisp would look like.

Page 33:

>(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

Yeah that seems about right.

Post reply on HN