Sel – Sed Lisp
Have you ever wished you had a functional programming language, but all you had was GNU coreutils?
Wish no more, with Sed Lisp a Lisp interpreter in sed
.
Quick start
$ make sel.sed
$ ./sel.sed <<EOF
val main (print "Hello, World!")
EOF
Hello, World!
The language
Example
; Comments are ;
; Define values with val
val nil ()
; Write functions by quoting the function body, or with the func keyword
; The list function just returns its arguments
func list (args)
; ^^ syntactic sugar for val list (quote (args))
; usage: (foreach function list)
func foreach (
(if (cadr-args) ; conditions are true if non-nil
(nil
((car-args) (caadr-args))
(foreach (car-args) (cdadr-args))
)
; If the list is nil, do nothing
nil
)
)
val main (foreach print
(list
"a warm greeting"
"from sed lisp"
)
)
Run with:
$ make sel.sed
$ ./sel.sed example.sel
a warm greeting
from sed lisp
Datatypes
There are four basic datatypes:
- Cons cells
- Strings
- Builtins
- Nil
Evaluation
Everything is eagerly evaluated, unless it is quoted ((quote (whatever))
).
In a list, each item is evaluated left-to-right, and then the head of the list is run with the tail as its arguments.
Within a function, you can get the args using the args
or c[ad]+r-args
builtins.
Builtin functions
There are an infinite number of builtin functions:
-
quote
: returns its first argument without evaluating anything -
args
: gets the arguments to the function -
print
: outputs its first argument, a string -
if
:(if cond a b)
doesb
ifcond
isnil
, anda
otherwise -
c[ad]+r
: standard Lispcar
,cdr
,cadr
, etc, but with an unlimited number ofa
's ord
's -
c[ad]+r-args
:(car-args)
is equivalent to(car (args))
, but faster and easier -
cons
: creates a new cons cell -
eq?
: returns truthy if the args are equal -
str-concat
: concatenates all of its arguments, which should be strings -
str-concatl
: concatenates a list of strings -
str-reverse-concat
: concatenates all of its arguments, which should be strings, in reverse order -
str-reverse-concatl
: concatenates a list of strings, in reverse order -
digit-add
: add two digits, giving a cons cell(bool carry, digit sum)
-
digit-add-carry
: add two digits + 1, giving a cons cell(bool carry, digit sum)
-
digit-lte?
:(digit-lte? x y)
returns truthy if x ≤ yNote that
digit-add
,digit-add-carry
, anddigit-lte?
only work if you%include arith.sel
in your program
Dynamic symbol lookup and scope
There is no dynamic symbol lookup, and no scope.
Code is run in two steps:
-
Parsing and name resolution. (File:
parser.sed
)The result is a collection of cons cells, strings, and builtins, with no names attached.
-
Actually running it. (File:
runner.sed
)
Mutability and memory management
Also none. Everything is fully immutable, and all data is leaked.
However, it's not as memory-inefficient as that makes it seem: everything (strings, builtins, and even cons cells) is interned.
Arithmentic
You can do arithmetic, too! See arith.py
for an explanation of how it works, and fibonacci.sel
for an example.
It boasts AFAIK the fastest sed implementation of recursive fibonacci ever written:
$ time ./sel.sed fibonacci.sel
(fibonacci 10) is 55
real 1m53.091s
user 1m46.753s
sys 0m6.225s
The implementation
It's MIT licensed, so you're free to use/modify/etc it. Not sure why you'd want to, though.
Requires GNU sed. Tested with GNU sed 4.8.
It's also blazing fast. The example program test-prog.sel
performs multiple list traversals in under a second half a second!
$ time ./sel.sed test-prog.sel
sed lisp says: Check it out!
sed lisp says: Now with more recursion
sed lisp says: https://github.com/mb64/sel
real 0m0.476s
user 0m0.454s
sys 0m0.021s
It's in two parts, the parser and the runner. They're designed such that they can be run (and debugged) independently:
$ sed -E -f parser.sed input.sel > input.sec # sec for SEL Compiled
$ # OR
$ make input.sec
$ sed -nE -f read-all.sed -f runner.sed input.sec
See notes.txt
for some design notes.