Bartosz Milewski - Replacing functions with data
Вставка
- Опубліковано 16 лип 2024
- Bartosz Milewski
Bartosz has a Ph D in theoretical physics but his interests led him to study programming, computer science, and mathematics. His blog posts cover wide areas of C++, Haskell, and category theory. His lectures on concurrent programming, Haskell, and category theory are available on UA-cam.
Replacing functions with data
In functional programming, functions are first-class citizens. This is due to the adjunction between the product and the exponential. It’s little known that, when you relax this adjunction, you can replace some functions with data in the process called defunctionalization. I’ll show you how to defunctionalize tree traversal in Haskell.
haskell.love
/ _haskellove - Наука та технологія
There is no one better than Bartosz for explaining FP and CT.
That is such a revelation at the end that after talking about Continuation Passing Style programming, functors, morphisms, sum types and product types, what we ended up with is just the good old humble stack.
The stack is a continuation, so it's no mystery that in the process of defunctionalizing cps we end up with it. It's just that macho industrial languages typically don't provide means of reflecting it to the user as a first class value, ie. call/cc and other operators and so its nature remains mystified in the mind of a typical programmer.
Pure gold! Recursion, tail recursion optimization, closure, CPS, adjunction, comma category all the important concepts are covered here including the solution to the interview question :-)
Defunctionalization is one of the ideas that permeates Essentials of Programming Languages, 3rd Edition (pg 41). Also, chapter 5 covers writing continuation passing interpreters and chapter 6 covers CPS. I liked learning more about the categorical aspects of it as well. Great talk as usual from Bartosz.
Why doesn't anyone talk about Lisp quote and (getsource 'funcname)
That feeling when everything makes sense at the end of the talk...
In a typical stack frame in a typical imperative language (e.g. C) you have arguments, local variables and the return address.
If I understood Bartosz's trick correctly, basically it moves the stack of arguments onto the heap. Depending on the particular function, this may either get rid of the need for local variables, or they can go on the heap as well. This makes the need for the return address go away, leaving the stack frame effectively empty and thus unnecessary.
TL;DR: store the stack in the heap, implicitly embedding the program counter in the choice of sum type variant.
Great talk 👍👍👍
Looks like a couple more steps and we'll get recursion schemes. Without explicit calls between apply and show4.
minute 16:20
I think show3 is not tail recursive, at least it is not 'only' tail recursive,
It is also indirectly recursive by 'next' and while the call to show3 in next is tail recursive on 'next', the call of 'next' is not tail recursive on 'show3'... so.... is this still going in stack overflow? if not, I the why is not obvious from the talk... at least for me.
Richie Blackmore seems to really know how stuff