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.9k
末尾呼び出し最適化と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
28
Media over QUICとRTMP+HLSの比較
kota_yata
1
700
2023年秋 中村研 WIP発表資料
kota_yata
0
41
2023年春 中澤大越研 WIP発表資料
kota_yata
0
23
BigIntの良いとこ悪いとこ
kota_yata
0
43
Catenaryの技術のこと
kota_yata
0
390
年越しアイデンティティ
kota_yata
0
360
Principle of SSI
kota_yata
0
440
What are the interns at Code for Japan doing?
kota_yata
0
380
Other Decks in Programming
See All in Programming
WebフロントエンドにおけるGraphQL(あるいはバックエンドのAPI)との向き合い方 / #241106_plk_frontend
izumin5210
4
1.4k
AWS Lambdaから始まった Serverlessの「熱」とキャリアパス / It started with AWS Lambda Serverless “fever” and career path
seike460
PRO
1
260
OSSで起業してもうすぐ10年 / Open Source Conference 2024 Shimane
furukawayasuto
0
110
エンジニアとして関わる要件と仕様(公開用)
murabayashi
0
290
ActiveSupport::Notifications supporting instrumentation of Rails apps with OpenTelemetry
ymtdzzz
1
230
Better Code Design in PHP
afilina
PRO
0
130
タクシーアプリ『GO』のリアルタイムデータ分析基盤における機械学習サービスの活用
mot_techtalk
4
1.4k
ピラミッド、アイスクリームコーン、SMURF: 自動テストの最適バランスを求めて / Pyramid Ice-Cream-Cone and SMURF
twada
PRO
10
1.3k
Macとオーディオ再生 2024/11/02
yusukeito
0
370
Streams APIとTCPフロー制御 / Web Streams API and TCP flow control
tasshi
2
350
CSC509 Lecture 13
javiergs
PRO
0
110
Figma Dev Modeで変わる!Flutterの開発体験
watanave
0
130
Featured
See All Featured
KATA
mclloyd
29
14k
Six Lessons from altMBA
skipperchong
27
3.5k
StorybookのUI Testing Handbookを読んだ
zakiyama
27
5.3k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
Into the Great Unknown - MozCon
thekraken
32
1.5k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
How to train your dragon (web standard)
notwaldorf
88
5.7k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Put a Button on it: Removing Barriers to Going Fast.
kastner
59
3.5k
Fireside Chat
paigeccino
34
3k
We Have a Design System, Now What?
morganepeng
50
7.2k
Music & Morning Musume
bryan
46
6.2k
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