Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
君は古の言語M4を知っているか (LT)
Search
MakKi
May 18, 2022
Programming
630
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
君は古の言語M4を知っているか (LT)
M4のチューリング完全性について、BrainF*ckを実装することで証明した
MakKi
May 18, 2022
Transcript
24 slides
君は古の言語 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.
ありがとうございました。
More Decks by MakKi
See All by MakKi
zero-micro: Codex Microがzero-kb02にそっくりだったので作ったった
makki_d
0
110
テストだけじゃない!インプロセスDBで生まれるGoらしさ
makki_d
0
85
テストだけじゃない!インプロセスDBで生まれるGoらしさ
makki_d
0
91
SQLだけでマイグレーションしたい!
makki_d
0
1.4k
Recap: An Operating System in Go
makki_d
2
220
XSLTで作るBrainfuck処理系
makki_d
0
490
眼鏡と視力についての誤解を解く
makki_d
0
270
標準ライブラリの動向とイテレータのパフォーマンス
makki_d
3
810
range over funcのエラー処理
makki_d
1
1.9k
Other Decks in Programming
See All in Programming
Engineering Biometric UX Across Android Versions | DroidKnights 2026
ryunen344
1
210
ローカルLLMの基本と近況 2611 / Local LLM basics and recent situation 2611
kishida
2
480
動画プレイヤーはなぜカクつくのか 〜Flutterのレンダリングとネイティブの境界を解剖する〜
naruogram
0
340
AIで開発が速くなった先で、開発チームは何を目指すか
shihochan
1
2.1k
Materialが消えた日 〜真っ白なFlutterキャンバスにRenderObjectで絵を描く〜
umigishiaoi
0
160
우리의 Nitro Modules는 당신의 Turbo Modules보다 아름답다
l2hyunwoo
0
260
クラウドゲーミングのパフォーマンス最適化に挑む / Cloud Gaming Performance Tuning
vivion
0
340
将来の標準フォーマッター?ktfmtを深堀る
t45k
0
140
地方こそサーバーレス — 10年続けた、顔が見えるチームで確かな基盤を / Serverless Matters Most in Regional Areas — 10 Years of Building Reliable Foundations with Close-Knit Teams
seike460
PRO
1
460
Vapor Mode でアクセシビリティは 壊れないか検証した話
fuqda
1
350
AI-Powered Domain-Driven Design
ziobrando
0
450
React Native에 현대적인 빌드 도구 더하기: Rollipop 구현기
leegeunhyeok
0
180
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
17k
My Coaching Mixtape
mlcsv
0
390
The Invisible Side of Design
smashingmag
301
52k
Mobile First: as difficult as doing things right
swwweet
225
10k
Context Engineering - Making Every Token Count
addyosmani
9
1.3k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
33
5.8k
Leo the Paperboy
mayatellez
11
2.5k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
31
10k
Exploring the relationship between traditional SERPs and Gen AI search
raygrieselhuber
PRO
4
4.4k
How to Think Like a Performance Engineer
csswizardry
28
2.9k
Kristin Tynski - Automating Marketing Tasks With AI
techseoconnect
PRO
0
590
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
128
56k