26 ms·

How does this relate and compare to actual type inference? For example, Common Lisp implementation SBCL is able to infer types pretty nicely now and it doesn't

How does this relate and compare to actual type inference? For example, Common Lisp implementation SBCL is able to infer types pretty nicely now and it doesn't need neural networks for "predicting" the types with some kind of chance.

User23 8y ago
I’m not sure how much of it is still relevant to SBCL since the fork was quite a while back, but the CMUCL user manual is a great read that describes how type inference and many other things work. https://www.cs.utexas.edu/users/jared/Milawa/Support/cmucl64/src/docs/cmu-user/index.html https://www.cs.utexas.edu/users/jared/Milawa/Support/cmucl64...
- BMarkmann 8y ago
  Probably still relevant given how SBCL's user guide says (in the only section that includes mention of type inferencing): "FIXME: The material in the CMUCL manual about getting good performance from the compiler should be reviewed, reformatted in Texinfo, lightly edited for SBCL, and substituted into this manual. In the meantime, the original CMUCL manual is still 95+% correct for the SBCL version of the Python compiler."
ychen306 8y ago
Kind of disappointed that they don't include this kind of analysis as baseline. Especially that the types infer by traditional algorithms are usually sound, which is not what you can say for ML-based methods (so far).
ScottBurson 8y ago
Data flow analysis will certainly predict a fair number of types in typical programs in dynamically-typed languages, but there will also be lots of cases it can't handle. I don't know the details of the CMUCL/SBCL type inference algorithm, but I've worked on whole-program data flow analysis, and there are still lots of types it fails to recover, for various reasons. Often, for example, the entire program is not available for analysis; if one doesn't know all the places a particular function can be called, one can't soundly infer all the types it might be passed. Nonetheless, in practice a given parameter of such a function is normally passed arguments of a particular type (or subtypes thereof), and frequently, clues such as the parameter name can help one take a pretty good guess as to what that type is. Since such a guess is sometimes going to be wrong, it can't safely be used for optimization, but it can be very useful for other purposes, such as analyzing the program to find potential security vulnerabilities.
- vidarh 8y ago
  It can still be used for optimization in many cases depending on the language, e.g by generating specialised versions and shunting calls from known call sites to the specialised version when you can either guarantee the guesses are right or cheaply lift guards up the call stack.
- seanmcdirmid 8y ago
  DFA isn’t usually used in type inferencing algorithms, at least ones that generate types for programmers rather than compiler optimizations. It isn’t that it is expensive, but in general syntax tree walking works well enough. Whole program analysis is too expensive for type inference (or much of anything for that matter) even with its precision ramped all the way down via something like CFA0. Type inference with sub typing is a very similar problem to alias analysis, which hints at why doing it in any but very restrictive contexts is too expensive.
  - ScottBurson 8y ago
    If you don't need perfect soundness, whole-program 1-CFA can be made practical by heuristic pruning. I've done it successfully in a commercial static analysis product.

User23 8y ago

I’m not sure how much of it is still relevant to SBCL since the fork was quite a while back, but the CMUCL user manual is a great read that describes how type inference and many other things work. https://www.cs.utexas.edu/users/jared/Milawa/Support/cmucl64/src/docs/cmu-user/index.html https://www.cs.utexas.edu/users/jared/Milawa/Support/cmucl64...

BMarkmann 8y ago
Probably still relevant given how SBCL's user guide says (in the only section that includes mention of type inferencing): "FIXME: The material in the CMUCL manual about getting good performance from the compiler should be reviewed, reformatted in Texinfo, lightly edited for SBCL, and substituted into this manual. In the meantime, the original CMUCL manual is still 95+% correct for the SBCL version of the Python compiler."

ychen306 8y ago

Kind of disappointed that they don't include this kind of analysis as baseline. Especially that the types infer by traditional algorithms are usually sound, which is not what you can say for ML-based methods (so far).

ScottBurson 8y ago

Data flow analysis will certainly predict a fair number of types in typical programs in dynamically-typed languages, but there will also be lots of cases it can't handle. I don't know the details of the CMUCL/SBCL type inference algorithm, but I've worked on whole-program data flow analysis, and there are still lots of types it fails to recover, for various reasons. Often, for example, the entire program is not available for analysis; if one doesn't know all the places a particular function can be called, one can't soundly infer all the types it might be passed. Nonetheless, in practice a given parameter of such a function is normally passed arguments of a particular type (or subtypes thereof), and frequently, clues such as the parameter name can help one take a pretty good guess as to what that type is. Since such a guess is sometimes going to be wrong, it can't safely be used for optimization, but it can be very useful for other purposes, such as analyzing the program to find potential security vulnerabilities.

vidarh 8y ago
It can still be used for optimization in many cases depending on the language, e.g by generating specialised versions and shunting calls from known call sites to the specialised version when you can either guarantee the guesses are right or cheaply lift guards up the call stack.
seanmcdirmid 8y ago
DFA isn’t usually used in type inferencing algorithms, at least ones that generate types for programmers rather than compiler optimizations. It isn’t that it is expensive, but in general syntax tree walking works well enough. Whole program analysis is too expensive for type inference (or much of anything for that matter) even with its precision ramped all the way down via something like CFA0. Type inference with sub typing is a very similar problem to alias analysis, which hints at why doing it in any but very restrictive contexts is too expensive.
- ScottBurson 8y ago
  If you don't need perfect soundness, whole-program 1-CFA can be made practical by heuristic pruning. I've done it successfully in a commercial static analysis product.