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
440
君は古の言語M4を知っているか (LT)
M4のチューリング完全性について、BrainF*ckを実装することで証明した
MakKi
May 18, 2022
Tweet
Share
More Decks by MakKi
See All by MakKi
XSLTで作るBrainfuck処理系
makki_d
0
220
眼鏡と視力についての誤解を解く
makki_d
0
130
標準ライブラリの動向とイテレータのパフォーマンス
makki_d
3
710
range over funcのエラー処理
makki_d
1
1.7k
GoとテストとインプロセスDB
makki_d
3
610
型パラメータが使えるようになったのでLINQを実装してみた
makki_d
2
1.4k
mallocしただけでメモリが確保できるって本当ですか?
makki_d
0
240
ホットリロードツールの作り方
makki_d
0
1.1k
JavaプログラムをGoに移植するためのテクニック――継承と例外
makki_d
1
1.8k
Other Decks in Programming
See All in Programming
kiroでゲームを作ってみた
iriikeita
0
140
대규모 트래픽을 처리하는 프론트 개발자의 전략
maryang
0
110
Streamlitで実現できるようになったこと、実現してくれたこと
ayumu_yamaguchi
2
270
実践 Dev Containers × Claude Code
touyu
1
120
書き捨てではなく継続開発可能なコードをAIコーディングエージェントで書くために意識していること
shuyakinjo
0
190
Jakarta EE Meets AI
ivargrimstad
0
580
Gemini CLIの"強み"を知る! Gemini CLIとClaude Codeを比較してみた!
kotahisafuru
3
920
Flutterと Vibe Coding で個人開発!
hyshu
1
230
GitHub Copilotの全体像と活用のヒント AI駆動開発の最初の一歩
74th
6
1.8k
JetBrainsのAI機能の紹介 #jjug
yusuke
0
180
ZeroETLで始めるDynamoDBとS3の連携
afooooil
0
150
Advanced Micro Frontends: Multi Version/ Framework Scenarios
manfredsteyer
PRO
0
150
Featured
See All Featured
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.4k
KATA
mclloyd
31
14k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Designing for humans not robots
tammielis
253
25k
Making the Leap to Tech Lead
cromwellryan
134
9.5k
Why You Should Never Use an ORM
jnunemaker
PRO
58
9.5k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
332
22k
A designer walks into a library…
pauljervisheath
207
24k
Java REST API Framework Comparison - PWX 2021
mraible
32
8.8k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
33
2.4k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.6k
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.
ありがとうございました。