2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

【><>】AtCoderの><>の実行環境とfish.pyのg命令/p命令の処理の違いについての検証

Last updated at Posted at 2024-10-30

はじめに

タイトル通りの話です.なお,この記事を書いている2024/10/30時点のお話ですので,記事をご覧になられている時には修正(?)されているかもしれません.
また,AtCoderや><>のことをご存じではない方は,><>でAtCoderをやる記事を書いたのでこれを参考にしてください.

AtCoderに提出したのは以下のようなコードです.なお,問題の原因になったところのみを抽出しておりますので,実際のコードとは違うことにご注意ください.
公式のインタープリタやオンラインインタープリタでは問題なく実行できたものの,AtCoderではエラーが発生してしまいました.

error.fish
"1"32p "1"f2p v
v             <
\
> $ ;

実行前

image.png

実行後

image.png

どうやらAtCoderの実行環境では,p命令でコードが配置されるコードブロックの外に書き込んだ命令を実行することができないようです.(つまり,$(15,2)$に追加された1を実行できないため,スタックに2つの数字がなく$を実行できない)

「これはAtCoderのバグだ!」ということを言いたいわけではありません.そもそも><>の仕様書すら見つからない(esolang wiki以外に情報がほとんどない)ため,私にはどの実装が正しいのかわかりません泣.
どちらかというと,C++におけるgccとClangの違いのようなものだと考える方がいいと思います.

とはいえAtCoderで><>を使う以上は,処理系によってどのような差があるかは知っておくべきだと感じたので,様々な環境でp命令とg命令の処理を検証してみました.

検証に使用するインタープリタ

なお,AtCoderの使用できる言語とライブラリの一覧を確認するとfishrを用いていると書いてありましたので,AtCoderのコードテストでもfishrが使われているものだと思います.

検証方法

以下のコードをそれぞれ実行し出力結果を確認します.出力ができなければどのようになったか(無限ループor実行時エラー)を確認します.

[1] コードブロック上にgとpをする場合
 00g n 100p " "o 00g n ;
[2] コードブロック上だが何も書かれていない領域で同じことをする場合
v
\32g n " "o 132p 32g n
;
[3] コードブロック外にgとpをする場合
ffg n " "o 1ffp ffg n;
[4] コードブロック内にpで命令を書き込み実行する
"v"70p > "N" o ;
       > "Y" o ;
[5] コードブロック外にpで命令を書き込み実行する
  "'Y'o;" 0fp 0ep 0dp 0cp 0bp v
> "N" o;                      v
v                             <

検証結果

[1] コードブロック上にgpをする場合

fish.py fishlanguage Mousetail fisr AtCoder
0 1 32 1 32 1 0 1 0 1

上段にインタープリタ,下段にプログラムの実行結果を表示しております.
想定される動作としては1回目のn0が出力され,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] コードブロック外にgpをする場合

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

fish.py 93行目
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とは違い存在しないキーでアクセスしてもエラーにならず,初期値で初期化してくれるものです.

fish.py 305行目
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

fish.rs 19行目
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
        }
    }
    // 中略 ...
}
fish.rs 128行目
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,
}

CodeBoxInterpreterですね.getメソッドでは範囲外にアクセスした場合Noneを返すようになっています.
Interpreterの中で命令を実行するところが以下のコードです.

fish.rs 416行目
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_memorywrite_memoryg p命令の実装のようです.これらを確認してみます.

fish.rs 631行目
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に等しい。
: スタックからy,x,vを取り出し、x,yの値をvに変更する。例えば123pはコードボックスの2,3に1を置く。

うーん.これだけではよくわかりませんね.gについては空白(SPC)のことを空のセルと言っているのか,何も書かれていないマスのことを空のセルと言っているのかわかりませんし,pについてはコードブロックの外に書き込んだ場合の処理が書いてありません.まさにsomething smells fishy...です.

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?