Imagining a language without booleans | Hacker News Reader

Imagining a language without booleans

justinpombrio.net

77 pointstodsacerdoti73 comments

Now that we have defined a language without booleans, we need some way to coalesce these optional values

We ideally want an infix function that can reduce the "truthiness" of two values.

Let us imagine this language is a Haskell-type-thing, and we can define pseudo-operators with pattern matching

    infixr 3 &&
    (&&) :: Optional -> Optional -> Optional
    Empty && _       = Empty
    _ && Empty       = Empty
    Some A && Some B = Some A
    _ && _           = Empty

    infixr 2 ||
    Some || _     = Some
    None || Some  = Some
    None || None  = None
    _    || _     = None

Hmm, let's see how that looks

    a = b && c
    d = e || f

The good news is that we are free from the tyranny of booleans. The bad news is that we just reinvented JavaScript :-)

That second operator is the <|> operator, from the Alternative typeclass.

The first one has some arbitrariness (do you take the left or right value if both are Just). But, thankfully the Applicative typeclass gives both <* and *>, which lets you choose which value you want:

  Just A <* Just B = Just A
  Just A *> Just B = Just B

(There's the possibility to merge values too, with f <$> Just A <*> Just B, which evaluates to Just (f A B). I feel like this is a "don't try to understand it, just get used to it" sort of syntax. It can be pretty convenient though.)

> The bad news is that we just reinvented JavaScript :-)

There's a whole lot more to JavaScript typing that makes it JavaScript.

After all, Python does this too (but the spellings are "and" and "or").

The big difference being that ‘truthiness’ is explicitly encoded next to the value rather than being an inherent property of certain values. That's a win in my book!

> invented JavaScript

Good Job! Now do the "no scalar values" challenge. FP fanbois gonna love the unwrapping.

I honestly really like those two operators in js.

Don't forget about ?? as well

I'm a big fan of the Elvis operator myself (.?)

.? is null-safe property access. Elvis is ?:

Oh, that makes more sense, because ?: has eyes

https://en.m.wikipedia.org/wiki/Elvis_operator

?:-)

Mmm nullish coalescing

Really cool post. I've had roughly similar thoughts when noodling on my current hobby language [1], but didn't work all the way through it to see if it hangs together. It seems like it might!

> Let me know if you’ve seen anything more similar.

If you take static typing off the table, then Icon's goal-directed execution is very much an inspiration in this area.

[1]: https://journal.stuffwithstuff.com/2023/01/03/type-checking-...

Icon was the first thing I thought of as well. I wonder about Prolog…

And Verse.

Which was mentioned in the original article.

Unfortunately, you're invariably going to end up with a "Some<false>" at some point, and you're going to spend the next 20 years explaining to people why that's not a wart in your language that your if "treats it as true", no matter how much you say "my language doesn't even have true so that's not a valid statement".

It isn't going to matter that it's technically a "JSON::false" or whatever... you're still going to get people calling that a wart forever. ("But a JSON::false would be a None" - no, you need that for either "null" or "missing". A JSON library has to have an exposed "false" value to distinguish it from null and missing, both for input and output.)

I'm not saying that doesn't mean to try this out, but as more of a heads up and something to talk about explicitly in the eventual tutorial.

Personally, I find myself fairly satisfied with if statements rigidly requiring a boolean and refusing to have a concept of "truthiness", which I consider a mistake, and I'm not sure this is solving real problems I've had. A user can always write the Option vs. None themselves in an if statement with mandatory else if they want. This introduces a wrapper level of Option that may not always play nice in real code (I mean, a lot of sum type types essentially already have it built in with things like "type Color = Red | Blue | Green | Unspecified" where adjoining a None is often unnecessary) and may really tempt you towards a concept of truthiness that may be a bigger wart than when you're trying to fix. It's pretty hard for a computer programming language to essentially evict the concept of a "bit" from the language. I'm not sure it can be done in practice, but it's fun to think about it and I encourage the pondering.

I admit I didn't read all of your commment.

But is

  Some<false>

different from

  Maybe<false>

? Is it a type-level construct to express a predicate like

  Array.prototype.some

In any case, optional types containing boolean values are definitively an anti-pattern.

And in cases where it's prudent to check for the "presence" of a property containing a

  Maybe<ObjectReference>

, while using coercion, it does not make sense to distinguish false from "falsy".

TypeScript's dynamic narrowing has become pretty comprehensive when it comes to this kind of issue.

Still, Option<Boolean> types are bad in most contexts I think, especially in languages like JS.

Instead of using boolean | undefined , I much prefer explicit defaults (parameters) or properties being declared every time (data).

Some<false> was written as the value; the type of that value would be Option<(Some Sort Of Still-A-Boolean)>. I have to write it that way because the entire conversation is about the language not having a boolean, so you can't properly write Option<bool> as a type in that language, which is why I mention it may actually be JSON::boolean or something, as well as several other booleans in other similar situations. My point is that you'll still end up with booleans in them though because you'll still have to have representations of other thing's booleans anyhow.

Thanks for coming back to my comment and explaining!

I don't really get it.. In one of the last example's he writes:

` if (node.last_child(s) is Ok(last_child))`

Is the part between the () not ultimately the same as a boolean expression? Like he wrote his own implementation of if/else syntax?

Also in the beginning he says: "An if with an else can produce a value", but isn't this just 'syntactic sugar'? I think the code that actually runs is the same as if you'd write if (value x = some_value) {value = something} else {value = something_else} ?

About the `if else` producing a value matter. Well, if you look at things that way, C can be said to be syntactic sugar of assembly, as for every C program you can write equivalent assembly. `if else` producing value is very useful because it allows you to write if else wherever a value is expected. You can call methods on an `if else` or pass one as an argument of function. When such an expression is sufficiently complex your equivalent code using non-value-producing `if else` would be a lot more verbose and unreadable.

This is equivalent to the `if let` syntax of Rust. In Rust at least this is treated as a special syntax but not a boolean. I once complained it's kinda confusing that it makes one think the `let` pattern matching syntax is a boolean expression which it is not, and the Rust people replied to me saying yeah it can be a boolean maybe at some point in the future. So yeah whether such syntax makes pattern matching a boolean really is just a matter of whether it's said to be one.

This concept doesn't require the Law of Excluded Middle that classical boolean values do.

Ah alright, since I don't know what that is I will attribute it to my own lack of knowledge then.

Basically, the Excluded Middle is for things neither True nor False.

Yeah okay I get it. The law basically states that 'not true' should be 'false' and vice versa.

I still don't get what's the use of this, or is this just a curiosity? It seems like the result is just a kind of ternary operator? Doesn't this still just compile to if(x.present) return x else y? Just with really obtuse syntax

If you are doing proofs then the law of the excluded middle creates paradoxes. "this statement is false" is a paradox with the law but isn't without the law. In a programming language not used for proofs? Then yeah it is just for fun.

https://en.wikibooks.org/wiki/Haskell/Understanding_monads/M...

This looks homeomorphic to the Maybe monad.

isomorphic?

homeo implies continuity

And continuous inverse! I was just being silly, you're right of course.

Definitely a fun alternative-history! It's a nice take to see `Option`s or `Result`s as a step towards logic programming. Typically once you introduce loops you need to have a way to combine `E`s; the way to represent an ordered set of things e.g. to be combined is to return a list of things, and then you're in logic programming world. [1]

[1]: https://wiki.haskell.org/Logic_programming_example

It's a bit weird to me that the result `not` discards the content of the value rather than just swapping its truthiness (not A?E : E?A).

> The closest thing I’ve seen is fallible expressions in Verse, but those are pretty different because they (i) don’t assign a value to an if without an else, and (ii) involve speculative execution.

Traditional ifs, and the ifs here, also involve speculative execution :) (i.e. execution that happens regardless of which branch you end up on). It's just delimited by the brackets of the if condition (a ‘failure context’ in Verseland). It's true that traditionally logic languages don't assign a value to failure. I guess algebraic effects (of which `Result` can be an example) can be seen as a generalization of failure in that way.

Amr Sabry &a. also have an interesting notion of ‘failure with value’ as the semantics of their negative types: https://dl.acm.org/doi/abs/10.1145/3434290 , http://lambda-the-ultimate.org/node/4964 (LtU for an older paper from the programme).

Basically Emacs Lisp. Where `nil` is the only falsy value, and anything else (including `t`, which analogizes to `Some(())`) are truthy values.

If you're looking to imagine a world without bools, do some branchless gpu shader coding. Certainly its a different way to think about processing data.

> do some branchless gpu shader coding

A mask array is just a bunch of boolean, and follows boolean math, because it is boolean values. A boolean type does not make a boolean value, it being two state does.

I've also seen (non-GPU) programs use numbers with multiplication, instead of if-else, as a means of preventing CPU branch stalls. This technique is sometimes called branchless programming.

So basically, C before version C99

Technically C23. _Bool is just a fancy substitute for unsigned char and "casting" with the !! sequence.

Imagine a language that not only doesn't have booleans, it only has positive fractions. It also doesn't have any keywords, yet it is Turing-complete.

Struggling to imagine it? Don't worry. John H Conway has done it for you.

https://en.wikipedia.org/wiki/FRACTRAN

In FRACTRAN, Bools is all you get.

The value is 6 is a:true, b:true, c: false, d: false, etc..

I love fractran tho, I must have written a thousand lines of it this year alone.

Booleans are a remnant of limited RAM.

2025, we can all just use integers and carry one less variable type in our sack.

Next we replace integers with floats and we’re done. 3 birds, 1 stone.

Floats are an excellent choice because they encode the inevitable ambiguity of the world. Instead of true and false we can have

    true    = 1
    false   = 0
    perhaps = 0.5

Tracking the accumulated 'perhaps'ness... "Essentially, each Ball Arithmetic number carries with it an explicit Radius that describes the interval which contains the true value. Because Ball Arithmetic data propagates throughout a calculation and is never demoted to a lower datatype, its advantage is that after each operation the resulting Ball reliably includes the true answer. Across an entire algorithm, the final result is a Ball that indicates explicitly how precise it is, thus eliminating the guesswork as to the effect on the algorithm of the inexactness of the input and any other inexact constants used"

- NARS2000 dialect of APL, Ball / Interval arithmetic: https://wiki.nars2000.org/index.php/Ball_Arithmetic

Addendum: «nevermore == -1» for «no value».

And now you've invented Church (among others)!

We could just use strings for everything, like bash, and tcl, and the weird scripting language embedded in every mid-2000s FPS game.

Why not only have strings? "zero", "one", "two", ... "threepointonefourone..."

Congratulations, you have invented tcl

Perl, awk, tcl, bash - all string based langs. Especially TCL

The nice part about floats is the bit packing is usually standard, meaning you can have them hold arbitrary data, if you sacrifice a couple of bits!

There's a robot controller that I work with that has a large number of calibration tables, of float32 values. This is where I store the json! :D

We could just use 2 integers for floats and not deal with inaccuracies. Even easier.

Floats can represent faaar bigger span than two integers. 2*10^-308 to 2*10^+308 is gonna require you 1024 bits or 32 integers. Now those 32 integers would represent that value exactly instead of rounding a few decimals, but some maths prefer approximate large span over exact values.

> Booleans are a remnant of limited RAM.

I highly doubt that. Let's call a boolean that is represented as one bit "true boolean type" Since no instruction set (that i'm aware of) has boolean operators, a "true boolean" would require every operation on it to evaluate to multiple bit-wise operations, which take up registers and cycles. Flags in registers are "true boolean", but they're usually operated on explicitly like int with bit-wise operators.

There is also the issue of bit alignment, atomic access, and stack and heap allocations being byte based; further restricting how a language that had "true booleans" would be able to actually be able to work with them.

I know that there are some languages that allow boolean arrays to be packed tightly as "true boolean", but that is a rare exception. Even char and byte types has this issue sometimes, but are more commonly "properly packed".

> we can all just use integers

So it's all integers already. The most common implementation of boolean around is probably #define true 1

But we really should use enums more instead of boolean. "fail, success, bad_param, error_404" is equally efficient to return as a bool.

> Next we replace integers with floats.

No. (well python and JavaScript kinda does already, but no) https://en.wikipedia.org/wiki/Pentium_FDIV_bug

Your argument against floats is a bug from 30 years ago? That's probably the weakest possible reason you could have given.

I love seeing these kinds of explorations in the realm of language design. I've wondered about expanding the notion of boolean operators like this. For all its flaws, one thing I've always liked about JS is the overloaded (||) and (&&) operators. It's really slick to write something like `foo.get_that_can_fail(x) || "default value"`.

This:

  bool  = nil?nil
  
  true  = Ok(nil)
  false = Err(nil)

is still booleans.

Icon and Verse use failure (backtracking!) as false and all values as true, but you still have conditionals and boolean logic even though you don't (or may not) have a boolean type.

Perhaps it’s cheating, but last I checked, Gleam has no “if”, only “match”. With that, and in languages with sum types, you can easily define your own boolean and boolean-adjacent types.

If null, you have booleans: null or not null. :)

I'm pretty sure Ruby already does this. if statements are expressions that return a value and return nil if there is no else.

(Also 0 == true in Ruby. Only false or nil are not true.)

Most dialects of BASIC didn't have booleans.

Everything old is new again.

And most assembly languages don't have general-purpose booleans. And C89 doesn't have booleans. And FORTHs don't have booleans in the base interpreter, those are words defined like any other.

Most BASIC dialects map booleans to integers with zero is false, non-zero is true and -1 is the canonical true result of boolean operators, so I think they effectively have booleans.

> Can we go further

Yes. we can get a Lisp background to get a better rounded and wiser perspective on all these topics.

funny, I've been toying with the idea of a language with only booleans

Wouldn’t that just be logic gates, Mealy and Moore machines written in text form?

Yes. Except, the language should be expressive enough that you can build abstractions and write "normal" code. And, the compiler should be smart enough to emit efficient native code for your target arch (and not doing FPGA-style hardware synthesis)

Well, that’s true and false.

Too good to be true or false

Perl

Not really without. More like obscured booleans, 2 embeds into T+1 which embeds into T+U. I mean C used the sign bit to do the same.

I can. it's called Erlang. true an false are just atoms.

Headline no bit. Then attack if.

There would be no branching if there were no "if". It's basic assembly. Not jumps. No loops.

Yes, I think it really only works in a side-effect free language. Otherwise after the first "failure", while every resulting value also turns to None, allocation, file access, database calls still happen, so you are now in a weird limbo state where everything was done, but no handle retained and in a weird position in control flow, kind-of between the lines, which isn't expressed by any of your code.

The operations could be short-circuiting.

Reply on news.ycombinator.com