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
9.3k
末尾呼び出し最適化と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
Media over QUICとRTMP+HLSの比較
kota_yata
1
530
2023年秋 中村研 WIP発表資料
kota_yata
0
34
2023年春 中澤大越研 WIP発表資料
kota_yata
0
21
BigIntの良いとこ悪いとこ
kota_yata
0
36
Catenaryの技術のこと
kota_yata
0
390
年越しアイデンティティ
kota_yata
0
360
Principle of SSI
kota_yata
0
430
What are the interns at Code for Japan doing?
kota_yata
0
380
Other Decks in Programming
See All in Programming
意外とフォントが大事だった話 / Font Issues on Internationalization
fumi23
0
100
How to Break into Reading Open Source
kaspth
1
190
Jakarta EE meets AI
ivargrimstad
0
360
Rustではじめる負荷試験
skanehira
5
1.2k
Understand the mechanism! Let's do screenshots tests of Compose Previews with various variations / 仕組みから理解する!Composeプレビューを様々なバリエーションでスクリーンショットテストしよう
sumio
3
480
令和トラベルにおけるLLM活用事例:社内ツール開発から得た学びと実践
ippo012
0
120
労務ドメインを快適に開発する方法 / How to Comfortably Develop in the Labor Domain
yuki21
1
250
null or undefined
susisu
22
6.2k
Go1.23で入った errorsパッケージの小さなアプデ
kuro_kurorrr
2
330
The Sequel to a Dream of Ruby Parser's Grammar
ydah
1
220
月間4.5億回再生を超える大規模サービス TVer iOSアプリのリアーキテクチャ戦略 - iOSDC2024
techtver
PRO
1
790
GraphQLの魅力を引き出すAndroidクライアント実装
morux2
3
320
Featured
See All Featured
How GitHub (no longer) Works
holman
310
140k
[RailsConf 2023] Rails as a piece of cake
palkan
48
4.6k
The Mythical Team-Month
searls
218
43k
Why Our Code Smells
bkeepers
PRO
334
56k
Art, The Web, and Tiny UX
lynnandtonic
294
20k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
166
48k
What's in a price? How to price your products and services
michaelherold
242
11k
The Cult of Friendly URLs
andyhume
76
6k
A Tale of Four Properties
chriscoyier
155
22k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
24
600
Clear Off the Table
cherdarchuk
91
320k
RailsConf 2023
tenderlove
28
800
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