BLisp: Lispっぽい静的型付け言語

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

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

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, vec![]).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番目の引数が2⁶⁴以上の場合はNoneをリターンします。

9. 数学的演算

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

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

powの指数部が2³²以上の場合は、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))

t と e は型変数です。このコードは、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. ジェネリック関数

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

(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関数を呼び出すことはできません。

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

(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. 外部関数呼び出し

blisp::embedded は、外部関数呼び出し用のマクロです。このマクロを利用すると、Rustの関数をBLispから容易に呼び出せるようになります。

たとえば、はじめに、Rustの関数を以下のように定義します。

use blisp::embedded;
use num_bigint::{BigInt, ToBigInt};

#[embedded]
fn add_four_ints(a: BigInt, b: (BigInt, BigInt), c: Option<BigInt>) -> Result<BigInt, String> {
    let mut result = a + b.0 + b.1;
    if let Some(n) = c {
        result += n;
    }

    Ok(result)
}

blisp::embedded マクロは外部関数呼び出し用の型定義を生成します。この関数は、以下のようにBLispから呼び出せます。

(export call_add_four_ints (n)
    (IO (-> ((Option Int)) (Result Int String)))
    (add_four_ints 1 [2 3] n))

外部関数を登録するためには、以下のように、 embedded によって生成される型定義のベクタを blisp::init に渡します。

// add_for_ints
let code = "(export call_add_four_ints (n)
    (IO (-> ((Option Int)) (Result Int String)))
    (add_four_ints 1 [2 3] n)
)";
let exprs = blisp::init(code, vec![Box::new(AddFourInts)]).unwrap();
let ctx = blisp::typing(exprs).unwrap();
let result = blisp::eval("(call_add_four_ints (Some 4))", &ctx).unwrap();

ここでは、関数名が add_four_ints のため、そのキャメルケースの AddFourInts を Box と Vec に包んで blisp::init に渡さなければなりません。

Rustの外部関数は以下に示される型のみ引数と返り値で利用可能です。 Vec<u64> のような他の型はサポート外ですが、 Vec<Option<bool>> のような型はOKです。 BLispとRustの間の型変換は embedded マクロが生成する関数によって自動的に行われます。

Table 1. Type Conversion between BLisp and Rust
BLisp	Rust
Int	BigInt
Bool	bool
Char	char
String	String
'(T)	Vec<T>
[T0, T1]	(T0, T1)
(Option T)	Option<T>
(Result T E)	Result<T, E>

19. Coqへのトランスパイラ (実験的)

BLispは実験的にCoqへのトランスパイラを実装しています。トランスパイラは、以下のように blisp::transpile を呼び出すことで実行されます。

let expr = "
(defun snoc (l y)
(Pure (-> (
    '(t) t)
'(t)))
(match l
    (nil (Cons y nil))
    ((Cons h b) (Cons h (snoc b y)))))

(defun rev (l)
(Pure (-> (
    '(t))
'(t)))
(match l
    (nil nil)
    ((Cons h t) (snoc (rev t) h))))
    ";
let exprs = blisp::init(expr, vec![]).unwrap();
let ctx = blisp::typing(exprs).unwrap();

println!("{}", blisp::transpile(&ctx));

これは以下のようなCoqのコードを出力します。この出力には、BLispのプレリュードも含まれます。

Require Import ZArith.
Require Import Coq.Lists.List.

Inductive Option (t: Type): Type :=
| Some (x0: t)
| None.

Arguments Some{t}.
Arguments None{t}.

Inductive Result (t e: Type): Type :=
| Ok (x0: t)
| Err (x0: e).

Arguments Ok{t e}.
Arguments Err{t e}.

Definition car {t: Type} (x: list t): Option t :=
match x with
  | (cons n _) => (Some n)
  | _ => (None)
  end.

Definition cdr {t: Type} (x: list t): list t :=
match x with
  | (cons _ l) => l
  | _ => nil
  end.

Definition filter {t: Type} (f: t -> bool) (x: list t): list t :=
(reverse (filter' f x nil ) ).

Fixpoint filter' {t: Type} (f: t -> bool) (x l: list t): list t :=
match x with
  | (cons h a) => match (f h ) with
    | true => (filter' f a (cons h l) )
    | false => (filter' f a l )
    end
  | _ => l
  end.

Fixpoint fold {a b: Type} (f: a -> b -> b) (init: b) (x: list a): b :=
match x with
  | (cons h l) => (fold f (f h init ) l )
  | _ => init
  end.

Fixpoint map {a b: Type} (f: a -> b) (x: list a): list b :=
match x with
  | (cons h l) => (cons (f h ) (map f l ))
  | _ => nil
  end.

Fixpoint rev {t: Type} (l: list t): list t :=
match l with
  | nil => nil
  | (cons h t) => (snoc (rev t ) h )
  end.

Definition reverse {t: Type} (x: list t): list t :=
(reverse' x nil ).

Fixpoint reverse' {t: Type} (x l: list t): list t :=
match x with
  | (cons h a) => (reverse' a (cons h l) )
  | _ => l
  end.

Fixpoint snoc {t: Type} (l: list t) (y: t): list t :=
match l with
  | nil => (cons y nil)
  | (cons h b) => (cons h (snoc b y ))
  end.

このトランスパイラは実験的なものであることに注意してください。よって、いくつかの出力はCoqが解釈できません。その場合は、手動でソースコードを修正してください。簡単にできるはずです。

20. 例

20.1. リバース

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

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

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

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

20.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))) ; リストをリターン

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