BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage Interviews Leah Hanson on the Julia Language, Static Analysis

Leah Hanson on the Julia Language, Static Analysis

Bookmarks
   

1. We are here at Code Mesh 2015 in London, I am sitting here with Leah Hanson, so Leah, who are you?

I am a software engineer on the Dev Tools team at Stripe, previously I worked at Google on some low level networking stuff and before that I was at Hacker School playing with Julia.

   

2. You gave a talk here about Julia, and you are doing a lot with Julia, so why Julia?

What I like about it is that it is very easy to use, and despite being as easy to use as Python, you still have a lot of low level control, you can control making sure that your memory doesn’t copy you can care about the representation of numbers, so that you know that your Int64, the type you are using is just an Int64, it’s not like this amorphous number and who knows what representation is magically happening under the hood. So you can poke around at a much lower level than you are used to in high level languages, I wrote a web socket server in it and you can do all of the bit operations that you need because the headers of the packets have a bunch of flags and one bit for each one, and Julia is storing them in a byte when it parses them from out of the header you can use bit flags and it is surprisingly straight forward considering that it’s a language designed to do linear algebra and not a language designed for doing packet stuff.

   

3. So is it just designed to give you low level bit access? Is that a design purpose?

I think the purpose is that when you are doing Math sometimes you really care about the speed, especially with numbers, and so you want to be able to control whether you are using Int64 or Float32, or for some storage formats they even use Float16, and because there are engineers and mathematicians that care about these very specific number formats and they care about particular versions of performance where these things matter they assure you get all this low level control that lets you do other things that are only sort of in the purview of the language, it's general purpose but it sort of falls out of it that it happens to be good at this other stuff.

   

4. How would you characterize Julia, is it an object oriented language, functional language, or something else?

It is closest to imperative, it has functional features like immutable types, you can have first class functions and anonymous functions, but it’s not really functional, most Julia code is not written in a particularly functional style, it’s definitely not object oriented since you have types that are separate from functions, you don’t put your functions in the type, the functions are their own thing, so I think imperative is the closest. It reminds me a lot of C, sort of a mixture between C and Python, because you do a lot of for loops, data types look a lot like C struct, but you don’t have to mess with pointers if you don’t want to. There’s a type to represent a pointer so you can talk to C but otherwise you have your types, you don’t have any pointers.

   

5. Can you do pointer arithmetic?

I haven’t tried that, I know that you can get a type that represents a pointer so that you can talk about C structures and use the C APIs directly, I imagine that there must be a way to just do pointer arithmetic, it’s not something that you would do if you are just writing Julia code, but it’s something that you might do if you are talking to a C library.

Werner: It’s something to fall back to but it’s not a natural way of thinking.

Yes, you don’t use pointers directly except if you are talking to C libraries where you happen to need one.

   

7. Can you explain what it is basically?

It helps if you start with what single dispatch is, multiple is as opposed to single, and object oriented is single dispatch. If you are imagining implementing a Python class, you imagine the method, add method, add takes self and then X, and so self is going to be, if we have y.foo(x), y is that self, and so it is the first argument of the function. It is the only one you care about, because the implementation of add that you are calling is based only on the first argument the type of the first argument, and that’s a single argument that we care about, we don’t care about any of the rest of the arguments for dispatch, whereas in multiple dispatch we care about all of them equally. If you are dispatching for a function in Julia functions are sort of their own things, so functions have methods directly, so if many methods of the add function and so you say I am going to call add, here are my arguments, here are the types of each argument, and then you go look at all the methods, and the only possibilities to actually call have to have the same number of arguments, and of those only the ones that say if you are calling add with two ints so the possibilities that would match would be add with two ints or you can have one of the arguments be an abstract type that’s a super type. So for example add of two numbers could work because number is a super type of Int64, or add of integers because integers are also a super type of Int64, but add of two Floats64 wouldn’t match because it’s a different concrete type it’s not one of the super types of Int64 so you pick the one that matches the most closely. So the ideal is to exact type match two Int64 and then the number of steps you have to go up so an integer is a closest match to a number, and you look at how far off each one of them is and you find the best match weighting everything equally.

   

8. And so you mentioned int64 and int, that’s kind of a type hierarchy?

Yes, the type hierarchy is basically a tree, I say basically because at the top there is a loop, everything has to have a super type so 'any' which is on top of the root of the tree, is it’s own super type, but other than that it’s a tree. Numbers are sub type of 'any', it doesn’t really matter at the top but I think numbers are subtype of 'any', and then integer is a subtype of number, signed is a subtype of integer, and you have your signed ints like Int64 and you have your unsigned integers like UInt64. And so you have this sort of tree of number types, it also branches more than I’m saying the floating point number is off at the same level as integers, and different sizes of ints they go all the way from Int8 to Int128, and there’s also a different bunch of different kinds of floats and also BigInts are another kind of integer. When you get down to the bottom it's just a bunch of implementation details of which one, but if you want to abstract and all you care about is that there is some kind of number, then you can write your functions in terms of that, and you only really use types basically in dispatch, your code could look very much like Python, except you usually use types when you want to have dispatch over your functions, just to control I want just one method of this I want to have a method that handles these different types. It’s neat because you don’t have to talk about types that much if you don’t want to, but you give the compiler more information when you add type annotations and you do it basically to get the behavior out of your program. You can get very much like Python if you go “I want the first argument to be an int” or like my new class, and then you’ll basically have Python where you are really basically dispatching on the first one, once you determined that you are going to use that implementation because you are using your type as the first argument, then everything is going to end up there, until you add new methods that do something else.

   

9. Is multiple dispatch the fundamental way to call functions?

Yes, every time you call a function it’s going to be multiple dispatch, I guess the only exception is anonymous functions, look more like a traditional view of functions where they don’t have methods, it’s just like named functions are generic because the name is what you instantiate all the methods on to, whereas anonymous functions look more like anonymous functions in any other language.

Werner: There is only one body.

Yes.

   

10. Is there some optimization with multiple dispatch that if you know the types at compile time it just doesn’t need to do any dispatch, it just compiles a call to the right method?

It specializes when you compile so you compile a specific method implementation and you compile for a specific concrete type, you wouldn’t compile for two numbers, you compile for Int64s, since we do just in time compilation you have actual values which definitely have concrete types. And so you compile for a specific set of concrete types and it means that when you are in the body and you have a method call you know the types because you know the argument types, and you can do inlining, or you can do de-virtualization which is where you compile the other method, and then you can jump straight into that function instead of having to do the dispatch. You can do optimization like that and also you can do – I think this is a specific application of inlining, there’s a function that let’s you look at the native assembly of any compiled function, and if you do a little bit of math which is integers, you can look at the assembly code and you can see all of it, if you are familiar with assembly code you see the expected operations for just doing Math on integers and registers, and you need to be able to write a simple function and then get simple assembly code, when you ask what it’s even doing. It’s an easier way to think about what assembly code is doing since you can look at the Julia code that’s more readable and then see what the assembly code comes out, and if you look up those instructions they are what you would expect.

Werner: You can learn basically what your code gets turned into.

Yes. It’s funny because I wrote a blog post one summer about these four functions because I was at MIT for the summer, where they develop Julia, and they were casually debugging the compiler I forgot what it was for, and I said “Wow, you have these four functions, these are so cool, you can see one that is parsed with a little bit of desugaring, you can see one that is type inferred, and there is the LLVMIR so before it goes into LLVM and then the native assembly that comes out of LLVM, and you can just call these functions on anything that you can compile you can call that on that unit”, and I said “This is so cool, I have never seen another language where you can just so easily run a function and get this output”. And they said “It’s obvious of course you need this to debug” And so I wrote a blog article but before I published it I gave them a couple of weeks, they wanted to rename the functions first, to have readable names, because the original names were inconsistent, they were just four names for internal debugging things, and now they are all named code_something, one of the is code_LLVM is the LLVMIR and code _native is the native assembly. But it was funny because this is stuff that’s really cool and magical and I went through and documented it and that is actually one of my most popular blog posts, when I am with other Julia people they go “Yes, I use your introspection blog post all the time, because that’s the one that describes introspecting on the abstract syntax tree stuff”.

   

11. Since you mentioned this, I think you did some work on static analysis? And you are basically using these methods to get the AST and other things?

Yes, basically just the type inferred AST. The other four aren't quite as useful, the LLVMIR and the assembly language are just text they are human readable but it’s hard to do analysis on them. And the first one isn't super useful for what I was doing, the parsed AST isn’t more useful than the type inferred one, and so it’s not strictly type checking, because the Julia type system is not designed to be checkable, for example you have type parameters, and your type parameters can be integers, symbols, so you can have these families of types that are not formally checkable, and in general I think there’s cases, it's not designed for type checking but it is designed to be type inferable. It's like simulating the code, like you are trying to see what types could appear on any given line, variables, you just care about what values it takes on and you sum them up.

I learnt how that worked so that wasn’t really relevant to checking them. I was keeping up with the mailing list at that point I looked for things that people stumbled on that would be checkable automatically. One thing is people have this performance problem where they set their variables to integer constants, like zero, which is totally natural, you just write X=0, but the problem is that’s an integer and you if all the math in your loop is actually using floating point and doing division you really want 0.0 otherwise it basically makes lots of little allocations because it’s sort of an unfortunate case, once you get type instability it makes everything on the heap and then every time you do because all the numeric stuff is immutable values, when you are on the heap you have to keep creating new ones so that they can definitely be immutable to everyone. In my talk I give a better example, once you are in that case it’s really confusing because you think “This definitely looks correct I don’t understand why this is so slow” and you have to make sure it's type stable and it gets really easy when people on the mailing list say “Oh yes you just need to change a couple of characters and it’s fine”. But it’s one of those things they say “My Julia code is slower than my Python code” when in fact it’s a hundred times faster, which is the improvement they are expecting, and it’s very frustrating when you go through the mailing list to find these things out so I wrote some checks where you can run them yourselves on any function you can compile because that is what works with these built in functions for looking at the type inferred AST, there is a check for if you created a variable and only you wrote to it but didn’t read from it, that can be the cause of a bug, if you just didn’t notice you wrote to this variable and you meant to use it in your equation later but you wrote the wrong one down so it checks for that because it’s simple to do and it occasionally causes problems for people.

And the other one I did this one was kind of fun it was you are checking to make sure that there is some method that can match the call you are making, so it looks at all the calls in the function you wrote and it looks at those functions and it makes sure it’s a method that can match and of course it may match a different one if you add more methods later, but it looks for things that are definitely impossible. One of those things was I found a couple of bugs in the base library using that, which was pretty neat because you expect the base library to be fine because people have used most of it, and one of them was they were doing some meta-programming so they had a bunch of linear algebra functions, so they have all these matrix types like triangular matrices so you can do some special stuff because you know some mathematical about the matrix shape, but they have a bunch of addition and subtraction methods that make one of the matrices less sparse and then do the addition that way, but some of the pairs don’t have addition and subtraction methods because nobody had happened to call them, nobody ran into that, I guess, or they ran into it and then worked around it, so I got to report a bug and on the GitHub request, one of the guys who does linear algebra, one of the core contributors was “Oh, thank you for going through all the linear algebra code, this is super impressive”, and I was “I did a bunch of static analysis, I don’t understand linear algebra code”. So that was really cool because you can understand what the bug is even if you don’t understand the math that I going on around it because you just look at the call and you are “Well, I can come up with a counter-example pretty easily because I just need to construct the types involved and then call the function and it’s going to fail”, so you can probably extend the static analysis to write the GitHub issue for you and explain it because all it needs to create is an instance of the type so you can actually call it and show you the error.

   

12. Interesting. So how can we get into the whole static analysis, if I want to add my own static analysis work, so can I start off with that?

In Julia or a language you use?

Werner: In Julia.

I think the best place to start off is if you want to do type-based stuff, it’s useful to understand the type inferred AST which doesn’t have the most friendly format, I think my blog post is still one of the better places to look up documentation for that, but once you understand that it is more straight forward, mostly a lot of trial and error of figuring out what the AST looks like for these sorts of errors you are looking for and once you do one or two of them it’s a lot easier to do the rest of them because you get the hang of what the AST looks like. The other thing is I just wrote a chapter for 500 Lines about doing static analysis in Julia, that’s basically a documented version of my work that walks you through most of the checks and how you write them, and it’s one of the early release chapters for 500 Lines, it’s called “500 Lines or Less”, it’s by the same people that did “Architecture of Open Source” series [Editor's note: the link to the chapter is http://aosabook.org/en/500L/static-analysis.html ].

   

13. I actually saw that, that’s interesting. So the AST, does that actually have things like source location, where it came from the source?

It has some, there are line number nodes, so it will tell you what the line numbers are. Those are only really useful for displaying because you can’t programmatically use them, you get the expression and it happens to have these nodes in it, but they are really useful for displaying error messages like “It happened on this line”.

Werner: I find it’s always a problem with existing ASTs because if you want to do refactoring or take some code and automatically refactor it, you have to know where each thing came from.

I think they did a little more than that, they wanted, we wanted to attach comments to the ASTs because they get removed in the first desugaring right now, but if you want to use comments as documentation, one form of that would be to have them attached to the methods you could say “Ok, these comments go with this method so when I generate my documentation I know that this comment is documentation for this specific method”; I don’t know if that actually got implemented, I know it was a thing that I wanted to implement, but the parser is a little hard to work with since it’s in Lisp, I don’t really use Lisp so that’s a barrier of entry for me.

   

14. What is Julia implemented in?

So the parser is in FemtoLisp which is actually a Scheme, but there’s that and there’s some C that’s mostly glue code, the C code implements some of the most basic types so you can start running Julia and then there is some C++ to talk to the LLVM and then once you have all of that you can start writing Julia code and then the Julia code starts adding features to run more Julia code; like the type inference is all in Julia, so it’s like you run the first couple of files and then you get to the type inference and you sort of load some of them again so that you can type-infer them, you can run Julia just slowly if you don’t have type inference.

   

15. I think you also did some other work with Julia; what was that other work?

When I was at Hacker School one of the first things I wrote in Julia was a web socket server, so at Hacker School which is now The Recurse Center, I’m not still used to the new name, you spend three months there and you work on whatever you want and it’s common that half-way or three-quarters of the way through the batch you go “I’ve done too many small projects, I want to work on a big group project with a few other people”, so this happened during our batch and this was just after Stefan had presented, he was one of the residents, he is one of the co-creators of Julia and one of the residents of our batch, so he spoke I think about floating-point numbers, but all of his examples were Julia code and people got interested in using Julia because some of the stuff was pretty neat, it was previous float and next float function, so you give it a floating-point number and I will give you next representable float; so for a lot of people it was surprising that floating-point numbers aren’t continuous, that you have to go up by this much before you can represent the value again, at least exactly.

So that was in our minds as we were talking about what to write. Their first proposal was we want to write a web browser so those who were a little more experienced “That’s a little bit complicated, a web server is much simpler and we should try that instead” and so we decided that since Julia didn’t have a web stack yet, we’d implement a web stack for Julia, so one of the things that sold me on Julia, it was some of the first Julia I’d written, but it was also neat they had just added TCP sockets and the only documentation available was one thread on the mailing list and the only example was this tiniest possible example of echo server that was all tied up with callbacks, so it was this thing wrapped around a callback function and we only understood the syntax, but within ten minutes since I used sockets before we unraveled it, the normal reads and writes on sockets, very much what you would expect if you’ve done sockets in C. So that was cool that you could so easily go from the first glimpse of Julia to unraveling this sort of not worry about documents and features, it was very natural working with the type system. That’s when I was doing the bit flags and web sockets server and that was a lot of fun. It was also fun to watch the people who were doing, we decided to use Joyent's HTTP parser, that’s what Node.js uses, but it was just a C program, we had to make a Julia wrapper to use it in the rest of the web stack; and the people doing that hadn’t really written C before, which I didn’t realize it first, but they called me and asked me some pointers on syntax and I am not the best at C, but I'd used it before and I could tell them what some of the syntax meant, and by the time we came back together the next day they had a complete wrapper and they had two small changes and then it worked. So that was really impressive that people that hadn’t done C before and had only just barely started doing Julia could wrap a whole C library in Julia and have it be just about working within a day and I found that really impressive, it just speaks to how easy it is to wrap C libraries in Julia and I feel like that is some of the best testimonials of it being easy to use, wrapping libraries that are written in C or Fortran in Julia.

Werner: You already mentioned your articles on “500 Lines or Less”. And you are also writing a book on Julia.

I’m writing “Learning Julia” for O’Reilly. I have a co-author, Spencer, and so we are hoping to have it out next summer as long as I don’t fall behind schedule more.

   

16. What is the focus going to be, is it just starting from scratch?

Yes. It doesn’t expect you to already know any Julia, it sort of expects you to have used some other programming language and that is loosely defined since a lot of Julia users are coming from MATLAB or Python and so the idea is that it’s mostly example-based. I finished, I have two chapters out and I have done some book signings at other conferences, but the first chapter is general examples of Julia so you can get a sense of what the features are, so hopefully by the end of the first chapter you are sold on there are some fancy features here, I might want to learn, and the second chapter is all about IO, so I was thinking about what do you need to actually start using Julia so you can get away from the book and do some stuff at work and then come back to the book once you’ve decided it’s for you; so you start out doing your file IO, the first example is just a silly little hangman game and then one of the later examples is in that chapter is making your own version control systems because you get to manipulate the files on the file system and practice with these functions like deleting things and copying things around, and that was pretty fun because I hadn’t used those functions before but basically they do what you’d expect, one of the things I enjoy about writing the book is I get to explore these parts of Julia that I haven’t actually used, but that I think are important for some applications and then it turns out to be very natural and what you’d expect it to be like; not that I have specific expectations for Julia, but I think the reason I happen to like Julia is it happens to match my mental model of how I expect things to work, it’s dynamically typed, but you can actually talk about types which I find more natural; my first programming language was Java so it took me two tries to start using Python because I was so used to thinking of things as having types and I just couldn’t quite get my head around Python, I actually had to learn Perl first where you could at least have scalar values and arrays and hashes, and each of them has a distinct symbol at least, sort of like having a type, and it wasn’t until I got my head around that that I actually started using Python, I still find it kind of funny, I couldn’t use Python the first time I tried to use it, it was just too confusing.

Werner: I think you mentioned next summer [2016], sometime, the book; so it’s “Learning Julia”. So I think we are all going to watch out for that, all the audience, and thank you, Leah.

Yes. Thank you.

Feb 04, 2016

BT