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.

August 18, 2013

The Human Consequences of Dynamic Typing

I agree with Jay McCarthy that static typing is anti-human. I think I can give a slightly more elaborate example of a program that every static type checker must reject, but that is nevertheless correct. Everything below is valid Common Lisp:

(defclass person ()
  ((name :initarg :name
         :accessor person-name)))
(defmethod display ((p person))
  (format t "Person: Name ~S, address ~S."
            (person-name p)
            (person-address p)))

A static type checker must reject this program because there is no address field defined in the class person that person-address presumably refers to. However, below is a run of the program in a Lisp listener that runs to a correct completion without fatal (!) errors:

CL-USER 1 > (defvar *p* (make-instance 'person :name "Pascal"))
*P*
CL-USER 2 > (display *p*)
Error: Undefined function PERSON-ADDRESS called with arguments
(#<PERSON 4020059AB3>).
  1 (continue) Try invoking PERSON-ADDRESS again.
  2 Return some values from the call to PERSON-ADDRESS.
  3 Try invoking something other than PERSON-ADDRESS with the
    same arguments.
  4 Set the symbol-function of PERSON-ADDRESS to another
    function.
  5 (abort) Return to level 0.
  6 Return to top loop level 0.
Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for
other options.
CL-USER 3 : 1 > (defclass person ()
                  ((name    :initarg :name
                            :accessor person-name)
                   (address :initarg :address
                            :accessor person-address)))
#<STANDARD-CLASS PERSON 4130371F6B>
CL-USER 4 : 1 > :c 1
Error: The slot ADDRESS is unbound in the object
#<PERSON 41303DD973> (an instance of class
#<STANDARD-CLASS PERSON 4130371F6B>).
  1 (continue) Try reading slot ADDRESS again.
  2 Specify a value to use this time for slot ADDRESS.
  3 Specify a value to set slot ADDRESS to.
  4 (abort) Return to level 0.
  5 Return to top loop level 0.
Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for
other options.
CL-USER 5 : 1 > :c 3
Enter a form to be evaluated: "Belgium"
Person: Name "Pascal", address "Belgium".
NIL
CL-USER 6 > (display *p*)
Person: Name "Pascal", address "Belgium".
NIL

The "trick" is that the Lisp listener allows for interactive modification of a program while it is running. No static type checker can anticipate what modifications will be performed at runtime.

This is not a toy feature of Common Lisp, but something that many Lisp developers rely on. For example, my own ContextL library crucially relies on the very class redefinition feature I demonstrate above. Joe Marshall provides another account how such features can solve real-world problems.

February 17, 2013

Closer to MOP supports ABCL 1.1.1

The darcs repositories of Closer to MOP now also support ABCL 1.1.1. I plan to make a more official release soon. The Common Lisp implementations currently covered are now as follows: Allegro 9.0, ABCL 1.1.1, CLisp 2.49, Clozure Common Lisp 1.8, CMU CL 20d, ECL 12.12.1, LispWorks 6.0.x and 6.1.x, SBCL 1.1.4, and SCL 1.3.9.

September 25, 2012

Closer to MOP on ABCL and ECL

Just to report on work in progress: I am currently working in my spare time on making sure that Closer to MOP works (again) with ABCL and ECL. ABCL is in relatively good shape, but still needs a couple of bugs fixed here and there. Rudi Schlatte is doing a fantastic job at responding to bug reports. I'm pretty sure the next release will have excellent Closer to MOP support. ECL's recent version came with several changes in its CLOS MOP implementation which broke a lot of things in Closer to MOP, so the current version of Closer to MOP doesn't work with ECL. I'm doing what I can to make sure Closer to MOP is back to speed again with ECL. However, I can only do this in my spare time, and will be busy moving in the next couple of weeks, so some delays are to be expected...

August 09, 2012

Arguments against call/cc

An excellent collection of good arguments against having call/cc in a programming language (such as Scheme), by the ever-inspiring Oleg Kiselyow: An argument against call/cc.