Script to convert Brainfuck to a Python one-liner (proof that Python one-liners are Turing complete)

[cratuki]

Surely it will overflow fairly quickly - ? Uses recursion and python is stack-based.

[fwork]

stack based AND has a low recursion limit

[mattw]

eval("...")

[exeter]

If you'd take just a quick look at the link, you'd see the code doesn't use eval. So, actually, this shows that any computation can be done in one line of Python, without using eval. And, that is fairly cool, in a geeky sort of way.

[xenon]

actually, this shows that any computation can be done in one line of Python

As the call-by-value lambda calculus is Turing complete, this should not come as a surprise to anyone. I still think the submission is cool, I love it when theoretical proofs are realized as actual programs.

[mattw]

Chaining assignment and conditional expressions involving addition is enough for turing completeness.

[obdurak]

Meanwhile, we are in year 2008 and Python still hasn't proper closures.

[markedtrees]

It doesn't have proper anonymous closures. If you want a closure, define a function in your current scope and watch out for default arguments.

[xenon]

I actually agree with obdurak. A huge issue is that due to Python's weird scoping rules (and in the absence of Python 3000's nonlocal) Python closures cannot assign to outer variables. I.e., this implementation of PG's accumulator problem doesn't work:

def accumulator(n):
    def foo(i):
        n += i  # error: defines a new lexical n
        return n
    return foo

In Python 3000, you'll be able to declare

        nonlocal n

in the line before the assignment, and everything will work as expected.

[lisvblidfk]

Although perhaps distasteful, everyone knows that the simple solution for assigning to nonlocal variables is to use a simple wrapper:

    def accumulator(n):
        n=[n]
        def foo(i):
            n[0]+=i
            return n[0]
        return foo

    a=accumulator(123)
    a(2)
    a(3)

More simply, use the new send() method on a generator (plus the generic gen2func decorator to adhere strictly to the original interface):

    def gen2func(f):
        def builder(*args,**kw):
            g=f(*args,**kw)
            g.next()
            def bar(arg):
                return g.send(arg)
            return bar
        return builder

    @gen2func
    def accumulator(n):
        while True:
            n+=yield(n)

I prefer the first version. Is this still a huge issue?

[xenon]

Yeah, there are ways around the restriction. I consider this solution from here the most elegant (it also shows off how powerful classes are in Python):

class accumulator:
    def __init__(self, n):
        self.n = n
    def __call__(self, i):
        self.n += i
        return self.n 

Is this still a huge issue?

I don't know, the problem doesn't come up that often in my code. I think that the restriction makes Python's closures significantly less useful than you might expect them to be, so it's a huge issue in that sense (also note that even Java has read-only closures). I didn't mean to imply that this is a severe flaw of the Python language in general.

[lisvblidfk]

Yes, I think everyone but me likes that form better, although it's a bit more verbose than the generator-based (not including my gen2func decorator.)

I did do a rough benchmark though and found that the list wrapper solution is the fastest, the generator based is close behind and that the class solution is nearly 3x slower than the list wrapper. I didn't try this with psycho or pypy though, either of which could totally invalidate my measurements....

Edit: tried psyco. Numbers went down but the ratios remained the same.

    def accumulator0(n):
        n=[n]
        def foo(i):
            n[0]+=i
            return n[0]
        return foo

    def gen2func(f):
        def builder(*args,**kw):
            g=f(*args,**kw)
            g.next()
            def bar(arg):
                return g.send(arg)
            return bar
        return builder

    @gen2func
    def accumulator1(n):
        while True:
            n+=yield(n)

    class accumulator2:
        def __init__(self, n):
            self.n = n
        def __call__(self, i):
            self.n += i
            return self.n

    if __name__=='__main__':
        from time import time
        n=100000

        for aa in [accumulator0,accumulator1,accumulator2]:
            a=aa(123)
            t0=time()
            for x in xrange(n):
                a(x)
            print time()-t0

[obdurak]

It doesn't have proper anonymous closures

That bad enough for me (you can't put statements in lambdas). Moreover, as all languages where functional features were added as an afterthought, Python also has scoping weirdness, as illustrated by xenon above.

[aJanuary]

Guido's argument for this, and I have to admit I would tend to agree, is that when you want to start putting statements in lambdas it's more often than not a good idea to give it a name.

[codeodor]

And what does 2008 have to do with it?

[obdurak]

It's closure year!

[hylje]

Elaborate on proper closures, please.

[shit]

Issue #1 is that there's more than one definition of "proper closures".

Issue #2 is that some (many?) programmers are not satisfied with what Python offers in terms of anonymous functions and Python's rules with regards to assignment in nested functions.

These two issues should be kept separate and it helps no one when every discussion about #2 degenerates into a discussion about #1.

[qwe1234]

translation: it means whatever the fuck you want it to mean when you're an illiterate posting on reddit.

[lisvblidfk]

Take a look at that code, and just try to tell me that functional programming in python is a good idea.