BLisp: A Statically Typed Lisp Like Language

BLisp is a statically typed Lisp like programming language which adopts effect system for no_std environments. BLisp supports higher order RPC like higher order functions of functional programming languages.

This repository provides only a library crate. Please see blisp-repl to use BLisp, and baremetalisp which is a toy OS.

日本語版はこちら

BLisp on no_std Environment

1. Features

Algebraic data type
Generics
Hindley–Milner based type inference
Effect system to separate side effects from pure functions
Big integer
Supporting no_std environments

2. Values

values

144       ; integer value
true      ; boolean value
false     ; boolean value
[true 10] ; tuple
[]        ; empty tuple
'(1 2 3)  ; list
'()       ; empty list, Nil

3. Basic Types

types

Int        ; signed integer
Bool       ; boolean
'(Int)     ; list of Int
[Int Bool] ; tuple of Int and Bool
(Pure (-> (Int Int) Bool)) ; Pure function, which takes 2 integers and return boolean value
(IO (-> (Int) [])) ; IO function, which takes an integer and return []

Pure and IO are function effects. In IO functions, both Pure and IO functions can be called. However, in Pure functions, calling only Pure functions is permitted.

4. Function Definition

Functions can be defined by defun or export. "defun" defines a local function which cannot be called from Rust’s eval function.

Suppose following 2 functions.

defun

(defun double (x)         ; function name is "double" and "x" is an argument
    (Pure (-> (Int) Int)) ; function Type
    (* 2 x))              ; function body

export

(export quad (x)          ; function name is "quad" and "x" is an argument
    (Pure (-> (Int) Int)) ; function Type
    (double (double x)))  ; function body

double cannot be called from Rust’s eval, but can be called from internally defined functions. quad can be called from Rust’s eval, and it calls double internally.

This is the code what actually do in Rust.

Rust’s eval

use blisp;

fn eval(e: &str, ctx: &blisp::semantics::Context) {
    // evaluate expressions
    let exprs = match blisp::eval(e, ctx) {
        Ok(es) => es,
        Err(err) => {
            println!("error:{}:{}: {}", err.pos.line, err.pos.column, err.msg);
            return;
        }
    };

    for r in exprs {
        match r {
            Ok(msg) => {
                println!("{}", msg);
            }
            Err(msg) => {
                println!("error: {}", msg);
            }
        }
    }
}

fn main() {
    // internal code
    let code = "
(defun double (x)         ; function name is double and x is an argument
    (Pure (-> (Int) Int)) ; function Type
    (* 2 x))              ; function body

(export quad (x)          ; function name is quad and x is an argument
    (Pure (-> (Int) Int)) ; function Type
    (double (double x)))  ; function body
";
    let exprs = blisp::init(code).unwrap();
    let ctx = blisp::typing(&exprs).unwrap();

    let e = "(double 10) ; error";
    eval(e, &ctx);

    let e = "(quad 10) ; OK";
    eval(e, &ctx);
}

This code output as follows.

error:0:1: Typing Error: double is not defined
40

5. Arithmetic Operations

basic

; (Pure (-> (Int Int) Int))
(+ 10 20)
(- 30 40)
(* 6 100)
(/ 100 2)
(% 10 3)

comparison

; (Pure (-> (Int Int) Bool))
(= 4 4)
(< 6 7)
(> 6 7)
(<= 30 40)
(>= 30 40)

6. Boolean Operations

logical

; (Pure (-> (Bool Bool) Bool))
(and true false)
(or true false)
(xor true false)

negation

; (Pure (-> (Bool) Bool))
(not true)

7. Algebraic Data Type

Algebraic data type can be defined as follows.

; in BLisp
(data Gender ; type name
    Male     ; value
    Female)  ; value

Type name’s and its value’s first character must be uppercase. This is equivalent to Rust’s following code.

// in Rust
enum Gender {
    Male,
    Female
}

Each element can have values as follows.

; in BLisp
(data Dim2
    (Dim2 Int Int)) ; Dim2 has integers

Dim2 can be instantiated as follows.

(Dim2 10 20)

This type is equivalent to Rust’s following type.

// in Rust
use num_bigint::BigInt;
enum Dim2 {
    Dim2(BigInt, BigInt)
}

8. Generics

Option and Result types are defined internally.

(data (Option t)
    (Some t)
    None)

(data (Result t e)
    (Ok t)
    (Err e))

t and e are type variables. This code is equivalent to Rust’s following code.

// in Rust
enum Option<T> {
    Some(T),
    None,
}

enum Result<T, E> {
    Ok(T),
    Err(E),
}

List type is a built-in type as follows.

(data (List t)
    (Cons t (List t))
    Nil)

So, following 2 lists are equivalent.

(Cons 1 (Cons 2 (Cons 3 Nil)))
'(1 2 3)

9. Generic Function

car and cdr are internally defined generic functions. These definitions are as follows.

(export car (x) (Pure (-> ('(t)) (Option t)))
    (match x
        ((Cons n _) (Some n))
        (_ None)))

(export cdr (x) (Pure (-> ('(t)) '(t)))
    (match x
        ((Cons _ l) l)
        (_ '())))

t is a type variable. These functions can be used as follows.

(car '(3 8 9))  ; returns (Some 3)
(cdr '(8 10 4)) ; returns '(10 4)

Normal and type variables' first character must be lowercase.

10. If Expression

Straightforward.

(if (< 10 20)
    '(1 2 3)
    '())

11. Match Expression

A list can be matched as follows.

(match '(1 2 3)
    ((Cons n _) n)
    ('() 0))

The expression

(Cons n _)

is a pattern. If the pattern is matched to '(1 2 3), 1 is assigned to a variable n. Then, n, namely 1, is returned.

This is an example of pattern matching of tuple.

(match [1 3]
    ([x y] [y x]))

This code swap 1st and 2nd elements of the tuple.

Integer values can be also used for pattern matching.

(match 20
    (20 true)
    (_ false))

More complex example is a as follows.

(match [(Some 10) true]
    ([(Some 10) false] 1)
    ([(Some 10) true] 2)
    (_ 0))

BLisp checks exhaustively of pattern. So, following code will be rejected.

(match '(1 2)
    ('() 0))

12. Let Expression

Let expression is used to bind variables as follows.

(let ((x 10) (y 20)) ; x is 10, y is 20
    (* x y))

(let ((x 10) (x (* x x)) (x (* x x))) ; x = 10, x = x * x, x = x * x
    x)

Destructuring can be also performed as follows.

(let (((Some x) (Some 10))) ; x is 10
    (* x 2))

(let (([x y] [10 20])) ; x is 10, y is 20
    (* x y))

13. Lambda Expression

Lambda expression is defined as follows.

(lambda (x y) (* x y))

This lambda takes 2 integers and return the multiplication. Applying arguments to this is simple as follows.

((lambda (x y) (* x y)) 10 20)

Every lambda expression is Pure. IO functions cannot be called in any lambda expressions.

map and fold functions are internally defined as follows.

(export map (f x) (Pure (-> ((Pure (-> (a) b)) '(a)) '(b)))
    (match x
        ((Cons h l) (Cons (f h) (map f l)))
        (_ '())))

(export fold (f init x) (Pure (-> ((Pure (-> (a b) b)) b '(a)) b))
    (match x
        ((Cons h l) (fold f (f h init) l))
        (_ init)))

map can be used to apply functions to elements of a list as follows.

; square each element
(let ((l '(1 2 3))
      (f (lambda (x) (* x x))))
        (map f l))

fold can be used to calculate over elements of a list. For example, summation can be computed as follows.

; summation
(let ((l '(20 50 60))
      (f (lambda (x y) (+ x y))))
        (fold f 0 l)) ; 0 is an initial value

Of course, this can be written as follows.

; summation
(fold + 0 '(20 50 60))

14. Foreign Function Interface

call-rust is a function to call Rust’s function. This is defined as a built-in function as follows.

(define call-rust
    (IO (-> (Int Int Int) (Option Int))) ; type of call-rust
    ; omitted
    )

It takes 3 integers and returns (Option Int). In order to call Rust’s function, setting a callback function is required as follows.

use blisp;
use num_bigint::BigInt;

let expr = "
(export callback (x y z)
    (IO (-> (Int Int Int) (Option Int)))
    (call-rust x y z))";
let exprs = blisp::init(expr).unwrap();
let mut ctx = blisp::typing(&exprs).unwrap();

let fun = |x: &BigInt, y: &BigInt, z: &BigInt| { (1)
    let n = x * y * z;
    println!("n = {}", n);
    Some(n)
};
ctx.set_callback(Box::new(fun));

let e = "(callback 100 2000 30000)"; (2)
blisp::eval(e, &ctx);

callback function called from BLisp. The function type must be Fn:(&BigInt, &BigInt, &BigInt) → Option<BigInt>
call Rust’s callback function

When executing this code, it outputs as follows.

n = 6000000000

call-rust is a IO function. Therefore, this cannot be called from Pure functions.

15. Examples

15.1. Factorial

Tail call factorial can be coded as follows.

(export factorial (n) (Pure (-> (Int) Int))
    (fact n 1))

(defun fact (n total) (Pure (-> (Int Int) Int))
    (if (<= n 0)
        total
        (fact (- n 1) (* n total))))

This function can be called as follows.

>> (factorial 10)
3628800
>>
>> (factorial 1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
>>
>> (factorial 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>>
>> (factorial 500)
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000