簡単なAPLインタプリタを構築しよう - パート1
Let's build a simple interpreter for APL – part 1 (mathspp.com)
要約
この記事は、PythonでAPLインタプリタを構築するシリーズの第1弾です。APLの構文解析の基本に焦点を当て、数値(整数、浮動小数点数、負数)、基本的な算術演算子、およびコンマ演算子(⍨)を処理するためのトークナイザを実装する方法を解説しています。ソースコードを右から左へトークン化するアプローチが採用されています。
全文翻訳
Let's build a simple interpreter for APL - part 1
[画像: コンピュータの前に立つ人物の白黒の落書き]
前書き
まず最初に、Ruslan Spivak氏のPascalインタプリタ構築に関するブログ記事シリーズに敬意を表します。私は数年前にこのシリーズの冒頭を読み、Rojプログラミング言語を作成することに至りました。今回は、Pascalとはかなり異なるAPLのインタプリタを構築することを目的として、再びこのシリーズを読み直しています。
APLインタプリタを書き、それについて書いている理由は以下の通りです。
- APLを学ぶのに役立つからです。
- Pythonのスキルを活かし、向上させることができます。
- コードを機能させるために行ったことを文書化できます。
- もしあなたがAPLインタプリタを自分で書くことにした場合、その手助けができます!
LSBASIシリーズを知っている方のために言っておくと、私のLSBASIシリーズの番号付けはSpivak氏のものと一致しません。これは、このインタプリタではSpivak氏が考慮しなかった(またはその逆の)事柄を考慮する必要があるためです。APLとPascalは、ある側面において非常に異なる特性を持っているからです。一方で、始まりはかなり似ており、この記事ではSpivak氏の8番目のブログ記事の半ばに相当する作業を紹介します。
コード
このプロジェクトのコードはこのGitHubリポジトリで入手できますので、ぜひスターを付けてください ;) このパートのソースコードは単にrgspl1.pyファイルです。試してみるためにダウンロードできます。
目標
このブログ記事シリーズは、APLインタプリタを構築する私の旅に沿ったものになります。最終目標は、Pythonで書かれた完全に機能するAPLインタプリタを持つことです!それは大変な作業になるでしょう ;)
今日の目標
この記事では、このプロジェクトを開始するための基本を説明します。特に、以下の要素を持つ単純なAPLステートメントを解析できるようになることを目指します。
- 浮動小数点数と整数(正数と負数 - APLでは
¯を使用して数値を否定します。例:¯3は (-3) です)およびそれらのベクトル。 - 関数
+-×÷の単項および二項バージョン。 - 交換/スイッチ演算子
⍨。 - 括弧で囲まれた式。
トークン化
最初に行うべきことは、APLソースコードを取得し、不要なもの(空白など)を取り除き、各文字が何を表すかを見つけることです。例えば、数値を検索して、それらが整数か浮動小数点数かを判断したり、APLのグリフを見てそれらを名前に割り当てたりします。
ここで使用するさまざまなトークンタイプを定義するTokenクラスのコードを示します。
class Token:
"""Represents a token parsed from the source code."""
INTEGER = "INTEGER"
FLOAT = "FLOAT"
PLUS = "PLUS"
MINUS = "MINUS"
TIMES = "TIMES"
DIVIDE = "DIVIDE"
NEGATE = "NEGATE"
COMMUTE = "COMMUTE"
LPARENS = "LPARENS"
RPARENS = "RPARENS"
EOF = "EOF"
# Helpful lists of token types.
FUNCTIONS = [PLUS, MINUS, TIMES, DIVIDE]
MONADIC_OPS = [COMMUTE]
# What You See Is What You Get characters that correspond to tokens.
WYSIWYG = "+-×÷()⍨"
# The mapping from characteres to token types.
mapping = {
"+": PLUS,
"-": MINUS,
"×": TIMES,
"÷": DIVIDE,
"(": LPARENS,
")": RPARENS,
"⍨": COMMUTE,
}
def __init__(self, type_, value):
self.type = type_
self.value = value
def __str__(self):
return f"Token({self.type}, {self.value})"
def __repr__(self):
return self.__str__()
これらのトークンタイプと__str__および__repr__メソッド(トークンインスタンスをより分かりやすく表示できるようにする)を定義した後、5 + 6のような文字列を[Token(EOF, None), Token(INTEGER, 5), Token(PLUS, +), Token(INTEGER, 6)]のようなトークンリストに変換できるようにする必要があります。
EOFトークン(end-of-fileトークン)がリストの最初にあることに注意してください。これは、APLの実行順序である右から左へAPLソースコードをトークン化することにしたためです。この決定が後で問題にならないことを願っています!
ちなみに、ここで間違いをたくさん犯すことをお知らせするのに良い機会かもしれません!もし、ある時点で何かを別の方法で行うアイデアがあれば、ぜひ試してみて、それがどうだったかを下のコメントで教えてください。
プログラムに戻り、Tokenクラスはすでにあります。次に、文字列を受け取ってトークンリストを構築するTokenizerを定義します。クラスの始まりは次のとおりです。
class Tokenizer:
"""Class that tokenizes source code into tokens."""
def __init__(self, code):
self.code = code
self.pos = len(self.code) - 1
self.current_char = self.code[self.pos]
def error(self, message):
"""Raises a Tokenizer error."""
raise Exception(f"TokenizerError: {message}")
def advance(self):
"""Advances the cursor position and sets the current character."""
self.pos -= 1
self.current_char = None if self.pos < 0 else self.code[self.pos]
# ...
このクラスをAPLコードの文字列でインスタンス化します。例えばTokenizer("5 + 6")です。error関数は、Tokenizerで問題が発生した場合に例外を発生させるためのヘルパー関数として使用されます。
最後に、advance関数は、トークナイザの「カーソル」を左に移動させ、current_charを保持するヘルパー変数を再定義する小さなユーティリティ関数です。APLコード全体を処理し終え、文字列の末尾(実際には右から左へ移動しているので先頭ですが)に達すると、current_charをNoneに設定して、これ以上処理するものがないことを示します。
このスケルトンが構築されたので、クラスの残りの部分は次のようになります。
class Tokenizer:
# ...
def skip_whitespace(self):
"""Skips all the whitespace in the source code."""
while self.current_char and self.current_char in " \t":
self.advance()
def get_integer(self):
"""Parses an integer from the source code."""
end_idx = self.pos
while self.current_char and self.current_char.isdigit():
self.advance()
return self.code[self.pos+1:end_idx+1]
def get_number_token(self):
"""Parses a number token from the source code."""
parts = [self.get_integer()]
# Check if we have a decimal number here.
if self.current_char == ".":
self.advance()
parts.append(".")
parts.append(self.get_integer())
# Check for a negation of the number.
if self.current_char == "¯":
self.advance()
parts.append("-")
num = "".join(parts[::-1])
if "." in num:
return Token(Token.FLOAT, float(num))
else:
return Token(Token.INTEGER, int(num))
def get_wysiwyg_token(self):
"""Retrieves a WYSIWYG token."""
char = self.current_char
if char in Token.mapping:
self.advance()
return Token(Token.mapping[char], char)
self.error("Could not parse WYSIWYG token.")
def get_next_token(self):
"""Finds the next token in the source code."""
self.skip_whitespace()
if not self.current_char:
return Token(Token.EOF, None)
if self.current_char in "0123456789":
return self.get_number_token()
if self.current_char in Token.WYSIWYG:
return self.get_wysiwyg_token()
self.error("Could not parse the next token...")
def tokenize(self):
"""Returns the whole token list."""
tokens = [self.get_next_token()]
while tokens[-1].type != Token.EOF:
tokens.append(self.get_next_token())
return tokens[::-1]
上記のコードを使用すると、5 -⍨ ¯2.3という式は、print(Tokenizer("5 -⍨ ¯2.3").tokenize())を実行した場合、[Token(EOF, None), Token(INTEGER, 5), Token(MINUS, -), Token(COMMUTE, ⍨), Token(FLOAT, -2.3)]のようにトークン化されます。信じられませんか?単に式をコピーして
5 -⍨ ¯2.3
スクリプトを実行して得られる読み込み-評価-印刷ループに貼り付けてみてください。
Tokenリスト内の構造を見つける
すべてのトークンを取得したら、それらをより構造化された方法で表現したいと考えます。その目的のために、抽象構文木(AST)と呼ばれるものを構築します(Spivak氏の7番目のLSBASI投稿を参照)。
このAST構造により、APLプログラムを解釈することがはるかに容易になります。そのために支払う代償は、まずツリーを構築することです。これは、トークンリスト(ここでも右から左へ)を走査し、スカラー、配列、演算子、二項関数/単項関数が何であるかを決定することによって行われます。これが私たちのASTが行う仕事です。その後、プログラムの解釈は非常に簡単になります。
これらのルールをどのようにAST構築に変換するかを知るために、まず実装したいAPL言語のサブセットの文法を考案することから始めました。文法は、言語でどのような種類のステートメントが意味をなすかを指定するために使用する記法ツールにすぎません。私たちの場合は、APLで意味をなすステートメントの種類を指定するために文法を構築します。
壁に頭をぶつけすぎて頭蓋骨がひび割れるほど苦労した後、
[画像: ひび割れた壁にもたれかかる頭の白黒の落書き]
多くの熟考、多くの下書き、そしてAPL Orchardの親切なグループからの助けを得て、右から左へ読むことを意図したこの文法を作成しました。
PROGRAM := EOF STATEMENT
STATEMENT := ( ARRAY FUNCTION | FUNCTION )* ARRAY
ARRAY := ( "(" STATEMENT ")" | SCALAR )+
SCALAR := INTEGER | FLOAT
FUNCTION := F | FUNCTION "⍨"
F := "+" | "-" | "×" | "÷"
各行はルールを表し、それは下のルールに依存する場合があります。最終的には、手元にあるトークンを見るだけでチェックできるFまたはSCALARのようなルールに到達します。この文法が機能する方法は、ルールを(右から左へ、APLがプログラムを解釈する方法で)上から下へ読むことです。
- プログラムは、ステートメントとファイルの終端です。
- ステートメントは、配列の後に、0回以上の単一の関数(これらは単項関数になります)または関数の後に別の配列(これらは二項関数になります)が続きます。
- 配列は、1つ以上のスカラーまたは括弧で囲まれたステートメントです。
- スカラーは、整数トークンまたは浮動小数点数トークンのいずれかです。
- 関数は、交換演算子と関数、または単一のfです。
- fは、私たちが知っているすべてのAPL関数のセットの短い名前です:
+-×÷。
互いに参照し合うルールや、階層の上位にあるルールを参照するルールがあることに注意してください。これらの自己参照と再帰は、文法を豊かにしますが、ASTの解析を少し難しくします。
これらのルールをASTを構築するコードに変換する方法は簡単です。まず、ASTが持つさまざまなノードのタイプを定義します。現時点では、スカラー、配列、二項関数、単項関数、および演算子です。
class ASTNode:
"""Stub class to be inherited by the different types of AST nodes.
The AST Nodes are used by the Parser instances to build an
Abstract Syntax Tree out of the APL programs.
These ASTs can then be traversed to interpret an APL program.
"""
class Scalar(ASTNode):
"""Node for a simple scalar like 3 or ¯4.2"""
def __init__(self, token):
self.token = token
self.value = self.token.value
def __str__(self):
return f"S({self.value})"
def __repr__(self):
return self.__str__()
class Array(ASTNode):
"""Node for an array of simple scalars, like 3 ¯4 5.6"""
def __init__(self, children):
self.children = children
def __str__(self):
return f"A({self.children})"
def __repr__(self):
return self.__str__()
class MOp(ASTNode):
"""Node for monadic operators like ⍨"""
def __init__(self, token, child):
self.token = token
self.child = child
def __str__(self):
return f"MOp({self.token.value} {self.child})"
def __repr__(self):
return self.__str__()
class Monad(ASTNode):
"""Node for monadic functions."""
def __init__(self, token, child):
self.token = token
self.child = child
def __str__(self):
return f"Monad({self.token.value} {self.child})"
def __repr__(self):
return self.__str__()
class Dyad(ASTNode):
"""Node for dyadic functions."""
def __init__(self, token, left, right):
self.token = token
self.left = left
self.right = right
def __str__(self):
return f"Dyad({self.token.value} {self.left} {self.right})"
def __repr__(self):
return self.__str__()
どのようなノードタイプがあるかを知った後、Tokenizerを入力として受け取り、トークンリストをASTに解析するためのメソッドを提供するParserクラスを定義します。
Parserクラスの始まりは次のとおりです。
class Parser:
"""Implements a parser for a subset of the APL language.
The grammar parsed is available at the module-level docstring.
"""
def __init__(self, tokenizer, debug=False):
self.tokens = tokenizer.tokenize()
self.pos = len(self.tokens) - 1
self.token_at = self.tokens[self.pos]
self.debug_on = debug
def debug(self, message):
"""If the debugging option is on, print a message."""
if self.debug_on:
print(f"PD @ {message}")
def error(self, message):
"""Throws a Parser-specific error message."""
raise Exception(f"Parser: {message}")
def eat(self, token_type):
"""Checks if the current token matches the expected token type."""
if self.token_at.type != token_type:
self.error(f"Expected {token_type} and got {self.token_at.type}.")
else:
self.pos -= 1
self.token_at = None if self.pos < 0 else self.tokens[self.pos]
def peek(self):
"""Returns the next token type without consuming it."""
peek_at = self.pos - 1
return None if peek_at < 0 else self.tokens[peek_at].type
私たちのParserインスタンスは、debugというキーワード引数(デフォルトはFalse)を受け取ります。これを使用して、上記の文法の各ルールの一致を開始するときのようなデバッグメッセージを印刷できます。Tokenizerと同様に、errorメソッドも定義します。
このクラスで新しいのは、ヘルパー関数eatとpeekです。eat関数は、指定されたトークンタイプを見ているはずであり、次に進みたい場合に使用されます。見ているはずのトークンタイプを「消費」し、正しければそのまま進みます。間違っていた場合は、クラスがエラーを発生させます。
例えば、SCALAR := INTEGER | FLOATというルールがあるとします。そのルールを一致させようとしていて、整数がないことがわかっている場合、それは浮動小数点数であるはずであり、「eat」して浮動小数点数を消費できます。
peekメソッドは、次のトークンが何であるかを確認できますが、現在のトークンを消費しません。現在のトークンを見ても何を見ているかを判断するのに十分でない場合に必要です。
例えば、+を見ている場合、次のトークンで配列が始まるかどうかを確認するまで、それが単項関数なのか二項関数なのかを知ることはできません。
これらのヘルパー関数を配置した後、文法のルールに対応するparse_*メソッドを定義します。各メソッドは、ルールによってASTに解析されたコードの部分を表すノードを返します。
class Parser:
# ...
def parse_program(self):
"""Parses a full program."""
self.debug(f"Parsing program from {self.tokens}")
node = self.parse_statement()
self.eat(Token.EOF)
return node
def parse_statement(self):
"""Parses a statement."""
self.debug(f"Parsing statement from {self.tokens[:self.pos+1]}")
node = self.parse_array()
while self.token_at.type in Token.FUNCTIONS + Token.MONADIC_OPS:
# pylint: disable=attribute-defined-outside-init
func, base = self.parse_function()
if isinstance(base, Dyad):
base.right = node
base.left = self.parse_array()
elif isinstance(base, Monad):
base.child = node
else:
self.error(f"Got {type(base)} instead of a Monad/Dyad.")
node = func
return node
def parse_array(self):
"""Parses an array composed of possibly several simple scalars."""
self.debug(f"Parsing array from {self.tokens[:self.pos+1]}")
nodes = []
while self.token_at.type in [Token.RPARENS, Token.INTEGER, Token.FLOAT]:
if self.token_at.type == Token.RPARENS:
self.eat(Token.RPARENS)
nodes.append(self.parse_statement())
self.eat(Token.LPARENS)
else:
nodes.append(self.parse_scalar())
nodes = nodes[::-1]
if not nodes:
self.error("Failed to parse scalars inside an array.")
elif len(nodes) == 1:
node = nodes[0]
else:
node = Array(nodes)
return node
def parse_scalar(self):
"""Parses a simple scalar."""
self.debug(f"Parsing scalar from {self.tokens[:self.pos+1]}")
if self.token_at.type == Token.INTEGER:
node = Scalar(self.token_at)
self.eat(Token.INTEGER)
else:
node = Scalar(self.token_at)
self.eat(Token.FLOAT)
return node
def parse_function(self):
"""Parses a function possibly monadically operated upon."""
self.debug(f"Parsing function from {self.tokens[:self.pos+1]}")
if self.token_at.type in Token.MONADIC_OPS:
node = MOp(self.token_at, None)
self.eat(self.token_at.type)
node.child, base = self.parse_function()
else:
base = node = self.parse_f()
return node, base
def parse_f(self):
"""Parses a simple one-character function.
We have to peek forward to decide if the function is monadic or dyadic.
"""
self.debug(f"Parsing f from {self.tokens[:self.pos+1]}")
if self.peek() in [Token.RPARENS, Token.INTEGER, Token.FLOAT]:
node = Dyad(self.token_at, None, None)
else:
node = Monad(self.token_at, None)
self.eat(node.token.type)
return node
def parse(self):
"""Parses the whole AST."""
return self.parse_program()
これらのすべてのメソッドを使用すると、非常に単純なAPLプログラムをASTに解析できるようになり、次のブログ記事で解釈できるようになります!
上記のリンクで、式 ×⍨ 4.5 - (4 ¯3 5.6) が MOp(⍨ Monad(× Dyad(- S(4.5) A([S(4), S(-3), S(5.6)])))) に解析されるのを確認できます。Aは配列、Sはスカラーを表します。
次回のブログ記事に向けて
次のブログ記事では、
- Visitorパターンを実装してASTを解釈し、最終結果を生成します。Spivak氏の8番目の投稿で彼がどのように行ったかを確認できます。
- スカラー/配列の代入を実装します。
⋄で区切られた複数のステートメントを許可します。
演習
プログラミングスキルを練習し、何が起こっているのかを本当に理解していることを確認するために、TokenizerとParserクラスを変更して、関数 ⌈ と ⌊ も処理できるようにすることをお勧めします。
もしあなたが十分に勇敢だと感じたら、次のブログ記事の変更点を自分で実装してみてください!
また次回お会いしましょう!
シリーズ
これは私がゆっくりと、しかし着実に取り組んでいるシリーズです。次の記事がいつ公開されるかの見積もりが必要な場合は、コメントまたはメールで私に連絡してください :) それまで、シリーズのすべての記事のリストを以下に示します。
- Let's build a simple interpreter for APL - part 1
- Let's build a simple interpreter for APL - part 2
- Let's build a simple interpreter for APL - part 3 - the array model
- Let's build a simple interpreter for APL - part 4
会話で最も賢いPython 🐍開発者になろう 🚀
毎週月曜日、アナロジー、図、コード例を使ってトピックを掘り下げ、より明確で、より速く、より慣用的なコードを書けるようになるPythonの深掘り情報をお届けします。