Posted at

Swift で Lisp のインタプリタを作ってみる

More than 5 years have passed since last update.

Swift の勉強のため,Lisp のインタプリタもどきを作ってみました.

参考にしたのは,Arc という Lisp の方言ですが,全く作り込めていないため,「もどき」です.作成したソースはgithub上に置いてあります.

iPhone アプリではなく,Mac のコマンドラインアプリとして作成しています.

現時点では以下の程度しかできません.


  • car, cdr, list, quote, lambda式

  • 変数の定義には "=" を使う


    • (= x 1)

    • (= y (lambda (z) (list z z z)))



今回作ってみたものの基本的な流れは,


  1. Lisp の型を表すクラスの作成

  2. 標準入力から文字列をパースする

  3. パースした内容を Lisp のオブジェクトに変換

  4. Lisp のオブジェクトに対して eval を呼び出して評価

となります.


1. Lisp の型を表すクラスの作成


  • Nil,文字列,シンボル,数字,リストと,環境を表すクラスを作成しました


LispObj プロトコル


  • 共通の protocol として LispObj を持つようにしています

  • LispObj は,良く使うリスト型かどうかをチェックする listp と,画面表示に使う toStr のみを定義しました

  • protocol が Java でいうインターフェイスにあたるものだと理解しています

protocol LispObj {

func toStr() -> String
func listp() -> ConsCell?
}


  • Swift ではプログラム中に「?」マークを付けると,nil を許容することが出来るという仕様のようです

  • Optionals と呼ばれているようです

  • ?が付いてない関数では nil を返そうとするとコンパイルエラーになった気がします

  • 似た機能として,キャストが可能であれば実施するが,出来なければしない,というのを as? で表します

  • 以下のような感じで結構多用してしまいました.正しいかはよくわかりません

if let hoge = foo as? Hoge {  // foo が Hoge にキャスト可能ならキャスト

// hoge を Hoge 型として利用する
} else {
// キャスト不可だった場合の処理をこっちに書く(hoge は使えない)
}


Nil クラス


  • Singleton の例としてここを参考にさせて頂きました.

class Nil: LispObj {

init() {
}

class var sharedInstance: Nil {
struct Singleton {
private static let instance = Nil()
}
return Singleton.instance
}

func toStr() -> String {
return "nil";
}

func listp() -> ConsCell? {
return nil;
}
}


Symbol クラス


  • 特に何の工夫も無いクラスです

  • LispNum と LispStr もほぼ同じ内容です

class Symbol: LispObj {

var name: String;
init(name: String) {
self.name = name;
}

func toStr() -> String {
return name;
}

func listp() -> ConsCell? {
return nil;
}
}


Error クラス


  • Swift には例外が無いっぽいので,エラーのハンドリング用に Error クラスを作成しました

  • 中身は Symbol とほぼ同じです.もう少しいいやり方がありそうな気もします..

class Error: LispObj {

var message: String;
init(message: String) {
self.message = message;
}

func toStr() -> String {
return "Error: " + message;
}

func listp() -> ConsCell? {
return nil;
}
}


ConsCell クラス


  • Lisp のリストを表わすために作成

  • car 部と cdr 部としてそれぞれLispObjectを持つようにした他,toStr はちょっと変わったLisp入門を参考に作成しました.

class ConsCell: LispObj {

var car: LispObj;
var cdr: LispObj;

init(car: LispObj, cdr: LispObj) {
self.car = car;
self.cdr = cdr;
}

func toStr() -> String {
var returnValue: String = "";

returnValue += "(";

var tmpcell = self;

while (true) {
returnValue += tmpcell.car.toStr();

if let cdrcell = tmpcell.cdr.listp() {
tmpcell = cdrcell;
} else if tmpcell.cdr is Nil {
break;
} else { //if tmpcell.cdr.isAtom() {
returnValue += ".";
returnValue += tmpcell.cdr.toStr();
break;
}
returnValue += " ";
}
returnValue += ")"

return returnValue;
}

func listp() -> ConsCell? {
return self;
}
}


2. 標準入力から文字列をパースする


標準入力から文字列取得



  • ここを参考に,以下のような関数を作りました

  • カーソルキー等にも入力値が割り当てられているようで,以下の呼び出し時に押すと,予期しない動作になったりします

func read() -> String {

var tmp = NSFileHandle.fileHandleWithStandardInput();

var rawdata = tmp.availableData;
var str = NSString(data: rawdata, encoding: NSUTF8StringEncoding);

return str;
}


取得した文字列を配列に変換


  • 必要な要素毎に分割して配列に入力しています

  • 文字列操作の関数があまり出揃っていない模様で,細かい処理がやりづらいです

  • Lisp では quote 記号が特別な意味を持つので,変換処理も加えています

// 解析結果のトークンリストを入れる配列

var tokenlist: [String] = [];

// どこまで読み込んだかを表す配列
var tokenIndex = 0;

func tokenize(str: String) { //-> ([String], Int) {
// ' (quote記号を (quote ... ) に置き換え

var str2 = ""
var quoteFlag = false
for a in str {
if a == "'" {
str2 += "(quote "
quoteFlag = true
} else if a == ")" && quoteFlag {
str2 += "))"
quoteFlag = false;
} else {
str2 += a
}
}

// "(" と ")" を空白付きに変換
let replacedStr = str2
.stringByReplacingOccurrencesOfString("(", withString: " ( ", options: nil, range: nil)
.stringByReplacingOccurrencesOfString(")", withString: " ) ", options: nil, range: nil)
.stringByReplacingOccurrencesOfString("\n", withString: " ", options: nil, range: nil);

tokenlist = replacedStr.componentsSeparatedByString(" ");
tokenIndex = 0;
}


3. パースした内容を Lisp のオブジェクトに変換


  • ここまでで,パースした Lisp のプログラムが配列に格納されているため,LispObj に変換する

  • リストではない場合は,Intにキャスト可能かや,セミコロンで囲われているか等を確認して対応する型に変換

  • リストの表現の場合はリスト型のオブジェクトを作成する

func parse() -> LispObj {

var c: LispObj;
c = read_next(get_token());
return c;
}
func read_next(var token: String) -> LispObj {
var carexp: LispObj, cdrexp: LispObj;
var list: LispObj = NIL;

if token == "" {
return NIL;
}
if (token != "(") { // "(" じゃないときの処理
if let n = token.toInt() {
return LispNum(value: n);
} else {
let prefix = token.hasPrefix("\"");
let suffix = token.hasSuffix("\"");
let length = token.utf16Count;

if prefix && suffix { // "hogehoge" のようにセミコロンで囲われている場合
if length > 2 {
return LispStr(value: token[1...token.utf16Count-2]);
} else {
return LispStr(value: "");
}
} else if prefix || suffix { // "hogehoge のように片方だけセミコロンが付いている場合
return Error(message: "wrong String:" + token);
} else {
return Symbol(name: token);
}
}
}

token = get_token(); // ( の次のトークンを取得
while (true) { // "(" から始まるとき
if (token == ")") {
return list;
}

carexp = read_next(token); // 読み込んだトークンをcar部分として処理
token = get_token(); // 次のトークン取得
if (token == ".") { // ペアの場合
token = get_token();
cdrexp = read_next(token); // 取得した次のトークンを cdr にセット
token = get_token(); // ペアの後は ) がくるはず
if token != ")" {
println(") required!");
}
return ConsCell(car: carexp, cdr: cdrexp);
}
list = concat(list, cons(carexp, NIL));
}
}


4. Lisp のオブジェクトに対して eval を呼び出して評価


  • 3までで作成した LispObj を与えられた環境の元で評価する

  • 昔作ったLisp in Arcを参考に実装

  • 環境は Dictonary 型を使い,名前と値を紐付けする

  • クロージャを使う場合は,Dictonary をグローバルのものとクロージャ内のものに分けて扱う

func eval(exp: LispObj, env: Environment) -> LispObj {

if exp is Error {
return exp;
}
if exp is Nil || exp is LispNum { // Nilまたは数値の場合はそのまま返す
return exp;
}
if exp is LispStr { // または文字列の場合もそのまま返す(エディタがエラーになるため、 || の連結は禁止
return exp;
}
if let symbol = exp as? Symbol { // シンボルならば環境の値を検索して返す
var value = get(symbol.name, env);
if !(value is Nil) {
return value;
} else {
return Error(message: "Undefined Value: " + symbol.name);
}
}

if let consexp = exp.listp() {
return apply(consexp.car, consexp.cdr, env);
}

return Error(message: "something wrong!");
}

func apply(operator_var: LispObj, operand: LispObj, env: Environment) -> LispObj {
let operator_body = eval(operator_var, env);

let tmp = operand;
if eq(car(operator_body), PRIMITIVE) { // プリミティブ関数の場合の処理
switch cdr(operator_body).toStr() {
case "car":
return car(eval(car(operand), env));
case "cdr":
return cdr(eval(car(operand), env));
case "=":
// (= x 10)
// (= y "test")
// (= z (+ 1 2))
if let variable = car(operand) as? Symbol { // -> x, y
let body = cadr(operand); // 10, "test"
let value = eval(body, env);
def_var(variable, value, env);

return variable;
} else {
return Error(message: "Wrong type argument: " + car(operand).toStr());
}
case "list":
return eval_args(operand, env);
case "quote":
if cdr(operand) is Nil {
return car(operand);
} else {
return Error(message: "Wrong number of arguments: " + operand.toStr());
}
case "lambda":
// lambda式の定義
// (lambda (x) (+ x 1))
// operand: ((x) (+ x 1))
let params = car(operand) // (x)
let body = cadr(operand) // (+ x 1)

let tmp = cons(LispStr(value: LAMBDA), cons(params, cons(body, cons(env.copy(), NIL))));
return tmp

default:
return Error(message: "unknown primitive procedure: " + cdr(operator_body).toStr());
}
}

if eq(car(operator_body), LAMBDA) {
// lambda式の実行
// oparator_body : ("*** lambda ***" (x) (list x x x) [env])
let lambda_params = cadr(operator_body); // (x)
let lambda_body = car(cddr(operator_body)); // (list x x x)
if let lambda_env = cadr(cddr(operator_body)) as? Environment { // [env]
let operand_check = eval_args(operand, env);
if (operand_check is Error) {
return operand_check;
}

if let ex_env = lambda_env.extend(lambda_params, operand: operand_check) {
return eval(lambda_body, ex_env);
} else {
return Error(message: "eval lambda params error: " + lambda_params.toStr() + " " + operand.toStr())
}
}
}

return Error(message: "not a function: " + operator_body.toStr());
}


まとめ

Swift は Java と JavaScript と Ruby がまざったような感じで,なかなか使い易い言語な気もします.が,文字列の操作の関数が少なかったり,β版なのですぐ仕様が変わったり,Xcode がすぐ落ちたりとまだまだな部分もありそうです.今後どうなるのか楽しみです.

Objective-C と互換を保ち続けるとなると,結局iPhoneアプリ作るときはあの長い関数名と付き合い続ける必要があるんでしょうかね...


参考