[Haskell-cafe] embedded interpreters

Tim Docker timd at macquarie.com.au
Thu Apr 21 00:14:17 EDT 2005


[I've asked this question on lambda-the-ultimate, but it remained unanswered,
 and it's probably more appropriate here in any case]

The papers referenced here:

	http://lambda-the-ultimate.org/node/view/552

describe a means of projecting values in an implementation
language to and from values in an embedded interpreted language. The papers
use ML, but Derek Elkin gives a straightforward translation to haskell, via
a typeclass. An excerpt is here:

> data U = UF !(U -> U) | UP !U !U | UU | UB !Bool | UI !Int | US !String
>     deriving Show
> 
> class EmbedProject a where
>     embed :: a -> U
>     project :: U -> a
> 
> instance EmbedProject Int where
>     embed = UI
>     project (UI i) = i
> 
> instance (EmbedProject a, EmbedProject b) => EmbedProject (a -> b) where
>     embed f = UF (embed . f . project)
>     project (UF f) = project . f . embed

This is nice and tidy. However, the project function can fail in practise - in
the above, this results in pattern matching failures. I'd like have more control
of this, which suggests the following:

> class EmbedProject a where
>     embed :: a -> U
>     project :: U -> Maybe a
> 
> instance EmbedProject Int where
>     embed = UI
>     project (UI i) = Just i
>     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?

Thanks,

Tim


More information about the Haskell-Cafe mailing list