Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
君は古の言語M4を知っているか (LT)
Search
MakKi
May 18, 2022
Programming
0
300
君は古の言語M4を知っているか (LT)
M4のチューリング完全性について、BrainF*ckを実装することで証明した
MakKi
May 18, 2022
Tweet
Share
More Decks by MakKi
See All by MakKi
標準ライブラリの動向とイテレータのパフォーマンス
makki_d
2
130
range over funcのエラー処理
makki_d
0
1.2k
GoとテストとインプロセスDB
makki_d
2
460
型パラメータが使えるようになったのでLINQを実装してみた
makki_d
2
1.3k
mallocしただけでメモリが確保できるって本当ですか?
makki_d
0
170
ホットリロードツールの作り方
makki_d
0
990
JavaプログラムをGoに移植するためのテクニック――継承と例外
makki_d
1
1.6k
JavaプログラムをGoに移植するためのテクニック――継承と例外
makki_d
4
4k
mallocしただけでメモリが確保できるって本当ですか?
makki_d
4
660
Other Decks in Programming
See All in Programming
DjangoNinjaで高速なAPI開発を実現する
masaya00
0
140
Patched fetch did not work
quramy
6
460
NANIMACHI
naokiito
0
840
◯◯エンジニアになった理由
gessy0129
PRO
0
110
Applied NLP in the Age of Generative AI
inesmontani
PRO
3
1k
Prolog入門
qnighy
4
1.1k
Frontend Magic mit CSS Houdini
joergneumann
0
420
"型"のあるRailsアプリケーション開発 / Typed Rails application development
sinsoku
7
2k
個人開発のおいしさと続け方
3l4l5
0
110
Shinjuku.rb#95:心の技術書紹介
free_world21
1
120
GraphQL あるいは React における自律的なデータ取得について
quramy
13
3.2k
From Idea to IDE: Developing Plugins for Android Studio
thisaay
1
540
Featured
See All Featured
Design by the Numbers
sachag
277
19k
The Mythical Team-Month
searls
218
43k
Into the Great Unknown - MozCon
thekraken
29
1.4k
VelocityConf: Rendering Performance Case Studies
addyosmani
322
23k
Git: the NoSQL Database
bkeepers
PRO
425
64k
Build The Right Thing And Hit Your Dates
maggiecrowley
30
2.3k
It's Worth the Effort
3n
182
27k
Infographics Made Easy
chrislema
239
18k
Principles of Awesome APIs and How to Build Them.
keavy
125
17k
Debugging Ruby Performance
tmm1
72
12k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
248
20k
Transcript
君は古の言語 M4を知っているか KLab株式会社 牧内大輔
自己紹介 • 牧内大輔(MakKi) • Twitter: @makki_d • GitHub: makiuchi-d •
学生の頃 ◦ 専攻は発生生物学 ◦ 動画関連のOSS(AviUtlの透過性ロゴとかいろいろ) • 入社してから ◦ ガラケー向けブラウザゲーム→スマホゲーム
最近の仕事 オンライン対戦データ中継システム • クライアント: C# (Unity/.Net) • サーバ: Go+MySQL(Aurora) •
通信: WebSocket、gRPC • 開発環境: docker-compose game (go) lobby (go) hub (go) MySQL 端末 部屋検索 gRPC 部屋作成・参加 部屋情報書き込み websocket 観戦clientとして接続 websocket clientとして接続 (Player or 観戦) HTTP(msgpack) 部屋検索・参加
M4 is 何?
M4 is 何? “ m4 は、ブライアン・カーニハンとデニス・リッチーが設計した汎用マク ロプロセッサである。その名称は、"macro" の "m" と、AP-3ミニコ
ンピュータでデニス・リッチーがそれ以前に書いたマクロプロセッサ "m3" の次、というところから来ている。 出展:wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
マクロプロセッサ?
マクロプロセッサ define(`H’, `Hello, $1!!’) こんなマクロを定義して
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) こんなふうに呼び出すと
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される 定型文を生成するのに便利
M4 is 何? “ ……それ以前のマクロプロセッサとは異なり、特定のコンピュータ言語 や自然言語を対象としたものではない。ただし、もとはFORTRANの方言 であるRatforの開発で使うために開発された。 他のマクロプロセッサとは異なり、m4 は一般的なプログラミング言語と 同様、チューリング完全である。
出展:wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
チューリング完全?
チューリング完全 “ 計算理論において、ある計算のメカニズムが万能チューリングマシンと 同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリ ングかんぜん、Turing-complete)あるいは計算完備であるという。 (中略) 簡単に言えば、チューリング完全であれば、実現可能なアルゴリズムや 手続きはすべて処理できるということを意味している。 出展:wikipedia http://ja.wikipedia.org/wiki/チューリング完全
つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる
つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる M4は万能
確かめてみよう
確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK
確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK チューリング完全な処理系 Brainfuck
Brainfuckとは +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.++++++ +..+++.>-.------------.<++++++++.--------.+++.------.- -------.>+. Hello, world!
M4で実装してみた
bfm4 https://github.com/makiuchi-d/bfm4 KLab TechBook Vol.1 でも解説(PDFダウンロードできます) https://www.klab.com/jp/blog/tech/2022/tbf12.html
デモ
結論 M4はチューリング完全である. Q.E.D.
ありがとうございました。