When you’re Smiling

Every once in a while, I go back and reread the Reddit thread where they were first talking about Smile. Each time I read it, it’s a reminder of what I’m up against. There are a lot of interesting notions about what’s good in a programming language; everybody has their own pet feature: It has to be as fast as C! It has to allow infinite threads! It has to be 100% type-safe! It has to be type-inferring! It has to be designed for building web services! Did you see how X implemented generics!? And you’d better not leave out Intellisense!!!

It reminds me of back in the ’90s when I worked with this lady who was convinced that client-server would take over the world — by which she meant custom apps running on PCs talking to mainframes. Our worldviews and past experiences skew our expectations toward what we want, and the future often doesn’t play out the way we hope or expect.

(This is gonna be a long post, and I’m going to talk a lot about Smile, including some philosophy and history, a deep-dive into the core syntax, and a bunch of additional examples at the end. I feel like writing a bit on one of my favorite topics. Don’t feel obligated to read the whole thing.)


 

Smile Isn’t for Everybody

Smile is the right language — for my design criteria. It’s intended to be small, elegant, concise — and expressive. Expressiveness is the ultimate goal, the critical target, the same way Lisp is expressive — and that’s Lisp: the language you can mutate to do and be anything. If ‘X’ functionality doesn’t exist in Lisp, you bolt it onto the language and keep going. If ‘Y’ functionality isn’t good enough, replace it. As a good example, in the early ’80s, object-orientation was becoming all the rage, and Lisp didn’t have any kind of objects. So a number of people added object-orientation to Lisp as libraries — there were Flavors and LOOPS and CLOS, and even some mini-object projects, and they all fought it out Darwinian fashion, and the best object-orientation system won. (Well, okay, CLOS won, but we can pretend it’s the best.)

Now imagine trying to do that with your language of choice. Imagine C# or Java without generics, just like they were back at their beginnings, and then imagine trying to extend those languages to support generics without altering the runtime. It’s trivial in Lisp to imagine such things, but without Sun/Oracle/Microsoft altering the Java or C# compilers, you couldn’t conceive of such things in Java or C#. Now imagine adding aspect-oriented programming, or declarative programming à la Prolog, or a compiler-constructor à la YACC natively to the language without help from the languages’ creators. It’s folly in most languages, but in Lisp or Scheme or Smalltalk — or Smile — it’s just an ordinary Tuesday.

I firmly believe that some time around 1960, we made a really serious mistake in the computer industry. McCarthy offered us a choice between Algol, which we (almost) understood but which didn’t conceptually scale, and Lisp, which we barely understood at all but which scaled infinitely — and we picked Algol. We picked what we understood: Iterative execution, structured execution, do-this-and-then-that-and-then-loop-back-and-do-it-again. We could have picked conceptual scalability, but it was scary and weird and read like gibberish, so we picked the safe choice, and Pascal, C, C++, Java, C#, D, JavaScript, Ruby, Python, Perl, PHP, and a hundred other popular languages all derive from that lineage.

The problem with that choice is that we ended up with an ugly dilemma: We spend a lot of time thinking about how to bend problems to fit your language rather than how to bend your language to fit your problems. When you’re coding in any of those languages I just named, your goal is to figure out how to use the language’s primitives and basic forms and syntax to describe your problem well enough for the computer to execute it. In Lisp or Smalltalk, your goal is to figure out how to bend, alter, and mutate the language so that your problem can be natively be expressed in the new mutant derivative language you’ve created.

Smile is my attempt to help us get back on the right track. It’s intended to be good at data structures and mutatable in ways that other languages simply aren’t. That said, I didn’t get all I wanted in the design. I wanted the ability for anything to mean anything anywhere under any circumstances for any reason, and without confusion, and I had to scale that goal back a little. But at its heart, Smile is still a Lisp, still a Smalltalk, and like the languages of the giants on whose shoulders it stands, it conceptually scales pretty darned well.

Current Status

I work on Smile a lot. Not that I have a lot of time — we have a one-year-old! — but I try when I can. Even if I’m not coding on it, I’m thinking about it: On my drive to and from work, at lunch, over the dinner table. It’s consumed my thoughts for more than a decade, and it continues to get better and better.

The core interpreter has actually been sitting on the sidelines for a few months while I build the bytecode compiler, which is starting to get pretty nice. Smile won’t get much attention if Ruby runs circles around it, and rightly so; but there’s no fundamental reason why Smile has to be slow: It’s just that the first interpreter was pretty inefficient. The next one should at least be competitive to languages like Ruby and Python, and while it’s starting to run (small) real programs now, I haven’t benchmarked it yet. With any luck, I’ll have enough of it done by the turn of the year that I can toss the old slow interpreter and at least have a shot at Smile being good enough to be worth sharing.

That’s the thing, you see. Smile’s a neat idea, but I don’t want the initial release to be off-putting. First interactions with a language can often color its reception for decades, and I think Smile is worthy enough that it deserves a real shot in the marketplace of ideas. So it needs an interpreter that’s at least passably fast, and libraries that are at least tolerable for basic work. If anybody else was involved in this, it might go faster, but it’s just me, and again, I have a baby and a wife and a life.


 

A Deeper Dive

One of the biggest criticisms of the earlier posts about Smile was that I didn’t share much of how the language works — how it really works. I gave some examples, but not much of the real meat. So today we’re going to remedy that.

There are only a handful of syntactic primitives in Smile. Lisp only has one — the list. Smalltalk has three: Two postfix forms, and its bracketed form. Smile has two basic forms used by everything, three “simplified” forms used by nearly all expressions, and a handful of “special” forms for extremely common things that we tend to expect will look a certain way, like if-then-else. All of the “simplified” and “special” forms are translated at compile time into one of the two basic forms — under the hood, there are Lists and there are Pairs, and there is nothing else.*

(* That’s not quite correct, if you consider the “bigger” form of the language where there are primitive types like Symbol and String and Integer32 and Real64 and a bunch of others. But from a Lispy perspective, where Lisp has its S-boxes or cons cells out of which the entire universe is built, Smile has Lists and Pairs out of which the entire universe is built.)

The two basic forms are these:

    List:  [x y z]
    Pair:  x.y

Lists are built out of cells (S-boxes, cons cells, etc.), and are linked lists, just like in Lisp. There’s a null hanging off the end, just like in Lisp, and null is the empty list, just like in Lisp. Dot is not a Lisp-style dotted pair; if you need a Lisp-style dotted pair, there’s the special ## operator, which you’ll probably never use.

Smile Pairs are a simple tuple form, and are no more complex than they look like: There’s a thing on the left and a thing on the right, and that’s it. Well, mostly. They are, of course, enough syntax to form binary trees by themselves, if you allow parentheses to control precedence.

The more astute among you have no doubt realized that Lists and Pairs are really the same thing — this isn’t really that different from Lisp. And under the hood, these two forms really are equivalent: Smile’s Lists are made of cells that are colored black by convention, and Smile’s Pairs are made of cells that are colored red by convention. Interestingly, this means red-black trees are pretty straightforward data structures in Smile.

The Smile eval function treats Lists as Lisp eval treats Lists — they’re function invocations, and the list members become function arguments, after they are resolved. Eval treats pairs a bit differently: They are treated as attempts to access a named member of an object, whether that member is data or a function. That means that [foo.bar baz.gronk] is a method call on foo of method bar, passing the gronk property of baz.

This is a relatively small change from Lisp, but it lets us uniformly talk about (and represent) both function calls and object-orientation in a single, very simple grammar.

Yes, it’s single-dispatch, and yes, the parameters are positional, not named. Neither one of these should be a deal-breaker.

Translation

There is an additional phase that occurs during compile: There is an “easy” syntax, inspired by the Smalltalk “easy” syntax, that is translated at compile-time into Lists and Pairs. It has three basic forms:

    Unary:   op x
    Binary:  x op y
    N-ary:   x op w, y, z, ...

Under the hood, anything in unary form is transformed into [x.op]. Anything in binary form is transformed into [x.op y]. N-ary form is really just an extension on binary form, and becomes [x.op w y z …].

Ops and x’s and y’s are all just symbols, no matter what they might look like. Smile uses some very simple detection rules, then, to decide if a symbol is an operator: If it was declared in a reachable lexical scope (like var x, or [$scope [x] [ … ]], or a function argument), it’s a variable. If it’s on the left-hand-side of an ‘=’ sign, it’s also a variable. Otherwise, it’s an operator.

There are also a handful of special forms, like if-then-else and function declarations and assignments, that are detected specially and translated into primitive operations:

    if x then y --> [$if x y]
    if x then y else z --> [$if x y z]
    |x| x + 1 --> [$fn [x] [x.+ 1]]
    y = w * z --> [\= y [w.* z]]
    `x --> [quote x]

That doesn’t cover all of the special forms, but with that much alone, you have yourself the beginnings of Smile. It’s even Turing-complete. Add yourself a [$new] operation to create some kind of data storage, and you already have a large percentage of the “core” language.


 

Let the Expressions Reign!

This is enough to begin to see how Smile really works. Everything is a function call or a method call (which are really the same thing). Everything is a list. And everything is an object. There is an inheritance model between objects, and it’s simple and prototypical, but without the weird baggage JavaScript has.

Here, then, are some interesting examples of the core syntax allowing all sorts of mutation. Every one of these is actually the core, bracketed syntax in disguise, and can be expressed in full with the syntax rules you’ve seen above:

    // Hello, World, two different ways:
    Stdout print-line "Hello, World.\n"
    [Stdout.print-line "Hello, World.\n"]

    // An incredibly inefficient way of computing 1.0:
    x = Real64.pi
    one = (sin x)^2 + (cos x)^2

    // Making a list by extending its tail:
    if tail then tail = tail.d = List cons item, null
    else tail = head = List cons item, null

    // The core "reduce" operation in map/reduce:
    accumulator = null
    collection each |item|
        accumulator = [your-reduce-fn accumulator item]

    // Conditional, reusable counting through a predicate:
    Enumerable.count = |pred| {
        total = 0
        collection each |item|
            if [pred item collection] then total += 1
        total
    }

    // Function composition:  With this declaration, you can write:  [f+g x y z]
    Fn.+ = |g| {
        f = this
        || [f [g.apply arguments]]
    }

    // The Y combinator!
    Fn.Y = |f| [
        |x| [x x]
        |y| [f || [y y] apply arguments]
    ]
    // Simpler but less pure definition for Y:  |f| { g = [f || g apply arguments] }

Smile has more than this, a lot more than this, but this is the gold, the core that makes Smile what it is: It grows like Lisp and Smalltalk, but it reads like JavaScript and Ruby. I’d like to think it’s something John McCarthy would have really enjoyed seeing.