Lambda the Ultimate

Python 'for' as Scheme 'let'
started 2/23/2004; 1:32:39 AM - last post 2/23/2004; 2:00:23 PM

Ehud Lamm - Python 'for' as Scheme 'let'

2/23/2004; 1:32:39 AM (reads: 9993, responses: 2)

Python 'for' as Scheme 'let'

We show that the 'for' operator of Python quite unexpectedly can be represented by a 'let' form of Scheme.

Another cool example from Oleg. This time, not only a nice example of Scheme macros, but of shift/reset operators as well.

Allow me to draw the following diagram:

list-comprehensions === monads === shift/reset === range

The first two are truly equivalences: in Haskell, a list comprehension is just another form of the 'do' notation in the case of a List monad. Filinski showed that shift/reset can be used to implement monads in the general way. My 'range' is based on shift-and-reset.

There is a difference however. If we avoid nested loops, then my shift/reset (called bshift/breset) are the same as shift/reset. Alas, regular shift/reset cannot nest. There are multi-level shift/reset, but they are difficult to use -- and hard to encapsulate in a macro such as 'range' because the macro needs to know on which level it operates. My bshift/breset are different. bshift/breset with different labels are unaware of each other.

BTW, other control operators, e.g., those by Matthias Felleisen, do not have the indifference property. The operator 'cupto' has -- but to some extent. Several cupto operators have to be used in a stack-wise fashion. Mines don't have to.

Posted to functional by Ehud Lamm on 2/23/04; 1:35:53 AM

Tim Sweeney - Re: Python 'for' as Scheme 'let'

2/23/2004; 1:46:08 PM (reads: 395, responses: 0)

I've been trying to sort out these similarities too. There is also a notion of a Monad with a "cut" operator similar to the Prolog cut operation discarding prior choice points; something along these lines may be valuable in modelling a array monad analogy to the "break" command in C for loops. (The "continue" command is already modelled by the array monad's zero.)

The presence of operations with side effects in things like list comprehensions complicates their interpretation as monads. One approach I find promising is to model all imperative operations in a program literally as IO monads, and to have a syntactic translation of things like for loops or list comprehensions whose contents have side effects into a simple composition of the Array or Maybe monad with the IO monad. Obviously this translation will only work for a predetermined set of monads (because not every monad can be composed with IO so as to yield a true monad as a result), but it would be nice to be able to model all imperative constructs and looping constructs with a mainstream-style syntax (as opposed to Haskell syntax) with the monad translation being automatic.

Note that in a suitable type system, you can construct a "TypeMonad" whose map functor takes the (exact) image of a supplied function over a supplied type, unit generates a singleton type containing just the supplied element, join is type union, and zero is the empty type.

The really neat thing is that comprehensions in the TypeMonad correspond to constructing new types elementwise from existing types, i.e. for(a:at,b:bt)[a,b] is the type of pairs containing elements from the types at and bt. And in the IdentityMonad, comprehensions correspond to lets: for(a:x,b:y)a+b is just x+y. So, many of the leading edge syntactic constructs in languages can be represented as comprehensions over a suitable monad.

Tim Sweeney - Re: Python 'for' as Scheme 'let'

2/23/2004; 2:00:23 PM (reads: 386, responses: 0)

Pardon the spam, but here are some more notes:

The TypeMonad described above also can be extended with a new "meet" operating (taking typewise intersection) and "infinity" object ("the type of all types" if it exists and is nonparadoxical in a given type system) as its idempotnent. This structure can then be seen as a lattice or a topos or a model of set theory depending on what you want from it. However, TypeMonad can't be sensibly composed with IO, because elements in a set are inherently ordered, in contrast to elements of a list of array.

Finally, there is a concept of a monad with a fixed-point operation (see http://www.cse.ogi.edu/PacSoft/projects/rmb/mdoTalk.pdf), which leads to the interesting possibility of accessing the previous results of a list comprehension while constructing subsequent elements.