4,368 karma · joined December 2, 2012
Reach me at keno@juliacomputing.com
Whereas in Julia, we use Cthulhu to read code ;) - https://github.com/JuliaDebug/Cthulhu.jl.
Each talk will have its own live stream on YouTube and you should be able to immediately watch the raw recording of past talks as well.
For example, one could imagine applying common subexpression compression to a tracer tape, and would get essentially the same thing.
Other places to stores this information are the stack of a closure chain, but it's still fundamentally the same information.
Overall I think Julia is a pretty great language to implement AD (as evidenced I'd say by the 15 or so different AD packages that people have written for individual use cases before the latest push for a unified one), but it still is a very powerful language, so if you want your AD to handle the whole language (as we do), then you're gonna have to do a bit of work.
For example, all the ML frameworks generally combine a high level tracer with a straight line AD transform, which then sometimes gets presented as a fundamental aspect of AD (which it isn't, you're just using the tracer to get an IR you can handle). As a result, this field has a lot of confused terminology, but all the results have been known since the 70s.
The name of the game for all the latest generation tools is to cleanly separate out the semantic AD transform from the rest of the system and then just use an unmodified compiler thereafter. We do it by transforming Julia IR, the Swift folks do it on SIL, and the Scala folks have an implementation using shift/reset and LMS. If you do this, a bunch of traditional AD techniques become just special cases of general purpose compiler transforms (DCE, CSE, etc). See this talk I gave recently for some more details: https://juliacomputing.com/blog/2019/02/19/growing-a-compile...
As an aside, a pet peeve of mine is people calling these algorithms "tape free". High storage requirements, due to the need to remember (or alternatively, recompute) intermediate values are a fundamental property of reverse mode AD and you can't get rid of it. The best you can do is hide it (e.g. in compiler managed stack or closure environments), with all the same fundamental challenges. This is probably a terminology clash, with people wanting to use "tape" as a term for a much more narrow kind of data structure generated from a tracing AD system, but the requirement to have some data structure like it, no matter how hidden is fundamental to the algorithm.
struct Cons{T, S}; head::T; tail::S end
pairwiseReduction(f, a::Cons{T, Cons{S, Tail}}) where {T,S,Tail} = Cons(f(a.head, a.tail.head), a.tail.tail)
pairwiseReduction(f, a) = a
(https://github.com/thautwarm/MLStyle.jl if you want the syntax) but that's somewhat beside the point.I think the primary problem here is one of terminology. Take Stefan's quote from the post you're responding to:
> The primary difference between static and dynamic languages, in my view, is this: in static languages, expressions have types; in dynamic languages, values have types.
There is a clash in terminology here. People coming from a static languages background would use the term "tag" for what dynamic languages people call a type. There isn't really a super good word in the dynamic languages world for what static languages people call a type, and the word type is generally re-used, since the distinction isn't as important (generally there is an embedding of the tags into the type system, so using "type" for both can be sensible). I'm gonna adopt (my best interpretation of) the static languages terminology here for this comment.
Some languages have both types and tags. The biggest difference then between static and dynamic languages are which of the two is primarily dispositive (in the sense of determining the semantics of the language). In dynamic languages, the tags are, in static languages the types are. This choice has deep seated implication for the kind of programs that can be written and the behavior of the program.
In fact, you sometimes end up in situations where static languages have multiple tag systems (but generally only one type system) and dynamic languages have multiple type systems (but generally only one tag system). In julia, the tag system is primary, but we have a very rich type system that is embedded in the tag system by parametricity and is used for dispatch. This type system is constructed in such a way that the subtyping relationship is induced by tag system (for types T, S, (T <: S iff for all values v s.t. tagof(v) <: T, tagof(v) <: S)) [1]. You basically want to choose a decidable type system that satisfies this constraint, but is at the same time sufficiently expressive to be useful for what people want to do.
We also have another, larger type system that is used for inference judgements, but that is generally transparent to the user. It is in principle possible to type check over any of these type static system, but type checking is not part of the semantics of the language.
The problem with statements like "Julia's type system does not allow for X", is that it presumes that the type system having some feature is a pre-requisite for having the corresponding functionality. So while Julia's type system does happen have support for unions (and universally qualified unions), the significance of that is for dispatch, not for whether the language can have expressions that can take on values of different tags.
In any case, I can assure you that many people working on Julia are well familiar with Haskell's type system. Hopefully I was able to convince you that there is at least something interesting about the way Julia's type system works.
[1] I should credit the Northeastern PL group for the term "tag-based semantic subtyping" here to describe this notion (https://github.com/julbinb/ftfjp-2019/blob/master/paper/mini...).
Good to hear that getting this into LLVM is still in the cards - totally understood that there are organizational challenges, just want to keep pushing in the right direction :). My schedule doesn't allow me to be at EuroLLVM this year unfortunately, but I'm sure we'll get an opportunity to catch up before long. Now that MLIR is out it'd be fun to dig in in detail.
I'm also looking forward to digging into the polyhedral compilation stuff more. It's about time that somebody attempted a ground up re-think of that, so I'm looking forward to understanding it better. I've talked to Chris a number of times about the rest of the design, but we never got into the specifics of the polyhedral compilation.
That said, I think it's a bit unfortunate that this ended up in TF rather than LLVM. TF of course needs good compiler tech more than most projects at this point, which is why MLIR came from that direction, but MLIR is much more of a general compiler project. I worry that putting in TF will discourage the rest of the ML industry from adopting it as eagerly (everybody is already using LLVM, so that branding would make that much easier). Also, looking at the code, MLIR looks structurally a lot more like an LLVM-heritage C++ project than a TF one (hell, you build it by cloning llvm and putting MLIR in the projects/ directory). Perhaps moving it under the LLVM umbrella is still in the cards - I'll keep advocating for it at least ;).
- Being completely written from scratch in Julia
- Mixed debugging between Julia and C/C++ code
- Integration with https://github.com/mozilla/rr for time traveling debugging
- Debugging windows programs running on a linux host under wine (and in particular even as an rr replay).
- Zero overhead debugging by using mixed modes (DWARF based debugging generally, a much more accurate interpreter based one when possible).
- Very precise location tracking, on an expression basis, not just a line-by-line basis
- Multi-process debugging by riding along RPC calls, even across machine and even as separate rr recordings across machines
As you can tell from this feature list, that project was a bit over ambitious and in the end failed to be a particularly useful debugger for Julia. It was useable for a bunch of basic cases, but fairly brittle. Also, then 0.6 came around and all of Julia's internal APIs changed and porting over the entirety of Gallium would have been quite hard.After 0.6 was released, I decided this wasn't working out for a Julia debugging story and pulled out just the interpreter and UI parts from Gallium (that package was called ASTInterpreter2.jl). This worked ok, but was lacking a bunch of features that I never got around to implementing, because the lead up to 1.0 required a whole bunch of compiler work that nobody else was available to do. This work now is based on that work from 0.6, but actually making it work nicely and paying a whole lot of attention to it that I was never able to. I'm very happy that Tim, Kristoffer and Sebastian decided to take this on, because I feel like my workload has only increased over the past year ;).
I still very much want all the ambitious features from above, and we do still have the code (and much of it is actually in use, just not for debugging) and I'm fully expecting them to make a recurrence. However, this time around, we'll start with a stable, usable system and gradually make it faster and add features, rather than building an unstable system with all the features and trying to fix it. The former approach is much better for getting usable tools out (though sometimes the latter can lead to more interesting results in a research setting). The other thing to note is that Julia is much more stable now, so it's easier to keep things running without breaking every few months.
Yes, the right way to think about dual numbers (esp once you generalize them beyond just the single e^2=0), is to think of them as tangent vectors (sections of the tangent bundle). I've never really liked the "dual number" terminology here. That's why I deliberately chose to use the duality of forward and reverse mode AD, because that notion of duality agrees with the underlying linear algebra (or in general differential geometry). I do agree it's a mess of terminology.