from Hacker News

A Language Without Conditionals

by JeanPierre on 2/10/13, 4:53 PM with 43 comments

by epidemian on 2/10/13, 11:55 PM
The author is not complying with their own requirements:
> Pattern matching and polymorphism is not allowed
Using dynamic dispatch on different functions of type Int -> Int is, precisely, polymorphism. Doesn't look much like the OO polymorphism that some people are used to, but FP folks use this kind of functional polymorphism all the time.
That being said, the main premise of the article is quite valuable: yes, you can program with no conditionals. And i think it's quite useful to know that polymorphism can be used like that without suffering too much of an unfriendly syntax (see lmm's comment on Smalltalk: http://news.ycombinator.com/item?id=5198419).
Finally, although pattern matching can be seen as an overpowered if-statement, the relation can be also turned around: the if-statement is a special case of pattern matching. I won't say that pattern matching is not conditional statements, but i think it's also quite valuable to notice that you can use pattern matching as a new programming primitive instead of the if-statement. For example, the if-statement implemented in Haskell:
```
  if :: Bool -> a -> a -> a
  if True  x _ = x
  if False _ y = y
```
Relying only on pattern matching instead of conditional if-statements can make quite the difference on how one reasons about programming problems (e.g. Prolog and declarative programming in general).
by philwelch on 2/10/13, 6:01 PM
So you just end up using function pointers and arrays to fake polymorphism. If you have the requirement that every part of a function has to be evaluated, you just end up branching between function calls rather than eliminating branching. This is vaguely reminiscent of how some functional languages use tail-recursion instead of loops--they don't eliminate iteration, they just express it a different way.
Where I disagree with the author is in pointing out that there is no real difference between declaring "fib(1) -> 1" in a pattern matching function definition and inserting a pointer to a function that returns 1 into an array of function pointers. Pattern matching and subtype polymorphism can even still get all the gains the author is looking for--namely, being able to debug branching by inspecting the call stack. For that matter, so would pushing a dummy stack frame every time you come to a branch, or even building a separate branch stack.
by paulsutter on 2/10/13, 7:14 PM
I love the Erlang example, I've been curious about Erlang and that's a powerful demonstration of conditional-free programming, contrary to the author's intent.
Sorry, but "n < 2" is a conditional, whether you're using an if statement, the "?" operator, or to reference an array of function pointers (at least from this old-school C/assembler programmer's perspective). Whereas that Erlang code looks elegantly conditional-free. Clearly branching will appear behind the scenes, but the Erlang code has no conditionals.
by Jabbles on 2/10/13, 7:44 PM
```
    int res = (*fn[(n < 2)])(n);
```
As stated by others, "n < 2" is a conditional or comparison or whatever (let's just say it's cheating :P) let's call it "m".
So we choose our function pointer with:
```
    int res = (*fn[m])(n);
```
where
```
    uint32_t m = n < 2?1:0;
```
and let's assume n is non-negative...
```
    uint32_t top_bits = n & 0xFFFFFFFEu;
    uint32_t p = 0;
    for (int i = 0; i < 32; i++){
        p |= (top_bits & (1u << i)) >> i;
    }
    uint32_t m = 1 - p;
```
Edit:
You can do the for loop to check if any bits are set in logarithmic time. For general comparisons see http://stackoverflow.com/questions/10096599/bitwise-operatio...
Oh and the "i < 32" doesn't count as you could just unroll it...
by xentronium on 2/10/13, 5:41 PM
If you are interested in ideas that can arise from putting some hard restrictions in the same vein, see "programming with nothing"[1]. SICP also explores this topic slightly in the exercise about Church numerals and thought experiments on how you could try to reimplement special forms using functions.
[1] http://codon.com/programming-with-nothing
by revelation on 2/10/13, 7:40 PM
In this post, we don't use conditionals but instead constructs that compilers use to compile conditionals.
by lmm on 2/10/13, 11:23 PM
Makes me think of the smalltalk approach to branching, where it's there, but just another method call (on a boolean) - rather than
```
    if(a > b) {...code...}
```
you do something like
```
    (a > b).ifTrue({...code...})
```
I think it's an approach more languages should use - it means there are fewer special cases in the syntax, and you can compose conditionals or use them in higher-order functions more easily.
by betterunix on 2/10/13, 5:33 PM
Reminds me of this approach to conditionals:
https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolea...
by gmartres on 2/11/13, 1:17 AM
Here's a real implementation of prettyprint without conditional jumps (this assumes signed right shifts are implemented as arithmetic shifts by your compiler, but everyone does that anyway):
```
  #include <stdio.h>
  #include <stdint.h>
  
  void prettyprint(int a, int b)
  {
      int lt_mask = (a-b) >> (sizeof(int) * 8 - 1);
      intptr_t lt = (intptr_t)"%d is < %d\n";
      intptr_t ge = (intptr_t)"%d is >= %d\n";
      char *text = (char*) (lt & lt_mask) + (ge & ~lt_mask);
      printf(text, a, b);
  }
  
  int main(int argc, char **argv)
  {
      prettyprint(atoi(argv[1]), atoi(argv[2]));
      return 0;
  }
```
The point is that the CPU doesn't have to guess what to execute next, so https://en.wikipedia.org/wiki/Branch_misprediction cannot happen.
And if what you're interested in is using the call stack to keep track of executed code, a more effective approach would be to convert the program to CPS, see https://en.wikipedia.org/wiki/Continuation-passing_style and http://matt.might.net/articles/cps-conversion/ .
by Nursie on 2/10/13, 5:34 PM
I'm not sure I understand the purpose of this really. If it was just a thought experiment then cool, I guess.
by Tyr42 on 2/11/13, 12:10 AM
I'd of like to seen the lambda calculus way of defining conditionals.
Let True = (λ x y => x) Let False = (λ x y => y)
Then to do an if, you just apply the conditional ((λ x y => x) 1 2) ---> 1 ((λ x y => y) 1 2) ---> 2
It's funny, really. Pure lambda calculus can feel a lot like a object oriented message passing style.
by jpatte on 2/11/13, 8:31 AM
From the article: "If the compiler/debugger is able to create this "evaluate every piece of line" format for functions (generating new ones when needed), then we can use the stack to check which branches we've taken — they're on the stack, after all!"
No, they are not. Having called functions instead of evaluating conditional statements doesn't change anything to the state of the [non-stale part of the] stack at the time you reach the breakpoint.
To achieve this one would need to execute the code following the branching (and containing the breakpoint) as callback of any of the "conditional" functions, so the followed branch would indeed appear in the stack. But that would just be impractical as you would reach stack overflow extremely quickly - not to mention the hit on performances.
by andreasvc on 2/11/13, 12:07 AM
I think it is more instructive to realize that certain (most?) problems rely on conditionals conceptually. You could then work around them by effectively implementing conditionals anew and spreading code over smaller functions, but the algorithm is still conditional in nature. I am also curious about the relation of conditionals to other constructs. Is the for loop disallowed because it checks for the end of the loop? But it could be implemented with a map over a range, which does no such check (assuming range is a primitive operation). In this way conditionals can be eliminated by recruiting a variety of possible constructs, but it all depends on the rules you're setting.
by bjourne on 2/10/13, 6:07 PM
This is a way prettyprint could have been written without branching:
```
    def prettyprint(a, b):
        fmt_string = {True:'%d is less than %d',False:'%d is higher than %d'}[a < b]
        return fmt_string % (a, b)
```
Or even (and this is cheating by using the int constructor):
```
    def prettyprint(a, b):
        fmt_string = '%d ' + ['is higher than', 'is less than'][int(a < b)] ' %d'
        return fmt_string % (a, b)
```
I think a good way to get acquainted with FP is to replace conditionals with lookup tables and lambda functions. But it is easy to overdo it, sometimes plain old if-statements are the most readable alternative.
by morganwilde on 2/10/13, 9:15 PM
I can honestly say that the best thing to have come out of this article was the link to Bret Victors talk on inventing on pricple - http://vimeo.com/36579366#t=1004. Thank you.
by emdezpk on 2/15/13, 4:48 PM
That a terrible C implementation.
It uses recursion, while a simple loop will suffice. Your fib(10000000000) will blow your RAM limit with growing stack (and will be slow) while implementation with loop would consume zero RAM and would run several times faster.
"And as if by magic, there's no need for conditionals" : also incorrect. You have a conditional in int res = (fn[(n < 2)])(n); specifically the (n < 2) part. All you have done after the hard work is moving conditional from one line to another.
"But we're still not sure of which branch we took." - So why don't you put the breakpoint before* the condition occurs, and step through it in the debugger??
by EarthLaunch on 2/10/13, 7:08 PM
It's true that first class functions can remove the need for conditionals. Isn't this simply functional programming? He starts with an Erlang example then doesn't talk about FP. I must be missing something.
by mamcx on 2/10/13, 7:14 PM
The most useful thing is the coloring of the branching. Neat.
by shurcooL on 2/10/13, 8:28 PM
Thank you to the author for this article.
After reading it, there's a chance I will use some of the insight I've gained in my Conception project.
by JosephHatfield on 2/10/13, 6:14 PM
Reminds me of Prolog