Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

List out of Lambda

stevelosh.com

Post reply on HN
Print view View original

31–40 of 49 posts

Re: List out of Lambda

#31

Post by Cushman »

bcoates wrote: post #27
Cushman wrote: post #23

It'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 th…

This celebrated discussion goes into some nice detail about object-closure equivalence: 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…

That is a much more eloquent version of what I was getting at, thank you :) To be clear, I don't really think closures are "bigger" conceptually either. I can't properly recall a time I understood one and not the other... It may be that understanding of both came simultaneously, as a humble student in a single moment of enlightenment.

Re: List out of Lambda

#32

Post by Bjartr »

arianvanp wrote: post #15
peter-fogg wrote: post #5

Earlier quoted context omitted.

It 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.

have you got any sources telling about this? I can't seem to find any. Would be a nice read

Here's the official NASA JPL C coding standard

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

Page 10 describes loop bounds and recursion limitations.

Re: List out of Lambda

#33

Post by acjohnson55 »

aethertap wrote: post #26
Cushman wrote: post #23

It'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 th…

I'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…

Inheritance 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.

Re: List out of Lambda

#34

Post by jfarmer »

fyi80 wrote: post #18

I 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.

I have a degree in mathematics from the University of Chicago. Want to talk about self-adjoint algebras of compactly supported continuous functions? I'm your man.

I also think teaching this using mathematical notation would be a mistake. People only learn things when they relate in part to something they already know. The original lambda calculus syntax is not only abstract, it was invented before programmable computers existed.

Unless someone is either already comfortable with mathematical notation or has a background in a programming language with similar concepts (Lisp, Haskell, etc.), it's going to be a stretch to teach someone the lambda calculus -- really teach them -- unless it's framed in terms of a language they already know.

JavaScript is a great language to use for this because it has C-like syntax, which virtually all programmers understand, and first-class functions. You could use Ruby, too, but the syntax would be even more opaque.

Here's someone building the lambda calculus using only Procs in Ruby: http://codon.com/programming-with-nothing

Then using Ruby 1.9's "stabbby lambda syntax" you get

    -> x { -> f { f[x] } }
Not sure that's any better. The key is explaining it in terms of something the ready already understands well.

If they're not already thinking mathematically a straight-forward introduction to the lambda calculus would be ineffective.

Re: List out of Lambda

#35

Post by munificent »

tmhedberg wrote: post #20
fyi80 wrote: post #18

I 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.

Agreed. 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

The grouping of expressions is clearer to many readers in the JS example. Unless you've spent a decent amount of time grokking the lambda calculus, the second line could be any of:

    (λx. (λf. f)) x
    (λx. (λf. f) x)
    (λx. (λf. f x))
The lambda calculus notation is weird. Using "." to separate parameter and body is unusual. The scope of the body isn't obvious.

JS is painfully verbose, but it's a verbose syntax many people have already put the time in to internalize.

Re: List out of Lambda

#36

Post by tome »

kenko wrote: post #19
TeeWEE wrote: post #2

For 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 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.

Losh 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.

There 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".

Re: List out of Lambda

#37

Post by tome »

ufo wrote: post #30
kenko wrote: post #19

Earlier quoted context omitted.

Losh 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.

I 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.

Also this encoding is cool:

http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h...

Re: List out of Lambda

#38

Post by tome »

munificent wrote: post #35
tmhedberg wrote: post #20

Earlier quoted context omitted.

Agreed. 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

The grouping of expressions is clearer to many readers in the JS example. Unless you've spent a decent amount of time grokking the lambda calculus, the second line could be any of: (λx. (λf. f)) x (λx. (λf. f) x) (λx. (λf. f x)) The lambda calculus notation is weird. Using "." to separate parameter and body is unusual. The scope of the body isn't obvious. JS is painfully verbose, but it's a verbose syntax many people…

Put the brackets in the lambda syntax then. It would be unambiguous and still clearer than the Javascript syntax.

Re: List out of Lambda

#39

Post by twoodfin »

aethertap wrote: post #26
Cushman wrote: post #23

It'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 th…

I'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…

I'm pretty sure this is an extended discussion/exercise in SICP.

Re: List out of Lambda

#40

Post by tardigrade »

Solid 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.
Post reply on HN