[Haskell] manipulating untyped lambda-calculus in Haskell
Vivian McPhail
vivian.mcphail at paradise.net.nz
Sat Apr 30 06:09:42 EDT 2005
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
More information about the Haskell
mailing list