自己紹介

asciianと言います。OSSソフトウェア開発をしています。普段は数学と言語学を研究しています。
好きなプログラミング言語はCommonLispやSchemeといったLispの他にGolangやJavaScriptも好きです。
Githubなどに成果を公開していますが、ほとんどが自分の研究と関係あるものです。
趣味はソフトウェア開発と散歩です。河原を歩くのが好きです。読書も好きですがほとんどは恋愛小説です。
今の専門は数理言語学です。数理言語学というのは論理学と言語学と情報科学が混ざった領域です。

開発環境はmacOSです。使用するエディタはVim/Emacs/Atom/VSCodeなどでプログラミング言語で変えています。

過去に作ったものとして次のようなものがあります。

  • Yomu - 英和辞書付きPDF閲覧ソフトウェア
  • iris - ISLispのインタプリタ
  • papyrus - CommonLisp用の文芸的プログラミング環境

LISPの処理系を作るときのコツ

自作の言語処理系というのは誰でも一度は憧れるものであろう。そのようなときによく勧められるのがLISPの処理系の作成である。そこでLISPの処理系をつくるときのコツを書く。読者に注意してほしいのは、ここでは実際のLISPの処理系は実装方法を紹介するのではないということである。世の中には沢山の素晴しいLISPの処理系のチュートリアルがあるので、そちらを参考にして欲しい。

前提条件

  • Brainf*ckやSKIコンビネータを実装できる
  • LISP系の言語を使ったことがある

実装手順の概要

筆者がよく使う手順を示す。これ以外の順番もあると思うが、実際に簡単なREPLが動作するまでの時間が最短になるようにすることで完成までの意欲を維持しやすくなるので、まずは以下の手順でやってみて欲しい。

  1. コンセルとシンボルの共用体を作る
  2. S式の字句解析器と構文解析器を作る(ここでは'(quote)などのリードマクロの実装はとりあえずしない)
  3. 変数名(1で作った共用体のシンボル)と値(1で作った共用体のシンボルとコンセル両方)からなる連想配列を環境として作る
  4. 評価器(evalapply)を作る
  5. 純LISPの関数(atom eq car cdr cons)を作る
  6. コンセルとシンボルの共用体に関数用のプロパティ(引数と内容)を加える
  7. 他の特殊形式(if quote lambda define)を作る
  8. defineを使ってCommon LispやSchemeにある関数を作る
  9. '(quote)`(quiasi-quote)などのリードマクロを読み込めるように字句解析器と構文解析器を拡張する
  10. マクロ展開器を作る
  11. 他のデータ構造を適宜追加していく

3の段階では名前空間の数が1つであるようなLISP1、4と6で名前空間を動的スコープにすると単純な実装で7まで辿りつけるはずである。7までは独力で実装可能だが8以降は他の実装を参考にしつつ作るのが一般的である

構文解析器と字句解析器

LISPの構文は簡素なので手書きでも十分に対応できるが配列や数値などの構文を入れていくとなると、やはり手書きで完璧なものを作るのにはそれなりの労力がかかってくる。もしS式の範囲を越えるような構文を導入したいのであれば素直にlexとyaccなどのツールを使ったりパーサーコンビネーターなどを使うほうが断然効率が良い。

実装言語の選択

お勧めはRubyやPython, JavaScriptなどのスクリプト言語である。これらの言語を使うことで手順1や手順6を省くことができる。また、malという学習用途のLISP実装プロジェクトがあり様々なプログラミング言語での実装を公開しているので、その雰囲気を確かめるのも良い。

関数の表現方法

関数の表現方法には幾つかあり古典的なものに引数と内容のコンセルとして保存しておき評価器で引数部分を環境に上書きして内容を実行することで関数を実装する方法がある。しかし最近のプログラミング言語には関数オブジェクトを使えるものも多く、関数オブジェクトで古典的な実装を覆うように実装する方法をとると評価器の実装や後のFFIの実装が楽になるので、関数オブジェクトを使うことをお勧めする。

LISP1かLISP2か

LISP1は関数と変数の名前空間が同じものである。一方でLISP2は関数用の名前空間と変数用の名前空間が別々である。LISP2にすると構文上ではFUNCTION特殊形式が必要になり、環境も関数と変数で二つ用意し制御する必要があるなど少々複雑になる。したがってまずはLISP1で作ってみることをお勧めする。

静的スコープか動的スコープか

静的スコープは処理系利用者からみると分かりやすいが、処理系作成者からすると大変難解である。
例えば、次の例を見て欲しい。

1
2
3
(let ((a 1))
(define a+ (lambda (n) (+ n a))))
(a+ 1) ;; 2

静的スコープの場合は評価器は関数が呼ばれたときに関数が定義されたときの環境に戻る必要がある。これを実現する方法として環境を階層化して履歴として保存する方法がある。具体的な実装としてはシャドーバインディングやディープバインディングなどがある。

動的スコープの場合は先の例は参照エラーになる。これは評価器が関数が定義されたときの環境に戻らないからである。したがって環境は階層化しなくても良くなり呼出し元の環境をそのまま関数の実行環境にするだけで良くなる。

以上の理由から処理系を実装する際に簡単なのは動的スコープの方である。

マクロの実装の仕方

Schemeの健全なマクロの実装については筆者が詳しくないので、ここでは古典的なマクロの実装方法についてのみ述べる。古典的マクロとはCommon LispやEmacs Lispにあるdefmacroによって定義されるマクロのことである。LISP1やLISP2に関係なく新しくマクロ用の名前空間を用意する必要がある。

また古典的マクロでは`(quasi-quote),(unquote),@(splicing)が良く使われるが、これらはlistappendquoteを使って等価な表現へと変換することが可能である。実装は参考文献にも乗っているので参考にしてほしい。

マクロ展開のタイミング

マクロの展開のタイミングは言語毎に違うが筆者は関数呼出し特殊化として評価器を拡張する方法を提案する。これはマクロ展開時にも定義された関数の呼出が発生しうるからである。

マクロと関数と特殊形式の違い

評価器はマクロと関数と特殊形式を区別して評価する必要がある。

引数 実行結果
マクロ 評価しない 評価する
関数 評価する 評価しない
特殊形式 未定義(あるいは評価しない) 評価しない

特殊形式の評価の例としてはifがある。これは条件が真ときと偽ときで評価する引数が異なる。引数の評価方法が特殊形式ごとに違うのでマクロの特殊化としてマクロとおなじ名前空間に入れてしまう場合もある。

処理系が完成したら

ぜひ公開してください。他の処理系にくらべて速いとか遅いとかは関係ありません。世界に一つだけの貴方の貴方による貴方ための処理系です。それだけで十分に価値があります。

また処理系の作成で培った技術で次のようなものも作れるようになっているはずです。是非挑戦してみてください。

  • 正規表現エンジン
  • セルフホスティングな処理系(自作のLISPの上で動く自作のLISPの処理系)
  • AltJSなどのLISPから他言語への翻訳処理

参考文献

日本語で読めるLISP処理系作成のチュートリアル

無料で読めるLISPの規格書

宣伝

筆者が作った処理系

ISLispのブラウザ拡張を作る

今年の夏は自由研究と称してISLispの処理系 irisを作りましたが、 そのISLispの処理系を元にブラウザ拡張を作ってみます。 ISLispとはLISPにおけるISO規格であり、1997年と2007年に標準化されているLISPの方言の一つです。 ISLispはCommonLispのサブセットのような規格です。詳しくは 公式サイトをご覧ください。

Go言語で評価器を作る

まずベースとなるその処理系はirisと呼ばれるGo言語製のインタプリタです。 Go言語には GopherJSと呼ばれるJavaScriptへの変換器がありますので、 それを用いてirisをコンパイルします。そのためにまずはインタプリタが提供するAPIを使って 評価器を作ります。

eval.go
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

package main

import (
	"bytes"
	"fmt"
	"html"
	"strings"

	"github.com/gopherjs/gopherjs/js"
	"github.com/asciian/iris/runtime"
	"github.com/asciian/iris/runtime/ilos/instance"
)

const version = "526f28d"

func main() {
	// コンソールにバージョン情報を出力
	print(`Welcome to Iris (` + version + `). Iris is an ISLisp implementation on Go.
This library works with gopherjs and has no methods to get input.
For more infomation, see https://islisp.js.org.
Copyright © 2017 asciian All Rights Reserved.`)
	// islispオブジェクトにeval関数を登録
	js.Global.Set("islisp", map[string]interface{}{"eval": eval})
}

func eval(s string) string {
	//文字列をストリームに変換
	r := strings.NewReader(s)
	//出力を文字列にする用ストリームを用意
	w := new(bytes.Buffer)
	// ラインタイムの初期化
	runtime.TopLevel.StandardInput = instance.NewStream(r, nil)
	runtime.TopLevel.StandardOutput = instance.NewStream(nil, w)
	runtime.TopLevel.ErrorOutput = instance.NewStream(nil, w)
	runtime.TopLevel.Function.Set(instance.NewSymbol("READ"), nil)
	runtime.TopLevel.Function.Set(instance.NewSymbol("READ-LINE"), nil)
	runtime.TopLevel.Function.Set(instance.NewSymbol("READ-CHAR"), nil)
	//トップレベルの標準入力(strings.Reader)から読み込む
	p, err := runtime.Read(runtime.TopLevel)
	if err != nil {
		fmt.Fprint(w, html.EscapeString(err.String()))
		return w.String()
	}
	//読み込んだS式を評価
	e, err := runtime.Eval(runtime.TopLevel, p)
	if err != nil {
		fmt.Fprint(w, html.EscapeString(err.String()))
		return w.String()
	}
	//評価した結果を文字列にして書き込む
	fmt.Fprint(w, html.EscapeString(e.String()))
	//文字列を返す
	return w.String()
}

これを以下のコマンドでコンパイルします。

$ gopherjs eval.go

すると、eval.jseval.js.mapの二つのファイルが手に入ります。 これを読み込むとJavaScriptからislisp.eval関数が使えるようになります。 この関数は文字列をインタプリタが評価し結果を文字列として返す関数です。

これは https://islisp.js.org/api/eval.js として公開しており誰でも読み込むことができます。 このAPIはISLispのドキュメントにて実行できるサンプルコードを実装する際に使用されています。

JavaScriptで拡張機能を作る

ウェブブラウザーの拡張機能を作る方法は色々ありますが、 ここでは最も簡単なユーザースクリプトを用いた方法で開発をします。 ユーザースクリプトとはウェブページにそのスクリプト注入して読み込むだけのシンプルな仕組みで ユーザスクリプトを実現するための拡張機能として、 FirefoxにはGreaseMonkeyやTemperMonkeyやViolentMonkeyなどあります。 またGoogle ChromeにはTemperMonkeyとViolentMonkeyがあります。

ではこのユーザースクリプトを使って”選択したテキストをS式として評価し、 その結果を表示する”機能を作りましょう。

islisp.user.js
// ==UserScript==
// @name ISLisp
// @namespace islisp.js.org
// @match *://*/*
// @grant none
// @require https://islisp.js.org/api/eval.js
// ==/UserScript==

// Licensed under the Apache License 2.0
// Copyright (c) 2017 TANIGUCHI Masaya All Rights Reserved.

// ポップアップ用の要素をBody要素の直下に作る
function createPopup() {
    const popup = document.createElement("div");
    popup.id = "popup";
    const viewer = document.body;
    viewer.style.position = "relative";
    viewer.appendChild(popup);
    return popup;
}

// ポップアップをCSSにより可視化、適切な位置に移動させる
function showPopup(content, top, left) {
    const popup = document.getElementById("popup") || createPopup();
    const viewer = document.body;
    const rect = viewer.getBoundingClientRect();
    popup.innerHTML = content;
    Object.assign(popup.style, {
        position: "absolute",
        display: "block",
        top: top - rect.top + "px",
        left: left - rect.left + "px",
        width: "300px",
        padding: "10px",
        backgroundColor: "rgba(0,0,0,0.7)",
        color: "#fff"
    });
}

// ポップアップをCSSにより隠す
function hidePopup() {
    const popup = document.getElementById("popup") || createPopup();
    popup.style.display = "none";
}

// テキストが選択されると、Selectionオブジェクトを作り、表示すべき座標を決定する
// その後表示を行う。すでに表示が行われている場合は隠す
addEventListener("mouseup", function(){
    const selection = getSelection();
    const keyword = selection.toString();
    if (keyword.length > 0) {
        const range = selection.getRangeAt(0);
        const rect = range.getBoundingClientRect();
        const content = islisp.eval(keyword);
        const top = rect.bottom;
        const left = (rect.right + rect.left) / 2 - 20;
        showPopup(content, top, left);
    } else {
        hidePopup();
    }
});

なお以上のソースコードは、英和辞書付きPDF閲覧ソフトウェア Yomuの意味表示機能のソースコードを流用しています。 そのためライセンスが違います。しかし、ユーザースクリプトは基本的に、パッケージングされて配布されるわけではなく 各ソースコードが別々にダウンロードされるだけなので、ライセンス関係の問題にはならないと思われます。

HTMLでインストール機能を作る

ユーザースクリプトを実現する拡張機能は、 インストール機能を備えておりユーザースクリプト*.user.jsへのリンクをクリックすると自動でインストールされます。 したがって以下のようなリンク作ります。

<a href="islisp.user.js">Install ISLisp Extension</a>

LISPで動作確認する

まずは各々のブラウザで拡張機能をインストールします。

Firefox

GreaseMonkey, TemperMonkey, ViolentMonkey

Google Chrome

TemperMonkey, ViolentMonkey

次に先ほど作ったユーザースクリプトをインストールしましょう。

インストールできたら、このページを再読み込みして以下のテキストを選択してみてください。 結果が表示されるはずです。

(+ 1 1) ;;=> 2

まとめ

拡張機能は以上の通り簡単に作れるので楽しいですね。 Go言語またはJavaScript言語には簡単にiris組み込むことができるので、 ElectronやCLIアプリケーションでの動的なスクリプティング機能ISLispとして作ることもできます。 特にJavaScriptについては各LISP方言の実装が用意されておりどれも素晴らしいです。 ISLispだけでなくJavaScriptでLISPを使うは面白いのでぜひお試しください。