Added monad comprehensions to Coffeescript

[zot]

I modded the Coffeescript compiler to add monad comprehensions, forked the repo, and pushed my changes to the "mocoffee" branch, here: https://github.com/zot/coffee-script

An example file is here: https://github.com/zot/coffee-script/blob/mocoffee/examples/mofor.coffee

Monad comprehensions are syntactic sugar that helps to reduce the indentation level of your code, if you use monads. Here are some articles on monads:

http://www.haskell.org/tutorial/monads.html http://en.wikipedia.org/wiki/Monads_in_functional_programming

They're really useful in functional programming. In fact, I'm starting a functional programming project that uses Javascript and that's why I'm looking at Coffeescript. Please let me know what you think of the syntax; I chose "mofor" because it's a monadic for-loop-ish construct. It looks like this:

mofor
  variable1 <- expr1
  ...
  if expr2
  ...
  variable2 <- expr3
  ...
->
  expr4
  ...

If used as an expression, it returns the flattened result. var <- expr is a "binding" expression and it binds var to the values in expr. You can mix filter expressions in with the bindings. At this point, expr can be an array or anything that understands map(), filter(), forEach(), and flatMap() (as in Scala). The code it generates is a little klugy at this point, and it relies on the existence of Array.prototype.flatMap(), if you're using arrays, which I'm just including in my code right now, but I'll improve these things over time.

Mofor translates to a nested group of map(), flatMap(), forEach(), and filter() expressions, each binding or filter line increasing the nesting level. Monad comprehensions help simplify the text.

Here are the examples from the mofor.coffee file:

sys.p (mofor
  a <- [1,2,3]
  b <- [4,5,6]
  if a % 2 == 0 or b % 2 == 0
->
  [a + 1, b + 1])

outputs:

[ [ 2, 5 ]
, [ 2, 7 ]
, [ 3, 5 ]
, [ 3, 6 ]
, [ 3, 7 ]
, [ 4, 5 ]
, [ 4, 7 ]
]

and:

sys.p (mofor
  a <- new Monad(3)
->
  a
)

outputs (I don't have a fancy print-string for monads, yet :) ):

{ '0': 3 }

[has207]

I have to say this is very impressive.. But as far as I understand it, monads are only really useful in functional programming when the functional language (such as Haskell) does not allow side-effects. This is not the case for JS or CoffeeScript, so the value of adding this additional syntax to Coffee seems dubious to me, as everything monads let you do here can already be done in much more straight-forward manner using existing syntax.

[zot]

Well, since I'm starting a functional programming project, using Javascript (you can write code without side effects in Javascript or Coffeescript as well as Haskell), I was choosing between Scheme->JS and Coffeescript, and I chose Coffeescript. I added monad comprehensions to Coffeescript for my own benefit and I thought I'd share, in case other people might find it useful.

By the way, in addition to monads, it's useful for iterating over several lists at a time and it flattens the results if you use it in an expression, so it's more convenient than for loops in some cases.

[zot]

I should say that monads have a LOT of other uses, besides hiding side effects, such as handling exceptions and representing optional values. They're also a control-flow construct, up there with "if". The wikipedia article I linked above talks about monads in depth.

[odf]

Looking great. I'm working on a functional coffeescript project myself, and this would come in very handy. The argument for not extending the existing for loops to user-defined data structures has been that it would make looping over arrays elements and object properties prohibitively inefficient. Using a separate syntax would bypass that problem.

And yes, Scala's monadic comprehensions and Python's generator expression demonstrate quite nicely that this kind of thing is not only useful in languages that forbid side effects.

[has207]

@odf

I can't speak for Scala as I don't know much about it other than it has an unwieldy type system, but Python's generators seem to me an example of hacking in lazy evaluation into a strictly evaluated language, which has little to do with monads. As such I'm not sure how their existence is an example of "this kind of thing".

However, there is an example of "this kind of thing" right here in JS -- the "with" statement. It aims to add syntactic sugar, but is so fraught with problems that nobody sane actually uses it, while at the same time it adds a noticeable tax on the interpreter just by virtue of being in the language, making all JS code slower as a result.

@zot

I think monads are a control flow construct right up there with the semi-colon, not so much the "if". They force a certain flow, which is functionality otherwise missing in Haskell, while Coffee already has it built in, so the value added, as I see it, is having a different way to do the same thing you can already do. Doing it monadically, while admittedly cool and theoretically interesting, only bloats the language without adding anything inherently useful when control flow is already defined by order of the calls and we can already write side-effect code without doing anything special. As I mentioned above, the "with" statement should serve as warning for adding new syntax sugar to the language that provides dubious benefits while bloating and slowing down the interpreter for /everyone/, not just those using the new syntax.

[zot]

@has207

It's clear to me that you don't like monads, you don't see any value in functional programming, and you probably never will. Thanks for the input and the value judgments.

[has207]

There's no reason to get personal. It's true, I don't "like" monads in the sense of wanting them as a built-in in every language, whether they belong there or not. They're great in Haskell, where they serve a real purpose. You can implement them in a non-strict functional language but they bring very little value there.

Btw, monads != functional programming. JS and Coffee are already functional programming languages without them. Just like LISP, Scheme, ML, list goes on and on.

This is impressive work, and I've commented twice on the fact that I think it's cool. I'd hate to see it included in the language, as it would undoubtedly tax the interpreter for little real life benefit. That said, it would be great as a stand-alone library. And the amount of downloads you get will tell you just how useful it is for people "out there" using Coffee, which may prove me wrong with actual data and earn its way into the core language.

All that said, I don't make any decisions about what's included in Coffee or not, your patch can get pulled in tomorrow regardless of what I have to say on the subject, so no reason to get worked up about it :)

[zot]

It could be that I'm just testy, today, but if you reread your previous comment, maybe you will find it to be as sarcastic and dismissive as I did.

Since Coffeescript is a compiler, adding to it will not slow down the JavaScript code that it generates.

Monads have many other uses, besides flow-of-control and managing side effects, some of which are given in the wikipedia article.

Personally, I'm not an expert on functional programming, but I do know JS and Coffeescript are not functional languages because of things like Math.random() and assignable properties. Functions in functional languages have no side effects, i.e. every time you call a function with given parameters, you get the same result (as opposed to Math.random()). You can, however, write functional programs in JS and Coffescript.

Here is an excellent talk on functional programming, if you want to learn more about it: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

[has207]

You're confusing functional with /purely/ functional. That is, "functional" by itself does not have the same meaning in programming as it does in math. JS has closures (another concept that has a different meaning in programming than in math) and first-class functions, which makes it functional, in the programming language sense. Just like LISP, Scheme, etc.

As for the tax on the Coffee compiler -- some of us out there can be using it in the browser, where the /compiler/ performance, and size, is extremely important.

For a humorous take on a related subject, see Steve Yegge's recent blog entry:

http://steve-yegge.blogspot.com/2010/12/haskell-researchers-announce-discovery.html

(Of particular note is the comment at the bottom about Perl and monads)

And I'm sorry if any of my comments came across as sarcastic or dismissive -- no sarcasm was intended.

[jashkenas]

I often (always) find that arguments about the possible utility of ideas and enhancements are best demonstrated with concrete use cases.

zots: Do you mind sharing a few examples of real-world CoffeeScript where mofor shines?

[odf]

@has207: To clarify, by "this kind of thing", I meant comprehension for user-defined collections. It doesn't matter whether those are meant to be mutable or immutable, or whether they use lazy evaluation or not. As zot wrote, anything with the methods map(), foreach(), filter() and flatMap() will do. It is also irrelevant whether we use the word monad or not. Monad is just a fancy name for a very basic and ubiquitous programming pattern that is not restricted to purely functional languages at all.

[zot]

@jashkenas As soon as I have a chance to write some code -- I only just looked at Coffeescript 3 days ago and cooked up "mofor"! I'm planning to use it a lot in my project and I'll be happy to keep you informed.

[zot]

@jashkenas, I looked through the Scala compiler source and found some examples of for comprehensions that might interest you...

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/compiler/scala/tools/ant/ScalaBazaar.scala#L282

This gathers a list of triples, (dest dir, src dir, file) to construct a zip file:

val zipContent =
  for {
    Pair(folder, fileSets) <- fileSetsMap.fileSets
    fileSet <- fileSets
    file <- fileSet.getDirectoryScanner(getProject).getIncludedFiles.toList
  } yield Triple(folder, fileSet.getDir(getProject), file)

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/compiler/scala/tools/ant/Same.scala#L119

Iterate through names and their "map files". mapFileName returns an Option monad, which is for optional values, either Some(value) or None. The loop body will only execute for destNames that exist (have a "Some" value instead of a "None" value).

  for (
    originName: String <- originNames; 
    destName: String <- mapper.mapFileName(originName)
  ) {
    ...

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/compiler/scala/tools/nsc/transform/Constructors.scala#L272

Collects all of the nonprivate getters which are not "outerFields" of the parents which are traits:

  val parentSymbols = Map((for {
    p <- impl.parents
    if p.symbol.isTrait
    sym <- p.symbol.info.nonPrivateMembers
    if sym.isGetter && !sym.isOuterField
  } yield sym.name -> p): _*)

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/compiler/scala/tools/nsc/Interpreter.scala#L267

Find the most recently handled tree by going through the reverse lists of requests and handlers

  private def mostRecentlyHandledTree: Option[Tree] = {
    for {
      req <- prevRequests.reverse
      handler <- req.handlers.reverse
      name <- handler.generatesValue
      if !isSynthVarName(name)
    } return Some(handler.member)

    None
  }

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/compiler/scala/tools/nsc/plugins/Plugin.scala#L133

find jars that fit a criteria in a list of directories:

  val alljars = (jars ::: (for {
    dir <- dirs if dir.isDirectory
    entry <- dir.toDirectory.files.toList sortBy (_.name)
    if entry.extension == "jar"
    pdesc <- loadDescription(entry)
    if !(ignoring contains pdesc.name)
  } yield entry)).distinct

[jashkenas]

I'm afraid I don't know any Scala. Mind translating one or two of those to your mofor syntax?

[zot]

OK, let's take the first one:

This gathers a list of triples, (dest dir, src dir, file) to construct a zip file:

  val zipContent =
    for {
      Pair(folder, fileSets) <- fileSetsMap.fileSets
      fileSet <- fileSets
      file <- fileSet.getDirectoryScanner(getProject).getIncludedFiles.toList
    } yield Triple(folder, fileSet.getDir(getProject), file)

Here's how this might look if mofor supported destructuring assignment (although it doesn't currently support that):

  zipContent = mofor
    [folder, fileSets] <- fileSetsMap.fileSets
    fileSet <- fileSets
    file <- fileSet.getDirectoryScanner(getProject).getIncludedFiles().toList()
  ->
    new Triple folder, fileSet.getDir(getProject), file

The third one:

Collects all of the nonprivate getters which are not "outerFields" of the parents which are traits:

  val parentSymbols = Map((for {
    p <- impl.parents
    if p.symbol.isTrait
    sym <- p.symbol.info.nonPrivateMembers
    if sym.isGetter && !sym.isOuterField
  } yield sym.name -> p): _*)

Let's assume there's a createObject(pairs) function that takes a list of two-element arrays, [name, value]:

  parentSymbols = createObject(mofor
    p <- impl.parents
    if p.symbol.isTrait
    sym <- p.symbol.info.nonPrivateMembers
    if sym.isGetter and !sym.isOuterField
  ->
    [sym.name, p])

[jashkenas]

How is your mofor version of the first example better than simply doing it like this:

zipContent = for [folder, fileSet] in fileSetsMap.fileSets
  file = fileSet.getDirectoryScanner(getProject).getIncludedFiles().toList()
  new Triple folder, fileSet.getDir(getProject), file

[zot]

(oops -- edited this to fix formatting)

You left out a few levels of the for-loop, there. I think you meant this:

  zipContent = []
  for [folder, fileSets] in fileSetsMap.fileSets
    for fileSet in fileSets
      for file in fileSet.getDirectoryScanner(getProject).getIncludedFiles().toList()
        zipContent.push (new Triple folder, fileSet.getDir(getProject), file)

[jashkenas]

Oh, that's how it works? Your revised code looks much, much clearer to me than the mofor version.

I'm afraid that for core CoffeeScript this is a wontfix ... but it's certainly a neat idea.

[zot]

Here's what mofor translates this to (assuming destructuring assignment):

  zipContent = fileSetsMap.fileSets.flatMap((folder, fileSets) ->
    fileSets.flatMap((fileSet) ->
      fileSet.getDirectoryScanner(getProject).getIncludedFiles().toList().map((file)->
        return new Triple folder, fileSet.getDir(getProject), file)))

[zot]

OK, I'm happy to maintain my fork, then.

[odf]

@jashkenas: I think it only looks cleaner to you because you're not used to that syntax. I've come across it before in Scala and actually find it much cleaner and more readable than nested for loops. But I guess taste plays a role there, too.

Anyway, I have to agree that comprehensions are not exactly a crucial feature, and stacking map(), filter(), flatten() and forEach() directly works just as well. ;-)

[zot]

@jashkenas: The first "mofor" example is less verbose than Coffeescript's "for" and provides some more functionality (you can't use a Coffeescript "for" expression there, because it wouldn't return a flattened list). Kind of like how Coffeescript's "for" is less verbose than JavaScript's "for" and provides some more functionality.

[satyr]

it wouldn't return a flattened list

It should, really. (Are there other languages with un-nestable for-comprehension?)

[zot]

I don't know. Haskell used to have "monad comprehensions," but it doesn't, anymore. As far as I know (which isn't very far in this area), for-comprehensions may be a Scala innovation. They are sort of a blend of list-comprehensions, of which Coffeescript has a form, and Haskell's monadic "do" operator. Here is what I think is the original Haskell monad paper: http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf

Here's more info on Scala's for-comprehensions: http://debasishg.blogspot.com/2008/03/monads-another-way-to-abstract.html Scala also uses them heavily in XML processing. Since maps in Scala can produce monads, you can use them in for-comprehensions, and the same for XML properties. So to execute code on documents that have attributes name, address, and phone, you would do something like this (using mofor, assuming getMoAttr returns a monad for an XML attribute):

  mofor
    el <- elements
    name <- el.getMoAttr('name')
    address <- el.getMoAttr('address')
    phone <- el.getMoAttr('phone)
  ->
    body

Because of the way monads work in for comprehensions (kind of like collections that can only have 0 or 1 elements), body only gets executed for elements that have name, address, and phone (and those variables are set to the values of those attributes), so getting an attribute is sort of a combination of an access and a test.

[zot]

I fixed up the syntax to make it more Coffeescript-y and I want to present a different way of thinking about what this does. It's an "extended for loop" that supports user-supplied collection types and flattens the results if you give it more than one loop variable. Here's the new syntax I have (subject to change if people come up with something better):

  diseaseTable = mofor
    person in infectedSet
    disease in person.diseasesSet
      [person.key, disease.key]

This gives you a 2-dimensional array of people and diseases, where the first column is the key for the diseased person and the second column is the disease. It works on user supplied collections, like sets.

[zot]

I added an alternate form with only one binding that's on the same line as 'mofor'. Here's an example that would iterate over a sparse array of totals and return the values, doubled:

  doubled = mofor total in sparseTotals
    total * 2

By the way, if people don't like the name "mofor," I'm happy to change it to something else, like xfor or whatever.

[satyr]

Mind sharing compilation as well?

[zot]

Sure. Since this uses custom collections, it compiles into nested method calls. It's not as efficient as a for loop stepping through an array, but then, it works on things like trees and sets. In my project, I'll be using AMTs (Array Mapped Tries) for sparse arrays, for instance. At this point, my code compiles these expressions:

  diseaseTable = mofor
      person in infectedSet
      disease in person.diseasesSet
        [person.key, disease.key]

    doubled = mofor total in sparseTotals
      total * 2

into this code:

  (function() {
    var diseaseTable, doubled;
    diseaseTable = (function() {
      return (infectedSet || []).flatMap(function(person){return (person.diseasesSet || []).map(function(disease){        return [person.key, disease.key];})})  })();
    doubled = (function() {
      return (sparseTotals || []).map(function(total){      return total * 2;})  })();
  }).call(this);

I may be using Expression.wrap, or something like that, too eagerly, because I don't think the diseaseTable and doubled expressions need to be wrapped in functions, but I'll improve the code generation over time. You get the idea, anyway. When you have several bindings (loop variables), it nests a flatMap for each binding around the rest, until it gets to the final binding, which uses map, instead of flatMap. If you have filters (if statements) mixed in, it cascades calls to filter() as well.

At this point, I'm using (expr || []) so that it handles nulls gracefully, but that's not really required and I'm not sure whether it's a good idea.

[zot]

By the way, I'm not sure my code generation approach is the best, either. Maybe it would be better for this:

    diseaseTable = mofor
        person in infectedSet
        disease in person.diseasesSet
          [person.key, disease.key]

To produce something like this: var diseaseTable = infectedSet.create() infectedSet.forEach(function(person){ person.diseaseSet.forEach(function(disease){ diseaseTable.add([person.key, disease.key])})}) It replaces map and flatMap with create and add in the API requirements, but it's probably more efficient. It also assumes that flatMap-map behaves like create-forEach-add, which I think it should, but I'm not positive about this.

[satyr]

var diseaseTable,

So it's basically:

diseaseTable = infectedSet.flatMap (person) -> 
  person.diseasesSet.map (disease) ->
    [person.key, disease.key]

I feel like there should rather be a generic syntax to flatten nested callbacks, like:

diseaseTable = (
  person  <- infectedSet.flatMap
  disease <- person.diseasesSet.map 
  [person.key, disease.key]
)

[zot]

Interesting. That's almost like the "circle" function composition operator.

[odf]

@zot: I think I like the flatMap version better than the create-forEach-add one. For lazy data structures such as streams, doing an add for each element could be much less efficient than a single map, whereas a map can always be implemented internally via create and add where that makes sense.

@satyr: That's an intriguing idea.

[zot]

@odf, true -- lazy structures are important!

[zot]

On that note :), I put a lazy sequence implementation and monads into my repo, here:

https://github.com/zot/coffee-script/blob/mocoffee/tools/lazy.coffee

[satyr]

a generic syntax to flatten nested callbacks

FYI, this is now live on Coco. The transformation is pretty simple:

a <- f
b

↓

f (a) ->
  b

One culprit is that it can't easily have bound versions (<= is taken already). I've aliased => as ~> and gave it <~ for now.

[zot]

I added yet more monad support to mofor, making it much more of a blend of Haskell's "do" and Scala's "for". @satyr, Haskell's "do" kind of reminds me of your nested callback thing, by the way. The old syntax still works, but now, this works: mofor game in currentGame do game.put "Moving ship" mofor do x in [1,2,3,4,5] y in [1,2,3,4,5] game.moveShip x, y p in game.pos game.print "MOVED TO: #{p[0]}, #{p[1]}" game.put "Done moving ship" As with Haskell's "do," game doesn't really change, even though it appears to; each statement just returns a transformation of the current value of game, which goes as input into the next statement. The inner mofor sets off a block that does nested iteration on the two collections, using reduce to track the transformations of game. So, the generated code "threads" game through the statements and collections, returning the final transformation of game. it's equivalent to this: currentGame.reduce ((game, _i1) -> (game.put "Moving ship").reduce ((game) -> (game.reduce ((game, _i2) -> [1,2,3,4,5].reduce ((game, _i3) -> [1,2,3,4,5].reduce ((game, _i4) -> game.moveShip x, y.reduce ((game, _i5) -> game.pos.reduce ((game, _i6) -> game.print "MOVED TO: #{p[0]}, #{p[1]}" ), game ), game ), game ), game ), game).reduce ((game, _i5) -> game.put "Done moving ship" ), game ), game ), null So, the idea is to allow you to use monads more naturally without all of the nested parens and repetition.

[taku0]

@zot , you can use monads without special syntax, deep indents, or parens:

foo.flatMap (x) -> \
x.flatMap (y) -> \
foo.guard(x > 0 and y > 0).flatMap -> \
foo.unit(x + y)

where foo.guard is defined like this:

(condition) -> if condition then [undefined] else []

or more generally,

(condition) -> if condition then @unit(undefined) else @mzero

[satyr]

CoffeeScript is all about sugars. "Just use desugared form" doesn't work here.

[hallettj]

I know that this is a closed and really old issue. But I wanted to point out that working with promises is a real sweet spot for monad-style programming. Consider this example of a series of ajax calls made using jQuery:

save = (record) ->
  deferred = new $.Deferred()

  $.get('/ids').success((ids) ->
    recordUrl = "/records/#{ids[0]}"

    $.post(recordUrl, record).success((revision) ->

      $.get(recordUrl, revision: revision).success((savedRecord) ->
        deferred.resolve savedRecord
      ).error (msg) ->
        deferred.reject msg

    ).error (msg) ->
      deferred.reject msg

  ).error (msg) ->
    deferred.reject msg

  deferred

This function takes a record, fetches a list of available uuids, selects the first available id, saves the record to a new URL based on that id, and fetches the updated version of the record after any server transformations that may have been made when it was saved. Finally, the result of the last call is forwarded to a deferred object that the save() function returned when it was called.

See the jQuery documentation for more information about jQuery.Deferred: http://api.jquery.com/category/deferred-object/

This process requires making several ajax calls that have to be performed in order and that each depend on the result of the previous call. The same code could be expressed more succinctly using mofor:

save = (record) ->
  mofor
    ids <- $.get('/ids')
    recordUrl = "/records/#{ids[0]}"
    revision <- $.post(recordUrl, record)
    savedRecord <- $.get(recordUrl, { revision: revision })
  ->
    savedRecord

In addition to being much shorter, this version expresses the order in which events occur more clearly and does not require extra code to pass forward any errors that may occur at each step. If any of the three ajax calls here results in an error then the promise that the entire mofor expression evaluates to will emit the same error.

Using jQuery.Deferred objects with mofor does require the monadic methods used by mofor to be added to the jQuery.Deferred prototype:

$.Deferred.prototype._proxy = (deferred) ->
  deferred.done (values...) =>
    @resolve values...
  deferred.fail (msgs...) =>
    @reject msgs...

$.Deferred.prototype.map = (f) ->
  deferred = new $.Deferred()
  @done (values...) ->
    deferred.resolve f(values...)
  @fail (msgs...) ->
    deferred.reject msgs...
  deferred

$.Deferred.prototype.filter = (p) ->
  deferred = new $.Deferred()
  @done (values...) =>
    if p(values...)
      deferred._proxy this
    else
      deferred.reject()
  @fail (msgs...) ->
    deferred.reject msgs...
  deferred

$.Deferred.prototype.flatMap = (f) ->
  deferred = new $.Deferred()
  @done (values...) ->
    deferred._proxy f(values...)
  @fail (msgs...) ->
    deferred.reject msgs...
  deferred

[zot]

Cool! This is the sort of thing I was hoping to enable with mofor.

[puffnfresh]

@hallettj old issue but Roy (my language) has monadic syntax. Here's an example using jQuery's deferred:

https://github.com/pufuwozu/roy/blob/master/examples/deferredmonad.roy

[zot]

Interesting! I'm also working on a functional language, but it's untyped (sort of) and lazy, but it's not quite ready to announce: https://github.com/zot/Leisure

[ms-tg]

I'd like to mention that I think this is a great idea, would really push CoffeeScript ahead just for the use in promises. Realize this is old.

[johanatan]

@ms-tg Agreed!

[vendethiel]

=> #2762 re-opening and re-closing since it appears to be "closed-but-not-too-much" (happens a lot with old gh issues)

[Leimy]

It's wrong to say that monads are only useful in functional languages where there's no side-effects.

Just because technique X was applied to a language to solve problems with representing flow, doesn't mean the only use of technique X is in those cases :-).

/bin/sh -e runs under an error monad (whether you like to believe it or not) for example, which says any failing step that is unchecked in the script causes the whole script to abort. You could think of it as converting your errors into exceptions that must be caught or they'll terminate the script.

I'm really new to coffeescript but sometimes these abstractions are nice to have. The problem is they often come with syntactical convenience for the author of code, which makes reading the code, by humans, much more difficult later.

Haskell is full of nice stuff like this, but it makes reading take way more effort than writing the code.