4 ms·

There are many interesting threads in this post, one of which is using “non standard interpretations” of programs, and enabling the compiler to augment the huma

There are many interesting threads in this post, one of which is using “non standard interpretations” of programs, and enabling the compiler to augment the human-written code with the extra pieces necessary to get gradients, propagate uncertainties, etc. I wonder whether there’s a more unified discussion of the potential of these methods. I suspect that a lot of “solvers” (each typically with their own DSL for specifying the problem) might be nicely formulated in such a framework. (Particularly in the case of auto diff, I found recent work/talks by Conal Elliot and Tom Minka quite enlightening.) Tangentially, thinking about Julia, while one initially gets awed by the speed, and then the multiple dispatch, I wonder whether it’s deepest superpower (that we’re still discovering) might be the expressiveness to augment the compiler to do interesting things with a piece of code. Generic programming then acts as a lever to use these improvements for a variety of use cases, and the speed is merely the icing on the cake!

mccoyb 5y ago
Just a comment: you’re right on the money here. This is the dream that a few people in the Julia community are working towards. The framework of abstract interpretation, when combined with multiple dispatch as a language design feature, is absolutely insane. I think programming language enthusiasts might meditate on these points —- and get quite excited with the direction that the Julia compiler implementation is heading.
- benrbray 5y ago
  This sounds cool. Do you happen to have any links to share?
  - mccoyb 5y ago
    If you are curious, I would stop by the Julia slack — specifically the #compiler-plugin channel. Otherwise, if you’re curious about how Julia’s type inference algorithm works via abstract interpretation, I would recommend the following blog posts: https://juliacomputing.com/blog/2016/04/inference-convergence/ https://juliacomputing.com/blog/2016/04/inference-convergenc... https://juliacomputing.com/blog/2017/05/inference-converage2/ https://juliacomputing.com/blog/2017/05/inference-converage2...
shakow 5y ago
> the expressiveness to augment the compiler to do interesting things with a piece of code. Julia has very interesting propositions on the subject, from language-level autodiff (https://fluxml.ai/Zygote.jl/latest/ https://fluxml.ai/Zygote.jl/latest/) to automated probabilistic programming (https://turing.ml/dev/ https://turing.ml/dev/) through DEs (https://diffeq.sciml.ai/stable/ https://diffeq.sciml.ai/stable/) and optimization (https://jump.dev/ https://jump.dev/). The whole ecosystem is in ebullition, and I'm very eager to see if it will be able to transform in the comping years into a solid foundation able to rival the layers of warts stacked on top of Python.
- mccoyb 5y ago
  Just a nit: Zygote is not technically a language level library. In fact, none of the above libraries really are language level — they are all just Julia libraries, some of which use macros. With the exception of metaprogramming with macros, none of these libraries customize inference/opt to do something funky. Zygote (for example) is based on a language level feature — generated functions which allow multistage programming in Julia — but beyond using this feature it does not configure or otherwise modify the normal compiler pipeline. With Julia, it is sometimes tough to tell — but Diffractor (for example) I would consider a language level library, as it modifies the traditional compiler pipeline to perform inference and optimization in a specific way.
  - shakow 5y ago
    I guess it depends on what you call “language-level”; I mentioned these libraries because they all make use of macros and/or AST manipulation, which I would put somewhere in a grey area between language and compiler.
freemint 5y ago
Autodiff isn't even the most impressive application of non standard interpretation. The most impressive one is sparsity detection. If you have some arbitrary code that returns a matrix you can infer which elements of the matrix are guaranteed to be zero independent of input using non standard interpretation by taking all the branches of the program. This discovered sparsity can be exploited by a lot the generic algorithms in Julia that also are able to efficiently work on sparse matrices. There is also a way of combining this with AD to get automatic sparse hessian of optimization which is huge.

mccoyb 5y ago

Just a comment: you’re right on the money here. This is the dream that a few people in the Julia community are working towards. The framework of abstract interpretation, when combined with multiple dispatch as a language design feature, is absolutely insane. I think programming language enthusiasts might meditate on these points —- and get quite excited with the direction that the Julia compiler implementation is heading.

benrbray 5y ago
This sounds cool. Do you happen to have any links to share?
- mccoyb 5y ago
  If you are curious, I would stop by the Julia slack — specifically the #compiler-plugin channel. Otherwise, if you’re curious about how Julia’s type inference algorithm works via abstract interpretation, I would recommend the following blog posts: https://juliacomputing.com/blog/2016/04/inference-convergence/ https://juliacomputing.com/blog/2016/04/inference-convergenc... https://juliacomputing.com/blog/2017/05/inference-converage2/ https://juliacomputing.com/blog/2017/05/inference-converage2...

shakow 5y ago

> the expressiveness to augment the compiler to do interesting things with a piece of code. Julia has very interesting propositions on the subject, from language-level autodiff (https://fluxml.ai/Zygote.jl/latest/ https://fluxml.ai/Zygote.jl/latest/) to automated probabilistic programming (https://turing.ml/dev/ https://turing.ml/dev/) through DEs (https://diffeq.sciml.ai/stable/ https://diffeq.sciml.ai/stable/) and optimization (https://jump.dev/ https://jump.dev/). The whole ecosystem is in ebullition, and I'm very eager to see if it will be able to transform in the comping years into a solid foundation able to rival the layers of warts stacked on top of Python.

mccoyb 5y ago
Just a nit: Zygote is not technically a language level library. In fact, none of the above libraries really are language level — they are all just Julia libraries, some of which use macros. With the exception of metaprogramming with macros, none of these libraries customize inference/opt to do something funky. Zygote (for example) is based on a language level feature — generated functions which allow multistage programming in Julia — but beyond using this feature it does not configure or otherwise modify the normal compiler pipeline. With Julia, it is sometimes tough to tell — but Diffractor (for example) I would consider a language level library, as it modifies the traditional compiler pipeline to perform inference and optimization in a specific way.
- shakow 5y ago
  I guess it depends on what you call “language-level”; I mentioned these libraries because they all make use of macros and/or AST manipulation, which I would put somewhere in a grey area between language and compiler.

freemint 5y ago

Autodiff isn't even the most impressive application of non standard interpretation. The most impressive one is sparsity detection. If you have some arbitrary code that returns a matrix you can infer which elements of the matrix are guaranteed to be zero independent of input using non standard interpretation by taking all the branches of the program. This discovered sparsity can be exploited by a lot the generic algorithms in Julia that also are able to efficiently work on sparse matrices. There is also a way of combining this with AD to get automatic sparse hessian of optimization which is huge.