SliP のご紹介と JavaScript での実装

0.始めに

こんにちは、SliP というプログラム言語を作っているものです。

SliP がどんな言語かというと、例えば 0 から 4 までの自然数の和を求めるプログラムは例えば以下のように再帰的に書けます。（もちろん再帰的じゃなくても書けます）

'sigma = '(
	@ == 0 ? [
		0
		( @ + ( @ - 1 ):sigma )
	]
);
4: sigma =

@ は引数を表します。@ が 0 なら 0 を、そうでなければ ( @ - 1 ) に sigma を適用したものに @ を足したもの、という求め方です。
SliP という名前から連想できる方もおられるかもしれませんが、非常に Lisp に影響をうけています。というか Lisp はとにかくカッコが多くて読みにくいんで、新しい文法を考えてしまおう、と思ったのが開発のきっかけです。

macOS のアプリに仕立てたものが以下のアドレスからダウンロードできます。

このアプリは Swift で書きましたが、この記事ではそのサブセットを JavaScript(node.js)で実装してみることにします。以下「JS版」といいます。
JS版の最終ソースはここにあります。

JS版のSliP を使って複数の数式をコピペして一気に計算できる、ついでにグラフィックまで描けちゃう電卓サイトを作ったので、もしよかったらみてやってください。

これに関する記事も書きました。

1.SliP のコンセプト

以下の型があります。

• 文字列(Literal)
• 数値(Numeric)
• 名前(Name)
• 辞書(Dict)
• リスト(List)
• 文(Sentence)
• 手続き(Procedure)
• 並行手続き(Parallel)
• 中置演算子(Infix)
• 単一引数関数(Unary)
• 前置演算子(Prefix)
• プリミティブ(Primitive)
• SliP

論理型はありません。条件判定をするときは値が [] (空のリスト、Nil と呼んでいます)かどうかで判断します。比較系のオペレータの値で Nil でないときは便宜的に SliP 型の唯一のオブジェクトである T が返されます。他の型は全て SliP 型を継承しています。

全てのオブジェクトは評価(Eval)するとオブジェクトを返します。Eval に渡される引数はコンテキスト（辞書チェーン）です。
また全てのオブジェクトは string メソッドを持ち、それは適切な文字列を返します。

JS版での実装（抜粋）

class
Context {
	constructor( _, next ) {
		this.dict = _
		this.next = next
	}
}

class
SliP {
	constructor( _ ) { this._ = _ }
	get
	string() { return 'T' }

	Eval( c ) { return this }
}

class
Numeric extends SliP {
	constructor( _ ) { super( _ ) }
	get
	string() { return String( this._ ) }
}

class
Literal extends SliP {
	constructor( _ ) { super( _ ) }
	get
	string() { return `"${this._}"` }
}

2.定数

SliP の定数とは、評価されるとそれ自身を返すオブジェクトです。以下のものがあります。

• 文字列(Literal)　例："ABC"
• 数値(Numeric)　例：123
• 辞書(Dict)　例："{"b":4}":dict
• リスト(List)　例：[ "A" 1 ]
• T　なんらかの空リスト([])でないオブジェクトを表します。

3.文と演算子

SliP の文は以下のような括弧にくくられた形をしてます。

( 1 + 2 )

この文の値は 3 です。

( 1 < 2 + 3 )

この文の値は T です。

( [ "A" "B" "C" ] : 2 )

この文の値は "C" です。他言語での [ "A", "B", "C" ][ 2 ] と同じ感じです。

中置演算子(infix operator)

+ とか < とか : は中置演算子と呼ばれます。以下にその名前と優先順位を示します。優先順位は小さいほど先に演算されることを意味します。左辺を l, 右辺を r で表します。

=  90 l に r を定義する
?  80 l が Nil でなければ r[ 0 ] を、そうでなければ r[ 1 ] を評価する
¿  80 l が Nil でなければ r を評価、そうでなければ Nil
&& 70 論理積
|| 70 論理和
^^ 70 排他的論理和
∈  60 l は r のメンバー
∋  60 r は l メンバー
== 60 l と r は等しい
<> 60 l と r は等しくない
<  60 l は r より小さい
>  60 l は r より大きい
<= 60 l は r 以下
>= 60 l は r 以上
,  50 ( "A", [ "B" "C" ] ) => [ "A" "B" "C" ](Lisp の cons)
&  40 ビット単位の論理積
|  40 ビット単位の論理和
^  40 ビット単位の排他的論理和
+  30 加算、数値、文字列、リストに適用
-  30 減算
×  20 乗算
÷  20 割り算
%  20 余り
:  10 適用
	( [ "A" "B" "C" ] : 2 ) => "C"
	( 0 : cos ) => 1
	( "{\"b\":4}" : dict : 'b ) => 4

乗算の名前は × です(Unicode の 0xD7)。 x(小文字のエックス) ではありません。

単一引数関数(unary function)

中置演算子':'の右辺には単一引数関数を置くことができます。以下にその名前と優先順位を示します。左辺を l, 右辺を r で表します。

! 評価したものを返します。
# リストのメンバーの数を返します。
* リストの最初のメンバーを除いたものを返します。(Lisp の cdr)
$ リストの最後のメンバーを返します。
· 文字列化したものを返します。
. 標準出力に表示します。引数をそのまま返します。
¦ 標準エラー出力に改行をつけて表示します。引数をそのまま返します。

アプリ版はこの他にも sin, cos のような数学関数などがインプリされています。

前置演算子(prefix operator)

前置演算子は以下のものがあります。前置演算子の優先度は中置演算子より高いです。

' 右辺をそのまま返します。クオートと呼ばれます。
¡ 右辺を例外として投げます。
~ 右辺をビット毎に反転したものを返します。
¬ 右辺を論理的に反転したものを返します。
` 右辺に2要素のリストをとり、0番目の要素である辞書をコンテクスト辞書チェーンの最初に付け加え、1番目の要素を評価したものを返します。

プリミティブ(primitive)

それだけで何かを返すものです。

@  引数(:オペレータの左辺)を返します。
@@ 引数リストを返します。
¤  コンテクスト（辞書チェーン）の最初の辞書をを内容とする辞書型のオブジェクトを返します。

JS 版の実装（抜粋）

const
_EvalSentence = ( c, _ ) => {
	switch ( _.length ) {
	case  0:
		return new List( _ )
	case  1:
		return _[ 0 ].Eval( c )
	case  2:
		break
	default:
		const wInfixIndices = Object.keys( _ ).filter( i => _[ i ] instanceof Infix ).map( _ => Number( _ ) )
		if ( wInfixIndices.length ) {
			const i = wInfixIndices.reduce(
				( a, c ) => _[ c ].priority >= _[ a ].priority ? c : a
			,	wInfixIndices[ 0 ]
			)
			if ( ( 0 < i ) && ( i < _.length - 1 ) ) {
				return _[ i ]._( c, _EvalSentence( c, _.slice( 0, i ) ), _EvalSentence( c, _.slice( i + 1 ) ) )
			}
		}
		break
	}
	throw `Syntax error: ${new _List( _ ).string}`
}

class
Sentence extends _List {
	constructor( _ ) { super( _ ) }
	get
	string() { return `( ${super.string} )` }

	Eval( c ) {
		return _EvalSentence( c, this._ )
	}
}

4.変数と名前とコンテキスト

コンテキストは辞書のチェーンです。後述の「手続き(procudure)」が実行される場合、チェーンの最初に新しい辞書が加えられます。
コンテキストの登録、参照にはキーとして名前が使われます。名前が評価されるとコンテキストの最初の辞書から参照しにいき、値が見つかればその値を返します。見つからなければチェーンの次の辞書を見にいき、次の辞書がなければ例外を投げます。
同じ名前でも値が違う場合があるので変数と呼ばれます。

名前にはほとんどの文字が使えます。使えない文字は以下のとおりです。

• 空白系　JavaScript の \s にマッチするもの
• 括弧系　[({«»})]
• オペレータに使われる文字　=,? など
• その他　;

JS 版の実装（抜粋）

class
Context {
	constructor( _, next ) {
		this.dict = _
		this.next = next
	}
}

class
Name extends SliP {
	constructor( _ ) { super( _ ) }
	get
	string() { return this._ }

	Eval( c ) {
		while ( c ) {
			const v = c.dict[ this._ ]
			if ( v ) return v
			c = c.next
		}
		throw `Undefined:${this._}`
	}
}

5.手続き(procudure)

手続きは複数の文(Sentence)を逐次処理するためのものです。また、これが評価されるとき、コンテキストの最初に新しい辞書が加えられます。各文の値のリストが返されます。

{	( 'a = 1 + 2 )
	( 'b = 3 + 4 )
	( a + b )
}

の値は

[ 3 7 10 ]

となります。

JS 版の実装（抜粋）

class
Procedure extends _List {
	constructor( _ ) { super( _ ) }
	get
	string() { return `{ ${super.string} }` }

	Eval( c ) {
		c = new Context( {}, c )
		return new List( this._.map( _ => _.Eval( c ) ) )
	}
}

6.並行手続き(Parallel)

並行手続きは複数の文を並行処理するものです。

«	( 'a = 4 )
	( 'a = 5 )
	( 'a = 6 )
»

の値は

[ 4 5 6 ]

となります。仕様ではこれの評価後の a の値は 4, 5, 6 のどれになるかは不定です。ただ、JS版での実装は上から逐次になっていて a は 6 になります。

7.糖衣構文

REPL(Read, Eval, Print Loop)のトップレベルだけ、糖衣構文を使うことができます。

最初にご紹介した以下のプログラムは糖衣構文です。

'sigma = '(
	@ == 0 ? [
		0
		( @ + ( @ - 1 ):sigma )
	]
);
4: sigma =

元の構文は

(	'sigma = '(
		@ == 0 ? [
			0
			( @ + ( @ - 1 ):sigma )
		]
	)
)
( 4: sigma :¦ )

です。

8.実際

おなじみのハノイの塔をやってみます。

'hanoi = '{
	( 'n	= @:0 )
	( 'from	= @:1 )
	( 'to	= @:2 )
	( 'via	= @:3 )
	(	n == 1
	?	[	( ( "From " + from:· + " To " + to:· ):¦ )
			{	( { ( n - 1 ) from via to }:hanoi )
				( ( "From " + from:· + " To " + to:· ):¦ )
				( { ( n - 1 ) via to from }:hanoi )
			}
		]
	)
};

　[ 3 "a" "b" "c" ]:hanoi;

3 枚の円盤を "a" の棒から "b" の棒へ "c" を経由して移すパターンです。
結果は以下のようになります。

"From a To b"
"From a To c"
"From b To c"
"From a To b"
"From c To a"
"From c To b"
"From a To b"

9.辞書型

辞書型のオブジェクトは2通りの生成の仕方があります。

辞書型の出力時の文字表現は辞書の内容を JSON にしたものになっています。
最初の方法は、JSON 文字列を内容として持つ文字型に dict オペレータを適用する方法です。

"{\"b\":\"4\"}" : dict : 'b =

結果は4となります。

次にコンテクストの最初の辞書から作る方法で、以下のように生成します。

'a = 3;
'add1 = '( @ + 1 );
¤ =

結果は {"a":"3","add1":"( @ + 1 )"} です。

¤ は現在のコンテクスト（辞書チェーン）の最初の辞書を内容とする辞書型のオブジェクトを返します。

JSON 辞書の値の辞書は SliP のプログラムとして読み込まれ、解釈された結果が値として登録されます。

なので：

3:( ( "{\"add2\":\"( @ + 2 )\"}" : dict ) : 'add2 ) =

は 5 を表示します。

`

は0番目の要素を評価した結果の辞書型の値をコンテクスト（辞書チェーン）の最初の辞書にして、1番目の要素を評価します。

'cd = {
	( 'a = 3 )
	¤
}:$;

`[ cd a ] =

結果は 3 になります。

JS 版の実装（抜粋）

class
Dict extends SliP {
	constructor( _ ) { super( _ ) }
	get
	string() {
		const v = Object.keys( this._ ).reduce(
			( dict, key ) => {
				const value = this._[ key ]
				dict[ key ] = value instanceof Literal ? value._ : value.string
				return dict
			}
		,	{}
		)
		return `${ JSON.stringify( v ) }`
	}
}

const c = new Context(
	{}
,	new Context(
		{	dict	: new Unary(
				( c, _ ) => {
					const wJSON = JSON.parse( _._ )
					return new Dict(
						Object.keys( wJSON ).reduce(
							( dict, key ) => {
								dict[ key ] = Read( new StringReader( wJSON[ key ] ) )
								return dict
							}
						,	{}
						)
					)
				}
			)
		}
	)
)

10.最後に

サンプルプログラムを
https://github.com/Satachito/SliP/blob/master/JS/Sample.slipここにおいておきました。

$ node SliP.js < Sample.slip

のように実行できます。
細々と作っているマイナー言語ですが一人でも興味を持ってもらえると嬉しいです。
最後まで読んでいただきありがとうございました。