Latest posts

Oh boy, it’s another Urn update! I know, I can hardly supress my excitment. There’s been almost 50 commits since the last release, and a whole host of features inside those commits. So let’s get started.

Goodbye setf!, hello lenses!

A while ago we introduced the collections library and the joy that is lenses. I won’t re-iterate what is said there, but in essence it provides a powerful and composable way to query and update objects (as well as making immutable copies of them). We’ve merged this feature into the main standard library, replacing the rather hacky setf!.

String interpolation

If you need to concatinate a load of strings together, there aren’t many nice ways. Sure, format strings help a bit but there is nothing quite as great as string interpolation! Prefixing a string with the dollar ($) sign (or calling the $ macro) allows you to embed variables directly in code:

> (let [(foo "some string")
.      (bar '(1 2 3))]
. $"Interpolating ${foo} and ~{bar}")

"Interpolating some string (1 2 3)"

Currently Urn’s implementation is very basic, just allowing variables (it’s implemented as a macro after all), but we’ve plans to extend it.

More code-generation improvements

Every release I witter on about the various code generation improvements we’ve made, and this time is no exception. I’ve been running the generated code through luacheck to try to find some places where we’re generating pretty poor Lua code. We’ve made a lot of progress in this area, cutting the number of warnings from 469 to 104 (which equates to a warning on 1.2% of lines).

This isn’t just a meaningless statistic though - the end result means more compact and “readable” code. Thanks to various enhancements, we’ve cut 300 lines from the previous release.

Well, I think you should ring your friend and gather the family for this special occasion. Yes: it’s another Urn update! And, once again, there is plenty to excite you (well, as long as you’re a cephalopod with a passion for compilers).

Magic function generation

On previous versions of Urn, we had this ugly mess of definitions for car and cdr compositions. Thanks to the power of compile-time code generation, we can replace 60 definitions with 17 simple lines. This has massively reduced duplication, and helps showcase a neat feature of the language!

Codegen improvements

As I’ve talked about many times before, Urn tries to generate the nicest and most efficient Lua code possible. However, due to the nature of Lisp (and some design choices we made for Urn), this isn’t always easy. Thankfully the last few releases have made significant improvements, and this one is no exception.

First off: we try to merge multiple local declarations into one. For instance:

(let [(a (abc))
      (b (xyz))]
  (print! a b))

would get compiled into:

local a, b = abc(), xyz()
print1(a, b)

As this is only a codegen improvement, it won’t merge assignments from different let/let* blocks. This is something I hope to address in the future.

We’ve also taught the compiler to understand operator precedence. Before Urn would play safe and wrap everything in brackets to ensure operator order was conserved. Urn now understands how Lua parses it, and so only needs to insert brackets where appropriate. This makes for a much more readable source!

Well, it’s Urn update time, and there’s a lot to be excited about!

Self-hosting!

As mentioned in the last post, the Urn compiler was initially written in Lua and ported across to Urn as the compiler matured. This release marks the last step of this process, with the compiler being written in 100% Urn. This shouldn’t have any major effect on the end user (you guys), but is still an important step in the maturing of the language.

Because it is mildly interesting, I thought I’d post some statistics about the Urn codebase:

• The compiler is made up of 5614 lines of Urn code.
• The standard library has 3498 lines of Urn, and 399 lines of Lua.
• There are an additional 789 lines of tests.

Improved name-mangling

If you’ve ever looked at the Lua code the Urn compiler emits, you’ll notice it isn’t especially nice. One of the worst bits is that every variable would be uniquely numbered: for instance arg would become arg1. This was required in order to avoid name collisions in the result of function inlining, but wasn’t especially pleasing to the eye either. Thankfully we’ve now improved this, meaning variables will only be numbered if there would otherwise be a name collision.

A further improvement here is that variables emitted from gensym will now be emitted as temp (with a number in the event of collisions). This makes the code slightly easier to read, and means using macros won’t result in large potions of the compiled output changing - only some expressions in the local scope.

Improved recursion

As I’m sure you’re aware (I’ve gone on about it enough times), Urn attempts to have a minimal “core language”, with everything else being added via macros. Consequently, there is no built-in support for loops, this being implemented using tail recursion.

Whilst this leads to a much simpler and more flexible compiler, it does mean the generated Lua is rather inefficient. For instance, consider the following for loop:

(for i 1 5 1
  (print! i))

This would compile into something like:

local temp = nil
temp = (function(temp1)
  if (temp1 <= 5) then
    print1(temp1)
    return temp((temp1 + 1))
  else
    return nil
  end
end)
temp(1)

Hardly very nice to look at, nor very efficient. However, if you look at what the macros expand do, the reasons why you get such ugly code become obvious:

((lambda (temp)
  (set! temp (lambda (temp1)
               (cond
                 [(<= temp1 5)
                  (base/print temp1)
                  (temp (+ temp1 1))]
                  [true])))
  (r_255 1)))

Ideally, we’d be able to detect this code is a loop and convert it into something more sane. However, it turns out that it’s rather hard to create a use-define chain and determine what is a loop and what isn’t. Thankfully we don’t need to - pretty much every loop (while, for, etc…) will get compiled into something resembling the above - we just need to detect that basic form instead!

We can also check for when such a loop is only used once, and so inline it at the call site, meaning you don’t have a temporary lambda at all. This means the initial for loop now gets compiled to the following:

local temp = nil
local temp1 = 1
while (temp1 <= 5) do
  print1(temp1)
  temp1 = (temp1 + 1)
end

Note that there are also some improvements to general loop compilation too. Under previous versions of Urn, such a loop would have been compiled as a while true do with a condition and breaks. We can now detect certain constructs and convert them into the appropriate loop. Obviously there are more potential improvements - this could be converted into a for loop. However, this is definitely a stab in the right direction.

It is also worth stating that these changes aren’t purely cosmetic - there is a significant performance impact too. Thanks to the improved codegen, compiling the compiler took 7.1 seconds, instead of the initial 9.8 - an improvements of 2.7 seconds.

Other changes

Many thanks to CrazedProgrammer and Lignumm for their additions to the standard library.

You can read the full changelog on the GitLab repo.

I’ve just pushed another update to Urn. This doesn’t have any major features, but offers some interesting improvements:

Another step towards self-hosting

When we first started writing the Urn compiler, we obviously couldn’t write it in Urn so, for want of a better choice, we wrote it in Lua. As Urn progressed, we’ve converted more and more of the compiler to Urn. Over the last couple of bits, I’ve ported about 650 lines of the compiler to Urn, meaning we’ve a little less than 500 lines left to migrate.

Thanks to this, the compiler is now 4900 lines of Urn (this excludes tests or the standard library). I’m not sure if this a demonstration of the conciseness of Urn, or the lack of comments in the code.

Various optimiser improvements

Sadly, Urns optimiser is by far the slowest part of the compiler - taking 5.4 seconds on the Urn compiler. However, thanks to a couple of minor changes in the tree visitor, the optimiser’s performance has increased - taking it down to 5.1 seconds for the Urn compiler. This is far from an ideal time, and so we will continue to make further improvements to the optimiser and code generation.

Oh my, it’s been a while since one of these. Rest assured, we haven’t been sitting idle - there have been 100 commits to master since our last release. So, let’s get into the changes:

We broke things

Firstly, this is a great opportunity to remind you that Urn, whilst pretty stable, is still in beta. This release has several breaking changes you should be aware of:

• #s and # are now one function called n.
• The # symbol is used to denote hexadecimal and binary literals. In order to stick closer to Common Lisp, you should now write #x23 and #b011011 when you require other bases. Escape codes inside strings have not changed.
• Several pattern matching expressions have become infix. This makes some pattern matching code slightly easier to read. Please refer to the documentation to see what has changed.

Standard library improvements

Pattern matching improvements

As mentioned in the breaking changes section, pattern matching got tweaked a little. There are now support for struct patterns and additional guards. For instance, you can now trivially decompose a structure:

(define my-vector { :x 1 :y 2 :z 3 })
(destructuring-bind [{ :x ?x :y ?y} my-vector]
  (print! x y))

and add additional requirements:

(case foo
  [((string? @ ?x) :when (= (string/char-at x 1) "f")) x] ;; Find strings which start with "f".
  [_ "boring"]) ;; Anything else

Set functions

demhydraz has added functions for a whole host of set manipulation functions. This includes set difference, union, and probably more. Actually I’m not sure if it’s more. I haven’t checked. Which is fine, as no one actually got this far through the post. Many thanks to incinirate for his work on improving the performance of the nub function.

bignum and bit32

Very many thanks to CrazedProgrammer here for these contributions. Urn now includes a big integer library, as well as a various functions for manipulating bits. I’m sure both of these will prove immensely valuable in the future.

Compiler improvements

Let’s be honest, only I’m excited by these. There have been a couple of minor improvements to the compiler which results in more efficient or smaller code being produced:

Tail recursion into loops

In order to keep a more minimal core language, Urn has no loops. These are emulated via tail recursive functions. However, these are less efficient than conventional loops and so a solution needed to be found. In this version of Urn, top level definitions will be converted into loops where appropriate. For instance, consider this definition of part-all.

partAll1 = (function(xs12, i8, e1, f3)
  while true do
    if (i8 > e1) then
      return true
    elseif f3(xs12[i8]) then
      i8 = (i8 + 1)
    else
      return false
    end
  end
end)

We do not currently optimise tail recursive functions in letrec (and so the while or for macros), though this is something you can expect to see in a later release. I’m also working on ways to generate even more idiomatic Lua, perhaps replacing the above code with a normal for loop.

Rewrite rules/loop fusion

We’ve also added “loop fusion” as an optional compiler plugin. This allows you to define “patterns” which will get simplified at compile time. For instance:

(fusion/defrule (map ?f (map ?g ?xs))
                (map (lambda (%x) (?f (?g %x))) ?xs))

Will rewrite two nested maps into one map over a composition of the two functions. This reduces the number of temporary lists required when using lots of list functions. However, it is not enabled by default as it can technically change the order of operations. This shouldn’t affect most programs, as loop iteration code should generally be pure, but I don’t feel comfortable enabling it by default.

Operators support multiple arguments

This is a relatively small one: All “Lua” operators now accept a variable number of arguments. For instance:

(print! (+ a b c d))

will compile to:

print1((a1 + b1 + c1 + d1))