メメメモモ

プログラミング、筋トレ、ゲーム、etc

四則演算と変数の扱いができるlisp

変数を使った四則演算ができる簡単なlispインタプリタを書きました。

トークン解析と構文解析

lispは下記のように書きます。

(- 3 2) ;6
(- 3 (* 2 3)) ;-3
(setq a 3)


プログラムはリストで記述されます。
リストとは'('と')'で囲まれた部分です。「(- 3 2)」
リストの中にリストを入れる事もできます。「(- 3 (* 2 3))」


トークン解析では文字列として読み込んだリストを、トークンに分けて配列に格納します。
例えば「(- 3 2)」を読み込んだ場合「'(','-','3','2',')'」の配列に分けます。
これを行なうスクリプトが下記のようなものになりました。

sub get_tokens {
    my $in_str = shift;

    my @chars = split(//,$in_str);
    my $token_buf = '';
    my @tokens = ();
    my $in_double_quote = 0;

    foreach my $c (@chars) {
        if ($c eq '"') {
            if ($in_double_quote) {
                $in_double_quote = 0;
            } else {
                $in_double_quote = 1;
            }
        }

        if ($c eq '(' || $c eq ')') {
            if ($token_buf) {
                push @tokens, $token_buf;
                $token_buf = '';
            }
            push @tokens, $c;
        } elsif (!$in_double_quote && is_ignore_char($c)) {
            if ($token_buf) {
                push @tokens, $token_buf;
                $token_buf = '';
            }
        } else {
            $token_buf .= $c;
            $token_buf .= $c;
        }
    }

    return @tokens;
}


sub is_ignore_char {
    my $c = shift;

    if ($c =~ /^(\t|\r|\n| |)$/) {
        return 1;
    } else {
        return 0;
    }
}

構文解析では、一つのリストを一つの配列に対応させます。
リストの中のリスト、という構造も表現するようにします。

['-','3','2']                # (- 3 2)
['-','3',['*','2','3']]  # (- 3 (* 2 3))

構文解析では、トークンの配列を受け取って解析を行なっています。

sub slisp_parse {
    my @tokens = @_;

    my @stack = ();

    foreach my $token (@tokens) {
        if ($token eq '(') {
            push @stack, [];
        } elsif ($token eq ')') {
            my $cur_stack = pop @stack;
            my $up_stack = pop @stack;
            if ($up_stack) {
                push @stack, [@$up_stack,$cur_stack];
            } else {
                push @stack, $cur_stack;
            }
        } elsif (is_primitive($token)) {
            my $cur_stack = pop @stack;
            push @stack, [@$cur_stack,$token];
        } elsif (check_type($token) =~ /^(string|number|symbol)/) {
            my $cur_stack = pop @stack;
            push @stack, [@$cur_stack,$token];
        } else {
            my $cur_stack = pop @stack;
            push @stack, [@$cur_stack,$token];
        }
    }
    @stack = ('progn',@stack);
    return [@stack];
}


sub is_primitive {
    my $token = shift;

    my @primitive_list =
        qw#list setq let defun                                                   
           if cond lambda apply                                                  
           progn quote print                                                     
           + - * / = > <                                                         
           not or and#;

    foreach my $p (@primitive_list) {
        if ($token eq $p) {
            return 1;
        }
    }

    return 0;
}


最終的に「[ 'progn',[ '+','3','2' ] ]」という形になります。


評価

構文解析したものを受け取って、実行していきます。
構文分析したものに従って実行する事を「評価」と呼びます。


評価は、外側のリストから行なわれます。
例えば「['progn',['+','3',['*','2','3'] ] ]」の場合、「['progn'...]」を評価します。
配列を受け取り、評価する関数は下記のようになります。

sub slisp_eval {
    my $exp = shift;
    if (is_self($exp)) {
        return $exp;
    } elsif (is_variable($exp)) {
        return lookup_variable_value($exp, \%env);
    } elsif (slisp_make_primitive($exp,'setq')) {
        return eval_assignment($exp, \%env);
    } elsif (slisp_make_primitive($exp,'progn')) {
        eval_sequence(progn_actions($exp));
    } elsif (is_arithmetic($exp)) {
        calc($exp);
    } elsif (slisp_make_primitive($exp,'print')) {
        slisp_print($exp);
    } else {
        die "Unknown expression type.". Data::Dumper->Dump([$exp]);
    }
}


各種類のリストに対して評価を行います。

計算リスト(['+','2','3'])

計算リストに対しては、calc関数が処理します。

sub calc {
        my $exp = shift;
        my $op = $exp->[0];
        my $first = slisp_eval($exp->[1]);
        my $second = slisp_eval($exp->[2]);
        if ($op eq '+') { return $first + $second; }
        if ($op eq '-') { return $first - $second; }
        if ($op eq '*') { return $first * $second; }
        if ($op eq '/') { return $first / $second; }
    }


演算子の各引数に対して評価してから計算します。例えば「['+','3',['+','3','1']]」といったリストに対応しています。

変数の代入と参照(['setq','a','1'])(['+','a','1'])

setqに対しては、eval_assignment関数が処理します。

sub eval_assignment {
     my ($exp, $env) = @_;
     my @e = @$exp;
     my %copy_env = %$env;

     my $variable = $e[1];
     my $value = slisp_eval($e[2],\%copy_env);
     $env->{$variable} = $value;
}

シンボルテーブルの役割をしている$envというハッシュ変数に、変数名と値を格納しています。


参照に関しては、lookup_variable_value関数が処理します。

sub lookup_variable_value {
    my ($exp, $env) = @_;
    return $env->{$exp};
}
progn

prognは、引数であるリストを順に評価していきます。
progn_actions関数で、prognに渡されている引数のリストを取ってきます。
そして、eval_sequence関数で、引数のリストを順番に評価していきます。

    sub eval_sequence {
        my $actions = shift;
        foreach my $action (@$actions) {
            my $value = slisp_eval($action);
        }
    }

テスト

下記のスクリプトをプログラムに読み込ませます。

(progn
  (setq a (- 3 (* 2 3)))
  (setq a (- a 100))
  (print a))
$ perl slisp.pl test.lisp


計算結果である「-103」が表示されます。

TODO

  • ifを使えるようにする
  • 関数定義(defun)ができるようにする

参考

Software Design (ソフトウェア デザイン) 2010年 05月号 [雑誌]

Software Design (ソフトウェア デザイン) 2010年 05月号 [雑誌]