72のプログラミング言語に移植された埋め込み可能なLISP言語の紹介 (複数言語を使った開発プロジェクトで同じコード／ロジックを再利用できます。JavaScript編)

• Joel Martin (github.com/kanaka, Principal Software Engineer at ViaSat, Inc) が主導して開発されている GitHub - kanaka/mal: mal - Make a Lisp というプロジェクトについて紹介します。同プロジェクトの目的として「Learn Lisp by creating a Lisp Interpreter」を掲げています。
• mal は以下に挙げるプログラミング言語による実装が公式リポジトリ上で公開されています: Ada, GNU awk, Bash shell, BASIC (C64 and QBasic), C, C++, C#, ChucK, Common Lisp, Clojure (Clojure and ClojureScript), CoffeeScript, Crystal, D, Dart, Elixir, Elm, Emacs Lisp, Erlang, ES6 (ECMAScript 6 / ECMAScript 2015), F#, Factor, Forth, Go, Groovy, GNU Guile, GNU Smalltalk, Haskell, Haxe (Neko, Python, C++ and JavaScript), Hy, Io, Java, JavaScript, Julia, Kotlin, LiveScript, Logo, Lua, GNU Make, mal itself, Matlab (GNU Octave and MATLAB), miniMAL, NASM, Nim, Object Pascal, Objective C, OCaml, Perl, Perl 6, PHP, Picolisp, PL/pgSQL (Postgres), PL/SQL (Oracle), Postscript, PowerShell, Python (2.X and 3.X), RPython, R, Racket, Rexx, Ruby, Rust, Scala, Scheme (R7RS), Skew, Swift, Swift 3, Tcl, TypeScript, VHDL, Vimscript, Visual Basic.NET, Yorick

この記事の目的

• この記事では、主に mal の利用法の中でも言語実装の学習以外の用途について研究・検証します。
• 既に公開されている72言語の実装を「ユーザーとして利用する」手順を紹介します。
• この記事(JavaScript編)では、JavaScriptでの「malの実装の中身についても触れます」(長くなるので複数記事に分割するかもしれません)。
• https://codepen.io/javacommons/pen/bamWgo にブラウザで使えるREPLの環境を作りました（2018/01/17にQiitaの記事にCodePen上のプログラムが埋め込めるようになったので、その機能を使って以下に埋め込んでいます。現在は仮想コンソールに入力された文字列をただオウム返しするだけです。jquery と jq-console というライブラリを使っています）。これを順番にforkしながら、ステップバイステップでJavaScript版の mal の実装について解説します。
• この記事は現在執筆途中です。しばらく書き足してから再投稿する予定です。少々お待ちください。

See the Pen bamWgo by JavaCommons (@javacommons) on CodePen.

Make-A-Lisp: Make Your Own Lisp Interpreter in 10 Incremental Steps (LambdaConf 2016)

See the Pen aERqLg by JavaCommons (@javacommons) on CodePen.

mal の概略

mal(Make a Lisp) は色々な言語で mal という Lisp 方言を実装してみようというプロジェクトです。
ClosureにインスパイアされたLispインタプリタで、現在72のプログラミング言語での実装が GitHub - kanaka/mal: mal - Make a Lisp で公開されています。
malを実例に利用したLispインタプリタの作成方法は、The Make-A-Lisp Process というドキュメントで詳しく説明されています。ステップバイステップ形式になっていて、”Step 0″のREPL (対話型評価環境)を作成するところから、最終段階の”Step A”でmalでmalを実装するところまで段階的に進んでいく形式です。
malのリポジトリには72の言語で実装されたソースコードがサブフォルダ毎に格納されていて、各フォルダ毎に11段階のステップに分けられたソースコードが格納されています。

• 72の言語での mal 処理系実装
• 11段階のステップに分けられた実装ガイド（全体の構成図付き）
• 各実装ステップごとのテストケース

といったほしい情報が揃っており、言語処理系初心者でも Lisp 実装について簡単に学べる環境が整っています。11段階の各ステップは以下の様な感じです。

• Step 0: The REPL : 実装を始める準備（自分の言語を Makefile に登録して make 一発でテストを走らせられるようにする，関数のスケルトンの作成）
• Step 1: Read and Print : REPL (read-eval-print loop) の read および print 部分の基本的な実装．Lisp の値を格納するデータ構造もつくる
• Step 2: Eval : 評価器．シンボル・リスト・ベクタ・マップの基本的なデータ構造を生成する関数および四則演算を行う関数をつくる
• Step 3: Environments : "環境"を実装する．Lisp の値に名前を付けると環境と呼ばれるテーブルに名前と値の組で保存される（例えば変数定義など）
• Step 4: If Fn Do : 制御構造関連の関数 if, fn, do を実装する．それぞれ条件分岐，関数定義，逐次実行が行えるようになる
• Step 5: Tail call optimization : いわゆる末尾再帰呼び出し最適化を実装する．なぜ末尾にある再帰呼び出しがループに変換できるのか分かる
• Step 6: Files and Eval : ファイル読み出し用の関数と eval() 関数を実装する．主に後で出てくるセルフホストのため．
• Step 7: Quoting : Lisp のクォートを実装する．これにより，自身の抽象構文木をデータ構造として直接扱うことができるようになる．
• Step 8: Macros : Lisp のマクロを実装する．定義されたマクロは eval による評価実行前に展開されるので，これで自身の構文を拡張することができる．試しに if を元に unless をつくってみたりした．
• Step 9: Try : 例外処理機構をつくる．いわゆる try-catch で，シンタックスエラーなどもこれで拾えるようにする．
• Step A: Mutation, Self-hosting and Interop : 値にメタ情報を持たせることができるようにする．また，変更可能(mutable)な値として atom というデータ型と atom を操作する標準関数をいくつか実装する．すでにある mal による mal 実装 を使って，自分で作った処理系をブートストラップとして mal をセルフホストする．（自分でつくった mal 処理系で実行する mal 処理系が step0 〜 stepA のすべてのテストを通す）

mal の実装ステップ(実装レベル分類)

• 「 The Make-A-Lisp Process: https://github.com/kanaka/mal/blob/master/process/guide.md 」より
• https://github.com/kanaka/mal/tree/master/impls に他の言語の実装コードもあります。以下の文章では js の実装コードのリンクを貼っていますが、お好みの言語の実装も参照してください。

Step 0: The REPL

• 実装を始める準備（自分の言語を Makefile に登録して make 一発でテストを走らせられるようにする，関数のスケルトンの作成）
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step0_repl.js

Step 1: Read and Print

• REPL (read-eval-print loop) の read および print 部分の基本的な実装．Lisp の値を格納するデータ構造もつくる
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step1_read_print.js

Step 2: Eval

• 評価器．シンボル・リスト・ベクタ・マップの基本的なデータ構造を生成する関数および四則演算を行う関数をつくる
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step2_eval.js

Step 3: Environments

• "環境"を実装する．Lisp の値に名前を付けると環境と呼ばれるテーブルに名前と値の組で保存される（例えば変数定義など）
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step3_env.js

Step 4: If Fn Do

• 制御構造関連の関数 if, fn, do を実装する．それぞれ条件分岐，関数定義，逐次実行が行えるようになる
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step4_if_fn_do.js

Step 5: Tail call optimization

• いわゆる末尾再帰呼び出し最適化を実装する．なぜ末尾にある再帰呼び出しがループに変換できるのか分かる
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step5_tco.js

Step 6: Files, Mutation, and Eval

• ファイル読み出し用の関数と eval() 関数を実装する．主に後で出てくるセルフホストのため．
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step6_file.js

Step 7: Quoting

• Lisp のクォートを実装する．これにより，自身の抽象構文木をデータ構造として直接扱うことができるようになる．
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step7_quote.js

Step 8: Macros

• Lisp のマクロを実装する．定義されたマクロは eval による評価実行前に展開されるので，これで自身の構文を拡張することができる．試しに if を元に unless をつくってみたりした．
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step8_macros.js

Step 9: Try

• 例外処理機構をつくる．いわゆる try-catch で，シンタックスエラーなどもこれで拾えるようにする．
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/step9_try.js

Step A: Metadata, Self-hosting and Interop

• 値にメタ情報を持たせることができるようにする．また，変更可能(mutable)な値として atom というデータ型と atom を操作する標準関数をいくつか実装する．すでにある mal による mal 実装 を使って，自分で作った処理系をブートストラップとして mal をセルフホストする．（自分でつくった mal 処理系で実行する mal 処理系が step0 〜 stepA のすべてのテストを通す）
• 実装コード: https://github.com/kanaka/mal/blob/master/impls/js/stepA_mal.js