POSTS

Happy Birthday Don Knuth

Happy Birthday

Don Knuth, author of The Art Of Computer Programming and creator of the TeX typesetting system is 83 today. Happy Birthday Don. Thank you for TeX and everything else.

You're warmly invited to join me online to celebrate Don's life and work. The virtual party is on Thursday 14 January, 6:30 to 7:30pm UK time. Here's the zoom details

TeX Office Hour

During the lockdown I'm holding a TeX Office Hour every Thursday evening, from 6:30 to 7:30pm UK time. All are welcome, particularly TeX beginners. Experts are also welcome. And for celebrating Don, any friend or fan of Don is welcome.

This celebration for Don Knuth is just one event in this series of TeX Office Hours. We all benefit when we share experience and understand each other better. Sometimes beginners ask the best questions, provide the best examples and problems.

The rest of this post celebrates a paper Don wrote in 1974. It's a bit technical. If you get to the end, I hope it's worth it for you.

Don Knuth and goto's

In 1974 Don wrote a major survey paper Structured Programming with goto statements. I'm going to share with you something from this paper. What I'm about to say might be unfamiliar, so bear with me while I make a gentle start.

Background

The goto is a powerful and easily abused program control flow statement. That said, there are cases where a goto statement can improve both performance and readability. (And by the way the switch – case statement in C is a sort of goto.)

I'll now pivot by suggesting that carefully chosen new program control flow statements can give the benefits of goto without the cost. For example, as in switch.

Merging binary trees

Don likes examples and problems. Here's one from his 1974 paper. Consider the problem of merging two sorted binary trees into one ordered sequence. Don wrote

A conceptually simple solution to this problem can be written with coroutines, or by forming an equivalent program that expresses the coroutine linkage in terms of goto statements.

He goes on to write:

It appears to be cumbersome (though not impossible) to do the job without using either feature [ie goto or coroutine].

By the way, Don gained this insight about coroutines as control structures from Christopher Strachey.

Async in Python

I've read Don's 1974 paper several times. I reread it again last year, because of a discussion about if – else on Python ideas. And suddenly I saw something I hadn't noticed before.

Python 3.4 introduced a new keywords async and await, which enabled a module that provided asynchronous I/O. Because I saw these keywords in a module I wanted to use, and because I knew that async I/O is a good idea (for high performance web servers), I wanted to understand what was going on.

And Python core developer Brett Cannon wrote this blog post that told me that new ideas were needed.

What really surprised me was that the new idea that really helped me understand what async and await in Don's 1974 paper. You see, it's all about coroutines. I could read the definition of coroutine, but I did have good examples. I couldn't see how it was useful.

Conclusion

Don's 1974 paper told me, in so many ways, was the coroutines were a systematic way of solving certain problems that otherwise would benefit from the use of the goto statement. And it gave me an explicit example that I could actually understand, namely the merging of sorted binary trees.

Finally, a suggestion. If you don't understand something, try to find a simple example. And at the beginning, the simpler the better (as long as it shows something).