FizzBuzz を処理できるSchemeっぽい処理系をJavaScriptで書いてみる

概要

このエントリでは、いわゆるFizzBuzz 問題に対して、Schemeっぽい文法を処理できる処理系を自分で書いて、Schemeっぽく書いたFizzBuzzを実行するまでを紹介します。

想定対象読者

• JavaScriptがある程度わかる方
• Schemeとかが何となくわかる方
• ネタなエントリを許容できる人

できたこと　と　（今）できないこと

できたこと

動作させたい対象は、下記です。

(define (fb x)
	(if
		(and (= (mod x 3) 0) (= (mod x 5) 0))
		"fizzbuzz"
		(if
			(= (mod x 3) 0)
			"fizz"
			(if
				(= (mod x 5) 0)
				"buzz"
				x
			)
		)
	)
)
(define (fizzbuzz x) (display (fb x)))

下記のような、REPLっぽいCLIで、FizzBuzz用のSchemeっぽいプログラムを実行し、結果を得ることができます。

• "fbs>" というのが、fizz-buzz-schemeのREPLの入力用プロンプトです。
• "samples"という組み込みコマンドで、サンプルのsample/fizzbuzz.fbs ファイルを読み込みます。
• (fizzbuzz 数字)で、与えられた数字を評価し、3で割り切れたらfizz、5で割り切れたらbuzz、3と5の両方で割り切れたらfizzbuzzを返します。

> npm run repl

fbs> samples
fbs> (fizzbuzz 2)
2#undefined
fbs> (fizzbuzz 3)
fizz#undefined
fbs> (fizzbuzz 4)
4#undefined
fbs> (fizzbuzz 5)
buzz#undefined
fbs> (fizzbuzz 15)
fizzbuzz#undefined

(今)できないこと

たくさんあります(後述の「not implemented」参照)。

コード

コードは、こちらにrelease 0.1.3として置いてあります。

作り方

前提

以下が必要です。

• Node 14+

構文解析

パーサは、GitHubにおいてあるこちらのようにしました。

トークンに分けるだけのtokenizeを書き、トークンに分けられたものを構文に応じて後段につなげるためのreadTokensを書いて、最後に外からお便利に呼べるようにparse関数を書きました。

評価

今のところ評価できるものは、以下の通りです。
（GitHubのREADME.mdに記載したものからの転記）

できることが極限に少ないですが、とはいえ、前述のFizzBuzzのプログラムを実行できます。

(at-most partly) implemented

• ✅Variable references
• ✅constants and quoteLiteral expressions
• ✅define 0> Assignments(with 1 variable, not closure)
• ✅basic arithmetic operators (+,mod) within basic accuracy of JavaScript. caution: '-','*','/' are not yet implemented
• ✅basic operators for FizzBuzz (and)
• ✅IF -> Conditionals
• ✅lambda -> Procedures
• ✅Procedure calls
• ✅set! Assignments
• ✅sequencing

not implemented

• ❌quasiquotation

コード

評価器のコードは、GitHubにおいてあるこちらのようにしました。
書いている途中で、中で何をやっているのかわかりやすいように、評価自体の前後でデバッグ用のログを出しながら書けるようにしています。

実際の処理は、それ用にクラスを作って処理を委譲しました。移譲先のコードはこちら。

  static eval (sexp, env = getGlobalEnv()) {
    if (log.getLevel() <= log.levels.DEBUG) {
      log.debug('----------------------------------------------------')
      log.debug('EVAL:' + sexp + ' in ' + env.toString())
    }
    const ret = FsEvaluator.evalInternal(sexp, env)
    if (log.getLevel() <= log.levels.DEBUG) {
      log.debug('RETURNS:' + ret)
      log.debug('----------------------------------------------------')
    }
    return ret
  }

  static evalInternal (sexp, env) {
    if (sexp instanceof FsSymbol) {
      return env.find(sexp)
    } else if (!Array.isArray(sexp)) {
      // i.e. FsNumber, FsBoolean...
      return sexp
    } else if (sexp[0].value === 'if') {
      return FsIf.proc(sexp.slice(1), env)
    } else if (sexp[0].value === 'quote') {
      return FsQuote.proc(sexp.slice(1))
    } else if (sexp[0].value === 'define') {
      return FsDefine.proc(sexp.slice(1), env)
    } else if (sexp[0].value === 'lambda') {
      return FsLambda.proc(sexp.slice(1), env)
    } else {
      const evaluated = sexp.map(s => this.eval(s, env))
      return evaluated[0](evaluated.slice(1))
    }
  }

実行

REPLのループを回している部分は以下のような感じです。REPL全体は、GitHubにおいてあるこちら。

このエントリ冒頭の実行例は、下記のループで実行しています。

let env = getGlobalEnv()
while (loop) {
  const exp = promptSync('fbs>')
  if (exp === 'clear') {
    env = getGlobalEnv()
  } if (exp === 'sample') {
    loadSample()
  } else if (exp === 'q') {
    console.log('bye.')
    loop = false
  } else {
    const res = FE.eval(FP.parse(exp), env).toString()
    console.log(res.toString())
  }
}

テスト

ツール

テスト用のツールは、Jestを使いました。これ一つ入れればいろいろできるという点で便利でした。

書いている途中でテスト結果を見やすくする目的で、Majestic を動かしながらやりました。テストは1ファイルずつ書いて実行していたので最初はCLIだけで足りていたのですが、書いている途中で本体一か所直すと複数テストが請われるパターンが出てきたときに、一覧で見られるのは便利でした。

CI

CIには、GitHub Actionsを使っています。バッジ↓

Schemeの構文

SchemeインタプリタのGauche を手元で動かして、テストケースを書く時の答え合わせに使いました。

おわりに

このエントリでは、FizzBuzz問題用のプログラムをSchemeのサブセットっぽい文法で書き、そのプラグラムを実行する処理系を書いて実行するところまでを紹介しました。

趣味でやっている範囲において、やってみて下記がよかったです。

• JavaScriptでこれどうやって書くんだっけ、みたいなJavaScriptの勉強ができた。
• JestとかMajesticとかツールを試してみることができ、おまけにYak-shaving用にcross-envとかのお便利ライブラリも試せた。ログはwinstonじゃなくてloglevelにして、シンプルでよかった。
• 動いて楽しかった。セミコロンなしのJSコードを書いてすっきりした。

今後

今後は、対応できる構文だったり、標準のシンボルを増やしてみたいです。

参考にしたサイト

• Structure and Interpretation of Computer Programs は、Schcmeを何となく思い出すために閲覧しました。
• (How to Write a (Lisp) Interpreter (in Python)) のサイト、およびこちらを翻訳されていたサイト ((Pythonで) 書く (Lisp) インタプリタ) も参考にしました。

追記

• 2021/08/06 初版(tag: 0.1.0)
• 2021/08/09 実装を少し直したのでサンプルの方を変更
• 2021/08/11 実装を少し直したのでサンプルの方を変更
• 2021/08/25 処理系でできることが増えている分を本文に反映