自作プログラミング言語を初級者が1週間で作る方法 (6) レコードと中置関数

自作プログラミング言語をなるべく簡単に作る方法を紹介します。また、実際に自作プログラミング言語を作ってみます。

前回の記事の続きです。今回はレコードと中置関数を使えるようにします。

レコードを作れるようにする

レコードを作れるようにします。レコード（構造体、連想配列）は複数の変数を一つにまとめて扱うものです。Yuz 言語ではレコードを

let p = {x: 2, y: 3, z: 4};

のように作ることにします。これと同じことをする JavaScript のコードは

const p = Object.freeze({x: 2, y: 3, z: 4});

となります。Object.freeze() はオブジェクトを凍結して変更不可能にするものです。今回は値を変更する文法は作らないので念のため凍結しておきます。

レコードを作る文法は前回の記事の Primary のところに加えます。

Primary
  = Paren
  / Record
  / Float
  / Boolean
  / Identifier

Record
  = "{" _ head:KeyValue tail:(_ "," _ KeyValue)* _ "}" {
      const keyvalues = tail.reduce((acc, x) => `${acc}, ${x[3]}`, head);
      return `Object.freeze({${keyvalues}})`;
    }

KeyValue
  = i:Identifier _ ":" _ e:Expression {
      return `${i}: ${e}`;
    }

レコードを使えるようにする

次はレコードを使えるようにします。レコードを使うというのはレコードのメンバーの値を取得するということです。JavaScript と同様に

let p = {x: 2, y: 3, z: 4};
p.x + p.y + p.z

のように . を使ってメンバーの値を取得できるようにします。このプログラムは 2 + 3 + 4 なので 9 を返します。レコードのメンバーの値の取得は関数適用と同じ優先順位にしたいので前回の記事の CallExpression のところに加えます。

CallExpression
  = head:Primary tail:(_ Argument)* {
      return tail.reduce((acc, x) => `${acc}${x[1]}`, head);
    }

Argument
  = "[" _ e:Expression _ "]" { return `(${e})`; }
  / "." _ i:Identifier { return `.${i}`; }

• {x: 2, y: 3}.x や {f: \x -> x * 2}.f[3] は正しいプログラムです。
• 3.x や true.x は実行時エラーとなります。
• 10 + .x はパースエラーとなります。
• {x: 2, y: 3}.x.x や {x: 2, y: 3}.z は JavaScript の仕様により undefined となります。

中置関数

関数を二項演算子のように扱う文法を作ってみます。func[a][b] を a 'func' b と書けるようにします。たとえばベクトルを表すレコードとして

let a = {x: 2, y: 3, z: 4};
let b = {x: 7, y: 1, z: 0};
let c = {x: 11, y: 9, z: 2};

があるとします。そしてベクトルを足し算する関数 add を

let add = \v1 -> \v2 -> {
    x: v1.x + v2.x,
    y: v1.y + v2.y,
    z: v1.z + v2.z
};

のように作ったとします。これを使って三つのベクトル a、b、c を足し算すると

add[add[a][b]][c]

となりますが、関数を二項演算子として使うと a + b + c のような要領で

a 'add' b 'add' c

と書くことができます。

ところで二項演算子には左結合と右結合があります。二項演算子を連鎖させた a * b * c * d という式があったときに、左結合の演算子は

((a * b) * c) * d

のように左から順に計算します。一方、右結合の演算子は

a * (b * (c * d))

のように右から順に計算します。

右結合の演算子にはあまりなじみがないかもしれません。代表的なものは累乗です。言語によって異なりますが、累乗の演算子 ^ ** は右結合であることが多いです。

中置関数を a 'func' b と書いたときは左結合、a `func` b と書いたときは右結合になることにします。中置関数の優先順位はとりあえず比較演算と四則演算の間にしておきます。

優先順位	演算子	文法の名前	結合性
8	||	OrExpression	左結合
7	&&	AndExpression	左結合
6	== !=	EqualExpression	連鎖できない
5	>= > <= <	RelatExpression	連鎖できない
4	`func`	RFuncExpression	右結合
3	'func'	LFuncExpression	左結合
2	+ -	AddExpression	左結合
1	* / %	MultExpression	左結合

中置関数のコードは次のようになります。下記のコードで RFuncExpression の定義の中にもう一度 RFuncExpression を入れました。このような循環した定義にすると二項演算子を右結合で連鎖させることができます。

RFuncExpression
  = head:LFuncExpression tail:(_ RFuncOperator _ RFuncExpression)? {
      return tail === null ? head : `${tail[1]}(${head})(${tail[3]})`;
    }

RFuncOperator
  = "`" _ e:Expression _ "`" { return `(${e})`; }

LFuncExpression
  = head:AddExpression tail:(_ LFuncOperator _ AddExpression)* {
      return tail.reduce((acc, x) => `${x[1]}(${acc})(${x[3]})`, head);
    }

LFuncOperator
  = "'" _ e:Expression _ "'" { return `(${e})`; }

• func が二変数以上の関数でないとき a 'func' b は実行時エラーとなります。
• func が三変数以上の関数のとき b 'func[a]' c や (a 'func' b)[c] は正しいプログラムです。

実行例

レコードと中置関数の実行例です。ベクトルの足し算は次のようになります。

データ構造

レコードを使うとリストや二分木などのデータ構造を作ることができます。データ構造を扱うときには nil や null といった「からっぽ」を表すものがあると便利です。

そこで Yuz 言語で nil を使えるようにします。nil を予約語に加え、JavaScript の null に変換されるようにします。

Primary
  = Paren
  / Record
  / Float
  / Boolean
  / Nil
  / Identifier

Nil
  = "nil" !IdentifierContinue { return null; }

ReservedWord
  = ("let" / "true" / "false" / "nil" / "if" / "then" / "else") !IdentifierContinue

まとめ

今回はレコードと中置関数を使えるようにしました。次回は Yuz 言語の書き味を確かめてみるために、リストと高階関数についてのプログラムを実際に Yuz 言語で書いてみます。

今回までで作った Peggy のコードをまとめると次のようになります。164 行しかないとてもシンプルなコードになりました。Yuz 言語は一旦これで完成とします。

Start
  = _ p:Program _ { return eval(p); }

Program
  = vars:(Variable _ ";" _)* e:Expression {
      const varsCode = vars.reduce((acc, x) => `${acc}${x[0]}; `, "");
      const returnCode = `return ${e};`;
      return `(() => { ${varsCode}${returnCode} })()`;
    }

Variable
  = "let" __ i:Identifier _ "=" _ e:Expression {
      return `const ${i} = ${e}`;
    }

Expression
  = LambdaExpression
  / IfThenElseExpression
  / OrExpression

LambdaExpression
  = "\\" _ i:Identifier _ "->" _ e:Expression {
      return `${i} => ${e}`;
    }

IfThenElseExpression
  = "if" __ a:Expression __ "then" __ b:Expression __ "else" __ c:Expression {
      return `${a} ? ${b} : ${c}`;
    }

OrExpression
  = head:AndExpression tail:(_ OrOperator _ AndExpression)* {
      return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
    }

OrOperator
  = "||"

AndExpression
  = head:EqualExpression tail:(_ AndOperator _ EqualExpression)* {
      return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
    }

AndOperator
  = "&&"

EqualExpression
  = head:RelatExpression tail:(_ EqualOperator _ RelatExpression)? {
      return tail === null ? head : `(${head}) ${tail[1]} (${tail[3]})`;
    }

EqualOperator
  = "==" { return "==="; }
  / "!=" { return "!=="; }

RelatExpression
  = head:RFuncExpression tail:(_ RelatOperator _ RFuncExpression)? {
      return tail === null ? head : `(${head}) ${tail[1]} (${tail[3]})`;
    }

RelatOperator
  = ">="
  / ">"
  / "<="
  / "<"

RFuncExpression
  = head:LFuncExpression tail:(_ RFuncOperator _ RFuncExpression)? {
      return tail === null ? head : `${tail[1]}(${head})(${tail[3]})`;
    }

RFuncOperator
  = "`" _ e:Expression _ "`" { return `(${e})`; }

LFuncExpression
  = head:AddExpression tail:(_ LFuncOperator _ AddExpression)* {
      return tail.reduce((acc, x) => `${x[1]}(${acc})(${x[3]})`, head);
    }

LFuncOperator
  = "'" _ e:Expression _ "'" { return `(${e})`; }

AddExpression
  = head:MultExpression tail:(_ AddOperator _ MultExpression)* {
      return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
    }

AddOperator
  = "+"
  / "-"

MultExpression
  = head:CallExpression tail:(_ MultOperator _ CallExpression)* {
      return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
    }

MultOperator
  = "*"
  / "/"
  / "%"

CallExpression
  = head:Primary tail:(_ Argument)* {
      return tail.reduce((acc, x) => `${acc}${x[1]}`, head);
    }

Argument
  = "[" _ e:Expression _ "]" { return `(${e})`; }
  / "." _ i:Identifier { return `.${i}`; }

Primary
  = Paren
  / Record
  / Float
  / Boolean
  / Nil
  / Identifier

Paren
  = "(" _ p:Program _ ")" { return `(${p})`; }

Record
  = "{" _ head:KeyValue tail:(_ "," _ KeyValue)* _ "}" {
      const keyvalues = tail.reduce((acc, x) => `${acc}, ${x[3]}`, head);
      return `Object.freeze({${keyvalues}})`;
    }

KeyValue
  = i:Identifier _ ":" _ e:Expression {
      return `${i}: ${e}`;
    }

Float
  = Integer ("." [0-9]+)? { return text(); }

Integer
  = [1-9] [0-9]* { return text(); }
  / "0"

Boolean
  = ("true" / "false") !IdentifierContinue { return text(); }

Nil
  = "nil" !IdentifierContinue { return null; }

Identifier
  = !ReservedWord IdentifierStart IdentifierContinue* {
      return `$${text()}`;
    }

ReservedWord
  = ("let" / "true" / "false" / "nil" / "if" / "then" / "else") !IdentifierContinue

IdentifierStart
  = [A-Za-z_]

IdentifierContinue
  = [0-9A-Za-z_]

__
  = [ \t\n\r]+

_
  = [ \t\n\r]*