List out of Lambda • Hacker News Board

Re: List out of Lambda

#11

Post by arianvanp » Fri, Apr 05, 2013, 1:57 PM UTC

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.

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

Re: List out of Lambda

#12

Post by mjt0229 » Fri, Apr 05, 2013, 1:59 PM UTC

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

Re: List out of Lambda

#13

Post by arianvanp » Fri, Apr 05, 2013, 1:59 PM UTC

arethuza wrote: post #6

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.

All you need is S and K - all the rest is syntactic sugar, even Y. :-)

SKI combinator is indeed another explanation of why the λ-calculus is turing complete : http://en.wikipedia.org/wiki/SKI_combinator_calculus

Re: List out of Lambda

#14

Post by martindale » Fri, Apr 05, 2013, 2:00 PM UTC

arethuza wrote: post #8

sfvisser wrote: post #4

Earlier quoted context omitted.

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

"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

Fascinating. What is this?

Re: List out of Lambda

#15

Post by arianvanp » Fri, Apr 05, 2013, 2:01 PM UTC

peter-fogg wrote: post #5

sfvisser wrote: post #4

Earlier quoted context omitted.

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

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

Re: List out of Lambda

#16

Post by GhotiFish » Fri, Apr 05, 2013, 2:02 PM UTC

   "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

Re: List out of Lambda

#17

Post by arethuza » Fri, Apr 05, 2013, 2:14 PM UTC

martindale wrote: post #14

arethuza wrote: post #8

Earlier quoted context omitted.

"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

Fascinating. What is this?

I saw a reference to Bitcoin transactions embedding executable content in another thread and was slightly taken aback:

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

Re: List out of Lambda

#18

Post by fyi80 » Fri, Apr 05, 2013, 2:40 PM UTC

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.

Re: List out of Lambda

#19

Post by kenko » Fri, Apr 05, 2013, 3:03 PM UTC

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.

Re: List out of Lambda

#20

Post by tmhedberg » Fri, Apr 05, 2013, 3:05 PM UTC

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