(take 5 william-byrd)

Posted by on Feb 16, 2012

William Byrd is a postdoc at Indiana University researching the applicability of declarative programming techniques to high-performance computing domains. In addition, he is one of the three authors of the fantastic book The Reasoned Schemer that walks the reader through the development of a small but powerful logical programming system in Scheme called miniKanren. Dr. Byrd attended the 2011 Clojure Conj and gave (along with Dr. Friedman) what became one of the best talks of the conference -- during the conference off hours. In this candid installment in the (take) series of micro-interviews Dr. Byrd discusses Clojure, Scheme, Lisp, macros, and miniKanren's evolution.

A trend in the Clojure language and its ecosystem is an increasing emphasis on declarative programming models, including Datalog, logic, and relational programming. Is this progression unique to the Clojure evolution, or is it more emblematic of a more general trend?

Declarative programming has been used in industry for decades: HTML, XSLT, GNU Make, and SQL are all declarative languages. I see a slightly different trend, towards programmers designing their own domain-specific languages, many of which are declarative. Of course Lispers have been doing this for decades--Lisp macros are arguably the most powerful tool for creating DSLs. Therefore Clojure is almost perfectly positioned as a pragmatic language for DSL creation. Almost, but not quite.

Not quite, because Clojure's macro system appears to me to be a kludge, trying to patch up Common Lisp's defmacro without going all the way to real hygienic macros. I don't mean to be overly critical--I'm not happy with the state of Scheme, either, which has not one but two hygienic macro systems, neither of which is ideal.

The more powerful Scheme macro system, syntax-case, gives the programmer the full power of Scheme at macro expansion time, along with the ability to "bend" hygiene when desired. Syntax-case is powerful enough to define Common Lisp's defmacro (and almost certainly powerful enough to define Clojure's defmacro as well). Unfortunately, syntax-case is notoriously complicated. As far as I can tell, mastering syntax-case requires a mental model equivalent in complexity to the macro expander's implementation. As a result, Dan, Oleg, and I refuse to use syntax-case.

The other Scheme macro system, syntax-rules, is strictly less powerful than syntax-case, and can in fact be implemented in syntax-case. However, the mental model required to use syntax-rules is much simpler, as it is essentially a term-rewriting system with hygiene. For vanilla forms such as let, and, and or, syntax-rules works beautifully. For incredibly complicated macros, such as the match pattern matcher used in Kent Dybvig's compiler course at Indiana, the full power of syntax-case is probably required. For almost all other macros, it seems like a system with just a little more power than syntax-rules would be both sufficient and ideal. For example, often a macro writer wishes to concatenate two symbols--currently this requires using syntax-case, even if the rest of the macro is trivial.

If a hygienic macro system that hits the sweet spot between syntax-rules and syntax-case is created, I hope it will be adopted by Schemers and Clojurers alike. A few steps in this direction include the Dylan macro system and Ryan Culpepper's syntax-parse. Also needed is a way to learn how to write non-trivial hygienic macros that doesn't involve earning a PhD in programming languages from Indiana or Northeastern.

Because of the limitations imposed by the JVM, is Clojure unable to address certain classes of problems due to a limitation in its support for CPS?

Clojure is Turing-complete, so in theory the answer to all such questions is 'no'--you can always encode the problem using iteration. In practice, you lose many of the powerful correctness-preserving transformations enabled by CPS (CPS is the gateway drug of program transformations).

Even worse, there is a tremendous hidden cost to the Clojure community. Schemers should be the greatest fans of Clojure; instead, they see the improper handling of tail calls, along with a suspect-looking macro system, and yawn instead of jumping onboard. I think the macro situation can and should be improved; I don't know what to do about tail calls, other than clearly explain the design tradeoffs to Schemers and challenge them to do better.

How do you see the future of Lisp progressing?

Common Lisp has no future--if taking the union of features from multiple Lisp Machine implementations didn't kill it (why have one object system when you can have three?), standardization did. Fortran is still evolving; Common Lisp isn't.

So far the Scheme community has avoided making the same mistakes. Historically, only the intersection of features from the major implementations have made it into the standard. The result is a standard language that is useless for real-world programming (FFI and threads aren't in the current standard, for example) but encourages researchers and implementers to experiment with new features. In fact, Scheme shouldn't be viewed as a complete programming language--rather, Scheme is a dialect of Lisp, and the various implementations (Racket, Chez, Ikarus, etc.) are dialects of Scheme. Scheme will never become a popular language, but popular languages are becoming more like Scheme. For example, Ruby ripped off much of Scheme--alas, Matz decided not to rip off the most important part, hygienic macros, which is why Ruby programmers think the solution to every problem is to hack the interpreter.

One interesting Lisp you didn't mention is Dylan, which was created by Apple in the 90's and then abandoned. Dylan is an object-oriented infix-notation Scheme designed for systems programming, with well-designed libraries, real hygienic macros, and outstanding performance. I'm trying to steal a few cool ideas from Dylan--Clojurers should as well. Dylan is dead, but hopefully its ideas will live on.

Clojure feels like a different beast entirely. Clojure has one canonical implementation, one lead designer, no rigorous standard (this part needs to change!), an enthusiastic and rapidly growing community, and a very practical bent. From that perspective, Clojure sounds much more like Ruby or Python than Lisp. Two major differences I see are the quality of the implementation (Clojure shows Pythoners that pragmatic dynamic languages needn't be slow) and the incorporation of STM, fast immutable data structures, logic programming, and other useful but potentially scary technologies that haven't made their way into the fundamentally conservative world of "scripting" languages (where much of the innovation is in syntactic sugar, since these languages lack hygienic macros).

Will Clojure become as popular as Ruby or Python? Probably not. Will the languages that replace Ruby and Python be influenced by Clojure? Almost certainly. This is one reason it's important for Clojurers to understand the weaknesses of the language, and not just its strengths.

What is it like to work with Dr. Friedman and Oleg Kiselyov?

Dan is a close friend and mentor--working with him is always great fun. We argue constantly over language design--sometimes I'm even right.

Oleg is an emissary from some advanced alien race. Working with him is both exhausting and enlightening.

What are you working on next?

I'm a postdoc working for Andrew Lumsdaine in CREST, the Center for Research in Extreme Scale Technologies at Indiana University. My primary research is on the design, implementation, and application of declarative languages to High Performance Computing. I'm fortunate to be working with Eric Holk, Claire Alvis, Andy Lumsdaine, Arun Chauhan, and several other talented hackers and language designers at Indiana. We're currently working on two languages: Kanor, a message-passing language for programming cluster supercomputers, and Harlan, a declarative language for general purpose GPU programming. Of course both languages are implemented in Scheme. We hope to embed Harlan in the Scheme REPL; if we are successful, perhaps David Nolen can port our implementation to Clojure!

I'm also working with Dan and Claire on improving cKanren, our implementation of constraint logic programming. I can't wait to see what cool tricks David uses in his core.logic version of cKanren.

For fun I run 3D printing and Arduino clubs for undergrads, and am working with Nicole Jacquard, Andy Lumsdaine, and Kylie Peppler to start a Fab Lab at Indiana. Next semester I'll be teaching a course on Arduino, which will rock.

I'm also doing some fun research with Zach Sparks and Claire at Indiana, and Chris Martens at CMU, on using logic programming to write Interactive Fiction.

Finally, I'm working with some Indiana-trained macrologists on a new hygienic macro system for Scheme, and hopefully for Clojure as well. I hope to say much more about that soon.

blog comments powered by Disqus