Lambda the Ultimate

... he even says so:

We have already mentioned Ramsey’s (2003; 2004)
independent use of the same basic technique to embed the LuaML interpreter.

Actually, no. See the discussion in Section 6.1 about why you can't embed into a monadic interpreter in Haskell or in ordinary ML. What's surprising is that by using an amazingly clever idea due to Andrzej Filinski, you *can* do it in an ML with control operators (e.g. SML/NJ or MLton (but unfortunately not SML.NET)).

... which is obviously impossible in Haskell (unless you make all functions be in a monad that supports shift/reset but that kind of defeats the point though it may still have some use). The issue in the paper is how to turn a "pure" type into it's monadic equivalent. However, it should be mostly straightforward to simply embed the monadic equivalent. This means you can't embed map, but instead must embed mapM (actually uncurried functions may be a bit more convenient).

It seems like we could use GADTs to (mostly) use the host language's typesystem to represent the hosted language's.

type F s t = s -> Eval t

data Expr t where
  Id   ::                 String -> Expr t
  Con  ::                      t -> Expr t
  Lam  ::       String -> Expr t -> Expr (F s t)
  App  :: Expr (F s t) -> Expr s -> Expr t

eval           :: Expr t -> Eval t
eval (Id v)    = lookupTypedVar v
eval (Con x)   = return x
eval (Lam v e) = return (\x -> setLocalVar v x e)
eval (App f x) = do f'  Eval t
...
setLocalVar    :: String -> s -> Eval t -> Eval t
...

Functions like lookupTypedVar and setLocalVar require some work, but at the very least they can be done with an embedding/projection pair and a typeclass.

Unfortunately, lifting host functions into the interpreted language is tricker this way because we have to transform α → β into α → Eval β so that plus :: Int → Int → Int becomes embed plus :: Int → Eval (Int → Eval Int). There's probably a clever way to do that, but it escapes me.

Also, there's the question of how to parse the interpreted language and produce the appropriately-typed values of Expr. I think there's a trick for that, but I could be wrong.

Unfortunately, lifting host functions into the interpreted language is tricker this way because we have to transform α → β into α → Eval β so that plus :: Int → Int → Int becomes embed plus :: Int → Eval (Int → Eval Int). There's probably a clever way to do that, but it escapes me.

This is covered in the paper and was the issue Nick Benton raised with my comment. In the particular case you mention you can do it and should be able to finagle the type class machinery to do it for you, but in the general higher order case you have problems: how do you turn an: (A → B) → C into (A → M B) → M C ? You'd have to have some way of turning (A → M B) into an (A → B) which isn't possible in general unless the effects represented by M can be handled implicitly.

You're right, that loses the "higher-order" aspect.

I suppose if more functions were defined over generic Arrow types, this would be less of a problem. Just use Kleisli m instead of (→).

(On the other hand, I wouldn't want to have to explain type signatures like ArrowFunctor α φ ⇒ α β γ → α (φ β) (φ γ) to newbies.)

I attempted to extend the example above with simple error handling when projection fails, ie:

class EmbedProject a where
    embed :: a -> U
    project :: U -> Maybe a

It all goes straightforwardly...

instance EmbedProject Int where
    embed = UI
    project (UI i) = Just i
    project _ = Nothing

instance (EmbedProject a, EmbedProject b) => EmbedProject (a,b) where
    embed (a,b) = UP (embed a) (embed b)
    project (UP a b) = do a' <- project a
			  b' <- project b
			  return (a',b')
    project _ = Nothing

...etc, until it comes to to defining the instance of EmbedProject for functions. embed is ok - incorrect parameters map to return values of the UU type. But I'm lost as to what needs to happen with the project function. The definition belows doesn't compile because (project.f.embed) has type a->Maybe b, but I need something of type Maybe (a->b):

instance (EmbedProject a, EmbedProject b) => EmbedProject (a -> b) where
    embed f = UF (\a -> maybe UU (embed.f) (project a) )
    project (UF f) = project.f.embed
    project _ = Nothing

Any suggestions? Is there something obvious (or non-obvious!) that I am missing?

[I just came across this whole embedded interpreters idea and found it quite interesting. My response in this discussion is probably way too late but perhaps someone might still find it useful...]

This can be solved by splitting the EmbedProject instance for functions into two parts:

instance (EmbedProject a, EmbedProject b) => EmbedProject (a -> b) where
    embed f = UF (\a -> maybe UU (embed . f) (project a))

instance (EmbedProject a, EmbedProject b) => EmbedProject (a -> Maybe b) where
    project (UF f) = Just (project . f . embed)
    project _ = Nothing

This allows to embed any host language function into the interpreter (as before) but projection can only be done onto functions of the form a -> Maybe b.

The reason is that the execution of an interpreted function could fail with a dynamic type error and so an infallible function signature like (a -> b) doesn't work.