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
JSExperience 7masters - Recursion & Trampolines
Search
Ana Luiza Portello
July 05, 2018
Programming
1
370
JSExperience 7masters - Recursion & Trampolines
Ana Luiza Portello
July 05, 2018
Tweet
Share
More Decks by Ana Luiza Portello
See All by Ana Luiza Portello
FRONTIN | Elas Programam - Programação Funcional no Front-end
anabastos
0
93
Workshop JSFP - SEMCOMP 2021
anabastos
0
270
Clojure é um Java melhor que Java - Codecon 2021
anabastos
0
150
Clojure 101 - Criciuma Dev
anabastos
0
320
TDC POA - GraphQL
anabastos
1
260
TDC Porto Alegre 2019 - JS Funcional com Ramda
anabastos
0
240
BackEndSP - GraphQL
anabastos
0
230
Git & Github - RLadies
anabastos
1
240
Programaria Summit - Performance FrontEnd
anabastos
1
220
Other Decks in Programming
See All in Programming
未来を拓くAI技術〜エージェント開発とAI駆動開発〜
leveragestech
2
200
コンテキストエンジニアリング Cursor編
kinopeee
1
740
20250808_AIAgent勉強会_ClaudeCodeデータ分析の実運用〜競馬を題材に回収率100%の先を目指すメソッドとは〜
kkakeru
0
220
AI時代に学習する意味はあるのか?
tomoyakamaji
0
110
AIを活用し、今後に備えるための技術知識 / Basic Knowledge to Utilize AI
kishida
17
3.6k
パッケージ設計の黒魔術/Kyoto.go#63
lufia
3
390
Kiroの仕様駆動開発から見えてきたAIコーディングとの正しい付き合い方
clshinji
1
180
Vue・React マルチプロダクト開発を支える Vite
andpad
0
110
TROCCO×dbtで実現する人にもAIにもやさしいデータ基盤
nealle
0
390
Azure SRE Agentで運用は楽になるのか?
kkamegawa
0
970
The state patternの実践 個人開発で培ったpractice集
miyanokomiya
0
160
AIコーディングAgentとの向き合い方
eycjur
0
250
Featured
See All Featured
Intergalactic Javascript Robots from Outer Space
tanoku
272
27k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
110
20k
The Invisible Side of Design
smashingmag
301
51k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
Java REST API Framework Comparison - PWX 2021
mraible
33
8.8k
A Tale of Four Properties
chriscoyier
160
23k
Imperfection Machines: The Place of Print at Facebook
scottboms
268
13k
Making Projects Easy
brettharned
117
6.4k
Being A Developer After 40
akosma
90
590k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
139
34k
The Cost Of JavaScript in 2023
addyosmani
53
8.9k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3k
Transcript
ANA LUIZA BASTOS github.com/anabastos @naluhh @anapbastos Fullstack Developer na Quanto
e cientista da computação na PUC-SP anabastos.me
JSLADIES fb.com/jsladiesbr twitter.com/jsladiessp meetup.com/JsLadies-BR/ LAMBDA.IO t.me/lambdastudygroup github.com/lambda-study-group/ meetup.com/Lambda-I-O-Sampa- Meetup/
VISÃO GERAL SOBRE RECURSÃO & TRAMPOLINES
VAMOS FALAR SOBRE RECURSÃO
Recursão é quando uma função chama a si mesma até
uma condição parar o loop.
λ Programação Funcional
Fatorial 1! = 1 3! = 1 * 2 *
3 = 6
const iterativeFactorial = (n) => { let i let contador
= 0 for (i = 1; i <= n; i++) { contador *= i } return contador }
1. Qual parte do código é recursiva 2. Condição de
saída
const fac = (n) => { if (n == 0)
{ return 1 } return n * fac(n - 1) }
• EXPRESSIVO • PURO / EVITANDO MUDANÇA DE ESTADO(CONTADOR) •
IMUTABILIDADE DE DADOS • DECLARATIVO • IDEMPOTENCIA
JS é single threaded e orientado a stack
None
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC call call call call
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC 1 1* 1 = 1 1 * 2 = 2 2 * 3 = 6
GC fac(9999) GC fac(9998) fac(9999) GC fac(9997) fac(9998) fac(9999) GC
oh no ... fac(9998) fac(9999) GC StackOverFlow :(
Cruza os dedos? Senta e chora?
TAIL CALL OPTIMIZATION (TCO)
Truque antigo
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC call call call call
TCO faz com que a gente evite explodir o stack
quando fazemos chamadas recursivas
PROPER TAIL CALLS (PTC)
Possibilita que sua função recursiva seja otimizada pela engine.
RECURSÃO EM CAUDA (TAIL CALL)
//Não é tail call :( const fac = (n) =>
n == 0 ? 1 : n * fac(n - 1)
A última coisa a ser feita na função é o
retorno da própria função.
Acumulador
const tailRecursiveFac = (n, acc = 1) => { return
n == 0 ? acc : tailRecursiveFac(n - 1, acc * n) }
ES6 http://www.ecma-international.org/ecma-262/6.0/#sec-tail-position- calls
None
Além disso existem casos de algoritmos que precisam de mais
de duas chamadas recursivas(multiple recursion) e não tem como colocar tudo no final
COMO LIDAR COM ISSO?
CONTINUATION PASSING STYLE (CPS)
Um estilo de programação em que o controle é passado
explicitamente em forma de continuação
Continuação é uma parte de código que ainda vai ser
executada em algum ponto do programa Callbacks por exemplo são continuations
Continuação não chama a si mesma, ela só expressa um
fluxo de computação onde os resultados fluem em uma direção. Aplicar continuações não é chamar funções é passar o controle do resultado.
LAZY EVALUATION
CALL-BY-NEED
> (1 + 3) * 2 8 > const expression
= () => (1 + 3) * 2 > expression() 8
Ou seja, o programa espera receber os dados antes de
continuar.
E daí?
CPS elimina a necessidade de um call stack pois os
valores estarão dentro da continuation sendo executada .
Acumulador para uma continuação
IDENTITY FUNCTION
const id = x => x
• O último parâmetro da função é sempre a continuation.
• Todas as funções precisam acabar chamando sua continuação com o resultado da execução da função.
const cpsFac = (n, con) => { return n ==
0 ? con(1) : cpsFac(n - 1, y => con(n + y)) } cpsFac(3, id) //6
TRAMPOLINES
Técnica stack safe para fazer chamadas tail-recursive em linguagens orientadas
a stack
Um trampoline é um loop que iterativamente invoca funções que
retornam thunks (continuation-passing style)
THUNKS
Função que encapsula outra função com os parâmetros que para
quando a execução dessa função for necessária.
function thunk(fn, args) { return fn(...args) }
Ao invés de chamar a tail call diretamente, cada método
retorna a chamada para um thunk para o trampolim chamar.
const trampoline = (thunk) => { while(thunk instanceof Function){ thunk
= thunk() } return thunk }
• É um loop que chama funções repetidamente • Cada
função é chamada de thunk. • O trampolim nunca chama mais de um thunk • É como se quebrasse o programa em pequenos thunks que saltam pra fora do trampolim, assim o stack não cresce.
const trampolineFac = (n) { const fac = (n, ac
= 1) => { return n == 0 ? ac : thunk(fac, n - 1, ac * n) } return trampoline(thunk(fac, n, 1)) }
GC fac(3) GC call GC fac(2) GC GC bounce bounce
:(
Trade off por stack safety Trocamos o trabalho de criar
stack frames com o de criar binding de funções.
Em muitos casos o trade-off de overhead por expressividade vale
a pena
Trampolines são mais apropriadas para funções complexas em que não
existem soluções iterativas e não conflitam com outras técnicas de mediar controle de fluxo(Promises).
• Kyle Simpson. Functional Light Programming. Cap 8. - github.com/getify/Functional-Light-JS
• Functional Programming Jargon - github.com/hemanth/functional-programming-jarg on • Structure and Interpretation of Computer Programs - Javascript Adaptation
• Compatibilidade TCO - kangax.github.io/compat-table/es6/#test-proper_tail_c alls_ • Yoyojs - npmjs.com/package/yoyojs
• Ramda Memoisation - ramdajs.com/docs/#memoize
t.me/lambdastudygroup github.com/lambda-study-group
OBRIGADA :) https://speakerdeck.com/anabastos