Lambda the Ultimate

The all and any look nice but I don't understand why they need to be builtins. Some restriction on how generator expressions can be used, or?

Today I feel like (reduce append list-of-lists) is a pretty subtle piece of code.

I've just written some code to automate evaluation of a student project. One crucial part is a search over a directory tree for submitted code. This is naturally expressed as a fold.

My problem with GvR's reasoning is his desire to drag everyone down to his level of ability. That certainly doesn't lead to a language I want to program in.

I don't think it's exactly a question of ability - I mean, I dare say GvR could transform himself into a Haskell ninja if he had a mind to. Plenty of other Pythonistas have managed it.

I think the problem, if it is a problem, is that Python is intended as a single-paradigm language, and that paradigm isn't functional.

There is a niche for a dynamically-typed, "impure" functional language with a simple syntax and broad library support. And that niche is filled by PLT Scheme.

I refer to this quote:

almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do

It's not a problem I've ever had... It just takes some time to learn the pattern of using fold, just like you have to learn the patterns of using generators, or objects, or anything else.

One crucial part is a search over a directory tree for submitted code. This is naturally expressed as a fold.

I don't find this natural at all. I'd implement it as a filter over an iterator/generator.

an inside out fold!

Advantage Noel. If Python was serious about having many ways to do things...

Someone ought to write up an accessible-to-imperative-programmers explanation of the relationship between fold/unfold and generators. It would make a good Wikipedia article...

It's Perl's philosophy to have "many ways to do things". The Python philosophy has general leaned towards "one clear, idiomatic way to do things". At least that's been my impression.

Start at the top of Continuations and delimited control.

But it's much nicer to create a generator for all data types, and then define map, fold and filter in terms of generators, with list comprehensions.

I think it's the bananas paper in practice.

(defmethod lipschitz-value-function ((csg-union csg-union))
  (let ((blending-function (or (blending-function csg-union)
                               (constantly 0.0))))
    (reduce #'(lambda (value-function1 value-function2)
                #'(lambda (position)
                    (let ((value1 (funcall value-function1 position))
                          (value2 (funcall value-function2 position)))
                      (- (min value1 value2)
                         (blend-value blending-function value1 value2)))))
            (unioned-surfaces csg-union)
            :key #'lipschitz-value-function)))

Oh, I have similar expressions for intersection and difference. I thought about abstracting things a bit so I'd have only one reduce instead of three, but I didn't feel it was worth it.

.. but let me just grab a pen and paper to figure out how that's supposed to work. ;-)

OK, I agree this is cool, but union really is the sum for surfaces isn't it? And intersection the product. How do you do difference for a list of surfaces? (Or difference of a list of anything for that matter.)

OK, I agree this is cool, but union really is the sum for surfaces isn't it? And intersection the product.
I'm not sure what you're getting at.

How do you do difference for a list of surfaces? (Or difference of a list of anything for that matter.)
The way Common Lisp does it for numbers: left associatively. (- a b c d) == (- (- (- a b) c) d).
If I wanted something to be right associative, I'd have to use reduce with the :from-end t option.

Since the haskell uses I have on hand are pretty arcane, here's the use I had of python's reduce sitting in my sent-mail folder.

The problem in question was an investigation of various methods to turn a floating point number into a fraction. (rational number) Anyway, I wrote it in python because I was playing around with python at the time.

In general in this program fractions are represented as a tuple of (numerator, denominator) - however, even if I had gone and defined a class and overloaded +, I'd still need reduce or something like it because ... well, just look at the code:

def stdMethod(x, tol=defaultTolerance):
    L = [int(x)]
    x = x - int(x)
    maxerr = x
    while (maxerr > tol):
        x = 1/x
        next = int(x)
        L.append(next)
        x = x - next
        maxerr = x * maxerr / float(next)
    # *****
    L.append((1,0))
    L.reverse()
    return reduce(lambda x,y: fadd((x[1],x[0]),(y,1)), L)

This code builds up a long continued fraction, eg: 4 + 1/(3 + 1/(2 + 1/(5))). In the code, this would be represented by L = [4, 3, 2, 5] at the point marked *****.

Anyway, reduce is then exactly what I need to convert this list of integers into a rational number. Even had I used a class and overloaded +, I still would want to let the last few lines be:

    L.reverse()
    L[0] = Rational(L[0])
    return reduce(lambda x,y: y + 1/x, L)

Interesting. I think your second example is different from the first; I think you misread your original code when you wrote this post.

I think your example 4 + 1/(3 + 1/(2 + 1/(5))) is wrong; I think you mean 1/(4 + 1/(3 + 1/(2 + 1/(5)))). In which case your second example should have been:

return reduce(lambda x, y: 1/(x + y), reversed(L), 0)

Without reduce(), it looks like this:

r = Rational(0)
for i in reversed(L):
    r = 1/(i + r)
return r

I think your example 4 + 1/(3 + 1/(2 + 1/(5))) is wrong;

Why do you suppose that?

I think you mean 1/(4 + 1/(3 + 1/(2 + 1/(5)))).

But then his list would be L=[0,4,3,2,5] and not L=[4,3,2,5]. I'm sure his specification is correct, because it folows the conventions of the compact abbreviated notation for simple continued fractions. I didn't verify his code, but the conversion of the list L—the compact abbreviated notation for simple continued fractions—into floating point notation looked correct to me. Correct me if I'm wrong, but it looks like your code will interpret the list [4,3,2,5] as [0,4,3,2,5]. In fact your code will interpret every list as having an implied 0 as the first element, in which case you cannot represent continued fractions greater than one. However, as far as I am aware, there is no such restriction on continued fractions.

It seems you could parallelize an associative fold rather easily - an explicit accumulation loop, maybe less so.

That's the point. You can only parallelize associative fold. And Guido says in Python only + and * are associative, and then sum() and product() are much easier to read.

It seems Python's priority is neither performance nor parallel performance, so perhaps that was a red herring.

People do tend to use specific libraries for parallel code, but it would be nice if parallel-friendly constructs were an encouraged part of the basic idiom.

I sure wish C++ had lambdas

There's always Boost.Lambda

Phoenix, which is also in Boost via Spirit; or FC++, which also gives you monads and almost a complete Haskell standard prelude.

If you want to do functional programming in C++, you have a lot of perfectly viable options.

if you don't mind:
- extending functional expression libraries to you custom types when necessary
- reverting to a more explicit solution whenever your compiler fails to do template expansion because of some shortcoming in the library implementation or the standard or an obscure combination of both
- reverting to a more explicit solution whenever your compiler fails to do template expansion because of non-compliant implementation
- trial'n'error development cycle because of nonsense page-long compiler errors
- O(n^x) compile time
- unclear syntax
- ...

existing lambda libraries are a cool showcase for the power of the c++ language, but not a feasable replacement for first-class lambda for any but the trivial case.

there is (still) hope for lambda becoming a first-class citizen of c++...

>>> def f():
...     if 1:
...             def g():
...                     print "test"
...     g()
...
>>> f()
test

It seems you could parallelize an associative fold rather easily - an explicit accumulation loop, maybe less so.

I don't understand this. Aren't the two are equivalent? Seriously.

In either case, the main problem is proving that the operation is associative and without side effects. In an extremely dynamic language like Python (where there's no static type information, and classes can be modified at run time, and there's operator overloading, and the reduce() builtin could be replaced at run time with something else), I just don't think it's realistic. It's totally impossible at compile time; and exceedingly difficult and expensive at run time.

And even if all those stars happen to align, the case for parallelization is still bad in CPython, since the implementation can only use one CPU at a time anyway (due to the Global Interperter Lock).

Actually, the idea of aggressively optimizing this seems a little far fetched to me to begin with. Do any Common Lisp implementations actually optimize reduce this way? The definition of reduce does not require the caller to guarantee associativity; there are even some non-associative examples.

...or at least deliberately hobbled, to limit its expressive power so that people will use alternative means of expression.

A proper anonymous function syntax would be an acceptable replacement. But I don't know if we'll get one.

reduce probably won't be much missed - there's very little Python code out there that uses folds the way true a true FP origamist would use folds. But I would miss the ability to write HOFs like reduce very much.

Not to mention Python's so-called `lexical scoping'. What a bunch of jokers the python language designers are.

Python is following very closely java footsteps: having just one formal way to do things, adding some metadata in the form of @attributes ( called 'function decorators' in python ), the need to declare classes to cope with the broken lexical scoping...

Perhaps they are trying to go after Java programmers at all costs?

it's coming out very depressing of late...

The "function decorators" are not that much attributive metadata but usually higher order functions that take the decorated function as an argument and return another function. The decorators are executed when the decorated function object is created.

Example: If a method f() is decorated by @classmethod a new function object f = classmethod(f) will be created. This mechanism can be used to attach certain attributes on the function of course:

def addfuncattr(attr,value=None):
def wrap(f):
setattr(f,attr,value)
return f
return wrap

@addfuncattr("some_attr",42)
def foo():pass

"The "function decorators" are not that much attributive metadata but usually higher order functions that take the decorated function as an argument and return another function."

... you "decorate" them with meta-data. :)

Personally, I'm beginning to like Matz's guiding philosophy more - programming should be an exercise in coolness.

I think programming should be an exercise in communication.

Plug: SuperCollider is like Ruby or Smalltalk, has list comprehensions, collect, select, inject (map, filter, fold), allows passing multiple blocks outside the parens. "if", "while", "for" are message sends, not built-in control structures.
http://c2.com/cgi/wiki?SuperCollider

if (x, { a }, { b })
is equivalent to:
if (x) { a } { b }

while({ a }, { b })
is equivalent to:
while { a } { b }

I looked up list comprehensions and, as a ruby hacker, I couldn't see why you would bother with them when functions like map() work just as well and don't require special syntax to be added. Then I realized that ruby's map() takes a block, and python's doesn't.

Yeah, but list comprehensions came from Haskell, which doesn't have that problem.

Have you looked at LINQ? Why have query comprehensions when you could write out all those method calls explicitly?

The answer is that syntax matters. You could write

x = swap . (concatMap .) . (. swap map) . swap (.)

but it's clearer to say

x f as bs = [f a b | a <- as, b <- bs]

Goopy is somewhat underwhelming - they seem to have interpreted "functional" as meaning "doing things with lists" - more often than not through explicit iteration. Not many HOFs around. Not that that's bad - for Python - but Goopy doesn't make a great counter-example right at the moment...

You are right about it being underwhelming, but I think it does make a point. First, they use HOF, and these are easier to use when you have lambda. Second, contrary to GvR, for them "functional" isn't a dirty word...

Definitely google loves map & reduce, but I guess they did not do this in python :)

I'd like to use this in my Plone/Zope paying work, could you add an explicit license so I'm able to do so?

--Shae Erisson - ScannedInAvian.com

I should point out that I don't recommend it for production use - it's never been tried with an input of significant size or a parser of significant complexity, and I'm not certain I understand either the space or time complexity of its operation (it's hard enough in Haskell...).

At the very least, I would test and tune it first.

Still, if you think you can use it, why not? I would normally attach a GPL notice, but if that's problematic I can make an exception (whatever goes nicely with Python/Plone/Zope, I guess).

If it doesn't have unit tests it's just opinion.

(I think that's a misquote of Heinlein?)

--Shae Erisson - ScannedInAvian.com

>>> reduce(lambda x,y:x+len(y), ["hello","there","everybody"], 0)
19

>>>help(reduce)
reduce(...)
    reduce(function, sequence[, initial]) -> value

If you don't like Guido's direction, don't use Python.

If this was the only available approach to language designers, I would have only this to say:

Sic semper tyrannis!

Histrionics aside, i believe it is reasonable for a language community to expect their knowledge and practice in that PL to remain monotonically increasing.
(i.e. you don't have to unlearn previous knowledge or undo previous programs.)

I can see if a feature was broken, and caused major problems in programs that used it, it would be reasonable to make a non-monotonic change.

But to arbitrarily remove features because they seem unaesthetic in retrospect seems guaranteed to erode a PLs credibility as a serious language for use in real apps.

One interesting phenomenon I've long observed is that many programmers think that every language should be like their favorite.

Is this unreasonable? If you like a language because of certain features, you consider those features good. Then of course their absence from another language will be bad (unless there is some mitigating good added instead).

Python serves a niche, and serves it well.

What is that niche? Pythonistas seem to tout it for a pretty wide range of purposes.

Bjarne Stroustrup famously quipped "If you want Smalltalk, you know where to find it."

That sounds like "let them eat cake". (I'm full of revolution today.... ;-) )

I really don't see what is wrong with asking PL designers, especially ones with clout, to try to make their languages "good" for a well-articulated, theoretically sound value of "good".

They can of course respond with a better-articulated, more theoretically or design-philosophically sound response, but "because I said so" is not such a response.

There are times when you need to throw things away.

I don't keep a bottle of bluing in my laundry room, now that modern bleaches do the same job better. There may be a place where bluing would be better for my laundry, but nobody keeps it around so even where it is better we don't use it.

We are talking about Python3000. That is the next MAJOR version. The reason for a major version is to break backward compatibility in some way - in the process correcting mistakes. Since reduce is used so rarely in python programs it is time to re-think the decision to use them.

Python's goal is to be readable above all else. I have no doubt that a good LISP hacker can write from scratch something faster/better than a good Python hacker could write the same thing. However with python the code will be much easier to read when he is done.

If you like a language because of some features, that is fine. However you should broaden your mind to other ways.

Reduce and map in python are not as powerful as other languages that have the same features. Python has a different way they want you to do things. This is not good or bad, it is different. (Overall. Where the python way won't work python is clearly worse, but where the python way works you can argue it is better for readability.)

I have been doing some serious python work for over a year now, and I have never found a need for map or reduce. There are python alternatives that are easier to use and understand. I found a use for lambda exactly once, and could have done a full function just as easy then. While everyone is different, I think my experience is typical of python programs. (That is Python programmers using 2.4, early versions of python lacked some of the alternatives I'm using)

There's more to it than people trying to impose favorite features across languages. In the same way that modern mainstream media tends to dumb down the electorate, we're seeing mainstream languages dumbing down programmers. An average programmer who primarily uses a single language has to go to a lot of effort to learn about features outside their chosen language. That may not matter in many cases, but it can matter much more when the features in question are actually a natural fit for the language they're using — then it becomes as though they're learning a pidgin language instead of the real language(s) it's based on.

Python is training large numbers of programmers to think inside a box which is now threatening to become even more restrictive. That's not doing most of those programmers any favors. It's fine if those programmers recognize that, and expand their intellectual and professional horizons with other languages, but that doesn't always happen. For many of those who don't make that leap, GvR is doing them a disservice. That can have a broader impact, too — the Python community is large, with a diverse set of stakeholders, and it interacts with other language communities in various ways.

Python serves a niche, and serves it well. Like anything, if it fails to continue serving the niche, it risks being replaced.

Is it just me, or is there a larger trend of an anti-FP backlash within the Python community (or at least some elements thereof)? There was the brouhaha on tail-call elimination a while back (along with claims suggesting that TCE is not necessary in languages with mutable variables, as it's primary use is to allow efficient implementation of iteration via recursion in single-assignment languages that can't implement it directly--or something like that). Guido (in the referenced posting) suggested that you don't need lambdas when you have objects (which is technically true--objects and lexical closures are known to be equivalent--but there are many times when one or the other is more syntactically convenient). And then there's the debate on introducing static typing to the language...

Python is, in many ways, a philosophical descendent of Smalltalk--complete with the belief that mutability of a program ought to be maximized rather than minimized. Which is at odds with the philosophies underlying FP--which include the belief that constraints upon the programmer which increase the compiler's ability to reason about a program's behavior are a good thing.

Maybe I'm extrapolating the curve far beyond the sample set (and I hope I am)... but it would be a shame for this sort of thing to occur. But that said (the point of my original post)--the Python community ought to tailor the language to fit their needs. If the result doesn't meet the needs of other programmers, so be it.

Is it just me, or is there a larger trend of an anti-FP backlash within the Python community (or at least some elements thereof)?

I think it's more pragmatic than that. Python has integrated key elements of FP: lists, tuples, unpacking of structures, returning complex types. When I was first exposed to FP (via the language Hope), what impressed me the most was the way lists were tossed about without any concern about what memory actually looked like. That's now part of the foundation of Python.

I don't think that deeper FP has truly proven itself. I don't mean that as flame bait; I've gotten to where I prefer FP for many things. But look at all the constant bickering in comp.lang.functional. Look at how short the lists of real world functional programs tend to be. (Erlang is the poster-child to a great extent, being used in high-end telecom systems, but then there's always debate about whether or not Erlang is functional because its concurrency model is impure).

In short, I think that the useful parts of FP have been integrated into the mainstream, while other parts have proven to be too esoteric (that is, they're beautiful from a purist's point of view, but there lots of other approaches as long as you don't mind veering away from being mathematically pure).

All languages make you think inside a box. That's why you have to learn many languages to gain a real, broad understanding of programming. Purity is inversely proportional to box size.

or languages that develop significant clout so that you can be forced by circumstances other than preference to use them? C++ has that clout, Java has it. Python is moving to that position, and while so moving is dropping abilities that made it palatable to Functional programmers (somewhat an hyperbolic statement)

A cynical person might wonder whether Python's move into mainstream popularity merely coincides with the deprecation of overt functional programming techniques. Or whether one is the cause and the other is the effect.

The two goals are not, of course, incompatible. In fact, Alan Kay has long said that late binding is key to building systems that can be rapidly modified, and that he thinks late binding is essential until software engineering becomes mature enough for that not to be a primary concern.

Python is just a descendent of ABC, a Scripting Language for Third-Grade Students, and that's all it will ever be. To wit: every Plone developer I know is telling me I should write a better CMS in the language I work on, and I can't blame them. Unsurprisingly, it's a Smalltalk descendent that follows this quote that you bring up, although I can't recall where it's actually from (or if it's from Alan at all).

James McCartney: I remember reading a quote I think from Alan Kay that the idea of Smalltalk was to shrink the assignment operator as far as possible and then encapsulate it.

water: Unsurprisingly, it's a Smalltalk descendent that follows this quote that you bring up, although I can't recall where it's actually from (or if it's from Alan at all).

The quote is definitely from Kay. I seem to recall that it's from a relatively recent ACM interview. It's been refreshing to me to read/listen to much of what Kay has said recently, because it's reinforced something that I feel is important, which is the intellectual debt that Smalltalk owes Lisp. As a friend of mine who wrote Bistro ("a place where people meet to share Java and Smalltalk") reminded me, people tend to place too much emphasis on classes in Smalltalk and overlook the other two important constructs: protocols and blocks, and blocks are just lambda. So even the granddaddy of OO languages (yes, I know about Simula; please don't post) had a fully capable functional subset. It only took C++ about 15 years to catch up...

I don't think that is the Smalltalk philosophy. I remember reading a quote I think from Alan Kay that the idea of Smalltalk was to shrink the assignment operator as far as possible and then encapsulate it.

Well, but it does make almost everything mutable, e.g. all collections, and even class definitions. The iteration protocol relies on side effects. Object initialization is done by creating an object with nil attributes and then changing their values.

Functional style can be found only in anonymous functions. But even here they used to have broken scoping rules (local variables shared with the method), tail calls don't necessarily run in constant stack space, passing a named method requires creating a wrapper block (or using a symbol but then it's incompatible with blocks), there are no Lisp-style lists, the syntax of block invocation is not pretty, etc.

IMHO Smalltalk is as far from functional style as Perl, Python and Ruby. That is, it provides most technical mechanisms necessary for FP, but its conventions and customs discourage it.

So why did Guido say that Python had lexical scoping, when almost nothing about binding can be determined for sure statically? I have to say I'm happy to see all the FP stuff being punted from Python, so that I don't have to hear the claim that "Python supports Haskell-like programming idioms" anymore.

I don't have to hear the claim that "Python supports Haskell-like programming idioms" anymore.

Ahem.

Actually, I kind of agree. I don't think it's a good idea to try to fake this stuff in a language that doesn't really support it terribly well. But I'd prefer to see it supported better than not supported at all.

Sorry to post to this old thread but I'm curious to know if these 'heaviside' are as powerful as the fold operator? For the basic +,- it seems to be, but what about when fold is generalized to data types other than lists? I've read in more than one place that map, filter, actually all relational algebra operators can be built from the fold operator...so this simpler notation of J and K are still as powerful as fold?

SoI think "+/" is the same as "fold(+,0)", but the notation you describe isn't as powerful, in general. (The full APL notation might have a real fold in it, but I don't know it so I can't say for sure.)

The reason is that your "Heaviside" operators need a unit for the function they are applied to, to act as a seed. That is, for addition (+), 0 is a unit -- x + 0 = x. For multiplication (*), 1 is a unit -- x * 1 = x. So there's a tradeoff; you can apply the / to fewer functions than fold, but it's terser.

But then what language does offer this sort of rigor?

Haskell is the "pure" FP language, though I wonder if you already know this and are asking a question that I don't quite understand. If you are looking for something that guarantees our software will never fail then you are looking for the impossible. Even programs that have been "proven" correct may have an error in the specification.

If you want even more rigor than Haskell provides, take a look here: A Comparison of Z, B, and VDM.

Python's docstrings are nice, but for them to work they have to be (1) present and (2) accurate.

That being said, I've often wished that more languages had ways to attach notes to code, rather than relying on specially marked comments.