6 ms·

A Language Without Conditionals

67 points by JeanPierre 14y ago

betterunix 14y ago
Reminds me of this approach to conditionals: https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolean_logic https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolea...
- raganwald 14y ago
  That was my first thought as well, replacing conditional evaluation with "choice."
Nursie 14y ago
I'm not sure I understand the purpose of this really. If it was just a thought experiment then cool, I guess.
- gatlin 14y ago
  I can't speak for anyone else, but I can think of one reason to do things like this. If I can use a minimal subset of language features and verify their correctness, and also verify the correctness of the ways in which I combine them, then it would follow that my entire program is much, much easier to prove correct. This is perhaps more useful in lisps or Haskell but it's still cool to think about. And, hell, maybe someone implementing a language in C could do something like this for the debugging properties. And while yes you could take this to the extreme and implement everything on top of SKI combinators, perhaps one wants to start a touch higher up than that. Anyway, maybe that's a useful answer?
  - Nursie 14y ago
    Maybe :) I guess I was just puzzled as to why the author felt that avoiding conditionals was a useful exercise in the first place. I realise that I'm probably wedded to a conditional-heavy way of thinking, I guess what threw me was that the author seemed to assume that eliminating conditionals stands as an aim on its own, regardless of minimising use of language features. At the same time he has a test in his array de-reference that seems to me to be effectively a conditional without using the explicit if(){} else{} construction. TBH I would have thought verifying the implicit conditional and function-pointer jump was no easier than the explicit...
xentronium 14y ago
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 http://codon.com/programming-with-nothing
philwelch 14y ago
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.
- JeanPierre 14y ago
  Certainly, there's no practical difference between pointers+arrays, polymorphism and conditional statements. That's the whole point: We're "simulating" or "creating" if-statements/polymorphism using other language constructs. My goal was to show that you can do conditional statements and polymorphism without having those constructs by implementing them on top of other constructs (and possibly vice versa). And by looking at them from a different angle, you may end up with some ideas which may or may not be of value, such as the debug-thing. Building a separate branch stack would be the same thing, the question at hand is how you find such an idea/solution to a problem.
- ufo 14y ago
  This is sad. If only people would take the Expression Problem[1] more seriously and realise that there is a good time to use ifs/pattern matching and a good time to use polymorphism/function arguments [1] http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wiki?ExpressionProblem
  - mvc 14y ago
    I think CLOS doesn't suffer from the expression problem. Both alterations to the data model can be implemented as a "patch" to the program without editing any of the original code.
bjourne 14y ago
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.
- kzrdude 14y ago
  True and False are 1 and 0 in Python too, so no int constructor needed. (Try 3 + True == 4)
  - slurgfest 14y ago
    True and False are not 1 and 0 in Python. >>> (1 is True) or (True is 1) False >>> (0 is False) or (False is 0) False >>> isinstance(0, bool) or isinstance(1, bool) False >>> isinstance(False, bool) and isinstance(True, bool) True Indexing with boolean expressions is bad style to begin with, but if you are going to do it then a bool cast shows explicitly what you are trying to do.
    - peter-fogg 14y ago
      You'll find that they are integers, though: >>> isinstance(True, int) True >>> bool.__mro__ (<type 'bool'>, <type 'int'>, <type 'object'>) Although they aren't literally the same object, 1 == True does evaluate to True.
      - slurgfest 14y ago
        Downvoting notwithstanding, the statement that 1 and 0 ARE True and False is flat false. It's not even kind of true: True is not 1 and False is not 0, the type of True and False is not int, and the established convention for comparing to these values is to use 'is' if you are not using the vaguer 'if cond' or 'if not cond'.
JosephHatfield 14y ago
Reminds me of Prolog
- andreasvc 14y ago
  A clause in Prolog is a predicate that is true when its conditions are met, i.e., can be seen as a single conditional in itself. Furthermore, there is pattern matching (unification, even), which was declared cheating in the post. Fibonacci examples would use this, just as the Erlang example in the post. There are also if-then rules (the -> operator), which I find makes code clearer. The same trick described in the post could be implemented in Prolog I suppose.
EarthLaunch 14y ago
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.
mamcx 14y ago
The most useful thing is the coloring of the branching. Neat.
- Nursie 14y ago
  Have you seen gcov/lcov? They're coverage tools rather than debuggers, but they can give you an html-browseable version of your source code coloured like that to show you which lines have been hit and how many times.
paulsutter 14y ago
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.
- JeanPierre 14y ago
  I consider "n < 2" to be an expression evaluating to either true (1) or false (0). You can do basic if-else branching by considering true/false statements as conditions to if/elseif/else branching, but true/false cannot be used to evaluate only parts of a function by itself. That's what I intended to express, sorry if it's not evident.
  - cpressey 14y ago
    What constitutes a "part of a function" in the article is a little confusing to me, for example: "I consider it as 'cheating' as we now have evaluated only parts of the function." Once you pass functions to a function, are those "part of the function"? If we say no, they're just arguments, it seems to sidestep the issue in an unsatisfying way; I could rewrite all my functions to take all the functions they call as arguments (dependency injection taken to the extreme) and suddenly all my functions have... no parts? That can't be right! On top of that, looking up an entry in a list (even one of functions), given an integer index, in a functional language, is arguably a series of conditional tests (is index 0? is index-1 0? is index-2 0? ...) Overall it's a fair article, but I think there have been a number of esolangs over the years that have tried to turn the idea of the conditional on its head, as well; more references might make it stronger.
- jfaucett 14y ago
  agree about the conditional, I was expecting some sort of functional alternative and was interested by the title, but on reading and realizing that the OP is proposing that "(n < 2)" evaluation and calling a func ptr as non-conditional programming is simply not true, that's conditional programming.
revelation 14y ago
In this post, we don't use conditionals but instead constructs that compilers use to compile conditionals.
Jabbles 14y ago
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-operations-equivalent-of-greater-than-operator http://stackoverflow.com/questions/10096599/bitwise-operatio... Oh and the "i < 32" doesn't count as you could just unroll it...
shurcooL 14y ago
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.
morganwilde 14y ago
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 http://vimeo.com/36579366#t=1004. Thank you.
- themgt 14y ago
  Thanks for singling that out. The specific demos of interactive coding/visualization were cool, but the end where he really gets into the general topic of finding a guiding principle and using that to change the world - was very, very well worth the time to listen to.
lmm 14y ago
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.
epidemian 14y ago
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 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).
andreasvc 14y ago
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.
Tyr42 14y ago
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.
- ufo 14y ago
  And Smalltalk does just that, by the way. Booleans have an `ifTrue: ifFalse:` method that receives two callbacks as parameters.
gmartres 14y ago
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 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 https://en.wikipedia.org/wiki/Continuation-passing_style and http://matt.might.net/articles/cps-conversion/ http://matt.might.net/articles/cps-conversion/ .
jpatte 14y ago
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.
emdezpk 14y ago
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??

67 points by JeanPierre 14y ago

Reminds me of this approach to conditionals: https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolean_logic https://en.wikipedia.org/wiki/SKI_combinator_calculus#Boolea...

raganwald 14y ago
That was my first thought as well, replacing conditional evaluation with "choice."

Nursie 14y ago

I'm not sure I understand the purpose of this really. If it was just a thought experiment then cool, I guess.

gatlin 14y ago
I can't speak for anyone else, but I can think of one reason to do things like this. If I can use a minimal subset of language features and verify their correctness, and also verify the correctness of the ways in which I combine them, then it would follow that my entire program is much, much easier to prove correct. This is perhaps more useful in lisps or Haskell but it's still cool to think about. And, hell, maybe someone implementing a language in C could do something like this for the debugging properties. And while yes you could take this to the extreme and implement everything on top of SKI combinators, perhaps one wants to start a touch higher up than that. Anyway, maybe that's a useful answer?
- Nursie 14y ago
  Maybe :) I guess I was just puzzled as to why the author felt that avoiding conditionals was a useful exercise in the first place. I realise that I'm probably wedded to a conditional-heavy way of thinking, I guess what threw me was that the author seemed to assume that eliminating conditionals stands as an aim on its own, regardless of minimising use of language features. At the same time he has a test in his array de-reference that seems to me to be effectively a conditional without using the explicit if(){} else{} construction. TBH I would have thought verifying the implicit conditional and function-pointer jump was no easier than the explicit...

xentronium 14y ago

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 http://codon.com/programming-with-nothing

philwelch 14y ago

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.

JeanPierre 14y ago
Certainly, there's no practical difference between pointers+arrays, polymorphism and conditional statements. That's the whole point: We're "simulating" or "creating" if-statements/polymorphism using other language constructs. My goal was to show that you can do conditional statements and polymorphism without having those constructs by implementing them on top of other constructs (and possibly vice versa). And by looking at them from a different angle, you may end up with some ideas which may or may not be of value, such as the debug-thing. Building a separate branch stack would be the same thing, the question at hand is how you find such an idea/solution to a problem.
ufo 14y ago
This is sad. If only people would take the Expression Problem[1] more seriously and realise that there is a good time to use ifs/pattern matching and a good time to use polymorphism/function arguments [1] http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wiki?ExpressionProblem
- mvc 14y ago
  I think CLOS doesn't suffer from the expression problem. Both alterations to the data model can be implemented as a "patch" to the program without editing any of the original code.

bjourne 14y ago

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.

kzrdude 14y ago
True and False are 1 and 0 in Python too, so no int constructor needed. (Try 3 + True == 4)
- slurgfest 14y ago
  True and False are not 1 and 0 in Python. >>> (1 is True) or (True is 1) False >>> (0 is False) or (False is 0) False >>> isinstance(0, bool) or isinstance(1, bool) False >>> isinstance(False, bool) and isinstance(True, bool) True Indexing with boolean expressions is bad style to begin with, but if you are going to do it then a bool cast shows explicitly what you are trying to do.
  - peter-fogg 14y ago
    You'll find that they are integers, though: >>> isinstance(True, int) True >>> bool.__mro__ (<type 'bool'>, <type 'int'>, <type 'object'>) Although they aren't literally the same object, 1 == True does evaluate to True.
    - slurgfest 14y ago
      Downvoting notwithstanding, the statement that 1 and 0 ARE True and False is flat false. It's not even kind of true: True is not 1 and False is not 0, the type of True and False is not int, and the established convention for comparing to these values is to use 'is' if you are not using the vaguer 'if cond' or 'if not cond'.

JosephHatfield 14y ago

Reminds me of Prolog

andreasvc 14y ago
A clause in Prolog is a predicate that is true when its conditions are met, i.e., can be seen as a single conditional in itself. Furthermore, there is pattern matching (unification, even), which was declared cheating in the post. Fibonacci examples would use this, just as the Erlang example in the post. There are also if-then rules (the -> operator), which I find makes code clearer. The same trick described in the post could be implemented in Prolog I suppose.

EarthLaunch 14y ago

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.

mamcx 14y ago

The most useful thing is the coloring of the branching. Neat.

Nursie 14y ago
Have you seen gcov/lcov? They're coverage tools rather than debuggers, but they can give you an html-browseable version of your source code coloured like that to show you which lines have been hit and how many times.

paulsutter 14y ago

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.

JeanPierre 14y ago
I consider "n < 2" to be an expression evaluating to either true (1) or false (0). You can do basic if-else branching by considering true/false statements as conditions to if/elseif/else branching, but true/false cannot be used to evaluate only parts of a function by itself. That's what I intended to express, sorry if it's not evident.
- cpressey 14y ago
  What constitutes a "part of a function" in the article is a little confusing to me, for example: "I consider it as 'cheating' as we now have evaluated only parts of the function." Once you pass functions to a function, are those "part of the function"? If we say no, they're just arguments, it seems to sidestep the issue in an unsatisfying way; I could rewrite all my functions to take all the functions they call as arguments (dependency injection taken to the extreme) and suddenly all my functions have... no parts? That can't be right! On top of that, looking up an entry in a list (even one of functions), given an integer index, in a functional language, is arguably a series of conditional tests (is index 0? is index-1 0? is index-2 0? ...) Overall it's a fair article, but I think there have been a number of esolangs over the years that have tried to turn the idea of the conditional on its head, as well; more references might make it stronger.
jfaucett 14y ago
agree about the conditional, I was expecting some sort of functional alternative and was interested by the title, but on reading and realizing that the OP is proposing that "(n < 2)" evaluation and calling a func ptr as non-conditional programming is simply not true, that's conditional programming.

revelation 14y ago

In this post, we don't use conditionals but instead constructs that compilers use to compile conditionals.

Jabbles 14y ago

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-operations-equivalent-of-greater-than-operator http://stackoverflow.com/questions/10096599/bitwise-operatio... Oh and the "i < 32" doesn't count as you could just unroll it...

shurcooL 14y ago

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.

morganwilde 14y ago

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 http://vimeo.com/36579366#t=1004. Thank you.

themgt 14y ago
Thanks for singling that out. The specific demos of interactive coding/visualization were cool, but the end where he really gets into the general topic of finding a guiding principle and using that to change the world - was very, very well worth the time to listen to.

lmm 14y ago

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.

epidemian 14y ago

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 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).

andreasvc 14y ago

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.

Tyr42 14y ago

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.

ufo 14y ago
And Smalltalk does just that, by the way. Booleans have an `ifTrue: ifFalse:` method that receives two callbacks as parameters.

gmartres 14y ago

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 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 https://en.wikipedia.org/wiki/Continuation-passing_style and http://matt.might.net/articles/cps-conversion/ http://matt.might.net/articles/cps-conversion/ .

jpatte 14y ago

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.

emdezpk 14y ago

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??