21 Nov 06:37 2005

## [stack] Monads in Joy

Manfred Von Thun <m.vonthun <at> latrobe.edu.au>

2005-11-21 05:37:46 GMT

2005-11-21 05:37:46 GMT

PREAMBLE For some years now I have been trying to understand monads in category theory and computing, with an embarrassing lack of any success. But recently things finally fell into place, and I want to share this with the group - and when I get around to it I want to write it up fully. "Monads arose in category theory, and have been used extensively in the Haskell programming community." True. But it led me and possibly others to several misconceptions: "Monads are for lazy languages like Haskell." False. You can have them in the eager language ML. "Monads are for strongly but polymorphically typed languagges." False. You can have monads in Lisp or Scheme (see Oleg's work). "Monads need lambda abstractions and hence only work for lambda calculus based languages." False. Any lambda calculus language can be translated into SK calculus which has no lambda abstractions. "Monads need a (binary infix) operator 'bindM' which semantically is a cousin of the apply operator (and syntactically written in reverse, but that is trivial). So monads can be used in applicative languages such as Haskell, ML, Lisp/Scheme, SK-calculus." True. "But monads cannot be used in concatenative languages such as Joy." False. That is what I want to show. THE LIST MONAD IN JOY Understanding monads in Joy came as an enlightenment to me when I reread Wadler's paper "The essence of functional programming" and noticed a very small section about the list monad in Haskell. Here at last was something I knew how to translate into Joy, and I think it is probably a good way to introduce monads to other Joy programmers. Define two functions: unitM # unitlist == [] cons joinM # form a a single list from a list of lists == concatenate == [null] [] [uncons] [concat] linrec Define two combinators, which both expect a single quotation: mapM # the ordinary mapping for lists == map bindM # a strange beast == map concatenate In the following [F] and [G] will be something like [dup *]. Now all the following laws are satisfied (all expect a list on top of the stack, except that (4) expects a list of lists, and (7) expects a list of lists of lists): ( 1) [] mapM == id ( 2) [F G] mapM == [F] mapM [G] mapM ( 3) unitM [F] mapM == [F] i unitM ( 4) joinM [F] mapM == [[F] map] map joinM ( 5) unitM joinM == id ( 6) [unitM] mapM joinM == id ( 7) [joinM] mapM joinM == joinM joinM The above do not use bindM yet, but the following do. The parameter [K] or [H] for bindM has to be a function K or H which produces a list, something like [dup * unitM] or [dup dup * [] cons cons]. These laws are also satisfied: ( 9) unitM [F] bindM == [F] i (10) [unitM] bindM == id (11) [F] bindM [G] bindM == [[F] i [G] bindM] bindM (12) [F] mapM == [F unitM] bindM (13) joinM == [] bindM A SMALL TASTE OF OTHER MONADS IN JOY For the definitions of unitM, bindM, mapM and bindM this is the list monad. For different definitions we get a different monad - provided all laws are satisfied. But we do not need all four primitives: we can have unitM and bindM as primitives, and then use (12) and (13) as definitions for mapM and joinM. Alternatively, we can have unitM, joinM and mapM as primitives and use (8) as a definition for bindM. The latter alternative is probably most natural for Joy programmers. Readers familiar with monads in Haskell will recognise the laws from Wadlers paper(s). Searching for different definitions yielding a different monad, the best is probably to start with a different definition for the combinator mapM. It has to take just one quotation parameter, and there are plenty like that in Joy. But one also needs appropriate unitM and joinM. Here are several: The (boring?) identity monad: unitM = id, joinM = id, mapM = I, bindM = I (* both I lower case! *) ^ ^ (* arrogant mailer!*) An "additive dip monad": unitM = 0, joinM = +, mapM = dip, bindM = dip + (here the [K] parameter to bindM must leave an extra integer on top of the stack) A "concatenative dip monad": unitM = [], joinM = concat, mapM = dip, bindM = dip concat (Here the [K] parameter to bindM must leave an extra list on top of the stack.) The two dip monads propagate a state on top of the stack, and different choices for unitM and joinM give different dippy monads. Combinators other than map, I, or dip as interpretations for mapM need investigating, such as nullary and infra. And even combinations [I]map, [map]map, [dip]map and I don't know what else. More in the future. I have a few examples of state monads. Does anybody know how to switch off the spelling "corrector" (for lower case I) inside this Entourage abomination? - Manfred ------------------------ Yahoo! Groups Sponsor --------------------~--> 1.2 million kids a year are victims of human trafficking. Stop slavery. http://us.click.yahoo.com/WpTY2A/izNLAA/yQLSAA/saFolB/TM --------------------------------------------------------------------~-> Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/concatenative/ <*> To unsubscribe from this group, send an email to: concatenative-unsubscribe <at> yahoogroups.com <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/