5 ms·

> Make illegal states unrepresentable This is a nice ideal to shoot for, but strict adherence as advocated in the article is a short path to algorithmic explos

• MeetingsBrowser 2y ago
  The mistake here is having 2^16 valid options. If you truly do have 2^16 valid and distinct behaviors, it is not possible for humans to correctly write 2^16 different code paths anyway. More than likely, the majority of the combinations of your 29 Boolean flags are invalid. You should strive to have that checked by the program, and not only as a note in external documentation. No one is saying int should be turned into an enum.
  • joe_the_user 2y ago
    The parent is discussing a situation where you have 16 distinct, binary states many but not all of which are mutually compatible. So you can have 16 bit vector of the states, 16 binary variables or an enum of valid states - the enum would have O(2^16) members because of the distribution of valid states but unlike the others, an invalid state would not be possible to represent.
  • jandrese 2y ago
    You only have 20 options, but making that many distinctive options is not exactly a stretch. It's not like every single set of options is its own code path, most options represents a small deviation at one particular part of the code. Most of the options aren't mutually exclusive either, only a few combinations are illegal. Imagine a simple shipping system for example. The package might be routed via truck, boat, plane, pipeline, foot, etc... Probably even a combination of those options. The package might be low, medium, or high priority, although high priority packages are not allowed to be delivered by boat. The package might be small, large, or liquid, but liquids can't be delivered by foot. There are 195 different countries with even more regulatory regimes to consider, some of which may have different customs requirements based on mode of transport. Now imagine a problem that is actually complicated. The idea of encoding all of this business logic into the datatype is a road to madness IMHO. Especially if the rules can change on you and require you to rework your datatypes to match. On the small scale this makes a lot of sense and is good advice, but strict adherence is impractical.
    • MeetingsBrowser 2y ago
      You don't need a single type to represent the entire program state. We probably both agree that separate types for shipping methods, priorities, size, country makes sense. The API can be designed to prevent illegal transitions between types to arrive at an invalid state. The exact implementation depends on the language. > The idea of encoding all of this business logic into the datatype is a road to madness IMHO The alternative is hoping that every developer remembers not to violate any of the implicit and unenforced rules. If the system is too complicated to be represented in code, can a human realistically hold the entire state machine in their head as they make changes?
• keybored 2y ago
  Where does this exponentional size requirement come from?
  • jandrese 2y ago
    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.
• yazzku 2y ago
  If you only have 3 states, then yes, that should be an enum, not a pair of booleans, because you have 3 states, not 2x2 independent ones. Making the 4th state unrepresentable removes code and error checking. It's also just simple domain modeling. Your latter example needs context. In what situation have you had an enum with 2^16 states? In any case, if you generally have a reasonable number of booleans, with some states being logically invalid, then you'll need error checking on those anyway. Leaving them as booleans gives you the ability to monkey-patch things later in an ad-hoc manner, which is useful when you're still in a prototyping phase and the requirements aren't clear (and you could argue that this is almost always the case in many problem domains; I think that would be valid criticism.) But if you've already modeled the domain and you want any assurance of correctness, then I don't see why you wouldn't enforce the constraints at the type level. Your criticism seems to me the usual trade-off between strong static typing and dynamic and/or weak monkey-typing.
• joe_the_user 2y ago
  This is an excellent illustration. I feel functional programming provides great tools and concept for a cohesive system (one with consistent requirements, which accomplishes a single thing, etc). But many programs you write involve parts that aren't very cohesive and trying to make them cohesive is far more work than just bolting on a case statement or similar things. Parent currently downvoted without comments. Seems like a sad way to respond.
  • kccqzy 2y ago
    I feel like you might be missing the point. A case statement is not to be treated as something you bolt on as a hack. It is the right tool for the job the vast majority of the times. When you use case statements, you refine and reduce your state space. It makes code easier to understand. When you combine this with the idea of making illegal states unrepresentable, a case statement gives you an exhaustive listing of what could happen. Even a lot of Haskell programmers, after using things like the `maybe` function to eliminate Maybe types and things like `fmap` over Maybe, eventually find that using case expressions produces the clearest code even though it may be one line longer. I really hope HN enforces a rule that a downvote must be accompanied by a reply.
• kccqzy 2y ago
  Nobody says you have to have a single enum type containing all the combinations. Chances are, you can use sum types (discriminated unions) to factor things nicely if you think about them. For example if option B is only relevant when option A is set to true, you can have something like data OptA = ATrue OptB | AFalse data OptB = BTrue | BFalse There are three valid combinations but no type has three alternatives. Nobody in their right mind would write out an enum with 2^16 cases. If you do, you are misusing enums and it's time to consider other tools in your language.
  • joe_the_user 2y ago
    Nobody says you have to have a single enum type containing all the combinations. No, no one would continue up to 2^16 and the code would get unmanageable long before that. But it's illustration of the problems starting out dealing with the invalid states of two variables using an enum because what happens when more and more variables arrive? Sure, the standard answer is "just refactor" but my experience is no client or boss wants to hear "adding this small state is going require a lot of change" and a trickle of binary conditions is a very common occurrence as is code expanding to handle these (and become excessively complicated). Chances are, you can use sum types (discriminated unions) to factor things nicely if you think about them. Maybe you have a good chance of combining these binary conditions in a good way. But I mention you've substituted a hard problem instance (factoring binary conditions) for an easy problem instance (checking binary conditions). Functional programming has a weird dual personality where on the one hand you hear "A functional programmer is always a smarty and solve hard problems as a matter of course" but also you hear "functional programming would be the dominant paradigm if only ... we taught people young so they wouldn't have their bad procedural habits"
    • BoiledCabbage 2y ago
      > and a trickle of binary conditions is a very common occurrence as is code expanding to handle these (and become excessively complicated). But you still have to handle this in your code. Wherever you have your conditions that handle this, your nest of if statements still need to cover all of these invalid combinations and ensure your app doesn't silently do the wrong thing or just crash (better). Changing requirements requires changing code. I don't think it's a valid argument to say "we shouldn't take that approach because as requirements change we'll have to change the code". That's essentially software development. Practically if you don't want to use enums and want another option, use a "builder" object. Pass in all of your booleans there and have it do you validation when you call its build method. It returns a read only configuration that the rest of your system can use, and the build method fails if an invalid combination of flags are passed in. Again you force only valid combinations to exist after you call "build". And all code relies on the config produced by the build method.
• galaxyLogic 2y ago
  True. And what is an "illegal state" anyway? If two options are "mutually incompatible" it means that they, as far as we know, so far, have never occured at the same time. But that is just how things are currently. The world may change. And it's important to strive for maintainable code that can accommodate such change easily. Expanding company operations to work in a different country is an example of this (our) "world changing". States that never occur together here, may occur together there. Or in the future more generally. So, making illegal states non-representable is about avoiding errors in respect to the system specification. But it does not take into account the fact that in the real world specifications typically evolve and change even during development, and perhaps more so later.
  • thfuran 2y ago
    So, what, you’d advocate declaring all function parameters and returns as void* to maximize flexibility with respect to future changes in requirements?
    • galaxyLogic 2y ago
      No of course not. Just that we shouldn't forget that "specs" can change and typically do. Keep an open mind.. Never say "never". Illegal states can become legal.
• reval 2y ago
  This is technically correct but disingenuous. This reminds of the climate change comic where a scientist asks “What if climate change is a big hoax and we create a better world god nothing?”
• aiono 2y ago
  In this example, is it really the case that all 20 are dependent into each other so you have to combine all of them into a single enum? For the ones that are independent you can keep them as booleans and you should.