Euler Lisp

Keywords: lisp math
Created: 2019-07-22 Mon 20:14:00

A LISP bytecode VM implemented in Rust.

Source code on Github: l3kn/EulerLisp

I always wanted to create my own programming language.

It might be one of the programming projects with the highest floor-to-ceiling ratio : a simple interpreter can take up less than a hundred lines of code, but adding features and improving the speed quickly increases the complexity, until it reaches the heights of industrial strength compilers like gcc, with millions of lines of code.

At around 7k lines of code this project lies somewhere inbetween (at least on a logarithmic scale).

The language is a Lisp1 modeled after Scheme and runs on a simple bytecode-VM, so that it is possible to write non-trivial programs and have them run at a reasonable speed.

(defn fib (n)
      (if (<= n 1)
          n
          (+ (fib (- n 1))
             (fib (- n 2)))))

(println (fib 30))

Of course this is a pretty meaningless benchmark, but on my machine the recursive fibonacci fuction above takes 1.1s to execute in EulerLisp which gets makes it between 2x and 10x slower than a few other languages I tested:

Motivation

As an incentive to make the language fast and usable, I'm using it to work through some Project Euler math problems.

leonrische.png

Figure 1: Project Euler badge

Up till now, I've solved around 200 of the problems and written around 7k lines of EulerLisp code.

TODO: List of favorite problems

Data Types

The main data type is called Datum and has different variants:

  • Bool
  • Integer (64bit signed)
  • Bignum (multiple precision)
  • Rational (64bit numerator and denominator)
  • Float (64bit)
  • Char
  • String
  • Symbol (pointer into a symbol table)
  • Vector
  • Builtin (reference to a function implemented in rust)
  • Closure (reference to a function in the target language)
  • PriorityQueue (for performance reasons, should be implemented in lisp)
  • Undefined
  • Nil

Builtin Functions

Bitwise

  • (bitwise-and args*)
  • (bitwise-or args*)
  • (bitwise-xor args*)
  • (bitwise-not args)

Comparison

  • ( args*)=, numeric equality
  • (! a b)=, numeric inequality
  • (equal? args*) , object equality
  • (< args*)
  • (< args*)=
  • (> args*)
  • (> args*)=
  • (min args*)
  • (max args*)

Lists, Vectors, Pair

  • (cons a b) , create a pair from a and b
  • (fst p) , get the first element of a pair
  • (rst p) , get the second element of a pair
  • (set-fst! p v) , set the first element of a pair
  • (set-rst! p v) , set the second element of a pair
  • (list args*) , create a list, equivalent to (cons arg1 (cons arg2 (cons ... (cons argn '()))))
  • (list->vector lst)
  • (permutations lst)
  • (combinations lst len)
  • (sort lst)
  • (uniq lst)
  • (join str lst)
  • (vector args*) create a vector
  • (vector-ref vec i)
  • (vector-set! vec i v)
  • (vector-push! vec v)
  • (vector-pop! vec)
  • (vector-shuffle! vec)
  • (vector-delete! vec i)
  • (vector-length vec)
  • (vector->list vec)
  • (make-vector size [initial])
  • (vector-copy vec [from] [to])

Numbers, Math

  • (+ args*)
  • (- arg) , negation
  • (- args*) , subtraction
  • (* args*)
  • (/ args*)
  • (% a mod)
  • (div a mod) , integer division
  • (divmod a mod) , the result is a pair (quotient . remainder)
  • (powf n e) , euler_lisp_d10721b11a16fbd3e20485af7d34d913cebc409b.svg ( pow for non-integer exponents)
  • (sqrt n) , euler_lisp_4ff5835565fd8cd3f15b0e4ba75a0612226afba0.svg
  • (cbrt n) , euler_lisp_4db19447bee31def620a542cce66b1865211be91.svg
  • (ln a) , logarithm base euler_lisp_184ed9fd78c72ef3e695d0a59e6a5179ca3944be.svg
  • (log2 a) , logarithm base euler_lisp_e9000c1b19d93af40921e37908158a634dc771e3.svg
  • (log10 a) , logarithm base euler_lisp_dac05120638abd2266c26e0dc7d2185c0f43591a.svg
  • (log a base)
  • (ceil a)
  • (round a)
  • (floor a)
  • (>> a by) , right shift
  • (<< a by) , left shift
  • (popcount a) , count the number of euler_lisp_3748b9ef238f157044d120d4a2efc94b6576b83c.svg s in the binary representation of euler_lisp_44f297e860dac0eb0204c372764629c000e60b74.svg
  • (prime? a)
  • (zero? a)
  • (number->digits a) , list of the digits of a in reverse order
  • (digits->number lst)
  • (number-of-digits a)
  • (denominator a)
  • (numerator a)
  • (sin a) , (cos a) , (tan a)
  • (asin a) , (atan a) , (acos a)
  • (atan2 a b) , four quadrant inverse tangent
  • (radiants a)
  • (totient a) , (totient-sum a) , euler_lisp_1f322b78ab9f59935066ecf284244916c66a7254.svg and euler_lisp_638ece3ad73070766a04aab6327535665efaa567.svg
  • (modexp b e n) , euler_lisp_5fb7f74bc455374a2cddaaefdb67f7933251fe44.svg
  • (modular-inverse b n) , inverse of euler_lisp_173e3df2d028a6302f8f1d50afa7eaeea3674d96.svg modulo euler_lisp_5c8720e3bac5fd81ef6d524ed2a1cdeee6ab2a66.svg
  • (extended-euclidian a b) , a list euler_lisp_b7ff8678f8d7ca1d058f0f635755743e9482b29d.svg , so that euler_lisp_ab220d61902d80c910d1abc4562dcc3fae7fee1e.svg
  • (prime-factors a) , prime factors of a as a list of pairs (p . e)
  • (num-prime-factors a) , number of prime factors of a
  • (primes n) , a list of the first n primes
  • (rand from to) , random number in euler_lisp_3566749b28698a9425934592752d03ebd7ce4fc9.svg

Bignum

  • (bignum n) , convert n to a bignum
  • (digits->bignum digits) , create a bignum from a list of digits (in reverse order)
  • (bignum-chunks bn) , base euler_lisp_59097f8598102e95a03daaa6010c6db04fbfa58d.svg "digits" of the bignum
  • (chunks->bignum bn) , create a bignum from a list of chunks

Input / Output

TODO

String

TODO

Types

TODO

Resources

If this inspired you to start building your own programming language, here are some resources that helped me:

Implementation

TODO

Garbage Collection

Currently I'm using rusts reference counted pointers Rc and RefCell as a substitute for implementing my own garbage collection.

This works fine in most cases, but because Scheme allows creating circular lists it it possible to create objects that are not reachable by some root but have non-zero reference counts.

(defn fill-memory ()
      (let ((circular (cons 1 2)))
        (set-rst! circular circular))
      (fill-memory))

(fill-memory)

In the future it would be nice to write my own simple garbage collector.

Continuations

Continuations capture the remaining parts of a computation.

The VM maintains the following state components:

  • val register
  • fun register
  • arg1 register
  • arg2 register
  • env
  • env stack
  • stack
  • program counter (through a Bytecode struct)
  • program counter stack (through a Bytecode struct)

call-with-current-continuation (often abbreviated as call/cc ) captures the current evaluation context and turns it into an object that can be called.

(call/cc f) allocates an activation frame, fills it with an object representing the current continuation and then calls the f with this activation frame.

We can ignore the registers, they are not saved in any function call. The program counter can be ignored, too, as it is restored by the RETURN in the body of function f .

Continuation invocation works by restoring the stack, setting val to the value the continuation was called with and then continuing to run the program.

(defn f (cont)
  (cont 2)
  3)

(println (f id))
(println (call/cc f))
   CREATE-CLOSURE 1
   JUMP @510
   PUSH-SHALLOW-ARGUMENT-REF 0
   PUSH-CONSTANT $2
   FUNCTION-INVOKE tail: false, arity: 1
   RESTORE-ENV
   CONSTANT $3
   RETURN
510:
   GLOBAL-SET g322
   // (set! f ...)

   PUSH-CHECKED-GLOBAL-REF println
   PUSH-CHECKED-GLOBAL-REF g322
   PUSH-CHECKED-GLOBAL-REF g236
   FUNCTION-INVOKE tail: false, arity: 1
   // call (f id)
   RESTORE-ENV
   PUSH-VALUE
   FUNCTION-INVOKE tail: false, arity: 1
   // call (println res)
   RESTORE-ENV
   PUSH-CHECKED-GLOBAL-REF println
   CHECKED-GLOBAL-REF g322
   // load `f` closure into val
   CALL-CC
   // call `f` with current continuation as argument
   PUSH-VALUE
   FUNCTION-INVOKE tail: true, arity: 1

When FUNCTION-INVOKE in the closure is called on the continuation,

TODO: Call/cc as builtin function, so that I can use it in map

Backlinks


Last export: 2020-05-29 Fri 00:09
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.