Republishing Bartosz Milewski’s Category Theory lectures

Category Theory is an incredibly exciting and challenging area of Maths, that (among other things) can really help us understand what programming is on a fundamental level, and make us better programmers.

By far the best explanation of Category Theory that I have ever seen is a series of videos by Bartosz Milewski.

The videos on YouTube have quite a bit of background noise, and they were not available on PeerTube, so I asked for permission to edit and repost them, and Bartosz generously agreed! The conversation was in the comments section of Category Theory 1.1: Motivation and Philosophy and I reproduce it below.

So, I present these awesome videos, with background noise removed using Audacity, for your enjoyment:

Category Theory by Bartosz Milewski

Permission details:

Andy Balaam: Utterly brilliant lecture series.  Is it available under a free license?  I'd like to try and clean up audio and repost it to PeerTube, if that is permitted. Bartosz Milewski: You have my permission. I consider my lectures public domain.

Andy Balaam: Utterly brilliant lecture series. Is it available under a free license? I’d like to try and clean up audio and repost it to PeerTube, if that is permitted.
Bartosz Milewski: You have my permission. I consider my lectures public domain.

Shutdown order consistency: how Rust helps

Some Java code with bugs

Here’s my main method (in Java). Can you guess the bug?

Db db = new Db();
Monitoring monitoring = new Monitoring();
Monitoring mon2 = new Monitoring();
Billing billing = new Billing(db, monitoring);
monitoring.setDb(db);

runMainLoop(billing, mon2);

db.stop();
billing.stop();
monitoring.stop();

If you would like to hunt down the 2 bugs manually, try reading the full code here: ShutdownOrder.java

But maybe you have an idea already? Maybe you’ve seen code like this before? If you have, you probably have an instinct that there’s some kind of bug, even if you can’t say for sure what it is. Code like this almost always has bugs!

This code compiles fine, but it contains two bugs.

First, we forgot to setDb() on mon2. This causes a NullPointerException, because Monitoring expects always to have a working Db.

Second, and in general harder to spot, we shut down our services in the wrong order. It turns out that Monitoring uses its Db during shutdown, so we get an exception. Even worse, if some other code needed to run after monitoring.stop(), it won’t, because the exception prevents us getting any further.

Of course, this is toy code, but this kind of problem is common (and much harder to spot) in real-life code. In fact, my team dealt with a similar bug this week.

It’s fundamentally hard to figure out your shutdown order. It’s complicated further if classes have start() methods too, which I have seen in lots of Java code.

Given that this is just a hard problem, maybe there’s no point looking for tools to make it easier?

Some Rust code without those bugs

Let’s try writing this code in Rust. Here’s the main method:

let db = Db::new();
let monitoring = Monitoring::new(&db);
let mon2 = Monitoring::new(&db);
let billing = Billing::new(&db, &monitoring);

run_main_loop(&billing, &mon2);

// drop() is called automatically on all objects here

Here’s the full code: shutdown_order.rs

This code shuts down all the services automatically at the end, and any mistakes we make in the order are compile errors, not things we find later when our code is running.

The code to shut down each service looks like this:

impl Drop for Monitoring<'_> {
    fn drop(&mut self) {
        // [Disconnect from monitoring API]
        self.db.add_record("MonitorShutDown");
    }
}

This is us implementing the Drop trait for the struct Monitoring (traits are a bit like Java Interfaces). The Drop trait is special: it indicates what to do when an instance of this struct is dropped. In Rust, this is guaranteed to happen when the instance goes out of scope, which is why our comment at the end of the main method sounds so confident.

Furthermore, Rust’s compiler shuts down everything in the reverse order in which it was created, and guarantees that nothing gets used after it has been dropped.

Rust’s lovely world gives us two relevant treats: no unexpected nulls, and lifetimes.

Treat number 1: no unexpected nulls

First, in Rust, like in other modern languages like Kotlin, we have to be explicit about items that could be missing. In our example, we were able to re-arrange the code so that db can never be missing (or null), and the compiler encouraged us to do so. If we really needed it to be missing some of the time, we could have used the Option type, and the compiler would have forced us to handle the case when it was missing, instead of unexpectedly getting a NullPointerException like we did in Java. (In fact, if we’d structured our code to use final in as many places as possible, we could have been encouraged towards basically the same solution in Java too.)

Treat number 2: lifetimes

Second, if you look a bit more closely at the full code of shutdown_order.rs you’ll see lots of confusing-looking annotations like <'a> and &'a:

struct Monitoring<'a> {
    db: &'a Db,
}

The approximate meaning of those annotations is: a Monitoring holds a reference to a Db, and that Db must last longer than the Monitoring.

This “lasts longer than” wording is what Rust Lifetimes are for. Lifetimes are a way of saying how long something lasts.

Lifetimes are really confusing when you start with Rust, and have caused me a lot of pain. Code like this is where they are both most painful and most helpful. As I mentioned earlier, the problem of shutdown order is fundamentally hard. Rust gives you that pain at the beginning, and until you understand what’s going on, the pain is very confusing and acute. But, once your code compiles, it is correct, at least as far as problems like this are concerned.

I love the sense of security it gives me to write Rust code and know the compiler has checked my code for this kind of problem, meaning it can’t crop up at 3am on Christmas Day…

Final note/caveat

This Rust code is probably over-simplified, because all the references are immutable (you can’t change the objects they point to). In practice, we may well have mutable references, and if we do we’re going have to deal with the further difficulty that Rust won’t allow two different objects to hold references to an object if any of those references are mutable. So it would object to Billing and Monitoring using the Db object at the same time. We’d need to make it immutable (as we have here), or find a different way of structuring the code: for example, we could hold the Db instance only within the run_main_loop code, and pass it in temporarily to the Billing and Monitoring objects when we called their methods. A large part of the art, fun and pain of learning Rust is finding new patterns for your code that do what you need to do and also keep the compiler happy. When you manage it, you get amazing benefits!

Edge computing providers

I’m looking into Edge computing at work. By Edge computing I mean running WASM programs in lots and lots of smallish computers in places near to actual people (rather than in huge cloud data centres). I think it’s cool because I love Rust, and Rust is the leading language to compile to WASM.

Here are some companies providing Edge computing services:

  • Fastly – good links with WASM community (hired Mozilla devs), and early adopters – custom WASM engine wasmtime.
  • Cloudflare – huge, and early adopters – WASM engine is Google V8.
  • AWS Lambda@Edge – docs are light on detail, but it looks like a real offering, probably.

Also-rans:

Who did I miss?

Struggling with Rust to figure out the right types for a function signature

I am loving writing code in Rust. So many things about the language and its ecosystem feel so right*.

* For example: ownership of objects, expressive type system, compile to native, offline API docs, immutability, high quality libraries.

One of the things I like about it is that I don’t feel like I need to use an IDE, so I can happily code in Vim with no clever plugins.

One thing an IDE might give me would be an “extract function” refactoring. In most languages I am happy to do that manually, because I can let the compile errors guide me on what my function should look like.

However, in Rust I sometimes find it’s hard to find the right signature for a function I want to extract, and I am struggling to persuade the compiler to help me.

Here is an example from my new listsync project, in listsync-client-rust.rs:

use actix_web::{middleware, App, HttpServer};
use listsync_client_rust;
// ...
#[actix_rt::main]
async fn main() -> std::io::Result<()> {
//...
    HttpServer::new(|| {
        App::new()
            .wrap(listsync_client_rust::cookie_session::new_session())
            .wrap(middleware::Logger::default())
            .configure(listsync_client_rust::config)
    })
//...

I would like to extract the code highlighted above, the creation of an App, into a separate function, like this:

fn new_app() -> ??? {
    App::new()
        .wrap(listsync_client_rust::cookie_session::new_session())
        .wrap(middleware::Logger::default())
        .configure(listsync_client_rust::config)
}
//...
    HttpServer::new(|| {
        new_app()
    })

Simple, right? To find out what the return type of the function should be, I can just make a bad guess, and get the compiler to tell me what I did wrong. In this case, I will guess by changing the question marks above into i32, and run cargo test. I get quite a few errors, one of which is:

error[E0277]: the trait bound `i32: actix_service::IntoServiceFactory<_>` is not satisfied
  --> src/bin/listsync-client-rust.rs:27:5
   |
27 | /     HttpServer::new(|| {
28 | |         new_app()
29 | |     })
   | |______^ the trait `actix_service::IntoServiceFactory<_>` is not implemented for `i32`
   |
   = note: required by `actix_web::server::HttpServer`

So the first problem I see is that the error message I am seeing is about the later code, and there are no errors about my new function.

I obviously went a little too fast. Let’s change the HttpServer::new code back to how it was before, and only make a new function new_app. Now I get an error that should help me:

error[E0308]: mismatched types
  --> src/bin/listsync-client-rust.rs:12:5
   |
11 |   fn new_app() -> i32 {
   |                   --- expected `i32` because of return type
12 | /     App::new()
13 | |         .wrap(listsync_client_rust::cookie_session::new_session())
14 | |         .wrap(middleware::Logger::default())
15 | |         .configure(listsync_client_rust::config)
   | |________________________________________________^ expected i32, found struct `actix_web::app::App`
   |
   = note: expected type `i32`
              found type `actix_web::app::App<impl actix_service::ServiceFactory, actix_web::middleware::logger::StreamLog<actix_http::body::Body>>`

So the compiler has told us what type we are returning! Let’s copy that into the type signature of the function:

use actix_service::ServiceFactory;
use actix_http::body::Body;
// ...
fn new_app() -> App<impl ServiceFactory, middleware::logger::StreamLog<Body>> {
// ...

The first error I get from the compiler is a distraction:

error[E0432]: unresolved import `actix_service`
 --> src/bin/listsync-client-rust.rs:1:5
  |
1 | use actix_service::ServiceFactory;
  |     ^^^^^^^^^^^^^ use of undeclared type or module `actix_service`

I can fix it by adding actix-service = "1.0.5" to Cargo.toml. (I found the version by looking in Cargo.lock, since this dependency was already implicitly used – I just need to make it explicit if I am going to use it directly.)

Once I do that I get the next error:

error[E0603]: module `logger` is private
  --> src/bin/listsync-client-rust.rs:13:54
   |
13 | fn new_app() -> App<impl ServiceFactory, middleware::logger::StreamLog<Body>> {
   |                                                      ^^^^^^

This leaves me a bit stuck: I can’t use StreamLog because it’s in a private module.

More importantly, it makes the point that I don’t actually want to be as specific as I am being: I don’t care what the exact type parameters for App are – I just want to return an App of some kind and have the compiler fill in the blanks. Ideally, if I change the body of new_app later, for example to add another wrap call that changes the type of App we are returning, I’d like to leave the return type the same and have it just work.

With that in mind, I took a look at the type that HttpServer::new takes in. Here is impl HttpServer:

impl<F, I, S, B> HttpServer<F, I, S, B> where
    F: Fn() -> I + Send + Clone + 'static,
    I: IntoServiceFactory<S>,
    S: ServiceFactory<Config = AppConfig, Request = Request>,
    S::Error: Into<Error> + 'static,
    S::InitError: Debug,
    S::Response: Into<Response<B>> + 'static,
    <S::Service as Service>::Future: 'static,
    B: MessageBody + 'static, 

and HttpServer::new looks like:

pub fn new(factory: F) -> Self

So it takes in a function which actually makes the App, and the type of that function is F, which is a Fn which returns a I + Send + Clone + 'static. From the declaration of impl HttpServer we can see that the type of I depends on S and B, which have quite complex types. Let’s paste the whole thing in:

use actix_http::{Error, Request, Response};
use actix_service::IntoServiceFactory;
use actix_web::body::MessageBody;
use actix_web::dev::{AppConfig, Service};
use core::fmt::Debug;
// ...
fn new_app<I, S, B>() -> I
where
    I: IntoServiceFactory<S> + Send + Clone + 'static,
    S: ServiceFactory<Config = AppConfig, Request = Request>,
    S::Error: Into<Error> + 'static,
    S::InitError: Debug,
    S::Response: Into<Response<B>> + 'static,
    <S::Service as Service>::Future: 'static,
    B: MessageBody + 'static,
{
    App::new()
        .wrap(listsync_client_rust::cookie_session::new_session())
        .wrap(middleware::Logger::default())
        .configure(listsync_client_rust::config)
}

Note that I had to modify I to include the extra requirements on the return type of F from the definition of HttpServer. (I think I did the right thing, but I’m not sure. If I just remove the + Send + Clone + 'static it seems to behave similarly.)

Now I get this error from the compiler:

error[E0308]: mismatched types
  --> src/bin/listsync-client-rust.rs:27:5
   |
17 |   fn new_app<I, S, B>() -> I
   |                            - expected `I` because of return type
...
27 | /     App::new()
28 | |         .wrap(listsync_client_rust::cookie_session::new_session())
29 | |         .wrap(middleware::Logger::default())
30 | |         .configure(listsync_client_rust::config)
   | |________________________________________________^ expected type parameter, found struct `actix_web::app::App`
   |
   = note: expected type `I`
              found type `actix_web::app::App<impl actix_service::ServiceFactory, actix_web::middleware::logger::StreamLog<actix_http::body::Body>>`
   = help: type parameters must be constrained to match other types
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

The compiler really tries to help here, suggesting I read a chapter of the Rust Book, but even after reading it I could not figure out how to do what I am trying to do.

Can anyone help me?

Wouldn’t it be amazing if there were some way the compiler could give me easier-to-understand help to figure this out?

London Python Meetup January 2019 – Async Python and GeoPandas

It was a pleasure to go to the London Python Meetup organised by @python_london. There were plenty of friendly people and interesting conversations.

I gave a talk “Making 100 million requests with Python aiohttp” (slides, Blog post) explaining the basics of writing async code in Python 3 and how I used that to make a very large number of HTTP requests.

Andy giving the presentation

(Photo by CB Bailey.)

Hopefully it was helpful – there were several good questions, so I am optimistic that people were engaged with it.

After that, there was an excellent talk by Gareth Lloyd called “GeoPandas, the geospatial extension for Pandas” in which he explained how to use the very well-developed geo-spatial data tools available in the Python ecosphere to transform, combine, plot and analyse data which includes location information. I was really impressed with how easy the libraries looked to use, and also with the cool Jupyter notebook Gareth used to explain the ideas using live demos.

London Python Meetups seem like a cool place to meet Pythonistas of all levels of experience in a nice, low-pressure environment!

Meetup link: aiohttp / GeoPandas

Godot: Dragging and dropping physics objects video

Series: 2D Shapes, drag and drop

Continuing to explore the Godot 3 game engine. I want to make a game where you drag blocks around and balance them on each other, but I couldn’t find much documentation on how to drag-and-drop objects (except menu UI elements), and especially I found quite a few wrinkles when doing this with objects that are normally controlled by the physics engine.

This time we actually write some code in Godot’s programming language, GDScript.

Godot version: v3.0.6.stable.official.8314054

Graft Animation Language on Raspberry Pi

Because the Rapsberry Pi uses a slightly older Python version, there is a special version of Graft for it.

Here’s how to get it:

  • Open a terminal window by clicking the black icon with a “>” symbol on it at the top near the left.
  • First we need to install a couple of things Graft needs, so type this, then press Enter:
    sudo apt install python3-attr at-spi2-core
  • If you want to be able to make animated GIFs, install one more thing:
    sudo apt install imagemagick
  • To download Graft and switch to the Raspberry Pi version, type in these commands, pressing Enter after each line.
    git clone https://github.com/andybalaam/graft.git
    cd graft
    git checkout raspberry-pi
  • Now, you should be able to run Graft just like on another computer, for example, like this:
    ./graft 'd+=10 S()'
  • If you’re looking for a fun way to start, why not try the worksheet “Tell a story by making animations with code”?

    For more info, see Graft Raspberry Pi Setup.

My experience upgrading to Elm 0.19

Elm is unstable, so upgrading to the next version can be painful. Here’s what I needed to do to upgrade from 0.18 to 0.19.

  • Replace elm-package.json and tests/elm-package.json with elm.json – e06f5a1728
  • Switch to the new elm-testb964b7c7a
  • Re-arrange Main, and how we call it from JavaScript – 0c118c49f
  • Stop using eeue56/elm-all-dict (since it’s not ported to 0.19 and porting it looked hard due to a lack of Debug.crash) – fe100f256
  • Replace toString with String.fromX or Debug.toString – 9e78163d0a3
  • Stop “shadowing” names by making new variables with the same name as another in the scope – 9688a621de
  • Adapt to the changed Html.style function – b991ab4f
  • Stop using Debug.crash – f98a70ad1
  • Adapt to the changes in the Regex module – 856762a4
  • Stop using tuples with more than 3 parts – 472c0bb7

The lack of Debug.crash is really, really painful, especially for a library like eeue56/elm-all-dict that has lots of invariants that are hard or impossible to enforce via the type system. On the other hand, if Elm can give a hard guarantee that there will be no runtime errors, this seems pretty cool. The problem is that some code may well have to return the wrong answer silently, instead of crashing, which could be much worse than crashing in some use-cases.

I was annoyed by the lack of more-than-3-part tuples, but even as I did the work to change my code, I saw it get better, so it’s hard to argue with.

The hardest part to work out was how to run the tests. Fortunately the tests themselves needed almost no changes. I just needed to do this:

rm -r tests/elm-stuff
rm tests/elm-package.json
sudo npm install -g elm-test@0.19.0-beta8
elm-test install
elm-test

My next job is to check out the –optimize compiler flag, and the advice on making the code smaller and faster.

How to write a programming language articles

Recent Overload journal issues contain my new articles on How to Write a Programming Language.

Part 1: How to Write a Programming Language: Part 1, The Lexer

Part 2: How to Write a Programming Language: Part 2, The Parser

PDF of the latest issue: Overload 146 containing part 2.

This is all creative-commons licensed and developed in public at github.com/andybalaam/articles-how-to-write-a-programming-language

Ideas on how lexing will work in Pepper3

I am trying to practice documentation-driven development in Pepper3, so every time I start on an area, I will write documentation explaining how it works, and include examples that are automatically verified during the build.

I’ve started work on lexing, since you can’t do much before you do that, but in fact, of course, I need to have a command line interface before I can verify any of the examples, so I’m working on that too.

Lexing is the process that takes a stream of characters (e.g. from a file) and turns it into a stream of “tokens” that are chunks of code like a variable name, a number or a string. (There is more on lexing in my mini programming language, Cell.)

My thoughts so far about lexing are in lexing.md, and current ideas about command line interface are at command_line.md. All very much subject to change.

Headlines:

  • Ordinary programmers can write their own lexing rules.
  • Operators (functions like “+” that find their arguments on their left and right, instead of between brackets like normal functions) are defined at the lexing phase, so any symbol (e.g. “in”) can be an operator if you want.
  • Anything you might want to do with a pepper program, including running it, compiling it, packaging it for an distribution system, should be available as a sub-command of the main pepper3 command line.
  • The command is “pepper3”, never “pepper”. If a new, incompatible version comes out, it will be called “pepper4”, and they will be parallel-installable, with no confusion.

Questions and answers about Pepper3

Series: Examples, Questions

My last post Examples of Pepper3 code was a reply to my friend’s email asking what it was all about. They replied with some questions, and I thought the questions and answers might shed some more light:

Questions!

Brilliant ones, thanks.

In general though you’ve said a lot about what Pepper can do without giving design decisions.

Yep, total brain dump.

Remind me again who this language is for :)

It’s a multi-paradigm (generic, functional, OO) language aimed at application programmers who want:

  • “native” performance on their chosen platform (definitely including actual native machine code). This is inspired by C++.
  • easy deployment (preferably a single binary containing everything, with an option to link most dependencies statically), including packaging of installers for major OSes. This is inspired by C++, and the pain of C++.
  • perfect flexibility for creating types – “meta-programming” is just programming. Things you would have done using code generation (e.g. generating a class hierarchy from an XSD) are done by running arbitrary code at compile time. The powerful type system is inspired by Haskell and the book “Modern C++ Design”, and the meta-programming is inspired by Lisp.
  • Simple memory management without GC through ownership. This is inspired by modern C++, and then Rust came along and implemented it before I could, thus proving it works. However, I would remove a lot of the functionality in Rust (lifetimes) to make it much simpler.
  • Strong support for functional programming if you want it. This is inspired by Haskell.
  • The simplest possible core language, with application programmers able to expand it by giving them the same tools as the language designers – e.g. “for” is just a function, so you can make your own. I am hoping I can even make “class” a function. This is inspired by Lisp, and oppositely-inspired by Java.
  • Separation between the idea of Interfaces, which I think I will call “type specifiers” (and will allow arbitrary code execution to determine whether a type satisfies the requirements) and structs/classes, allowing us to make new Interfaces and have old code satisfy them, meaning we can do generic stuff with e.g. ints even if
    no-one declared that “class Int : public Quaternion” or whatever.
  • Lots of “nudges” towards things that are good: by default things will be functional and immutable – you will have to explicitly say if you want to use more dangerous constructs like side effects and mutable values.
  • No implicit conversions, or really anything happening without you saying so.

Can you assign floats to ints or vice versa?

Yes, but you shouldn’t.

If you’re setting types in code at the start of a file, is this only available in the main file? Are there multiple files per program? Can
you have libraries? If so, do these decide the functionality of their types in the library or does this only happen in the main file?

I haven’t totally decided – either by being enforced, or as a matter of style, you will generally do this once at the beginning of the program (and choose on the compiler command line to do it e.g. the debug way or the release way) and it will affect all of your code.

Libraries will be packaged as Pepper3 source code, so choices you make of the type of Int etc. will be reflected through the whole dependency tree. Cool, huh?

This is inspired by Python.

Can you group variables together into structs or similar?

Yes – it will be especially easy to make “value types”, and lots of default methods will be provided, that you will be strongly encouraged to use – e.g. copy and move operations. This is inspired by Elm.

Why are variables immutable by default but mutable with a special syntax? It’s the opposite of C++ const, but why that way around?

This is one of the “nudges” – immutable stuff is much easier to think about, and makes parallel stuff easier, and allows optimisations and so on, so turning it on by default means you have to choose to take the bad path, and are inclined to take the virtuous one. This is inspired by Haskell and Rust.

Why only allow assignments, function calls and operators? I’m sure you have good reasons.

To be as simple as possible, so you only have those things to learn and the rest can be understood by just reading the code. This is inspired by Python.

I wrote more of my (earlier) thoughts in this 4-post series, which is better thought through: Goodness in Programming Languages

Examples of Pepper3 code

Series: Examples, Questions

I have restarted my effort to make a new programming language that fits the way I like things. I haven’t pushed any code yet, but I have made a lot of progress in my head to understand what I want.

Here are some random examples that might get across some of the ways I am thinking:


// You code using general types like "Int" but you can set what
// they really are in the code (usually at the beginning), so
// if you plan to use native ints in the production code, it's
// a good idea to use:
Int = CheckedNativeInt;
// while in dev, since it will crash at runtime if you overflow.

// Then, in production when you're sure you have no errors,
// switch to an unchecked one:
Int = NativeInt;

// But, if you prefer correctness over efficiency, you can use
// mathematical integer that never overflows:
Int = ArbitrarySizeInt;


// Variables are immutable by default, so:
Int x = 4;
x = 3;      // this is a compile error


// But this is OK
Mutable(Int) y = 6;
y = y + x;

// Notice that you can call functions that return types that you
// then use, like Mutable(Int) here.

// Generally, code can run at either compile time or run time.
// Code to do with types has to run at compile time.
// By default, other code runs at run time, but you can force
// it to run early if you want to.


// A main method looks like this - you get hold of e.g. stdout through
// a World instance - I try to avoid any global functions like print, or
// global variables like sys.stdout.

Auto main =
{:(World world)->Int
    //...
};

// (Although note that Int, String etc. actually are global variables,
// which is a bit annoying)

// I wish the main method were simpler-looking.  The only saving grace
// is that for simple examples you don't need a main method -
// Pepper3 just calculates the expression you provide in your file and
// prints it out.


// Expressions in curly brackets are lambda functions, so:

{3};

// is a function taking no arguments, returning 3, and:

{:(Int x)
    x * 2
};

// is a function that doubles a value.

Obviously, we can tie functions to names:

Auto dbl =
    {:(Int x)
        x * 2
    };

// Meaning we can call dbl like this:
dbl(4);

// Auto is a magic word to say ("use type inference"), so
// this is equivalent to the above:

fn([Int]->Int) dbl =
    {:(Int x)
        x * 2
    };


// Because {} makes an anon function, things like "for" can be
// functions instead of keywords.

for(range(3), {:(Int x)
    world.stdout.println(to(String)(x));
});


// As far as possible, Pepper3 will only contain assignment statements:
String s = "xx";

// and expressions containing function calls and operators:
dbl(3) + 6;


// This means we can make our own constructs like a different type of
// for loop, which would need a new keyword in some languages:

Auto parallel_for = import(multiprocess.parallel_for);

Adding a concurrency limit to Python’s asyncio.as_completed

Series: asyncio basics, large numbers in parallel, parallel HTTP requests, adding to stdlib

In the previous post I demonstrated how the limited_as_completed method allows us to run a very large number of tasks using concurrency, but limiting the number of concurrent tasks to a sensible limit to ensure we don’t exhaust resources like memory or operating system file handles.

I think this could be a useful addition to the Python standard library, so I have been working on a modification to the current asyncio.as_completed method. My work so far is here: limited-as_completed.

I ran similar tests to the ones I ran for the last blog post with this code to validate that the modified standard library version achieves the same goals as before.

I used an identical copy of timed from the previous post and updated versions of the other files because I was using a much newer version of aiohttp along with the custom-built python I was running.

server looked like:

#!/usr/bin/env python3

from aiohttp import web
import asyncio
import random

async def handle(request):
    await asyncio.sleep(random.randint(0, 3))
    return web.Response(text="Hello, World!")

app = web.Application()
app.router.add_get('/{name}', handle)

web.run_app(app)

client-async-sem needed me to add a custom TCPConnector to avoid a new limit on the number of concurrent connections that was added to aiohttp in version 2.0. I also need to move the ClientSession usage inside a coroutine to avoid a warning:

#!/usr/bin/env python3

from aiohttp import ClientSession, TCPConnector
import asyncio
import sys

limit = 1000

async def fetch(url, session):
    async with session.get(url) as response:
        return await response.read()

async def bound_fetch(sem, url, session):
    # Getter function with semaphore.
    async with sem:
        await fetch(url, session)

async def run(r):
    with ClientSession(connector=TCPConnector(limit=limit)) as session:
        url = "http://localhost:8080/{}"
        tasks = []
        # create instance of Semaphore
        sem = asyncio.Semaphore(limit)
        for i in range(r):
            # pass Semaphore and session to every GET request
            task = asyncio.ensure_future(
                bound_fetch(sem, url.format(i), session))
            tasks.append(task)
        responses = asyncio.gather(*tasks)
        await responses

loop = asyncio.get_event_loop()
loop.run_until_complete(asyncio.ensure_future(run(int(sys.argv[1]))))

My new code that uses my proposed extension to as_completed looked like:

#!/usr/bin/env python3

from aiohttp import ClientSession, TCPConnector
import asyncio
import sys

async def fetch(url, session):
    async with session.get(url) as response:
        return await response.read()

limit = 1000

async def print_when_done():
    with ClientSession(connector=TCPConnector(limit=limit)) as session:
        tasks = (fetch(url.format(i), session) for i in range(r))
        for res in asyncio.as_completed(tasks, limit=limit):
            await res

r = int(sys.argv[1])
url = "http://localhost:8080/{}"
loop = asyncio.get_event_loop()
loop.run_until_complete(print_when_done())
loop.close()

and with these, we get similar behaviour to the previous post:

$ ./timed ./client-async-sem 10000
Memory usage: 73640KB	Time: 19.18 seconds
$ ./timed ./client-async-stdlib 10000
Memory usage: 49332KB	Time: 18.97 seconds

So the implementation I plan to submit to the Python standard library appears to work well. In fact, I think it is better than the one I presented in the previous post, because it uses on_complete callbacks to notice when futures have completed, which reduces the busy-looping we were doing to check for and yield finished tasks.

The Python issue is bpo-30782 and the pull request is #2424.

Note: at first glance, it looks like the aiohttp.ClientSession‘s limit on the number of connections (introduced in version 1.0 and then updated in version 2.0) gives us what we want without any of this extra code, but in fact it only limits the number of connections, not the number of futures we are creating, so it has the same problem of unbounded memory use as the semaphore-based implementation.

Basic ideas of Python 3 asyncio concurrency

Series: asyncio basics, large numbers in parallel, parallel HTTP requests, adding to stdlib

Python 3’s asyncio module and the async and await keywords combine to allow us to do cooperative concurrent programming, where a code path voluntarily yields control to a scheduler, trusting that it will get control back when some resource has become available (or just when the scheduler feels like it). This way of programming can be very confusing, and has been popularised by Twisted in the Python world, and nodejs (among others) in other worlds.

I have been trying to get my head around the basic ideas as they surface in Python 3’s model. Below are some definitions and explanations that have been useful to me as I tried to grasp how it all works.

Futures and coroutines are both things that you can wait for.

You can make a coroutine by declaring it with async def:

import asyncio
async def mycoro(number):
    print("Starting %d" % number)
    await asyncio.sleep(1)
    print("Finishing %d" % number)
    return str(number)

Almost always, a coroutine will await something such as some blocking IO. (Above we just sleep for a second.) When we await, we actually yield control to the scheduler so it can do other work and wake us up later, when something interesting has happened.

You can make a future out of a coroutine, but often you don’t need to. Bear in mind that if you do want to make a future, you should use ensure_future, but this actually runs what you pass to it – it doesn’t just create a future:

myfuture1 = asyncio.ensure_future(mycoro(1))
# Runs mycoro!

But, to get its result, you must wait for it – it is only scheduled in the background:

# Assume mycoro is defined as above
myfuture1 = asyncio.ensure_future(mycoro(1))
# We end the program without waiting for the future to finish

So the above fails like this:

$ python3 ./python-async.py
Task was destroyed but it is pending!
task: <Task pending coro=<mycoro() running at ./python-async:10>>
sys:1: RuntimeWarning: coroutine 'mycoro' was never awaited

The right way to block waiting for a future outside of a coroutine is to ask the event loop to do it:

# Keep on assuming mycoro is defined as above for all the examples
myfuture1 = asyncio.ensure_future(mycoro(1))
loop = asyncio.get_event_loop()
loop.run_until_complete(myfuture1)
loop.close()

Now this works properly (although we’re not yet getting any benefit from being asynchronous):

$ python3 python-async.py
Starting 1
Finishing 1

To run several things concurrently, we make a future that is the combination of several other futures. asyncio can make a future like that out of coroutines using asyncio.gather:

several_futures = asyncio.gather(
    mycoro(1), mycoro(2), mycoro(3))
loop = asyncio.get_event_loop()
print(loop.run_until_complete(several_futures))
loop.close()

The three coroutines all run at the same time, so this only takes about 1 second to run, even though we are running 3 tasks, each of which takes 1 second:

$ python3 python-async.py
Starting 3
Starting 1
Starting 2
Finishing 3
Finishing 1
Finishing 2
['1', '2', '3']

asyncio.gather won’t necessarily run your coroutines in order, but it will return a list of results in the same order as its input.

Notice also that run_until_complete returns the result of the future created by gather – a list of all the results from the individual coroutines.

To do the next bit we need to know how to call a coroutine from a coroutine. As we’ve already seen, just calling a coroutine in the normal Python way doesn’t run it, but gives you back a “coroutine object”. To actually run the code, we need to wait for it. When we want to block everything until we have a result, we can use something like run_until_complete but in an async context we want to yield control to the scheduler and let it give us back control when the coroutine has finished. We do that by using await:

import asyncio
async def f2():
    print("start f2")
    await asyncio.sleep(1)
    print("stop f2")
async def f1():
    print("start f1")
    await f2()
    print("stop f1")
loop = asyncio.get_event_loop()
loop.run_until_complete(f1())
loop.close()

This prints:

$ python3 python-async.py
start f1
start f2
stop f2
stop f1

Now we know how to call a coroutine from inside a coroutine, we can continue.

We have seen that asyncio.gather takes in some futures/coroutines and returns a future that collects their results (in order).

If, instead, you want to get results as soon as they are available, you need to write a second coroutine that deals with each result by looping through the results of asyncio.as_completed and awaiting each one.

# Keep on assuming mycoro is defined as at the top
async def print_when_done(tasks):
    for res in asyncio.as_completed(tasks):
        print("Result %s" % await res)
coros = [mycoro(1), mycoro(2), mycoro(3)]
loop = asyncio.get_event_loop()
loop.run_until_complete(print_when_done(coros))
loop.close()

This prints:

$ python3 python-async.py
Starting 1
Starting 3
Starting 2
Finishing 3
Result 3
Finishing 2
Result 2
Finishing 1
Result 1

Notice that task 3 finishes first and its result is printed, even though tasks 1 and 2 are still running.

asyncio.as_completed returns an iterable sequence of futures, each of which must be awaited, so it must run inside a coroutine, which must be waited for too.

The argument to asyncio.as_completed has to be a list of coroutines or futures, not an iterable, so you can’t use it with a very large list of items that won’t fit in memory.

Side note: if we want to work with very large lists, asyncio.wait won’t help us here – it also takes a list of futures and waits for all of them to complete (like gather), or, with other arguments, for one of them to complete or one of them to fail. It then returns two sets of futures: done and not-done. Each of these must be awaited to get their results, so:

asyncio.gather

# is roughly equivalent to:

async def mygather(*args):
    ret = []
    for r in (await asyncio.wait(args))[0]:
        ret.append(await r)
    return ret

I am interested in running very large numbers of tasks with limited concurrency – see the next article for how I managed it.