PG on the cover of Forbes

Post by axod » Fri, Nov 19, 2010, 10:35 PM UTC

timtadh wrote: post #60

axod wrote: post #48

Earlier quoted context omitted.

Loops are how most people think. They're also how most CPUs think. It seems to me logical for both parties to express programs mostly using loops.

Except there is no difference at the machine instruction level between a recursive and iterative approaches. They are isomorphic to each other. That is why you can implement all recursive algorithms using an explicit stack and a loop and all iterative algorithms as recursive functions.

Post by sesqu » Sat, Nov 20, 2010, 12:14 AM UTC

perlgeek wrote: post #26

evanrmurphy wrote: post #18

Earlier quoted context omitted.

> Heh... completely wrong, but I suppose it's the best you can expect a non-techie/math nerd readership to get. Heck, it's probably close to the most you can expect the average programmer to get. How would you explain the Y Combinator to the Hacker News readership?

There have been explanations for the HN readers. Here's one that I'd put in a non-techy newspaper: The Y Combinator is a way to make computer code self-referential without having to introduce names for parts of the code. Or a bit less accurate: The Y Combinator is a clever way to make computer code self-referential.

Post by axod » Sat, Nov 20, 2010, 7:59 AM UTC

smanek wrote: post #62

axod wrote: post #40

Earlier quoted context omitted.

Why is it an issue though? Recursion is an optional thing some programmers like using. It's not necessary. edit: rather than downmod me to -1 for stating a fact, why not reply?

That's like saying integers are an optional thing, and it's no big deal if your programming language doesn't have them. True, they aren't necessary (look at peano arith or pure lambda calc) - but it sure makes things a lot easier. It's much more concise and intuitive to write some search or divide and conquer algos recursively than imperatively.

Post by [deleted] » Sat, Nov 20, 2010, 3:45 PM UTC

axod wrote: post #61

timtadh wrote: post #60

Earlier quoted context omitted.

Except there is no difference at the machine instruction level between a recursive and iterative approaches. They are isomorphic to each other. That is why you can implement all recursive algorithms using an explicit stack and a loop and all iterative algorithms as recursive functions.

Huh? There's a lot of difference in the unoptimized form of recursion - namely stack usage. Yes you can hack together tail call recursion to try and make recursion perform as well as iteration does, but what really is the point?

Post by tlrobinson » Mon, Nov 22, 2010, 6:56 PM UTC

tlrobinson wrote: post #31

eliben wrote: post #24

Earlier quoted context omitted.

The Y combinator is a programming construct allowing one to write recursive functions without explicitly calling themselves (unnamed recursive functions): (define Y (lambda (X) ((lambda (procedure) (X (lambda (arg) ((procedure procedure) arg)))) (lambda (procedure) (X (lambda (arg) ((procedure procedure) arg))))))) (define F* (lambda (func-arg) (lambda (n) (if (zero? n) 1 (* n (func-arg (- n 1))))))) (define fact (Y…

I took the liberty of translating this to JavaScript, primarily to help me understand it, but thought I should share: // (define Y // (lambda (X) // ((lambda (procedure) // (X (lambda (arg) ((procedure procedure) arg)))) // (lambda (procedure) // (X (lambda (arg) ((procedure procedure) arg))))))) var Y = function(X) { return (function (procedure) { return X(function (arg) { return procedure(procedure)(arg); }); })(fu…

    var Y = function(X) {
        var Z = X(function(arg) {
            return Z(arg);
        });
        return Z;
    }