4 ms·
Predicting Variable Types in Dynamically Typed Programming Languages
- phoe-krk 8y agoHow 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 agoI’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 agoProbably 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 agoKind 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 agoData 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 agoIt 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 agoDFA 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 agoIf 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.
- satyanash 8y ago> ...allows programmers to write code quickly by not requiring to declare the types of each variable which are determined at run-time based on the values assigned to that variable, thereby increasing programmer productivity Modern compilers for statically typed languages are really good at inferring types of various identifiers based on multiple hints in a deterministic way (see Kotlin, Swift etc). Mentioned statically typed languages C,C++ and Java are pretty old and therefore carry some baggage of verbosity that is no longer needed. > ...since the variable types are not declared in the source code, the source code becomes difficult to understand and extend > For programmers working on the large code base written in dynamic languages, it is hard to understand the control flow of the program if the types are not available at the compile time. Dynamic languages as a result of their "dynamicness" tend to allow much better expression of control flow when compared to static languages. Only recently available statically typed languages have targeted expressiveness as a first class goal in designing the language. In fact, statically typed languages are notorious for obtuse control flows as a result of their type enforcement (see C, C++, Golang)
- saagarjha 8y ago> Modern compilers for statically typed languages are really good at inferring types of various identifiers based on multiple hints in a deterministic way (see Kotlin, Swift etc) I think it’s importatnt to mention that in Swift this lookup has exponential behavior, and can time out if the expression is too complex.
- hellofunk 8y agoI’ve always wondered why Swift and Kotlin, which are two very similar languages of approximately the same age, have such widely different compiler stability. Kotlin feels quite solid and mature, while Swift sometimes just feels like one big hack. Considering the enormous resources Apple has compared to JetBrains, I find it strange their trajectories have been so very different.
- continuational 8y agoJetBrains business is all about understanding programming languages - Java in particular. And Kotlin is very, very close to Java.
- sifoobar 8y agoSnigl [0] traces the code before running it; simulating stack contents and inferring generic calls based on that information as far as possible, among other things. It's not perfect, but it's the only way I've found that makes sense in combination with Forth-like stack semantics where function parameters are never specified explicitly. And that runs fast enough to make sense in an interpreted language. I also like that it's implemented as a transformation on VM code, which makes it flexible and easy to debug. [0] https://gitlab.com/sifoo/snigl#tracing https://gitlab.com/sifoo/snigl#tracing
- mlevental 8y agokind of cool but why is the model trained on such a small data set? why not train it on a bunch of codebases that use type hints?