« Expression problem | Main | Exchanging recursive types for a bug »

November 17, 2004

Recursive types

I added the 'case' without 'otherwise' operator to the interpreter and managed to get the Postgres library for O'Caml to work.

I also discovered I have a problem with the SLinks type inference algorithm: I believe the current type representation is not powerful enough to give a safe type to recursive functions. Unfortunately, I was not careful enough when adding recursive functions to the language and only tested (and thought) it with recursive functions that returned single values, and not structures built by the recursive function. Here is an example of the problem:
defrec ^f = fun ^x -> case x of <#a=^a> in f(a) or <#b=^b> in b;
Receives type: (<#a:pre('1), #b:pre('2)> -> '2). Of course, type variable '1 should really be <#a:pre('1), #b:pre('2)> where '1 should really be ... and so this f function is not type safe:
f(<#a=5>);
Leads to a fatal exception at runtime.