Friday, September 26, 2008

On writing Python one-liners.


# I'm off to the Oregon Shakespeare Festival for the weekend so no
# time to finish my Untangling series. But I do have time to post this...

# The other day someone asked me if it was possible to implement a
# certain task in one line of Python. My response was "yes, but you
# wouldn't want to." You can think of what follows as the demonstration
# that you really don't want to.

# The problem is, there are lots of Python constructions you can't
# do on one line: assigning variables, defining functions, using
# conditionals, recursion and so on. So it appears there's a limit
# to what you can do. Amazingly, all of these problems can be solved
# with the use of lambdas.

# One place you often want one line lambdas is in the use of the map
# function. So let's stick with that as an example and warm up with
# an easy example. Lets say we want to add 1 to all of the numbers
# from 0 to 19. We can write:

def inc(n):
return n+1

print "1.",map(inc,range(0,20))

# Lambdas enable you to write that as a one-liner:

print "1.",map(lambda x:x+1,range(0,20))

# Now what happens if we want to apply a function that uses a local
# (constant) variable. For example:

def f1(n):
m = 2*n+1
return m+m*m

print "2.",map(f1,range(0,20))

# We can eliminate the assigment by means of a function. m changes from
# being a local to a function argument:

def f2(n):
def g(m):
return m+m*m
return g(2*n+1)

print "2.",map(f2,range(0,20))

# But that seems to make things worse because now we have a function
# definition instead of a variable assigment. But we can eliminate
# that with a lambda:

def f3(n):
return (lambda m:m+m*m)(2*n+1)

print "2.",map(f3,range(0,20))

# And now we can write the whole thing as one big lambda:

print "2.",map(lambda n:(lambda m:m+m*m)(2*n+1),range(0,20))

# But what happens if we want to define a bunch of local functions
# inside our lambda? We can use the same technique. We (1) use
# lambdas to allow us to fake local variable definitions and
# (2) use lambdas to define the functions. So we can replace this:

def f(n):
def g(n):
return 2*n+1

def h(n):
return 3*n-2

return g(h(g(h(n))))

print "3.",map(f,range(0,20))

# with this:

print "3.",map(lambda n:(lambda g,h,n:g(h(g(h(n)))))(lambda n:2*n+1,lambda n:3*n-2,n),range(0,20))

# We're passing in lambdas as arguments to a lambda so that they
# get bound to g and h.

# But what happens if we want a recursive definition like:

def fact(n):
if n<=1:
return 1
else:
return n*fact(n-1)

print "4.",map(fact,range(0,20))

# Because the function is bound to the name fact, we can refer to
# fact by name inside the defintion of fact. How can we do this in
# a one-line lambda? We can start by eliminating the self-reference
# in a fairly standard way. First rewrite fact so it doesn't call
# itself, but calls a function passed in as an argument:

def urfact(f,n):
if n<=1:
return 1
else:
return n*f(f,n-1)

# We can then make a factorial function by calling urfact with itself,
# allowing it to carry out the recursion:

def fact1(n):
return urfact(urfact,n)

print "4.",map(fact1,range(0,20))

# We can use urfact directly without fact1:

print "4.",map(lambda n:urfact(urfact,n),range(0,20))

# Now all we need is a one-liner definition of urfact. It's tempting to try:

def urfact1(f,n):
return {True:1,False:n*f(f,n-1)}[n<=1]

# But that results in non-termination because it evaluates *both* branches
# of the conditional. In a lazy language like Haskell, the branch not taken
# wouldn't be evaluated. But Python can be made lazy by using...you
# guessed it...lambda. The expression lambda:x is like a lazy version
# of the expression x. It doesn't get evaluated until you apply it as a
# function of no arguments, at which time it takes on the value x. So we
# can rewrite urfact as:

def urfact2(f,n):
return {True:lambda:1,False:lambda:n*f(f,n-1)}[n<=1]()

# And we get

print "4.",map(lambda n:urfact2(urfact2,n),range(0,20))

# Note how we use urfact2 twice, so we need the trick above for local
# definitions to get it down to one reference:

print "4.",map(lambda n:(lambda f:f(f,n))(urfact2),range(0,20))

# And now we can replace urfact2 with a lambda

print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n-1)}[n<=1]()),range(0,20))

# And that's enough for now. I expect that if we keep going we'll find
# way to rewrite any Python program as a one liner. You could probably
# even write a program to automatically 'compile' a usable subset of
# Python into one liners.

# But you probably don't want to do that.

24 Comments:

Blogger Clint Laskowski said...

this is bending my mind just reading it; nicely done

Friday, 26 September, 2008  
Blogger Stuart Dootson said...

You *can* do conditionals in 1 line in Python:

if n<=1:
return 1
else:
return n*f(f,n-1)

becomes

return 1 if n <= 1 else n*f(f,n-1)

Friday, 26 September, 2008  
Anonymous Anonymous said...

Have fun debugging! I'll stick with "normal" code thank you.

Friday, 26 September, 2008  
Anonymous Anonymous said...

In the case of assigning lambdas to local variables you can also do:

print "3.",map(lambda n:(lambda n,g=(lambda n:2*n+1),h=(lambda n:3*n-2):g(h(g(h(n)))))(n),range(0,20))

Friday, 26 September, 2008  
Blogger Mike Machenry said...

Also important to note is that people who would judge a programming language by the class of programs that can be written in one line in that language don't really deserve and answer to their question.

Friday, 26 September, 2008  
Anonymous Anonymous said...

I won't be the only one to notice this, but you are basically transforming an iterative program into a functional one. Your final Python looks a lot like Lisp, except that a Lisp program wouldn't need to be on one line.

Friday, 26 September, 2008  
Anonymous Anonymous said...

I won't be the only one to notice this, but you are basically transforming an iterative program into a functional one. Your final Python looks a lot like Lisp, except that a Lisp program wouldn't need to be on one line.

Friday, 26 September, 2008  
Anonymous Anonymous said...

Great post!!
I didn't even know about that lambda thing! Very interesting, very interesting...

Friday, 26 September, 2008  
Anonymous Anonymous said...

Don't you know about Python ternary operator ? It was introduced in Python 2.5...

(a if cond else b)

print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n-1)}[n<=1]()),range(0,20))

=

print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:(1 if n<=1 else n*f(f,n-1))),range(0,20))

Friday, 26 September, 2008  
Blogger matthew said...

hey, that's a pretty slick explanation of the Y combinator! honestly, i've never seen it developed so plainly.

Friday, 26 September, 2008  
Blogger Unknown said...

Some of these can be written more cleanly using some of the newer features of Python. You don't need map anymore, you can use list comprehensions, so things like

print "1.",map(inc,range(0,20))

Can be

print "1.", [inc(x) for x in xrange(0, 20)]

(And xrange instead of range because it does not construct a list in-place, but just a constant-memory iterator). And you have a ternary operator now in 2.5, so

def urfact2(f,n):
return {True:lambda:1,False:lambda:n*f(f,n-1)}[n<=1]()

Can be something like

urfact2 = lambda f, n: 1 if n <= 1 else n * f(x-1)

Which evaluates lazily so you don't need the extra () to avoid blowing the stack or even an [] access to the inline dictionary.

But yes, interesting introduction to this type of functional gymnastics that Python does well.

Friday, 26 September, 2008  
Blogger Andrew said...

Yes, but can you write the python script that compiles all other python scripts into one line of code in one line of code?

Friday, 26 September, 2008  
Blogger Jon said...

Clever, and very useful to think about from a pure CS standpoint, but from a getitdone engineering standpoint all this work wouldn't be necessary if python allowed braces to represent indent/outdent.

Friday, 26 September, 2008  
Anonymous Anonymous said...

Reminds me of http://www.nishiohirokazu.org/blog/2006/09/how_to_write_oneliner_in_pytho.html

Friday, 26 September, 2008  
Blogger Azrolboyz said...

thanks for sharing
azrolboyz

Saturday, 27 September, 2008  
Anonymous Anonymous said...

print "4.",map(lambda n:(lambda f:f(f,n))(lambda f,n:{True:lambda:1,False:lambda:n*f(f,n-1)}[n<=1]()),range(0,20))

You should try to write Perl one liners...

Saturday, 27 September, 2008  
Blogger Arnar Birgisson said...

I expect that if we keep going we'll find way to rewrite any Python program as a one liner

More than expect, I think you know :)

In fact, it is possible to encode any Lambda Calculus term as a Python one-liner like this. Since we know Lambda Calculus is Turing complete - we thus know we can write any program (not just Python programs) as a Python one-liner.

But yes... you probably wouldn't want to do that :)

Saturday, 27 September, 2008  
Blogger sigfpe said...

Stuart,

As you might guess, I'm not really a Python programmer, I just do it part time in my day job :-)

I didn't know about the one line conditional syntax. But it was a good excuse to demonstrate how to achieve laziness with lambdas.

Saturday, 27 September, 2008  
Blogger Unknown said...

Hmm, you could write a one liner that compiles python apps into one liners.
But I guess you would write the app to make one liners first, then run it on it's self?
Speaking of meta, pypy is rad.

Monday, 29 September, 2008  
Blogger seenxu said...

for sake of code readiness, I'd prefer more lines of code, or at least short one liner, rather than combined too many things in a quite long line.

thx for sharing

Saturday, 11 October, 2008  
Anonymous Anonymous said...

>> In fact, it is possible to encode any Lambda Calculus term as a Python one-liner like this. Since we know Lambda Calculus is Turing complete - we thus know we can write any program (not just Python programs) as a Python one-liner.

We can compute any computable function as a Python one liner.
To do interactive computation you need a bit more than lambda calculus.

Saturday, 11 October, 2008  
Anonymous Anonymous said...

self = (lambda f: (lambda *a,**k: f(f,*a,**k)))

fact1 = (lambda n: (lambda f,n: f(f,n)) (lambda f,n: n*f(f,n-1) if n else 1, n))

fact2 = self(lambda f,n: n*f(f,n-1) if n else 1)

Tuesday, 14 October, 2008  
Anonymous Unbelieveable Stuff said...

Nice One......

Tuesday, 22 December, 2009  
Anonymous John Tromp said...

A prime number sieve in nothing but lambdas:

import sys
(lambda y:lambda z:z(z(y(lambda p:lambda n:(lambda s:lambda z:z(lambda x:lambda
y:y)(lambda d:p(s)(y(s))(d)))(lambda x:lambda a:lambda s:lambda p:p(a)(lambda y
:s(n(x))(y))))(lambda c:lambda a:lambda s:z(lambda y:s(c)(y)))))(y(lambda p:
lambda b:lambda t:t(sys.stdout.write(b('.')('P'))or p))))(lambda f:(lambda q:q(
q))(lambda x:f(lambda y:x(x)(y))))(lambda s:lambda p:p(lambda x:lambda y:x)(s))

Sunday, 18 September, 2011  

Post a Comment

<< Home