State Machines and the Strange Case of Mutating API

post by Martin Sustrik (sustrik) · 2018-12-24T05:50:00.599Z · score: 8 (3 votes) · LW · GW · 5 comments

State machines are widely used to implement network protocols, or, generally, objects that have to react to external events.

Consider TCP state machine:

During its lifetime TCP socket moves throught different states in the diagram. When you start connecting it's in SYN SENT state, when the initial handshake is over, it's in ESTABLISHED state and so on.

And here's an interesting observation: The API of the socket changes as you move from one state to another. For example, it doesn't make sense to receive data while you are still connecting. But once you are connected, receiving data is all right.

To give a more illustrative example, have a look at SOCKS5 protocol. It's basically a TCP or UDP proxy protocol. It's used, for example, by Tor. It starts with authentication phase, supporting different kinds of authentication. Then it moves to connection establishment phase. Once again there are different ways to connect. You can connect to an IPv4 address, to a IPv6 address or to a hostname. Finally, the state machine moves to one of the working states. This can be a TCP connection or an UDP connection.

Note how API changes between the states. In CLOSED state you can call functions such as connect_unauthenticated or connect_password. In AUTHENTICATED state you can call connect_tcp, bind_tcp or open_udp. In TCP ESTABLISHED you can do normal stream socket operations, while in UDP ESTABLISHED you can do datagram operations.

This requirement of mutating API is at odds with how the state machines are normally implemented: There's a single object representing the connection during it's entire lifetime. Therefore, a single object must support different APIs.

What it leads to is code like this:

void Socks5::connect_tcp(Addr addr) { if(state != AUTHENTICATED) throw "Cannot connect is this state."; ... }

Which, let's be frank, is just an implementation of dynamically typed language on top of statically-typed one.

In other words, by implementing state machines this way we are giving up proper type checking. While compiler would be perfectly able to warn us if connect_tcp was called in CLOSED state, we give up on the possibility and we check the constraint at runtime.

This sounds like bad coding style, but it turns out that the programming languages we use fail to provide tools to handle this kind of scenarios. It's not network programmers who are at fault, but rather programming language designers.

The closest you can get is having a different interface for each state and whenever state transition happens closing the old interface and opening a new one:

auto i1 = socks5_socket(); auto i2 = i1->connect_unauthenticated(proxy_addr); // i1 is an invalid pointer at this point auto i3 = i1->connect_tcp(addr); // i2 is an invalid pointer at this point

But note how ugly the code is. You have there undefined variables (i1, i2) hanging around. If you accidentally try to use them, you'll get a runtime error. And imagine how would the code closing the socket have to look like!

So you try to "undeclare" those variables, but the only way to do "undeclare" is it let the variable fall out of scope:

socks5_tcp_established *i3; { socks5_authenticated *i2; { auto i1 = socks5_socket(); i2 = i1->connect_unauthenticated(proxy_addr); } i3 = i1->connect_tcp(addr); }

You've got what you wanted — only i3 is declared when you get to the end of the block — but you aren't better off. Now you have undefined variables at the beginning. And I am not even speaking of how ugly the code looks like.

Anyway, this rant is addressed to programming language designers: What options do we have to support such mutating API at the moment. And can we do better?

5 comments

Comments sorted by top scores.

comment by uncomputable · 2018-12-24T17:40:47.400Z · score: 3 (2 votes) · LW(p) · GW(p)

there's been some work on adding linear types to programming languages, to do things like ensure that you can't use a resource after it has been closed/freed. similarly you could prevent the use of a resource before it has been fully opened/configured. (useful for sockets since they require multiple steps.)

wadler's "linear types can change the world!" might be an appropriate starting point. https://homepages.inf.ed.ac.uk/wadler/topics/linear-logic.html#linear-types

apologies, i have not read it. linear types are outside my area of interest.

comment by rossry · 2018-12-24T12:28:14.792Z · score: 3 (2 votes) · LW(p) · GW(p)

I'm not a network programmer or language designer by trade, so I expect to be missing something here, but I'll give it a go to learn where I'm wrong.

If you're using distinct interfaces for distinct states (as it seems you are in your latter examples) and your compiler is going to enforce them, then shadowing variables (as a language feature) lets you unassign them as you go along. In a language I'm more familiar with, which uses polymorphic types rather than interfaces:

let socket = socks5_socket () in
let socket = connect_unauthenticated socket ~proxy in
let socket = connect_tcp socket address in
enjoy socket ();

with signatures:

val sock5_socket : unit -> [> `Closed of Socket.t]
val connect_unauthenticated : [< `Closed of Socket.t] -> proxy:Address.t -> [> `Authenticated of Socket.t]
val connect_tcp -> [< `Authenticated of Socket.t] -> Address.t -> [> `Tcp_established of Socket.t]
val enjoy : [< `Tcp_established of Socket.t] -> unit -> unit

so that if you forget the connect_unauthenticated line (big danger of shadowing as you mutate), your compiler will correct you with a friendly but stern:

This expression has type [> `Closed of Socket.t] but an expression was expected of type [< `Authenticated of Socket.t].

Of course, shadowing without type-safety sounds like a nightmare, and I'm not claiming that any language you want to use actually supports it as syntax. But I occasionally appreciate it (given, of course, that I've got a type inspector readily keybound, to query what state my socket is in at this particular point).

comment by TAG · 2018-12-26T13:45:22.227Z · score: 1 (1 votes) · LW(p) · GW(p)

And here’s an interesting observation: The API of the socket changes as you move from one state to another.

Anyway, this rant is addressed to programming language designers: What options do we have to support such mutating API at the moment. And can we do better?

It's called typestate. It's been tried, and it tends to be cumbersome.

comment by rsaarelm · 2018-12-25T10:51:59.812Z · score: 1 (1 votes) · LW(p) · GW(p)

You can do the linear typing thing in Rust. Have a hidden internal handle and API wrapper objects on top of it that get consumed on method calls and can return different wrappers holding the same handle. I took a shot at doing a toy implementation for the TCP case:

type internal_tcp_handle = usize;  // Hidden internal implementation

/// Initial closed state
#[derive(Debug)]
pub struct Tcp(internal_tcp_handle);

impl Tcp {
    pub fn connect_unauthenticated(self) -> Result<AuthTcp, Tcp> {
        // Consume current API wrapper,
        // return next state API wrapper with same handle.
        Ok(AuthTcp(self.0))
    }

    pub fn connect_password(self, _user: &str, pass: &str) -> Result<AuthTcp, Tcp> {
        // Can fail back to current state if password is empty.
        if pass.is_empty() { Err(self) } else { Ok(AuthTcp(self.0)) }
    }
}

/// Authenticated state.
#[derive(Debug)]
pub struct AuthTcp(internal_tcp_handle);

impl AuthTcp {
    pub fn connect_tcp(self, addr: &str) -> Result<TcpConnection, AuthTcp> {
        if addr.is_empty() { Err(self) } else { Ok(TcpConnection(self.0)) }
    }

    pub fn connect_udp(self, addr: &str) -> Result<UdpConnection, AuthTcp> {
        if addr.is_empty() { Err(self) } else { Ok(UdpConnection(self.0)) }
    }
}

#[derive(Debug)]
pub struct TcpConnection(internal_tcp_handle);

#[derive(Debug)]
pub struct UdpConnection(internal_tcp_handle);

fn main() {
    // Create unauthenticated TCP object.
    let tcp = Tcp(123);
    println!("Connection state: {:?}", tcp);

    // This would be a compiler error:
    // let tcp = tcp.connect_tcp("8.8.8.8").unwrap();
    // 'tcp' is bound to an API that doesn't support connect operations yet.

    // Rebind the stupid way, unwrap just runtime errors unless return is Ok.
    let tcp = tcp.connect_unauthenticated().unwrap();
    // Now 'tcp' is bound to the authenticated API, we can open connections.
    println!("Connection state: {:?}", tcp);

    // The runtime errory way is ugly, let's handle failure properly...
    if let Ok(tcp) = tcp.connect_tcp("8.8.8.8") {
        println!("Connection state: {:?}", tcp);
    } else {
        println!("Failed to connect to address!");
    }
    // TODO Now that we can use connected TCP methods on 'tcp',
    // implement those and write some actual network code...
}
comment by Ivan Matek (ivan-matek) · 2018-12-25T16:22:23.334Z · score: -1 (2 votes) · LW(p) · GW(p)

Actually this is one of the examples where C++17 std::variant shines...