Upgrade to Pro — share decks privately, control downloads, hide ads and more …
Sign up for free

XSLTで作るBrainfuck処理系

Avatar for MakKi MakKi
June 14, 2025
Programming
440
0

 XSLTで作るBrainfuck処理系

関数型まつり2025

Avatar for MakKi

MakKi

June 14, 2025

More Decks by MakKi

See All by MakKi
テストだけじゃない！インプロセスDBで生まれるGoらしさ
Avatar for MakKi makki_d
0
56
テストだけじゃない！インプロセスDBで生まれるGoらしさ
Avatar for MakKi makki_d
0
72
SQLだけでマイグレーションしたい！
Avatar for MakKi makki_d
0
1.4k
Recap: An Operating System in Go
Avatar for MakKi makki_d
2
190
眼鏡と視力についての誤解を解く
Avatar for MakKi makki_d
0
240
標準ライブラリの動向とイテレータのパフォーマンス
Avatar for MakKi makki_d
3
790
range over funcのエラー処理
Avatar for MakKi makki_d
1
1.9k
GoとテストとインプロセスDB
Avatar for MakKi makki_d
3
710
君は古の言語M4を知っているか (LT)
Avatar for MakKi makki_d
0
590

Other Decks in Programming

See All in Programming
業務時間外もAIに働いてもらう話
Avatar for taki colorful12
3
10k
標準パッケージに uuid が追加された 背景から見る Go らしい意思決定 / go_127_uuid_decision
Avatar for convto convto
5
5.7k
The Good Stuff, Not the Slop: Engineering High-Quality Android Apps with Modern AI Tooling
Avatar for danybony danybony
1
230
DroidKaigi 2026 「個人開発という実験場: Android エンジニアが手にする4つの自由」
Avatar for SlashNephy slashnephy
0
230
自分的「カンファレンスの楽しみ方」
Avatar for syumai syumai
0
200
アクセシビリティから考える情報設計
Avatar for high-g high_g_engineer
0
350
【高い買い物LT会】初任給で話題の国産フィジカルAIを買った話
Avatar for 赤神青空 akagami
PRO
0
130
{ Android | Kotlin } Gradle Plugin in 2026
Avatar for RyuNen344 ryunen344
1
300
Swift愛好会と私（ウホーイ） / Swift Fan Club and Uhooi
Avatar for uhooi uhooi
0
150
LL言語やWebフレームワークの PostgreSQL対応 〜DBの機能がユーザーに届くまで〜
Avatar for 武田 憲太郎 kentaroutakeda
0
150
AgentCore CLI で進化した AWS での AI エージェントの作り方 : 必要な機能を必要な時に
Avatar for Takahiro Kubo icoxfog417
PRO
2
270
デプロイ直後のレイテンシスパイクを調べたら、 Railsの仕様にたどり着いた
Avatar for naohisa nhsykym
0
110

Featured

See All Featured
How To Speak Unicorn (iThemes Webinar)
Avatar for Michelle Schulp Hunt marktimemedia
1
570
GraphQLとの向き合い方2022年版
Avatar for Yosuke Kurami quramy
50
15k
HU Berlin: Industrial-Strength Natural Language Processing with spaCy and Prodigy
Avatar for Ines Montani inesmontani
PRO
0
690
Put a Button on it: Removing Barriers to Going Fast.
Avatar for kastner kastner
60
4.6k
Mobile First: as difficult as doing things right
Avatar for Swwweet swwweet
225
10k
What's in a price? How to price your products and services
Avatar for Michael Herold michaelherold
247
13k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
Avatar for Irina Nazarova irinanazarova
9
1.5k
Getting science done with accelerated Python computing platforms
Avatar for Jacob Tomlinson jacobtomlinson
2
470
We Analyzed 250 Million AI Search Results: Here's What I Found
Avatar for Josh Blyskal joshbly
1
1.9k
Breaking role norms: Why Content Design is so much more than writing copy - Taylor Woolridge
Avatar for UX Y'all uxyall
1
400
Efficient Content Optimization with Google Search Console & Apps Script
Avatar for Katarina Dahlin katarinadahlin
PRO
1
840
StorybookのUI Testing Handbookを読んだ
Avatar for Shingo Yamazaki zakiyama
31
6.9k

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が一級オブジェクトになったのは また別のお話……