Lurk is a Lisp
Since Lurk is a Lisp, it has practically no syntax and expressions can be formed with simple rules.
The expression 3
is self-evaluating.
lurk-user> 3
[1 iteration] => 3
When an expression is evaluated, you should see a response with the result and an iteration count, in this case, 1. You can think of this as representing the "cost" or number of "clock cycles" required to evaluate the expression. In the simplest case of a self-evaluating expression, only a single iteration is required.
Characters and strings are also self-evaluating.
lurk-user> 'a'
[1 iteration] => 'a'
lurk-user> "abc"
[1 iteration] => "abc"
Lists are evaluated by treating the first element as an operator and the rest as operands.
lurk-user> (+ 2 3)
[3 iterations] => 5
An operator can be either a built-in operator or an expression that evaluates to a function (more on this later).
A list whose first element is neither a built-in operator nor evaluates to a function yields an error when evaluated.
lurk-user> (1 2 3)
[2 iterations] => <Err ApplyNonFunc>
nil
and t
nil
and t
are self-evaluating symbols.
lurk-user> nil
[1 iteration] => nil
lurk-user> t
[1 iteration] => t
nil
carries the semantics of "false".
lurk-user> (= 1 2)
[3 iterations] => nil
lurk-user> (if nil 1 2)
[3 iterations] => 2
t
carries the semantics of "true".
lurk-user> (= 1 1)
[2 iterations] => t
lurk-user> (if t 1 2)
[3 iterations] => 1
More on lists
Pairs are constructed with cons
, and their elements are separated by a .
when printed.
lurk-user> (cons 1 2)
[3 iterations] => (1 . 2)
A pair whose second element is nil
is said to form a list with one element.
lurk-user> (cons 1 nil)
[3 iterations] => (1)
Note that nil
is elided when printing lists.
We can left-expand this list by consing an element as its new head.
lurk-user> (cons 0 (cons 1 nil))
[5 iterations] => (0 1)
Thus, within this design, nil
can be used to represent the empty list.
To deconstruct a pair, we can use car
and cdr
, which return the first and the second element respectively.
lurk-user> (car (cons 1 2))
[4 iterations] => 1
lurk-user> (cdr (cons 1 2))
[4 iterations] => 2
And in our abstraction of lists, we say that car
and cdr
return the list's head and tail respectively.
lurk-user> (car (cons 0 (cons 1 nil)))
[6 iterations] => 0
lurk-user> (cdr (cons 0 (cons 1 nil)))
[6 iterations] => (1)
By definition, (car nil)
and (cdr nil)
return nil
.
lurk-user> (car nil)
[2 iterations] => nil
lurk-user> (cdr nil)
[2 iterations] => nil
Functions
A Lurk function can be created by using the lambda
built-in operator, which requires a list of arguments and a body.
lurk-user> (lambda (x) (+ x 1))
[1 iteration] => <Fun (x) ((+ x 1))>
Then we can write function applications by using lists, as mentioned before.
lurk-user> ((lambda (x) (+ x 1)) 10)
[6 iterations] => 11
Functions with multiple arguments follow the same input design.
lurk-user> ((lambda (x y) (+ x y)) 3 5)
[7 iterations] => 8
Variadic functions are supported by adding &rest <var>
at the end of the arguments list, which binds a list of all remaining parameters to <var>
.
lurk-user> ((lambda (&rest x) x))
[3 iterations] => nil
lurk-user> ((lambda (&rest x) x) 1 2 3)
[6 iterations] => (1 2 3)
lurk-user> ((lambda (x y &rest z) z) 1 2 3)
[6 iterations] => (3)
lurk-user> ((lambda (x y &rest z) z) 1 2)
[5 iterations] => nil
Lurk supports partial applications, so we can apply arguments one by one if we want.
lurk-user> (((lambda (x y) (+ x y)) 3) 5)
[8 iterations] => 8
A function may also be defined to not need any arguments.
lurk-user> (lambda () nil)
[1 iteration] => <Fun () (nil)>
lurk-user> ((lambda () nil))
[3 iterations] => nil
Note that the second expression actually calls the function.
Functions can also be recursive and call themselves by their names. But how do we name functions?
Bindings
We'll come back to recursive functions in a bit.
First, let's see how let
allows us to introduce variable bindings.
lurk-user> (let ((a 1)) a)
[3 iterations] => 1
let
consumes a list of bindings and the final expression, which can use the introduced variables (or not).
lurk-user>
(let ((a 1)
(b 2)
(c 3))
(+ a b))
[7 iterations] => 3
When defining the value bound to a variable, we can use the variables that were previously bound.
lurk-user>
(let ((a 1)
(b (+ a 1)))
b)
[6 iterations] => 2
Later bindings shadow previous ones.
lurk-user>
(let ((a 1)
(a 2))
a)
[4 iterations] => 2
And inner bindings shadow outer ones.
lurk-user>
(let ((a 1))
(let ((a 2)) a))
[5 iterations] => 2
Now we can bind functions to variables.
lurk-user>
(let ((succ (lambda (x) (+ x 1))))
(succ 10))
[8 iterations] => 11
So, can we create a looping recursive function yet?
lurk-user>
(let ((loop (lambda () (loop))))
(loop))
[6 iterations] => <Err UnboundVar>
In a let
expression, free variables are expected to be already available by, for instance, being defined on a previous binding.
If we try to call loop
when defining loop
, it will be unbound.
lurk-user>
(let ((not-a-loop (lambda () 42))
(not-a-loop (lambda () (not-a-loop))))
(not-a-loop))
[8 iterations] => 42
In the example above, the body of the second binding for not-a-loop
simply calls the previous definition of not-a-loop
.
If we want to define recursive functions, we need to use letrec
.
lurk-user>
(letrec ((loop (lambda () (loop))))
(loop))
Error: Loop detected
And now we can finally write a recursive function that computes the sum of the first n
numbers.
lurk-user>
(letrec ((sum-upto (lambda (n) (if (= n 0)
0
(+ n (sum-upto (- n 1)))))))
(sum-upto 5))
[55 iterations] => 15
Higher-order functions
Lurk supports Higher-order functions. That is, Lurk functions can receive functions as input and return functions as output, allowing for a wide range of expressive functional programming idioms.
lurk-user>
(letrec ((map (lambda (f list)
(if (eq list nil)
nil
(cons (f (car list))
(map f (cdr list))))))
(square (lambda (x) (* x x))))
(map square '(1 2 3 4 5)))
[78 iterations] => (1 4 9 16 25)
By the way, how was the list (1 2 3 4 5)
produced so easily?
Quoting
The quote
built-in operator skips the reduction of its argument and returns it as it is.
We've seen that trying to reduce (1 2 3)
doesn't work.
But if we want Lurk not to face that list as a function application, we can use quoting.
lurk-user> (quote (1 2 3))
[1 iteration] => (1 2 3)
And we can use '
as syntax sugar for brevity.
lurk-user> '(1 2 3)
[1 iteration] => (1 2 3)