Generic Haskell bridge + Pure evaluation + GHC 7.8.4 support

[hanshoglund]

This monster PR does the following:

• Make Expresso cross-compile with GHC 8.0.2 (reproducible using the stack file in the repo) and GHC 7.8.4 (using a slightly secret build system, not reproducible for now)
• Rewrite evaluator to be pure, using a new class MonadEval to represent the evaluation step. A default implementation simply ingests/spits out the thunks. Laziness tests (and peek in REPL) still work.
• Add a Haskell bridge (see below)
• Removes the [Char] optimization, thus simplifying the evaluator code. I plan to add Text and ByteString types instead, which allow an efficient implementation in terms of the corresponding HS types.

Haskell bridge docs (tentative)

Conventions here are based on aeson: the classes FromValue and ToValue converts Expresso values into Haskell ones and vice versa. Conversions HS -> Expresso is total, while Expresso -> HS is partial, using MonadError for failure. The instance (ToValue a, FromValue b) => FromValue (a -> b) allow conversion of (first-order) Expresso functions to Haskell functions. There is also a class HasType, which maps (monomorphic) Haskell types to Expresso types.

Generic instances can be derived for the above classes. The main caveat is that recursive Haskell types will generate infinite Expresso types: the standard way to solve this is to either avoid recursive types on the Haskell side, or provide custom implementations in terms of [a] (the only recursive Expresso type).

[willtim]

Hi Hans,

The lazy tests are misnamed, they are really non-strictness tests. Laziness is of course difficult to test as it's a performance optimisation. The idea is that the second time a thunk is forced, a cached value is returned. I could not see how to do this without mutable state. Are you sure your new evaluator is really lazy and not just non-strict?

I tried testing using import expressions in the Repl, but these now seem to hang? E.g. typing: import "Prelude.x".

There's also a lot of new compiler warnings. :/

Given the orthogonal features added, is it possible to split this pull request up in anyway?

Thanks, Tim

[hanshoglund]

Agree re the PR size. Alas some of the changes relate, e.g. the FromValue class needs to be defined in terms of the evaluation mechanism (MonadEval) etc. Will adress some of the issues here for now:

1. I believe my implementation achieves call-by-need, by effectively carrying the Haskell thunks in the Lam constructor. Anecdotal evidence:

> let fib = fix (fib -> n -> if (n < 2) then n else fib (n-1) + fib (n-2))
> let p = fib 29
> p
121393 -- slow
> p
121393 -- fast
> p
121393 -- fast
> let x = fib 30 in {a=x}
{a = 832040} -- takes N seconds
> let x = fib 30 in {a=x,b=x,c=x,d=x}
{a = 832040, b = 832040, c = 832040, d = 832040} -- takes N seconds, rather than (N*4) seconds

2. Can not reproduce the import Prelude issue. Did you have local changes?

3. The only major change for GHC 7.8.4 support is faking explicitly bidirectional pattern synonyms. E.g. instead of:

pattern Pat a b       <- (proj -> (PatF a b)) where
    Pat a b = inj (PatF vs t)

we simply do

pattern Pat a b       = (proj -> (PatF a b)) 
_Pat a b = inj (PatF vs t)

so lots of added underscores in the typechecker/evaluator. This is ugly, but the idea is they should be easy to drop at some point.

[hanshoglund]

By the way I think you have CRLF endings in your Eval.hs. You probably want to normalize to get a sensible git diff (other files used LF, so I simply normalized this one).

[willtim]

Hi Hans,

I'm still not sure the evaluator is working correctly with respect to laziness: e.g. :peek { x = fib 300 } seems to hang as if the fib 300 is being evaluated.

We could use STRefs to be confident about the thunk behavior? These would then give us the pure interface you need on the outside.

Regarding the Maybe type. I originally added it because it was a closed type and the variant constructors were open. However, now that we have type annotations, we can of course provide some smart constructors to construct a closed variant, e.g.

just : a -> <Just : a, Nothing : {} > nothing : <Just : a, Nothing : {} >

So I agree that it is probably a good idea to get rid of the special-case maybe. Perhaps we should add those smart constructors into the Prelude?

Regarding the text and blob functions: the reason why I tried to originally unify Strings and Lists (i.e. repeating the same mistake dating back to Lisp), was to reduce the number of primitives. Having Text and List versions of common operations such as map, fold, intercalate etc I thought was burdensome. The biggest problem being that we want to namespace them. However, one idea would be to expose the Text primitives through a record of functions (module). There are a few ways of doing this. Perhaps the simplest is to expose the actual Text prims with horrible mangled names e.g. "text_intercalate" and then create a Text.x module which exposes them with nice names. Users can then simply:

let text = import "Text.x" text.intercalate ... etc

Looking forward to more improvements! I feel a merge is close! Thanks, Tim

[hanshoglund]

Thanks,

Evaluator: on my integration branch I actually diverged further, as I wanted to replace the concrete EvalM with a type parameter. I'm experimenting with something like this. This is nice, because we can now use this class to overload a set of primitive effects in the evaluator, not just laziness/failure.

 class MonadError String f => MonadEval f where
    force    :: Thunk f -> f (Value f)
    delay    :: f (Value f) -> f (Thunk f) -- a.k.a. mkThunk
    -- More effects:
    error :: String -> f Void
    trace :: String -> f (Value f)
    -- etc

My current (possibly faulty) implementation is simply:

instance MonadEval EvalM where
  force = getThunk
  delay = return . Thunk
  error = throwError
  trace x = do { toValue <$> tell x  }

but if I'm not mistaken this could be implemented in terms of STRefs/TVars or whatever.

The main casualties of this approach is simplicity (as Value/Thunk are now parameterized on the effect type, they must kind (Type -> Type) -> Type) and the instance instance (ToValue a, FromValue b) => FromValue (a -> f b), as it is impossible to require that the f in the instance head is the same as the one being "passed" to the fromValue call. However that instance seemed suspicious to me anyway, and the following combinators can be provided instead:

fromValue :: (MonadEval f, FromValue a) => Value f -> f a
fromValue1 :: (ToValue a, FromValue b, MonadEval f) => Value f -> a -> f b
fromValue2 :: (ToValue a, ToValue b, FromValue c, MonadEval f) => Value f -> a -> b -> f b
-- etc

Re: Maybe: nice idea, will do that.

Re: Text/ByteString I basically agree. Of course in theory it would be nice if everything was representable by records/variants, but the lack of general recursive types prevents that. Instead I link to think of this as a type system based on {}, <>, [], (->), and other types are isomorphic to a composition of these, e.g.

Bool ≃ <True:{},False:{}>
Integer ≃ { sign:Bool, val:[{}] }
Word8 ≃ { Bool, Bool, ... }
Blob ≃ [Word8]
-- etc

This gives us a nice set of minimal primitives: just witness the isomorphism! Things like reverse/intercalate, can now be written in the language itself using composition these minimal primitives (text.reverse = text.fromList . reverse . text.toList etc). We might of course want to implement e.g. text.reverse as a primitive for performance, but the user should be able to believe that the implementation is just a composition of minimal/public primitives.