Glisp v2: Language Implementation

Termiology

  • Symbol: シンボル。Identifierだと、後々式IDと被ってしまう
  • Expr: 式
  • Param: 仮引数
  • Arg: 実引数
  • Prim: プリミティブ型
  • Fn: 関数
  • TypeVar: 型変数
  • items: とりあえず子要素は何でも。むやみに気の利いたネーミングにしない

指針 

  • 無闇やたらに識別子を短くしようとしない
    • LiteralをLitとか
  • 効率化のためのキャッシュはしない。Single Source of Truthを心がける
    • 親の式がどのキー、何番目のインデックスで自らの式を保持しているかをキャッシュしたい気持ちを振り切る
  • JavaScript風を大事にする
  • Glispモジュールは階層を持たせない
    • ExprとValueの命名を被せない
      • Expr側にはDef、Literalなどを適宜乗せる
        • どっちよ? 全部リテラルっちゃリテラルでしょう
        • ダサいけどprefixをつける
          • FnExpr, StringExpr

評価機

EnvにUnifiedされた型引数を追加すべき?

現状、実引数のみを渡している。

シンタックス

パーサーについて

  • 出来る限りあらゆるコードをパース可能とする
    • キーや仮引数名の重複は実行時にエラーを投げる（追々）
  • 重複したラベル付きリスト（辞書式や関数宣言式の仮引数部）の扱い
    • Record<string, Expr>で持っているので、そもそもそういうASTを表現出来ない
    • Entiresとして持つ方が良いのかも。まぁ、一旦無視。

List

関数適用式、ベクタ式などのリストのこと。カッコと要素はスペースを詰めても構わないが、要素間はかならずデリミタを入れることとします。そうすることで、要素をGUI側からエディット後にprint() した際、前後の要素と結合して意味が変わるのを防ぎます。（まだ未実装）

  • (a[]b) という式の[]をbに変更したとき、(abc)に変わってしまう
  • ([]>) の []を=に変更したとき、(=>)となりパースエラー

2つ組

辞書のキーと値、let式のシンボルと束縛される式、関数定義の仮引数名と型など、必ず対となる構文要素はA: B のような形とします。

こうすることで、後々仮引数を型推論できるようになったり、ES6のShorthand Properties構文のような略記法をサポートした時など、2つ組の右辺を省略できるような際には単にコロンを省けば良しとすることができます。match式やstruct式など、2つ組の片一方を将来的に省くことが想定出来ない場合にも、「構文上の2つ組はA: Bと表す」というルールを一貫させることで、記述は1文字冗長になったとしても構文をシンプルにすることを優先します。

また、CSTの実装を簡略化するための、キーと:の間にスペースを入れるとパースエラーとすることとします。

  • OK: key: value key:value [x:X]:X
  • Error: key : value [x:X] : X

Astのカテゴライズ

Astは意味ではなく、構文でカテゴライズするようにします。
例えば()と(+ 1 2)は意味論的に全く異なりますが、いずれも「括弧を用いたリスト状のリテラル」を表すAppを用います。[1 2 3]も[...Number]もいずれもVecLiteralを用います。

また、ASTの階層は出来る限り()や[]といったリストに対応するようにします。（メタデータを除く）
例えば関数宣言は(=> (型変数) [仮引数] (本体)) のような形となりますが、型変数部はTypeVars、仮引数部はParamというASTオブジェクトとして表現されます。

評価機について

  • 出来るだけevalはしない
  • 「型」については必ずevalする
    • (=> [x:Number]: (union 1 2)) という関数型が合った時、戻り値の型である(union 1 2)はevalしなくてはならない

Ast階層

  • →は単方向への参照
  • ⇔は双方向への参照
  • Dotted arrow: a reference to parent
  • Rectagnle node: Ast
  • Rounded rectangle node: non-AST object
  • Stadium-shaped node:literal
  • Hexagon node: Null

Let

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

FnDef

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

Print関数

Astにのみprint関数が存在します。
すべての値は、「その値自身に評価される式」を生成するメゾッド toExpr を持ちます。
（つまり、ユーザー定義されたプリミティブ型については、ユーザーがtoExprを定義する義務が課せられます）

「その値自身に評価される式」を生成するには、その式が既存のASTのどこを起点とするかという情報が必要になります。

値のprint関数の実体は、this.toAst(baseAst).print()です。

値は、自らが生成された式への参照を保持します。（BaseValue.originalAst）

正規形

それ以上評価できない式を指します。

  • Enum, struct, 関数の定義部
  • Primitive型
  • 上記を指し示すシンボル

enumやstructの定義部や、それを指し示すシンボルはそれ以上評価することの出来ない正規形です。

もし (enum [true false]) を指し示すシンボル Boolean が、更に (enum [true false]) に評価されたら、それはオリジナルのBooleanとは異なる新しい列挙型の定義式となってしまいます。

Interop

値は出来るだけそのままの名前、AstはプレフィクスAstをつける。すべてのオブジェクトはGlispパッケージ以下にexportされている。cod

Glispの関数のホスト言語による実装はこんな感じ。引数の.valueにアクセスすると正格評価され、

// if関数の実装
type Fn = (...args: Glisp.Arg) => Glisp.Value
function(test: Glisp.Arg, then: Glisp.Arg, _else: Glisp.Arg) {
    return Glisp.isTruthy(test.value) ? then.value : _else.value
}
function(f: Glisp.Arg, coll: Glisp.Arg) {
    const _f = f.value
    return Glisp.vector.of(
        ...coll.value.map((c, i) => _f(Glisp.arg(c), Glisp.Arg(Glisp.Number(i))))
    )
}
// (let x: 10 y: "apple" (if x 1 "else"))
scope(
  {
    x: number(10),
    y: string`apple`,
  },
  app(symbol`if`, symbol`x`, number(1), symbol`else`),
);

シンボル解決

Type Variables

型変数はGlobalコンテクストにおいて何に評価されてほしいか

二通りある

  • (=> (T) [x:T]: T)の T は型変数として評価されてほしい
  • (=> (T) [f: (=> [x:T]: T)]: T) のfにおけるTは型変数として評価されてほしい
  • (=> (T) [x: T] (=> [y: T] y)) の内側のT は () に評価されてほしい

代数的データ型（ADT; Algebraic Data Type）

本当はHaskellのADTのように、列挙型、直和型、直積型などをすべてdataキーワードで表現したいのですが、実装難度が高そうなので、列挙型と構造体のような直積型のみ扱えるものとします。カインド * -> * っぽいものも当分は実装しません。（Maybe、Eitherなど）

列挙型

Boolean: (enum [true false])

; Haskellと異なりdata constructorの名前は自動的に公開されません。参照するにはパス構文を用います。
true: Boolean/true
false: Boolean/false

Alignment: (enum [left center right justify])
LineCap: (enum [^{doc: "Butt"} butt
                ^{doc: "Round"} round
                ^{doc: "Square"} square]) ; data constructor毎にメタデータを付与

直積型

いわゆる構造体のようなものです。当分は実装せずにプリミティブを用います。

Vec2: (struct [x: Number y: Number] ; 構造体の中身
               zero: (self 0 0) ; クラス変数、関数のようなもの。Vec2/zero などでアクセスできる
               one: (self 1 1)
               +: (=> [...xs:self] (...)))

Mat2d: (struct [a: Number b: Number c: Number d: Number tx: Number ty: Number]
               identity: (self 1 0 0 1 0 0)
               translate: (=> [p: Vec2] (self 1 0 0 1 (.x p) (.y p))))

本当にやりたかったADT

Maybe: (data (T) [Just: [value: T]
                  Nothing])

> (Maybe/Just (+ 1 2)) ;; inferred to (Maybe Number)

Never型

いわゆるボトム型です。TypeScriptのneverと同様。

ユニオン型

いずれかの型を表現するものです。型理論でいう直和型にあたります。

(union Number String)
(union Number) ; evaluates to Number