Awl

Lisp: from late Old English awlyspian, meaning “to lisp.”

Awl is an experimental mini-language based on the Lisp family of programming languages.

Synopsis

It was written for fun and profit to learn more about interpreter design, programming in C, and using emscripten to transpile to JavaScript.

Note: This naturally goes without saying, but Awl is just an experimental learning project, which means that it is lacking in thorough testing and probably has many bugs. It should not be used for production code, lest it summon Undefined Behavior™ upon you.

That being said, experimenting and hacking on non-production-ready code just for fun can be worthwhile!

Examples

Here are a few examples that briefly demonstrate some of Awl’s features.

Math:

; Math example
;;

(func (mean l) (/ (sum l) (len l)))

(func (variance l)
    (let ((mu (mean l)))
        (/
            (sum (map (fn (x) (^ (- x mu) 2)) l))
            (len l))))

(define xs {1 2 3 4 5 6})
(println (mean xs)) ; prints 3.5
(println (variance xs)) ; prints 2.916

Recursion:

; Recursive cycle
;;

(func (cycle xs)
    (let ((f (fn (n)
        (let ((i (% n (len xs))))
            (cons (head (slice xs i (+ i 1)))
                  (list (fn () (f (+ n 1)))))))))
        (fn () (f 0))))

(define xs {1 2 3 4})
(println ((cycle xs)))
(println ((head (tail ((cycle xs))))))

Mergesort:

; Merge sort
;;

(func (merge-sort l)
    (if (<= (len l) 1)
        l
        (let ((middle (// (len l) 2))
              (left (slice l 0 middle))
              (right (slice l middle))
              (left-sorted (merge-sort left))
              (right-sorted (merge-sort right)))
            (merge left-sorted right-sorted))))

(func (merge l r)
    (if (nil? l)
        r
        (if (nil? r)
            l
            (let ((hl (head l))
                  (hr (head r)))
                (if (< hl hr)
                    (cons hl (merge (tail l) r))
                    (cons hr (merge l (tail r))))))))

(println (merge-sort {4 3 2 1}))
; prints -> {1 2 3 4}

(println (merge-sort {54 83 1274 83 74 218 9}))
; prints -> {9 54 74 83 83 218 1274}

Compiling

Most of Awl’s dependencies are included in the repository, so you shouldn’t need to install anything other than the build tools. Awl takes advantage of some new features in C11, so you will need a fairly recent C compiler.

• Both clang (tested with version 3.5.0) and gcc (tested with version 4.7.2) are known to successfully compile
• You’ll need make
• To transpile to JavaScript, you’ll need the emscripten toolkit, including emcc.
• To minify the output JavaScript from emscripten, you’ll need uglifyjs, but it isn’t strictly necessary.

First, clone the repository, and then compile using make:

$ git clone https://github.com/voithos/awl.git
$ cd awl
$ make

This will create an awl binary under bin/.

You can also compile and execute tests:

$ make test

Or transpile to JavaScript (emcc will need to be in your $PATH):

$ make web

Clean up if you want to start over:

$ make clean

Usage

The awl binary can take a single argument - a path to a file to execute.

$ ./bin/awl [file]

If no argument is given, then it will drop into an interactive interpreter (REPL):

$ ./bin/awl
awl v0.x.y
Ctrl+D to exit

awl>

Features

Awl is a mini-language that is inspired by the Lisp family of languages. Thus, it shares most of its features with Lisp and Scheme. These include:

• Dynamic typing
• First-class functions, including anonymous (lambda) functions
• Function closures
• Partial application
• Tail-call optimization
• Data immutability
• Lists as the primary data structure
• Homoiconicity - that is, similar representations of code and data
• Metaprogramming in the form of simple macros

Currently, Awl’s data definition and manipulation capabilities are lacking, but this will hopefully be changed in the future.

Language Reference

Awl is an expression-based language. Basically everything is an expression, and can be arbitrarily nested. A program consists of a sequence of such expressions.

Basic Features

Awl supports inline comments using semicolons (;):

; Can go on its own line
(func (plus-one x)
    (+ x 1)) ; Or at the end of a line

Printing to standard output can be done using print and println:

awl> (println "Hello sekai!")
Hello sekai!

Variables are created with define (which affects the local environment) and global (which, as the name suggests, affects the global environment):

awl> (define foo 'bar')
awl> (println foo)
bar

Primitive Data Types

Expressions

Function calls in Awl are defined as S-Expressions (symbolic expressions). They are syntactically enclosed in parentheses (). The first argument of the expression must be a callable, and is evaluated in the current environment with any following arguments as parameters (this is the iconic “Polish notation” of Lisp).

awl> (+ 5 6)
11
awl> (println 'foo')
foo

When evaluating user-defined functions, partial application is done automatically for any unfilled arguments (this is currently not done for builtins). This makes it easy to use higher-order functions quickly:

awl> (define xs {1 2 3 4})
awl> (define square (map (fn (x) (* x x))))
awl> (square xs)
{1 4 9 16}

Variable and function identifiers, called “symbols,” are evaluated to the values that they map to, except in certain special forms (e.g. when they are being defined):

awl> (define x 5)
awl> (+ x 6)
11

The primitive types evaluate to themselves.

Q-Expressions (quoted expressions, often referred to simply as ‘lists’) are particularly important. They are enclosed inside curly braces {}. They are a collection type and behave similar to lists in other languages. They can store any number and mixture of primitive types. And they have one more important ability: expressions that they contain which would normally be evaluated, such as symbols and S-Expressions, are left unevaluated (i.e. they are “quoted”). This allows them to contain arbitrary code, and then be converted and evaluated as S-Expressions:

awl> (head {1 2 3})
1
awl> (tail {1 2 3})
{2 3}
awl> (define x {* 3 (+ 2 2)})
awl> x
{* 3 (+ 2 2)}
awl> (eval x)
12

There are a few more expression types that are useful in special cases.

E-Expressions (escaped expressions) are denoted with a preceding backslash \, and can be used to specifically evaluate a section within a Q-Expression literal:

awl> {1 2 (+ 2 1)}
{1 2 (+ 2 1)}
awl> {1 2 \(+ 2 1)}
{1 2 3}

C-Expressions (concatenating expressions) are denoted with a preceding at-sign @. They behave similarly to E-Expressions, with the exception that, when given a list (Q-Expression), they “extract” the contents and include it directly in the outer list:

awl> {1 2 \{3 4}}
{1 2 {3 4}}
awl> {1 2 @{3 4}}
{1 2 3 4}

Finally, there is another collection type that is slightly more mundane than Q-Expressions and their ilk: Dictionaries. Dictionaries act as simple key-value stores, and are similar to the dictionaries in other languages. They are delimited with square brackets [], use Q-Symbols as their keys, and can store any normal value:

awl> (dict-get [:foo 12 :bar 43] :foo)
12
awl> (dict-set [:x 1 :y 2] :z 3)
[:'x' 1 :'y' 2 :'z' 3]

Builtins

Builtins usually behave like normal functions, but they also have the special role of enabling some of Awl’s basic features, since they are written in C (for example, the fn builtin creates a new anonymous function).

Awl makes no distinction between “operators” (+, -, *) and other kinds of builtins - they are simply named differently.

Core Library

In addition to builtins, there exists a core library that Awl imports on startup. Among other things, this library aims to exercise some of Awl’s features, as well as provide some basic functional tools.

Open Source

Many thanks goes to the following awesome libraries and open source projects, and their creators:

• mpc.c
• ptest.c
• linenoise
• clang / LLVM
• emscripten
• JQuery Terminal

Also, thanks goes to the creator of the free “Build Your Own Lisp” online book, which is what Awl was inspired from.