= BLisp: Lispっぽい静的型付け言語
Yuuki Takano <ytakano@wide.ad.jp>
v0.4.0, 2023-02
:doctype: article
:toc:
:sectnums:
:lang: ja
:encoding: utf-8
:stem: latexmath
:source-highlighter: pygments
BLispは静的型付けされたLispライクなプログラミング言語で、no_std環境用のエフェクトシステムを採用しています。BLispは関数型プログラミング言語の高階関数のような高階のRPCをサポートしています。
* https://github.com/ytakano/blisp[GitHubリポジトリ]
* https://crates.io/crates/blisp[BLispのcrates.io]
本リポジトリではライブラリクレートのみを提供しています。BLispを利用するには https://github.com/ytakano/blisp-repl[blisp-repl] か、おもちゃのOSである https://github.com/ytakano/baremetalisp[baremetalisp] を参照してください。
https://ytakano.github.io/blisp/[English version is here.]
.no_stdで動くBLisp
image:https://cdn-ak.f.st-hatena.com/images/fotolife/y/ytakano/20210221/20210221155657.gif[no_stdで動くBLisp]
== 特徴
* 代数的データ型
* ジェネリクス
* 型推論
* IOと純粋な関数を分離するためのエフェクトシステム
* 多倍長整数
* no_std環境のサポート
== 値
.values
[source, lisp]
----
`A` ; 文字リテラル
"Hello" ; 文字列リテラル
144 ; 整数値
0xabcDEF ; 16進数
0o777 ; 8進数
0b1001 ; 2進数
true ; 真偽値
false ; 真偽値
[true 10] ; タプル
[] ; 空のタプル
'(1 2 3) ; リスト
'() ; 空のリスト、Nil
----
== 基本型
.types
[source, lisp]
----
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関数の呼び出しのみ許可されています。
== 関数定義
関数はdefunやexportで定義することができます。"defun"はRustのeval関数からは呼び出せないローカル関数を定義します。
以下の2つの関数があるとしましょう。
.defun
[source, lisp]
----
(defun double (x) ; 関数名がdoubleでxは引数
(Pure (-> (Int) Int)) ; 関数の型
(* 2 x)) ; 関数の中身
----
.export
[source, lisp]
----
(export quad (x) ; 関数名がquadで引数はx
(Pure (-> (Int) Int)) ; 関数の型
(double (double x))) ; 関数の中身
----
doubleはRustのevalからは呼び出せませんが、内部で定義された関数からは呼び出せます。quadはRustのevalから呼び出すことができ、内部的にdoubleを呼び出します。
これはRustで実際に行うコードです。
.Rust's eval
[source, rust]
----
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
== 算術演算
.基本
[source, lisp]
----
; (Pure (-> (Int Int) Int))
(+ 10 20)
(- 30 40)
(* 6 100)
(/ 100 2)
(% 10 3)
----
== 真偽値演算
.logical
[source, lisp]
----
; (Pure (-> (Bool Bool) Bool))
(and true false)
(or true false)
(xor true false)
----
.negation
[source, lisp]
----
; (Pure (-> (Bool) Bool))
(not true)
----
== 比較演算
=, !=, <, >, \<=, >= といった関数は、同じ型の2つの値に対して適用できます。
.comparison between 2 values whose types are same
[source, lisp]
----
; (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
[source, lisp]
----
; (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"より大きいか？
----
== ビット演算
[source, lisp]
----
(band 1 0) ; ビット積
(band 1 1) ; ビット積
(bor 1 0) ; ビット和
(bor 1 1) ; ビット和
(bxor 1 0) ; ビット排他的論理和
----
.ビットシフト
[source, lisp]
----
; (Pure (-> (Int Int) (Option Int)))
(<< 8 4) ; (Some 128)
(>> 128 4) ; (Some 8)
(>> -128 4) ; (Some -8)
----
2番目の引数が2^64^以上の場合はNoneをリターンします。
== 数学的演算
[source, lisp]
----
; (Pure (-> (Int Int) (Option Int)))
(pow 10 20) ; (Some 100000000000000000000) namely 10^20
; (Pure (-> (Int) (Option Int)))
(sqrt 16) ; (Some 4)
----
powの指数部が2^32^以上の場合は、powはNoneをリターンします。
sqrtの引数が0以下の場合は、sqrtはNoneをリターンします。
== 代数的データ型
代数的データ型は以下のように定義できます。
[source, lisp]
----
; in BLisp
(data Gender ; 型名
Male ; 値
Female) ; 値
----
型名とその値の最初の文字は大文字でなければなりません。これはRustの以下のコードと同等です。
[source, rust]
----
// in Rust
enum Gender {
Male,
Female
}
----
各要素は以下のような値を持つことができます。
[source, lisp]
----
; in BLisp
(data Dim2
(Dim2 Int Int)) ; Dim2は2つのInt型の値を持つ
----
Dim2は以下のようにインスタンス化することができます。
[source, lisp]
----
(Dim2 10 20)
----
この型はRustの以下の型と同等です。
[source, rust]
----
// in Rust
use num_bigint::BigInt;
enum Dim2 {
Dim2(BigInt, BigInt)
}
----
== ジェネリクス
Option型とResult型は内部で定義されています。
[source, lisp]
----
(data (Option t)
(Some t)
None)
(data (Result t e)
(Ok t)
(Err e))
----
_t_ と _e_ は型変数です。このコードは、Rustの以下のコードと同等です。
[source, rust]
----
// in Rust
enum Option<T> {
Some(T),
None,
}
enum Result<T, E> {
Ok(T),
Err(E),
}
----
リスト型は以下のような組み込み型です。
[source, lisp]
----
(data (List t)
(Cons t (List t))
Nil)
----
したがって、以下の2つのリストは等価です。
[source, lisp]
----
(Cons 1 (Cons 2 (Cons 3 Nil)))
'(1 2 3)
----
== ジェネリック関数
_car_ と _cdr_ は内部的に定義されたジェネリック関数です。これらの定義は以下の通りです。
[source, lisp]
----
(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_は型変数です。これらの関数は以下のように使うことができます。
[source, lisp]
----
(car '(3 8 9)) ; returns (Some 3)
(cdr '(8 10 4)) ; returns '(10 4)
----
通常変数と型変数の最初の文字は小文字でなければなりません。
== If式
単純です.
[source, lisp]
----
(if (< 10 20)
'(1 2 3)
'())
----
== Match式
リストは以下のようにマッチさせることができます。
[source, lisp]
----
(match '(1 2 3)
((Cons n _) n)
('() 0))
----
この、
(Cons n _)
という式はパターンです。
パターンが '(1 2 3) にマッチした場合、1は可変変数 _n_ に代入されます。そうすると、_n_ つまり1が返されます。
タプルのパターンマッチングの例です。
[source, lisp]
----
(match [1 3]
([x y] [y x]))
----
このコードはタプルの第1要素と第2要素を入れ替えます。
整数値はパターンマッチングにも使用できます。
[source, lisp]
----
(match 20
(20 true)
(_ false))
----
より複雑な例としては、以下のようなものがあります。
[source, lisp]
----
(match [(Some 10) true]
([(Some 10) false] 1)
([(Some 10) true] 2)
(_ 0))
----
BLispはパターンを網羅的にチェックします。そのため、以下のコードは拒否されます。
[source, lisp]
----
(match '(1 2)
('() 0))
----
== Let式
変数のバインドには、以下のようにLet式を使用します。
[source, lisp]
----
(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)
----
また、以下のように分配束縛を行うこともできます。
[source, lisp]
----
(let (((Some x) (Some 10))) ; x is 10
(* x 2))
(let (([x y] [10 20])) ; x is 10, y is 20
(* x y))
----
== ラムダ式
ラムダ式は以下のように定義されます。
[source, lisp]
----
(lambda (x y) (* x y))
----
このラムダは2つの整数を受け取り、それらの乗算を返します。これに引数を適用するのは次のように簡単に行えます。
[source, lisp]
----
((lambda (x y) (* x y)) 10 20)
----
すべてのラムダ式は純粋です。よって、ラムダ式からIO関数を呼び出すことはできません。
_map_ と _fold_ 関数は内部的に以下のように定義されています。
[source, lisp]
----
(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_ を使うと、以下のようにリストの要素に関数を適用することができます。
[source, lisp]
----
; それぞれをの要素を2乗
(let ((l '(1 2 3))
(f (lambda (x) (* x x))))
(map f l))
----
_fold_ を使用して、リストの要素にまたがって計算することができます。例えば、合計は以下のように計算できます。
[source, lisp]
----
; 合計
(let ((l '(20 50 60))
(f (lambda (x y) (+ x y))))
(fold f 0 l)) ; 0 is an initial value
----
当然、これは以下のようにも記述できます。
[source, lisp]
----
; summation
(fold + 0 '(20 50 60))
----
== マクロ
マクロは `macro` で定義できます。
各ルールはパターンとテンプレートの組からなり、最初に一致したルールが展開されます。
[source, lisp]
----
(macro add
((add $e1 $e2) (+ $e1 $e2))
((add $e1 $e2 $e3 ...) (+ $e1 (add $e2 $e3 ...))))
----
`$` で始まる識別子はパターン変数です。
パターン変数には、マクロ呼び出し側で一致した式がそのまま代入されます。
`...` は、パターン変数やテンプレート断片の後ろに置くことで、残りの引数を可変長部分としてまとめて扱えます。
[source, lisp]
----
(add 1 2) ; 3
(add 1 2 3 4 5) ; 15
----
マクロは局所変数を導入する式も生成できます。
たとえば、一時変数を含むラムダ式は以下のように書けます。
[source, lisp]
----
(macro with_tmp
((_ $x) ((lambda (tmp) (+ tmp $x)) 1)))
(export test (tmp) (Pure (-> (Int) Int))
(with_tmp tmp))
----
BLispのマクロは、テンプレートが導入する局所 binder に対して衛生的です。
`lambda` の引数、`let` の束縛、`match` のパターン変数は展開時に fresh な内部名へ自動的にリネームされるため、呼び出し側の同名変数を変数捕捉しません。
一方で、`defun`、`export`、`data` のようなトップレベル名は自動では改名されません。
== 文字列と文字
_chars_ はStringから(List Char)へ変換します。
[source, lisp]
----
; (Pure (-> (String) (List Char)))
(chars "Hello") ; '(`H` `e` `l` `l` `o`)
----
_str_ は(List Char)からStringへ変換します。
[source, lisp]
----
; (Pure (-> ((List Char)) String))
(str '(`H` `e` `l` `l` `o`)) ; "Hello"
----
== 外部関数呼び出し
_blisp::embedded_ は、外部関数呼び出し用のマクロです。
このマクロを利用すると、Rustの関数をBLispから容易に呼び出せるようになります。
たとえば、はじめに、Rustの関数を以下のように定義します。
[source, 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から呼び出せます。
[source, lisp]
----
(export call_add_four_ints (n)
(IO (-> ((Option Int)) (Result Int String)))
(add_four_ints 1 [2 3] n))
----
外部関数を登録するためには、以下のように、 _embedded_ によって生成される型定義のベクタを
_blisp::init_ に渡します。
[source, rust]
----
// 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_ マクロが生成する関数によって自動的に行われます。
.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>_
|===
== Coqへのトランスパイラ (実験的)
BLispは実験的にCoqへのトランスパイラを実装しています。
トランスパイラは、以下のように _blisp::transpile_ を呼び出すことで実行されます。
[source, coq]
----
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のプレリュードも含まれます。
[source, coq]
----
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が解釈できません。
その場合は、手動でソースコードを修正してください。
簡単にできるはずです。
== 例
=== リバース
_reverse_ は内部で定義されている関数です。この関数はリストを反転します。
[source, lisp]
----
(reverse '(1 2 3 4 5 6 7 8 9))
----
このコードの出力は以下の通りです。
'(9 8 7 6 5 4 3 2 1)
=== Filter
_filter_ は内部で定義されている関数です。この関数はリストの中身をフィルターします。
[source, lisp]
----
(filter (lambda (x) (= (% x 2) 0)) '(1 2 3 4 5 6 7 8 9))
----
このコードの出力は以下の通りです。
'(2 4 6 8)
_filter_' の型は以下の通りです。
[source, lisp]
----
(Pure (->
((Pure (-> (t) Bool)) ; 関数を引数にとる
'(t)) ; リストを引数にとる
'(t))) ; リストをリターン
----
=== 階乗
末尾呼び出し版の階乗関数は、以下のように実装できます。
[source, lisp]
----
(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