Buscar en Mind w/o Soul

lunes, mayo 18, 2009

More monadic and non-monadic parsers in python

More monadic and non-monadic parsers in python


Some intuitions on Monads

Remember your first lesson in structured programming, when the teacher insisted there where 3 operations for program structure: the conditional (if), loop (while), and sequence (;) operators. Conditionals choose between two alternate control sequences; loops repeat a sequence; and 'sequence' itself defines the order in which simple operations are chained together.

Did you mutter to yourself then, "how can 'sequence' be an operator and not just, well, how the program is laid out in the file?" Well, fact is you really can think of sequence as an explicit operator. And monads are a way to overload that operator, in the OOP sense of operator overloading.

If you have defined a monad in a functional program, you can use it to build a sequence of operations, just like you would in an imperative program. But you can actually change the meaning of the composition in the sequence: every step of your program, the logic in the monad is activated and it decides how (and if) it should perform the next step.

See this example from Monads in Ruby (with nice syntax!):
def with_failable_rbinding(first_divisor)
with_monad Failable do
val1 =xx fdiv(2.0, first_divisor)
val2 =xx fdiv(3.0, 1.0)
val3 =xx fdiv(val1, val2)
Here you have a do-block containing a sequence of divisions composed using the special monadic assignment =xx. Everything executed within the block is handled by the Failable monad, wich is programmed to return a special non-numeric Failure value when a division by 0 is performed:

puts fdiv_with_binding(1.0)
=> Success(0.666666666666667)
puts fdiv_with_binding(0.0)

=> Failure(cannot divide by zero)

For every side effect in traditional imperative programming (control of errors, concurrency, input/output, commit/rollback of the whole application state, non-determinism... and some more) you can get some specific logic added for it, anytime, for free, without any syntactic complexity other than the sequence operation. Better yet, you can change the allowed side effects without actually changing a single line of your imperative procedure, just by redefining the logic encapsulated in the monad that glues the statemens in the procedure together.

See some more of my intuitions on monads here.