Upgrade to Pro — share decks privately, control downloads, hide ads and more …

XSLTで作るBrainfuck処理系

Avatar for MakKi MakKi
June 14, 2025
Programming
0
96

 XSLTで作るBrainfuck処理系

関数型まつり2025
Avatar for MakKi

MakKi

June 14, 2025
Tweet

More Decks by MakKi

See All by MakKi
眼鏡と視力についての誤解を解く
Avatar for MakKi makki_d
0
120
標準ライブラリの動向とイテレータのパフォーマンス
Avatar for MakKi makki_d
3
680
range over funcのエラー処理
Avatar for MakKi makki_d
1
1.7k
GoとテストとインプロセスDB
Avatar for MakKi makki_d
3
600
君は古の言語M4を知っているか (LT)
Avatar for MakKi makki_d
0
410
型パラメータが使えるようになったのでLINQを実装してみた
Avatar for MakKi makki_d
2
1.4k
mallocしただけでメモリが確保できるって本当ですか？
Avatar for MakKi makki_d
0
230
ホットリロードツールの作り方
Avatar for MakKi makki_d
0
1.1k
JavaプログラムをGoに移植するためのテクニック――継承と例外
Avatar for MakKi makki_d
1
1.7k

Other Decks in Programming

See All in Programming
Parallel::Pipesの紹介
Avatar for Shoichi Kaji skaji
2
900
Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング
Avatar for Naoya Ito naoya
4
400
セキュリティマネジャー廃止とクラウドネイティブ型サンドボックス活用
Avatar for Kenji Kazumura kazumura
1
150
機械学習って何？ 5分で解説頑張ってみる
Avatar for Kazuki Ishikawa kuroneko2828
0
180
ワイがおすすめする新潟の食 / 20250530phpconf-niigata-eve
Avatar for kasacchiful kasacchiful
0
290
OpenNext + Hono on Cloudflare で イマドキWeb開発スタックを実現する
Avatar for rokuosan rokuosan
0
110
バリデーションライブラリ徹底比較
Avatar for Yuta Tanaka nayuta999999
1
580
複数アプリケーションを育てていくための共通化戦略
Avatar for irof irof
9
3.5k
TypeScriptのmoduleオプションを改めて整理する
Avatar for おおいし bicstone
4
460
漸進。
Avatar for TOMIKAWA Sotaro ssssota
0
1.6k
関数型まつり2025登壇資料「関数プログラミングと再帰」
Avatar for Taison Tsukada taisontsukada
1
320
RubyKaigi Hack Space in Tokyo & 函館最速 "予習" 会 / RubyKaigi Hack Space in Tokyo & The Fastest Briefing of RubyKaigi 2026 in Hakodate
Avatar for moznion moznion
1
130

Featured

See All Featured
Scaling GitHub
Avatar for Zach Holman holman
459
140k
Fight the Zombie Pattern Library - RWD Summit 2016
Avatar for Marcelo Somers marcelosomers
233
17k
Gamification - CAS2011
Avatar for David Bonilla davidbonilla
81
5.3k
Keith and Marios Guide to Fast Websites
Avatar for Keith Pitt keithpitt
411
22k
Stop Working from a Prison Cell
Avatar for Chris Michel hatefulcrawdad
269
20k
Rails Girls Zürich Keynote
Avatar for Gregor Martynus gr2m
94
13k
Why You Should Never Use an ORM
Avatar for John Nunemaker jnunemaker
PRO
56
9.4k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
Avatar for Sam Stephenson sstephenson
161
15k
Into the Great Unknown - MozCon
Avatar for Noah Learner thekraken
39
1.8k
Bootstrapping a Software Product
Avatar for Garrett Dimon garrettdimon
PRO
307
110k
Six Lessons from altMBA
Avatar for Skipper Chong Warson skipperchong
28
3.8k
Being A Developer After 40
Avatar for Adrian Kosmaczewski akosma
90
590k

Transcript

  1. XSLTで作るBrainfuck処理系 XSLTは関数型言語たり得るか？

  2. 自己紹介 • 牧内大輔（MakKi） ◦ 　@makki_d ◦ 　makiuchi-d • KLab株式会社 ◦

    スマホゲーム、主にサーバサイドや同期通信まわり • OSS ◦ gozxing: バーコードQRコード ◦ arelo: 自動リロード ◦ EMLauncher: スマホデバッグアプリ配信 ◦ WSNet2: 同期通信 • Go言語界隈によく出没

  3. XSLT

  4. • EXtensible Stylesheet Language Transformation • XMLをXMLや他の形式に変換するスタイルシート 言語 ◦ XSL自身もXMLで記述する

    XSLTとは XML </> HTML < > TXT Aa XML </> XSLT XSL </>

  5. <?xml version="1.0" encoding="utf-8"?> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:output method="html"/> <xsl:template match="/">

    <html> <body> <h1>Library Books</h1> <ul> <xsl:apply-templates select="library/book"/> </ul> </body> </html> </xsl:template> <xsl:template match="book"> <li> <strong> <xsl:value-of select="title"/> </strong> by <xsl:value-of select="author"/> </li> </xsl:template> </xsl:stylesheet> convert.xsl <?xml version="1.0" encoding="utf-8"?> <library> <book> <title>Learning XSLT</title> <author>John Doe</author> </book> <book> <title>XML in Action</title> <author>Jane Smith</author> </book> </library> input.xml <html> <body> <h1>Library Books</h1> <ul> <li> <strong>Learning XSLT</strong> by John Doe </li> <li> <strong>XML in Action</strong> by Jane Smith </li> </ul> </body> </html> output.html

  6. XSLTの特徴 • 宣言的なテンプレート <xsl:template> • テンプレートの再帰呼び出し による繰り返し処理 • パターンマッチング でテンプレートを自動選択

    • 変数 <xsl:variable> が不変（再代入不可） すごく関数型言語ぽい！

  7. XSLTは関数型言語か？ • そもそもプログラミング言語 と言えるのか？ ◦ プログラミング言語であるからにはチューリング完全が求められる • プログラミング言語ならばチューリング完全 であるべき ◦

    計算可能なアルゴリズムは全てチューリングマシン上の計算に書き換えられる ▪ チューリングマシンはあらゆる計算可能な計算が可能 ◦ チューリングマシンと同等の能力を持つことを「チューリング完全」と呼ぶ ▪ チューリング完全ならあらゆる計算可能な計算が可能 • チューリング完全な 処理系を実装できればチューリング完全

  8. Brainfuckを実装してみた

  9. Brainfuckとは • 記号のみで記述 • 8つの命令しかない言語 • メモリ配列 とポインタを持つ • もちろんチューリング完全

    実装が簡単！ +++++++++[>++++++++>+++++++++ ++>+++++<<<-]>.>++.+++++++..+ ++.>-.------------.<++++++++. --------.+++.------.--------. >+. hello.bf

  10. BrainfuckをXMLで表現 • 各命令をタグで表現 ◦ 記号と1:1対応 • XSLTプロセッサがパースしてくれる ◦ [と ]の対応が親子関係でわかる

    • 標準入力も含めることに <?xml version="1.0" encoding="utf-8"?> <?xml-stylesheet type="text/xsl" href="bf.xsl"?> <bf> <code> <inc/><inc/> <loop> <dec/><right/><read/><inc/><print/><left/> <end/> </loop> </code> <input>Aa</input> </bf> atob.xml “Aa”を”Bb”にするプログラム: ++[->,+.]

  11. ポインタのインクリメント（ >） • 状態を引数でまるごと伝搬 ◦ ptr: ポインタ ◦ mem: メモリ配列

    ◦ input: 標準入力文字列 • <right/>のテンプレート ◦ 次の命令のテンプレート呼び出し ◦ 直後の兄弟要素 ▪ following-sibling::*[1] ◦ 引数のptrを+1 <xsl:template match="right"> <xsl:param name="ptr"/> <xsl:param name="mem"/> <xsl:param name="input"/> <xsl:apply-templates select="following-sibling::*[1]"> <xsl:with-param name="ptr" select="$ptr + 1"/> <xsl:with-param name="mem" select="$mem"/> <xsl:with-param name="input" select="$input"/> </xsl:apply-templates> </xsl:template>

  12. メモリの実装 • メモリ配列の表現 ◦ 連番のXML要素 ▪ key = '_'+ptrの値 •

    読み出し ◦ 名前が$keyな要素の値 ▪ sumで存在しないとき0に • 書き込み ◦ write-valテンプレート ◦ $key以外の要素のコピー ◦ $keyの要素を追加 ▪ 値を$valに <_0>65</_0> <_1>66</_1> <_2>67</_2> <_3>68</_3> sum(exsl:node-set($mem)/*[name()=$key]) <xsl:template name="write-val"> <xsl:param name="mem"/> <xsl:param name="key"/> <xsl:param name="val"/> <xsl:for-each select="exsl:node-set($mem)/*[name()!=$key]"> <xsl:copy-of select="."/> </xsl:for-each> <xsl:element name="{$key}"> <xsl:value-of select="$val"/> </xsl:element> </xsl:template>

  13. 値のインクリメント（ +） • ポインタが指すメモリの現在の値 ◦ 取り出すための key（'_' + ptr） ◦

    値 val • write-val テンプレート ◦ メモリの"$key"に"$val+1" を書く ◦ まるごと作り直して次の命令に渡す <xsl:template match="inc"> <!-- param 省略 --> <xsl:variable name="key" select="concat('_', $ptr)"/> <xsl:variable name="val" select="sum(exsl:node-set($mem)/*[name()=$key])"/> <xsl:variable name="mem"> <xsl:call-template name="write-val"> <xsl:with-param name="mem" select="$mem"/> <xsl:with-param name="key" select="$key"/> <xsl:with-param name="val" select="$val + 1"/> </xsl:call-template> </xsl:variable> <!-- apply-templates 省略 -->

  14. ループ（[ ]） • <xsl:choose>で分岐 ◦ 非0のとき：子要素の先頭 ▪ "*[1]" ◦ 0のとき：直後の兄弟要素

    ▪ "following-sibling::*[1]" • ループ終端 <end/> ◦ 親要素でapply-template ▪ "parent::node()" <!-- いろいろ省略 --> <xsl:choose> <xsl:when test="$val != 0"> <xsl:apply-templates select="*[1]"> <xsl:with-param name="ptr" select="$ptr"/> <xsl:with-param name="mem" select="$mem"/> <xsl:with-param name="input" select="$input"/> </xsl:apply-templates> </xsl:when> <xsl:otherwise> <xsl:apply-templates select="following-sibling::*[1]"> <xsl:with-param name="ptr" select="$ptr"/> <xsl:with-param name="mem" select="$mem"/> <xsl:with-param name="input" select="$input"/> </xsl:apply-templates> </xsl:otherwise> </xsl:choose>

  15. 実装できた！ • https://github.com/makiuchi-d/bfxslt • 解説記事 KLabTechBook Vol. 14 ◦ 技術書典18にて頒布中

    ▪ 物理本500円（在庫残り1冊） ▪ 電子版0円 ◦ ブログでも読めます 新刊もあります

  16. XSLTは プログラミング言語 である

  17. 関数型言語たり得るか？

  18. 関数型言語であるためには • 関数が一級オブジェクト ◦ 関数を変数に拘束できたり演算できたり • XSLTのテンプレートは一級オブジェクトではない ◦ テンプレート自体を変数や引数に拘束できない ◦

    動的生成もできない ▪ XSL自体もXMLなのでXSLからXSLを生成するXSLTを多段で呼べばあるいは ……

  19. XSLTは 関数型言語ぽい プログラミング言語である

  20. つづく？ 実はXSLT2.0でtemplateとは別にfunctionが導入され XSLT3.0でfunctionが一級オブジェクトになったのは また別のお話……