Why not use one of the 40-year old type checking algorithms? https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system What type do you infer for def id(n): return n ? On 07.09.2015 05:21, David Foster wrote:
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 program.
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 know: (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.
-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/