ghc - Haskell type-level lambda calculus error (or lack thereof) -

i have been reading page in haskell wiki on type arithmetic , have had little trouble section on lambda calculus embedded in type system. section, gathered following code should not work ghc/ghci - apparently ghc shouldn't able determine type signature of g.

{-# options -fglasgow-exts #-} {-# language flexiblecontexts #-} {-# language undecidableinstances #-}  data x data app t u data lam t  class subst s t u | s t -> u instance subst x u u instance (subst s u s', subst t u t') => subst (app s t) u (app s' t') instance subst (lam t) u (lam t)  class apply s t u | s t -> u instance (subst s t u, eval u u') => apply (lam s) t u'  class eval t u | t -> u instance eval x x instance eval (lam t) (lam t) instance (eval s s', apply s' t u) => eval (app s t) u  f :: eval (app (lam x) x) u => u f = undefined g :: eval (app (lam (app x x )) (lam (app x x ))) u => u g = undefined 

note had add flexiblecontexts , undecidableinstances, since given code doesn't seem compile without these extensions. however, when run ghci (version 8.0.2), following results:

*main> :t f f :: x *main> :t g g :: u 

this strange me, because type u hasn't been defined anywhere. result of 2 language extensions above interacting each other , glasgow-exts? if so, how?

the type u lone type variable -- a in undefined :: a.

to boil down bare essentials, consider alternate file:

{-# language undecidableinstances #-} {-# language flexibleinstances #-}  class loopy instance loopy => loopy  x :: loopy => x = undefined 

if ask type of x in ghci, tell has type a, no context. may seem bit magical; have realize instance resolution in ghc allowed recursive, , implementation goes great lengths support this.

we can follow along in detail what's happening in example, if like, analogous above file. here details.

so, we'd see if we're allowed have instance:

eval (app (lam (app x x)) (lam (app x x))) u 

we know

instance (eval s s', apply s' t u) => eval (app s t) u 

so we're allowed have whenever have both of these:

eval (lam (app x x)) s' apply s' (lam (app x x)) u 

the first 1 easy, since:

instance eval (lam t) (lam t) 

so we're allowed have our cake when have:

apply (lam (app x x)) (lam (app x x)) u 

since

instance (subst s t u, eval u u') => apply (lam s) t u' 

to find our cake, should check under these 2 rocks:

subst (app x x) (lam (app x x)) u eval u u' 

from

instance (subst s u s', subst t u t') => subst (app s t) u (app s' t') 

we learn can have cake when

subst x (lam (app x x)) s' subst x (lam (app x x)) t' eval (app s' t') u' 

which easy make progress on, since:

instance subst x u u 

therefore, can have our original instance whenever:

eval (app (lam (app x x)) (lam (app x x))) u' 

but, hey presto! original instance looking for. in summary can have our original instance whenever can have our original instance. declare can have our original instance, , can have our original instance! isn't peachy.