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

21–30 of 101 posts

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

#21

Post by armchairhacker »

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

Lisp is more expressive: I can write any program in LC but I'd much rather use Lisp.

Similarly someone could write C or JavaScript or Swift or Haskell in LC. Although I'd argue Lisp is a bit better as it's one of the first languages, one of the first to involve functional concepts like code-as-data, and itself is based on really simple concepts like LC.

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

#22

Post by kazinator »

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

Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus.

Lisp gives you a way to talk about lambda calculus, in a way that executes. For instance, papers about lambda calculus may talk about "beta reduction" and things of that nature. Those concepts are not in lambda calculus; they are about lambda calculus.

In lambda calculus examples you have terms like \x x and whatnot. But lambda calculus doesn't explain what x is; x is an identifier and that is part of the description of lambda calculus, and not in lambda calculus.

Lisp has the batteries included for describing languages, such as lambda calculus. It has an answer for what is x: it's a symbol, available as a data type. It has an answer for what is "beta reduction"; it's a function you can write, and execute on some piece of lambda calculus.

Lisp closes the circle; the stuff you talk about in a paper can become code, and code which is not far from what the paper talks about.

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

#23

Post by somewhereoutth »

lisper wrote: post #18
somewhereoutth wrote: post #17

Earlier quoted context omitted.

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

I agree that much of the motivation comes from real world imperatives, but, for example, P=NP is of deep mathematical interest in its own right, and if/when mathematicians solve it, they will move on and let us sort out the details.

We can actually build stuff (beyond some somewhat blessed prototypes) often only when we've understood the mathematics behind it - edit: or is that the other way around??

I'm not sure that any rigorous discipline can consider itself outside or unbound by mathematics.

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

#24

Post by kazinator »

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…

LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine.

LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type.

LC does not know what a LC expression is. Papers about LC know what that is, but they are not executable.

In Lisp we can say, okay, lambda calculus can be represented sort of like this:

  (lambda (x) x)
and so on. That's a nested list. It contains symbols. We can use an assoc list to associate symbols with the terms that are their values. And so on ...

Lisp has the programmatic vocabulary to talk about lambda calculus formally, in a way that is executable.

I don't suspect there is a significantly easier way for LC to interpret LC than to use the 42 page expression to create a Lisp, and then write the interpreter in that lisp.

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

#25

Post by somewhereoutth »

contravariant wrote: post #20

Here I was wondering what a lambda expression implementing lisp would look like. Page 33: >(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((... Yeah that seems about right.

Yes but isn't it beautiful? But seriously, instead of seeing lots of brackets, see the whole as a texture, a texture that has some importance (per Lisp advocates). See it in context with other textures, indeed all possible textures.

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

#26

Post by sudosysgen »

quickthrower2 wrote: post #19
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)!

Multiplication is generally done in O(n^2) of the number of bits so I'm not sure what you mean to say. Do you mean O(n^2) of the size of the operands?

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

#27

Post by kazinator »

lisper wrote: post #18
somewhereoutth wrote: post #17

Earlier quoted context omitted.

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

The complexity topic from which we have P = NP is not actually about time, but number of steps.

Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time.

If you have access to unlimited parallelism, then, for instance, some recursive algorithms that completely process a tree structure can drop from linear time to logarithmic.

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

#28

Post by somewhereoutth »

armchairhacker wrote: post #21
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?)

Lisp is more expressive: I can write any program in LC but I'd much rather use Lisp. Similarly someone could write C or JavaScript or Swift or Haskell in LC. Although I'd argue Lisp is a bit better as it's one of the first languages, one of the first to involve functional concepts like code-as-data, and itself is based on really simple concepts like LC.

Yes expressiveness is a crucial quality.

I'd suggest that code-as-data is in fact not a functional concept, and indeed may not necessarily be as helpful as we might like to think.

Lisp strayed from the path somewhat when it embarked on runtime enclosure (if my understanding is correct), and anyway it was never going to be as elegant as a true rewrite system.

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

#29

Post by somewhereoutth »

kazinator wrote: post #22
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?)

Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus. Lisp gives you a way to talk about lambda calculus, in a way that executes. For instance, papers about lambda calculus may talk about "beta reduction" and things of that nature. Those concepts are not in lambda calculus; they are about lambda calculus. In lambda calculus exa…

Beta reduction is in fact the essence of LC - without it all you'd have is a nice tree.

The beauty and generality of LC is that x doesn't need an explanation, it is just a placeholder, yet that is enough to define interesting (perhaps all) things.

Lisp is an abstraction, that per article can be built upon the deeper abstraction of LC - question is, what does it give us in terms of expressiveness and understanding?

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

#30

Post by somewhereoutth »

kazinator wrote: post #24
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…

LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine. LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type. LC does not know what a LC expression is. Papers about LC know wh…

Perhaps LC is telling us that maybe macros weren't such a good idea after all??
Post reply on HN