July 20, 2014

A Lisper's first impression of Julia

I have recently looked at Julia, a new programming language developed at MIT that promises to be a dynamic programming language that is suitable for scientific computing with a high-performance implementation. It is an interesting project that heavily borrows from Common Lisp, Dylan, and Scheme, and you can rightfully argue that Julia itself is actually a Lisp dialect. While I wasn’t very impressed with some other recent Lisp dialects (Arc, Clojure), Julia puts a couple of very interesting features on the table. Below is a discussion of the more salient aspects of Julia, as seen from a Common Lispers perspective. It is based on the documentation of the prerelease version 0.3 of Julia.

Julia is closest to Dylan in many regards. It uses a somewhat mainstream syntax rather than s-expressions. Unlike Dylan, you can nevertheless write ‘full’ macros, since macro definitions are implemented in Julia, not some template language, and backquote/quasiquote is integrated with the Julia syntax. Julia is a Lisp-1 (like Scheme or Dylan) rather than a Lisp-2 (like Common Lisp or ISLISP), which makes it necessary to add macro hygiene features. Fortunately, this does not mean you have to deal with the rather painful syntax-case construct of some Scheme dialects, but you can still use far simpler backquote/quasiquote constructions, just with macro hygiene taken care of by default. Julia also allows you to selectively break hygiene. Although I usually strongly prefer the simplicity of Common Lisp’s non-hygienic macro system, the fact that Julia is a Lisp-1 turns macro hygiene into a real problem, so I guess this is a reasonable design.

Julia provides object-oriented programming from the ground up, similar to Dylan. It centers on generic functions rather than classes, where methods are defined outside classes and allow for multiple dispatch, just like in Dylan and Common Lisp. Like Dylan, and unlike Common Lisp, it does not distinguish between functions and generic functions: All functions can have methods, you do not have to make up your mind whether you want methods or plain functions. Unlike in Common Lisp, there are no method combinations, no before/after/around methods, and call-next-method is not directly supported, but has to be done manually. This is probably to simplify method dispatch, maybe to have some performance advantages, though I find it hard to imagine that adding method combinations would make things substantially worse.

You still need a class hierarchy to drive method dispatch. Unlike in Common Lisp, there is no multiple inheritance, only single inheritance. In fact, there is actually no real inheritance, because in Julia, only leaf classes of the class hierarchy are allowed to define slots/fields. All superclasses are required to be “abstract,” without any slot definitions. Also, Julia classes cannot be redefined at runtime, so in fact Julia classes are much closer to Common Lisp’s structured types rather than classes.

Julia’s execution model is based on dynamic compilation. As a user, you don’t have to compile your code at all, source code is just compiled on the fly (similar as in Clozure Common Lisp). Julia inlines functions on the fly, including generic functions, and can de-optimize when function definitions change at runtime. This is more flexible than in Common Lisp, where inlined functions can get out of sync with their potentially changed definitions. Also, while the Common Lisp specification does not say anything with regard to being able to inline generic functions or not, there are aspects in the CLOS MOP specification that prevent generic functions from being inlined, at least for user-defined extensions of generic functions. Julia definitely seems more “modern” here.

In Julia, there is no distinction between variable binding and variable assignment. If you assign to a variable that has not been used before in the same lexical environment, it is silently introduced. In Common Lisp/Scheme/Dylan, there is a distinction between ‘let forms that introduce variable bindings, and assignments (setq/setf/set!) that perform assignments. I’m highly skeptical of Julia’s design here, because this potentially leads to bugs that are hard to find: A simple typo in your source code just may go unnoticed.

In Julia, all variables are lexically scoped (except for some seemingly quirky scoping semantics for global variables, see below). There are no special / dynamically scoped variables in Julia, which is a major omission in my book. Some academics don’t like special scoping, but their presence in Common Lisp is incredibly useful in practice, especially but not only for multi-threading!

Julia’s default representation for integers is either 32-bit or 64-bit integers, depending on the target architecture, which silently wrap around. Julia also supports “BigInts” that can be arbitrarily large, but you have to ask for them explicitly. In Common Lisp, integers are by default arbitrarily large, which I think is an advantage. Due to type tagging in Common Lisp implementations, even “big” integers are typically allocated as immediate values rather than on the heap when they fall into the “fixnum” range. I didn’t find anything in the Julia documentation that discusses this aspect of “BigInt.”

In Julia, all mathematical operations are generic functions and can be extended by user-defined methods. This is a strong advantage for Julia. In Common Lisp, mathematical operations are “plain” functions which cannot be extended. Due to some aspects in the design of Common Lisp’s generic functions, it’s hard to inline (or open-code) them, which is why for performance reasons, it’s better to express mathematical (and other such performance-critical functions) as “plain” functions. Apart from that, the support for number types seems to be on par between Julia and Common Lisp (complex types, rational numbers, floating point numbers, etc.)

In Julia, strings are unicode strings by default. My knowledge about unicode support in Common Lisp implementations is limited, so I cannot really make any comparisons here. One interesting aspect in Julia’s string support is that there can be user-defined macros to parse them and construct other syntactic entities out of them. This feels somewhat similar to read macros in Common Lisp, although with a slightly different scope.

Julia’s support for functions is similar to Common Lisp: They can be first class and anonymous (lambda expressions). There are varargs (&rest), optional and keyword arguments. In Common Lisp, optional and keyword arguments cannot be dispatched on in methods. In Julia, optional arguments can be dispatched on, but not keywords. (This is a pity, dispatch on keyword arguments would be very interesting, and is something I wanted to add as part of Closer to MOP for a long time!)

Julia’s support for control flow is much more limited than in Common Lisp. There are equivalents for progn, cond/if, for and while loops. Unlike Common Lisp, there is no support for a full loop facility, or even for a simple goto construct. Common Lisp clearly wins here. Julia’s support for exception handling is also limited: No handler-bind, no restarts, unlike in Common Lisp, which are also really useful features.

Julia’s type system has some interesting differences to Common Lisp: There is a distinction between mutable and immutable classes. Immutable classes disallow any side effects on their fields. This seems to be primarily directed at enabling stack allocation as an optimization. In Common Lisp, you would use dynamic extent declarations when allocating structs (or other data types) to achieve similar performance improvements. I’m not sure why it would matter that the fields need to be read-only for such an optimization, but if this covers most cases, maybe this is good enough.

Julia allows for returning and receiving multiple values from function calls, similar to Common Lisp. This is a feature I like a lot in Common Lisp, so I’m happy it’s also in Julia. In Julia, this is achieved by an explicit tuple type representation which doesn’t exist in this form in Common Lisp. In Lisp, you could also return/receive lists instead of multiple values, which would correspond to this kind of tuple type, but lists add an additional performance overhead, which multiple values and, presumably, tuples in Julia don’t have.

Julia supports parametric types. I don’t see at the moment why this is relevant. You could achieve similar functionality also with some macrology. Maybe I’m missing something here.

There is a whole section on constructors (make-instance / make-struct) in the Julia manual. This makes me suspicious, this should be an easier topic.

Julia has a module system. It supports export and automatic import of explicitly exported identifiers. You can also still access non-exported identifiers with additional syntax. This is good, because module designers may not always perfectly anticipate what users actually need to access. Common Lisp’s package system supports a similar distinction between external and internal definitions that can be accessed in different ways. I slightly prefer Common Lisp’s ability to use the package name as a prefix even for explicitly exported definitions. There is no feature in Julia to rename imported identifiers, which is something where Common Lisp’s support for explicit package name prefixes can come in very handy. I would like to see something like Oberon’s support for renaming identifiers on import in some Lisp dialect someday, because I believe that is the most complete solution for dealing with potential name conflicts.

In terms of meta-programming, apart from macros, Julia also supports (top-level) eval, like Common Lisp. Julia’s support for “reflection” is much weaker than Common Lisp’s CLOS MOP: You can only inspect types at runtime, but you cannot modify them (and language designers should stop calling something “reflection” that is clearly just “introspection”).

Both Julia and Common Lisp support multi-dimensional arrays. Common Lisp’s arrays are in row-major order, starting at index 0 in every dimension. Julia’s arrays are column-major order, starting at index 1 in every dimension. Julia’s support for multi-dimensional arrays is a library feature, whereas Common Lisp’s support is built into the language. Julia supports both dense and sparse matrices, where Common Lisp supports only dense matrices out of the box.

There are a lot of libraries that ship with Julia targeted at scientific computing.

Julia supports parallel programming with a model built on top of message passing: If you want to run parallel algorithms, you essentially start several instances of Julia that communicate with each other. The model does not support shared memory, and there is no multi-threading within a Julia instance (although there seem to be discussions among the Julia designers to add this in the future). The model is built on top of MPI as an implementation backend. However, the actual programming model supports single-sided communication: You can ask a function to be executed in some other Julia worker process, and can later synchronize with it to fetch results. On top of that, there are some high-level constructs provided as library features, such parallel maps and loops. Julia’s message passing model ensures that within a Julia instance, only one task is executed at a time, so there is yet no need to provide low-level synchronization mechanisms, such as locks or atomic operations. The lack of shared-memory parallelism is problematic because many parallel algorithms that are very easy to express with shared memory become quite complicated in a distributed memory setting. On the other hand, Julia’s model easily supports true distributed programming: You can configure Julia to run several instances across a cluster, and use them in a quite straightforward way: substantially easier than what you have to do with, say, MPI, and much closer with regard to ease of use to modern PGAS languages like Chapel or X10.

The ANSI specification for Common Lisp does not mention anything about multi-threading or parallel programming at all, but many Common Lisp implementations add support for shared-memory parallelism. I will not go into details here, but let me just briefly state that, for example, the LispWorks implementation of Common Lisp provides excellent support for symmetric multiprocessing that is at least on par with what you can find in most other language implementations in terms of parallel programming support. However, unfortunately, support for true distributed memory models seems almost non-existent in Common Lisp, apart for some basic support for MPI in a library that was maintained only for a very short period of time a couple of years ago. Julia looks like a good source of inspiration for adding such features to Common Lisp.

However, one aspect of Julia’s message passing approach seems problematic, as far as I can tell: You can pass closures between different instances of Julia, but it’s not clear how free variables in a lambda expression are bound. It seems that lexical variables are bound and serialized to another process, but global variables are not serialized and need to be present in any presence that may execute the closure. Experiments with adding side effects to free variables in lambda expressions that are passed to other processes seem to suggest that the semantics of this combination of features are unpredictable. At least, I have not been able to figure out what happens when — sometimes variables seem to be updated at the sender’s side, sometimes not — and I didn’t find a discussion of this topic in the Julia manual.

Anyway, as you can tell, there are a lot of interesting features in Julia, and it’s definitely worth a try.

17 comments:

Viral B. Shah said...

Julia actually uses regular TCP/IP for communication. There is an MPI package (https://github.com/lcw/MPI.jl) should one want MPI as the transport and other MPI primitives, especially collectives and such.

Parallel programming in Julia is very much work in progress and will see significant improvements in the next couple of releases.

Redline6561 said...

Lparallel is a recent CL library that provides not only excellent, portable tools for SMP but also a companion library lfarm for distributed computation. Might be worth having a look. :)

Valentin said...

Recently GOTO support has been added in Julia. https://github.com/JuliaLang/julia/pull/5699

It just doesn't sem to be mentioned in the documentation.

Harlan said...

The note about parametric types being unnecessary because of macros is interesting. Unlike Lisps, Julia was, as I understand, designed to minimize the need for metaprogramming for most end-user tasks, specifically because much of the intended audience of scientists and engineers are not professional programmers. One of the primary goals of Julia is to be a much better language than Matlab, which is a low bar, but does suggest the value of certain language features and design philosophies that might seem odd from other points of view.

Stefan Karpinski said...

> Julia supports parametric types. I don’t see at the moment why this is relevant. You could achieve similar functionality also with some macrology. Maybe I’m missing something here.

Parametric types allow you to, among other things, specify what kind of data arrays can contain. The guarantees that Array{Float64} or Array{Complex{Float64}} have C/Fortran-compatible memory layout, which means you can call BLAS, LAPACK, FFTW, and other numerical libraries on them quickly and easily. It is also very common to want to dispatch on parametric types, and Julia's dispatch system makes this simple and clean. You can, for example, provide a generic matrix multiply for Matrix{<:Number}*Matrix{<:Number} but have a specific method that uses BLAS instead to implement Matrix{Float64}*Matrix{Float64}. Without first-class support for parametric types and dispatching on them, this would have to be hacked in, and worse still, user-defined types would be forced to use the generic fallback or resort to some kind of horrible monkey patching to try to insert a custom matrix multiply.

> There is a whole section on constructors (make-instance / make-struct) in the Julia manual. This makes me suspicious, this should be an easier topic.

This is one of the aspects of the language that is least satisfying to me at the moment. I can only say that parametric types significantly complicate the matter.

Akshay said...

I wish CL actually had inline generics and parameterized types (like simple-array); implementing this with macrology wasn't very straight forward in Matlisp.

Doing this is also annoying because one ends up reimplementing things (and cruft) which, IMO, are better done as part of the compiler (which can do static typechecking amongst other things).

CL does show its age when it comes to all this. Not surprising when you realize that functional programming came to the forefront - academically- only at the end of the AI winter.

I wonder if there are enough people who feel this way, so that CL spec can be updated.

Pascal Costanza said...

@Viral: Thanks for the clarification about MPI, I wasn't aware of this. About parallel programming: That's very good news. I hope you are also following there a toolbox approach, where high-level constructs can be built on top of low-level ones (somewhat like LispWorks or TBB).

@Redline6561: Yes, I always forget about lparallel. Shame on me, and thanks a lot for mentioning it!

@Valentin: This is good news!

@Stefan: Being able to dispatch on parametric types is indeed interesting. I haven't thought of that. For constructors: Method combination (before/after/around methods) can be really beneficial here. For example, consider the design of ISLISP. See http://www.islisp.info/Documents/PDF/islisp-2007-03-17-pd-v23.pdf - Section 15.4

@Akshay: The crucial part, as far as I can tell, is the protocol for compute-discriminating-function, which only allows for installing a discriminating function in the only one existing generic function object. To allow for polymorphic inline caches, it would be useful to have (a) a variant of compute-discriminating-function that can install a discriminating function in some other generic function object and (b) a variant of compute-discriminating-function that can restrict the acceptable types, to create a more efficient discriminating function. This all would require some elaborate changes in the protocols, though...

Eli said...

Have you written up your impressions of Clojure or your reasons for not being impressed with it?

As a Common Lisp programmer who has recently (as in a week ago) begun work on a Clojure project I would be very interested.

Pascal Costanza said...

@Eli: It's very unlikely that I will write a similar comparison between Clojure and Common Lisp. Sorry.

Sam Tobin-Hochstadt said...

It's just not true, as you know well, that having a separate namespace for functions removes the necessity of hygiene in macros. It's also not true that syntax-case is somehow fundamental to Scheme macros -- syntax-case is merely a fancy pattern matcher.

Viral B. Shah said...

@Pascal You are very right about a layering approach for parallel computing. We currently have a very low-level method of doing RPCs, where you can spawn processes and get a RemoteRef and wait on it. On top of this, we currently have @parallel, pmap, and DArrays. We will continue to have more layering and refactor these capabilities once we release 0.3.

Pascal Costanza said...

@Viral: This sounds very good, I'm looking forward to what's coming.

@Sam Tobin-Hochstadt: Please don't make assumptions about what I do know well and what I don't know well. I do know well that hygienic macro systems are strictly more expressive than non-hygienic macro systems. However, what I, in fact, also do know well is that in Common Lisp, the combination of Lisp-2 and the package system make macro hygiene issues almost completely irrelevant, to the extent that the few cases you can construct where they would be relevant don't matter anymore in practice. You should study this in more detail, there are some interesting insights to be had.

I also didn't say that syntax-case is fundamental. It just seems to be one of the preferred macro systems in Scheme, to the extent that it even made it into R6RS. (I would prefer renaming. Julia's approach also looks also promising.)

Thomas said...

Thanks for writing this up! I wasn't aware of Julia, but it looks really interesting.

You said that you wished there were a Lisp with a module system that supports renaming identifiers. Racket's module system does this: http://docs.racket-lang.org/reference/require.html

See only-in, except-in, prefix-in, rename-in, ...

That module system is really the Racket crown jewels. That, and the fact that everything is built around lexical bindings to enable it, rather than explicit first class symbols for names.

Pascal Costanza said...

@Thomas: prefix-in indeed looks like what I mean. I wasn't aware of this, thanks for pointing this out.

I strongly prefer a system based on symbols/packages rather than modules/lexical bindings, but I understand why others may disagree and prefer things the other way around. It's good that both choices exist.

Thomas said...

@Pascal: I agree it's good that both exist, although they only solve partially-overlapping issues. In particular, if I have to deal with the possibility of more than one version of the same code being active at the same time, I want a lexical module system; if I have to juggle symbols at runtime, I want a package system. For most everything else, I agree it's more a question of personal preference.

Bob said...

In terms of macros, you may be interested in a pull request that is pending. I have no idea if it will be merged but it looks to me that it would make writing macros a bit easier. Look here: https://github.com/JuliaLang/julia/pull/6910

Pascal Costanza said...

@Bob: Wow, David Moon is contributing patches to Julia? It can't get much cooler than that...