Skip to content

dpbriggs/x7

BranchesTags

Repository files navigation

The x7 Programming Language

x7 is a lisp I built to better understand programming languages and interpreters.

The standard library is being written in either x7 or rust for performance.

Features

Usual Lispy Goodness

You have brackets. Lots of brackets. And lists. And functions.

Self-documenting

The goal is to have every function describe itself, so you can live in the repl.

Use the doc function on a symbol to see it’s documentation:

>>> (print (doc foreach))
Eagerly apply the given function to a sequence or list.
Example:
(foreach
  (fn (x) (println x))
  (range 20)) ; prints 0 to 20. Returns ().

(foreach
  (fn (x) (println x))
  (take 5 (map (fn (x) (* x x x x x x)) (range)))) ; prints 0, 1, 64, 729, 4096

The general goal is to be as helpful as possible. So stacktraces include more information than you’d usually get, such as arguments.

For example, the following program will fail:

(defn bottom (x) (% x 2))
(defn middle (x) (bottom x))
(defn top () (middle "a"))
(top)

And give this helpful stacktrace:

Error: BadTypes

Stacktrace:
  - Remainder requires left and right are num types, was given "a" % 2
  - Error in Fn<%, 2, [ ]>, with args ("a" 2)
  - Error in Fn<bottom, 1, [ x ]>, with args ("a")
  - Error in Fn<middle, 1, [ x ]>, with args ("a")
  - Error in Fn<top, 0, [ ]>, with args ()

Convenient FFI

x7 offers easy and convenient embedding into other rust programs.

use x7::ffi::{X7Interpreter, ForeignData};

let interpreter = X7Interpreter::new();
let res = interpreter.run_program::<u64>("(+ 1 1)").unwrap();
assert_eq!(res, 2);

You can interface your own types in x7 with the ForeignData trait, and add foreign functions into the interpreter. To maximize convenience foreign functions are typed in terms of their own datatypes - not x7’s Expr type.

let interpreter = X7Interpreter::new();
let my_sum_fn = |args: Vec<u64>| Ok(args.iter().sum());
// Add the my-sum to interpreter
interpreter.add_function("my-sum", 1, Arc::new(my_sum_fn));

// And verify we get u64 with value 6 out of it.
assert_eq!(interpreter.run_program::<u64>("(my-sum 1 2 3)").unwrap(), 6);

More interesting is the fact that functions added to the interpreter in a strongly typed way, allowing us to mix types!

// Recall that my-sum is a Fn(Vec<u64>) -> u64
let string_res = interpreter.run_program::<String>("(my-sum 1 2 3)").unwrap();
// And we get a string out it!
assert_eq!(string_res, "6".to_string());

The reason it works is we embed the type information into the function added to the interpreter, and x7’s Expr type acts as a bridge between types.

For more info see the ffi.rs example in the examples folder!

You can run the example with:

cargo run --example ffi

Speedy Iterators

Certain constructs like (range) and map are backed by lazy iterators, making them pretty fast.

Examples

Fibonacci Numbers

We can print the first hundred fibonacci numbers in 14 milliseconds:

;; fib.x7
;; Run with: x7 fib.x7

;; Map (l, r) -> (r, l + r)

(defn fib-step (x)
  (bind ((l r) x) ^(r (+ l r))))

;; Reduce (0 1) `num` times using fib-step to
;; generate the `num`'th fibonacci number

(defn fib (num)
  (nth 0 (reduce
          fib-step
          (tuple 0 1)
          (range num))))

;; Print one hundred fibonacci numbers
;;
;; Note: (take 100 (map fib (range)))
;; is an iterator which maps to Rust's iterators which
;; makes them very fast. No weird intermediate allocations.

(println (time (foreach
                println
                (take 100 (map fib (range))))))

Outputs:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
...truncated...
83621143489848422977
135301852344706746049
218922995834555169026

More Features

Dynamic Records and Syntactic Sugar

A recent addition to the language is the defrecord and defmethod functions, which allow you to define records in x7 and add methods to the them respectively.

Here’s an example of defining Vec3, and a way to add them together:

;; Define a record
(defrecord Vec3 "Three dimensional vector" x y z)

;; Add a method to it
(defmethod Vec3 +
  "Add two vectors together"
  (other)
  (Vec3
   (+ other.x self.x)
   (+ other.y self.y)
   (+ other.z self.z)))

This lets us encapsulate data, and access it in a nice structured way.

;; Instantiate a Vec3
(def my-vector (Vec3 1 1 1))

;; Call the + method
(.+ my-vector my-vector) ;; Record<Vec3, fields=[ x: 2 y: 2 z: 2 ]>

The process of adding this support added two new ways to interact with expressions - callable Records and field-access-sugar

Callable Records

To make record construction nice, you can treat records defined with defrecord as constructor functions:

>>> (defrecord Point x y)
Record<Point, uninitialized>
>>> (Point 0 0)
Record<Point, fields=[ x: 0 y: 0 ]>

Record Field Syntactic Sugar

By default, fields of a record are treated as zero-arity methods on that record, with self being inserted with method_call syntax.

This meant that this got old after a while:

(+ (.x self) (.x other))

So I added some sugar in the form of self.x:

>>> (defrecord Point x y)
>>> (def origin (Point 0 0))
>>> origin.x
0

It works in a recursive way if you have deeply nested fields.

>>> (defrecord Point x y)
>>> (defrecord Space origin)
>>> (def space (Space (Point 0 0)))
>>> space.origin
Record<Point, fields=[ x: 0 y: 0 ]>
>>> space.origin.x
0
>>> space.origin.y
0

The syntax immediately evaluates, as it gets transformed a nested list of function calls:

space.origin.y ;; (.y (.origin space))

You can do some tricks with this, like this:

(def file (fs::open "input.txt"))
(def re (re::compile "(\d+)-(\d+) (.): (.*)"))
(def captures (.captures re file.read_to_string))

Zero arity functions can also be referenced:

>>> (def v (Vec3 1 1 1))
nil
>>> v.scale
Fn<curried_method_call<Vec3<scale>; #args=1>, 0, [ ]>
>>> (v.scale 3)
Record<Vec3, fields=[ x: 3 y: 3 z: 3 ]>
>>> v.length
1.73205080

Anonymous Function Syntactic Sugar

You can easily create anonymous functions with #(...). Here’s an example:

(filter #(< $1 10) (range 100)) ;; (0 1 2 3 4 5 6 7 8 9)

(map #(+ 10 $1) (range 10)) ;; (10 11 12 13 14 15 16 17 18 19)

Fields are labelled $1, $2, ....

Language Description

x7 is a quirky lisp which sort of evolved naturally. It has the following data-types:

  pub enum Expr {
    Num(Num),
    Integer(Integer),
    Symbol(Symbol),
    List(Vector<Expr>),
    Function(Arc<Function>),
    Nil,
    String(String),
    Quote(Vector<Expr>),
    Tuple(Vector<Expr>),
    Bool(bool),
    LazyIter(IterType),
    Dict(Dict),
    Record(crate::records::RecordType),
}

Num

Numbers in x7 are arbitrary precision BigDecimal types backed by the bigdecimal crate.

Example:

0
0.0
1.1
1000000000000000000

Integer

A fast-path for integer heavy calculations. If you can avoid non-whole numbers this is substantially faster than the Num type.

Example:

1
2
-5

Symbol

Symbols are references to some object in the symbol table. They can’t contain quotes or brackets.

Example:

+
sort
doc

List

A list is a sequential collection of values. When evaluated, the first argument is called as a function with the rest of the elements as arguments.

Example:

(+ 1 2)
(println "hello world!")

Function

A function is a type defined by the fn or defn keywords. They accept a variable number of arguments and carry a local scope. Variables shadow each other, and functions will close over arguments.

Example:

(defn is-odd?
  (x)
  (= 1 (% x 2))) ; add function is-odd? to symbol table

(map
  (fn (num) (* num num)) ; anon func
  (range 20))

(defn not=
  (& args) ; excess variables can be captured into a list
  (not (apply = args)))

Nil

Null type. Usually equal to an empty list.

String

A UTF-8 string of characters between two quotes: “hello world!”

Quote

An unevaluated list. When evaluated, it turns into a list.

Has special syntax: '(1 2 3) And a keyword: (quote 1 2 3)

Tuple

Same thing as a list, but always evals to itself.

Has special syntax: ^(1 2 3) And a keyword: (tuple 1 2 3)

Bool

Classic boolean. True or false.

Example:

true
false
(= 1 0) ;; false

LazyIter

A sequence of values backed by a Rust iterator. These are useful for working with infinite sequences.

Currently, map, filter, take, and range can yield lazy iterators.

They are evaluated with doall to make a list or foreach to operate on it.

Example:

(doall (take 5 (map inc (range)))) ; (1 2 3 4 5)
; Or
(foreach
  println
  (take 5 (map inc (range)))) ; prints one through five

Dict

Classic immutable dictionary. This is certainly a work in progress.

Example:

(def foo (dict "key1" "value1" 3 4))

(get foo 3)  ;; 4
(get foo "key1")  ;; "value1"

(set foo 5 6)  ;; {"key1": "value1", 3: 4, 5: 6}
               ;; This does not mutate `foo`!
(get foo 5)  ;; nil

Record

Objects in x7. See the record section above.

Standard Library Reference

The x7 language has self-documenting features. The standard library reference is generated with the script below, which org-mode pastes into the list below:

(defn pretty-print
  "Format doc strings into something org-mode will agree with."
  (x)
  (bind
   ((sym docu) x)
   (do
       (println "*** =" sym "=")
       (println "")
       (println "#+BEGIN_SRC elisp")
       (println docu)
       (println "#+END_SRC")
       (println ""))))

(foreach
 pretty-print
 (zip (all-symbols) (map doc (all-symbols))))

+

Add two items together. Concatenates strings, lists, and tuples.
Example: (+ 1 1 1) ; 3
Example: (+ "Hello " "World") ; "Hello World"

-

Subtracts all items from the first. Only works with Nums.
Example: (- 2 1 1) ; 0

*

Multiply all items against the first. Works with Nums and (String Num*)
Example: (* 1 2 3) ; 6
         (* "abc" 3) ; "abcabcabc"

%

Take the remainder of the first item against the second.
    Example: (% 4 2) ; 0

/

Divide the first element by the rest.
Example: (/ 8 2 2 2) ; 1

sqrt

Take the square root of a number. There's minor precision loss as it's way faster to convert to floats internally over using a bigdecimal.
Example: (sqrt 9) ; 3

===

Test if all items are equal.
Example: (= 1 1) ; true
         (= 1) ; true

<

Test if the first item is strictly smaller than the rest.
    Example: (< 0 1 2) ; true

<=

Test if the first item is smaller or equal to the rest.
    Example: (<= 0 0 0.05 1) ; true

>

Test if the first item is strictly greater than the rest.
    Example: (> 10 0 1 2 3 4) ; true

>=

Test if the first item is greater than or equal to the rest.
    Example: (>= 10 10 5) ; true

inc

Increment the given number.
Example:
(inc 2.2) ;; 3.3
(inc 1) ;; 2

dec

Decrement the given number.
Example:
(dec 2.2) ;; 3.3
(dec 1) ;; 2

pow

Raise a number to an exponent.
Example:
(pow 2 3) ;; 8
(pow 10 3) ;; 1000

floor

Floor a number.
Example:
(floor 5.5) ;; 5.5

int

Create an integer from the input.

Example:
(int 3.2) ;; 3

not

Invert the bool. true becomes false and vice-versa.

or

logical or.

and

logical and.

xor

logical xor.

ident

Identity function. Returns what you give it.

quote

Transforms the given input into a quote. Usually you will want to use the '(1 2 3) syntax.

symbol

Turn a string into a symbol

str

Make a string

bool

Coerce a value to bool. In general if a collection is non-empty, it is true. The len method is called on Records

print

Print the given argument WITHOUT a newline.

println

Print the given argument WITH a newline.

input

Get user input from stdin

split

Split a string with some substring.
Example:
>>> (split "," "hello, world")
(tuple "hello" " world")

replace

Replace a substring in a string with some other string.
Example:
>>> (replace "abc" "OwO" "abc def")
"OwO def"

ident-exists

Returns true if a given symbol exists in the interpeter

eval

Eval an expression.
Example (in repl):
>>> '(+ 1 2)
(+ 1 2)
>>> (eval '(+ 1 2))
3

parse

Parse an expression.
Example (in repl):
>>> (parse "(+ 1 2)")

def