27 ms·
Julia's multiple dispatch explained with Pokemons
- macintux 5y ago(post title has been edited since I commented, nothing to see here)
- deleted 5y ago[deleted]
- nixpulvis 5y agoThank you, I thought I was going crazy over here! What the fuck does it mean!?
- creddit 5y agoPokemon* This used to make me very frustrated as a child.
- christophilus 5y agogreat*
- fouc 5y ago> "Pokémon" is identical in both the singular and plural, as is each individual species name; it is grammatically correct to say "one Pokémon" and "many Pokémon", as well as "one Pikachu" and "many Pikachu". Interesting, did not know this
- thaumasiotes 5y agoIt is a general phenomenon of Japanese, not something specific to Pokemon.
- coolestguy 5y agothe correct term is "pokemans"
- coldtea 5y agoYes, it's Pokemi /s
- deleted 5y ago[deleted]
- ampdepolymerase 5y agoPokémon, you left out the accent aigu.
- tqi 5y agoOne of the great 30 Rock moments: https://getyarn.io/yarn-clip/674493b9-cb97-454b-84e5-68afe0cc28b5 https://getyarn.io/yarn-clip/674493b9-cb97-454b-84e5-68afe0c...
- deleted 5y ago[deleted]
- fastball 5y ago> Pokémon are a great way to explain Julia's Multiple Dispatch
- zwkrt 5y agoThis post shows MD but it misses the forest for the trees. To riff on the blog post linked below, “what if you have an Onyx holding a hard stone executing Earthquake in a Sandstorm against a Flygon with the ability Hover?” The answer is that rules should be encoded in data structures and not in the type system. The type system is for structuring how your program runs not its logical correctness. If you have a coworker who, upon hearing that you have a new business requirement, says “oh goodie I’ll reconfigure our whole type system!” please report them to the relevant local authorities. If you aren’t writing code that handles types as 1st class objects like a parser, please reconsider using this pattern. If you are writing a parser, this isn’t even the fancy way to do it anymore, but at least you’re holding the book upside right. The funny thing is that the Pokémon valences are already in a table at the start of the blog post; an ideal location to store such data! https://ericlippert.com/2015/04/27/wizards-and-warriors-part-one/ https://ericlippert.com/2015/04/27/wizards-and-warriors-part... EDIT: this is not shade on the OP, I just don’t want junior (or senior!) engineers reading this and implementing their business logic in MD because I don’t want to debug it or extend it!
- im_down_w_otp 5y ago>"The type system is for structuring how your program runs not its logical correctness." Type-level programming can be a very powerful and useful way to coerce correctness in some scenarios, so I'm really confused by this statement.
- zwkrt 5y agoYeah if you’re writing a standard library or a parser or maybe a database query optimizer, but if you aren’t writing code about code, then it’s probably not the way to go.
- zem 5y agotake a look at https://blog.moertel.com/posts/2006-10-18-a-type-based-solution-to-the-strings-problem.html https://blog.moertel.com/posts/2006-10-18-a-type-based-solut... for a good counterexample
- malkia 5y agoIs this like Common Lisp's dispatch as defined by the default CLOS implementation?
- ThomasMoll 5y agoYes! In fact I think Julia borrows a lot of concepts from CL and the like for their type system implementation.
- snicker7 5y agoJulia is basically a trojan horse for Lisp. Syntactically, it looks kind-of like Matlab. But semantically it is very much in the Lisp family. Since 1959, Lisp remains the best idea in computer programming. And Julia is bringing it to the masses.
- pjmlp 5y agoYeah, although Java did it first. "We were after the C++ programmers. We managed to drag a lot of them about halfway to Lisp." - Guy Steele I assume Guy Steele knows his stuff when talking about Lisp like languages.
- lispm 5y agoJava mostly only got typical runtime ideas (managed memory, virtual machine, code loading, calling conventions, runtime safety) of the JVM from Lisp (often via Smalltalk, etc.), but not ideas like executable memory heaps, code as data, etc. Higher language feature from Lisp (CLOS, macros, conditions, closures, interactive development, ...) were not brought to mainstream Java. Closures, some interactivity, ... eventually were added many years later. From a Lisp user perspective Java was more than 'halfway' away, and probably still is.
- pjmlp 5y agoGuy Steele did not say 100%, after all. So we could argue bullet points about how someone highly relevant in Lisp and Scheme community was wrong on his assertion, if you like.
- SPBS 5y ago> I’ll admit, multiple dispatch is a super abstract concept, one that you really only appreciate when you need it. After reading this post and this stackexchange link[0], I'm not sure it is that complicated. The behaviour in the post can be explained as Julia picking the most specific function that fits based on the runtime type (i.e. uncovering the underlying concrete type at runtime and checking for an implementation). In fact the stackexchange answer mentions that dynamic languages don't differentiate between overloading and multiple dispatch at all, since everything is resolved at runtime. So, overloading and multiple dispatch seem more like that same concept but are one is eagerly resolved while the other is lazily resolved. [0] https://softwareengineering.stackexchange.com/a/125088 https://softwareengineering.stackexchange.com/a/125088
- ThomasMoll 5y agoDepending on the language target and method of execution dynamic resolution of runtime types can be quite hard. IIRC Java's JVM is super optimized for static codepaths, whereas Julia uses a JIT system that is "slow" on first run but speeds up considerably after all methods in a hot code path are resolved.
- brabel 5y agoYep, it's just late binding. If you want that in the JVM, you can use Groovy, which does just that.
- brabel 5y agoExample: class Fire{} class Water {} class Grass {} class Ice {} def eff(Fire f, Grass g) { 'burn' } def eff(Fire f, Ice ice) { 'melt' } def eff(Water w, Grass g) { 'grow' } def eff(Water w, Ice ice) { 'freeze' } def eff(a, b) { 'undefined' } println eff(new Fire(), new Grass()) println eff(new Fire(), new Ice()) println eff(new Water(), new Grass()) println eff(new Water(), new Ice()) println eff(new Ice(), new Water()) Prints: burn melt grow freeze undefined
- pjmlp 5y ago
- anonytrary 5y agoSuper nitpicky, but @dang can we please update the title? "Pokemon" is both singular and plural, nobody ever says "Pokemons". It's just the Pokemon nerd in me... the title feels so wrong.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- ThomasMoll 5y agoI'll admit, I'm a bit disappointed that my original title "Julia used Multiple Dispatch! It's Super Effective!" didn't make the HN frontpage.
- deleted 5y ago[deleted]
- dudeinjapan 5y agoBug: eff(atk::Electric, def::Grass) = NO_EFFECT Grass should be Ground
- lukelunchbox 5y ago"Pokemons"? what are you, 60?
- maximilianroos 5y agoThis is an excellent intro to Pokemon, explained using Julia's multiple dispatch mechanics.
- joiguru 5y agoOne point I have read repeatedly is that Julia is aimed at High Performance Computing (HPC). Another argument I have read repeatedly is how object oriented programming (with its single dispatch) is bad for HPC because of pointer indirections leading to cache misses. This leads me to conclude Julia will be much worse (than well written C/C++) due to its multiple dispatch.
- celrod 5y agoIn practice, Julia's multiple dispatch is almost always devirtualized. That is, dispatch is resolved at compile time. Generic code relies on specialization instead of dynamic dispatches to be generic with respect to input types. That is, for each new input type, a new method gets compiled (allowing the dispatch to be resolved statically).
- joiguru 5y agoDo you have a citation for this? My google searches have led me to believe this to not be true; see [1] Here is the relevant quote from [1]: "In the context of julia though, compile time type simply do not exist ...." [1]: https://discourse.julialang.org/t/claim-false-julia-isnt-multiple-dispatch-but-overloading/42370/41 https://discourse.julialang.org/t/claim-false-julia-isnt-mul...
- adgjlsfhk1 5y agoJulia semantically doesn't have compile time type, but is free to (and almost always does) figure out the compile time type and use that information aggressively as long as doing so doesn't change behavior.
- celrod 5y agoBy "compile time", I meant the first time you call the function with a given type signature. Also, that comment is saying "compile time type" does not exist. I don't know C++, so I cannot comment on it, but from the sound of Yu Yichao's comment, C++ has separate concepts for runtime vs compile time types. Julia does not (as already said by adgjlsfhk1).
- ALittleLight 5y agoI would try to implement PokeTypes by using an enum to define each PokeType. I'd have a dictionary that stored attacker, defender pairs as a key and the value would be the effectiveness of the attack. The "eff" function (which I'd call something like attack_effectiveness) would just be a get from the dictionary that defaulted to NORMAL_DAMAGE if the key wasn't contained in the dictionary. Later, I'd probably build up the dictionary from something that was easier to read and update to make maintaining it easier. My point here is that I don't really see the point of using types to implement this functionality. Is my approach weak in some way that is solved by this?
- adgjlsfhk1 5y agoThis solution works until you have 1 type that has a different fallback than everything else.
- ALittleLight 5y agoI think it would still work. You would just need to define every attacker-defender pair for that type. If types with different fallbacks were common then you'd just define a dictionary of attack effectiveness fallbacks and the attack_effectiveness function would get from the attacker-defender dictionary and default to fallback for the attacker type.
- ThomasMoll 5y agoI think the advantage here is that instead of centralizing the relationships between all types in one place, these relationships can be defined anywhere, including external packages. This makes composition of additional types extremely easy, even when multiple people are working on the project.
- gradschoolfail 5y agoso, it seems to me, the relevant question is: Is it the Julia JIT that makes the type inference fast, or is it the type inference that makes the JIT fast? (see other comments eg by adgflsfhk1 that ask about whether the types are resolved at runtime or compile time or whether the julia compiler is neither AOT nor JIT but JAOT) Can anyone answer LI5?
- adgjlsfhk1 5y agoIt's a bit of both. Julia's JIT makes code without annotated types fast since it can figure out the types just before runtime and de-virtualize on that basis. The reason julia is able to make such aggressive compile time optimizations is because it only compiles the code that you actually use. In many ways, julia (performance-wise) is similar to heavily templated C++, but the key difference is that in C++ templated code, you have to compile for every combination of possible types, which can easily be thousands of times more methods that are actually needed.
- gpderetta 5y agoWhat? No of course not, you have to compile templates for only for types that are actually used. In fact it would be impossible to compile them for every (combination of) possible types.
- mbauman 5y agoWhen folks talk about the performance of Julia's JIT, they're generally talking about the compile-time overhead (and not the runtime speed). Type inference is one part of the compile-time overhead that enables improved runtime speed... but I think you're actually curious about runtime speed. Julia aggressively compiles multiple specialized versions of almost all the methods it encounters — one specialization for each unique combination of the argument types you pass. Even if you only define a single method `f(x,y) = 3x+2y`, Julia will compile a specialized floating point implementation when you call `f(2.5, 3.5)`, an integer implementation when you call `f(1, 2)`, and so on. It's this very aggressive compilation of everything many times over that makes Julia infamously slow to start and fast to run. Inside each of these specializations, Julia concretely knows the type of `x` and `y`. And so it can — while compiling it — look up exactly which multiplication method it should use to compute `3x` and `2y`, inline them, infer the types of the results, lookup which `+` method to call, and inline it. Even if you end up calling bigger functions that don't inline, Julia can hard-code the pointer to the exact specialization of every function you call because it's in a context where it knows the exact types of everything. So it's a bit of a chicken-and-egg question. Julia's JIT (typically) compiles specializations of methods with precisely known argument types. This makes does make inference easier: every function call is a fresh start! If at any point inference loses the trail, it's ok, Julia just compiles it pessimistically to handle any type and can lookup the exact method/specialization that's needed for each function call on-demand (potentially compiling it and getting a new fresh start if needed), and then you're back on the happy well-inferred and super-specialized path.
- gradschoolfail 5y agoIs julia faster than python because it is a lisp and thus easy to write an optimizing compiler for it? Yeah, so is multiple dispatch something that is intertwined with SSA?
- adgjlsfhk1 5y agoJulia has a bunch of semantic differences that are also responsible. For a quick list: 1. you can't add fields to structs (ie all types have __slots__) This is really important since it means you can store structs inline which avoids a ton of pointer chasing 2. eval always happens in the global scope (and world age means that eval doesn't have effect until you hit the global scope). This means that you can inline code which is one of the most important optimizations. There are a few of other careful compromises like this where Julia gives up the small amount of dynamism that makes optimization impossible, while keeping enough dynamic behavior to be highly usable without doing anything that makes optimization impossible.
- nxpnsv 5y agoI guess I am old, but I feel I understand Julia better than I understand Pokemon...
- vanderZwan 5y agoI mean, the only part you need to understand for this blog post is "rock-paper-scissors, but extended to N types and with more than just win/lose as the outcome from pairing them up"
- nxpnsv 5y agoYes, it's not a bad post. Nor are Pokemons, I'm sure. Just an observation: I felt I learned more about Pokemon than Julia reading the post, thus concluding probably I was not the target audience.
- exdsq 5y agoPerhaps a dumb question but why couldn't I just use pattern matching for this? Your essentially writing the pattern matching rules out anyway. Type -> Type -> Effectiveness isEffective a b | fire water = supereffective | water fire = noteffective etc...
- nightfly 5y agoIn Common Lisp, multiple dispatch lets you provide a new specialization of a function at a different time/place. I imagine it's similar in Julia.
- petrigun 5y agoOP said that we would have to use reflection to make this work in Java, but I think we can also make use of Generic classes: class Pokemon<T extends PokeType> { public T type; public Pokemon(T givenType) { type = givenType; } } and in main(): Normal n1 = new Normal(); Pokemon<Normal> pokemon1 = new Pokemon<>(n1);
- leipie 5y agoIf i onderstaand thuis correctly, there is a known pattern for resolving this in languages like Java. Is called double dispatch it only takes a bit more boilerplate than using this Haskell like pattern matching: https://en.m.wikipedia.org/wiki/Double_dispatch https://en.m.wikipedia.org/wiki/Double_dispatch
- okareaman 5y agoApparently, function overloading in a language like C# is done at compile time, while in Julia is done at runtime based on the type of argument given.
- RocketSyntax 5y agoseems super abstract and hard to maintain.
- e12e 5y agoAlways nice to see people explaning/exploring technical concepts - but in this case I think the official documentation is both clear and useful: https://docs.julialang.org/en/v1/manual/methods/ https://docs.julialang.org/en/v1/manual/methods/