Comment

Comment by js8

I used to be a fan of these languages like Lisp and Forth and Joy (and Factor and Haskell), but then I found that what I a really long for is just (untyped) lambda calculus (as a universal language). (Combinatory logic is just a similar representation of lambda calculus, but the differences go away quickly once you start abstracting stuff.)

I think expressing semantics of all (common) programming languages in lambda calculus would give us a solid foundation for automated program translation. And we should aim for that, the babel tower of languages doesn't really help anyone.

The current issue I have is with type theory. So I am trying to embed notion of types directly into the lambda terms, so they would sort of "automatically typecheck" when composed. The crucial in this, in my opinion, are lambda terms that do not use lambda abstraction in their body, because you can think of these terms as a kind of mini-DSLs that have yet to be interpreted.

Anyway, once we can translate calculus of constructions (and other common formal logics) into untyped lambda calculus, it will also help us doing automated theorem proving. It must be theoretically possible, but to my knowledge nobody has really done this sort of hardcore formalization.

parent js8 1 year ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton