三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#

AtCoderで Forth 入門

概要

今回はプログラミング言語Forth について書きます。
この記事は刺身タンポポ同好会のアドベントカレンダーの記事です。
刺身タンポポ同好会についてはこちら
昨日の記事はこちら
明日の記事はこちら

目次


Forth とは

言語概要は wikipediaの記事 でも読んでみてください。
とてもざっくり説明すると、逆ポーランド気法を用いるスタック型の言語です。
ちなみに、いわゆる難解プログラミング言語ではなく、れっきとした実用言語みたいです。
ただし、私は難解プログラミングに近いものを感じました。 型という概念はないですが、形式上浮動小数がなかったり、入出力がめんどくさいイメージです。(もしかしたら私のリサーチ不足で実際にはあるのかもしれません。)

所感

この言語は実用言語ということもあり、関数を作成することができます。
普段書いている brainfuck には関数がないのでとてもうれしいです。 また、- も関数名に使える珍しい言語なので、せっかくなのでケバブケースでコードを書いていきます。

命令一覧

難解プログラミング言語ではないので、結構多いです。
こちらのサイトに一覧があるので参考にしてください。 今回の肝になる命令をいくつか挙げておきます。

  • 関数宣言
    : name ... ; で関数を宣言できます。関数と書きましたが関数以外にも使えます。
  • ループ
    begin ... untilbegin ... while ... then などでループが書けます。
  • スタック操作命令   dup, swap, drop 等があります。
  • 算術命令 四則演算や比較演算です。

AtCoder で利用してみる

導入

この言語はAtCoderで使えるので問題を解くことを考えていきましょう。 幸い、AtCoderの問題の多くは整数のみで解くことができます。

入力

数値の入力を行う必要があります。 数値の入力は簡単で、1 文字ずつ数字にパースし既存の値を 10 倍して足すを繰り返すだけです。

: read-number 0 0 begin swap 10 * + key 48 - dup 0 < until drop ;

出力

数値の出力を行う必要もあります。 数値の出力は 正負の判定を行った後、10 の商と余りを求めて余りをスタックに積んでいきます。それを商が0になるまで繰り返し、スタック上の数値を順に出力すればいいです。 もちろん、スタック上のすべてを出力すると数値出力で積まれた数値以外も出力してしまいますので、マーカーとして 0 をあらかじめスタックに積むなどを行う必要があります。

: write-pure ( d --  ) 
dup 0<> if dup 0< if ." -" negate then -1 swap begin dup 0 <> while 10 /mod repeat drop begin dup -1 <> while 48 + emit repeat drop else ." 0" then ;

実際の問題を解く。

今回は簡単な問題として、ABC007-A 植木算 を解きます。 この問題は入力の数値から 1 引いた数値を出力することで達成できます。

: read-number 0 0 begin swap 10 * + key 48 - dup 0 < until drop ;
dup 0 <> while 10 /mod repeat drop begin dup -1 <> while 48 + emit repeat drop else ." 0" then ;
: write-cr ( d --  ) write-pure cr ;
 
read-number
1- 
write-cr

以上で解けました。 実際の提出はこちらです。

終わりに

この記事を見た人のほとんどが「ちゃんと解説を書け」と思うことだと思います。
私も思います。ただ、どうせ丁寧に書いてもほとんどの人は斜め読みしかしないでしょうし、本当に読みたいと思う人は、自力で解読すると思ってます。
もっと言うと、これを見て自力で書いてみたいという殊勝な人は元から難解プログラミング言語にあるていど触れており、この記事に書かれているコードなら自力で作成できる人だと思ってます。
なのでそれを言い訳にあまり丁寧には書きませんでした。 マインクラフトをしていたら記事を書く時間が無くなったとか、Forth をそもそもだいぶ忘れていたとかではありせん。決して。 この記事を見て万が一気になったという人はぜひ使ってみてください。