BLispは静的型付けされたLispライクなプログラミング言語で、no_std環境用のエフェクトシステムを採用しています。BLispは関数型プログラミング言語の高階関数のような高階のRPCをサポートしています。

本リポジトリではライブラリクレートのみを提供しています。BLispを利用するには blisp-repl か、おもちゃのOSである baremetalisp を参照してください。

no_stdで動くBLisp

no_stdで動くBLisp

1. 特徴

  • 代数的データ型

  • ジェネリクス

  • 型推論

  • IOと純粋な関数を分離するためのエフェクトシステム

  • 多倍長整数

  • no_std環境のサポート

2. 値

values
`A`       ; 文字リテラル
"Hello"   ; 文字列リテラル
144       ; 整数値
0xabcDEF  ; 16進数
0o777     ; 8進数
0b1001    ; 2進数
true      ; 真偽値
false     ; 真偽値
[true 10] ; タプル
[]        ; 空のタプル
'(1 2 3)  ; リスト
'()       ; 空のリスト、Nil

3. 基本型

types
Char       ; 文字型
String     ; 文字列型
Int        ; 整数型
Bool       ; 真偽値型
'(Int)     ; Int型のリスト型
[Int Bool] ; Int型とBool型のタプル型
(Pure (-> (Int Int) Bool)) ; Int型の値を2つとり、Bool型の値をリターンする純粋な関数
(IO (-> (Int) [])) ; Int型の値をとり[]をリターンするIOのある関数

PureとIOは関数の効果です。IO関数内では、Pure関数とIO関数の両方を呼び出すことができます。しかし、Pure関数内では、Pure関数の呼び出しのみ許可されています。

4. 関数定義

関数はdefunやexportで定義することができます。"defun"はRustのeval関数からは呼び出せないローカル関数を定義します。

以下の2つの関数があるとしましょう。

defun
(defun double (x)         ; 関数名がdoubleでxは引数
    (Pure (-> (Int) Int)) ; 関数の型
    (* 2 x))              ; 関数の中身
export
(export quad (x)          ; 関数名がquadで引数はx
    (Pure (-> (Int) Int)) ; 関数の型
    (double (double x)))  ; 関数の中身

doubleはRustのevalからは呼び出せませんが、内部で定義された関数からは呼び出せます。quadはRustのevalから呼び出すことができ、内部的にdoubleを呼び出します。

これは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)         ; 関数名がdoubleでxは引数
    (Pure (-> (Int) Int)) ; 関数の型
    (* 2 x))              ; 関数の中身

(export quad (x)          ; 関数名がquadで引数はx
    (Pure (-> (Int) Int)) ; 関数の型
    (double (double x)))  ; 関数の中身
";
    let exprs = blisp::init(code).unwrap();
    let ctx = blisp::typing(&exprs).unwrap();

    let e = "(double 10) ; エラー";
    eval(e, &ctx);

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

このコードは以下のように出力します。

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

5. 算術演算

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

6. 真偽値演算

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

7. 比較演算

=, !=, <, >, <=, >= といった関数は、同じ型の2つの値に対して適用できます。

comparison between 2 values whose types are same
; (Pure (-> (t t) Bool))
(= 4 4)               ; true
(!= 4 4)              ; false
(= "Hello" "Hello")   ; true
(= (Some 1) (Some 2)) ; false
(< 6 7)
(> 6 7)
(<= 30 40)
(>= 30 40)
(< "Hello" "World")
(<= (Some 1) (Some 2))

eq, neq, lt, gt, leq, geq といった関数は、異なる型同士の値でも比較可能です。

comparison between any 2 values
; (Pure (-> (t1 t1) Bool))
(geq (Some 1) "Hello") ; (Some 1)は"Hello"より大きい、もしくは等しいか?
(eq "Hello" 100)       ; "Hello"と100は等しいか?
(neq "Hello" 100)      ; "Hello"と100は等しくないか?
(lt 100 (Some 20))     ; 100は(Some 20)より小さいか?
(gt 200 "Hello")       ; 200は"Hello"より大きいか?

8. ビット演算

(band 1 0) ; ビット積
(band 1 1) ; ビット積
(bor 1 0)  ; ビット和
(bor 1 1)  ; ビット和
(bxor 1 0) ; ビット排他的論理和
ビットシフト
; (Pure (-> (Int Int) (Option Int)))
(<< 8 4)   ; (Some 128)
(>> 128 4) ; (Some 8)
(>> -128 4) ; (Some -8)

2番目の引数が264以上の場合はNoneをリターンします。

9. 数学的演算

; (Pure (-> (Int Int) (Option Int)))
(pow 10 20) ; (Some 100000000000000000000) namely 10^20

; (Pure (-> (Int) (Option Int)))
(sqrt 16)   ; (Some 4)

powの指数部が232以上の場合は、powはNoneをリターンします。

sqrtの引数が0以下の場合は、sqrtはNoneをリターンします。

10. 代数的データ型

代数的データ型は以下のように定義できます。

; in BLisp
(data Gender ; 型名
    Male     ; 値
    Female)  ; 値

型名とその値の最初の文字は大文字でなければなりません。これはRustの以下のコードと同等です。

// in Rust
enum Gender {
    Male,
    Female
}

各要素は以下のような値を持つことができます。

; in BLisp
(data Dim2
    (Dim2 Int Int)) ; Dim2は2つのInt型の値を持つ

Dim2は以下のようにインスタンス化することができます。

(Dim2 10 20)

この型はRustの以下の型と同等です。

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

11. ジェネリクス

Option型とResult型は内部で定義されています。

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

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

te は型変数です。このコードは、Rustの以下のコードと同等です。

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

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

リスト型は以下のような組み込み型です。

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

したがって、以下の2つのリストは等価です。

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

12. ジェネリック関数

carcdr は内部的に定義されたジェネリック関数です。これらの定義は以下の通りです。

(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_は型変数です。これらの関数は以下のように使うことができます。

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

通常変数と型変数の最初の文字は小文字でなければなりません。

13. If式

単純です.

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

14. Match式

リストは以下のようにマッチさせることができます。

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

この、

(Cons n _)

という式はパターンです。 パターンが '(1 2 3) にマッチした場合、1は可変変数 n に代入されます。そうすると、n つまり1が返されます。

タプルのパターンマッチングの例です。

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

このコードはタプルの第1要素と第2要素を入れ替えます。

整数値はパターンマッチングにも使用できます。

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

より複雑な例としては、以下のようなものがあります。

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

BLispはパターンを網羅的にチェックします。そのため、以下のコードは拒否されます。

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

15. Let式

変数のバインドには、以下のようにLet式を使用します。

(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)

また、以下のように分配束縛を行うこともできます。

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

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

16. ラムダ式

ラムダ式は以下のように定義されます。

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

このラムダは2つの整数を受け取り、それらの乗算を返します。これに引数を適用するのは次のように簡単に行えます。

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

すべてのラムダ式は純粋です。よって、ラムダ式からIO関数を呼び出すことはできません。

mapfold 関数は内部的に以下のように定義されています。

(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 を使うと、以下のようにリストの要素に関数を適用することができます。

; それぞれをの要素を2乗
(let ((l '(1 2 3))
      (f (lambda (x) (* x x))))
        (map f l))

fold を使用して、リストの要素にまたがって計算することができます。例えば、合計は以下のように計算できます。

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

当然、これは以下のようにも記述できます。

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

17. 文字列と文字

chars はStringから(List Char)へ変換します。

; (Pure (-> (String) (List Char)))
(chars "Hello") ; '(`H` `e` `l` `l` `o`)

str は(List Char)からStringへ変換します。

; (Pure (-> ((List Char)) String))
(str '(`H` `e` `l` `l` `o`)) ; "Hello"

18. 外部関数呼び出し

call-rust はRustの関数を呼び出すための関数です。 これは以下のように組み込み関数として定義されています。

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

この関数は3つの整数値をとり、(Option Int)をリターンします。 Rustの関数を呼び出すためには、以下のようにコールバック関数を設定しなければなりません。

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);
  1. BLispから呼び出されるコールバック関数です. この関数の型は Fn:(&BigInt, &BigInt, &BigInt) → Option<BigInt> でなければなりません。

  2. Rustのコールバック関数を呼び出しています。

このコードを呼び出すと、次のように出力されます。

n = 6000000000

call-rust はIO関数です. 従って、Pure関数からは呼び出すことは出来ません。

19. 例

19.1. リバース

reverse は内部で定義されている関数です。この関数はリストを反転します。

(reverse '(1 2 3 4 5 6 7 8 9))

このコードの出力は以下の通りです。

'(9 8 7 6 5 4 3 2 1)

19.2. Filter

filter は内部で定義されている関数です。この関数はリストの中身をフィルターします。

(filter (lambda (x) (= (% x 2) 0)) '(1 2 3 4 5 6 7 8 9))

このコードの出力は以下の通りです。

'(2 4 6 8)

filter' の型は以下の通りです。

(Pure (->
    ((Pure (-> (t) Bool)) ; 関数を引数にとる
     '(t))                ; リストを引数にとる
    '(t))) ; リストをリターン

19.3. 階乗

末尾呼び出し版の階乗関数は、以下のように実装できます。

(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))))

この関数は以下のように呼び出すことができます。

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