There is a game called TIS-100 where you solve problems using a grid of networked processors that can each store one current register and a second value you can swap to. It's an extremely constrained environment as such.
There is one challenge where you receive a series of numbers, have to sort and then output them. The game provides a couple of FIFO units you can read and write from in order to facilitate this.
I, instead, decided to do it without using them. I ended up storing all of the state in branching. By passing values down and then jumping and returning literals from branches, it gave me effectively a comparatively massive amount of space based on where the instruction pointer was sitting in any given node, letting me manipulate the state, storing it as branches taken, and then dumping out literals from the lowest levels of those before resetting the nodes for the next series of values.
It made me cognizant of how state, assumptions and literal values are "stored" by which branch you choose, with no actual variables.
This is also what happens when you run a "check" on a value rather than parsing it into a more specific type related to the check [1]. After a `if( !isa_username( somestring) ){ return ; }` you will often assume that `somename` is a username without actually encoding that into its type.
Because these assumptions are not checked by the compiler, then the compiler can't stop you from inappropriately merging branches or accidentally cutting out checks later.
Narrowing involves actual types. I was referring to the compiler not checking mere value validation.
I was referencing the kind of validation where someone checks a bunch of attributes of a string, usually, or perhaps the range of an integer, but never actually does anything excepting in fail cases and then passes it on to other functions that then just expect those invariants to hold. I doubt typescript is remembering that my string doesn't have dashes in it or that it adheres to some regex, for example.
Type narrowing is fantastic for making things like nil punning work inside a complex type system.
I really like typescript's types. From where they started, they did an absolutely incredible job creating a robust and powerful type system that could manage almost any existing javascript code pattern.
type ValidatedInputString = string & { __brand: "User Input Post Validation" };
const validateUserInput = (input: string) => {
const simpleValidatedInput = input.replace(/\</g, "≤");
return simpleValidatedInput as ValidatedInputString;
};
at runtime, simpleValidatedInput is still a string—it has not been parsed into a more specific type. The code just asserts (falsely) that it's a ValidatedInputString, and defines the latter in a way that prevents passing string-strings as ValidatedInputStrings.
I do appreciate your expounding on this, but I assure you I do get it.
Using types to track these things is the appropriate solution. In most languages you would either create a wrapping object you can get the original back from or perhaps extend the basic type. Here we can just use `as` to cast the value into an intersection with the number, which I assume allows it to continue being used as a number but will catch failures on functions that needs a ValidatedInputString, in much the same way the an inherited subtype might. Probably better.
I get it and you are right, this is the right thing to do.
My original comment was that for those that do not do this appropriate type level work to track that we have validated a value, then it becomes an assumed aspect of the branch.
This was very, very common in older code I've seen. I think I can safely assume that it still happens today, though if I am wrong I'll be glad that parsing the values into new types has made enough headway that it is seen as simply the default.
An important difference between grandparent and parent comments is that the former mentioned a post about Haskell where the type system is based on category theory, and type refinements don't apply much (if at all). On the other hand, the latter talks about Typescript, which has a type system is based on set theory and type refinements apply very well.
Anothet example similar to Typescript is Ruby's Sorbet type checker, which is also based on set theory and does a great usage of type refinements as well.
I have second thoughts on the author's assertion that "When it’s possible to store state in code instead, that often leads to a clearer program."
I have found that an explicit state machine can be more readable when there are many states. When there are too many states, a straightforward transformation to control flow often cannot eliminate all the "goto"s like the author successfully did. Even if they were eliminated, there are usually too many nested "if" conditions and the like to be easily readable. That's the kind of spaghetti code that first inspired a ban on goto. (And that's not even including cases when you are writing code to a spec that's a state machine, like the TCP state machine.)
What I personally like, sometimes, is to make the state variable an enum and give names to be states. State 0 becomes kBeforeStart, state 1 becomes kInsideQuote, state 2 becomes kAfterBackslash. It suddenly now becomes intuitive. If you've written any kind of emulator or interpreter it's even more intuitive, because the state machine is just the DFA expanded from the regular expression. If I'm using a language with guaranteed tail calls, I can also replace each case in that switch by a separate named function.
It's possible to write clear and readable code in either style. Doing so requires skill and expertise, of which I don't think the author lacks.
Yes. The second version is difficult to understand when there's a need to add new states or modify the states. The first version has a straightforward structure and shape, making it easier to understand and update the state machine.
I don't agree. The second version is the typical way hand-written compiler lexers are written, and they're straightforward to add new "states" to, or to modify the states. The program counter is where you're "at", and the state space is normally straightforward. In fact it only gets complicated when additional non-control-flow state has been added.
A typical hand-written lexer looks a bit like this (EOF testing omitted for clarity):
// skip whitespace
while isWhiteSpace(peekChar())
nextChar()
// determine token type
switch (peekChar())
case isAlpha
start := currentPosition()
nextChar()
while isAlphaNumeric(peekChar())
nextChar()
tokenType = IDENT
tokenValue = substring(start, currentPosition())
case isNumeric
start := currentPosition()
nextChar()
while isNumeric(peekChar())
nextChar()
tokenType = INT
tokenValue = substring(start, currentPosition())
tokenAsInt = int(tokenValue)
case '+'
nextChar()
tokenType = PLUS
// and so on
Adding new cases to this is trivial. Nested context-specific lexical details (like escape codes in strings) aren't merged with a global state machine, and can be handed off to subroutines, enabling a modularity which is less confusing than having multiple state machines.
What's really unfortunate is that compilers already perform this "control flow -> state machine" transformation, but almost none of them expose it to the user for direct manipulation - instead, they tightly couple it to a bunch of unrelated abstractions like event loop runtimes, async executors, managed stacks, etc. I'd kill for a compiler that can properly:
* Parse a coroutine that produces and consumes values
* Perform all the normal function-level optimizations to minimize frame space (stack slot reuse via liveness analysis of local variables, re-computing temporaries across yield points, etc.)
* Expose that coroutine frame as a fixed-size struct that I can explicitly resume and query
Zig is almost there, but suspend/resume cannot return values/take arguments, which requires some unergonomic workarounds. Rust is making some promising progress on unified coroutines (https://github.com/rust-lang/rfcs/pull/2781), but the generator types are opaque so you can't encapsulate them in a Sized struct or allocate an array of them. Not to mention that it's still extra-unstable, and last I checked, there were issues with generator size optimizations (https://github.com/rust-lang/rust/issues/59087). C++20 coroutines are similarly opaque and cannot be allocated as a contiguous array.
Yes, something like Python generators which have yield and send, but typed, and which compiles down to an efficiently sized struct with a resume function. Here's a crude illustration of what I mean, using pseudo-code describing a TCP session flow:
coroutine tcp_session() {
var syn_packet = @consume();
if(!check_syn_flag(syn_packet)) {
@produce(ERROR_BAD_INPUT);
return;
}
var syn_ack_packet = build_tcp_segment(...);
@produce(syn_ack_packet);
var ack_packet = @consume();
if(!check_ack_flag(ack_packet)) {
@produce(ERROR_BAD_INPUT);
}
// ... proceed with tcp session
}
Such a coroutine would then be usable elsewhere in code like so:
var tcp_connections = map<(ip_address, u16), tcp_session>::new();
// ...
var incoming_ip_packet = read_ip_packet_from_raw_socket();
var result = tcp_connections[get_dst(incoming_ip_packet)].resume(incoming_ip_packet);
if(result == ERROR_BAD_INPUT) {
// ...
}
And the compiler would be able to determine upfront what the size of the tcp_session struct is, so there'd be no need for implicit boxing/heap allocations.
So something like this, off the top of my head. It's not the most Rust-native code because I tried to match your code block as closely as possible to make the parallels more obvious.
struct TCPHandle {
sender: Sender<TCPPacket>,
// I'm taking liberties here, you can't use impl like this
// so you'd have to engage in some shenanigans which I don't
// want to type right now...
stream_to_client: impl Stream<Item = Result<TCPPacket, TCPError>>,
}
fn tcp_session() -> TCPHandle {
let (sender, receiver) = channel();
let stream_to_client = stream! {
let syn_packet = receiver.recv().await;
if (!check_syn_flag(syn_packet)) {
yield Err(TCPError::BadInputError);
return;
}
let syn_ack_packet = build_tcp_segment(...);
yield Ok(syn_ack_packet);
let ack_packet = receiver.recv().await;
if (!check_ack_flag(ack_packet)) {
yield Err(TCPError::BadInputError);
return;
}
// ... proceed with TCP session
}
TCPHandle { sender, stream_to_client }
}
let tcp_connections = HashMap<(Ipv4Addr, u16), TCPHandle>;
loop {
let incoming_ip_packet = read_ip_packet_from_raw_socket().await;
let handle = tcp_connections.get_mut(get_dst(&incoming_ip_packet));
handle.sender.send(incoming_ip_packet).await;
let result = handle.stream_to_client.next().await;
match result {
Ok(packet) => send_ip_packet_to_raw_socket(packet).await,
Err(e) => { ... handle errors },
}
}
I'm curious how something like this would work for your purposes... you could probably wrap the whole thing up a little more and make it behave even more like your example?
I'm aware that encapsulated control flow like this exists at a syntactic level, but the implementation deficiencies remain unaddressed:
1. No access to the actual concrete type, as you mentioned, which means you can't do Vec<Stream<...>> - you have to resort to indirections like Vec<Box<dyn Stream<...>>>. You might be able to work around this somehow if you were determined enough (DWARF debug info and std::mem::transmute come to mind), but any such approach would result in an ugly and exceedingly fragile abomination.
2. Brittle, if any, optimization. `stream!` is basically async/await with proc macro syntax dressing, and Rust's async/await implementation still suffers the same sort of bloated frame size issues as generators do, under certain circumstances.
To provide some context, suppose I want to write a custom event loop that handles millions of concurrent sessions (could be filesystem transactions, or TCP sessions, or some other I/O). At that level, every kilobyte of per-session data I add equates to additional gigabytes of memory usage. Every byte of space used by the compiler-generated state machine has to be carefully accounted for. I can't afford to have my per-session context blowing up in size because the compiler naively duplicates stack slots for arguments across yield points [1], or because one of my local variable types implements Copy [2], or because the compiler will simply fail to optimize local variables that are never live across a yield point [3]. I suppose if I care so much about memory usage, I could just draw up my own state machine, mentally track the liveness of each state variable and lay out a hand-written size-optimized struct accordingly, but that's going to be a painful exercise and a maintainability nightmare.
I think high level control over control flow manipulation is really underrated and underutilised in programming languages.
For example, the decision where to jump is extremely powerful but the primitives we have for it are weak. (Exceptions, algebraic effects, if statements)
Inheritance controls control flow but doesn't actually solve the pattern of desired behaviour and code organisation most people want.
One idea I am exploring is the idea that efficient control flow can be compiled from the inferred relationships of a rule engine.
Information systems should be used to create all the relationships between data and associations of desired behaviour to data values or partial data values.
Then all the if statements, switch statements and vtables can be inferred.
In other words the types the code operates on is inferred from desired behaviour based on state.
I, too, once thought this way. The problem is that inference and implicit behavior is cognitively expensive. With any language, humans have to be able to act as an adhoc, likely unoptimized or even worst case compiler.
You can work around this by transcending text with all the comforts of a modern IDE, interacting with the toolchain directly, but this has a cost too. The toolchain is often out of reach during code reviews, in diffs, snippets, etc.
Now I much prefer the ability to comprehend printed code revealed in spots under flickering candlelight or rasterized on a pocket display consumed while in a moving vehicle, or a drunken stupor even.
You're right, of course - it does indeed have the potential to increase cognitive expense. I would hope it would only increase cognitive load in the rule engine interface. But I would want that to be a GUI. I think I would prefer that to parsing custom code each time (that's the tradeoff I'm making).
I just get very frustrated reading other people's code that encode complicated rules that I need to decipher how they've represented the mapping of code to behaviour.
In corporate Java projects, I think what gets created is complicated structures and abstractions to handle flexibility and abstract over details that are harder to understand than the English explanation of what they're trying to do. WHEN X DO Y.
When people reach for the visitor pattern, controllers, inheritance, runtime reflection control flow and annotations and object proxies, overridden methods and so on. It's a overcomplicated bespoke dance about managing control flow and they're all different strategies but they do the same thing.
The idea is in early stages. I'm currently working on something else, I am trying to understand the control flow of a coroutine and yield.
This is a fascinating concept that I've written about before: "C#’s async/await compared to protothreads in C++". [1] Both async/await in C# and protothreads [2] in C unroll control flow to a state machine. In C, this is done using some simple but crazy macros using the fact that you can interleave switch statements with other control flow (ala Duff's Device [3]).
Many years ago I ported Adam Dunkel's protothreads library to C++ [4]. You can use C protothreads in C++ directly, of course, but it's a bit nicer to use classes.
How would one go about this in C or Rust? Chans are idiomatic and fast in Golang, what would you do in places lacking that?
Context: all my Rust programs recently have been ending up structured around some threads communicating item-by-item with mpsc_channels. This feels (unsubstantiated) non-ideal, esp if I'm doing something latency sensitive like processing input. But what, if anything, to do instead?
C is a language without much of a standard library. To do this in C you'd first need to write a coroutine library.
In Rust, your approach sounds fine. However you should also consider simply using Rust's iterator. Define a struct containing the state you want, then implement it as an Iterator. In the future, you can also just write control flow and have the compiler transform that for you. Take a look at the first few sections of https://lang-team.rust-lang.org/design_notes/general_corouti...
The game that I'm working on in my spare time has a lot of state machines in it compiled to CLOS, letting me use method calls as a means of directly sending sending events. Rather than write all those methods myself, with `case` forms on the state, I spent an afternoon writing this [0]
(defmacro defdelta (class &body body)
(let* ((body `(,@body
(- enter - - -)
(- leave - - -)))
(acc (group-by
1
(let ((-q0) (-e) (-w) (-q) (-a))
(loop for (q0 e w q a) in (cdr body) do
(setf -q0 (tc q0 -q0)
-e (tc e -e)
-w (tc w -w)
-q (tc q -q)
-a (tc a -a))
collect (list -q0 -e -w -q -a))))))
(push (cons class acc) *delta*)
`(progn
,@(loop for (e . clauses) in acc collecting
`(progn
(defevent ,e)
(defmethod ,e ((me ,class) &rest args)
(when (member *@* args)
(apply #'emit ',e (state me) me args))
(case (state me)
,@ (loop for (q0 . deltas) in (group-by 0 clauses)
collecting
`(,q0 (random-case
,@ (loop for (- -- w q a) in deltas
collecting
`((,@(or w 1))
,@(when (and q (not (eq q0 q)))
`((change-state me ',q args)))
,@(when a
`((apply ',a me args)))))))))))))))
along with some support code (e.g., the action functions) to define the auto-closing, auto-locking behavior of doors.
---
[0] Some helpers have been omitted. `defevent` defines a generic function with the given name and a particular set of arguments, and a default method that does nothing. `change-state` handles the mechanics of updating the state variable, sending a `leave` event just before the transition and `enter` just after.
This makes me think of tries. You don’t actually need to store the value at the leaf if you simply knew the path traversed in the traversal function. Of course sometimes it’s more efficient to store values.
There is one challenge where you receive a series of numbers, have to sort and then output them. The game provides a couple of FIFO units you can read and write from in order to facilitate this.
I, instead, decided to do it without using them. I ended up storing all of the state in branching. By passing values down and then jumping and returning literals from branches, it gave me effectively a comparatively massive amount of space based on where the instruction pointer was sitting in any given node, letting me manipulate the state, storing it as branches taken, and then dumping out literals from the lowest levels of those before resetting the nodes for the next series of values.
It made me cognizant of how state, assumptions and literal values are "stored" by which branch you choose, with no actual variables.
This is also what happens when you run a "check" on a value rather than parsing it into a more specific type related to the check [1]. After a `if( !isa_username( somestring) ){ return ; }` you will often assume that `somename` is a username without actually encoding that into its type.
Because these assumptions are not checked by the compiler, then the compiler can't stop you from inappropriately merging branches or accidentally cutting out checks later.
It's powerful, common, and generally dangerous.
[1] https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...