15 ms·
Towards λ-calculus
- platzhirsch 8y agoLearnt 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.
- martyalain 8y agoI 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.
- deleted 8y ago[deleted]
- omegaMoo 8y agoSeriously though, why don’t people just program in minified JavaScript directly? It’s just easier to reason about what a program will do, when the expressions more closely model an equation, no?
- dcow 8y agoIt's easier to formally reason about a program that is specified in a small formal language than one that is sloppy, big, and leaks state, yes. When you can formally reason about a program you can prove correctness. And that's the ultimate goal. Minified JavaScript is not a fair comparison either. You can write scheme and lisp programs that are very readable. It annoys me when people conflate a terse and/or illegible programming style with functional programming. We have abstractions and large languages so that humans can better understand the intent of a program. Isn't that exactly what this post is about, making a more readable lambda calculus interpreter?
- twblalock 8y ago> It annoys me when people conflate a terse and/or illegible programming style with functional programming. The problem is, functional programming languages are almost always harder to read than other languages. Haskell is the obvious example, but Lisp is pretty bad too. It takes a bit of experience to be able to refactor in the middle of a Lisp block without messing up the balancing of the parentheses. Yes, it can be learned, and it can be learned faster than people expect. But the barrier to entry is much higher than it is for most languages. By the way, I love both Haskell and Lisp, and I think more people should use them. But I'm not going to pretend it's easy get started working with those languages. F# and other languages ML-style syntax are probably the easiest to read.
- gh02t 8y agoDepends on what is "easy" for you. Haskell is syntactically dense and can be obtuse in the hands of many authors, but on the other hand I find it easier to read well written Haskell because it's easier to break down into chunks. Similar for Lisp, keeping track of parentheses can be annoying but the regularity of S-expressions make it pretty easy to follow syntactically. I do agree it can be hard to get started in Haskell (though not so much Lisp, especially Scheme), but I think that's for other reasons that aren't really dependent on the syntax or readability. I think we can all agree APL is incomprehensible moon language, though /s.
- jrq 8y agoAPL fascinates me, but it's very hard to understand. I haven't found any intellectual footing as it's so dissimilar to what I've learned already. Would you have any good book recommendations? Or any recommendations, really? I'm just asking in the chance that you do.
- jacquesm 8y agoAPL really is no harder to understand than any other programming language, in a way it is easier than most because you can look at the whole program at once without being bothered by all the cruft of loops and such. You're probably mostly thrown off by the symbols. There was a gorgeous article submitted a couple of days ago: http://www.jsoftware.com/papers/50/ http://www.jsoftware.com/papers/50/ That should serve as a good intro.
- e19293001 8y agoFor 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/546bc3780db3a3c0f8d88b35e421ae4eec21.pdf https://pdfs.semanticscholar.org/d986/546bc3780db3a3c0f8d88b...
- lgessler 8y agoSeconded--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).
- arethuza 8y agoI 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].
- jacquesm 8y ago> 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.
- arethuza 8y agoIndeed, 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!
- lisper 8y agoFactorials in pure lambda calculus that actually run in non-geologic time: http://www.flownet.com/ron/lambda-calculus.html http://www.flownet.com/ron/lambda-calculus.html
- martyalain 8y agoSomething like http://lambdaway.free.fr/workshop/?view=NIL http://lambdaway.free.fr/workshop/?view=NIL
- lisper 8y agoThat is actually very cool. You should submit it to HN.
- martyalain 8y agoThanks. I did it 3 months ago without any comment. https://news.ycombinator.com/item?id=16202754 https://news.ycombinator.com/item?id=16202754
- lisper 8y agoA 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 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.
- martyalain 8y agoSometimes (quasi) re-submissions are flagged https://news.ycombinator.com/item?id=16066019 https://news.ycombinator.com/item?id=16066019
- martyalain 8y agoAnd sometimes they stay alone for ever: https://news.ycombinator.com/item?id=16983540 https://news.ycombinator.com/item?id=16983540
- martyalain 8y agoHello 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
- wiz21c 8y ago>>> 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 :-)
- martyalain 8y ago:) :) :)
- arunaugustine 8y agoFor some reason, this URL is blocked by Government of India: "Your requested URL has been blocked as per the directions received from Department of Telecommunications, Government of India. Please contact administrator for more information."
- deleted 8y ago[deleted]
- romanovcode 8y agoI 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.
- martyalain 8y agoIt'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?
- empath75 8y agoLambda 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.
- martyalain 8y agoIt'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 http://lambdaway.free.fr/workshop/?view=lambdacode ). In this other wiki page ( http://lambdaway.free.fr/?view=NIL 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.
- allenleein 8y agoFor people who wanna learn Functional Programming, I recommend this resources: https://github.com/allenleein/brains/projects/9 https://github.com/allenleein/brains/projects/9