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 programing languages.

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

日本語版はこちら

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. qued 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 varable 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

14. Examples

14.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