Brainfuck にコンパイルされる言語 Nazuki の 2020 年の進捗状況

遅れましたが、この記事は TSG Advent Calendar 2020 の 22 日目です。

21 日目は放課後ていぼう日誌はいいぞさんの『旅』です。23 日目は taiyoslime さんの『なんか書く』です。


4、5 年ほどちまちま作っているものがあるので、それの今までの状況をまとめようかと思います。

できていること

大まかな目標はタイトルの通り、「Brainfuckコンパイルされる言語」です。が、もう少し正確には「オレオレ仮想機械を作り、それをエミュレートする Brainfuck を生成する言語」です。

github.com

動機

まず Brainfuck を抽象化するにあたって、マクロを導入するという方法があると思います。が、マクロでは例えば以下のようなプログラムは作れません。

def fact(n):
  if n == 0:
    return 1
  else:
    return fact(n - 1) * n

そもそも普通のプログラミング言語における関数がコンパイル後にどう動作しているのかを考えると、関数を呼び出すときに今コードのどの部分を実行しているかをスタックに入れておき、そこから関数のある場所へ移動する、終わったらスタックに入れておいた場所に戻る、といった仕組みになっています。

ということは、関数のようなものを実現するには実行時に「今プログラムのどこを実行しているのか?」の情報を持っていないといけません。制御構造が [ ] しかない Brainfuck においてこれをやるのは不可能です。

ということで、ある種の仮想機械を Brainfuck 上でエミュレートすることでこれを実現しよう、というのが Nazuki の方針です。名前は「脳」を表す古語から取っています。

命令セット

仕組みとしては、まず 32 ビットスタックマシン上の「オレオレ命令セット」を用意します。これは今のところ

  • スタック操作
    定数プッシュ、複製、{上から、下から} n 番目を{取得、書き換え}、破棄
  • ビット操作
    反転、AND、OR、XOR、左シフト、論理右シフト、算術右シフト
  • 算術操作
    インクリメント、足し算、引き算、掛け算
  • 比較操作
    等しい、等しくない、{符号あり、符号なし}で{より小さい、以下、より大きい、以上}
  • 入出力
    整数入力、整数出力、文字列出力
  • 制御命令
    相対ジャンプ、ゼロだったら相対ジャンプ、ゼロじゃなかったら相対ジャンプ、等しかったら相対ジャンプ

があります。

アセンブラがまずすることは、実際のプログラムではこれが全部使われないのと、定数プッシュや相対ジャンプにおける即値部分がものによって異なるので、それを分類した命令セットを構築します。例えば

push 1
push 2
add
push 3
add
print

という命令列からは {push 1, push 2, push 3, add, print} という命令セットが得られます。各命例の具体的な命令コードは決まっておらず、命令セットがコンパイル時に決まるアーキテクチャを他に知らないのですが、これを個人的に「動的命令セット」と読んでいます。

ラベルが含まれる場合、制御命令を何命令分前/後ろにジャンプすればいいかの相対ジャンプに置き換えます。

メモリ配置

次にこれをエミュレートする仮想機械を Brainfuck で構成します。

まず Brainfuck 上のメモリを以下のようなメモリ配置に決めます。

|---------program---------||----stack----|
[0][0]...[0][0][1]...[1][1][1][1]...[1][1][0][0]...
             ^                             ^
            IP                            SP

Brainfuckインタプリタによってメモリが一方向に無限に伸びているのか双方向に無限に伸びているのか異なるのですが、ここでは一方向に伸びていると仮定します。

まずスタック領域では、1 つの仮想的な「メモリ」を、Brainfuck のセル 33 個に対応させます。このうち 32 個はそのメモリに入るデータに対応していて、(Brainfuck の 1 セルには大抵の場合 0255 の値が入りますが)01 しか入れないようにします。もうひとつのセルはメモリへのアクセスや、計算を非破壊的に行うための一時セルに使います(用途が複数あるので用語が定めづらいのですが、アクセサとでも呼ぶことにします)。

プログラム領域では、データセルが \lceil \log_2 (命令セットのサイズ) \rceil ビットになっています。

01 しか入れないようになっているのは、演算のしやすさもありますし、データを運ぶ回数を抑える役割もあります。例えばセル 4 つで 32 ビット整数を表そうとすると、-1 の表現は 255, 255, 255, 255 となるのでこれを運ぶのに 1020 回往復しなければなりません。2 進数なら最大 32 回の往復で済みます。データ幅が 33/5 倍になっているのがトレードオフではありますが、Brainfuck インタプリタに最適化機能がついていれば 33 セルの移動は一気にできます。

そしてこの仮想機械は上図のようにインストラクションポインタ (IP) とスタックポインタ (SP) を持っていて、IP から SP までの部分のアクセサを 1 に、その外側を 0 にします。こうすることで IP と SP の行き来が可能です。

仮想機械

さて生成された Brainfuck 仮想機械は以下のような挙動をします。

  • 命令列をプログラム領域に配置する。
  • 以下をループする。
    • IP に移動する。
    • ビットが 10 かを非破壊的に見て分岐するものを再帰的に重ねることで、命令ごとに分岐する。
      • たいていの命令では、まず SP に移動する。
      • 演算命令ならスタック上で演算を行う。
      • 制御命令なら指定された分だけ IP を移動させる。
      • 終了命令ならループを抜ける。
      • IP に戻ってくる。
    • IP を 1 つすすめる。

ここまでの一連の動作によって、Brainfuck でより高水準な操作を行うことができます。

ブラウザで動かす

最近これをブラウザで動かせるようになりました。まだ人に使ってもらうほど完成してはいないので、使い方の説明はないです……。

n4o847.github.io

f:id:n4o847:20201224155830p:plain

できていないこと

文字列、配列の扱い

決まった文字列を出力するだけであればそれをひとつの命令にしてしまえばいいですが、文字列や配列を操作するとなると難しいです。

そもそも長さがコンパイル時にわからない列を扱うのが厳しいです。多分普通の言語のメモリ割り当ては

  • プログラム領域
  • 静的領域
  • ヒープ領域
  • スタック領域

になっていると思います。ということで、文字列や配列を扱うとしたら以下の手段があるかなと思います。

  • 静的領域を作る
    コンパイル時に予め長さを確保する方法です。IP と SP の間の往復は頻繁に起こるので、入れるとしたらプログラム領域より左側でしょうか。
  • ヒープ領域を作る
    メモリが双方向無限になっていればよいのですが、処理系によっては一方向無限です。そこで Brainfuck において、セルを交互に割り振ることでメモリを二重に見せることができるというテクニックが存在するので、それを使ってスタックをもうひとつ作ります。全体的な処理効率は落ちます。

アセンブリ言語より上のレイヤー

もとはこっちも作っていましたが、今はちょっと後回しです……。

概念、用語、フォルダ構造の整理

概念の名前がわかることで既存の手法が調べやすくなり、モジュール名や関数名もいい感じになるのですが、難しい。

特にコンパイラ基盤、言語処理系周りの概念についてもうちょい色々知りたいなと思います。

ドキュメントの整備

ぐえ。。。

経緯(自分語り)

Brainfuck の抽象化を構想し始めたのは多分 2016 年ごろです。当初は JavaScript で実装されており、VM の機構がありませんでした。この頃は高校の部活の時間で主に開発していましたが、規定のため部のパソコンには Git が入っておらず、そもそも Git をあまり良くわかっていなかったので、paiza.io で動かして保存していたらしいです。

途中で VM が必要なことに気づき、コンパイラとかの仕組みを調べたりしました。この頃進捗を Qiita にまとめようとしていたっぽいですが、途中で終わっている……。

qiita.com

qiita.com

2018 年になり、受験も終わり、CombNaf という学生 LT イベントでその時点での進捗を発表しました。今見返すとめちゃくちゃ恥ずかしいので見ないでください。

nafmo.hatenablog.jp

nafmo.hatenablog.jp

2018 ~ 2019 年頃、実装言語を Ruby に置き換えました。

github.com

これは Ruby で以下のような記述ができて楽なためです。

https://github.com/n4o847/nazuki-rb/blob/1787bbe7ed5a7f1cd13c2e340d2b2126af13d7b4/src/generator.rb#L364-L377

    def sp_and
      32.times do
        _left
        _dec
        _loop do
          _inc
          _left(33)
          _set(0)
          _right(33)
        end
      end
      _left
      _dec
    end

めちゃくちゃ楽だったのですが、動的型付けのためインターフェイスを移行するときなどにつらくなり、あとブラウザ上で生成できるようにしたいという願望から、2019 年春頃に実装言語を Rust に置き換えました。

github.com

コンパイル時に型がわかり、WebAssembly に変換することでブラウザから実行できるのは良かったのですが、記述が以下のように冗長になってしまいました。

https://github.com/n4o847/nazuki-rs/blob/0fd9e6c1155d35bf91250e2f73f38548d9d8efbc/src/generator.rs#L371-L391

    fn i32_and(&mut self) {
        mem! {
            start_point: 66,
            _a_head: 0,
            a_body: 1..=32,
            b_head: 33,
            b_body: 34..=65,
            end_point: 33,
        }

        self.exit(start_point);
        for i in (0..32).rev() {
            self.sub(b_body[i], 1);
            self.while_(b_body[i], |s| {
                s.add(b_body[i], 1);
                s.set(a_body[i], 0);
            });
        }
        self.sub(b_head, 1);
        self.enter(end_point);
    }

self. を毎回書くのがつらいですね。マクロでドメイン固有言語 (DSL) を作っても良かったのですが、レイヤーが複数ある Nazuki において新たに DSL を増やすことはややこしさを増やすことに繋がります。

ということで 2019 年秋頃、実装言語を Haskell にしてみました。

github.com

Haskell だとモナドと do 記法を使って以下のような記述ができます。

https://github.com/n4o847/nazuki-hs/blob/9f67d89d7c36d9775c2379be7bc10e9506cf6545/src/Nazuki/Generator/IntOf2To32.hs#L208-L220

doAnd :: Oper
doAnd = do
  let a_ = mems [1 .. 32]
  let b = mem 33
  let b_ = mems [34 .. 65]
  consume 2
  forM_ [31, 30 .. 0] \i -> do
    sub (b_ i) 1
    while (b_ i) do
      add (b_ i) 1
      set (a_ i) 0
  sub b 1
  produce 1

これはもうめちゃくちゃ最高なので、今はこれで良いかなと思っています。

そして 2020 年秋頃に Asterius という Haskell → WebAssembly コンパイラを見つけて、今はブラウザで動かす部分も作ろうとしています。

github.com

ブラウザで動かせる点と Haskell より細かいところが整っている点で PureScript という選択肢もあるのですが、そこは悩み中です。

先行研究とか

先行研究がすごいとちょっとメンタルがやられますよね。

  • shinh/elvm
    色々な esolang をバックエンドとして扱っているコンパイラ基盤です。正直 Nazuki でやりたかったことはここで既に実現されているのですが、生成される Brainfuck がサイズや実行時間的にあまり実用的でないので、そこでの差が出せるかなとは……思っています……。

  • hsjoihs/camphorscript
    Brainfuck を生成するより高水準な言語、という意味で近いですが、Nazuki が一段エミュレーションを噛ませているのに対しこちらの理念としてゼロコスト抽象化があるようなので、方向性が違うかな……と思います。

AtCoder への適用

当初、このプロジェクトを AtCoder に適用する気はありませんでした。AtCoderBrainfuck での提出は度々していましたが、最初は別のプログラムで生成していたか手書きだったかだと思います。

ここ最近は AtCoder への適用を考えています。AtCoder Brainfuck 界隈 (?) にも強い人がどんどん現れて、コツコツやらないとどんどん順位が下がっていくのがつらいですね……。

AtCoder に適用していく上でわかってきたのは、

  • A 問題くらいの難易度であれば実行時間にまったく問題はない。内部実装が 2 進数になっているおかげで結構高速っぽい。
  • ループが必要になってくるとちょっと厳しくなってくる。
  • AtCoder の提出コード長は 512 KiB までに制限されているが、例えば掛け算を使ってしまうと 77400 B あるのでちょっと厳しいかも。
  • 文字列操作系の問題に弱い。

あたりです。将来的にはその辺りの強化もしていきたいと思っています。

正則文法は人工言語の夢を見るか?

この記事は 語学・言語学・言語創作 Advent Calendar 2020 の 10 日目です。


人工言語にしろ何にしろ、言語の文法について考えようと思ったとき、チョムスキー階層というのを目にしたことがあるのではないでしょうか。

f:id:n4o847:20201209180221p:plain
よくある図

この中でも正則文法というのは、最も制限の強い文法になっています。

この正則文法によって人工言語的な営みをすることがどの程度可能か? というのが本記事のテーマです。

定義とかの話なので面倒なら飛ばしてください

言語と文法

まず、ここでの言語と文法の定義を書いておきます。

最初に記号というものを定めます。a, b, c, , ., ...みたいな感じです。

言語とは、記号列の集合のことです。上で決めた記号を適当に並べたとき、mi pilin pona, hellooooooo, askldjfahqrweklahfukseh など無限の組み合わせが存在しますが、この中で有効なもののみを集めたものが言語です。もちろん言語自体も無限の大きさの集合になり得ます。

文法とは、ふたつの捉え方がありますが、ひとつはその言語に沿うような記号列を生成するルールのことです。これには後述の正則文法などが該当します。もうひとつは、ある記号列がその言語に含まれるか判定するルールのことです。これには後述の非決定性有限オートマトンなどが該当します。どちらにせよ、その言語を定めるためのルールのことを文法といいます。

正則文法の定義

正則文法は制限が強く、ルールが全て以下のような形になっています。

  • A -> a B
  • A -> a
  • A -> ε

小文字はその言語で使う記号のどれかです。大文字はそれを置き換えることができるある種の変数のようなものです。ε は空文字のことです。

最初に決まった大文字から始めて、ルールによってどんどん置き換えていくことで記号列を生成していきます。

ちなみに、A -> a B でなく A -> B a を使うものもあり、前者は右線形文法、後者は左線形文法と呼ばれます。

正則言語の等価な定義

正則言語とは、以下を満たす言語のことであり、いずれも等価です。

正則文法と人工言語

さて、文法が簡単な人工言語のひとつとして、トキポナという言語がありますね。

正則文法がどの程度人工言語に対して運用可能か考える上で、トキポナが正則言語であるかどうかを調べれば、トキポナは運用可能な人工言語である(個人の感想)のでお題を満たすということになります。

が、実際にトキポナには公式な形式文法は定められていません(多分)。そもそも、トキポナは話者によって多少ルールが異なる場合があり、あるトキポナ文が非文かどうかは話者によっても異なると思います。

そうするとトキポナが正則言語であることを形式的に証明することは難しいのですが、今回の目的は人工言語一般に対する話なので、「トキポナの文法をよく近似している形式文法」を考えることで、本当のトキポナとの細かい差異を気にせず、人工言語としての運用を考えることができます。

ほぼトキポナ形式文法を用意する

トキポナっぽい形式文法は多分色々考えられているでしょうが、とりあえずググって出てきたこの PDF を使います。

https://www2.hawaii.edu/~chin/661F12/Projects/ztomaszewski.pdf

Appendix の部分にこのようなルールが載っています。

トキポナを正規表現に変換する

これが正則言語かどうかを形式的に証明するには、上で述べた等価な形のどれかに変換する必要があります。

これを正則文法のルールに変換するのはしんどいので、正規表現に変換することを考えてみます。

固有名詞

トキポナの音韻規則として、

  • 音節 ji wu wo ti は存在しない
  • n で終わる音節の次に m n で始まる音節は続かない

というものがあります。これを考慮したトキポナの単語を表す正規表現としては以前

のようなものを考えたのですが、先読みを使ってしまうと正規表現にならない(?????? これは大抵のプログラミング言語で使われている正規表現が実際には正規表現でないことによります)のでこれを先読みを使わないものに変換します。

存在しない音節については逆に存在する音節を列挙すればいいです。n に関しては、逆に n の前に関して制限がないので、後ろとセットにして列挙すればいいです。

  • 語頭: A|E|I|O|U|Ja|Je|Jo|Ju|Ka|Ke|Ki|Ko|Ku|La|Le|Li|Lo|Lu|Ma|Me|Mi|Mo|Mu|Na|Ne|Ni|No|Nu|Pa|Pe|Pi|Po|Pu|Sa|Se|Si|So|Su|Ta|Te|Ti|To|Tu|Wa|We|Wi
  • n なし後続音節: ja|je|jo|ju|ka|ke|ki|ko|ku|la|le|li|lo|lu|ma|me|mi|mo|mu|na|ne|ni|no|nu|pa|pe|pi|po|pu|sa|se|si|so|su|ta|te|ti|to|tu|wa|we|wi
  • n あり後続音節: nja|nje|njo|nju|nka|nke|nki|nko|nku|nla|nle|nli|nlo|nlu|npa|npe|npi|npo|npu|nsa|nse|nsi|nso|nsu|nta|nte|nti|nto|ntu|nwa|nwe|nwi

まとめると

(?:A|E|I|O|U|Ja|Je|Jo|Ju|Ka|Ke|Ki|Ko|Ku|La|Le|Li|Lo|Lu|Ma|Me|Mi|Mo|Mu|Na|Ne|Ni|No|Nu|Pa|Pe|Pi|Po|Pu|Sa|Se|Si|So|Su|Ta|Te|Ti|To|Tu|Wa|We|Wi)(?:ja|je|jo|ju|ka|ke|ki|ko|ku|la|le|li|lo|lu|ma|me|mi|mo|mu|na|ne|ni|no|nu|pa|pe|pi|po|pu|sa|se|si|so|su|ta|te|ti|to|tu|wa|we|wi|nja|nje|njo|nju|nka|nke|nki|nko|nku|nla|nle|nli|nlo|nlu|npa|npe|npi|npo|npu|nsa|nse|nsi|nso|nsu|nta|nte|nti|nto|ntu|nwa|nwe|nwi)*n?

という形になります。

ここで、この正規表現はトキポナの音韻構造を無視した分析をすることになりますが、結果的に同じ言語を受け入れるのであれば問題ありません。

自己再帰、相互再帰

非終端記号(ルールの左辺に出てくる変数)の依存関係はこのようになっています。

f:id:n4o847:20201209234946p:plain
非終端記号の依存関係

自己再帰している

CompoundSubj -> NP en CompoundSubj
Modifier -> Mod | Mod Modifier
Pred -> VP | VP li Pred
VP -> IntransVP | TransVP | VP PrepPh
DO -> e NP | e NP DO
PrepPh -> Prep NP | Prep NP PrepPh

などは

CompoundSubj -> NP(?: en NP)+
Modifier -> Mod(?: Mod)
Pred -> VP(?: li VP)*
DO -> e NP(?: e NP)*
PrepPh -> Prep NP(?: Prep NP)*

に置き換えます。

また、例えば

VP -> IntransVP | TransVP | VP PrepPh
PrepPh -> Prep NP | Prep NP PrepPh

はこのままだと

VP -> (?:IntransVP|TransVP)(?: Prep NP(?: Prep NP)*)*

のようになって効率が悪いので一気に

VP -> (?:IntransVP|TransVP)(?: Prep NP)*

にします。

NP の周辺がやっかいですが、問題なのはこの文法で

NP anu NP pi (?:N Modifier|Name)

のようなときに anupi の結合の強さに曖昧性がある点です。上で述べたように、構造を無視しても結果的に同じ言語を受け入れれば良いので、どちらかにまとめても良いです。ということで

NP -> NP'(?: anu NP')*
NP' -> ~ (?: pi (?:N Modifier|Name))*

とします。

「~ ala ~」構文

「~ ala ~」構文は結構怪しくて、「~」の部分に任意の名詞句を許してしまうと正則言語でなくなってしまいます。

これは sina jan Palotijekojoselansikotepalajannepomusenosipijanotelasantisimalinitaluwipikaso ala jan Palotijekojoselansikotepalajannepomusenosipijanotelasantisimalinitaluwipikaso? みたいなクソなが名詞句があったときに、有限状態オートマトンで対応できないことや、反復補題でどこを反復しても非文になる(多分)ことから証明できます。

対策としては、これを sina jan ala jan Palotijekojoselansikotepalajannepomusenosipijanotelasantisimalinitaluwipikaso のようなもののみ許すというものです。

そもそも後者のほうが自然だとは思いますが、前者が非文かというと微妙じゃないですか……?

とりあえず今回のルールでは「~」部分を有限にするとして、上に載せたルールだと「ala」の左と右が一致することがルールになっていないので、それも補います。

YnV -> V ala V

YnV -> (?:anpa ala anpa|ante ala ante|awen ala awen|ijo ala ijo|ike ala ike|jaki ala jaki|jan ala jan|jo ala jo|kalama ala kalama|kama ala kama|ken ala ken|kepeken ala kepeken|kule ala kule|lape ala lape|lawa ala lawa|lete ala lete|lili ala lili|lon ala lon|lukin ala lukin|moku ala moku|moli ala moli|musi ala musi|mute ala mute|nasa ala nasa|olin ala olin|open ala open|pakala ala pakala|pali ala pali|pana ala pana|pilin ala pilin|pimeja ala pimeja|pini ala pini|poka ala poka|pona ala pona|seli ala seli|sin ala sin|sitelen ala sitelen|sona ala sona|suli ala suli|suwi ala suwi|tawa ala tawa|telo ala telo|toki ala toki|tomo ala tomo|tu ala tu|unpa ala unpa|utala ala utala|wan ala wan|wawa ala wawa|weka ala weka|wile ala wile)

のようにします。

結果

あとは手でごちゃごちゃやりながら置換していくと、最終的な S

(544247 文字!!!)となります。

正直、ちゃんと動く保証はないです。

有限オートマトン

ここから非決定性有限オートマトンを作りたかったのですが、正規表現が予想以上に大きくなってしまったのでやめました。

敗因

トキポナを表す正規表現がこんなに大きくなってしまった原因は、

  • そもそも最初の文法が正規表現に適した形になっておらず、最適化が難しい
  • 「主語が misina のときだけ li がつかない」のような、絶妙に扱いづらいルールがある。「~ではないとき」のようなことを先読みなしでやろうとすると記述量が増えてしまうため
  • 音韻規則や全単語も含めているので大きいのは当たり前

などが考えられます。

結論

結論として、ほぼトキポナな文法が正規表現で表せたので、正則言語でも人工言語としての運用がある程度可能、ということになりました。

考えられる今後の活動として、

  • トキポナのもっと簡単な正則文法を作る
  • トキポナのもっと簡単な正規表現を作る
    • 実際のトキポナ文にマッチするかコーパスを使って確かめてみる
  • トキポナを有限オートマトンにしてみる

もしくは

といったものが考えられます。

追記

nymwa さんが別アプローチを取っていました。

オートマトンを直接構築しているらしいです。既存の文法を正則になるように変換するよりかは、ボトムアップに作っていく方がシンプルになりそうですね。

TSG LIVE! 5 ライブコードゴルフ大会 Day2 writeup

TSG LIVE! 5 ライブコードゴルフ大会 (Day1) writeup の続きです。

Day2 のライブコードゴルフ大会は、外部チームとしてこたつがめさんと %20 さんが招かれ、TSG チームと対戦しました。

Day1

n4o847.hatenablog.com

Day2

YouTube Live のアーカイブはこちらです。

youtu.be

さらに、今回ゲストとして参加してくれたお二方が参加記を書いてくれています。

kotatsugame.hatenablog.com

i-i.hatenablog.jp

問題概要

それ以前のどの数値よりも真に小さいか判定せよ

Szkiくんは甘いものに目がなく、毎日おやつを食べていました。
しかし最近Szkiくんは太ってしまったので、ダイエットのためおやつに制限を設けることにしました。
制限は、「その日のおやつのカロリーが以前のおやつたちのカロリーのいずれよりも真に小さいとき、おやつを食べる」というものです。
今日から50日ぶんのおやつのカロリーが2桁の数値で与えられるので、Szkiくんがおやつを食べた日は1、食べなかった日は0を出力してください。

入力

  • 2桁の数値(01以上99以下)が50個、改行区切りで与えられる。
  • 入力の最後には改行が付与される。

出力

  • 与えられた数値それぞれについて、それ以前に与えられた数値のいずれよりも真に小さいとき1、そうでないとき0を出力せよ。

制約

  • 同じ数値は2度出現しない。
  • 入力の数値は10以上99以下である。
  • 初日については1を出力すること。

入力例

入力例

88
18
21
41
55
46
64
58
67
86
89
28
72
12
77
83
93
61
23
15
53
34
35
81
96
10
76
82
19
51
49
47
59
84
24
87
71
33
20
94
45
56
90
39
85
50
40
26
69
68

出力例

11000000000001000000000001000000000000000000000000

行動の振り返り

ぐわ~~~~~~~~

博多市さんと事前の打ち合わせで、東京周辺は赤がいて Ruby (埼玉)、Python (山梨)、C (長野) など相手が強そうな言語があるので、兵庫周辺から攻めようということになり、Crystal (京都) と Node.js (大阪) は普段書いている博多市にまかせて自分は Aheui (和歌山)、Starry (奈良)、GolfScript (滋賀) の esolang を担当することにしました。……が、

書けない!!!!! たすけて

かなりの時間を Starry に溶かしてしまったのは本当に反省すべきムーブだと思っています。切り替えて Aheui や GolfScript をやってみるも手がつかず……

今考えると書き慣れている Brainfuck (三重) は Crystal に接しているので手をつければよかったのかも知れませんが、当日は全く気づきませんでした。

RubyPython は博多市との話し合いによって縮んでいったので、その点は良かったかなと思っています。

相手が強豪なので汎用言語を避けて esolang に向かっていましたが、結果かなり厳しい展開となってしまいました。

コード

C、Go、PythonRubyPerl、Crystal、GolfScript、><>、WhiteSpace についてはこたつがめさんと %20 さんが解説してくれています。

え、自分が解説するものなくない……?

とはいえ、なんとか書ききれた Starry、まだ縮みそうな ><> (新潟)、今回惜しくも手がつけられなかった Brainfuck について語っていこうかなと思います。

Starry (4359 bytes)

まずライブコードゴルフ大会での基本的な戦略として、esolang では縮めるよりも動くことが大事なので、ループ処理を書かずに回数分の処理を繰り返して書きます。

ということで同じ処理を 49 回繰り返しますが、問題はこの言語に大小判定がないというところです。

しばらくして割り算による大小比較に至りましたが、小さい方の数値を残すのもしんどく、唯一の分岐命令である「非ゼロならジャンプ」を使おうとするも、49 回処理を書いているせいでラベル(空白を並べる数で決まる)が長すぎてコード長制限に引っかかりました。

分岐なしで処理できる方法をずっと考えていて、最終的に出した方針としては

print(1)
a=input()
49 times:
  b=input()
  t=(b+100)/(a+100)
  print(t)
  a=b*t+a*(1-t)

みたいなことをやっています。もっと早く思いつきたかった。

というか、せめてジェネレータを事前に作っておくべきでした。本当にアホ

><> (45 bytes → 22 bytes)

アーカイブを見て知りましたが、こたつがめさんが終了間際で ><> コードを Whitespace に出して焦っていたらしいですね。

TSG チームからは届く余地もなかったですが、><> は好きな言語で、あまりゴルフされていないそうなのでゴルフしてみたのがこちらです。

ff*v
?!~>:iii,+:@,1):n

Brainfuck

都道府県の感覚がなさすぎて、Crystal と隣接していることに気づきませんでした。YouTube のコメント欄で(多分 angel さん?)ゴルフしてくれていたので、ここでも考えてみようかなと思います。

とりあえず AC を目指したのが

->>,+[
  <,
  >[-<++++++++++>]
  <<[->-[[->>+<<]>>>-<<<]
  >>[-<<+>>]>+[-<+<<<[-]>>>>]<<+<<]
  >>[-<<+>>]
  +[+++++>+<]
  >---.[-]
<,,+]

で、空白抜きで 114 bytes になりました。

angel さんは 76 bytes なので結構遠い……

まとめ

サークル外からゲストを募ってライブに出てもらうという初の試みでした。結果は悔しく終わってしまったものの、とても興奮する戦いでした。対戦してくれたこたつがめさんと %20 さんに感謝です。

ライブ内で AtCoder 1 位 2 位という文句で紹介していますが、実はこれは偶然そうなったものです。誰を呼ぶかで悩んで結局自分と関わりのあった人たちに声をかけることとなり、それに応じてくれた方たちにも感謝したいと思います。この方法自体には後悔もあり、枠が決まっている以上結局積極性で選んでしまうのと、そもそも声をかけていない人に認知されないというのと……。でも最終的にゲストになったお二方とも今までのライブゴルフを熱心に観てくれていた方々であり参加したがっていたそうなので、今回の決断は間違っていなかったと思います。

個人の希望でしかありませんが、サークル外の人でも楽しめる機会がまたあればいいと思っています。ありがとうございました。

TSG LIVE! 5 ライブコードゴルフ大会 Day1 writeup

2020年五月祭で TSG が催したプログラミング生放送企画『TSG LIVE! 4』内のコーナー『ライブコードゴルフ大会』に参加した感想です。

新型コロナウイルスの影響により 9 月に延期(五月祭なのに)、さらにオンラインでの開催となりましたが、TSG LIVE! では今までと変わらないクオリティで企画を提供できたのではないかと思います。

今回自分は Day1 で作問および実況解説、Day2 でプレイヤーを担当したので、両方について触れていきます。

Day1

YouTube Live のアーカイブはこちらです。

youtu.be

スライドの作成者は自分なので、ここで出してしまいます。

問題概要

大文字か小文字かを判定せよ。

入力

  • ラテン文字 A から Z の 26 文字が順番に、一行で与えられる。
    • 各文字は大文字あるいは小文字である。
  • 入力の最後には改行が付与される。

出力

  • 与えられた文字それぞれについて、大文字であれば 1 を、小文字であれば 0 を出力せよ。
  • 出力された文字列に含まれる空白文字(改行含む)は無視される。

制約

  • 入力には必ず大文字がひとつ以上、小文字がひとつ以上含まれる。

入力例

ABCdefghiJKLmnopqRSTUvwxYz

出力例

11100000011100000111100010

コード

各言語の作問者解はスライドの方に載せました。補足したい部分について補足していきます。

C (44 bytes)

main(c){for(;c=getchar()>>5;)putchar(51-c);}

ナンさんの提出を見て思いましたが、最後が 51^c のほうが美しいですね。コードゴルフは芸術でもあるので美的感覚を養っていきたい所存です。

Python (33 bytes → 32 bytes)

for c in input():print(0+(c<"a"))

しーあるさんの Twitter の 2 日目に対する言及で気づきましたが、こちらも 0+(c<"a")+(c<"a") にできるので縮みますね。

Ruby (21 bytes → 20 bytes)

スライドでは

$<.bytes{p 80./_1-10}

と載せていますが、YouTube Live のコメントでこたつがめさんが

$<.bytes{p 2./_1>>5}

という解を載せてくれており、見事に取られてしまいました。ちなみにこたつがめさんは

頭がAtCoderだった

というコメントを残していますが、これは AtCoder と今回の esolang-battler のシステムの違いによるもので、AtCoder では正常終了しなければいけないのに対し esolang-battler では異常終了が許されています。というわけで過去の大会でもゼロ除算でループを抜けるなどの手法が典型になっているんですね~。

PPAP (131 bytes → 120 bytes)

I have 句を最初に書かなければいけないと思いこんでいたら、iLiss さんがライブ中に I have 句を途中に書いたコードを出していて、作問者解より短くなってしまいました。すごい。

これ以上のゴルフは面倒なのでやりません……。

FerNANDo (59 bytes → 45 bytes)

作問者解とプレイヤー解が一致し、もう縮まないだろうと思っていたのですが、YouTube Live で %20 さんが

最初に入力読まなくてもいいので縮むはず(改行を余計に出力すればいいので)

ferNANDo最初に空白を余計に出力すれば45B。7 7;7;0 0 7 9 0 0 0 6;9 8 7 6 5 4 3 2 1;6 6;7

といったコメントを残していました。実はライブ中に自力ではコメントを拾いきれておらず、口頭で伝えられてもどういう意味か瞬時に理解できなかったのが心残りですが、今考えるとたしかにそうでした。すごい。

Brainfuck (63 bytes)

,[+++++++++[[>]+<[-<]>]>>>>>>[->-<]+[+++++>+<]>---.,----------]

という解を載せており、ライブ中に説明するのは無理だと思ったのでここで解説します。

まず ,----------[++++++++++ ~ ,----------] は改行がくるまで読み込む典型的な方法です。

次の [[>]+<[-<]>] は 2 進数展開です。2 進数のインクリメントは末尾の 01...110...0 に置換することで再現できるということを考えると、そのセルの数分だけインクリメントを繰り返しているということがわかります。

+ が 1 つ足りませんがこれは A および a が 0b01?00001 で、1 足りなくてもビット判定に影響が無いからです。

次に 6 ビット目を見て、あったら 7 ビット目を消しています。7 ビット目は 1 が確定しているので反転に使えます。

+[+++++>+<] は wrap-around な処理系において 255 / 5 == 51 を用意するのに便利な典型的な方法です。

あとは、場所をもとに戻す必要がないので右に移動しながらループを繰り返すことになります。

Day2

n4o847.hatenablog.com

Cookpad Online Summer Internship 2020 に参加しました

クックパッドのサマーインターンシップに参加しました。

参加したコースは Web アプリ開発コース で、9/7~11 の5日間ありました。1~2日目は技術講義とサービス開発講義を受け、3~5日目は各自でお題に沿ったアプリケーションの開発に取り組みました。

意気込み

大抵のインターンシップはそうだと思いますが、今年は新型コロナウイルスの影響によりオンラインでの開催でした。

夏に入った頃、サークル Slack の雑談チャンネルにいる同学年の人々の間でインターンシップの話題が多く上がっていたことがきっかけで、いくつかインターンシップに申し込んでみました。というわけで、人生はじめてのインターンシップ参加となりました。

今までプログラミングは趣味の範疇で行ってきたので、こういった業務での開発に触れる経験も必要だろうというのがちゃんとした動機です。将来のことはわかりませんが、将来的にそういった職につく可能性は高いと思いますし。

あとは、面接も含めてすべてオンラインだったことで参加する精神的な障壁が下がっていたというのもありますし、Slack にしろ Twitter にしろ周辺にいる人は割と社会的なあれこれから身を置くイメージがあったのが、急にそういった話をしだしてびっくりしたというのもあります。

技術講義・サービス開発講義

講義で実際に使われたスライドはこちらで公開されています。

techlife.cookpad.com

特徴的だったのは、単に技術的な話だけではなく、ユーザーの課題を解決するためのサービス開発手法についても学んだというところだと思います。これによって技術的な部分も強い目的を持って学べたと思います。

技術講義(1日目、2日目午前)のハンズオンは AWS に用意された環境を使って小規模なレシピサービスを作るというもので、Ruby on Rails やデータベース設計の経験不足もありましたがかなり難しく、時間内に終わりませんでした。逆にこれで自分の限界がわかったので、のちの PBL での戦略を決めるのに役立ったと思います。

サービス開発講義(2日目午後)のハンズオンはユーザーの課題を解決するアプリケーションの考案とそのプロトタイピングです。これも単なるコーディングとは別の力を要求され暗中模索といった感じで、なかなか難しかったです。

PBL

アプリケーション開発は PBL (Project-Based Learning) という、実際に考えられるユーザーの課題を考え、それを解決するサービスとしての開発を行いました。価値仮設(どのようなユーザーがいたら何が価値になるかの予想)とユーザーストーリー(どのような場面でそのサービスが必要になるかの具体的な物語)を建てるのも難しく、上述のハンズオンで自分が組めるアプリケーションの限界もなんとなくわかり、かなり苦闘しながらの開発となりました。

Ruby on Rails での開発ならメンターさんのヘルプを十分に受けられるということで、またせっかくなので Ruby on Rails に慣れたいというのもあり、バックエンドでは Ruby on Rails を使いましたが、時間的な制約から極力慣れている技術を使いたいということでバックエンドとフロントエンドを分離し、バックエンドの Ruby on RailsAPI モードにして、フロントエンドは TypeScript + React を使って REST API でやりとりする方式にしました。結局 CRUD の Read しか実装できなかったので、バックエンドはデータベースを引っ張って返すだけの処理になってしまいましたが……。フロントエンドでガワの実装はできたので、今回の要求であった Minimum Viable Product としては十分だったのではないかと思います。

実際メンターさんがかなり懇切丁寧に付き添ってくれて、悩んでいる部分を聞いたら魚もくれつつ魚の釣り方も教えてくれるし、アイデア的な部分も弱いところにビシバシ指摘をくれて納得できたのでとても助かりました。

ちなみに PBL のお題は「一人暮らしをしている人の料理が楽しみになるアプリケーション」で、実際に自分が作ったのは「ハッシュタグを通じて同じ趣味を持つ人の普段の料理を探せるアプリケーション」です。

最終日に各自作ったアプリケーションの発表があり、15人いて一人4分という短い時間で、発表も大変でした。一人ひとりに審査員が講評をくれたので、フィードバックが得られたのが良かったです。他の人が何を考えて何を作ったのか見られたのも良い刺激になったと思います。

感想

サービス開発という枠組みで具体的な手法まで学べたのはかなり経験になりました。技術面でも、今まであまり触れてこなかったバックエンド部分に触れて楽しかったので、今後のモチベになると思います。

会社の雰囲気としてもいい感じで、将来どういう環境で働きたいか考える参考にもなったと思います。

や、将来とか何も考えていませんが……どうなるんでしょうね。

裏話

メモ: 使った技術、用語など

  • やりとり・連絡
  • アプリ
  • インフラ
    • AWS
      • CodeCommit, CodeBuild, CodePipeline
      • ECS
    • Docker は今回は未使用
  • サービス開発

おまけ: もらったものの写真

f:id:n4o847:20200918212606j:plain

f:id:n4o847:20200918212755j:plain

f:id:n4o847:20200918212815j:plain

f:id:n4o847:20200918212844j:plain

星屑テレパス 1巻 宇宙語解読

不明瞭な文字は「?」、隠れている部分は「#」、誤字脱字衍字と思われる箇所は太字です。

そで(著者あいさつ)

PEGGJOV=MOVLOV
PIVOU BOVVU=VUV,
ĈIUJ EN LA UNIVERSO !!

宇宙の皆さん こんにちは!!

(翻訳)ペッギョヴ=モヴロヴ ピヴーバヴヴ=ヴヴ、宇宙の皆さん!!

作中でも使われているあいさつですね。

p. 5 学生証

VERDIRE, MI ESTAS E####

(翻訳)実を言うと、私は……

なんですかねこれ???? そもそもなんで学生証に宇宙語が書いてあるんでしょう?

estas 以降がコマの外で読めないんですが、ユウの出自の根幹に関わってそうな雰囲気があって気になりますね……

第1話

p. 11 あいさつ

ペッギョヴ=モヴロヴ ピヴーバヴヴ=ヴヴ

スペルが単行本挿絵で明らかになりました。

第3話

p. 32 手帳表紙

雑誌

SPACE VOYAGE DIARY

単行本

SPACA VOJAĜA TAGLIBRO

(翻訳)宇宙航海日誌

ここ実は雑誌掲載時には英語(Y の部分は J と同じ文字だが英語に合わせた)になっていたのですが、単行本収録時に修正されたようです。

p. 33 手帳中身

雑誌

上ページ

ĈI TIU KOSMOŜIPO NE PLU POVAS
ESTI U?A?A IUJ EL LA FUNKCIOJ
JAM ESTIS FARITAJ KAJ NE POVAS
ESTI RIPARITAJ.
POST TIO NUR ATENDU LA TEMPON
DE LA KRASO.
LA ANTAŬDIRITA ALIRO ESTAS
LA TERO.
MI ESTAS ĈI TIU STEL###

(翻訳) この宇宙船はもう????できない。いくつかの機能がすでに済んでおり修理することができない。あとは衝突の時を待つのみ。予測された進入(地点)は地球である。私はこの星###

下ページ

#########NDA LOKO.
MI PA?AS ĈION, KION MI ##### PARI.
KURU KIEL EBLE PLEJ POR#####U.
KURU KAJ PARAS MU??AJN #####
ATENDANTE, MIA MONDO.
KOSMARKOJ NE PLU BEZONA#####

(うまく翻訳できず……)

単行本

上ページ

ĈI TIU KOSMOVETURILO
NE PLU UTILAS.
IUJ EL LA FUNKCIOJ
JAM FINIS SION ROLON.
MI NE PAVAS RIPARI ILIN.
ĈIO MI POVOS FARI ESTAS ATENDO
LA MOMENTON DE LA KRASO.
LA ANTAŬVIDITA ALTERIĜA
PUNKTO ESTAS LA TERO.
SUR ĈI TIU PLANEDO,
MI DEZIRAS ####

(翻訳) この宇宙船はもう役に立たない。機能のいくつかはすでにその役目を終えている。私にはそれらを直すことができない。私にできるであろうすべてのことは、衝突の瞬間を待つことだけだ。予測された着陸地点は地球である。この惑星で、私が望むのは####

下ページ

############ROJ
ESTAS FINITAJ.
BRILLA MONDO, LUMA MON###
LA MOND_, KIUN MI IROS
ESTOS MIRINDA LOKO.
MI PLENUMOS Ĉ_UJN MIAJN D###
MI KUROS, KUROS, SALTOS, K###
FLUGOS, KAJ, RAKONTOS!
BONVOLU ATENDU, MIA SOL###

(翻訳) ########は完了した。輝く世界、明るい世界#### 素晴らしい場所だと言える世界。私は私の####をすべて果たすだろう。私は走って、走って、跳ねて、####て、飛んで、そして話をするだろう! 待っていて、私の####

単行本ではエスペラントとしてより自然な文章に修正されたようです。

上のページでは宇宙船の故障、それらが直せないこと、地球に着陸することが書かれています。下のページは未来形になっていますが、何でしょう?

第4話

p. 37 あいさつ

ボナヴー
BONAN
(よっす~)

マティヴー
MATENON
(おいす~)

エスペラントの朝のあいさつ「bonan matenon ボーナンマテーノン」が分割され、互いに呼びかける形になっています。発音は表記と異なっており、もとの単語を語感が良いところで切り取って、語末を「ヴー」にしているようです。

p. 40 旗

LA PLEJ BONA LUMO
EN LA SPACO!

(翻訳)宇宙で最高の光

p. 44 挿絵

「こんにちは」
PEGGJOV=MOVLOV, PIVOU BOVVU=VUV
ペッギョヴ=モヴロヴ ピヴー バヴヴ=ヴヴ

この挨拶はすべてエスペラントには無い単語で構成されています。G や V が連続することも本来はあまりないと思います。「ボナヴー」「マティヴー」もそうですが、V を多用する印象がありますね。

p. 54 挿絵

「仲間・同志」
KAMARADO
トモラーヴ

エスペラントでの意味も「仲間・同志」で、発音は「カマラード」になるはずですが、なぜか「トモラーヴ」になっています。

まとめ

総合的には、文字で書かれているものは完全にエスペラントですが、発音したときに独特の響きに変わるようです。宇宙語が出てくる部分を解読することで、なにか意味深な記述が見つかったりして面白いですね。

ここでとりあげたのは宇宙語に関してのみですが、それ以外でもこの作品には素晴らしいものが詰まっていると思います。星屑テレパスはいいぞ。

COMP を試した

f:id:n4o847:20200411142926j:plain

COMP TRIAL PACK が届いたので摂取した話。

4 月 11 日、昼(Powder)

4 月 8 日の昼に注文したら、GCJ をやってる最中に届いた。

昼ごはんに家族の分のお米をよそったらちょうど自分の分がなかったので、食べる(飲む?)ことにした。

COMP TRIAL PACK のセット内容は POWDER * 3 PACKS + GUMMY * 2 PACKS である。公式サイトによると自分の性別・年齢・運動量では 1食あたり POWDER * 2 程度が適当らしいが、最初なので 1 PACK で試してみる。

1 PACK に対して水 300 mL が推奨らしいのでコップに入れてみるとなみなみの量だった。ここに粉を入れたらこぼれそうなので少しずつ飲むことにする。

溶かしてみた印象としては、なかなか溶けづらい。小麦粉や片栗粉がダマになってしまうような感じ。スプーンで押しつぶしながら混ぜるが溶かしきれない。

飲んでみると、やはり溶けきれない塊が気に障る感じがある。味は、牛乳と豆乳ととうもろこしの中間みたいな味だった(豆乳は好きではないので飲んだことないけど)。個人的には美味しいとはいえない。

冷たいとお腹ゆるくなりそうなのと溶解度の問題かと思ったので温めてみた。味も溶け具合もそんなに変わらない。

ちょうど近くにコーンスープの素がおいてあったので入れて見た。だいぶ飲みやすくなった。もともとの味が薄いので最終的にはコーンスープだし、溶け残りもそんなに気にならなくなる。

飲み終わった感想としては、お腹にたまる感じはあるが、味に関しては早くも飽きそうな感じがある。何かと混ぜて飲むのがいいのかもしれない。

4 月 12 日、昼(Gummy)

GUMMY 1 PACK も POWDER 1 PACK と同じくらいのカロリーとなっている。

フルーツミックス風味らしく、それっぽい匂いがする(フルーツ苦手なのでよくわからない)。40 粒くらい入っている。

特に美味しいわけでもなく不味いわけでもないくらい? 味はそんなに濃くなくて言われてみればフルーツ感がある。噛みごたえは硬めだけど弾性はそんなにない感じ。

10 粒くらい食べたら飽きた。

4 月 13 日、昼(Powder)

お湯に入れてみた。慣れたかもしれないし気のせいかもしれない。

ココアパウダーを入れてみた。ちょっとしか残ってなかったので薄くなってしまったが、もうちょい入れたらまあ飲めるようになるかな、くらいの味になった。

4 月 14 日、昼

カップ麺を食べた。

4 月 15 日、昼(Powder)

2 日前の残った POWDER を飲んだ。感想という感想もなくなってきたのでここまでにする。

まとめ

食事とは何か、どうあるべきかについて考えさせられた。

食べ物自体に求める条件として、

①おいしいこと
②空腹が満たされること
③栄養になること

があり、それに付随して

④安く食べられること
⑤速く食べられること

が実現されれば嬉しいと思っていた。今回の COMP においては、

①自分は味の好き嫌いが多いこともあり、おいしいと思えなかった。
②おいしさが満たされないため満腹まで摂取する気になれなかった。
③長期的な指標であるため実感できなかった。
④高いわけではないが、安いわけでもない。
⑤慣れれば速いのかもしれないがそこまで感じなかった。

という、総合的には良さを実感できない結果となってしまった。期待しすぎていた部分があったのかもしれない。

完全食そのものは決して悪いものではないと思っている。だが感覚としては、食べ物というより薬を飲んでいる気分に近いと思った。