Arantium Maestum

プログラミング、囲碁、読書の話題

Python

LispKit Lisp処理系の実装 6:SECD抽象機械の状態遷移〜条件分岐、関数関連など

前回に続いてstep関数内の命令コードに対するパターンマッチを見ていく。 今回見ていくのは以下の命令コード: 条件分岐のSEL、JOIN スタックに値を乗せるLD、LDC、LDF 関数適用のAP、RTN 再帰関数のためのDUM、RAP プログラム停止のSTOP 条件分岐のSEL、JOI…

LispKit Lisp処理系の実装 5:SECD抽象機械の状態遷移〜リスト操作と比較・算術演算

前回の記事ではSECD抽象機械のメモリとレジスタを定義していった。今回(と次回)はSECD抽象機械が実際にどうやってプログラムを実行するかを見ていく。 SECDマシン上でプログラムを実行するということは、Controlレジスタcが指し示すコンパイルされたプログ…

LispKit Lisp処理系の実装 4:SECD抽象機械のメモリとレジスタ

前回はLispKit Lispの挙動を確認するためもあってASTを直接実行するインタプリタを実装した。これからはLispKit LispのプログラムをSECD抽象機械上で実行するために必要なものを揃えていく。 今回と次回はSECDマシン自体の実装の話。 SECDマシン SECD抽象機…

LispKit Lisp処理系の実装 3:インタプリタ〜条件分岐から関数適用まで

前回に続いてインタプリタの実装。今回はeval_の後半、IFによる条件分岐以降の項目を見ていく。 条件分岐のパターンマッチ 条件式を評価してその結果に対してパターンマッチ、分岐部分の式は片方しか評価されない。 case Cons(Alpha("IF"), Cons(e1, Cons(e2…

LispKit Lisp処理系の実装 2:インタプリタ〜変数から算術演算子まで

前回のパーサの出力するASTをそのまま実行するインタプリタを実装する。 インタプリタを実装する意義 「SECD抽象機械へのコンパイラ実装の前にインタプリタを作る」というのはHendersonのFunctional Programming Application & Implementationでの流れに従っ…

LispKit Lisp処理系の実装 1:パーサ

前回書いたとおりまずはパーサを実装する。 最近散々パーサ実装について書いてきてなんだが、Lispなのでかなりの手抜きパーサ。 字句解析 まずはトークンの定義: from dataclasses import dataclass @dataclass class Lparen: pass @dataclass class Rparen…

LispKit Lisp処理系の実装 序

純粋関数型Lisp方言であるLispKit LispのインタプリタとSECD抽象機械の機械語へのコンパイラを作成する。 タネ本はHendersonの「Functional Programming - Application & Interpretation」で、この本に載っているISWIMやPASCALのコードを大体なぞるようにPyt…

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのメモリ効率化

前回まで見てきたBacktrackingパーサ、Packratパーサは「これまで見たすべてのトークン」をメモリ上のバッファに保持し続け、それらに対してのパース結果もすべてキャッシュに残し続ける実装になっていて、パース終了直前にはソースファイルのすべてのトーク…

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのキャッシュクリア

前回のコードだとparse関数を複数回呼び出すと前回のキャッシュが残っていてパースがうまくいかない問題があった。parse呼び出しごとにキャッシュをクリアするようにしたい。 キャッシュ xparser.pyモジュールのトップレベルにキャッシュのリストとそのリス…

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサ

前回の記事は同じパースを何回も繰り返すので非効率だと書いたが、まずはどの程度非効率なのかを計測してからPackratパーサで効率化を図る。 計測 まずは問題の程度を計測したい。 こんなデコレータを定義する: def _print_call(func): @functools.wraps(fu…

PythonでLanguage Implementation Patternsのパーサと戯れる Backtrack可能なパーサ

前回実装したBacktrackableストリームを使って「任意のトークンを消費してパースを試した上でバックトラックできる」パーサを実装していく。 言語 前回同様の言語。再掲するとこのようなもの: list : '[' elements ']'; elements : element (',' element)*;…

PythonでLanguage Implementation Patternsのパーサと戯れる Backtrackableストリームオブジェクト

前回のような固定数のトークン先読みではなく、任意のトークンを消費しつつパースし続け、失敗したらバックトラックするようなパーサを作りたい。 今回の記事はまずバックトラック機能を提供するトークンストリームのクラスを作成する。(パーサ本体は次回)…

PythonでLanguage Implementation Patternsのパーサと戯れる LL(2)再帰的パーサ

先読み要素を増やすことで前回のLL(1)パーサより複雑な構文をパースできるようになる。 言語 ここまで見てきたリスト言語に変数間の代入を追加する: list : '[' elements ']'; elements : element (',' element)*; element : NAME | assign | list; assign …

PythonでLanguage Implementation Patternsのパーサと戯れる ネストしたリストのLL(1)再帰的パーサ

前回の記事の言語とパーサを拡張して、ネストありリスト言語の再帰下降パーサを作る。 言語 文法はこの通り: list : '[' elements ']'; elements : element (',' element)*; element : NAME | list; # elementが再帰的にlistになり得る NAME : ('a'..'z' | …

PythonでLanguage Implementation Patternsのパーサと戯れる 簡単なリスト言語の非再帰的なパーサ

(注:この記事を出した当初はパースが成功した場合Trueを返す実装にしていたが、Language Implementation Patternsと同じように成功した場合は何も返さないように修正した。実装がスッキリするということと、失敗は例外で表現しているので返り値には意味が…

PythonでLanguage Implementation Patternsのパーサと戯れる lexerとPeekableストリームオブジェクト

パーサを作るにあたってまずはlexerから。 lexerと簡単なパーサで共通しているのは「消費可能なストリームの先頭を『消費することなく』先読みする必要がある」という点。lexerだと入力の文字のストリーム、パーサだとlexerの返すトークンストリーム、と対象…

PythonでLanguage Implementation Patternsのパーサと戯れる 序

前2回の記事でも書いたとおり、Language Implementation Patternsのはじめの方をPythonで実装している。 具体的にはPackrat Parsingまで、本に出てくるクラスベースな実装ではなく、lookaheadやbacktrackの機能はトークンストリームの方に持たせた上で相互…

Language Implementation PatternsのLL(1) ParserをPythonで実装してみる

前回に続いてLanguage Implementation PatternsのJava実装例をPythonでやってみる。 今回はLL(1) Recursive Descent Parser。 パース対象 パースする言語は前回と同様: list : '[' elements ']'; elements : element (',' element)*; element : NAME | list…

Language Implementation PatternsのLL(1) LexerをPythonで実装してみる

Language Implementation Patternsという本がある。翻訳もされていて、邦題は「言語実装パターン―コンパイラ技術によるテキスト処理から言語実装まで」。作者はTerrence Parrで、ANTLRというJavaベースのパーサ・ジェネレータの開発者。 パーサ作成から始め…

Pythonで参照渡し

最近こういうツイートを見た。 なんか参照渡しでツイッター検索すると、Pythonに参照渡しがあるという一大宗教があるらしい誰が教祖だ?— (call me #'knjname) (@knjname) August 22, 2021 実際「値渡し」「参照渡し」という用語はCやC++などの「変数が多く…

PythonでリテラルなしIfなし変数束縛なしFizzBuzzワンライナー〜ラムダの力を讃えよ〜

前回こう書いた通り: 追記:前回の記事に書き忘れたが、walrus operatorことAssignment Expressionsを多用しているのでPython3.8以降が必要。 これまで見てきたワンライナーはPython3.8から導入された変数束縛式:=を使っていて、そのせいで最近のPythonバー…

PythonでリテラルなしIfなしFizzBuzzワンライナー

前回の記事のFizzBuzzコードをちょこっといじってこんな感じで満足していた: リテラルを使わず簡潔な高可読性FizzBuzzが書けるプログラマです(f:=lambda *a,A=id,Fizz=id,Buzz=id:len(a) or (k:=sorted(f.__kwdefaults__)) and print(A if (x:=A%f(f,f,f))*…

PythonでリテラルなしFizzBuzzワンライナー

ツイッターでこういう話が出ていた(@nishio さん、面白いお題をありがとうございます!): リテラル禁止FizzBuzz大会、開幕!(待て https://t.co/zpIirtNpmO— nishio hirokazu (@nishio) April 16, 2021 リテラルなしでFizzBuzz?出来らぁ! class Fizz: d…

lambda関数だけのPython世界で四則演算

お察しかもしれないがラムダ計算についての話である。 最近あったPyConで気になるチュートリアルがあった: www.youtube.com このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、 Pythonのlambdaキーワードで作る無名関数…

100 Days of Codeをやってみた

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。 100 Days Of Code概要 ルールは簡単: なるべく毎日1時間以上、業務外のコードを書く github…

PythonでForth処理系を書く! その7(繰り返し処理 DO-LOOP)

繰り返し処理を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも書いた通り、この構文の要素は3つあって: DOでスタックに乗っている二つの整数を分岐のために使う スタックから得たはじめの整数がループカウンタの…

PythonでForth処理系を書く! その6(条件分岐 IF-ELSE-THEN)

条件分岐を実装する。 PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。 上記の記事からの再掲になるが、このような構文で: 1 IF 2 ELSE …

PythonでForth処理系を書く! その5(Read-Eval-Print-Loop)

REPL機能を実装する。 main.pyに引数がなければREPLを実行するようにする(引数としてファイル名が渡されていればそのファイルを実行)。REPLは一行ずつユーザからForthコードを受け取り、今まで受け取ったコードの環境を引き継ぎつつ実行する。 github.com …

PythonでForth処理系を書く! その4(内部状態をPython Dictionaryに保存)

前回の終わりで書いたように、Forth処理系の内部状態、とくにコンパイラ部分とインタプリタ部分のものをデータ構造として抜き出して、保存・出力できるようにしたい。 その変更がこれ: github.com 主要な変更は二点: 内部状態をPythonのDictionaryで表し、…

PythonでForth処理系を書く! その3(最低限の機能)

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestum でも書いた通り、まずは以下の機能を最低限として実装する: 整数をスタックに乗せる スタックから二つの整数をとり、それらを足し合わせた整数をスタックに乗せる スタックから整数…