7 ms·
List out of Lambda
- TeeWEE 14y agoFor people who are interested. The theoretical foundations for this is lambda-calculus created by Alonso Church. Encoding integers with lambda is called the curch encoding: http://en.wikipedia.org/wiki/Church_numerals http://en.wikipedia.org/wiki/Church_numerals Functional programming in general is built upon the foundations laid out by him. Actually the domainname of hackernews (ycombinator) has a lot todo with lambda calculus.
- arethuza 14y agoAll you need is S and K - all the rest is syntactic sugar, even Y. :-)
- arianvanp 14y agoSKI combinator is indeed another explanation of why the λ-calculus is turing complete : http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus
- masklinn 14y agoAnd for a pretty nice demonstration of (untyped) lambda calculus, http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing
- arianvanp 14y agoFor anyone curious of the λ-calculus, and why the Y-Combinator plays an important role in the turing completeness of this, please check out the excellent Y-not series by Jim Weirich[0] [0] http://www.neo.com/2012/11/13/y-not-adventures-in-functional-programming-part-i http://www.neo.com/2012/11/13/y-not-adventures-in-functional...
- kenko 14y agoLosh doesn't use Church numerals, though, he represents numbers as lists. The fact that lists are also represented as functions is a diversion; his number three doesn't represent a function f -> x -> x that returns the threefold composition of its first argument applied to its second.
- ufo 14y agoI didn't get too much into the original article but my impression is that he is using Scot encoding (essentially a 1-to1 translation of pattern matching) instead of church encoding (somethign equivalent to folds). Scott encoding doesn't get much publicity but its perfectly valid and much more intuitive, IMO.
- tome 14y agoAlso this encoding is cool: http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h...
- tome 14y agoThere must be some confusion here. For "the threefold composition of its first argument applied to its second" the type should be "(x -> x) -> x -> x".
- kenko 14y agoRight, I was (stupidly, it was early!) just using "f" as a shorthand for a function type like x -> x.
- Millennium 14y agoTuring-completeness, of course. After that, it's all a matter of allowing you to stay as focused as possible on the task at hand: some reasonable way to express your chosen paradigm, library support for things ancillary to your actual task, and some measure of support in the tools you find useful.
- sfvisser 14y ago> Turing-completeness, of course. Lots of useful programs can be written without turing completeness. It can be useful, but only for a limited problem domain.
- peter-fogg 14y agoIt actually can have some benefits -- a language without any unbounded loops or recursion isn't Turing-complete, but you do get a static guarantee of termination. NASA, for example, writes much of their C code only with bounded recursion. So they can't compute some things, but they can be sure that the Mars lander never gets stuck in an infinite loop.
- arianvanp 14y agohave you got any sources telling about this? I can't seem to find any. Would be a nice read
- Bjartr 14y agoHere's the official NASA JPL C coding standard http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf Page 10 describes loop bounds and recursion limitations.
- arethuza 14y ago"Lots of useful programs can be written without turing completeness." Including Bitcoin transactions - I learned this from elsewhere on HN today. FYI: https://en.bitcoin.it/wiki/Script https://en.bitcoin.it/wiki/Script
- McUsr 14y agoSeriously, what I need in a programming language depends on what I intend to achieve with it. I use blocks in Objective-C and "closures" in Applescript. to lambda(aStatment) script intern say aStatment end script end lambda set a to lambda("applescript…") set b to lambda("knows how to …") set c to lambda("make a closure if not a lambda…") tell a to run tell b to run tell c to run
- deleted 14y ago[deleted]
- mjt0229 14y agoIt's better to think of map without thinking of looping. I think its a good idea to think of it as converting a container of A to a container of B. It doesn't matter how it happens, and the container might be empty, or only big enough only to hold 1 item. Loop is beside the point.
- GhotiFish 14y ago"If you ignore the practical issues of computers like size, weight, cost, heat, and so on, what do you really need in a programming language?" One instruction https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
- fyi80 14y agoI get that JavaScript is a popular language, but burying a fundamental concept under a cluttered and confusing syntax like JavaScript, when it's much cleaner to explain the math using sensibly notation. Ugh. It's nice that Steve is reaching down to his audience, but it would be nice for the audience to step out of their muddy sandbox once in a while.
- tmhedberg 14y agoAgreed. I can't understand how something like function(x) {return function(f) {return f(x);};} can be considered easier to comprehend than λx. λf. f x
- mamcx 14y agoNot everyone is used to read that math notation. Is like say: "Why put it in JS instead of assembler?". JS is probably the most universal language out there (at least in terms of widespread). I prefer this stuff in python. Less syntax, more clear. But then, is the same thing: You imagine your (math) syntax is better, I think is python, somebody will complain why not haskell, but js is more practical. Or, is just the one the OP like. That is probably the only and best reason.
- tmhedberg 14y ago> Not everyone is used to read that math notation. Agreed, but it doesn't take more than a couple of sentences to describe the entire syntax of the λ-calculus. It's not hard to pick it up even if you've never encountered it before. Contrast that with JavaScript, where even as someone who has written my fair share of it, my eyes tend to glaze over when they hit a string of `});}))());};`. Yet people happily write that sort of thing, then turn around and complain about nested parentheses in Lisp!
- mrspeaker 14y agoIn current Firefox nightlies (and soon everywhere (i.e. Firefox AND Chrome)) it's just: x => f => f(x) http://wiki.ecmascript.org/doku.php?id=harmony:arrow_function_syntax http://wiki.ecmascript.org/doku.php?id=harmony:arrow_functio...
- Cushman 14y agoIt's always cool to see an accessible demo of the lambda calculus, but to nitpick... Isn't it cheating a bit to say this doesn't use Object when, in JavaScript, the persistent arguments object exists and is even explicitly accessible? You're just hiding Object instantiation behind function calls, and using syntactic sugar to access the local object. I'm not totally sold that objects are a "bigger" language feature than closures, conceptually.
- aethertap 14y agoI'm having to reach back into the dustbin of my mind, but I seem to recall implementing an object system using only closures at one point. As I recall, it had all of the "normal" features of objects - inheritance, member variables, methods, etc. It was done with closures and the members were accessed in a message-passing style (in scheme, (myobject 'show) for example). Based on that, I think that closures and objects are probably equivalent in their expressive ability. Could be wrong though, like I said it was a long time ago.
- acjohnson55 14y agoInheritance can be a bit tricky to fit in, as I recall, but it's quite elegant to implement basic classes and objects with just closures.
- pjscott 14y agoA very simple and elegant way to handle inheritance is to give each object a pointer to another object -- let's call it "prototype" -- and delegate any failed member variable or method lookups to the prototype. This is how JavaScript's object system works.
- twoodfin 14y agoI'm pretty sure this is an extended discussion/exercise in SICP.
- bcoates 14y agoThis celebrated discussion goes into some nice detail about object-closure equivalence: http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg03277.html http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/m... If you're too impatient, here's the punchline: The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures." Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress. On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
- tapichu 14y agoI'm a bit turned off by the syntax, but lambda calculus is always fun
- tardigrade 14y agoSolid intro into the lambda calculus. Wasn't so into the js examples, but after reading the other comments, I can totally see how a functional/mathematical syntax would have been very disorienting for someone not familiar with the lambda calc. Since those people are obviously the target audience, js seems fitting.
- cycomachead 14y agoHaving used scheme before, and gone through some of SICP, it was neat to see the topic expressed in JS. I think it came through fine, though I'll always have a love for Scheme!
- justatdotin 14y agogreat read, thanks for sharing.