jeremy at n-heptane.com
Tue Mar 25 15:55:47 EDT 2008
At Tue, 25 Mar 2008 10:34:07 -0400,
Jonathan S. Shapiro wrote:
> 2. Every valid Haskell program *would* have a direct transcription to
> BitC *if* BitC provided support for monads.
> This leads me to the question: should we add the monad concept to BitC?
The core support for Monads in Haskell is just a class declaration in
class Monad m where
-- | Sequentially compose two actions, passing any value produced
-- by the first as an argument to the second.
(>>=) :: forall a b. m a -> (a -> m b) -> m b
-- | Sequentially compose two actions, discarding any value produced
-- by the first, like sequencing operators (such as the semicolon)
-- in imperative languages.
(>>) :: forall a b. m a -> m b -> m b
-- Explicit for-alls so that we know what order to
-- give type arguments when desugaring
-- | Inject a value into the monadic type.
return :: a -> m a
-- | Fail with a message. This operation is not part of the
-- mathematical definition of a monad, but is invoked on pattern-match
-- failure in a @do@ expression.
fail :: String -> m a
m >> k = m >>= \_ -> k
fail s = error s
There are also Monad instances for a number of different datatypes,
such as Maybe, lists, etc. I believe this stuff could easily be added
as a third-party library.
There are some monad instances which are built on top of low-level
compiler support, such as ST, STM, IO, etc. Supporting these would be
far more difficult since you have to implement the low-level STM
primitives in BitC before you can create a STM Monad. Even if you only
support the IO monad, there are still a lot of issues to worry
about. For example, you would need to make sure you set your buffering
modes the same (ie, BlockBuffer, LineBuffer, NoBuffering), or you will
get different results. And, if you look at things like lazy IO, then
things get fun real fast.
The third piece of support for monads in Haskell is the 'do
notian'. This is just syntactic sugar.
I suspect the more difficult part of the translation is the differing
evaluation strategies. You can simulate non-strict evaluation to a
degree in ocaml by using the lazy and force constructs. However, last
time I tried, I was unable to successfully convert the following
function to ocaml while retaining the same non-strict evaluation:
-- | 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
span :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@ = (xs, xs)
span p xs@(x:xs')
| p x = let (ys,zs) = span p xs' in (x:ys,zs)
| otherwise = (,xs)
I believe it was specifically this construct that tripped me up.
let (ys,zs) = span p xs' in (x:ys,zs)
Note that it passes a portion of the result of the function in as an
argument to the function. Of course, even if you could transcribe from
Haskell -> BitC by adding enough lazy/force commands -- it would be
very difficult for the user to continue to extend the code that way.
Also, there are some things that Haskell got wrong when they did
Monads. For example, The Monad class should probably require a Functor
instance. Additionally, it would be nice to split the Monad class into
two classes so that you can make restricted Monads. For example, it
would be nice to have a Set Monad. But, the elements of a set must be
instances of the Ord class. There is no way to specify that
restriction with the current Monad class, though it is well know how
it could have been done.
And, finally, the addition of the fail method to the Monad class is
widely considered to be a mistake.
So, I think the differing evaluation strategies would make a direct
transcription from Haskell->BitC rather difficult. You could, of
course, transform the Haskell code into a strict CPS style (or
something similar) -- but it would no longer be suitable for human
On the other hand, monads are a useful construct. Most of the monads
can be implemented in a standard library, with no special support from
the compiler (assuming the class support in BitC is sufficiently
similar to Haskell 98). In Haskell, the do-notation is also
nice. Depending on what happens with BitC's syntax, adding some
explicit sugar could be nice as well.
More information about the bitc-dev