Imagining a Language without Booleans
Let’s start where I started. Just thinking about if statements.
An if with an else can produce a value:
// C int x = - 5 ; int abs_x = x > 0 ? x : - x ;
# Python x = - 5 abs_x = x if x > 0 else - x
// Rust let x = - 5 ; let abs_x = if x > 0 { x } else { - x };
What about an if without an else ?
// C int x = - 5 ; int abs_x = x > 0 ? x ; // Syntax error!
# Python x = - 5 abs_x = x if x > 0 # Syntax error!
// Rust let x = - 5 ; let abs_x = if x > 0 { x }; // Type error -- evaluates to ()!
No dice.
Optional if
I realized that there is a meaningful value for if (x > 0) x , though. It’s Option :
// Hypothetical-Lang let x = - 5 ; let pos_x = if ( x > 0 ) x ; // = None let y = 7 ; let pos_y = if ( y > 0 ) y ; // = Some(7)
(This hypothetical language will look a lot like Rust, but with different syntax for if since we’re giving it a different semantics.)
In general, if the conditional evaluates to true then the if evalutes to Some , otherwise it evaluates to None :
if (true) e ⟼ Some(e) if (false) e ⟼ None
So the type of if is that it takes a bool and a T , and produces an Option :
if (bool) T : Option
(That is to say: if expr_1 has type bool and expr_2 has type T , then if (expr_1) expr_2 has type Option .)
This generalized if could be used to perform an operation that’s only valid when the conditional is true:
fn strip_prefix ( string : & str , prefix : & str ) -> Option <& str > { if ( string . starts_with ( prefix )) & string [ prefix . len ()..] }
or in conjunction with a method like filter_map :
let numbers = vec ! [ 9.0 , - 20.0 , 16.0 , - 16.0 ]; let square_roots = numbers . into_iter () . filter_map ( | x | if ( x > 0 ) x . sqrt ()); assert_eq ! ( square_roots . next (), Some ( 3.0 )); assert_eq ! ( square_roots . next (), Some ( 4.0 )); assert_eq ! ( square_roots . next (), None );
Optional else
There’s a matching interpretation for else . It’s type is:
Option else T : T
and its evaluation rules are that:
None else e ⟼ e Some(x) else e ⟼ x
So it supplies a default for an option:
fn get_name ( personal_info : & HashMap < String , String > ) -> & str { personal_info . get ( "name" ) else "Whoever you are" }
(This is exactly the behavior of Rust’s unwrap_or_else() , except that you don’t need to manually wrap the expression in a closure.)
Of course, you usually pair an else with an if . This continues to work like you’d expect, as you can check using the type rules:
let abs_num = if (num > 0) num else -num; -------- --- bool i32 ---------------- ---- Option i32 --------------------------- i32
Notice what we’ve done: we’ve turned both if and else into binary operators.
Optional and and or
Can we go further? What about and and or – can they work on options? They would take options, and return options.
or will take the first option if it’s Some , or otherwise take the second. You could use it to try multiple options each of which may or may not succeed:
fn get_color ( attrs : & HashMap < String , String > ) -> Option <& str > { attrs . get ( "color" ) or attrs . get ( "colour" ) }
and will take the second option, so long as the first option was Some . You could use it to try something but only if a condition holds. For example, if you wanted to parse a hex color like "#a52a2a" if a string starts with # , or a color name like "brown" otherwise, you could write:
fn parse_color ( color : & str ) -> Option < Color > { ( color . starts_with ( "#" ) and parse_color_hex ( color )) or parse_color_name ( color ) }
More formally, and and or would have the evaluation rules:
None and e ⟼ None Some(x) and e ⟼ e None or e ⟼ e Some(x) or e ⟼ Some(x)
and the type rules:
Option and Option : Option Option or Option : Option
(This makes and and or equivalent to Rust’s and_then and or_else .)
If you have good mathematical intuition you might notice the asymmetry between the type rules for and and or and suspect that we’re missing some sort of generalization. Don’t worry, it will come.
But booleans?
But wait! You still need to be able to use and and or inside an if ’s condition, for example if (x >= 0 and x < len) . That doesn’t work if and produces an option!
There’s an easy fix, though. There’s an equivalence between booleans and options:
bool = Option<()> true = Some(()) false = None
So we could eliminate booleans from our hypothetical language, and always use the equivalent options instead.
Putting it all Together
Now let’s imagine what a programming language without booleans might look like.
We just talked about replacing bool with Option<()> , because those types are equivalent. But there’s a further equivalence with results, as well:
Option = Result bool = Option<()> = Result<(), ()>
If we’re going to use the equivalence between booleans and options, we might as well go all the way and use the equivalence between options and results. Results everywhere!
Since they’ll be so ubiquitous, let’s invent a short syntax for them. T ? E can mean “either a successful value T , or an error E ”. What Rust would call Result .
Then bool is a type alias for ()?() . Except… that looks like an ASCII drawing of a fly’s face. So let’s call the unit value (and the unit type) nil instead. Then we have:
bool = nil?nil true = Ok(nil) false = Err(nil)
These will be aliases built into the language.
Writing all of the type rules from before but using results instead of options, we have:
if (A?E) B : B?E A?E else A : A A?E and B?E : B?E A?E or A?F : A?F not A?E : nil?nil
(There’s the nice symmetry that was lacking before.)
And writing all of the evaluation rules:
if (Ok(x)) e ⟼ Ok(e) if (Err(x)) e ⟼ Err(x) Ok(x) else e ⟼ x Err(x) else e ⟼ e Ok(x) and e ⟼ e Err(x) and e ⟼ Err(x) Ok(x) or e ⟼ Ok(x) Err(x) or e ⟼ e not Ok(x) ⟼ false not Err(x) ⟼ true
(I’m not really sure whether if (A?E) B is the right type, or if if should require its conditional’s error to be nil , like if (A?nil) B .)
Now we can start to imagine what conditionals in this language might look like.
else if
We’ve replaced if and else with binary operators, so we should verify that else if still works the way it’s supposed to:
let sign = if ( n > 0 ) 1 else if ( n < 0 ) - 1 else 0 ;
It does, so long as else is right associative. That is, the grouping needs to be like this:
if (n > 0) 1 else if (n < 0) -1 else 0 ------------ ------------- -------------------- --------------------------------------
or if
Surprisingly there’s another way to write multi-way conditionals:
let sign = if ( n > 0 ) 1 or if ( n < 0 ) - 1 else 0 ;
This behaves exactly the same as else if ! It’s relying on the or binding tighter than the else :
if (n > 0) 1 or if (n < 0) -1 else 0 ------------ ------------- ----------------------------- ------------------------------------
It took me a bit to get past my “WTF” reaction, but now I kind of like saying “or if”.
true and false
Remember that true and false are simply shorthands for Ok(nil) and Err(nil) . So you can write:
fn delete_file ( path : FilePath ) -> nil ? IOError { if ( not file_exists ( path )) return true ; ... }
and:
fn pop ( vec : & mut Vec < i32 > ) -> i32 ? nil { if ( vec . len == 0 ) return false ; ... }
is
It’s very useful to be able to bind a pattern inside a conditional. Rust uses the syntax if let for this; let’s use the syntax is instead:
fn parse_and_clamp ( s : & str , min : i32 , max : i32 ) -> i32 ? nil { if ( parse_num ( s ) is Ok ( n )) { if ( n < min ) min or if ( n > max ) max else n } }
try / else
Python lets you put an else clause after a for loop. The else clause runs if the for loop doesn’t break . For example:
for elem in list : if predicate ( elem ): print ( "Found!" , elem ) break else : print ( "Not found :-(" )
There’s a natural extension of this in our hypothetical language – a for loop can break with a value, and prodcues Ok if it does:
fn find ( list : & Vec < i32 > , predicate : fn ( i32 ) -> bool ) -> i32 ? nil { for elem in list { if ( predicate ( elem )) break elem ; } }
This can be composed with our existing else construct:
fn find_with_default ( list : & Vec < i32 > , predicate : fn ( i32 ) -> bool , default : i32 ) -> i32 { for elem in list { if ( predicate ( elem )) break elem ; } else default }
Fewer Ok s and Err s
Many functions which would require wrapping their result in Ok or Err or Some if they were written in Rust, no longer require that. For example, parsing a boolean in Rust:
fn parse_bool ( s : & str ) -> Option < bool > { if s == "true" { Some ( true ) } else if s == "false" { Some ( false ) } else { None } }
vs. in our hypothetical language:
fn parse_bool ( s : & str ) -> bool ? nil { if ( s == "true" ) true or if ( s == "false" ) false }
Real Messy Examples
All the examples so far have been short. Let’s look at some real code, code from deep inside the guts of my personal projects. No need to understand what it does (I certainly don’t remember the details), we just need to rewrite it in this hypothetical language and see how it compares.
Here’s one snippet:
if ! node . can_have_children ( s ) { return None ; } if let Some ( last_child ) = node . last_child ( s ) { Some ( Location ( AtNode ( last_child ))) } else { Some ( Location ( BelowNode ( node ))) }
which can now be written as:
if ( node . can_have_children ( s )) { if ( node . last_child ( s ) is Ok ( last_child )) Location ( AtNode ( last_child )) else Location ( BelowNode ( node )) }
And other example:
if let Some ( menu ) = & mut self . active_menu { if let Some ( key_prog ) = menu . lookup ( key ) { return Some ( KeyLookupResult :: KeyProg ( key_prog )); } if let Some ( ch ) = key . as_plain_char () { if menu . execute ( MenuSelectionCmd :: Insert ( ch )) { return Some ( KeyLookupResult :: Redisplay ); } } } else { let layer = self . composite_layer ( doc_name ); let keymap = layer . keymaps . get ( & KeymapLabel :: Mode ( mode )); if let Some ( key_prog ) = keymap . lookup ( key , None ) { return Some ( KeyLookupResult :: KeyProg ( key_prog )); } if mode == Mode :: Text { if let Some ( ch ) = key . as_plain_char () { return Some ( KeyLookupResult :: InsertChar ( ch )); } } } None
would be written as:
if ( & mut self . active_menu is Ok ( menu )) { if ( menu . lookup ( key ) is Ok ( key_prog )) { KeyLookupResult :: KeyProg ( key_prog ) } or if ( key . as_plain_char () is Ok ( ch ) and menu . execute ( MenuSelectionCmd :: Insert ( ch ))) { KeyLookupResult :: Redisplay } } else { let layer = self . composite_layer ( doc_name ); let keymap = layer . keymaps . get ( & KeymapLabel :: Mode ( mode )); if ( keymap . lookup ( key , false ) is Ok ( key_prog )) { KeyLookupResult :: KeyProg ( key_prog ) } or if ( mode == Mode :: Text and key . as_plain_char () is Ok ( ch )) { KeyLookupResult :: InsertChar ( ch ) } }
Notice that this loses the need for wrapping the results in Some and the need for early return statements.
Conclusion
This sure seems to be a coherent design! It will certainly influence how I think about conditionals.
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. Let me know if you’ve seen anything more similar.