[Haskell] manipulating untyped lambda-calculus in Haskell

[Vivian McPhail]

Hi,

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:

\begin{code}
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) 
\end{code}

then what I need is a function to apply these:

\begin{code}
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"
\end{code}

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.

Thanks,

Vivian McPhail 

PS Is there something I can do with the Typeable class of hs-plugins?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell/attachments/20050430/13928a72/attachment.htm