Beautiful ideas in programming: generators and continuations
hhyu.org
hhyu.org
If you are used to call backs, promises, tick() calls or closures, it will be natural to reach for them a lot, and be disappointed at their state in the Python ecosystem.
But while I do miss better anonymous functions support sometimes in Python, it is rarely a problem because it comes with other tools to arrive to the same result.
Generators are one of them. Of course, you'll have to realize that generators are way more that a lazy way of generating data. You can use them for control flow, hold state, hide complexity or delegate behavior using a common interface. The send() method is very often completely ignored by most devs, and the yield from underused.
But beyond generators are a lot more things that, in the same vein, will bring you to python enlightenment once you start thinking with them instead of trying to make a Python fits into a square hole:
- the functools module
- the itertools module
- context managers
- any/all/zip/iter/next/enumerate
- decorators (it can do so much more than you imagine)
- type hints (take a look at fast api for awesomeness)
It's a real disappointment that Python has no answer for JavaScript fat arrow.
The fat arrow is the one construct that completely changes the structure of all the programs I write - it makes things extremely terse and I use it in nearly every function/method in some way.
I'm a big fan of Python's whitespace structure but it seems to be an obstacle to creating single line functions that are both powerful and get multiple things done, which sometimes makes a program easier to read and more understandable. Sure there's lambda functions but I find them clumsy and hard to work with compared to the beauty of the fat arrow.
But I also know by experience that people from other languages are reaching for anonymous functions way too often instead of using the tools that are suitable for the use case in python.
E.G: if you use a lot of map() and filter() in python, you are doing it wrong.
Maybe - but at the same time, generators are side-effectful and quite general. That means, when someone uses a generator, now I have to understand what happens by looking at the code. If someone uses a promise or a closure/lambda, then the scope of what can happen is much more limited.
It's like looping vs. mapping. You can use "for ... in ..." syntax or you can do "map(..., ...)" but I generally prefer the latter (minus the syntax overhead in python), simply because I easily see at a glance what the intend is.
In languages without generators it's easy to write code that traverses some data structure in hard-coded way and does something configurable on every node, but it's hard to write code that traverses a data structure in configurable way and does some hardcoded thing on every element.
In Python it's trivial both ways and even both at once.
Wouldn’t this just be a function that operates on an iterator? I suppose generators make the creation of lazy iterators easier, but generally the solution for languages without generators is to have your traversal build a list. So you lose the laziness but the code remains simple. Then map your per-node processing to the list.
Yes, but then you move from O(1) to O(n) in memory usage. And if you want to optimize it you have to restructure your code, when in python lists and generators are drop-in replacements.
Which other languages? Generator support is common:
https://en.m.wikipedia.org/wiki/Generator_(computer_programm...
Certainly in Java you can use the `Iterator` interface to get generator like behavior. But that's both a whole lot more complex and more verbose. Primarily because you have to coordinate the `hasNext` method with the `next` method.
With python and yield syntax, that naturally falls out without a bunch of extra code juggling.
Although some generator implementations are not as complete as python ones, and the ecosystem generally donc have much support for it
E.g : Very few languages have an equivalent to itertools.
def print_every_file_in(root_path):
for path in children(root_path):
if is_file(path):
print("file: " + path + ", size:" + get_size(path))
else:
print_every_file_in(root_path)
def print_file(path):
print("file: " + path + ", size:" + get_size(path))
def print_every_file_in(root_path):
for path in children(root_path):
if is_file(path):
print_file(path)
else:
print_every_file_in(path)
But in Python it's equally trivial to extract the traversal:
def every_file_in_path(root_path):
for path in children(root_path):
if is_file(path):
yield path
else:
yield from every_file_in_path(path)
def print_every_file_in(root_path):
for file in every_file_in_path(root_path):
print("file: " + path + ", size:" + get_size(path))
def print_every_file_in(root_path):
for file in every_file_in_path(root_path):
print_file(file)
needing to store state - use a class
needing lazy evalutaion - use a class (though this is a common enough use case to be a primitive, e.g. Kotlin)
decorators - if you pass decorated methods around -> now you have to remember the context the methods hold. Instead, refactor your code to be more direct so that you don't need decorators.
type hints - they are not fully enforceable at compile time, unless everything in your codebase has type hints. This is never the case and type hints can easily lull you into a false sense of security.
functools module - generally I'm ok with this but sonetimes you have to be aware of when you need to deep copy vs when you don't etc.
static IEnumerable<int> Fibonacci()
{
int first = 0;
int second = 1;
yield return first;
yield return second;
while (true)
{
(first, second) = (second, second + first);
yield return second;
}
} def _combined(args):
return decorator(args) and original(args)
* Granted not really used for general-purpose programming like Python.
[0]:https://www.gnu.org/software/emacs/manual/html_node/elisp/Ad...
edit, sorry I've meant generators. Incidentally, it's also true for js decorators.
>>> def count_binary():
... yield "1"
... for prefix in count_binary():
... yield prefix + "0"
... yield prefix + "1"
...
>>> cb = count_binary()
>>> next(cb)
'1'
>>> next(cb)
'10'
>>> next(cb)
'11'
>>> next(cb)
'101'
Monadic reflection can be implemented with continuations. Effects, specifically effect handlers, can be implemented with delimited continuations which weren't mentioned in this article. Delimited continuations and undelimited continuations can implement each other. Both undelimited continuations and delimited continuations can be implemented as a monad.
The main issue with all of this and why effects exist and why monads and delimited continuations aren't enough has to do with the fact that delimited continuations can't be easily type checked and monads aren't open for extension.
I did not like that undelimited continuations were not mentioned. They are so much easier to understand than call/cc continuations as they are the rectification of some segment of the return stack as a function which when called returns through that segment and then to the caller like a regular function.
call/cc continuations are undelimited continuations right? It sounds like you're talking about call/ec, escape continuations or one-shot continuations. They're essentially longjmp in C.
All of call/cc, call/ec, call/1cc are effectively jumps to a saved stack. (The difference between these is that the first can be used more than once and both to enter and exit. The second can only be used to exit. The third can only be used once.)
shift is instead captures the return stack up to the first reset and forms a function out of it that when called runs the rest of each of the frames before returning to the caller of that created function.
I think you mean delimited continuations? "Undelimited continuations" is call/cc.
you can also google "oliver danvy delimited continuations" or "felleisen delimited continuations"
The first time my procedure "fork" returned twice, it took me a while to wrap my head around it. I don't see why you couldn't implement continuations in modern Free Pascal/Lazarus, all you really have to do is make a copy of the stack(using the heap), then adjust BP and SP, everything else on the stack is relative to those two registers.
I've hard a hard time using continuations in languages with not-total capture. Ada has package variables (similar to singleton without the headache) that are not captured by call/cc libraries... There's also the secondary stack (specific to GNAT, not sure) for functions that return objects of unknown size at call site, which also are a pain to capture/restore... Good luck with those.
I think continuations, to be really footgun-less, need to be integrated in the language & runtime, so that when you need to serialize the current state you can 'capture all the things'. A bit like python with its generator/automaton approach.
[0] http://www.xmailserver.org/libpcl.html
[1] http://www.devdoc.net/c/boost-1.65.1/libs/context/doc/html/c...
Easy-to-understand but nonsystematic counterexample: what happens when the stack contains a pointer to dynamically allocated memory? If you shallow copy it, you have a double free. If you deep copy it, how? Do you even know how much memory to allocate? What if it's a file descriptor instead?
(Fork only works because the OS can blindly duplicate the entire process and everything in it, and even then you have problems like IO buffers.)
You have to make certain assumptions about the nature of the program as compiled, if those assumptions are wrong, poof!
It seemed to me that beside niche fp or implementation of async, kanren,etc people rarely used them.
Not criticizing the concept just trying to assess the real world usage.
Otherwise, you may find yourself having to implement break, continue, and return using the exception system in your implementing language, and that can end up being either aesthetically unpleasing or downright messy (I painted myself into a corner once writing an evaluation engine in Go and, to meet a deadline, implemented break using panic and recover!).
In particular, in Common Lisp, restarts are only valid in the dynamic environment where they were created by restart-bind. In contrast, call/cc captures this dynamic environment and makes it available later. You can't store restarts and invoke them later the way you can with call/cc.
You simply cannot create a stack trace from within a C++ exception handler because that state is gone. Hence my argument that exceptions are not a continuation, there is nothing to continue.
try{
foo()
}catch(Exception e){
bar(e)
}
void foo() {
throw new exception();
}
(bar (call/cc foo))
(defun foo (cont)
(cont (make-exception))
The major difference is that continuations allow you to do this:
(defparam *global*)
(defparam *shadow-list* (list))
(defun foo (cont)
(setf *global* cont))
(with-open-file (f "~/file.log")
(loop
for line = (read-line stream nil 'eof)
until (eq line 'eof)
collect (cons line (call/cc foo)))
(*global* *shadow-list*)
(*global* *shadow-list*) ;; what is the state of the file here? what if there was an exception reading from the file?
To be fair, it's probably relatively easy to use dynamic-wind to raise some runtime error when trying to resume the continuation after the original context "ended".
Pitman's comments on this are in http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuat..., Sitaram's response is at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.3..., and Pitman's final response is at http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuat....
Disclaimer: I have never written a line of Go in my life.
https://www.cs.cornell.edu/people/egs/papers/trickles-tocs.p... https://thelackthereof.org/docs/library/cs/continuations.pdf
> I skipped the entire chapter because I couldn’t understand what continuations were good for.
I found that was the case when first learning other concepts in programming. It's not until you experience working on bigger projects where you find some tools become useful, and examples in the books are sometimes to concise to express their true power.
I don't think that is what concurrently means. Generators allow interleaved execution or lazy evaluation. In fact the author makes this point further down so I think the above sentence was just a slip of the pen. But I point it out because that very misunderstanding is one that tripped me up for a time.
> More accurately, yield in a function creates a generator, which suspends its execution at the point where yield appears in the definition.
That's better.
Given that concurrency is often implemented with a state machine, the difference is not what happens at run time. The difference is the programming model used.
Parallel execution is a fully separate matter.
But let me ask another question: What's the difference between yielding from a function and returning? Why is yielding considered concurrent programming and returning sequential?
I guess I had associated concurrent programming with threads but maybe multi-threaded programming is better called parallel execution?
Brainfuck probably has the simplest model I can think of - you have an instruction pointer referring to the next byte in the program to execute, and a flat array of memory cells that program instructions may read and write. Every command in the language is about working with those two elements.
C has a much more complex model consisting of statements that are stepped through, functions that may be called (including recursively) with parameters, local variables, global variables, static local variables, constness vs mutability, pointer types, names for symbolic access to those things... And probably a lot more that I've neglected.
Concurrency is a thing that might be part of a programming model where you are allowed to interleave execution of multiple logical workflows but still write each logical workflow as a single unit of code. The programming model model tells you what properties you are guaranteed to get.
An execution model is something that describes implementation of a programming model. A related example is how concurrency is implemented in a particular system. Is it multiple threads running simultaneously? Is it a complex state machine jumping between logical workflows as demanded by their semantics? Is it an even-more-complex m:n model involving both threads and state machines?
Execution models aren't irrelevant to programming. They can have a significant impact on performance and edge-case behavior that the programming model doesn't clearly specify. But you should be able to write programs with only the programming model in mind and get correct code in most circumstances. (I'd call it a specification failure if you can't.)
A programming model describes the tools the programmers have available, their semantics and interactions. An execution model describes how those things run on the hardware that is present.
In contrast, parallel programming usually refers to program flows where multiple instruction streams can be interleaved arbitrarily without changing the final result. For example, when using mapping a pure function on a list, the execution of the function for each element of the list can be executed in parallel without any concurrency.
Alternatively, parallel execution can refer to any case where multiple instruction streams are actually executed in parallel, regardless of their order.
Concurrency often has pitfalls even with single-threaded execution models. For example, if two generators share some common state, even if they are executed in a single thread, the final result depends on how they are used and may be unexpected.
https://blog.golang.org/waza-talk
A good talk that expresses the current sentiment and helped establish it. Concurrency may be parallel, but doesn’t need to be. This does go against the common (outside programming) notion of the meaning of concurrent which means it provides a strong potential for confusion.
If you have multiple contexts, logically separable, and they can execute independently you end up with some form of concurrent design.
The reason people often think of coroutines (like generators resuming) vs routines (functions) as concurrent vs not concurrent has everything to do with contexts that can be thought of as executing in a non-deterministic order. Certainly there might be external dependencies that "force" an ordering to execution, but at the end of the day, it's the independence of an operation/computation that makes it concurrent with another.
Concurrency can give rise to opportunities for things to execute in parallel, but it does not require them. Parallelism is therefore a condition of execution/evaluation.
On a uniprocessor unix kernel, processes execute concurrently. On a multiproccessor unix kernel, you hope for parallel execution of processes (though they may be totally unrelated in context or goal), but you always maintain the concurrency. The scheduler pauses and switches contexts.
The ability to switch contexts seems fairly equivalent to concurrency. And I don't think much else is needed.
I'm not sure that's 100% correct, but it's how I like to think of this situation.
For the record, the quoted explanation you disagree with fits Esterel and other data-flow languages perfectly, and nobody will deny that they are (synchronous) concurrent languages.
But it sounds like from the replies I was wrong.
To make it a little cleaner, I've replaced the "receiver" definition with a function reference instead. What's the continuation here?
(define sum-of-squares
(lambda (bound)
(call/cc the-receiver)))In a little more detail, let's take a function that looks like this; I'll use the shorter syntax to avoid line noise:
(define (sum-of-squares bound)
0)
(print (sum-of-squares 100)) ;; prints "0"
(define (sum-of-squares bound)
(call/cc the-receiver)) ;; will return whatever is passed to current continuation
;; for now, it will jump to the receiver, passing the whole call stack to it
(define (the-receiver cont)
(cont 18))
(sum-of-squares 100) ;; will start executing sum-of-squares, then jump to the-receiver, passing it the call stack
;; then, the-receiver will jump back into sum-of-squares, replacing the value of the whole `call/cc` form with the value 18
;; which will be returned to the top level
def sum_of_squares(bound):
try:
the_receiver()
except MyContinuation as e:
return e.Value
def the_receiver():
raise MyContinuation(18)
(define some-continuation '())
(define (sum-of-squares bound)
(call/cc the-receiver)) ;; will return whatever is passed to current continuation
;; for now, it will jump to the receiver, passing the whole call stack to it
(define (the-receiver cont)
(set! some-continuation cont)) ;; the receiver stores the value of cont into some-continuation and returns control to the top level.
;; at this point, sum-of-squares and anything that was calling it has NOT finished executing:
;; it's frozen in the continuation
(display (sum-of-squares 100)) ;;sets some-continuation to the continuation, doesn't print anything
(some-continuation 18) ;; prints 18
(some-continuation 200) ;; prints 200
(display (+ 100 (sum-of-squares 100))) ;;sets some-continuation to a new vale, doesn't print anything
(some-continuation 18) ;; prints 118
(some-continuation 200) ;; prints 300call/cc is used to allow some form control and allow the loop to exit
> Before the sum-of-square function does anything, I use call/cc to capture the continuation, and assign it to the variable break. Notice that in the syntax of Scheme, this is the last step of the function. Therefore, calling break will immediately exist the function with a returned value, no matter where it is called.
(display "Done with looping")
> Using yield in a function definition is not the only way in which generators can be constructed in Python
Anyone can point out what do they mean by that? Googling didn’t help much.