Lambda the Ultimate

However, it seems to me the an "open source" language like Python is much better at bridging this gap compared to languages with traditional evolutionary models.

List comprehensions were the first thing I saw in Python that looked really cool. Iterator comprehensions would be even cooler. How about

[yield(fn(p)) for p in someList]

This would be equivalent to:

def iteratorComprehension():
   For p in someList:
      yield(fn(p))

[fn(p) for p in someList]

def listComprehension():
   accum = []
   for p in someList:
      accum.append(fn(p))
   return accum

Ahead? You must mean behind. List comprehensions were introduced by Turner in 1981 and appear in many functional languages, including not only Haskell but Miranda.

I don't know as much about yield and friends, but I know they are in Icon, and in various ML-like like languages.

Python has been around for ten years or so now. It only got lexical scoping and lambda-expressions very recently. Scheme has had them since the very first version of the language, which was introduced in 1975. That version of Scheme even had a primitive continuation-accessor catch, which come to think of it may bear some resemblance to yield.

Currently Scheme has a denotational semantics, a macro system, quasiquotation syntax, laziness via promises, and first-class continuations. Python has none of these. There are macro packages for Scheme available for list comprehensions, pattern-matching, yield, Concurrent ML-style concurrency, etc.

Far from leading the way, Python is a completely unremarkable language which is rather dragging behind. The only advantage it has over Scheme is non-technical: a large library and user community. And maybe the indentation syntax (which, BTW, was introduced in ISWIM, the first functional language, in 1966! And also appears in a more flexible form in Haskell).

Please give credit where credit is due.

And don't even get me started on C++...

List comprehensions are certainly cool, but, as I've stated in the past, I have an issue with the yield instruction. While I understand the need for it, given the lack of complete support for higher-level programming in Python, it just smacks too much of goto. Even worse, it's like a come from.

Those that should (must) be aware of such advances and features are the language designers. But they must also take into account the underlying nature of the language, and the expectations of its users (things we have discussed often in the past).

And don't even get me started on C++...

Why not? I really like it when you get started on stuff :-) (seriously, I generally learn something new)

Andrew Cooke says:

i'm surprised that iterator comprehensions don't "just work"

You can build a list comprehension with an iterator as the source, but the result is a fully-evaluated list, not a lazy one (a "generator", in Python terminology). If you had iterator comprehensions, you should also be able to derive a generator from a list.

I don't have a major problem with yield, but it does look like syntactic sugar for something else which isn't being directly exposed (if that makes sense) and I can see how that would smell bad to some people. Examples of good and bad uses would help - it's being promoted primarily as a means of improving performance where large amounts of data are being iterated over...

I don't disagree with Frank Atanassow about Python's place in the language steeplechase. Its real strengths are its freely available libraries, documentation/tutorials and ease of adoption - which is really down to the libraries and documentation. If Scheme "came with batteries included" and had more documentation written by people who weren't trying to teach computer science at the same time, it would probably be easier to learn than Python as the syntax is more uniform.

Python's lack of distinction, as a piece of language design, may be part of what helps it gain acceptance: you can learn a lot of what there is to learn of Python before anyone thinks of mentioning "denotational semantics, a macro system, quasiquotation syntax, laziness via promises, and first-class continuations". Ultimately that may be a weakness, but in popularity contest terms it's still an advantage. Maybe first-class continuations need better PR - at least Paul Graham's out there, doing his utmost.

(Whenever someone says anything like "blah blah blah Python blah blah blah" or "lets skip over continuations, I don't really understand them" in front of an audience of programming language mavens, it reminds me of the buck-toothed, snaggle-haired, white-coated fellow in The Simpsons getting the instant, outraged attention of a lecture hall full of scientists by declaring, loudly, "PI IS EXACTLY 3". They only do it to annoy, because they know it teases.)

If Scheme "came with batteries included"

I actually continue to be amazed at what comes as standard in PLT Scheme / Dr Scheme, and what is available in libraries for scheme (I recently found out that there are several openGL libraries / bindings for DrScheme). Overall, I think that it is a pretty well "batteries included" distribution of scheme.

What seems to be more of a problem with scheme is that there are so many to choose from, instead of one standard distribution for each platform. Of course this is quite probably an unavoidable side effect of having a language which doesn't appear to have too many nasty gotchas to catch unwary language implementors, along with all the examples of how to implement interpreters and compilers that are found in a number of scheme textbooks (like SICP).

i'm surprised that iterator comprehensions don't "just work". i thought iterators and lists provided the same underlying inetrface (via special "__foo" methods). what stops this from falling out of the mix for free?

Well, they do and don't work. You can use an iterator in a list comprehension, but what you get back is a (eager/non-lazy) list. E.g.

>>> def lazy():
...     for n in 'abcdef':
...         yield n
...
>>> lst = [n for n in lazy()]
>>> lst
['a', 'b', 'c', 'd', 'e', 'f']
>>> lazy
<function lazy at 0x104b6c>
>>> lazy()
<generator object at 0x125dac>

This is fine, as far as it goes. But once you use a less petite lazy sequence, you'll run into problems:

>>> def biglazy():
...     i = 0
...     while i < sys.maxint:
...         yield i
...         i += 1
...
>>> lst = [n for n in biglazy()]

You won't be happy if you do that.

I think this is true of many languages. There is a lot to be said for having a "standard" GUI library, so that GUI programs are guaranteed to work across platforms. Even better if you include a "standard" database package, and so on. When all is said and done, sooner or later we want to use these languages for "real" work, rather than just for academic explorations.

This isn't to say that you couldn't use alternatives, just that you could guarantee a common subset.

I am positive that there would be greater take up of alternative languages if such a thing was true. Like it or not, all modern platforms are GUI rather than text based. It is not helpful to have Graphics libraries that only work on one platform, or only with specific releases of a language's compiler. (Haskell anybody?)

There is a lot to be said for having a "standard" GUI library

Be nice if it wasn't Tkinter, either...

Java does include batteries, but Sun has a tendency to change these batteries every once in a while.

It will be interesting to see if the .NET environment, or something like it, can be used as a sort of "universal battery", for jumpstarting new languages. The downside may be that the desire to be plug-compatible with this battery will inhibit design variations among such new PLs.

One problem with iterator functions like fold[l|r] and for-each is that the client (the one that initiates the iteration) can not control the iteration easily (although it is possible with continuations - but not necessarily safe). For example, you don't want to implement assoc using fold. This problem leads to the symptom that you will need to implement many iterator functions (I) for each data structure (D). In other words, each data structure comes with multiple iterator functions that are specialized for the particular data structure leading to Theta(I*D) functions being written. At worst, the situation looks like this (although quite often data structure authors are lazy and do not provide all the necessary iterator functions):

            +--> ds1-for-each ----+
            +--> ds1-foldl -------+
            |      ...            +--> ds1
            +--> ds1-foldr -------+
   client --+
            +--> ds2-for-each ----+
            +--> ds2-foldl -------+
            |      ...            +--> ds2
+--> ds2-foldr -------+

Iterator objects, or cursors, like in the C++ STL or Java Collections, make it very easy for the client to control the iteration. In more advanced languages, you could then build just a single set of iterator functions that depend only on the iterator interface. In other words, you would need to implement only Theta(I+D) things. The situation looks like this:

           +--> for-each ----+                        +-- ds1
           +--> foldl -------+                        |
  client --+    ...          +--> cursor-interface <--+
           +--> foldr -------+                        |
+-- ds2

Unfortunately it can be difficult to implement cursors for anything more complex than trivial "linear" data structures. If you need to implement a cursor for a tree, for example, the cursor needs to keep track of the location in a tree and this often requires storing a stack in the cursor. (This paragraph, of course, applies mostly to weak languages that don't have coroutines or continuations.)

The coroutine style iterators in Sather make it easy to program cursors over complex data structures. You can essentially program the cursor like you would program an iterator function. The main difference is that at the points where an iterator function would call the function supplied by the client, you instead yield the object to the client. E.g. consider the following pseudo code for an iterator function:

  (define (for-each f l)
    (unless (null? l)
      (f (first l))
(for-each f (rest l))))

And the following pseudo code for a cursor:

  (define (for-each l)
    (unless (null? l)
      (yield (first l))
(for-each (rest l))))

The above easily generalizes to more complex data structures.

With sufficiently clever compiling techniques (inlining the cursor logic into the generic iterator function), coroutine style iterators plus generic iterator functions could be just as efficient as (specific) iterator functions.

The downside may be that the desire to be plug-compatible with this battery will inhibit design variations among such new PLs.

With .NET there are two issues that I can see. The first is language compatibility - it's becoming fairly apparent that the CLR supports some paradigms better than others. The second is the batteries themselves - ADO.NET, for instance. These are object-oriented component-shaped libraries, which expose functionality through methods attached to objects in containment hierarchies. They assume that you're going to be programming with them in certain ways. There will be a certain impedence mismatch between an object-based library and a programming style that utilises higher-order functions, combinators, lazy evaluation etc.; at the very least, the latter style won't be encouraged by the libraries (functional programmers will find themselves writing procedural-style code to set up components, call methods on them and tear them down). So it isn't only plug-in compatibility that's at issue: paradigm compatibility matters as well.

In the case of Python, while it's possible to use a (more-or-less) functional programming style, the supplied libraries by and large do not. You could probably translate a lot of HaXML (Haskell XML library based largely on the use of combinators) into Python, for instance - but of course the core Python XML libraries look nothing like HaXML. So the constructs and combinations supported by the language itself definitely aren't the whole story (as BeyondJS also demonstrates).

> This problem leads to the symptom that you will need to implement many iterator functions (I) for each data structure (D). In other words, each data structure comes with multiple iterator functions that are specialized for the particular data structure leading to Theta(I*D) functions being written. At worst, the situation looks like this (although quite often data structure authors are lazy and do not provide all the necessary iterator functions):

Hmmm, I don't agree with the above statement. On a language with coroutine-like iterators we can define generic folds, etc. using only the iterator interface. The following pseudocode (using Haskell-like type-class constructor) shall suffice:

class Collection a {
    each! : Collection a -> Iterator a;
    fromIterator : Iterator a -> Self;
}
for-each(collection, apply) {
    loop {
        item := each!(collection);
        apply(item);
    }
}
fold(collection, apply, initial) {
    result := initial;
    loop {
        result := apply(result, each!(collection));
    }
    return result;
}
find(collection, predicate) {
    loop {
        item := each!(collection);
        if predicate(item) then
           return Just(item);
        end
    }
    return Nothing;
}
map(collection, apply) {
    return fromIterator(map(each!(collection), apply));
}
map(iterator, apply) {
    loop {
        yield apply(result, each!(collection));
    }
    quit;
}
filter(collection, predicate) {
    loop {
        item := each!(collection);
        if predicate(item) then
           yield item;
        end
    }
    quit;
}

And so on. Other basic collection functions (e.g.: size, exists, for-all, count) can be implemented over fold, which is based on the generic iterator function. Of course subtypes can specialize the functions, so an array can use O(1) size instead. We don't need to implement "Theta(I*D) functions" because, AFAICT, no subtype can implement a version of map more efficient if the each! iterator is already correct. IOW a language with coroutine-like iterators can use generic functions for common iteration patterns, just like a language with cursors can. Sather base collections library has this kind of functions. But all this iterator hassle inexists in a lazy language like Haskell. AFAIK someone more proficient could implement this example using type-classes and Monads, and instead of a Iterator type-class, a regular list could be used.

- i believe that haskell (or at least ghc) now abstracts folds as a type class. in other words, for a particular data structure you can provide certain functiona that match an "interface" and fold can then be used on that structure. don't have a reference with me, unfortunately.

- you don't need a stack to implement iterators over tree structures. i was playing around not long ago with tree structures where all structural information is "local" - nodes only know about their parent and children. that's enough to give pre/post order depth first traversal (but not breadth first, iirc). there's a cost in performance but (again, iirc) the amortized cost is only a constant factor worse. this may seem pointless, but it's a big help when (for example) manipulating ast trees (destructively). as long as your manipulations "make sense" and you always take care to keep a reference to a node that's "in the tree" you can chop and change the rest of the structure around without worrying about the stack you've been using to traverse the tree containing invalid nodes. who cares about efficency anyway? :o)

We use a similar technique in BeyondJS. It's sufficient for a collection, or any object as a mater of fact, to implement the foreach method in order to receive most of the other iteration functions.

Nope. You cannot encode folds in general using type classes, even using explicit fixpoints, because a type class specifies a particular kind for each type variable, but folds make sense for functors of arbitrary kinds. Even if you restrict yourself to functors of kind *, it is not so useful because a) if you do use explicit fixpoints, you cannot express folds for built-in datatypes like lists, b) if you don't, you have to associate each datatype in an arbitrary way with a `base functor', c) folds are definable in a generic way, so using type classes here (which are good for ad hoc stuff) is not really satisfactory in the first place.

BTW, these problems with folds are one of the ugliest points of Haskell, IMO, though probably they do not impact programmers very much.

you don't need a stack to implement iterators over tree structures. i was playing around not long ago with tree structures where all structural information is "local" - nodes only know about their parent and children.

A tree is a thing in which each node knows what its children are, but not its parent. What you are describing is the symmetric closure of a tree regarded as a graph. It is important that a tree not know about its parent because, if they did, then, for example, two identical (sub)trees with different parents would be unequal.

Anyway, you need what amounts to a stack to fold a tree. By putting in parent links and storing state in the iterator you are just encoding the stack in a different way.

i'm at work, but in the introduction to the "origami" chapter in "fun of programming" isn't there a reference to work on generalising folds in haskell? that's what i was thinking of when i made that comment...

sorry for the lax terminology. my point was more about a neat hack that makes programming with imperative code and mutable data easier/safer/simpler/slower (there's no iterator - the parent link is enough to find relative nodes)

I couldn't resists the urge to point out that this is exactly one of the points I was making in my post (well, I can see a couple of slips in terminology in my post, but the point should be quite clear). Thanks!

Do you have any solutions or alternatives in mind? Any languages that you think handle this better?

I wish Scheme had a larger standardized library. The SRFI process (http://srfi.schemers.org) is a step in the right direction.

"I also think that this is trying to turn Python into a functional language, where most algorithms use lazy infinite sequences, and I just don't think that's where its future lies."

http://www.python.org/peps/pep-0289.html

Recent Python development has made generators and iterators a more central concept, and there seems to be a trend toward making the standard library use lazy iteration in more places (e.g. long-term plans to make range() an iterator generator). Maybe Guido will reconsider his position eventually (especially if someone first works out the implementation details). I hope so, because I really like the proposed syntax.

You could probably translate a lot of HaXML (Haskell XML library based largely on the use of combinators) into Python

Funny you should mention it. I feel that my gnosis.xml.validity library does a lot of what HaXml does--that was my main inspiration. Do a search, I wrote some articles on this, and you can download it either by itself or as part of Gnosis Utilities (start at http://gnosis.cx/download/gnosis).

"I also think that this is trying to turn Python into a functional language, where most algorithms use lazy infinite sequences, and I just don't think that's where its future lies."

I can't reasonably disagree with GvR about where Python's future lies (it's pretty much his call), but I don't understand why he's so bothered about the risk of Python being "turned into" a functional language. Perhaps a small delegation of Haskell mavens should be dispatched to waylay Guido and laugh condescendingly at the very suggestion until he relents.

I can recommend David Mertz's Functional/Python work, especially to anyone who's been charmed by BeyondJS. Credit where it's due: I think it was one of David's articles where I read about HaXml originally.

I took that to mean the future of programming...

And I must say that I am not sure all Haskell lovers agree that laziness is the wave of the future. Some may actually agree with Guido...

Maybe if you take "the future of Python" and "the future of programming" to mean the same thing - What's good for General Motors...

But no, I think Guido has a specific bugbear about the contamination of Python's Pythonicity by the fancy ways of functional programmers - witness his regrets over the inclusion of lambda. But this contamination has happened anyway, since you demonstrably don't need support for functional concepts in the core language to program in a functional style (just like you can do OO in Scheme); and it won't turn Python into a functional programming language, because it basically isn't anything like one.

if only Clean had Haskell's libraries and community we could move between laziness and strictness and strictness and laziness.

I may be in a minority, but I think Haskell made a mistake having laziness as the default behaviour.

Basically, too much time is spent forcing strict evaluation of otherwise lazy behaviour, first by the programmer, and then by the compiler (after strictness analysis).

A far better approach is to be found in Oz, where in those situations you need laziness, you simply ask for it.

i.e.

fun lazy {F params} [code] end

Although, there is a subtle difference in that Haskell's approach is sequential, (a thunk is evaluated when its result is required), and the Oz approach is concurrent, i.e. can have been performed on a separate CPU or even machine.

Yes, fold should be a language construct like case. See, for example:

Brian Howard. Inductive, Coinductive and Pointed Types. Proc. ICFP '96, 1996. (CiteSeer)

Also datatype declarations should explicitly mention the `base functor' (e.g., for lists over A the base functor is F(X)=1+A*X; the type list(A) is the least fixpoint of F), and/or there needs to be a coarser notion of type equivalence which the language is aware of, and which at least a decidable subclass of functors must respect.

i'm at work, but in the introduction to the "origami" chapter in "fun of programming" isn't there a reference to work on generalising folds in haskell? that's what i was thinking of when i made that comment...

I haven't seen that book yet, and none of my colleagues who have it are here at the moment. Maybe I'll take a look tomorrow. However, I think there is no satisfactory solution possible in Haskell.

And I must say that I am not sure all Haskell lovers agree that laziness is the wave of the future.

Me for example, but I also think that if lazy computations are not expressible in the language then there is a problem.

But no, I think Guido has a specific bugbear about the contamination of Python's Pythonicity by the fancy ways of functional programmers

If I may be allowed another snide remark---oh what the hell, I always do anyhow---perhaps this is a case of cognitive dissonance. Suppose you spend a lot of money on a car which turns out to be really uncomfortable. Since you have invested so much money in the car, admitting that it is uncomfortable would be difficult for you. Similarly, people who invest much of their mental energy on (and social standing expounding the merits of) OOP are loath to accept FP because, if FP is better, they have wasted a lot of energy.

Of course, I hate OOP and have invested a lot of effort in understanding FP. :) OTOH, I was an OOP zealot before I became an FP---uh, let us not say zealot---convert.

[and guido is trapped anyway, from a purely practical pov, by the implementation of lists in python. already it's obvious who has come to python from fp because they post to the newsgroup either asociating [1:] with cdr or wondering why [...].sort() returns null ("lists" being arrays of mutable values in python).]

Unfortunately it can be difficult to implement cursors for anything more complex than trivial "linear" data structures. If you need to implement a cursor for a tree, for example, the cursor needs to keep track of the location in a tree and this often requires storing a stack in the cursor. (This paragraph, of course, applies mostly to weak languages that don't have coroutines or continuations.)

Indeed, in a language with first-class continuations, a programmer doesn't need to implement cursors at all: he can always get them by passing an enumerator to a generic procedure enumerator->cursor (a.k.a. foreach->lazy-list)
http://srfi.schemers.org/srfi-39/mail-archive/msg00036.html
That procedure works with *any* enumerator, be it an enumerator over a list, a tree, a database, or any other data structure. The following page shows the example for a treap (a balanced tree):
http://pobox.com/~oleg/ftp/Scheme/enumerators-callcc.html

Hmmm, I don't agree with the above statement. On a language with coroutine-like iterators we can define generic folds, etc. using only the iterator interface.

It's better to define cursors via enumerators (by mechanically inverting them) rather than the other way around, for the reasons of resource usage. The problem with cursors is that they must be explicitly closed or finalized -- neither of which is a good solution. See a message "An argument against cursors" on the SRFI-44 discussion list.