Urn - A Lisp implementation for Lua

Urn is a new language developed by me, SquidDev, and demhydraz. Urn is a Lisp dialect with a focus on minimism which compiles to Lua.
So what is a Lisp?
Lisp is a whole family of programming languages, including Common Lisp, Scheme and Clojure. Unlike your standard imperative language with if statements, loops and expressions, Lisp just has one thing: the list. All expressions are function calls, but with the function on the right of the leading parenthesis.

For example, in Lua you might write something like:

if x % 2 == 0 then
  print(x / 2)
else
  print(3 * x + 1)
end

in Lisp you'd write:

(if (= (% x 2) 0)
  (print! (/ x 2))
  (print! (+ (* 3 x) 1)))

So some of you just closed this window in disgust and, to be fair, that is an acceptable first time reaction, but bare with. In return, you get some powerful meta-programming tools which allows you to augment the language in any way you desire.

Macros, the heart of Urn
One of the key features of Lisps is the ability to manipulate code at compile time, transforming it and allowing new syntax. This is achieved through macros. Macros are defined and used just like normal functions, but instead are given a representation of your program and manipulate it, producing new code. One such example is the if macro, as used above:

(defmacro if (c t B)
  `(cond (,c ,t) (true ,B)))

I won't go too much into what is going on here, but in short: you define a macro if which takes three arguments c: the condition, t: the code to execute when true and b, the code to execute when false. It then returns a new expression with these variables spliced in.

Whilst this is a simple example, macros allow you to extend the language in a whole host of ways: all major constructs (variable assignment, loops, assertions) are implemented via macros. In fact, the "core" language of Urn is composed of just a few simple builtins:

• define, define-macro and define-native allow you to create top level definitions.
• quote, syntax-quote, unquote and unquote-splice allow you to easily switch between code and data.
• lambda creates a new function with the specified arguments and body.
• cond is an if-elseif chain, executing the first body whose corresponding expression is truthy.
• set! assigns an already existing variable (such as a function argument) a new value.
• import will load code from another file.

If you've used a Lisp before then Urn should be dead simple to get started with. If not, I recommend you check out The Common Lisp Cookbook. Whilst it isn't exactly the same, many of the examples should translate into Urn quite simply.

Features
Powerful assertion and testing framework, ensuring your code is (generally) correct.


Detailed parser messages, helping you find that problem as soon as possible.


Getting started
Urn is currently hosted on GitLab and mirrored on GitHub. You can clone the repo from either location, or download a zipped version.
You should just be able to execute run.lua to launch the REPL, or specify a series of .lisp files in order to compile a set of files.

Currently the Urn compiler will not run on ComputerCraft, though the compiled files should work without problem. You might be able to get it to run under BSRocks - I'll get back to you on that one.

You can find some auto-generated documentation online. Hopefully this will be expanded in the future to include tutorials and what not.

Looks very nice, will definitely play around with it :D/>

I've just released another version of Urn, with some very groovy features:

Firstly we've started work on Urn's static analysis framework, which provides warnings for code which isn't technically incorrect but shows you've probably made a mistake.



The bindings to Lua's core library have also been given an overhaul with two benefits. Firstly the preamble size has been significantly reduced: from ~130 lines to 15. This means you now only have to see the code that you're interested in. The other advantage of this is the ability to constant fold arbitrary native functions. For instance:

(print! (string/sub "foo bar!" 5))

is simplified to:

print_21_1("bar!")

as string/sub is considered a "pure" function.

I've also done a bit of work on Urn's documentation site. Whilst it is still lacking tutorials, all libraries are documented there which should help you get started :)/>.

I've just pushed another release of Urn.

Firstly, good news for Windows users. Urn will attempt to work out whether your terminal supports ANSI colours, only using them if so. If your terminal is incorrectly detected, please create an issue on GitHub or GitLab.

I've also worked in improving the optimiser. It now will correctly simplify variable accesses to their root value. Something like:

(define x <comple_expr>)
(define y x)
(define z y)
(print! z)

will simplify to

(define x <comple_expr>)
(print! x)

You can see the result of this optimisation on files like this.

One of the common pieces of feedback we've had is that people don't really know what they're doing with Urn. Over the last couple of days I've been working on a series of tutorials for Urn: explaining some of the language features, introducing macros, and what not. Hopefully this make getting started with Urn a breeze.

However, that being said, getting documentation right is hard - especially if you are overly familiar with the language already. If you do struggle to understand something it means the docs are failing! Drop me a line (through the forums, GitHub, GitLab, Discord, Gitter, etc…) and I'd be happy to clarify things and fix the docs.

Many thanks to all those people who have given feedback on Urn so far. Go forth, and try out the docs!

Well, another release with a load more improvements! The highlights:

• Add support for module level documentation.
• Further improvements to how variables are inlined, meaning even more constant expressions get folded.
• Pattern matching! Ahahahr. Hype! Hype!

Right, if you've never seen pattern matching before, then you can think of it as a switch statement on steroids. In short, it allows you to compare the specified object against a series of "patterns": these can be constants, descriptions of a list, or arbitrary functions. For instance, the pattern:

(case x
  [((?x ?y) . ?xs) (print! "List where the head has two entries" x y (pretty xs))]
  [(?x . ?xs) (print! "List with head and tail" (pretty x) (pretty xs))]
  [() (print! "Empty list")])

• If you run it against a list looking something like ((1 2) 3 4 5) then the first pattern will match, with x = 1, y = 2, xs = (3 4 5) as it has the same "layout".
• If it is a list with at least one entry (such as (1 2 3)) then the second pattern matches, giving x = 1, xs = (2 3).
• If the above pattern didn't work, then we must have an empty list, meaning the third pattern matches.

As you can see, this is much shorter than the equivalent Lua (or Lisp without match) code. For the full capabilities of the pattern matching library, see the documentation.

It's sometime after 11o'clock (well, it is in my timezone) which means it must be time for an Urn update!

Line mappings
We've finally got round to adding line mapping, which means any code executed whilst using the Urn compiler will have its positions mapped back to the original source. For instance, consider the following code:

(defun foo (x y)
  (+ x y))

(defun do-bar! (x y)
  (succ (foo (succ y))))

(print! (do-bar! nil 23))

When executed (lua run.lua demo/fail.lisp –run), you'll get something like:

demo/fail.lisp:2 (out.lua:24): attempt to perform arithmetic on a nil value (local 'y')
stack traceback:
        demo/fail.lisp:2 (out.lua:24): in upvalue 'foo'
        demo/fail.lisp:5 (out.lua:27): in local 'do-bar!'
        demo/fail.lisp:7 (out.lua:29): in main chunk

As you can see, all line numbers are converted back to their positions in the root lisp file. In addition to that, names are un-mangles, meaning you get do-bar! rather than doBar_21_1. It is worth noting that this metadata is not persisted, so running the compiled code directly will not result in mapped lines.

Benchmarking
We've also added a fancy benchmarking and timing library, meaning you can wrap function definitions with `(time! …)` in order to time every invocation. For instance:

(time! (defun foo (bar baz)
         (with (sum 0)
           (for i bar baz (set! sum (+ sum i))))))

Also in this release:

• Add for-pairs macro for easier iteration over structs.
• Remove pair library.

It's friday, it's five to five and it's Crackerjack Urn update time. Well, only one of those are true but you should still be excited. There are a couple of exciting things in this update, so let's get cracking.

Top-level unquote
If you've been following the tutorials you'll recall that syntax-quote and unquote allow you to step up and down the "compilation ladder", syntax-quote moving from code to data and unquote moving back up to code. With this update, you can unquote even further up the ladder, allowing you to execute arbitrary code at compile time without the use of macros.

For example, say you want to have a list of the first 10 square numbers. Previously, you could define it as

(define squares (map (cut ^ <> 2) (range 1 10)))

However, this means it'll be executed every time you run your program. This could slow it down. Instead, let's generate these at compile time:

(define squares ,(cons `list (map (cut ^ <> 2) (range 1 10))))

This compiles to

(define squares (list 1 4 9 16 25 36 49 64 81 100))

Of course, there are far more powerful applications of this which we won't go into here.

Property checking
Property checking is a form of testing where you can write some form of assertion and it will generate random inputs, trying to break it. For instance:

(check [(list x)]
  (eq? x (reverse (reverse x))))

Will check if reversing a list twice always results in the same list. This means you can write general assertions for all inputs, rather than specific test cases. For more information, see the documentation.

Lambda-binding syntax
let and friends (let*, letrec, etc…) now allow creating functions just by specifying the arguments and function body - no lambda required!

(letrec [(factorial (x accum)
					  (if (= x 0)
						accum
					   (factorial (- x 1) (* accum x))))]
  (print! (factorial 3 1)))

It's honestly sad to see this topic not getting much attention. What you've got here Squid is something truly epic, it is an absolutely fantastic language, accompanied by equally incredible tools, tutorials, documentation, and the likes. The fact that it doesn't seem to attract many replies is truly mind-boggling. Seriously, give yourself a pat on the back, you deserve it. Anyways, really looking forward to seeing what people make with this, and to use it myself! Cheers!

This indeed is awesome. I think there are not really any replies because people are too stunned, or can't comprehend what all this means for CC (and Lua itself). Great job!

It's update time and oh boy: what an update!

New CLI
First off, in our slow quest to make the Urn compiler self-hosting we've ported the Urn command line interface to Urn. However, this wasn't just a boring old line-for-line port, the rewrite comes with a whole host of new options:

Spoiler

It uses Urn's new argument parser library meaning it can handle all standard argument formats, as well as providing more informative help messages. This new CLI also offers finer control: allowing you to disable specific optimisations, add shebangs to your files, automatically set the executable bit, etc…

Contributions from other people
I'd like to say a big thanks to CrazedProgrammer and Lignum. CrazedProgrammer has sent a couple of PRs in, adding a fancy io library for file manipulation, as well as several additions to the string library. Lignum has put together a bindings for ComputerCraft, meaning you can use your favourite APIs inside Urn. Check out the repo for more information and installation instructions.

Other improvements

• Add optional and type patterns to the pattern matcher.
• Format bold and italic documentation in the REPL.
• Add more granular system to monitor and control optimisation and analysis passes.
• Optimise the optimiser.

As the clock strikes 12, it's update time. Firstly, another big shout out to CrazedProgrammer and Lignum for PR's they've sent. Thanks to them Urn is better tested and has even more features.

Now onto the changes. This update, much like the Musketeers, comes in three parts:

REPL
The REPL is great for testing and experimenting with Urn. In this update, we've added some new features to make it even easier to use:

• Add :search command to find symbols and documentation matching a given pattern.
• Add a magic value out, assigned to the value of the last expression.

Libraries
The standard library is growing day by day with new functionality to make life easier. In this update:

• Add drop and take for making slices of lists
• Add keys and values for accessing structs.
• Export string and math libraries by default.
• Add many more tests for the stdlib

Code generation and optimisation
One of the big problems with Urn currently is that the generated code is rather ugly. Most of it isn't any less efficient than normal Lua, just significantly more verbose than desired. Thankfully, we're beginning to take steps to improve code generation. The backend can now recognise branches which could be compiled to and, or or not and emit the appropriate Lua.

We've also added function inlining, meaning that simple helper functions will be removed, removing the overhead of function calls. You can see the effect of that here.

• Add a inlining optimisation pass (disabled by default, enable with -O+inline).
• Add a new codegen system, with support for not, and and or.
• Simplify trivial lamda expressions
• Correctly pack arguments in directly called lambdas
• Don't constant fold functions which returned multiple values.
• Fix code generation issues when calling quoted lists, or expressions involving quoted lists.
• General performance improvements to the optimiser.

Another update to Urn, though just a minor one. We've been hard at work improving the speed of Urn, using faster algorithms and generating better code. Due to a couple of nifty changes and optimisations, the Urn compiler is somewhere between 30% and 50% faster.

For instance, building the entire Urn compiler (with inlining enabled) took about 3.8 seconds on the last release, but now takes 2.4 seconds. It's worth noting that the Urn compiler is rather large by Lua standards (7k LOC - even Howl has less than that): most of your programs will compile well within a second, even with all optimisations turned on.


Full changelog
Libraries

• [demhydraz] Performance improvements to eq?
• [SquidDev] Pattern matching uses = instead of eq? when matching against literals.
• [demhydraz] Performance improvements to string?, number? and boolean?.
• [demhydraz] Performance improvements to much of the list library.
• [demhydraz] Add any type to the check library.

Code generation

• [SquidDev] Emit trivial and and or statements as their Lua versions (technically in the last release but apparently I forgot to push it).
• [SquidDev] Emit struct instantiations as their Lua equivalent.

Again, just a minor update to Urn, though with some pretty nifty features and improvements. Once again we've got some additional performance improvements - this shaves 0.2-0.3 seconds off the compile time of the main compiler, equating to ~7% faster.

In order to improve the efficiency of Urn, we've added a couple of different profiling modes to Urn. The first one monitors function calls, producing a table of how long is spent inside each function. The second profiler simply samples the call stack every 10k instructions. All call stacks are then merged together and printed to the terminal. What is especially useful is the ability to "invert" the trace, seeing what functions call a particular function instead.

There is also the ability to output text suitable for consumption with the FlameGraph tool, allowing you to generate graphics like this:



For reference, this was generated with tacky/cli.lua –profiler –stack-fold –stack-kind=flame –stack-limit=50 urn/cli – urn/cli | perl flamegraph.pl > out.svg. This simply profiles how long the compiler takes to compile itself. For more information about the options which can be used with the profiler, run tacky.cli –help.

Full Changelog
Libraries

• [demhydraz] Add a `matches?` to test if a pattern matches.
• [demhydraz] Allow using arbitrary predicates in pattern matching.
• [demhydraz] Add mutating version of `insert`.
• [demhydraz] Allow any number of optional values to be missing in pattern matching.

CLI

• [SquidDev] Add stack sampling profiler, with flamegraph support.

Optimiser

• [SquidDev] Optimise usage analysis, shaving 0.3 seconds off compilation.

Another update. This time, we've started adding some much needed features to the standard library. Here are a couple of highlights:

handler-case
handler-case could be thought of a pumped-up try-catch statement. It executes the body like normal, but if you hit an error it will attempt to pattern match against it, meaning you can handle a whole different host of error types:

(handler-case
  (error! "oh-no")
  [(as string? ?x) (print! x)])

use
I'm sure you've had that time where you've forgotten to close a stray file handle, and not been able to delete it without rebooting your (ComputerCraft) computer? use takes care of that, ensuring every object is closed when the block exits.

(use [(file (io/open "temp")]
  (print! (self file :read "a")))

setf! and over!
setf! and over! provide a uniform way of modifying values. setf! takes a value to modify and sets the given value to it. over! takes a value, applies the given function, and stores it back where it came from. The real advantage of these is that they work on a whole host of different things: symbols, lists indexes, table keys, etc… This means it is simple to create macros which work on a whole range of values.

For instance, you could declare the +=* operator as something like:

(defmacro += (selector val) `(over! ,selector (lambda (,'x) (+ ,'x ,val))))

then use it on values, lists, etc…

(+= foo 2)
(+= (nth bar 2) 3)
(+= (.> baz :qux :quux) 4)

Do note, this will ensure you don't index a variable more than once, meaning the last example gets compiled to something like:

local temp = baz.qux
temp.quux = baz.quux + 4

*Don't actually call it this, it isn't very 'lispy' a name.

Full Changelog
Library

• [@demhydraz] Add `handler-case`, a pattern matching error handler.
• [@demhydraz] Add `use` for variables with finalisers
• [@demhydraz] Make `debug` print the input expression and value, returning the input value.
• [@demhydraz] Add `pretty` support for structs.
• [@demhydraz] Make `nil?` work on empty strings.
• [@SquidDev] Add `setf!` and `over!`.

CLI

• [@demhydraz] Add theming to the REPL. This can be done by setting the argument variable URN_COLOURS to something of the form (text 0) (bold 1), etc…
• [@SquidDev] Add `:module` command to display information about the given module.

It's been a while since the last update - sorry about that. However, work on Urn has continued, resulting in some significant improvements to various parts. So then, let's dive in to the major changes.

Compiler Plugins
One cool little feature we've added is the ability to register custom optimisation and warning passes with the compiler. The primary purpose of this is library-specific optimisation and warnings: for instance, you could reduce (reverse (reverse x)) to x, (assuming the list is not subsequently modified). We've got plans to add several builtin plugins, such as basic type checking, but that will come at a later date.

Code-gen improvements
One of Urn's biggest failings right now is that it doesn't generate very readable or idiomatic Lua. Whilst we are never going to be perfect, this release has seen several improvements in the emitting of conditionals. For instance, 4 line if statements are now reduced to a single line and or or.

We've also extended the cases where directly-called-lambdas are inlined. Before it would only inline functions which were called with constant terms. Now we will inline any time we can guarantee the execution order of expressions will not be changed. For instance:

local msg3 = _2e2e_2("Expected ", arg12["var"], " after --", key6, ", got ", (function(xs15, idx5)
	return xs15[idx5]
end)(args3, idx3))

would not have been inlined before as idx3 is rebound elsewhere. Thanks to this optimisation, we now emit:

local msg3 = _2e2e_2("Expected ", arg11["var"], " after --", key6, ", got ", args3[idx2])

as expected. This has halved the number of directly-called-lambdas in the code base.

Over all, the code gen improvements have resulted in a 600 line reduction in the compiled compiler. Other files have seen similar reductions (urn/traceback went from 246 lines to 212).

Changelog
Libraries

• [@SquidDev] Add compiler plugin API
• [@Lignum] Add struct->list.

CLI

• [@demhydraz] Add –exec task, which reads in a program from stdin and executes it.
• [@SquidDev] Escape illegal identifiers in the gen-native task.

Optimiser / Codegen

• [@SquidDev] Include line numbers when dumping invalid sources
• [@SquidDev] Remove set! when its definition is destroyed.
• [@SquidDev] Simplify lambdas which are designed to avoid multiple-return values
• [@SquidDev] Inline directly called lambdas where execution order will not be modified
• [@SquidDev] Don't emit empty else blocks.
• [@SquidDev] Simplify conditionals where the result is only a boolean.

Because Urn updates are like London busses: you have to wait for ages, then several come at once.

Multiple returns from macros and top level unquotes.
This has been on the todo list for an age, and I've finally got round from it. One of the biggest limitations of macros was that they could only return one value, meaning anything which needed to define multiple variables wouldn't work. As of this release, you can return multiple values from these, meaning multiple pieces of code can be spliced in. This commit also allows passing multiple values to top-level unquotes, as well as also allowing top-level unquote-splices. For instance:

,@(list
	  `(define foo ,(* 2 3))
	  `(define bar ,(+ 2 3))

will now evaluate the body of the unquote splice, and push it in, resulting in

(define foo 6)
(define bar 5)

It is worth noting that multiple returns can only be used in blocks (lambda and conditional bodies).

Code-gen improvements
I won't re-iterate previous posts about code-gen issues, but this release has also seen significant code-size reductions (about 780 LOC). We've grown even smarter about detecting various conditional expressions, meaning complex, multi-line if statements can be reduced to a single line. You only need to look at the first line of the diff to see how effective this optimisation is. Looking over the compiled code, I feel we've reached the point where the emitted code isn't high quality, but it is acceptable. We've come away since the initial release.

Full Changelog
Libraries

• [@SquidDev] Fix `struct` and friends not checking argument length.

Compiler

• [@SquidDev] Allow multiple returns from top level unquotes and macros.
• [@SquidDev] Allow `unquote-splice` to be used in the top level, as well as `unquote` accepting multiple arguments.

Optimiser / Codegen

• [@SquidDev] Don't simplify `cond`s where the test symbol is mutated.
• [@SquidDev] Improved compilation of and/or in non-conditional contexts.

It's update time! Now with even more meta-programming.

Querying variables at compile time.
In addition to being able to add your own optimisation and analysis passes, we've also added the option to query the current context from macros and unquotes. This allows a way to dynamically query variable names, values and definitions at compile time. For instance, given:

(defun foo () (print! "Hello") 23)

we can then query foo using several methods from the compiler/resolve package.

,(with (var (var-lookup 'foo)) ;; Lookup the variable in the "active scope".
   (print! "Definition" (pretty (var-definition var))) ;; Print the variable's definition.
   (print! "Value" (pretty (var-value var))) ;; Print the variable's value
   (print! "Call" (pretty ((var-value var))))) ;; Print the result of calling the variable.

Collections 0.1
This is, as clearly evidenced by the lack of previous releases, the first release of the collections library. urn/collections is a collection (pun intended) of useful data structures and supporting architecture. While this version does not have many data structures, it does present a great leap forward in the supporting architecture area.

Namely, this release includes two much-needed critical bits of functionality, namely algebraic data types (algebraic.lisp) and lenses (lens.lisp).

Algebraic data types are a nice abstraction for presentation and decomposition of structured data, and, since they’re implemented as a relatively thin layer over lists, they are performant and compatible: namely, no modification has been needed for the standard library pattern matching system to support these ADTs.

Lenses are, basically put, purely-functional, composable getters and setters on steroids. You can use them to zoom into (pun intended, again) a bit of a data structure and potentially change it (or apply a function to it.)

Additionally, there’s rudimentary support for lazy sequences, but those haven’t been integrated with either ADT or lenses.

Codegen improvements
There are also been a couple of minor optimisation and codegen improvements, fixing a couple of bugs, and reducing code size very slightly. For instance, this see these lines were reduced to a single if statement. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla ipsum dolor, mattis vel nisl vitae, condimentum sollicitudin ex. Duis quis dui nec est facilisis rhoncus. Suspendisse potenti. Cras massa tellus, viverra in maximus non, maximus nec odio.

Full Changelog
Libraries

• [@demhydraz] Add pattern matching lambdas
• [@SquidDev] Add the ability to query the current compiler state/scope
• [@demhydraz] Add reify.
• [@demhydraz] Add sym…

Optimiser / Codegen

• [@SquidDev] Ensure the condition is an expression for and/or terms.
• [@SquidDev] Improve visiting of nodes inside expression-fold. This results in slightly smaller code sizes for directly called lambdas involving conditions.

Another update! Firstly, about Urn itself: someone posted a link to Urn's repo on Reddit, which meant we got lots of useful feedback from various people.

Struct literals
I finally caved in and added "struct literals". This means the compiler now has the notion of a table built in to it, and so can generate more efficient code. It also makes your code a significantly prettier:

(with (obj { :name "Bertie"
                  :age 23 })
  (print! (.> obj :name)))

Compiler improvements
We've put some work into making the compiler easier to work with. Firstly, if you attempt to use an undefined variable, we'll now suggest variables in scope with similar name. This makes it much easier to see when you've got a typo.


We've also improved multi-line support in the REPL. If Urn detects that an expression isn't finished, it will automatically prompt for another line: meaning you input complex expressions with ease.



Full Changelog

Libraries

• [@demhydraz] Remove const-struct and empty-struct.
• [@demhydraz] Add active-module and scope-vars.
• [@demhydraz] Add apply.
• [@demhydraz] Make map have a variable number of arguments.
• [@demhydraz] Rename nil? to empty?, and use nil? to check for nil-ness.

CLI

• [@SquidDev] Improve REPL's mulit-line support.

Compiler

• [@SquidDev] Add `struct-literal` builtin, allowing defining tables.
• [@SquidDev] Suggest similar names variables when a symbol cannot be resolved.
• [@SquidDev] Minor lexer fixes.

Codegen

• [@SquidDev] Fix `and` and `or` including statements.

It's a little earlier than normal, but it's still update time.

New documentation
This isn't very exciting, but we've re-done a fair bit of documentation, adding explanations on syntax and special forms, as well as more tutorials on Lua interop and the compiler API & plugin system.

General recursion helper
demhydraz has been working on a whole range of improvements to the standard library. One of these is the new loop construct. This makes it possible to define a tail-recursive construct without an explicit letrec: Instead of calling yourself, you call recur. For instance, here is a naive way to reverse a list:

(loop [(o '())
	   (l '(1 2 3))]
  [(empty? l) o]
  (recur (cons (car l) o) (cdr l)))

Full changelog
Libraries

• [@demhydraz] Ensure pattern metavars are only seen once.
• [@demhydraz] Add flat-map.
• [@demhydraz] Add a general recursion helper (loop).
• [@demhydraz] Deprecate traverse.
• [@demhydraz] Remove assert.

Compiler

• [@SquidDev] Add ability to mark symbols as deprecated.
• [@SquidDev] Fix –gen-native generating invalid code when using strange prefixes.
• [@SquidDev] Warn when links in docstrings are invalid.

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. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras a varius leo, at ultricies dolor. Aenean purus urna, pulvinar eget lobortis nec, rhoncus eu dolor. Fusce vulputate arcu sit amet. 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))

Full Changelog
The full changelog can be viewed 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 by far from an ideal time, and so we will continue to make further improvements to the optimiser and code generation.

Full Changelog
The full changelog can be viewed on the GitLab repo.

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 Lignummn for their additions to the standard library.

You can read the full changelog on the GitLab repo.

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!

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.
Goodby 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 and (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.

Updates my dears, and not a moment too soon. It's been 100 commits since our last release, and each commit is packed with lispy goodness. OK, maybe not every commit. In this time, we've reached 1000 commits which, whilst a rather arbitrary milestone, it still a milestone we can celebrate. There's been more changes than I can cover here, so I'd really recommend checking out the release nodes for the whole picture. Anyway, here's a small summary of what's new:

Multimethods (aka defgeneric)
Whilst Urn prides itself on the extensible power that macros offer, the extensibility of the standard library has historically been lacking. There are several functions which do a long if-elseif chain of type comparisons, with a final metatable lookup if all else fails. This is obviously undesirable and so something needed to be done. Enter multimethods.

If you've used an object oriented language such as C++ or Java then you will have used methods before, and so multimethods will not be an entirely alien concept. However, instead of dispatching based on the type of the first argument, it uses all arguments to determine which function to call. This makes multimethods a much more powerful solution.

In order to demonstrate their power, we'll create a generic merge method. This'll attempt to merge two objects together and return the resulting object. First we define a new method with defgeneric, providing our argument names and a docstring:

(defgeneric merge (x y)
  "Merge X and Y together, returning a new object.")

We can now call merge, but we'll just get an error. After all, we haven't defined any implementations yet. This is done with defmethod, specifying the argument types and an implementation. Let's do a couple of simple ones:

(defmethod (merge string string) (x y) (.. x y))
(defmethod (merge list list) (x y) (append x y))

Now let's use these:

> (merge "foo" "bar")
out = "foobar"
> (merge '(1 2 3) '(4 5 6))
out = (1 2 3 4 5 6)

Of course, if you've got a fancy structure which can be merged, its trivial to add support for that too. We've made great use of this feature in the standard library, converting pretty and eq? to use it.

I'd really recommend reading hydraz's blog for more information about this feature. He's the one who wrote it, and goes into much more detail about the implementation and rational behind it. Now's when I'd normally insert a cynical comment about no-one getting this far, but it's late and there are plenty more features to cover…

Fancy structures
One of the gems of Lua is it's table. This simple data structure forms the base of many of Urn's standard types. However, using passing around tables and indexing them via strings does rather take the idea of abstraction and smash it on the floor. We've written the urn/struct library to provide a more intuitive way to create your own data structures.

This library provides the defstruct macro. This provides a small DSL which allows you to declare fields, constructors and more. This will, in turn, generate the appropriate constructor, getters, setters and pattern matching utilities. Sounds great? Well let's jump in and declare the struct staple - a point.

(defstruct point
  (fields
    (immutable x)
    (immutable y)))

(defmethod (pretty point) (p)
  (string/format "(x=%d y=%d)" (point-x p) (point-y p)))

This structure definition will create a constructor (make-point) and a type predicate (point?). Each field definition will specify an argument to the constructor and a getter. If the field is marked as mutable, then a setter will also be generated. We also chuck in a pretty implementation for good measure.

Now we can start constructing points, indexing their fields and printing them:

> (point 1 2)
out = (x=1 y=2)
> (point-x (make-point 1 2))
out = 1
> (point-y (make-point 1 2))
out = 2

If you don't like these function names, then customising them is trivial. One can also make particular fields hidden package-local, if you have implementation specific fields. See the documentation for more information.

Testing, coverage and stability
All these new features a awfully nice, if we don't have any guarantees they actually work correctly. That's why we've spent a lot of time getting our testing infrastructure up to date. I won't go into the details as frankly, it isn't that interesting but here's a couple of highlights:

Example testing
The Urn documentation is full of example usage for various functions, complete with inputs and outputs. These examples are perfect for a trivial test case, to ensure the basic functionality is there. To make best use of these examples, we've written a compiler plugin which extracts codeblocks from docstrings and runs them, verifying the output is as expected.

Whilst I'm not proposing doing away with normal tests - after all, you don't want to include every edge case in an example - they are a small step in making sure Urn is fully tested. Furthermore, it allows us to ensure all examples are up to date, and provides an incentive to write more documentation - always a plus.

Code coverage
Tests are great for seeing what works, but it's much harder to find what doesn't work. One way to help with this is to determine what the test suite doesn't check. And so, of course, we've written a small code coverage utility for Urn. It generates files in the same format as LuaCov, and so provides some interpobility with other Lua-based tools. To get started, just run your code with the –profile=coverage switch.

Codegen and optimiser improvements
Normally I'd bang on about the most exciting optimisation changes this release. However, for better or for worse, there haven't been many major changes. Instead, there's been a lot of work on stabilising the various systems, resulting in a less buggy and more consistent experience. Whilst it's far from perfect, we're one step closer to not blowing up in your face the whole time.

We've just released another Urn update - 0.5.1. This is a relatively small update, mostly composed of bug fixes and performance improvements. That's not to say there aren't some useful new features though!

REPL improvements
The Urn REPL is a great tool for testing and prototyping code. It's something we regularly use, and so are always eager to improve it.

One task we often find ourselves doing is loading up the REPL, importing a module and testing a small feature in it. This process has now been streamlined: when using the –repl flag, any file provided on the command line will be automatically imported into the current scope.

We've also added a :view command, which allows you to preview a symbol's definition. This saves you switching between source code and the REPL, trying to remember how you got that awesome feature to work.



Optimised optimiser
The Urn compiler has never been the fastest beast, with the optimiser being the worst offender. Whilst the optimiser is great at reducing the size (and speed) of generated code, it also takes considerable time to run. Even worse, much of the optimiser's time was just spent in iterating over every node - not even running the various passes! Something had to be done.

Urn 0.5.1 introduces a new framework for optimisations, doing something so obvious I'm surprised we weren't doing it from the start. Instead of running each pass sequentially, we have one unified visitor object which will call each pass for every node it hits. Not only does this substantially reduce the visitor overhead, it reduces the number of times we have to run a pass, resulting it in an even bigger performance increase! We've also made some improvements to definition and usage tracking, which ensures that the information is more up-to-date, and so the optimiser can make smarter decisions.

These various improvements have resulted in a 2-3x performance increase in the optimiser (depending on Lua version and implementation). In fact, it now takes less time to optimise the compiler than it does to load it. There is evidently room for performance improvements elsewhere!

Wow, it's been a while since the last update. During that time, we've been doing a lot of work on the standard library. So let's dig right in an see what's changed.

Standard library restructuring
Urn's standard library has always been a bit of a mess, with features scattered everywhere. Whilst some chaos is inevitable due to having to bootstrap the library, there was still lots of improvement. Sadly, deciding on a good approach proved more complicated than expected.

For Urn 0.6 we finally went about this restructuring, splitting Urn into several modules such as core (for bootstrapping the stdlib), data (data manipulation libraries) and test (used for writing tests). It's worth noting that some programs may need changing to work with the new layout, but rest assured we won't be changing it again any time soon.

Extended math library
Lisp has always had a history of numerical computing, and Urn does not disappoint. 0.6 adds support for rationals, complex numbers, vectors and matrices. It's now that much simpler to do your maths homework in Urn!

In order for these features to work fluidly together, we've added a collection of generic arithmetic methods, such as n+ and n* which operate on arbitrary data structures. These methods, along with rational literals, bring a lot to the table.

> (import math/vector ())
> (n* (vector 1 2 3) 2/3)
out = [2/3 4/3 2/1]

String formatting changes
hydraz has done a lot of work on developing more powerful ways to format strings. Whilst string/format is useful, it can still be tedious to use. Thankfully the data/format library accepts format strings which neatly integrate with pretty printing, as well as allowing keyword arguments and interpolation of symbols in the current scope. I'd really recommend checking out the documentation for more information.

> (format nil "0x{foo%x}" :foo 123)
out = "0x7b"

Internal changes
Whilst the obvious changes have occurred within the libraries, the compiler's internals have also changed. Aside from improved codegen, line mappings are now substantially more accurate. Consequently code coverage and error messages are more informative - always a perk when debugging!

Normally I start these update posts with some comment about how much has changed, or how long it's been since the last one. Sadly, I can't think of anything to say so let's just jump right into some key changes:

Method improvements
Methods are a really powerful way of writing functions which can handle all sorts of data types. That being said, they are not without their problems and so we're always working to improve them. One issue is the large increase in code size that using methods results in. In Urn 0.6.1, we've tried to lower that overhead, resulting in even smaller files!

Alongside with that, we've also added the ability to specify wrappers within methods. Every call to your method will go through this delegate, allowing one to provide specialist logic. This is used by the eq? method to check using the == operator before trying anything else.

(defgeneric eq? (x y)
  "Compare values for equality deeply."
  :delegate (lambda (x y)
              (if (= x y)
                true
                (myself x y))))

Code generation and optimisation tweaks
Interestingly enough, method delegates exposed several places where code generation could be further improved. One such improvement was forcing bindings to be generated as local definitions rather than directly called functions. This makes code more readable and potentially allows further improvements as statements can be emitted more sensibly. For instance, consider the following code:

(print!
  (with (foo (if (empty? '()) 1 2))
    (+ 1 foo)))

here's how it would be compiled on 0.6.0:

return print1(1 + (function(foo)
        return foo
end)((function()
        if empty_3f_1({tag="list", n=0}) then
                return 1
        else
                return 2
        end
end)()))

and here's the equivalent code on 0.6.1:

return print1(1 + (function()
        local foo
        if empty_3f_1({tag="list", n=0}) then
                foo = 1
        else
                foo = 2
        end
        return foo
end)())

Another interesting optimisation we now apply is lowering "deferrable" variables. For instance, consider this definition:

(with (foo '())
  (when (empty? '())
    (debug foo)))

The definition of foo is only needed if then when block is executed, and so we're able to "push" the definition down:

(when (empty? '())
  (with (foo '())
    (debug foo)))

Whilst this code doesn't appear much in practice (or at least in this overly simplistic form), it's nice to catch the few occasions where it does.

How time flies. It's been almost three months since the last Urn release, and a whole year since the first one. I can't say there's one "super exciting" feature in this update, but instead there's been many small improvements to the standard library and internals.

Configurable assertions
Often when I write Urn (or any other language for that matter), I find myself needing debug assertions. Namely, assertions which can be enabled at development time or disabled when I need to eck out every last bit of performance. Urn now has built-in support for this, thanks to the demand and desire macros.

Both of these macros take a value which must be upheld and, optionally, an error message which will be displayed if it is not.

> (defun negate (a)
.   (demand (number? a) "a must be a number")
.   (* a -1))

> (negate false)
[ERROR] demand not met: (number? a) (a must be a number).

stack traceback:
  lib/core/demand:29-31: in global 'demand-failure'
  <stdin>:2: in global 'negate'
  <stdin>:1 in main chunk

The difference between the two is when the assertions are enabled. demand is enabled by default, being disabled by passing -flax-checks to the compiler. Conversely, desire is disabled by default, with -fstrict-checks enabling such assertions.

Utilising a similar mechanic, one can also use -fstrict-structs to add typechecks to struct getters and setters. This will ensure the target is a struct of the expected type, preventing you from passing modifying unknown values.

You can enable all "strict" checks with the -fstrict flag, and disable all normal checks with -flax. Note that -flax arguments take precedence over their strict equivalents.

Rewritten native bindings
Interacting with Lua has always been a bit of a tricky thing with Urn. Whilst things have changed several times over the various Urn releases, we've never really hit a "sweet spot". That being said, the latest redesign is substantially closer than we've got before.

Previously, one would define a .meta.lua file, which defined how various native definitions worked: whether they were some piece of Lua syntax, or a binding to an arbitrary Lua expression: whether they were some piece of Lua syntax, or a binding to an arbitrary expression. Whilst we are still sticking with this concept, all of these declarations have moved inline with the main define-native file.

This makes things a little cleaner (as we no longer need multiple files) and allows for dynamically generating definitions at compile time.

Compiler cleanup
As the Urn compiler is almost as old as Urn itself, most of it was written without access to some of the more recent features. One of the ways this is most apparent is how raw Lua tables and indexes are used for every structure, meaning you have no clue what (.> x :name) is referring to. Additionally, it makes it awfully easy to misspell field names, or set the correct field on entirely the wrong object.

This Urn release makes great strides in "sturdying-up" the compiler, converting many of the data structures to use defstruct. Not only does this provide better type safety, it also makes it much easier to read and write documentation on specific fields.

REPL reloading
One of the workflows I often rely on is loading files into the REPL, checking functions work as expected, and then modifying the files if not. Sadly, each time you change the file, you need to restart the REPL, meaning you have to start from scratch. This release adds the :reload (or :r) command to the REPL. This will scan all loaded modules, determine which ones have changed, recompile them. This means you can add or remove features without ever having to leave the comfort of Urn.

We've also rewritten the online REPL, using lua.vm.js to run the Urn compiler in the browser. This should make things more responsive (and removes the need to rely on friends' servers). Many thanks to RawGit for their GitHub CDN service, which is used to fetch the standard library.

Do note that this is just a snapshot of the changes included in this release of Urn. Do check the full changelog or peruse the docs for more information.