PLY (Python Lex-Yacc) で作る Algol 60 処理系 第3部
2008.12.8 - 2009.2.17 (鈴)- 第１部
- 1. はじめに
- 2. Algol 60 とは
- 3. PLY の導入
- 4. 字句解析
- 5. 構文解析
- 6. ここまでのまとめ
- 第２部
- 7. 名前の解決
- 8. インタープリタ - 文の単方向リンクと goto 文
- 9. インタープリタ - 手続きとディスプレイとスタック
- 10. インタープリタ - 式の中からの大域脱出
- 11. インタープリタ - call-by-name の実現
- 12. インタープリタ - のこりの言語要素
- 第３部
- 13. インタープリタへの標準関数の組込み
- 13.1 read, print, _nativecall
- 13.2 Prelude.py
- 13.3 修正報告書のミス
- 14. メイン・スクリプト algol60
- 15. インタープリタの使い方
- 15.1 同梱の PLY について
- 16. ここまでのまとめ
- 第４部
- 17. PLY-3.0 と Python 2/3 互換性
- 18. 構文レベルの Python 2/3 両対応
- 19. オブジェクト・レベルの Python 2/3 両対応
- 20. その他の変更
- algol60-0.6.tar.bz2 (59246 バイト)
Python (2.3.5 から 2.6 まで) による Algol 60 インタープリタ 0.6 版 (PLY 2.5 同梱)
- Lexer.py 字句解析器
- Types.py 各構文要素を表す型など
- Parser.py 構文解析器
- Interpreter.py インタープリタ本体
- Prelude.py 標準関数の実装
- algol60 メイン・スクリプト
13. インタープリタへの標準関数の組込み
1963 年の Algol 60 改訂報告書 3.2.4 節 は，Algol 60 に組み込むべき標準関数として数学関数を 8 個，同 3.2.5 節は実数から整数への変換関数を 1 個挙げていました。 これらの関数は recommend されているだけで必須ではありませんでした。 また，入出力手続きは規定されていませんでした。
Sample Implementation and Examples 第２章 は，改訂報告書で挙げられた 9 個の標準関数に加え， 1964 年の "Report on Input-Output Procedures for Algol 60" に基づき 4 個の入出力手続きを挙げています。 本稿で示した Algol 60 のプログラム例で使われている read 手続きと print 手続きは，これに由来します。
一方，1976 年の Algol 60 修正報告書 3.2.4 節 は，これと異なる入出力手続きを標準関数として規定しました。 また同報告書では recommend の語が消え，標準関数は単に仕様の一部になりました。
これは現在では当たり前に思えますが，当時は，時代を先どった画期的なことだったに違いありません。 1970 年代当時，Fortran や Pascal は，入出力のために専用の文や，言語の枠外の機能である可変個数の引数をとる 特別な手続きを用意していました。 くだんの read 手続きや print 手続きもそのような種類の手続きでした。
しかし，高水準言語自身による標準関数の記述というアイディアについて Algol 60 がオリジナリティを主張できるかどうかははっきりしません。 もしも修正報告書に書かれた標準関数の仕様が，すでに 1960 年ごろ着想され，実装され， ただ報告書に記載できるだけの意見の一致を修正報告書の時点まで見なかったのならばともかく，少なくとも C 言語のもとになった BCPL が 1960 年代末期， すでにそういったアイディアをかなえていたからです。
本インタープリタでは，修正報告書の仕様に従って標準関数を用意するとともに，便宜のための機能として read 手続きと print 手続きを実現します。
13.1 read, print, _nativecall
read 手続きと print 手続きは可変個数の引数をとりますから，Algol 60 自身で記述することはできません。
Interpreter クラス内部に組み込んで実現します。
read(V1, V2, ……, Vn); comment 整数か実数を入力し，順に変数 V1, V2, ……, Vn に代入する; print(E1, E2, ……, En); comment 式 E1, E2, ……, En の値を，空白をはさんで順に出力する;
名前解決後，識別子 ident
が未定義ならば ident.quantity is None
が成り立つことを利用して，それぞれの実装メソッドへ分岐します。
READ = intern('read'); PRINT = intern('print') NATIVECALL = intern('_nativecall') # 独自拡張: Python の関数を呼び出す …… class Interpreter: …… def call_function(self, ident, args): "関数を呼び出す。関数の戻り値を結果の値として返す。" assert isinstance(ident, Identifier) proc = ident.quantity if proc is None: name = ident.name if name is READ: self.do_read_procedure(args) elif name is PRINT: self.do_print_procedure(args) elif name is NATIVECALL: return self.call_native(args) else: raise SemanticsError("undefined procedure: %s at %d" % (name, ident.lineno)) elif isinstance(proc, FormalParameter): q = self.__get_proc(proc) frame = Frame(q, args, None, self, ident.lineno) return self.__call_with_frame(frame, proc) else: frame = Frame(proc, args, None, self, ident.lineno) frame.result = None self.do_statement(frame) return frame.result
read と print のほか，_nativecall に対しても分岐しています。
１文字入出力など基本的な機能をネイティブ・コードで実現するとき，Algol 60
の元々の想定では手続き本体として処理系依存な方法でネイティブ・コードを書くわけですが，
ここでは，より簡単に，文字列引数で指定された Python 関数を呼び出すメタな関数を使うことにします。
それが本インタープリタ独自の拡張機能である _nativecall 関数です。
_nativecall
など内部実装用の識別子を _ で始めることにして，妥当な Algol 60 プログラムとの名前の衝突を回避することにします。
_nativecall の実装メソッド call_native は，引数並び args の各要素を
Python 関数へ値渡し (call-by-value) で渡すため，それぞれ Algol の式として評価します。
先頭の引数は，Algol の式として評価した後，さらに eval を使って Python の式として評価します。
こうして得られた Python 関数を，残りの引数とともに呼び出します。
def call_native(self, args):
_a = [ self.eval_expression(e) for e in args ]
assert isinstance(_a[0], str), _a
_f = eval(_a[0])
return _f(*_a[1:])
ここで，eval を使って評価するとき，self が見えていることに注意してください。
ですから，Python 関数に現在の Interpreter インスタンスを渡したいときは，
Algol プログラムから _nativecall(`Prelude.outchar(self)', …) のように呼び出します。
eval("Prelude.outchar(self)") が行われ，
Python 関数 Prelude.outchar に現在の self が渡されます。
この戻り値がすぐまた今度は args の残りの評価値を引数として
Python 関数として呼び出されますから，Prelude.outchar
は関数を戻り値とする高階関数でなければなりません。
13.2 Prelude.py
修正報告書に規定された標準手続きを定義するため，Prelude.py というモジュールを用意します。
その大部分は 修正報告書 付録２
に基づく内容からなる文字列定数 PRELUDE ですが，
前述の Prelude.outchar 関数など，若干の補助的な定義もあります。
import math, sys def get_file(channel, mode): f = channels.get(channel) if f is None: channels[channel] = f = os.fdopen(channel, mode) return f channels = {0: sys.stdin, 1: sys.stdout, 2: sys.stderr} def inchar(channel, s): rf = get_file(channel, "r") ch = rf.read(1) r = s.find(ch) return r + 1 def outchar(interp): def _outchar(channel, s, i): rf = get_file(channel, "w") ch = s[i - 1] rf.write(ch) if channel == 1: interp.in_new_line = (ch == '\n') return _outchar def maxint(): return sys.maxint def entier(e): return int(math.floor(e)) # 下記は Modified Report on the Algorithmic Language ALGOL 60 (1976) # の Appendix 2 The environmental block を元にしている。 # ただし，同文献の ininteger 手続きの記述の誤りは訂正してある。 PRELUDE = """ begin comment Simple functions; real procedure abs(E); value E; real E; abs := if E >= 0.0 then E else -E; integer procedure iabs(E); value E; integer E; iabs := if E >= 0 then E else -E; integer procedure sign(E); value E; integer E; sign := if E > 0.0 then 1 else if E < 0.0 then -1 else 0; integer procedure entier(E); value E; real E; comment entier := largest integer not greater than E, i.e. E - 1 < entier <= E; entier := _nativecall(`Prelude.entier', E); …… comment Terminating procedures; procedure stop; go to _stoplabel; …… integer procedure maxint; maxint := _nativecall(`Prelude.maxint'); real procedure epsilon; epsilon := 2e-16; ; _stoplabel: end """
利用者が与えた Algol プログラムは，
PRELUDE の中でラベル _stoplabel の直前にあるダミー文 (C 言語などでいう空文)
の位置に置く必要があります。
本インタープリタは，その置き換えを構文木で行います。
class Interpreter: def __init__(self, parser): self.parser = parser def run(self, source_text): "ソーステキストをプログラムとして実行する。" prelude = self.parser.parse(Prelude.PRELUDE) assert isinstance(prelude, Block) assert isinstance(prelude.statements[0], DummyStatement) s = program_tree = self.parser.parse(source_text) while isinstance(s, LabelledStatement): s = s.statements if isinstance(s, Block): s.resolve_identifiers() # PRELUDE の宣言とプログラムからブロックを作る。 prelude.statements[0] = program_tree tree = Block(prelude.declarations, prelude.statements) tree.resolve_identifiers() main = ProcedureQuantity(Identifier("(main)", 1), type=None, params=None, values=None, specs=None, body=tree) ……
13.3 修正報告書のミス
PRELUDE で実装される標準関数のうち,
integer，outinteger，inreal，outreal
の四つの入出力手続きはかなり大きく本格的なコードになっています。
これが動くかどうかで，Algol 処理系自身の妥当性をある程度，検証できます。
本インタープリタは，一応，このテストに合格している模様です。
$ algol60 - begin real x; inreal(0, x); outstring(1, `=> '); outreal(1, x) end ^D 123.456 => 123.4560000000000 $
もっとも，ininteger 手続きは当初なぜか正しく動きませんでした。
類似する inreal 手続きとも比較して調べたところ，本インタープリタのせいではなく，
修正報告書の記述に 6 行ほどコードの欠落があることが判明しました。
オリジナルの修正報告書を入手していないため，元々なのか，それとも HTML 化するときにミスがあったのかは不明です。
PRELUDE 内の ininteger の定義のうち，下記で強調した部分が，修正報告書の欠落を補ったコードです。
procedure ininteger(channel, int);
value channel; integer channel, int;
comment int takes the value of an integer;
begin
integer k, m;
Boolean b, d;
integer procedure ins;
begin
integer n;
comment read one character, converting newlines to spaces;
inchar(channel, `0123456789-+ ;`NL'', n);
ins := if n = 15 then 13 else n
end ins;
comment pass over initial spaces or newlines;
for k := ins while k = 13 do
;
comment fault anything except sign or digit;
if k = 0 or 13 < k then
fault(`invalid character', k);
if 10 < k then
begin
comment sign found, d indicates digit found, b
indicates the sign, m is value so far;
d := false;
b := k /= 11;
m := 0
end
else
begin
d := b := true;
m := k - 1
end;
for k := ins while 1 <= k and k <= 10 do
begin
comment deal with further digits;
m := 10 * m + k - 1;
d := true
end k loop;
comment fault if not digit has been found, or the terminator
was invalid;
if d impl k < 13 then
fault(`invalid character', k);
int := if b then m else -m
end ininteger;
14. メイン・スクリプト algol60
PLY は構文解析ルールから構成した表をカレントディレクトリに parsetab.py として出力し，次回からの処理を高速化します。 しかし，インタープリタを使うとカレントディレクトリに parsetab.py が勝手に作られるのは鬱陶しいものです。 これを解決するには，作成された parsetab.py を Parser.py などを置いているディレクトリに移動させます。 次回からはその parsetab.py が使われ，カレントディレクトリにファイルが作られなくなります。
しかし，ここでは手間を省くため，もっと簡単な方法を採りました。
メイン・スクリプトの中で os.chdir をしてカレントディレクトリそのものを変更します。
#!/usr/bin/env python # -*- mode: python -*- coding: utf-8 -*- """ Algol 60 Interpreter in Python (2.3.5 - 2.6) by (鈴) at Oki Software Last Revised: H20.12/4 """ import os, sys __version__ = "0.6" if len(sys.argv) != 2: print >>sys.stderr, ("algol60 %s in python %d.%d.%d" % ((__version__,) + sys.version_info[:3])) print >>sys.stderr, "usage: algol60 source_file_name" print >>sys.stderr, " algol60 - < source_file_name" sys.exit(1) prog = sys.argv[0] prog_path = os.path.dirname(prog) lib_path = os.path.join(prog_path, "..", "lib", "algol60") lib_path = os.path.abspath(lib_path) sys.path.insert(0, lib_path) try: import psyco psyco.full() except ImportError: pass from Parser import Parser, SyntaxError, SemanticsError from Interpreter import Interpreter parser = Parser(debug=False) interp = Interpreter(parser) if sys.argv[1] == "-": source_text = sys.stdin.read() else: file_name = sys.argv[1] fpath = os.path.abspath(file_name) rf = open(file_name) try: source_text = rf.read() finally: rf.close() try: os.chdir(lib_path) interp.run(source_text) except (SyntaxError, SemanticsError), ex: print "%s: %s" % (ex.__class__.__name__, ex) sys.exit(1)
メイン・スクリプトは次を仮定しています。
- 自分自身のファイル名が algol60 である。
- 自分のおかれているディレクトリから
../lib/algol60/の位置にモジュール群がある。 sys.argv[0]は自分自身への相対パスまたは絶対パスである。
15. インタープリタの使い方
Unix または Unix ライクな環境上で Python 2.3.5 から Python 2.6 までのどれかが動いていれば，すぐに本インタープリタを使うことができます。 少しの修正で，あるいはそのまま，他の環境でも動かすことができると思います。 インタープリタ内部で PLY を使っていますが， 同梱していますから，あらかじめ PLY をインストールしておく必要はありません (インストールしてあっても構いません)。
$ bzcat algol60-0.6.tar.bz2 |tar xf - $ cd algol60-0.6 $ ls -F bin/ demo/ lib/ $ ./bin/algol60 demo/factorial.txt n := 1 1 1 n := 5 5 120 n := 10 10 3628800 n := 100 100 9332621544394415268169923885626670049071596826438162146859296389521759999322 99156089414639761565182862536979208272237582511852109168640000000000000000000000 00 n := -1 $ ./bin/algol60 demo/absmax.txt ans := 21.20000000000000 at 1 2 $
パスの通った場所にインストールするには algol60-0.6 の下にある bin と lib の内容 (どちらも algol60 という名前です) を 適当な場所 (/usr/local や ~/ など) の bin と lib の下にうつします。
$ cd algol60-0.6 $ mv bin/algol60 ~/bin $ mv lib/algol60 ~/lib
ちなみに，インタープリタの性能のめやすとして，tak 関数について L2 Lisp 7.2, 7.3 と比べると，同じ Python 上の L2 Lisp 7.2 の半分未満の実行速度でした。 これは Ruby 上の L2 Lisp 7.3 とほぼ同じです。 改善の余地はあるものの，初期の版としてはまあまあと言えるでしょう。 使ったのは，OS X 10.4.11/Core Duo 2GHz 上の Python 2.6 + Psyco 1.6 と Ruby 1.8.6 です。
% cat tak.l
(defun tak (x y z)
(if (>= y x)
z
(tak (tak (- x 1) y z)
(tak (- y 1) z x)
(tak (- z 1) x y))))
(print (tak 18 12 6)) ; 7
% time L2Lisp.py tak.l
7
L2Lisp.py tak.l 3.05s user 0.06s system 91% cpu 3.387 total
% cat tak.txt
begin
integer procedure tak (x, y, z);
value x, y, z;
integer x, y, z;
tak :=
if x <= y then z
else tak (tak (x - 1, y, z),
tak (y - 1, z, x),
tak (z - 1, x, y));
integer i;
i := tak (18, 12, 6); comment => 7;
outinteger (1, i)
end
% time algol60 tak.txt
7
algol60 tak.txt 8.27s user 0.07s system 99% cpu 8.353 total
% time L2Lisp.rb tak.l
7
L2Lisp.rb tak.l 8.28s user 0.03s system 93% cpu 8.856 total
%
15.1 同梱の PLY について
便宜のため，本インタープリタは， http://www.dabeaz.com/ply/ で配布されている PLY-2.5 のファイルを最小限だけ同梱しています。 algol60-0.6/lib/algol60/ply/ 以下がそのファイルです。
実際にそこをみると Yacc 相当モジュールとして yacc.py と yacc.py.orig があることに気付くと思います。 yacc.py.orig が元々の PLY-2.5 のファイルです。 yacc.py は，Python 2.6 で md5 モジュールが deprecate されたことを受けて， Python 2.3.5 から Python 2.6 まで対応できるように私が一部修正したファイルです。 Python 2.5.* までならば (あるいは Python 2.6 でも警告を気にしないならば) オリジナルの PLY-2.5 のファイルを使っても問題ありません。
--- ply/yacc.py.orig 2008-05-29 01:13:22.000000000 +0900
+++ ply/yacc.py 2008-12-02 17:35:52.000000000 +0900
@@ -71,7 +71,13 @@
yaccdevel = 0 # Set to True if developing yacc. This turns off optimized
# implementations of certain functions.
-import re, types, sys, cStringIO, md5, os.path
+import re, types, sys, cStringIO, os.path
+try:
+ import hashlib
+ def md5new(): return hashlib.md5()
+except ImportError:
+ import md5
+ def md5new(): return md5.new()
# Exception raised for yacc-related errors
class YaccError(Exception): pass
@@ -1156,7 +1162,7 @@
Errorfunc = None # User defined error handler
- Signature = md5.new() # Digital signature of the grammar rules, precedence
+ Signature = md5new() # Digital signature of the grammar rules, precedence
# and other information. Used to determined when a
# parsing table needs to be regenerated.
16. ここまでのまとめ
ここで作成したインタープリタは，言語仕様の点では一応，Algol 60 のフルセットです。
ミニチュアのサブセットではありません。
Lisp のようにエキゾチックではない，普通の
外見をもったプログラミング言語の，約 2700 行の Python コード (PRELUDE の Algol 60
コードを含む) による実装として，
いろいろな処理系づくりの参考やたたき台に役立つのではないかと思います。
構成上，この処理系をコンパイラではなくインタープリタにしているのは Interpreter.py です。 ここだけ差し替えれば，コンパイラにすることもできます。