The author is not complying with their own requirements:<p>> Pattern matching and polymorphism is not allowed<p>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.<p>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: <a href="http://news.ycombinator.com/item?id=5198419" rel="nofollow">http://news.ycombinator.com/item?id=5198419</a>).<p>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:<p><pre><code> if :: Bool -> a -> a -> a
if True x _ = x
if False _ y = y
</code></pre>
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).
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.<p>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.
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.<p>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.
<p><pre><code> int res = (*fn[(n < 2)])(n);
</code></pre>
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".<p>So we choose our function pointer with:<p><pre><code> int res = (*fn[m])(n);
</code></pre>
where<p><pre><code> uint32_t m = n < 2?1:0;
</code></pre>
and let's assume n is non-negative...<p><pre><code> 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;
</code></pre>
Edit:<p>You can do the for loop to check if any bits are set in logarithmic time. For general comparisons see <a href="http://stackoverflow.com/questions/10096599/bitwise-operations-equivalent-of-greater-than-operator" rel="nofollow">http://stackoverflow.com/questions/10096599/bitwise-operatio...</a><p>Oh and the "i < 32" doesn't count as you could just unroll it...
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.<p>[1] <a href="http://codon.com/programming-with-nothing" rel="nofollow">http://codon.com/programming-with-nothing</a>
Makes me think of the smalltalk approach to branching, where it's there, but just another method call (on a boolean) - rather than<p><pre><code> if(a > b) {...code...}
</code></pre>
you do something like<p><pre><code> (a > b).ifTrue({...code...})
</code></pre>
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.
Reminds me of this approach to conditionals:<p><a href="https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolean_logic" rel="nofollow">https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolea...</a>
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):<p><pre><code> #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;
}
</code></pre>
The point is that the CPU doesn't have to guess what to execute next, so <a href="https://en.wikipedia.org/wiki/Branch_misprediction" rel="nofollow">https://en.wikipedia.org/wiki/Branch_misprediction</a> cannot happen.<p>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 <a href="https://en.wikipedia.org/wiki/Continuation-passing_style" rel="nofollow">https://en.wikipedia.org/wiki/Continuation-passing_style</a> and <a href="http://matt.might.net/articles/cps-conversion/" rel="nofollow">http://matt.might.net/articles/cps-conversion/</a> .
I'd of like to seen the lambda calculus way of defining conditionals.<p>Let True = (λ x y => x)
Let False = (λ x y => y)<p>Then to do an if, you just apply the conditional
((λ x y => x) 1 2) ---> 1
((λ x y => y) 1 2) ---> 2<p>It's funny, really. Pure lambda calculus can feel a lot like a object oriented message passing style.
From the article: <i>"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!"</i><p>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.<p>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.
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.
This is a way prettyprint could have been written without branching:<p><pre><code> 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)
</code></pre>
Or even (and this is cheating by using the int constructor):<p><pre><code> def prettyprint(a, b):
fmt_string = '%d ' + ['is higher than', 'is less than'][int(a < b)] ' %d'
return fmt_string % (a, b)
</code></pre>
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.
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 - <a href="http://vimeo.com/36579366#t=1004" rel="nofollow">http://vimeo.com/36579366#t=1004</a>. Thank you.
That a <i>terrible</i> C implementation.<p>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.<p>"And as if by magic, there's no need for conditionals"
: also incorrect.
You have a conditional in
int res = (<i>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.<p>"But we're still not sure of which branch we took."
- So why don't you put the breakpoint </i>before* the condition occurs, and step through it in the debugger??
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.