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
末尾呼び出し最適化とJavaScript
Search
kota-yata
April 23, 2021
Programming
12
11k
末尾呼び出し最適化とJavaScript
著者情報 : kota-yata.com
プレゼン動画 :
https://www.youtube.com/watch?v=BcaPCnWZuvY
kota-yata
April 23, 2021
Tweet
Share
More Decks by kota-yata
See All by kota-yata
パタヘネ輪読: 第一章
kota_yata
0
53
2023年秋 中村研 WIP発表資料
kota_yata
0
67
2023年春 中澤大越研 WIP発表資料
kota_yata
0
40
BigIntの良いとこ悪いとこ
kota_yata
0
67
Catenaryの技術のこと
kota_yata
0
400
年越しアイデンティティ
kota_yata
0
380
Principle of SSI
kota_yata
0
460
What are the interns at Code for Japan doing?
kota_yata
0
390
Other Decks in Programming
See All in Programming
AtCoder Heuristic First-step Vol.1 講義スライド
terryu16
2
1k
MCP世界への招待: AIエンジニアが創る次世代エージェント連携の世界
gunta
2
560
eBPF Updates (March 2025)
kentatada
0
130
2025/3/18 サービスの成長で生じる幅広いパフォーマンスの問題を、 AIで手軽に解決する
shirahama_x
0
160
RailsでCQRS/ESをやってみたきづき
suzukimar
2
1.5k
爆速スッキリ! Rspack 移行の成果と道のり - Muddy Web #11
dora1998
1
150
安全に倒し切るリリースをするために:15年来レガシーシステムのフルリプレイス挑戦記
sakuraikotone
5
2.2k
Compose Navigation実装の見通しを良くする
hiroaki404
0
180
本当だってば!俺もTRICK 2022に入賞してたんだってば!
jinroq
0
240
リアクティブシステムの変遷から理解するalien-signals / Learning alien-signals from the evolution of reactive systems
yamanoku
2
960
英語文法から学ぶ、クリーンな設計の秘訣
newnomad
1
270
Devinのメモリ活用の学びを自社サービスにどう組み込むか?
itarutomy
0
1.7k
Featured
See All Featured
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
Reflections from 52 weeks, 52 projects
jeffersonlam
349
20k
VelocityConf: Rendering Performance Case Studies
addyosmani
328
24k
Optimising Largest Contentful Paint
csswizardry
35
3.2k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Gamification - CAS2011
davidbonilla
81
5.2k
Git: the NoSQL Database
bkeepers
PRO
429
65k
[RailsConf 2023] Rails as a piece of cake
palkan
53
5.4k
Facilitating Awesome Meetings
lara
53
6.3k
Thoughts on Productivity
jonyablonski
69
4.5k
The World Runs on Bad Software
bkeepers
PRO
67
11k
Transcript
末尾呼び出し最適化とJavaScript 2021/04/23 - @kota_yata
おれ Kota Yatagai (@kota_yata) 趣味でフロントエンド開発をしてます 暗号系結構好きです ブロックチェーンの勉強はじめました Svelte / Nuxt
2021/04/23 - @kota_yata
今⽇のはなし 再帰関数の最適化を⾏う「末尾呼び出し最適化」の説明をして、今のJavaScript環境での実装 状況とかの話もします。 2021/04/23 - @kota_yata
末尾呼び出しってなに? Tail Call 関数の末尾に返り値として関数を呼び出している関数 その中で⾃分⾃⾝を返り値として呼び出している=末尾で再帰している関数を末尾再帰関数と いう // 階乗を求める末尾再帰関数の例 const factorial
= (number, result) => { if (number === 0) return result; return factorial(number - 1, result * number); } 2021/04/23 - @kota_yata
末尾呼び出し最適化ってなに? Tail Call Optimization(以下TCO) コンパイラなどの⾔語処理系で⾏う関数の最適化処理(速度改善の最適化ではない) 末尾呼び出し関数においてスタックフレームを使い回すことでメモリ使⽤量を抑える⼿法 末尾再帰関数の場合は実質的に末尾の再帰を除去、ループ処理に変換している ➡ 末尾呼び出 し除去(Tail
Call Elimination) TCOをすればスタックオーバーフローを起こさないことが保証される 2021/04/23 - @kota_yata
もう少し詳しく 末尾再帰関数(さっきの階乗の関数の例)の場合、スタックを追うと Trace at factorial (/Users/hoge/test.js:2:11) at factorial (/Users/hoge/test.js:4:10) at
factorial (/Users/hoge/test.js:4:10) at factorial (/Users/hgoe/test.js:4:10) 末尾で同じ処理を繰り返してなんらかの条件で処理を終了する... ループと同じでは? 実質的な処理はループと同じなので、機械的にループ⽂に変換することができる 逆に末尾再帰でない再帰関数を機械的にループ⽂に変換するのはかなり難しい 2021/04/23 - @kota_yata
TCOが実装されている⾔語 Kotlin Haskell Erlang Python...サードパーティーのライブラリで実装されている(baruchel/tco) Scala...末尾再帰の場合のみ(通常の末尾呼び出しでは最適化されない) ... JavaScriptさん?? 2021/04/23 -
@kota_yata
JavaScriptエンジンにおけるTCO 現在JavaScriptCoreエンジン(Safari)でのみ末尾最適化が実装されている ES6でTCOを⾏うように定められたがV8(Chrome), SpiderMonkey(Firefox)などの主要 ブラウザでは実装されていない なぜなのか。 2021/04/23 - @kota_yata
経緯 2011年頃 : TC39内で同意をとり、TCOの実装をES6に盛り込んだ 2015年 : ES6がリリース。この時点ではまだどのブラウザもTCOを実装していなかった 2016年初頭 : Safariが実装。ChromeはExperimental
Feature Flag(Origin Trials)として実 装した。ここでMozillaチームとMicrosoftチームが⽂句を⾔い始める 2021/04/23 - @kota_yata
Mozillaさんの主張 TCOがブラウザに実装された場合、特定の条件でのみ暗黙的にTCOが実⾏されることにな り、どの関数がTCOの対象なのかわかりにくくなるじゃないか。 つまり... 2021/04/23 - @kota_yata
TCOが適⽤される条件 その呼び出しが確実に最後の処理になる場合 ブロック直下での返り値 const hoge = () => { ...
return hoge() // 確実に最後の処理になるためTCO が適⽤される } 2021/04/23 - @kota_yata
TCOが適⽤される条件 その呼び出しが確実に最後の処理になる場合 if⽂の場合if内とelse内の両⽅ const hoge = () => { if
(...) { return hoge(); } else { return hoge(); } } どっちに転んでも hoge() が実⾏されるためTCOの対象 2021/04/23 - @kota_yata
TCOが適⽤される条件 その呼び出しが確実に最後の処理になる場合 try-catchの場合catch内 const hoge = () => { try
{ return hoge(); // この後にエラーハンドリングがあるのでTCO の対象外 } catch (err) { return hoge(); // このエラーハンドリングが最後の処理になるのでTCO の対象 } } などなどTCOが適⽤される条件は単純ではない 2021/04/23 - @kota_yata
Mozillaさんの主張 TCOがブラウザに実装された場合、特定の条件でのみ暗黙的にTCOが実⾏されることにな り、どの関数がTCOの対象なのかわかりにくくなるじゃないか。 つまり... 開発者がTCOされると思って実装した再帰関数が実はTCOの対象ではなく、スタックオーバ ーフローを起こすことが増えてしまう。TCOはされないと分かっていて実装するよりも危険 な状態である 他にもデバッグが難しくなるなどの問題点も指摘した(スタックトレース時にはすでにTCO されているため何も出⼒されない)。 2021/04/23
- @kota_yata
スタックオーバーフローが起こした事件 2013年、⽶国でトヨタ⾞が急加速する事故が多発。 原因はファームウェアの⽋陥 CPUでスタックオーバーフローを回避する処理がなされていなかった 死傷者が出たことや当初トヨタが⽋陥を隠蔽したこともあり、最終的に1100億円の賠償⾦を ⽀払って和解 2021/04/23 - @kota_yata
Microsoftさんの主張 WindowsABIとの兼ね合いで効率的に実装できません。 そうですか、頑張ってください。 2021/04/23 - @kota_yata
経緯 2011年頃 : TC39内で同意をとり、TCOの実装をES6に盛り込んだ 2015年 : ES6がリリース。この時点ではまだどのブラウザもTCOを実装していなかった 2016年初頭 : Safariが実装。ChromeはExperimental
Feature Flag(Origin Trials)として実 装した。ここでMozillaチームとMicrosoftチームが⽂句を⾔い始める 2016年中頃 : Mozillaの指摘を受けてChromeチームがSyntactic Tail Callsというプロポーザ ルを提出する 2021/04/23 - @kota_yata
Syntactic Tail Calls(以下STC) その関数をTCOの対象にするかどうか明⽰的に指定するような⽂法を盛り込んだプロポーザ ル const formalHoge = () =>
{ return formalHoge(); // TCO されない従来の書き⽅ } const syntacticHoge = () => { return continue syntacticHoge(); // STC で盛り込まれたcontinue を⽤いた明⽰的なTCO の指定 } こうすることで、開発者が主体的にTCO対象にするか否かを選択できる。 デバッグが容易になり、スタックオーバーフローも正しく回避できる。 最⾼じゃん! 2021/04/23 - @kota_yata
Safari 「ダメです」 2021/04/23 - @kota_yata
STCプロポーザルが提出された時点での⽴ち位置 Microsoft : TCOは実装すべきでない Mozilla : TCOは実装すべきでない。なんならTCOの仕様をES6から削除すべき Chrome : TCOの代替策としてSTCを提⽰した
Safari : TCOをES6の仕様通りに実装すべきである そもそもSTCとES6のTCO仕様は共存できない(明⽰的に指定するか暗黙的に対象にする か) その上でSafariは唯⼀TCOの実装を推し進めているブラウザだったため、STCを承諾するわけ には⾏かなかった。 Mozillaも反対し、結局STCのプロポーザルは承諾されなかった。 2021/04/23 - @kota_yata
そんなこんなで現状整理 Safari以外のブラウザはTCOを実装していない。STCは標準化されず。 Babelではv5までTCOが実装されていたがv6で消滅(最新版はv7) 2021年のJavaScript環境で末尾呼び出し最適化は諦めた⽅が良さそう... 2021/04/23 - @kota_yata
じゃあどうすれば... ⾃分で最適化しましょう。 const factorial = (number, result) => { if
(number === 0) return result; return factorial(number - 1, result * number); } // ⬇ ⾃分でwhile ⽂に書き直す const factorial = (number) => { let result = 1; let count = number; while(count > 0) { result *= count; count--; } return result; } // やってることはコンパイラが機械的に⾏っているTCO と同じ 2021/04/23 - @kota_yata
感想 でもやっぱり再帰の⽅がスマートに書けることは多いからTCO欲しい。 当時の議論からすでに5年近く経ってもSafariのTCOに関して開発者から⽂句が出ているわけ ではないということは、TCOを実装してもある程度うまく回るのではないかという感想で す。 TC39のIssues⾒ているとたまに「そろそろTCO再検討しても良いのでは?」みたいな提案も ⾒受けられるので、今後の動向に注⽬したい 2021/04/23 - @kota_yata
参考⽂献 https://tc39.es/proposal-ptc-syntax/ https://v8.dev/blog/modern-javascript https://stackoverflow.com/questions/54719548/tail-call-optimization-implementation-in-javascript-engines https://kangax.github.io/compat-table/es6/ https://stackoverflow.com/questions/25228871/how-to-understand-trampoline-in- javascript/27704484#27704484 http://js-next.hatenablog.com/entry/2016/01/28/232111 http://js-next.hatenablog.com/entry/2016/04/27/194215 https://2ality.com/2015/06/tail-call-optimization.html#checking-whether-a-function-call-is-in-a-tail-
position https://github.com/tc39/proposal-ptc-syntax https://github.com/tc39/proposal-ptc-syntax/issues/23 2021/04/23 - @kota_yata