javascript - How to type check recursive definitions using Algorithm W? -

i implementing algorithm w (the hindley-milner type system) in javascript:

the function implements above rules typecheck , has following signature:

typecheck :: (context, expr) -> monotype 

it defined follows:

function typecheck(context, expression) {     switch (expression.type) {     case "var":         var name = expression.name;         var type = context[name];         return inst(type);     case "app":         var fun = typecheck(context, expression.fun);         var dom = typecheck(context, expression.arg);         var cod = new variable;         unify(fun, abs(dom, cod));         return cod;     case "abs":         var param = expression.param;         var env   = object.create(context);         var dom   = env[param] = new variable;         var cod   = typecheck(env, expression.result);         return abs(dom, cod);     case "let":         var assignments = expression.assignments;         var env = object.create(context);          (var name in assignments) {             var value = assignments[name];             var type  = typecheck(context, value);             env[name] = gen(context, type);         }          return typecheck(env, expression.result);     } } 

a little bit data types:

1. a context object maps identifiers polytypes.

   type context = map string polytype 

2. an expression defined following algebraic data type:

   data expr = var { name        :: string                          }           | app { fun         :: expr,            arg    :: expr }           | abs { param       :: string,          result :: expr }           | let { assignments :: map string expr, result :: expr }           | rec { assignments :: map string expr, result :: expr } 

in addition, have following functions required algorithm not essential question:

inst ::  polytype -> monotype abs  :: (monotype,   monotype) -> monotype gen  :: (context,    monotype) -> polytype 

the inst function specializes polytype , gen function generalizes monotype.

anyway, want extend typecheck function allow recursive definitions well:

where:

1. 
2. 

however, stuck chicken , egg problem. context number 1 has assumptions v_1 : τ_1, ..., v_n : τ_n. furthermore, implies e_1 : τ_1, ..., e_n : τ_n. hence, first need create context in order find types of e_1, ..., e_n in order create context need find types of e_1, ..., e_n.

how solve problem? thinking of assigning new monotype variables identifiers v_1, ..., v_n , unifying each monotype variable respective type. method ocaml uses let rec bindings. however, method not yield general type demonstrated following ocaml code:

$ ocaml         ocaml version 4.02.1  # let rec foo x = foo (bar true)        , bar x = x;; val foo : bool -> 'a = <fun> val bar : bool -> bool = <fun> 

however, ghc compute general type:

$ ghci ghci, version 7.10.1: http://www.haskell.org/ghc/  :? prelude> let foo x = foo (bar true); bar x = x prelude> :t foo foo :: bool -> t prelude> :t bar bar :: t -> t 

as can see, ocaml infers type val bar : bool -> bool while ghc infers type bar :: t -> t. how haskell infer general type of function bar?

i understand @augustss' answer type inference recursive polymorphic functions undecidable. example, haskell cannot infer type of following size function without additional type annotations:

data nested = epsilon | cons (nested [a])  size epsilon     = 0 size (cons _ xs) = 1 + size xs 

if specify type signature size :: nested -> int haskell accepts program.

however, if allow subset of algebraic data types, inductive types, data definition nested becomes invalid because not inductive; , if not mistaken type inference of inductive polymorphic functions indeed decidable. if so, algorithm used infer type of polymorphic inductive functions?

you type check using explicit recursion primitive fix having type (a -> a) -> a. can insert fix hand or automatically.

if want extend type inferences that's quite easy too. when encountering recursive function f, generate new unification variable , put f type in environment. after type checking body, unify body type variable , generalize usual. think suggest. not allow infer polymorphic recursion, in general undecidable.