[Haskell] manipulating untyped lambda-calculus in Haskell
vivian.mcphail at paradise.net.nz
Sat Apr 30 06:09:42 EDT 2005
I am writing a NL parser in Haskell, relying on combinatorial grammar for the syntactic derivation.
Each word has an associated syntax and semantics, the semantic term is a lambda expression loaded at run-time using hs-plugins.
I : np : <semantic term> :: Sem m a
love : s\np : <semantic term> :: Sem m a
Predicates in english can have up to 5 arguments, and some of these arguments are functions, so the type of Sem m a is an enumeration of the types that we can build up from (STT m a) and (->).
I started by enumerating this by hand:
data Monad m => Sem m a = ZSem (SST m a)
| USem (SST m a -> SST m a)
| BSem (SST m a -> SST m a -> SST m a)
| TSem (SST m a -> SST m a -> SST m a -> SST m a)
| QSem (SST m a -> SST m a -> SST m a -> SST m a -> SST m a)
| FSem (SST m a -> SST m a -> SST m a -> SST m a -> SST m a -> SST)
| U1Sem ((SST m a -> SST m a) -> SST m a)
| B1Sem ((SST m a -> SST m a) -> SST m a -> SST m a)
| T1Sem ((SST m a -> SST m a) -> SST m a -> SST m a -> SST m a)
then what I need is a function to apply these:
applySem :: Monad m => Sem m a -> Sem m a -> Sem m a
applySem (USem a) (ZSem b) = ZSem $ a b
applySem (BSem a) (ZSem b) = USem $ a b
applySem (TSem a) (ZSem b) = BSem $ a b
applySem (QSem a) (ZSem b) = TSem $ a b
applySem (U1Sem a) (USem b) = ZSem # a b
applySem (B1Sem a) (USem b) = USem $ a b
applySem (T1Sem a) (USem b) = BSem $ a b
applySem (T2Sem a) (ZSem b) = B1Sem $ a b
applySem (B12Sem a) (USem b) = U1Sem $ a b
applySem _ _ = error "application of Semantic functions"
My typing system ensures that only the correct functions will be applied to each other (the typing system manipulates lambda terms with an additional type (Stc Name (Sem m a)). A complete parse will reduce the lambda terms to closed terms containing only App and Stc, no Var or Lam. I can then use applySem to reduce the term to a single (Sem m a) type, which I can then run.
What I have done thus far is enumerate by hand, but for full coverage for 5 argument predicates I need to list 5^5 data constructors and entries in the applySem function. For theoretically complete coverage I would need to enumerate all possible types constructed from (STT m a) and (->).
It seems that I must be missing something? Is there a more elegant way of doing this?
One can make the observation that the applySem function always applies a function of type (b -> a) to a function of type b to yield a function of type a.
I suppose I could write a code generator (in haskell) that enumerates all possible derivations of (STT m a) and (->) but there would still be 5^5 data constructors.
PS Is there something I can do with the Typeable class of hs-plugins?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell