2 ms·

Imagine you have a program where there are 4 options, W, X, Y, Z. Y and Z can't be set at the same time, and X can't be set unless W is set. If Y is set then

Imagine you have a program where there are 4 options, W, X, Y, Z. Y and Z can't be set at the same time, and X can't be set unless W is set. If Y is set then X must be set as well. How do you represent this in a way that makes it impossible, even through programmer error elsewhere in the program, to have the flags in an invalid state? You can create en enum that looks like: enum program_state = ( W_X_Y_NZ, W_NX_NY_Z, NW_NX_NY_Z, ... and so on );

keybored 2y ago
And the Make Impossible States Unrepresentable crowd program like that?
- WorldMaker 2y ago
  It is not too bad in languages with discriminated unions. It's also not hard to fake discriminated unions in languages without them, even if you will miss some of the niceties. Rather than thinking of it as an enum, think of it as a list of contructors: class ProgramState { bool w, x, y, z; ProgramState(x, z) // implies y = true, w = true ProgramState(w, z) // cannot set x; implies y = false (cannot set y) } Even if the class needs all four fields, internally to represent all the possible combinations of data, there's no constructors/setters to work with them independently. (Which is also related to why "Make Impossible States Unrepresentable" also generally implies immutable, no setters at all makes it much easier to make states impossible.) In languages with discriminated unions you might even have some natural field sharing depending on how your "constructors" are written and the memory expansion isn't necessarily "exponential".
  - crdrost 2y ago
    Also to mention it, languages without discriminated unions often have generics and function types, which can be used to build discriminated unions with Church encodings: // idiomatic typescript type Optional<IfAbsent, IfPresent> = | {type: 'absent', detail: IfAbsent} | {type: 'present', value: IfPresent} // Church-encoded version type Either<x, y> = <z>(ifLeft: (x: x) => z, ifRight: (y: y) => z) => z // isomorphism between the two function church<x, y>(opt: Optional<x, y>): Either<x, y> { return (ifLeft, ifRight) => opt.type === 'absent'? ifLeft(opt.detail) : ifRight(opt.value) } function unchurch<x, y>(opt: Either<x, y>): Optional<x, y> { return opt<Optional<x,y>>(x => ({type: 'absent', detail: x}), y => ({type: 'present', value: y})) } In addition the Church encoding of a sum type, is a function that takes N handler functions and calls the appropriate one for the case that the data type is in. With a little squinting, this is the Visitor pattern. interface LeftRightVisitor<X, Y, Z> { visit(x: Left<X>): Z visit(y: Right<Y>): Z } interface LeftRight<X, Y> { accept<Z>(visitor: LeftRightVisitor<X, Y, Z>): Z; } class Left<X> implements LeftRight<X, any> { constructor(public readonly x: X) {} accept<Z>(visitor: LeftRightVisitor<X, any, Z>) { return visitor.visit(this) } } class Right<Y> implements LeftRight<any, Y> { constructor(public readonly y: Y) {} accept<Z>(visitor: LeftRightVisitor<any, Y, Z>) { return visitor.visit(this) } } // isomorphism function visitify<X, Y>(opt: Optional<X, Y>): LeftRight<X, Y> { return opt.type === 'absent' ? new Left(opt.detail) : new Right(opt.value) } function unvisitify<X, Y>(opt: LeftRight<X, Y>): Optional<X, Y> { return opt.accept({ visit(value: Left<X> | Right<Y>) { return value instanceof Left? {type: 'absent', detail: value.x} : {type: 'present', value: value.y} } }) } The main difference with the usual visitor pattern is that the usual visitor pattern doesn't return anything (it expects you to be holding some mutable state and the visitor will mutate it), you can do that too if you don't have access to a suitable generic for the Z parameter.
Hackbraten 2y ago
Maybe I'm spoiled by TypeScript but this is how I'd do it in a structural typing system: type ConstrainedByW = | { w: false, x: false } | { w: true, x: bool } type ConstrainedByY = | { x: bool, y: false, z: bool } | { x: true, y: true, z: false } type ProgramState = ConstrainedByW & ConstrainedByY
- jandrese 2y ago
  Yes, but certainly you can see how even a toy example with just 4 booleans is already getting complicated?
  - Hackbraten 2y ago
    It's certainly complicated. But not WTF-level complicated. Complexity is both subjective and relative. Allowing invalid states in your model is going to complicate things, too. I wouldn't mind having this example in production. It will scale just fine with the number of booleans.
aiono 2y ago
enum program_state { X_W, Y_X_W, Z, W, Z_W, Z_X_W, } You only have these 6 options. And in this case you can easily use a SAT solver to generate the cases for you so that you don't have to write them by hand.

keybored 2y ago

And the Make Impossible States Unrepresentable crowd program like that?

WorldMaker 2y ago
It is not too bad in languages with discriminated unions. It's also not hard to fake discriminated unions in languages without them, even if you will miss some of the niceties. Rather than thinking of it as an enum, think of it as a list of contructors: class ProgramState { bool w, x, y, z; ProgramState(x, z) // implies y = true, w = true ProgramState(w, z) // cannot set x; implies y = false (cannot set y) } Even if the class needs all four fields, internally to represent all the possible combinations of data, there's no constructors/setters to work with them independently. (Which is also related to why "Make Impossible States Unrepresentable" also generally implies immutable, no setters at all makes it much easier to make states impossible.) In languages with discriminated unions you might even have some natural field sharing depending on how your "constructors" are written and the memory expansion isn't necessarily "exponential".
- crdrost 2y ago
  Also to mention it, languages without discriminated unions often have generics and function types, which can be used to build discriminated unions with Church encodings: // idiomatic typescript type Optional<IfAbsent, IfPresent> = | {type: 'absent', detail: IfAbsent} | {type: 'present', value: IfPresent} // Church-encoded version type Either<x, y> = <z>(ifLeft: (x: x) => z, ifRight: (y: y) => z) => z // isomorphism between the two function church<x, y>(opt: Optional<x, y>): Either<x, y> { return (ifLeft, ifRight) => opt.type === 'absent'? ifLeft(opt.detail) : ifRight(opt.value) } function unchurch<x, y>(opt: Either<x, y>): Optional<x, y> { return opt<Optional<x,y>>(x => ({type: 'absent', detail: x}), y => ({type: 'present', value: y})) } In addition the Church encoding of a sum type, is a function that takes N handler functions and calls the appropriate one for the case that the data type is in. With a little squinting, this is the Visitor pattern. interface LeftRightVisitor<X, Y, Z> { visit(x: Left<X>): Z visit(y: Right<Y>): Z } interface LeftRight<X, Y> { accept<Z>(visitor: LeftRightVisitor<X, Y, Z>): Z; } class Left<X> implements LeftRight<X, any> { constructor(public readonly x: X) {} accept<Z>(visitor: LeftRightVisitor<X, any, Z>) { return visitor.visit(this) } } class Right<Y> implements LeftRight<any, Y> { constructor(public readonly y: Y) {} accept<Z>(visitor: LeftRightVisitor<any, Y, Z>) { return visitor.visit(this) } } // isomorphism function visitify<X, Y>(opt: Optional<X, Y>): LeftRight<X, Y> { return opt.type === 'absent' ? new Left(opt.detail) : new Right(opt.value) } function unvisitify<X, Y>(opt: LeftRight<X, Y>): Optional<X, Y> { return opt.accept({ visit(value: Left<X> | Right<Y>) { return value instanceof Left? {type: 'absent', detail: value.x} : {type: 'present', value: value.y} } }) } The main difference with the usual visitor pattern is that the usual visitor pattern doesn't return anything (it expects you to be holding some mutable state and the visitor will mutate it), you can do that too if you don't have access to a suitable generic for the Z parameter.

Hackbraten 2y ago

Maybe I'm spoiled by TypeScript but this is how I'd do it in a structural typing system: type ConstrainedByW = | { w: false, x: false } | { w: true, x: bool } type ConstrainedByY = | { x: bool, y: false, z: bool } | { x: true, y: true, z: false } type ProgramState = ConstrainedByW & ConstrainedByY

jandrese 2y ago
Yes, but certainly you can see how even a toy example with just 4 booleans is already getting complicated?
- Hackbraten 2y ago
  It's certainly complicated. But not WTF-level complicated. Complexity is both subjective and relative. Allowing invalid states in your model is going to complicate things, too. I wouldn't mind having this example in production. It will scale just fine with the number of booleans.

aiono 2y ago

enum program_state { X_W, Y_X_W, Z, W, Z_W, Z_X_W, } You only have these 6 options. And in this case you can easily use a SAT solver to generate the cases for you so that you don't have to write them by hand.