はじめに
タイトル通りの話です.なお,この記事を書いている2024/10/30時点のお話ですので,記事をご覧になられている時には修正(?)されているかもしれません.
また,AtCoderや><>
のことをご存じではない方は,><>
でAtCoderをやる記事を書いたのでこれを参考にしてください.
AtCoderに提出したのは以下のようなコードです.なお,問題の原因になったところのみを抽出しておりますので,実際のコードとは違うことにご注意ください.
公式のインタープリタやオンラインインタープリタでは問題なく実行できたものの,AtCoderではエラーが発生してしまいました.
"1"32p "1"f2p v
v <
\
> $ ;
実行前
実行後
どうやらAtCoderの実行環境では,p
命令でコードが配置されるコードブロックの外に書き込んだ命令を実行することができないようです.(つまり,$(15,2)$に追加された1
を実行できないため,スタックに2つの数字がなく$
を実行できない)
「これはAtCoderのバグだ!」ということを言いたいわけではありません.そもそも><>
の仕様書すら見つからない(esolang wiki以外に情報がほとんどない)ため,私にはどの実装が正しいのかわかりません泣.
どちらかというと,C++におけるgccとClangの違いのようなものだと考える方がいいと思います.
とはいえAtCoderで><>
を使う以上は,処理系によってどのような差があるかは知っておくべきだと感じたので,様々な環境でp
命令とg
命令の処理を検証してみました.
検証に使用するインタープリタ
- 公式のインタープリタ(Python製) fish.py
- オンラインインタープリタ(TypeScript製) fishlanguage,Mousetail's Fish Interpreter
- Rust製インタープリタ fishr
- AtCoderのコードテスト
なお,AtCoderの使用できる言語とライブラリの一覧を確認するとfishrを用いていると書いてありましたので,AtCoderのコードテストでもfishrが使われているものだと思います.
検証方法
以下のコードをそれぞれ実行し出力結果を確認します.出力ができなければどのようになったか(無限ループor実行時エラー)を確認します.
00g n 100p " "o 00g n ;
v
\32g n " "o 132p 32g n
;
ffg n " "o 1ffp ffg n;
"v"70p > "N" o ;
> "Y" o ;
"'Y'o;" 0fp 0ep 0dp 0cp 0bp v
> "N" o; v
v <
検証結果
[1] コードブロック上にg
とp
をする場合
fish.py | fishlanguage | Mousetail | fisr | AtCoder |
---|---|---|---|---|
0 1 | 32 1 | 32 1 | 0 1 | 0 1 |
上段にインタープリタ,下段にプログラムの実行結果を表示しております.
想定される動作としては1回目のn
で0
が出力され,2回目にp
で書き込んだ1
が出力されるというものです.
AtCoderのインタープリタは公式のインタープリタと同じ動作をしていますが,まさかのオンラインインタープリタが2つとも公式と違う動作をしています.2つとも空白(SPC)を表すASCIIコードの32
を出力しています.
[2] コードブロック上だが何も書かれていない領域で同じことをする場合
fish.py | fishlanguage | Mousetail | fisr | AtCoder |
---|---|---|---|---|
0 1 | 0 1 | 0 1 | 0 1 | 0 1 |
すべて公式のインタープリタと同じ結果です.
[3] コードブロック外にg
とp
をする場合
fish.py | fishlanguage | Mousetail | fisr | AtCoder |
---|---|---|---|---|
0 1 | 0 1 | 0 1 | 0 1 | 0 1 |
これもすべて公式のインタープリタと同じ結果です.
[4] コードブロック内にp
で命令を書き込み実行する
fish.py | fishlanguage | Mousetail | fisr | AtCoder |
---|---|---|---|---|
Y | Y | Y | Y | Y |
同様にすべて公式のインタープリタと同じ結果です.
[5] コードブロック外にp
で命令を書き込み実行する
fish.py | fishlanguage | Mousetail | fisr | AtCoder |
---|---|---|---|---|
Y | Y | Y | N | N |
前述のとおり,AtCoderのインタープリタは公式のインタープリタとは違う結果を出力しています.
まとめ
以上より実際に,AtCoderのインタープリタと公式のインタープリタの処理に差があると分かりました.
加えて,オンラインインタープリタと公式のインタープリタの間にも処理に差があると分かりました.
- オンラインインタープリタでは空白(SPC)が書かれているマスに
g
すると32
が返る - AtCoderではコードブロックの外に
p
した命令を実行できない,ただし,書き込めないわけではなくg
で値を取得することはできる
インタープリタのソースコードを読んでみる
幸い><>
のインタープリタのソースコードはGitHub上に公開されているので,p
g
周りの実装を確認し,検証の結果が正しいかを確かめました.
とはいえ,私はRustを読めないのでRustの入門書を片手にさらっと確認しただけですので,間違った解釈をしているかもしれません.ご容赦ください.
fish.py (公式のインタープリタ)
以下のコードはfish.pyの引用です.
https://gist.github.com/anonymous/6392418
class Interpreter:
"""
><> "compiler" and interpreter.
"""
def __init__(self, code):
"""
Initialize a new interpreter.
Arguments:
code -- the code to execute as a string
"""
# check for hashbang in first line
lines = code.split("\n")
if lines[0][:2] == "#!":
code = "\n".join(lines[1:])
# construct a 2D defaultdict to contain the code
self._codebox = defaultdict(lambda: defaultdict(int))
line_n = char_n = 0
for char in code:
if char != "\n":
self._codebox[line_n][char_n] = 0 if char == " " else ord(char)
char_n += 1
else:
char_n = 0
line_n += 1
# 以下略 ...
これは_codebox
(コードブロック)の初期化の処理です.defaultdict
を入れ子にすることで2次元の配列を定義しているようですね.
defaultdict
は通常のdict
とは違い存在しないキーでアクセスしてもエラーにならず,初期値で初期化してくれるものです.
class Interpreter:
def _handle_instruction(self, instruction):
# 中略 ...
# get value in codebox
elif instruction == "g":
x, y = self._pop(), self._pop()
self._push(self._codebox[x][y])
# set (put) value in codebox
elif instruction == "p":
x, y, z = self._pop(), self._pop(), self._pop()
self._codebox[x][y] = z
# 以下略 ...
p
g
ともにスタックから値をポップして,_codebox
のインデックスにアクセスして処理を行うというシンプルな実装です.
検証の結果との矛盾も無いように思います.
fishr (Rust製のインタープリタ)
以下のコードはfishr/src/fish.rsの引用です.
https://github.com/noirotm/fishr/blob/master/src/fish.rs
pub struct CodeBox {
data: Vec<Vec<u8>>,
height: usize,
width: usize,
}
impl CodeBox {
// 中略 ...
fn get(&self, x: usize, y: usize) -> Option<u8> {
if x < self.width && y < self.height {
let line = self.data.get(y)?;
Some(line.get(x).map_or(b' ', |c| *c))
} else {
None
}
}
// 中略 ...
}
pub struct Interpreter<R: Read, W: Write> {
pub ip: InstructionPtr,
pub dir: Direction,
pub stack: StackOfStacks<Val>,
pub memory: HashMap<MemPos, Val>,
pub trace: bool,
pub tick: Option<Duration>,
input: Bytes<R>,
output: W,
rng: ThreadRng,
state: ParserState,
memory_is_dirty: bool,
}
CodeBox
とInterpreter
ですね.get
メソッドでは範囲外にアクセスした場合None
を返すようになっています.
Interpreter
の中で命令を実行するところが以下のコードです.
impl<R: Read, W: Write> Interpreter<R, W> {
// 中略 ...
fn execute_instruction(&mut self, instruction: u8, code: &CodeBox) -> Result<RuntimeStatus> {
match instruction {
// 中略 ...
// # Memory operations
// Push from memory
b'g' => self.read_memory(code)?,
// Pop to memory
b'p' => self.write_memory(code)?,
// 中略 ...
_ => return Err(RuntimeError::InvalidInstruction),
}
Ok(RuntimeStatus::Continue)
}
// 中略 ...
}
read_memory
とwrite_memory
がg
p
命令の実装のようです.これらを確認してみます.
impl<R: Read, W: Write> Interpreter<R, W> {
// 中略 ...
fn get_memory(&self, code: &CodeBox, x: i64, y: i64) -> Val {
// fetch from map only if memory is dirty
if self.memory_is_dirty {
if let Some(v) = self.memory.get(&MemPos { x, y }) {
return v.clone();
}
}
let b = code.get(x as usize, y as usize);
Val::Byte(match b {
Some(b' ') | None => 0,
Some(b) => b,
})
}
// 中略 ...
fn read_memory(&mut self, code: &CodeBox) -> Result<()> {
let y = self.pop()?.to_i64();
let x = self.pop()?.to_i64();
let val = self.get_memory(code, x, y);
self.stack.top_mut().push(val);
Ok(())
}
fn write_memory(&mut self, code: &CodeBox) -> Result<()> {
let y = self.pop()?.to_i64();
let x = self.pop()?.to_i64();
let v = self.pop()?;
let val = self.get_memory(code, x, y);
// abort if we don't actually change memory
if v != val {
self.memory.insert(MemPos { x, y }, v);
self.memory_is_dirty = true;
}
Ok(())
}
// 中略 ...
}
abort if we don't actually change memory
(実際にメモリを変更しなければ中止する)と書いてある通り,範囲外にアクセスした場合はメンバ変数のmemory
に値を追加したり読み取ったりしているようですね.そして,memory_is_dirty
というフラグをtrue
にしています.CodeBox
の拡張をする処理は無いようなので,これも検証の結果と合致しますね.
結びに
p
命令でコードブロックの外に命令を書き込んでそれを実行する,というのは少々特殊な実装をしない限りおきないと思うので,そこまで大きな影響はないと思います.
しかし,知識として知っておくとエラーの原因を特定しやすくなると思います.(><>
のエラーメッセージはたった1種類しかないため,エラーの解決はプログラマの知識が重要になります.)
なお,特殊な実装をした結果,詰まったのが以下の記事の7問目です.これがあったため,処理の違いに気が付きました.
オマケ esolang wikiを読んでみる
「><>
の仕様書が見つからないため,私にはどの実装が正しいのかわかりません」と書きましたが,一応esolang wikiには><>
の各命令の説明が書いてあります.
g
: Pop y and x off the stack, and push the value at x,y in the codebox. Empty cells are equal to 0.
p
: Pop y, x, and v off the stack, and change the value at x,y to v. E.g. 123p puts 1 at 2,3 in the codebox.
esolang wikiより引用
日本語訳は以下の通りです.
g
: yとxをスタックから取り出し、x,yの値をコードボックスにプッシュする。 空のセルは0に等しい。
p
: スタックからy,x,vを取り出し、x,yの値をvに変更する。例えば123pはコードボックスの2,3に1を置く。
うーん.これだけではよくわかりませんね.g
については空白(SPC)のことを空のセルと言っているのか,何も書かれていないマスのことを空のセルと言っているのかわかりませんし,p
についてはコードブロックの外に書き込んだ場合の処理が書いてありません.まさにsomething smells fishy...です.