橋本 Hashimoto   麦Baku

橋本 Hashimoto   麦Baku

Glisp v2: Documentation (Scratchpad)

This page is a personal scratchpad.

2023年2月現在 https://glisp.app で動いている言語仕様から大幅に改変したい。

有識者からの助言を仰げるのではないかと思ったので、実装よりも先に仕様を書いておきます。
まだ書いてる最中です。所々ドキュメントというより独り言になってるし、文章も途切れてる。

https://github.com/baku89/glisp-lang

全体的な設計思想

  • 言語の風味はS式を用いたJavaScript
    • 予約語や演算子、基礎的なデータ操作関数などは、JavaScriptの命名を優先する
    • Lisp的な要素についてはClojureを、関数型言語的な要素についてはHaskellなどを参考にする
  • Code as Data: 逐次実行されるプログラムではなく、declarativeなデータ
    • 実行順といった時制概念が無い
    • シンボル名は「値の容れ物」ではなく、「式に紐付けられた名前」。再代入という考え方が無い
    • ASTのどの部分からも評価を始めることができる
    • すべての式が何らかの値に評価される。副作用を伴う「文」は存在しない。
  • 型検査のサポート
    • エラー耐性: 型の不一致や、実行時エラーが生じた場合においても、型に応じてできるだけ「それらしい」デフォルト値を返すようにする
      • (+ 1 2 "str") は 3 に評価される
      • (* 1 2 "str") は 2 に評価される
      • この2つの例からも分かるように、同じ数値型でもそのデフォルト値を任意に定めることができる
    • GUIのためのメタデータ: Glispの型は「データが意味論的に何であるか」という従来の意味に加えて、GUIとして表示するための付加情報を含めて型情報として扱う
  • 言語仕様は最小に
    • 予約語には英語ではなく記号を記号を用いる（e.g. fn は =>）
    • 普通の言語であれば予約語として扱うものを、可能な限りただのシンボルとして扱う
      • e.g. if, true, false などは Preludeモジュールで宣言されている。
      • 名前を下位のスコープで上書きした場合はどうするの? → Warningを出すとともに、Preludeを参照するためのパス参照（後述）をサポートする
  • あまり頑張らない
    • 親切な糖衣構文や略記法、高度な関数型言語機能を提供しようと無理をすることでこんがらがない
    • まずは完成させる

Termiology

  • 式（expression, expr）: 何らかの値を返すためのプログラム。JSでいえば 1 + 2 や true || false など。Glispはすべてのプログラムが式です。
  • 文（statement）: 副作用を伴う、値を返さないプログラム。JSでいえば if文など。Glispには存在しません。
  • 値（value): Glispの評価によって得られるデータ。glisp-langでは、ASTとしての 0 とその式が返す値としての 0 とをデータ上厳密に区別します。
  • リスト: 構文上リストのように見える式全てを指します。

前提

  • 知っていること：
    • LispのS式
    • 「正格評価」「遅延評価」
    • Haskellなど関数型言語の基礎的な知識
  • https://glisp.app のような、お絵かきツールと統合されたライブラリの存在を仮定しています。（path/d関数など）

リテラル

言語の構文としてサポートしているのは数値型と文字列型のみです。

;; 数値型
10
-4
+200
2.4
Infinity
NaN
-Infinity

;; 基数の異なる整数型
0xff ; 未実装
0b100 ; 未実装 

;; 文字列型
"This is a atring"

true, false, null といった、通常の言語では予約語とされるような式も、Glispの場合はただのシンボルとして扱われます。

単位付き数値リテラル

2.1e4 のような記法もサポートしています。内部的には ($e 2.1 4) の糖衣構文として扱われます。

2.1e4   ; ($e 2.1 4) 多分指数表記
100%    ; ($% 100)   多分百分率
45deg   ; ($deg 45)
1.5turn ; ($turn 1.5)
3/40    ; ($/ 3 40)
3V3     ; ($V 3 3)
2...4   ; ($... 2 4)

ベクタ

配列やタプルは以下のように記述します。異なる型（後述）を混ぜたり、入れ子にすることも可能です。

[1 2 3]
[]
<a href="1%5D%20%5B2">1] [2</a>
["hello" false]
[(+ 1 2) (! false)]

辞書

{a: 10 b: 20}
{a: 10 b: {x: "apple" y: "banana"}}

シンボル

大文字と小文字を区別します。

foo                 ; A symbol named ‘foo’.
FOO                 ; A symbol named ‘FOO’, different from ‘foo’.
1+                  ; A symbol named ‘1+’
                    ;   (not ‘+1’, which is an integer).
+-*/_!$%^&=<>@      ; A symbol named ‘+-*/_!$%^&=:<>@’.
                    ;   These characters need not be escaped.
;; シンボルのエスケープはまだ未実装                    
\+1                 ; A symbol named ‘+1’
                    ;   (not a very readable name).
\(*\ 1\ 2\)         ; A symbol named ‘(* 1 2)’ (a worse name).

Ref: Symbol Type (GNU Emacs Lisp)

ただし、以下は予約語のため使えません。

=>     ; 関数式
@      ; 直近の祖先のlet式を参照
let    ; let式宣言
return ; let式中のreturn式を参照
data   ; 代数的データ型宣言
struct
union  ; ユニオン型
type   ; 型が期待されるコンテクスト以外の場所で型であることを明示するためのキーワード
enum
struct
interface
default
Never  ; Never型

適用式

いわゆる「関数呼び出し」は以下のように行います。引数の余剰分は無視されます。

(+ 1 2)
(Vec2 2 2)

ラムダ計算や関数型言語に触れていない限り耳馴染みのない関数適用（function application）という言葉を用いるのは、「サブルーチンの実行」という逐次的なイメージはGlispの設計思想に合わないからです。

シンボルとスコープ

スコープや変数の宣言は

(let シンボル名1: 式1 シンボル名2: 式2 ... 返り式)

のように記述します。例えばこのように。

(let x: 1
     y: 2
     (+ x y)) ; Evaluates to 3

返り式は必須ではありません。その場合、スコープ式全体は「空」を表すユニット値 () を返します。

また、シンボルに束縛された式は、その宣言順を問わず前後から参照することができます。

(let x: (+ y 2)
     y: 1]
     x) ; Evaluates to 3

スコープ式は入れ子にすることもできます。それぞれの式に同じ名前のシンボルが宣言されている場合、より内側のlet式における宣言が優先されます。

(let x: 10
     y: (let x: 20
             x) ;; x evaluates to 20
     x) ; x evaluates to 10

Glispにおけるシンボルは、一般的なプログラミング言語における変数名のような「値の容れ物」ではなく、「特定の式につけられた名前」です。例えばJSの場合、 const x = 2 * 3 という文が実行された時 xという変数名に右辺の実行結果 3 が代入されます。Glispにおける同等の式 (let x:　(* 2 3)) における x は (* 2 3) という式を参照するための単なる別名に過ぎません。また、多くの言語では代入式の右辺は正格評価されますが、Glispの場合はxが指し示す式の評価後の値が実際に必要とされるまで評価が遅延されます。

以下の例において、スコ０府式全体を評価した場合は (very-heavy-numeric-computation 10) は参照されないため、その評価は一瞬で終わります。一方 (+ x 2) を評価した場合には、シンボル名 x を介してそのとても重い数値計算が実行されます。

(let x: (very-heavy-numeric-computation 10)]
     y: (+ x 2)
     (* 2 3))

Glispにおけるシンボルは「式につけられた名前」であるため、以下のような再代入を意図したコードは不正となります。

(let x: 10
     x: (+ x 1)])

循環参照も出来ません。以下のような式もエラーです。

(let x: 1
     (let x: (+ x 1) ; 外側のlet式でxが宣言されている場合でも、内側のlet式のxは自己参照しているためエラー
          x))

(let x: y
     y: x
     x) ; xとyとが循環参照をしているためエラー

※ 再帰的定義はできるようにしたいです。例えばこんな感じに:

; Binary Tree. Haskellでいう
; data Tree a = Nil | Node a (Tree a) (Tree a)
(let Tree: (data [a] Nil (Node a (Tree a) (Tree a)))

関数宣言

以下のように記述します。仮引数名には必ず後述の型をアノテーションしないといけません。戻り値を省略した場合、自動的に型推論されます。

; (=> [:仮引数1 型1　:仮引数2 型2　...:可変長引数 可変長引数の型]: 戻り値
;     (関数本体))

; 例
(=> [x: Number]: Number (* x x)) ; square
(=> [x: Number y: Number]: Number (/ x y)) ; divide
 
; 可変長引数
(=> [...:xs Number] (reduce + xs 0)) ; sum

; 多相関数
; typeclassやinterfaceが無いので、型変数をall型以外の型に制約する文法は今の所なし
(=> (T) [x: T y: T] [x y])
(=> (A B C) [f: (=> [a: A]: B)
             g: (=> [b: B]: C)]
    (=> [a: A] (g (f a))))  
    
; >=> で、2引数関数をfoldl（左畳み込み）の要領で多引数関数っぽく扱える
compose: (>=> (T U V) [f:(=> [x:T]: U) g:(=> [y:U]: z:V)]
              (=> [x:T] (g (f x))))
(compose inc even? not)
; (compose (compose inc even?) not) と同じ意味

マッチ式

RustやPHPのマッチ式に対応するものです。ifやswitch分の一般化といえます。

(switch name: expr
        case1: ret1
        case2: ret2
        ...
        default)

name は、exprの評価結果の別名です。retやdefault内で参照された場合、対応するcaseの型との交差型に推論されます。

例えば以下のようにです。

(match x: (if true 1 "hello") ; ここでのxは (union 1 "hello") 型
  Number: (+ x 2)     ; (intersect xは1に推論さえる
  String: (++ x "!")) ; xは"helloに推論される

順序も関係します。

(let suffix: (match x: 2
               1: "st"
               2: "nd"
               3: "rd"
            "th") ; evaluates to "nd"
     (++ x suffix))  ; -> "2nd"

exprは省略可能です。その場合、name はより外側のスコープで宣言された同名の式に束縛されます。
また、caseやdefaultでキャプチャしきれなかった型があった場合には ()を返します。

(match x ;; xはNumber型
     -1: "one") ; -> ()

その他、一切交差しない型がある場合は、warningを出します。

(match a: (+ 2 3)
  1: "one"
  1: "one again"   ; Unreachable as `1` has already matched
  String: "string" ; Unreachable as String is not a subtype of Number
  Number: "number"
  _: "others")     ; Unreachable as all possible types have consumed

defaultも省略可能です。

(match .

型

Glispは型を持ちます。以下がその一覧です（Glisp v2： Why strong type？）

  • All型: すべての型のスーパータイプ
    • ユニット()
    • プリミティブ型
      • 例： Number、String
      • プリミティブ値
    • 関数型
      • 例：(=> [x:Number]: Number)
    • (代数的データ型)
      • 列挙型
        • 例：(enum {true false})
      • 直積型
        • 例：(struct [x:Number y:Number])
    • ベクタ型
      • 例： [Number Number]、[...String]
    • 辞書型
      • 例：{name: String}、{...Number}
    • ユニオン型
      • 例：(union String Number)
  • Never型: いわゆるボトム型。すべての型のサブタイプ

すべての値は何らかの型に属します。例えば1 や "hello" という値はビルトインのプリミティブ型 Number と String にそれぞれ属します。すべての型はトップ型のサブタイプであり、またNeverはすべての型の部分型です。

GlispではNumber String のような「型を表す値」をその他の値と同様に扱うことができます。つまり、適用式の引数として渡したり、別のシンボル名に束縛することができるということです。「型を表す値」のみが属する型は存在せず、All型に直接属します。

また、1や"hello"といった値も、その値自身のみからなる型として扱うことも出来ます。つまり、Glispにおけるすべての値は型としての意味も併せ持ちます。

トップ型

すべての型が属する型です。_（アンダースコア）一文字で表します。

TypeScriptのany型と似ていますが、any型がすべての型のサブタイプでありスーパータイプであるのに対し、Glispのトップ型はすべての型のスーパータイプであるのみで、トップ型自身を除くどの型のサブタイプでもありません。

関数適用において、トップ型が期待される引数には任意の型の値を渡すことはできます。しかしトップ型以外の型（例えば Number）が期待される引数に、トップ型の値を渡すことはできません。対照的に、TypeScriptの場合はNumber型の引数にany型の値を渡すことが可能です。

ユニット

ユニットは，特に意味のある値がない状況で使われる値です。リテラルは ()と書き，型も同じく()と書きます。（参考）

Glispにおけるユニットはエラーが起こった際のデフォルト値として使われます。またユニット型はどの型のサブタイプでもありませんが、引数として渡した場合にエラーが発生しません。

プリミティブ型

プリミティブ型はホスト言語（JavaScript）のオブジェクトを直接表現するのに使います。

  • JSにおけるプリミティブ型： 文字列、数値
  • Image, DOM、ArrayBufferなどブラウザやNode.JS環境におけるビルトイン・オブジェクト
  • Paper.Path、THREE.Mesh、色など、ライブラリ上のオブジェクト

上記のうち、数値と文字列のみ 2や "Hello"など専用のリテラルによって文字列から直接パースすることが出来る特別なプリミティブ型といえます。

専用のリテラルが用意されていないプリミティブ型をユーザー定義する場合、値を「それ自身に評価される式」に変換する処理を実装しなくてはいけません。多くの場合、その型に属するあらゆる値を生成することの出来るコンストラクタ関数の適用式となります。

例えば、1px四方の透明ピクセルを表すImage型のためのリテラルはGlispに存在しませんが、

(image/base64 "data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7")

などといった形で表現することができます。

(svg/d "M0,0 H10 V10 H-10 Z")

※ REPLのprint関数は「値をそれ自身に評価される式を表すASTに変換し、さらに そのASTを文字列として出力する」実装となっています。

ちなみにプリミティブ型はその宣言時に階層構造を持たせることもできます。

ベクタ型

[Number Number]    ; 要素数2のNumber型からなるベクタ
[...Number]        ; Number型おみから成るベクタ。要素数は問わない
[Number Number?]   ; 要素数が1または2の数値型からなるベクタ
[String ...Number] ; 1番目の要素がString、それ以後の要素がNumber型のベクタ

辞書型

{a: Number}
{...Number}           ; キーすべてが数値型
{a: String ...Number} ;　キー「a」のみ文字列型、それ以外は数値型

関数型

「関数の型」のことです。通常の関数宣言から本体部を除くと関数型と見なされます。

(=> [x:Number y:Number]: Number)

言語実装の話: 型推論

すべての式は以下の手順で再帰的に型推論することができます。

  • 適用式：その関数の型の戻り値　（e.g. (+ 1 2) → Number）
  • let式：return式の型。無ければユニット型
  • quote式：quoteされている式の型
  • それ以外：その式自身の値

例えば、1 という式は 1 自身に推論されます。Glispでは型を表す値以外のすべての値が「その値のみからなるシングルトン型」としての意味も併せ持ちます。

型メゾッド

Primitive型、Enum型はその定義時にメゾッドを宣言することも出来ます。

メタデータ

値メタデータ

Glispでは、以下の構文を用いて値にメタデータを付加することができます。

 ^dict expr

メタデータはその値が表す型に対する付加情報として用いられます。例えば、型のデフォルト値、説明文、数値スライダーとして表示された際の最小・最大値などが含まれます。

; meta部は辞書値でなくてはいけません
^{default: 0} Number

; expr部は「型を表す値」を返す任意の式をセットすることも出来ます
^{default: "" label: "Content"} (if true String Number)

; meta部を辞書値を返す式にすることも出来ます
^(merge metaA metaB) _

Glispのすべての値はイミュータブルなので、^{doc: "This is Number"} NumberはオリジナルのNumberの値には影響しません。その代わり、メタデータを付加されたNumber のコピーが返されます。

メタデータは繰り返し付加することができます。その際、メタデータとして設定された辞書はマージされます。

A: ^{default: 2 doc: "Number"} ^{default: 1} Number
; The metadata of A {default: 2 number doc: Number}

メタデータは

以下のように、型を繰り返し継承しながらメタデータを付加することも出来ます。

(let ; UI上の数値スライダーで負の値を設定出来ない値を作る
     PositiveNumber:   ^{doc: "This is a number" min: 0} Number
     ; PositiveNumberを継承し、0-1の範囲で使えるスライダーを
     NormalizedNumber: ^{doc: "Normalized number" max: 1} PositiveNumber

(let [Number1 ^{default: 1} Number
      divide (=> [x: ^{doc: "Dividend"} Number1
                  y: ^{doc: "Divisor"} Number1]
                 (/ x y))])

デフォルト値

型メタデータのうち、default にセットされた値は、その型のデフォルト値として使用されます。例えば、関数適用において引数の型が合わないときなどに使われます。

square: (=> [x: ^{default: 1}Number] (* x x))

> (square "text") ; String型なので、xのデフォルト値 1 が代わりに使われる
< 1

式メタデータ

式メタデータは、値ではなく、式にメタデータを付加するために用います。

#id? dict expr

#Circle0(circle [0 0] 100)
#Add0{pos: [10 10] collapsed: true}(+ 2 4)

値メタデータと異なり、辞書値の中身は評価後の値に一切影響しません。ASTをGUIとして表示するために必要な付加情報のみを扱います。

Quote式

式に```（バッククオート）を前置することで、評価後の値ではなく、式そのものについて言及することができます。

`(+ 1 2)

例えば「円オブジェクトをアートボードに配置する」スクリプトを記述する際にはこのようにします。

(add-item `(path/circle [50 50] 25))

もしこれをquote無しで記述した場合、add-itemの引数は正格評価されるため、(path/circle [50 50] 25)の評価結果である (path/d "M25,50 a 25,25 0 1,1 50,0 a25,25 0 1,1 -50,0")がアートボード追加されてしまいます。

また、quoteされた式の中で ~（チルダ）を前置した式は評価されます。先の例でいうと

(add-item `(path/circle [50 50] ~(* 5 5)))

とした場合は、(* 5 5)の部分が先んじて評価され、アートボードには(path/circle [50 50] 25)が追加されます。

1-Step Evaluation

一般的なLisp方言の場合、 \(1 2 3)というquote式が評価されると(1 2 3)というリストを返し、それ以上評価が進むことはありません。この仕様を用いてデータとしてのリストを表現するのが慣例です。 Glispは、quote式の評価後の値に適用式()` が含まれる限り、評価が繰り返し行われます。例えば以下のような2乗関数が定義されたとき:

square: (=> [x: Number] `(* ~x ~x))

式 (square 4)は以下のような順序で多段階に評価されます。

(square (+ 1 3))
(* (+ 1 3) (+ 1 3))
(* 4 4)
16

もう一つ例を挙げると、このような正方形パスを返す関数があるとします。

path/square (=> [width: Number]
                `(path/poly [0 0] [~width 0] [~width ~width] [0 ~width]))

この場合、式 (path/square (+ 10 1) は次のようなステップで評価されます。

(path/square (+ 10 1))
(path/poly [0 0] [(+ 10 1) 0] [(+ 10 1) (+ 10 1)] [0 (+ 10 1)])
(path/poly [0 0] [11 0] [11 11] [0 11])
(path/d "M0,0 H11 V11 H-11 Z")

通常この多段階評価の途中過程をユーザーが目にすることはありませんが、Glispでは敢えて1ステップで評価を止めることも可能です。上記のパスの例でいうと、正方形を表すパスオブジェクトが4つの頂点を持つ多角形パスオブジェクトに分解され、最後には頂点や接線を自由に設定できるただのパスへと分解される様子がわかります。

これはデザインツールにおける Bake をプログラミング言語において実装したものといえます。また、Clojureのmacroexpandにも似ています。

値ではなく式をデフォルト値にする

mat2d/*:
(=> [...ms: ^{default: [`(mat2d/translate (Vec2 0 0)])
                        `(mat2d/rotate 0deg)
                        `(mat2d/scale (Vec2 0 0))]}
            Mat2d]
    (...))

パス構文

GlispのASTは、すべての式にパスが割り振られています。そのため、let式でシンボルを宣言せずとも以下のように式を相互参照することができます。

(path/circle [../r ../r] 10)

../ はお察しの通り、ベクタ式 [../r ../r] の一つ外側の関数適用式 (path/circle ...) を参照するための相対パスです。半径を表すであろう引数10 を r にという名前で参照できるのは、path/circle 関数の定義がこのようになっているからです。

(=> [c:Vec2 r:Number] (...))

これまで登場したシンボル x のような記法も「スコープ式によってx に束縛された式のうち、直近の祖先」を参照せよというパス構文の一つに過ぎません。パス構文では以下のような記法を用いることができます。

  • xスコープ式によってx に束縛された式のうち、直近の祖先のもの
  • ..x: スコープ式によってxに束縛された式のうち、2番目に直近の祖先のもの
  • ..x/..x: スコープ式によってxに束縛された式のうち、3番目に直近の祖先のもの
  • ../：親ノード
  • ./ : 現在のノード
  • 1: その式の3つめの要素
  • @1:関数適用における 可変長引数部分の2つめの式
  • name: （他のパスの後に続けて）
    • 関数適用式: 実引数のうち、仮引数名がnameの式
    • スコープ式: name に束縛された式
    • 関数宣言式: 仮引数、もしくは型変数名がnameの式

未実装

  • ..#x/：祖先のうち、ID x が割り振られた直近のノード
  • ..Type/：祖先のうち、型Type に推論されるノード
  • / ：Preludeモジュールを表す。/のみだと除算演算子を意味するので、続くパスを後置して用います
  • @: 祖先ノードの
  • return：let式からみたreturn式。通常、@/return のようにして扱います
  • =>：関数適用式からみた関数への参照

先述のとおり、関数適用式の引数は、その関数宣言の仮引数名によって参照することができます。

(circle [x y] z)
;             ^この位置から各ASTを参照する
./c   ; [x y]
./=>  ; circle

 (circle [x y] z) 
 ;        ^この位置から各ASTを参照する
 ./1   ; y
 ../r  ; r
 ../=> ; circle

しれっと ./1 などが登場しましたが、ベクタ式の要素を参照するためのものです。./-n など負の数を指定した場合はベクタの最後からn番目の要素を参照することもできます。

同様に、辞書式の要素もキーによって参照できます。

{x: 10
 y: {a: 20}
 z: 4}
;   ^この位置から各ASTを参照する
./x        ; 10
./y/a      ; 20
./y/a/../x ; 10 (潜って登って、という参照の往復も表現できます。特に使い所はありませんが）

パターンマッチング

パターンマッチと同時に変数のキャプチャはできない仕様です。

n: (+ 1 2)

(match n
       0: "zero"
       1: "one"
       2: "two"
       false) ; Inferred to (union 0 1 2 false)
 
 (match n
        Number: true
        String: false) ; 到達し得ないコード
        
; ifの実装はこんな感じにできます。
if: (=> (T)
        [cond: _ then: T else: T]
        (match (isTruthy cond)
               true: then
               else))

モジュール

le式の内側を書きます。Return式にexportする式を辞書にします。defaultキーは特別で、モジュール全体を参照されたときに返す値を指します。

; ファイルの最初の辞書型は
^{doc: "2 dimentional vector"}

Mat2d: (import "./Mat2d.glisp")

x: (=> [v: Vec2] (nth v 0))
y: (=> [v: Vec2] (nth v 1))

Vec2: (type [Number Number])
Vec2_+: (=> [a: Vec2 b: Vec2]: Vec2 [(+ (x a) (x b)) (+ (y a) (y b))])
Vec2_dot: (=> [a: Vec2 y: Vec2] (+ (* (x a) (x b))
                                   (* (y a) (y b))))

{default: Vec2
 +:       Vec2_+
 dot:     Vec2_dot}

(let Vec2: (import "./Vec2.glisp")
     (Vec2/+ [1 2] [3 4]))

(let