[Haskell-cafe] I wrote a type checker: ARF. Is it novel?

David Foster davidfstr at gmail.com
Mon Sep 7 03:21:16 UTC 2015

I've written a small untyped language calculus (ARF) and an 
interprocedural flow-based type checker to explore techniques for 
efficiently inferring all types in the presence of recursive function 
calls, with no prior type declarations or annotations required in the 
original program.

The type checking algorithm I've come up with appears not only to work 
but also to have good performance: O(m^2) time in the worst case and 
O(m) time in the average case, where m is the number of functions in the 

So the question I'd like to pose to any type system buffs on this list is:
(1) Is such an interprocedural flow-based type checking algorithm with 
that kind of performance likely to be novel?

And if you have some interest and time to actually review the strategy 
and/or implementation of the algorithm at 
<https://github.com/davidfstr/arf#assign-recurse-flow-arf>, I'd love to 
(2) Are there similar type checking algorithms that already exist in the 
academic literature?

I'm posting these questions here because I'm guessing that a number of 
folk that work with type systems and type checkers are likely to be 
subscribed to this list. If there are other more-appropriate venues, I'd 
love to hear about about them as well.

David Foster

More information about the Haskell-Cafe mailing list