Towards λ-calculus | Hacker News Reader

Towards λ-calculus

lambdaway.free.fr

178 pointsmartyalain45 comments

For those who want to grok lambda calculus, I would highly recommend "An Introduction to Functional Programming Through Lambda Calculus" book by Greg Michaelson[0]. After going through the book, I could say that you're brain will adapt the functional programming paradigm if you are used to the imperative programming language. Functional programming will change the way you think and make you a better programmer.

[0] - https://pdfs.semanticscholar.org/d986/546bc3780db3a3c0f8d88b...

Seconded--I got this book on a whim and didn't expect to finish it very quickly, but I was having so much fun with it it displaced all the other books I was working on at the time. This was step two on my journey towards embracing FP (step one was seeing OCaml in a class).

I was lucky enough to be taught lambda calculus and related topics at Heriot-Watt by Greg - I'll never forget the moment when he introduced the S and K combinators - been fascinated with those ever since.

[NB Related topics included strongly recommending GEB].

> I'll never forget the moment when he introduced the S and K combinators - been fascinated with those ever since.

Rabbit hole warning. If you go down this particular hole you will lose at least a month and maybe more. It will be the most fun you've had in a long time but your productivity will take an extreme hit.

Indeed, my final year project was to build a functional programming language that macro expanded into lambda calculus the transform that into different sets of combinators and look at the performance improvements.

To this day (almost exactly 30 years) - I am staggered that you can express Y in terms of S & K. I know this follows trivially but actually having coded it and watched it run (slowly) did made it very real to me.

NB This was running on an Orion minicomputer with rather limited memory - I had to implement a mark and sweep garbage collector to get expressions of any size to run!

Do you still have this? That would be a very nice project to share.

I still have a print out of it - I did find myself considering the idea of re-implementing it in something a bit nicer than 1980s K&R C.

I'd be happy to help if you want.

It's somewhere on my long list of projects to work on - thanks for the offer though :-)

Sounds very promising!

To make sure(er) the PDF sticks around, here it is stored on IPFS: https://ipfs.io/ipfs/QmRKHcRYBpYJBWbiRkPeGA9kWfsjUtZPq45oMi6...

It's intended more for kids, but Alligator Eggs is a fun way to play with lambda calculus: http://worrydream.com/AlligatorEggs/

Hello HN folks,

Again and again, as a personal work, I try to find the best minimal foundations for a language. Beside lambdatalk and its “non standard” regexp based implementation, I explore with lambdacode a standard AST based implementation.

Am I on the good lambda-calculus way?

   - http://lambdaway.free.fr/workshop/?view=lambdacode_inside_min
   - http://lambdaway.free.fr/workshop/?view=lambdacode 
   - http://lambdaway.free.fr/workshop/?view=helloworld
   - http://lambdaway.free.fr/

If you are willing to read it as pure speculation, I would appreciate that. If not, I am sure you have a waste basket handy.

Thanks

>>> If you are willing to read it as pure speculation, I would appreciate that. If not, I am sure you have a waste basket handy.

Langlands :-)

:) :) :)

Factorials in pure lambda calculus that actually run in non-geologic time:

http://www.flownet.com/ron/lambda-calculus.html

Something like http://lambdaway.free.fr/workshop/?view=NIL

That is actually very cool. You should submit it to HN.

Thanks. I did it 3 months ago without any comment. https://news.ycombinator.com/item?id=16202754

A lot of good stuff is falling through the cracks nowadays. Even YC content is going unnoticed, e.g.

https://news.ycombinator.com/item?id=16946261

But if a submission gets no comments you can re-submit it after a few hours without setting off the de-duper.

Sometimes (quasi) re-submissions are flagged https://news.ycombinator.com/item?id=16066019

And sometimes they stay alone for ever: https://news.ycombinator.com/item?id=16983540

For people who wanna learn Functional Programming, I recommend this resources:

https://github.com/allenleein/brains/projects/9

Learnt functional programming and lambda calculus under Raul Rojas, happy to see he's mentioned here. He taught us the evaluation step as a vacuum cleaner sucking in the variables.

I began to understand lambda-calculus with this introduction from Raoul Rojas. But I was lost when he explains recursion via the Y-combinator. In fact I think that recursion is best understood when lambdas are introduced to bring a bit of lazyness in an by default eager evaluation. The (if bool one two) control structure is not so easy to understand under the cap.

I don't get one thing from this article. Am I suppose to be impressed by this code that prints some fruits?

> In order to understand what can be done with so little

    ((lambda (f n) (f f n)) (lambda (f list) ((((lambda (n) (n (lambda (x) (lambda (z) (z (lambda (x y) y)))) (lambda (z) (z (lambda (x y) x))))) list) ((lambda (x y) (lambda (z) (z x y))) (lambda (list) '.) (lambda (list) (join ((lambda (z) (z (lambda (x y) x))) list) (f f ((lambda (z) (z (lambda (x y) y))) list)) )))) list)) ((lambda (x y) (lambda (z) (z x y))) 'apple ((lambda (x y) (lambda (z) (z x y))) 'banana ((lambda (x y) (lambda (z) (z x y))) 'lemon ((lambda (x y) (lambda (z) (z x y))) 'grapes ((lambda (x y) (lambda (z) (z x y))) 'orange (lambda (s z) z)))))))

    apple banana lemon grapes orange

Not too impressive if you ask me, maybe if you want to obfuscate your code so nobody will understand it. Maybe then.

It's not intended to impress anybody. I write the result first, an unreadable lambda-calc expression, then I explain the making of in few lines easier to understand, IMHO, than what I could see elsewhere. Did I missed something in the explanations?

Lambda calculus is an attempt to build the foundations of computation using a couple of primitives and some re-write rules. It’s the equivalent of ZFC for math.

It's just what I try to do. I think that the lambda-calculus is the Maxwell's equations of the computer field and not the LISP as Alan Kay said. The implementation is also an important point. In the wiki page "towards λ-calculus" I use a standard AST based evaluator, a minimal version of ( http://lambdaway.free.fr/workshop/?view=lambdacode ). In this other wiki page ( http://lambdaway.free.fr/?view=NIL ) I use a completely different implementation, {lambda talk}, where the re-write rules are the heart of the machine: 1) finding from inside-out S-expressions in the whole code and replacing them by words and 2) inside lambdas, replacing in the body arguments by the given values. Not only this implementation works like (what I understand to be) a Turing machine, but it works fine in a wiki context where quoting words and bracketing sentences would be unacceptable. I find this "inverted" implementation worthwhile, from the both theoretical and practical points of view.

Lambda Calculus is perhaps the Maxwell's equations of computability, not of the computer field. What Kay might have meant is that Lisp is the Maxwell's equations of programming a computer to do something useful.

Lambda Calculus doesn't even have numbers; you either have to build them out of functions, or else extend Lambda Calculus with numeric terms. Lambda Calculus doesn't have eval or quote, and if it did, they wouldn't work because Lambda Calculus doesn't have a data structure representing Lambda Calculus source code. Lambda Calculus also lacks practicalities like assignable variables, which are part of computer science and mutable data structures in general.

MacCarthy had another analogy: Lisp for programming is kind of like the advantage of using binary over decimal for digital computers:

> This internal representation of symbolic information gives up the familiar infix notations in favor of a notation that simplifies the task of programming the substantive computations, e.g. logical deduction or algebraic simplification, differentiation or integration. If customary notations are to be used externally, translation programs must be written. Thus most LISP programs use a prefix notation for algebraic expressions, because they usually must determine the main connective before deciding what to do next. In this LISP differs from almost every other symbolic computation system. COMIT, FORMAC, and Formula Algol programs all express the computations as operations on some approximation to the customary printed forms of symbolic expressions. SNOBOL operates on character strings but is neutral on how character strings are used to represent symbolic information. This feature probably accounts for LISP's success in competition with these languages, especially when large programs have to be written. The advantage is like that of binary computers over decimal - but larger. [History of Lisp -> LISP prehistory - Summer 1956 through Summer 1958.]

"Lambda Calculus is perhaps the Maxwell's equations of computability, not of the computer field." I agree with you.

"What Kay might have meant is that Lisp is the Maxwell's equations of programming a computer to do something useful." But what I discovered is that lambda calculus + S-expressions define a consistent infrastructure on which useful superstructures can be built, data structures (pairs, trees, lists,...) and data controls (recursion). And make implementation a pleasure, either via AST (lambda code) or via regexps {lambda talk}.

Reply on news.ycombinator.com