esm アジャイル事業部 開発者ブログ

永和システムマネジメント アジャイル事業部の開発者ブログです。

個人開発中に見た不可解な挙動を調べたらHTML Living Standardに行き着いた話

こんにちは @color_box です。

個人開発中に遭遇した疑問を調べていたら、HTMLのLiving Standardに行き着いた話について書きます。

続きを読む

Turing Completeで学ぶデジタル回路設計

f:id:htkymtks:20211123005417p:plain:w500

こんにちは。永和システムマネジメントの内角低め担当、はたけやまです。

今回は、11月前半の私の可処分時間の全てを注ぎ込んだパズルゲーム「Turing Complete」を紹介します。

Turing Completeとは?

store.steampowered.com

宇宙人にさらわれた主人公が、宇宙人から出題されるパズルを解きながらデジタル回路を作成していく論理パズルゲームです。 Steamで早期アクセス版として配信されており、お値段は2050円。対応プラットフォームWindows、macOS、SteamOS + Linuxです。

Turing Complete は「デジタル回路設計パート」と「プログラミングパート」の二つのパートを行き来しながらゲームが進みます。

デジタル回路設計パート 〜 NANDがあればなんでもできる

f:id:htkymtks:20211122190054p:plain
https://en.wikipedia.org/wiki/NAND_gate より
f:id:htkymtks:20211122190216p:plain
NAND真理値表

NAND回路をご存知ですか?AND回路の出力をNOTで反転させた上記のような回路です。NAND回路があればAND回路やOR回路ひいてはCPUまで、あらゆる論理回路を構成できることが知られています。

f:id:htkymtks:20211122203941p:plain

ゲーム開始時点ではプレイヤーはNAND回路しか使えませんが、NAND回路を組み合わせて「NOT回路」→「AND回路」→「OR回路」→「半加算機」とステップアップしていき、最終的にはチューリング完全なCPUの組み立てを目指します。

f:id:htkymtks:20211121182156p:plain:w300
OR回路
f:id:htkymtks:20211121181929p:plain:w300
CPU

プログラミングパート

CPUを組み立てたあとは、組み立てたCPUを使ってプログラミングパズルを解いていきます。飛来する小惑星の円周を計測したり、金庫のパスコードをブルートフォースアタックでクラッキングしたり、ハノイの塔を解いたりと多彩なステージが待ち受けています。スタックや関数呼び出しを自分で実装するステージなどもあったりして「これが...論理パズル...???」みたいな気持ちになったりして面白かったです。また、アセンブラばかり書いていると「あー、アセンブラだりー、Rubyつかいてー」と普段使っている高級言語のありがたさが身に染みたりしました。

f:id:htkymtks:20211122003746p:plain:w300
小惑星の円周を測れ!

f:id:htkymtks:20211122003940p:plain:w300
ハノイの塔

CPUはピタゴラスイッチ

回路を設計していく中で、シンプルなルールに則って規則ただしくデータが流れていく様はピタゴラ装置のようだなあと感じることが何度もありました。 情報化社会がこんなピタゴラスイッチみたいなものに支えられてるのかと思うと、狐につままれたような気分になります。

こんな人におすすめ

Turing Completeはこんな人におすすめです。

とはいえ、ちょっと微妙なところもあります。

  • 早期アクセス版なので結構バグが残っている
  • 多少の予備知識がないとクリアは難しいかも

現状のTuring Completeは早期アクセス版、未だ開発途中なためバグが結構残っています。例をあげると、複数の部品を動かしたあとにUNDOすると高確率でクラッシュしたり、バグでステージがクリアできなくなったり(すぐに修正されましたが)ということがありました。俺がバグ出ししてやるぜ!という強い気持ちでプレイするのがおすすめです。

また、開発途中のためか説明が足りないところが結構あります。デジタル回路設計について何も知らない状態で挑むとちょっと大変かもしれません。(実績を見ると最終ステージまで到達したユーザーは全体の5%ほどのようです)

それでも挑みたい!という方は以下の書籍が参考になると思います。

まとめ

以上Turing Completeのご紹介でした。低レイヤ好きの皆様はぜひチューリング完全なCPUの自作を目指してみてください!

おまけ 〜 NAND回路はどうやって作るの?

「NAND回路があればどんな論理回路も作れる」と言うけど、そのNAND回路はどうやって作るのか気になりませんか?

Turing Completeと同じ回路設計ゲーム「NandGame」の「NAND」と「NAND(CMOS)」のステージにその答えがあるので、気になる方は以下のリンクをたどって是非チャレンジしてみてください!

nandgame.com

Problem が倒せない

こんにちは、悟空体験アクションRPG を楽しんでる nsgc です。

去年の今頃、Continuous KPTA について紹介しましたが、 KPTA をしていて、いつまでも Problem が残り続けることってありませんか?

私の関わったプロジェクトでは、何度もそういう場面に出くわすことがあります。
1, 2イテレーション位ならまだしも、何ヶ月前からあるの? というものがそのままになっていたりするのです。

なぜこういったことになるのでしょうか?

プロジェクトのコンテキストに依存するところも大きいのですが、これまでの経験したことや伝え聞いた内容からどういうケースがあり、そういう場合にチームはどうしたら良いのか、どうしていったのかを今回は挙げてみました。

Action が具体的じゃない

「KPTA の Action には具体的なものを挙げましょう」、という前提から外れてしまっているケースです。

「XXXの勉強をがんばる」とか「本番作業に気をつける」というお気持ち表明や意気込みだと何をしたら良いのか分からず、いつまでも不安は除けません。
「朝会の後 XXXの読書会をする」、「次回のメンテナンスでは本番作業の手順を用意する」というように具体的で行動しやすい Action にすると着手しやすく、 Problem を早く解決できるかもしれません。

解決まで時間がかかる

Action を実行しているけど、問題解決のための行動がほんの少しずつなので Problem の領域に残ったままになる、という場合もあるかもしれません。

この場合、全部解決するまで KPTA ボード上に残しておく必要は必ずしも無く、少しずつでも改善していっているのならそこから取り除き、別の所で進捗を把握しても良いかもしれません。
タスクとして切り出してプロジェクトの計画に組み込んでいるなら、そっちで成果を追うようにしましょう。

問題が強大すぎる

実現できない Try ばかりのため、着手できる Action が出ない場合は、その Problem はチームで解決できる範囲を超えているのかもしれません。
環境での制約によりどうしようもできない、お客様の社内ルールに手を入れる必要がある、といった場合はなかなか難しいことも多いです。

エスカレーションできるなら偉い人にお任せし、チームの問題からはいったん切り離した方が良いかもしれません。

本当は Problem じゃなかった

ここまでも見てきたように様々な理由で Action に着手できないことはありますが、実は Problem がそもそも Problem じゃない、もしくは Problem では無くなっている事はありませんか?
ふりかえりで挙げた当初は不安や課題であると認識していた。しかし、具体的な改善 Action はなされていないが時間が経つことで、学習や慣れなどを経たためか、何も気にならなくなったというケースです。

もし、チームで誰も困っていないのなら思い切って Problem から除くと良いかもしれません。
きっと、問題だと感じたら、また挙がってくるのですから。

解決のためのコストパフォーマンスが悪い

課題や問題の発生頻度が低く、困り具合が小さいのに対して、それに対する解決策のコストが大きい時にも Problem として残り続けるのかもしれません。

手軽な Action を抽出し実行するか、それが出来ないのならいっそチームとしては Problem を容認しても良いかもしれません。
私達には、もっと他に議論するべき問題がたくさんあるのです。

カイゼンサイクルがまわっていない

ビジネスサイドからの要求が多く、そのため目の前のタスクで手いっぱいになっているケースです。
Action に着手する時間がない。最悪な場合、ふりかえりの時間も取れない場合もあります。

一時的である場合はともかく慢性的にそういう状態になっているのなら、プロジェクト自体の立て直しが必要なのかもしれません。

最後に

残り続ける Problem はこうしてみると実に簡単な原因ばかりに見えますが、なかなかそのことに気付かないことが多いです。
ただ、あらかじめ今回あげたケースがあるということを頭の片隅に置いておくと、客観的に分析し対処できるのではないかと思っております。

もし、私と同じように Problem が残り続けてお困りの方は、上のようなケースにあてはまっていないか検討し、Problem をどうしていくかを考えてみましょう。

Rails / OSS パッチ会オンライン 2021年11月のお知らせ

【重要】Rails/OSS パッチ会で運用していた Idobata ルームは近日閉鎖されます。本記事で言及している Discord へ引越しをお願いします。

2021年11月の Rails / OSS パッチ会を 11月25日(木)に Discord でのオンライン開催をします。

この会をひとことでいうと、日頃のお仕事で使っている Rails をはじめとする OSS について、upstream にパッチを送る会です。

会には Ruby と Rails のコミッターである顧問の a_matsuda もいますので、例えば Rails に送るパッチのネタがあるけれど、パッチを送るに適しているかの判断やパッチを送る流れが悩ましいときなど a_matsuda に相談して足がかりにするなどできます。

開催時間は 17:00-19:00 となりますがご都合のあう方はぜひご参加下さい。

Discord の Rails/OSS パッチ会サーバーへの招待 URL は以下です👇

discord.gg

パッチ会では、来月リリース予定の Ruby 3.1 に関する話題などあるかもしれません。

これからパッチ会に参加してみようという方もぜひどうぞ。Discord でお会いしましょう。


永和システムマネジメントでは、Ruby とアジャイルソフトウェア開発を通じてコミュニティと成長したいエンジニアを絶賛募集しています。

agile.esm.co.jp

【ご案内】Rails/OSSパッチ会をDiscordに会場変更しました

【重要】2021年11月中旬に Rails/OSS パッチ会で運用している Idobata の ルームは閉鎖されます。本記事で案内されている Discord へ引越しをお願いします。

Rails/OSS パッチ会の会場を Discord に移動しました。音質次第で当日のオンライン会場も Discord となる予定です。

Discord の Rails/OSS パッチ会サーバーへの招待 URL は以下です👇

discord.gg

これからパッチ会に参加してみようという方もぜひどうぞ。これまでやりとりに使っていた Idobata の rails ルームは 11 月中旬に閉鎖される予定です。Idobata を情報チャンネルとしていた方は Discord への引越しをお願いします。

次回の Rails/OSS パッチ会は 11月25日(木) 17:00-19:00 です。Discord でお会いしましょう。


永和システムマネジメントでは、Ruby とアジャイルソフトウェア開発を通じてコミュニティと成長したいエンジニアを絶賛募集しています。

agile.esm.co.jp

f:id:koic:20211102145713p:plain

いつもと違うプログラミングの風景を見に行く

昨年、「プログラミング多言語主義」という記事を書きました。

それを踏まえて。 ふだんと違うプログラミング言語を使ったとき、実際にどんな風景が見えるのか、それ見に行こう… というのが、今回の記事の表のテーマです。

先に弁明をしておくと。 今回書くコードは「いつもと違う風景を見る」ことに重心を置いていて、効率とかは脇によけてあります。 その点はご容赦を。

どう書く?:すべての順列を生成するプログラム

早速ですが、一連の要素の順番を入れ替えてできる並びをすべて挙げる例を考えてみましょう。

例えば

(1, 2, 3)

という入力に対して、

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

という出力をえる、というものです。

Rubyで書いたばあいであれば、このような結果になると想像してください。

perm([1, 2, 3])
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]]

あるいはイテレータで、

perm([1, 2, 3]) do |output|
  p output
end
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

Thinking Time

お時間のある方はここで立ち止まって、自分ならどんなコードを書くか、想像してみてください…。

順列を定義する

さて、ここではふだん触れられることの少ない言語を使って順列を定義してみたいと思います。

Prologです。

ふだんあまり使われない言語(たぶん)、Prolog

Prologプログラミングは、ふだん手続的なプログラミングをしている人にとっては、視点の転換をしいてくる面白い言語です。 いつもと違う視点のプログラミングをしてみる例として、今回はPrologで実装していきたいと思います。

Prologを紹介した書籍としては「7つの言語 7つの世界」が割と有名です。 わたしもこの本で関心を持った一人です。

気付くと邦訳が出てから十年になるんですね。

Prolog利用者人口をわたしも把握しているわけではありませんが、周囲を見るかぎり使用している人を見かけません。 そこであえて、Prologを使ってコードを書いてみたいと思います。 はい、わたしの趣味です。

なお今回のコードは、2つの処理系 GNU PrologSWI-Prolog で動作を確認しています。

思考の準備運動

まずはじめに、Prologプログラミングの面白いところを append という述語を例に説明してみたいと思います。 この append はとても使い出がある述語で、この後の実装でも利用する予定です。

「述語」という言葉を使いましたが、Prolog は、関数(function)やメソッド(method)でなく、述語(predicate)でプログラムを書きます。 述語とは入力に対して真偽を返すものです。

append は3つの引数を受け取り、第1引数のリストに第2引数のリストを連結したリストが第3引数のリストであるばあいに真を返します。

実際に処理系を起動して動きを見てみましょう。

GNU Prologの例:

$ gprolog # GNU Prolog を起動
| ?- append([1, 2], [3, 4], [1, 2, 3, 4]).
yes

SWI-Prolog の例:

$ swipl # SWI-Prolog を起動
?- append([1, 2], [3, 4], [1, 2, 3, 4]).
true.

GNU Prologでは真偽を yes, no で返し、SWI Prologでは true, false で返すという違いはありますが、どちらも同じように真を返しています(以降はGNU Prologを使います)。

Prologは、ここが面白いところですが、述語の引数の一部を変数にすると、結果が真になるような値をその変数に割り当てて返してくれます。

例えば、第3引数を変数にすると次のようになります。 ちなみに Prolog では変数名は大文字から書き始めるルールになっていて、ここでは L が変数になります。

| ?- append([1, 2], [3, 4], L).
L = [1,2,3,4]

式が真になるために必要な値が、変数 L に割り当てられました。

これは第1引数を変数にしても、第2引数を変数にしても同じです。

| ?- append([1, 2], L, [1, 2, 3, 4]).
L = [3,4]
| ?- append(L, [3, 4], [1, 2, 3, 4]).
L = [1,2]

第1引数と第2引数の両方を変数にすると、他のプログラミング言語ではあまり見かけない結果を返してくれます。

| ?- append(L1, L2, [1, 2, 3, 4]).
L1 = []
L2 = [1,2,3,4] ?

まず、[][1, 2, 3, 4] を追加すると [1, 2, 3, 4] になるので、結果が真になる値の組み合わせです。

結果を表示した後は入力待ちの状態になっているので、ここでセミコロン ( ; ) を入力します。

| ?- append(L1, L2, [1, 2, 3, 4]).
L1 = []
L2 = [1,2,3,4] ? ;

L1 = [1]
L2 = [2,3,4] ?

[1][2, 3, 4] の組み合わせが表示されます。 これも式が真になる値の組み合わせです。

このように真になる値が複数あるばあいに、すべての結果を出力してくれます。 セミコロンは他の値の出力を促す入力になっています。

他にも組み合わせがあるので、何回かセミコロンを入力してましょう。

| ?- append(L1, L2, [1, 2, 3, 4]).
L1 = []
L2 = [1,2,3,4] ? ;

L1 = [1]
L2 = [2,3,4] ? ;

L1 = [1,2]
L2 = [3,4] ? ;

L1 = [1,2,3]
L2 = [4] ? ;

L1 = [1,2,3,4]
L2 = []

とりうる値のすべての組み合わせが出力されると、ようやく通常のプロンプトに戻りました。

Prolog自体の詳細は、先に紹介した「7つの言語 7つの世界」やドキュメントを参照してみてください。

これらを踏まえて。 ようやく順列をえる述語 perm を実装します。

順列の Prolog での実装

% agile-dev-blog.pro

perm([], []).                           % 空のばあい
perm([Head | Tail], Output) :-          % 第1引数を Head と Tail に分割
  perm(Tail, Partial),                  % Partial は Tail の順列であり、
  append(Left, Right, Partial),         % Partial は Left と Right から成り、
  append(Left, [Head | Right], Output). % Output は、その Left と Right の間に Head を置いたもの

このコードは agile-dev-blog.pro というファイル名のファイルに保存しておいてください。

[Head | Tail] という記述は、リストを先頭の要素と後続のリストにわけて表現したものです。

| ?- [1, 2, 3] == [1 | [2, 3]].
yes

先頭の複数の要素については次のように書くこともできます。

| ?- [1, 2, 3, 4] == [1, 2 | [3, 4]].
yes

| ?- [1, 2 | [3, 4]] == [1 | [2 | [3, 4]]].
yes

では実行してみましょう。

GNU Prologでのばあいは次のようにファイルを読み込みます。

$ gprolog --consult-file agile-dev-blog.pro

SWI-Prologのばあいは次のようになります。

$ swipl -f agile-dev-blog.pro

起動してファイルの読み込みが完了するとプロンプトが表示されれますので、次のように入力します。

| ?- perm([1, 2, 3], Output).

今回実装した perm も、先ほどの append のばあいと同じように、変数がとりうる値は複数あるので、セミコロンを入力して残りを表示しましょう。

| ?- perm([1, 2, 3], Output).
Output = [1,2,3] ? ;
Output = [2,1,3] ? ;
Output = [2,3,1] ? ;
Output = [1,3,2] ? ;
Output = [3,1,2] ? ;
Output = [3,2,1]

いかがでしょう?。 コードも動きも見慣れない、不思議な印象を受けたのではないでしょうか。

ふだんプログラミングをするとき、多くのばあいで「問題を『どのように』解くか」と、手順を考えると思います。

一方Prologプログラミングでは「問題に対して解は『どうあるべき』なのか」と考えることが求められれます。 脳のふだん使わない部分を、がんばって稼働させる感覚さえしてきます。

どう書く?:ソートプログラム

これで順列をえる手段を入手することができました。

これを利用して、今度はソートを考えてみたいと思います。

Thinking Time

お時間のある方はここで立ち止まって、自分ならどんなコードを書くか、想像してみてください…。

Prolog でなく、先ほどの Thinking Time で想像したご自身のコードをもとに考えてもらって大丈夫です…。

ソートを定義する

ソートのアルゴリズムは多々ありますが、いざソートを定義しようとすると、その手順が頭に浮かんでしまいます。

その思いをふりはらい、入力と出力に注目してみます。

入力: [5, 1, 4, 2, 3]

出力: [1, 2, 3, 4, 5]

ここまでの話の流れをふまえて。 入力と出力をじっと見てみると。 出力は「入力の要素を並べ替えてできる列のうち、隣り合うどの2つの要素を取り出しても、左の要素が右の要素以下であるもの」という見方も見えてきませんか?

ソートの Prolog での実装

そのような見方をPrologのコードにしてみましょう。

% agiile-dev-blog.pro

perm([], []).
perm([N | Rest], Perm) :-
  perm(Rest, Partial),
  append(Left, Right, Partial),
  append(Left, [N | Right], Perm).

my_sort(Input, Output) :- % ※ 組み込みの述語 sort と名前が衝突しないようにしています
  perm(Input, Output),             % 順列のうち、
  forall(                          % すべての、
    append(_, [N, M | _], Output), % 出力内の、隣接する要素は、
    N =< M                         % 左の要素が右の要素以下である
  ).

起動してファイルを読み込ませて実行してみます。

| ?- my_sort([5, 1, 4, 2, 3], L).
L = [1,2,3,4,5] ?

結果が出力されました。 が、入力待ちになっています。

これは見つけた結果以外で条件に合うものが残りの中にある可能性があるためです。 この入力では1つだけですが、重複した要素があるばあいにそれぞれを別の要素として扱っているので、それぞれの順序が結果として出力されます。

| ?- my_sort([2, 1, 1], L).
L = [1,1,2] ? ;
L = [1,1,2]

このようなばあい、Prolog のプログラミングの手法として、条件に合う結果がえられたら探索の打ち切りを指示することができます。

my_sort(Input, Output) :-
  perm(Input, Output),
  forall(
    append(_, [N, M | _], Output),
    N =< M
  ),
  !. % 条件に合致したら探索を打ち切る
| ?- my_sort([2, 1, 1], L).
L = [1,1,2]

最初に見つかった結果だけが出力されるようになりました。

どこかで見覚えがありません?

プログラミングとしては、見慣れないコードだったかと思いますが、ここ感じどこかで覚えがありませんか?

ある集まりから、条件に合う結果を出力する。

Ruby on Railsプログラマでしたらよくご存知の、SQLがそれですね。 SQLを書くことは、条件を組み合わせてDBに格納されているデータから欲しいデータを取得する、プログラムを書いていることでもあるわけです。

SQLは、実際にデータ検索以外の問題を解くこともできます(これとかこれとかこれとか)。 ですが、あまり無茶をなさらぬよう…。

まとめ:いつもと違う風景を見に行く

ある問題を解くアルゴリズムが複数あることからもわかるように、複数の解法があることが一般的です。

一方で、解法に注目するのでなく、ここでPrologで書いたように、結果に注目して問題に取り組むという方法もあるわけです。

複雑化する問題に頭を抱えたとき、この記事が「そもそも問題はなんだっけ?」「欲しいものはなんだっけ?」という気付きの一助になれば幸いです。


「情報化技術を通じて社会と共生する」株式会社永和システムマネジメント アジャイル事業部では、エンジニアを絶賛募集しています。 応募エントリお待ちしております! 一緒にいつもと違う風景を見に行きませんか? 応募エントリお待ちしております!

agile.esm.co.jp

Rails / OSS パッチ会オンライン 2021年10月のお知らせ

2021年10月の Rails / OSS パッチ会を 10月28日(木)にオンライン開催します。

この会をひとことでいうと、日頃のお仕事で使っている Rails をはじめとする OSS への upstream にパッチを送る会です。

会には Ruby と Rails のコミッターである顧問の a_matsuda もいますので、例えば Rails に送るパッチのネタがあるけれど、パッチを送るに適しているかの判断やパッチを送る流れが悩ましいときなど a_matsuda に相談して足がかりにするなどできます。

開催時間は 17:00-19:00 となりますがご都合のあう方はぜひご参加下さい。Zoom あたりのテレビ会議システムを使います。

当日の招待 URL は Idobata の esminc/rails ルームで共有する予定です。

idobata.io

特に募集ページなど設けませんが、上記理由からすでに Idobata のアカウントを持っている方は、当日の案内を Idobata にてご確認ください。 また Idobata はクローズ化されているため Idobata アカウントを持っていない参加希望の方は、@koic までメンションしてください。

パッチ会では、来月開催の RubyConf 2021 に関する話題などあるかもしれません。

rubyconf.org

Hacktoberfest への活動の場としてもご活用ください。

hacktoberfest.digitalocean.com

その他の開催方針については以下の Gist に記していますので、ご参照ください。

Reboot Rails/OSS meetup online · GitHub