Version 20 (modified by benl, 9 years ago) (diff)


Effect System

Effect typing vs State monads

Instead of state monads (like IO), Disciple uses default strict evaluation and effect typing to deal with computational effects. Effect typing helps us write less code than in Haskell because the types of effectful functions have the same shape as their pure counterparts.

For example, in Haskell the pure map function has type:

map :: (a -> b) -> [a] -> [b]

but if we need to pass an effectful function defined in terms of a state monad, we must use the monadic version, mapM instead.

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

This puts us in a situation where we really need two copies of every higher-order function, one pure and one monadic. This is even more of a problem when a library (like Data.Map) exports pure versions of some functions but not monadic ones. In this case we either have to refactor our code to be less monadic, or spend time writing a function that should really be in the library.

In Haskell, because putStr prints to the screen it has the IO constructor in its return type:

putStr :: String -> IO ()

In Disciple, this fact is encoded as an effect on the function arrow instead:

putStr :: String -(!Console)> ()

Which we can also write as:

putStr :: String -(!e1)> ()
       :- !e1 = !Console

In this type, !e1 is an effect variable, much like a is a type variable. !Console is an effect constructor that tells us what else happens when putStr is called, besides returning a unit value.

Because this second version of putStr doesn't have the monad in its type, in most cases we can just use the plain version of map and not have to worry about mapM.

main () 
 = do   map putStr ["one", "two", "three"]   -- print 'onetwothree'

We still think the Monad type class is useful, and we support it as well. However, when writing Haskell programs we've found that most uses of Monad are for IO, and to manage the internal state of the program. In Disciple, we use effects for state-based functions because it's more convenient, and reserve Monad for things that definitely want a non-standard notion of sequence, like parser combinators.

Extended type information

From the previous example, it might look as though we've lost the information that putStr has an effect and descended into the quagmire of untracked side effects and imperative programming. This would be true if map only had the simple type that it does in Haskell (or ML), because there'd be no way to track the fact that the application of map also causes a !Console effect like its argument does. However, during type inference DDC performs an effect analysis on the program and can determine that this code also writes to the screen. As this information is inferred you don't need to write it yourself, but you can add it to signatures if you want to be precise about how a function is supposed to behave. When the extra information is included, the "extended" type of map becomes:

map :: forall a b %r0 %r1 !e0
    .  (a -(!e0)> b) -> List %r0 a -(!e1)> List %r1 b
    :- !e1  = !Read %r0 + !e0

The variables starting with % are region variables, and the type (List %r0 a) represents a list in a region of memory called %r0 which has elements of type a. The effect sum !{!Read %r0; !e0} records the fact that the map function, when applied to both its arguments, has the effect of reading the input list as well as doing whatever the argument function does.

The Disciplined Disciple Compiler (DDC) uses this effect discipline to track which parts of the program cause computational effects and which are pure. This allows it to check the type safety of programs that use these effects, and to perform the same sort of code transformation style optimizations as done by other Haskell compilers such as GHC.

However, none of this would be useful if you actually had to write these extended types in regular programs. It's a good thing then that, for the most part, you can ignore the extended information when writing programs. Because all the extra information is orthogonal to the main shape of the type, that is, its argument and return data types, the compiler can fill this in for you behind the scenes. This is called type elaboration. The extra information is present in the interface files and core language, but you'll only have to worry about it if you import foreign functions from C land or start to mix laziness with destructive update in the same program.

The definition of map that you would write in a real Disciple program is just the same as in Haskell, including the type signature:

map :: (a -> b) -> [a] -> [b]
map f []        = []
map f (x : xs)  = f x : map f xs