Can you write any algorithm without an if statement?

Question

This site tickled my sense of humour - http://www.antiifcampaign.com/ but can polymorphism work in every case where you would use an if statement?

Answer 1

Though not OOP-related: In Prolog, the only way to write your whole application is without if statements.

Answer 2

I very seldom use if statements... but I confess I am mostly writing in Erlang :-)

Answer 3

Yes actually, you can have a turing-complete language that has no "if" per se and only allows "while" statements:

http://cseweb.ucsd.edu/classes/fa08/cse200/while.html

As for OO design, it makes sense to use an inheritance pattern rather than switches based on a type field in certain cases... That's not always feasible or necessarily desirable though.

@ennuikiller: conditionals would just be a matter of syntactic sugar:

if (test) body;     is equivalent to    x=test; while (x) {x=nil; body;}

if-then-else is a little more verbose:

if (test) ifBody; else elseBody;

is equivalent to

x = test; y = true;
while (x) {x = nil; y = nil; ifBody;}
while (y) {y = nil; elseBody;}

the primitive data structure is a list of lists. you could say 2 scalars are equal if they are lists of the same length. you would loop over them simultaneously using the head/tail operators and see if they stop at the same point.

of course that could all be wrapped up in macros.

The simplest turing complete language is probably iota. It contains only 2 symbols ('i' and '*').

Answer 4

Haskell doesn't even have if statements, being pure functional. ;D

Answer 5

The idea of polymorphism is to call an object without to first verify the class of that object.
That doesn't mean the if statement should not be used at all; you should avoid to write

if (object.isArray()) {
  // Code to execute when the object is an array.
} else if (object.inString()) {
  // Code to execute if the object is a string.
}

Answer 6

answer:That website is against using if statements for checking if an object has a specific type. This is completely different from if (foo == 5). It's bad to use if's like if (foo instanceof pickle) The alternative, using polymorphism instead, promotes encapsulation, making code infinitely easier to debug, maintain, and extend.

Being against if's in general (doing a certain thing based on a condition) will gain you nothing. Notice how all the other answers here still make decisions, so what's really the difference?

explanation of the why behind polymorhishm:

Take this situation:

void draw(Shape s) {
    if (s instanceof Rectangle)
        //treat s as rectangle
    if (s instanceof Circle)
        //treat s as circle
}

Its much better if you don't have to worry about the specific type of an object, generalizing how objects are processes.

void draw(Shape s) {
    s.draw();
}

This moves the logic of how to draw a shape into the shape class itself, so we can now treat all shapes the same. This way if we want to add a new type of shape, all we have to do is write the class and give it a draw method instead of modifying every conditional list in the whole program.

This idea is everywhere in programming today, the whole concept of interfaces is all about polymorphism. (Shape is an interface defining a certain behavior, allowing us to process any type that implements the Shape interface in our method.) Dynamic programming languages take this even further, allowing us to pass any type that supports the necessary actions into a method. Which looks better to you: (python style pseudo-code)

def multiply(a,b):
    if (a is string and b is int):
        //repeat a b times.
    if (a is int and b is int):
        //multiply a and b

or using polymorphism:

def multiply(a,b):
    return a*b

You can now use any 2 types that support the * operator, allowing you to use the method with types that haven't event been created yet.

See polymorphism, what is polymorhism on stackoverflow

Answer 7

? // usually this operator gets me by ... though readability goes out the window

Answer 8

Smalltalk, which is considered as a "truly" object oriented language, has no "if" statement, and it has no "for" statement, no "while" statement. There are other examples (like Haskell) but this is a good one.

Quoting Smalltalk has no “if” statement:

Some of the audience may be thinking that this is evidence confirming their suspicions that Smalltalk is weird, but what I’m going to tell you is this:

An “if” statement is an abomination in an Object Oriented language.

Why? Well, an OO language is composed of classes, objects and methods, and an “if” statement is inescapably none of those. You can’t write “if” in an OO way. It shouldn’t exist. Conditional execution, like everything else, should be a method. A method of what? Boolean.

Now, funnily enough, in Smalltalk, Boolean has a method called ifTrue:ifFalse: (that name will look pretty odd now, but pass over it for now). It’s abstract in Boolean, but Boolean has two subclasses: True and False. The method is passed two blocks of code. In True, the method simply runs the code for the true case. In False, it runs the code for the false case. Here’s an example that hopefully explains:

(x >= 0) ifTrue: [
'Positive'
] ifFalse: [
'Negative'
]

You should be able to see ifTrue: and ifFalse: in there. Don’t worry that they’re not together.

The expression (x >= 0) evaluates to true or false. Say it’s true, then we have:

true ifTrue: [
'Positive'
] ifFalse: [
'Negative'
]

I hope that it’s fairly obvious that that will produce ‘Positive’.

If it was false, we’d have:

false ifTrue: [
'Positive'
] ifFalse: [
'Negative'
]

That produces ‘Negative’.

OK, that’s how it’s done. What’s so great about it? Well, in what other language can you do this? More seriously, the answer is that there aren’t any special cases in this language. Everything can be done in an OO way, and everything is done in an OO way.

I definitely recommend reading the whole post and Code is an object from the same author as well.

Answer 9

It depends on the language.

Statically typed languages should be able to handle all of the type checking by sharing common interfaces and overloading functions/methods.

Dynamically typed languages might need to approach the problem differently since type is not checked when a message is passed, only when an object is being accessed (more or less). Using common interfaces is still good practice and can eliminate many of the type checking if statements.

While some constructs are usually a sign of code smell, I am hesitant to eliminate any approach to a problem apriori. There may be times when type checking via if is the expedient solution.

Note: Others have suggested using switch instead, but that is just a clever way of writing more legible if statements.

Answer 10

There are some nice tricks you can do to remove branches from your code. Some of these techniques are outlined in this blog post.

Answer 11

I used to write code a lot as the recommend in the anti-if campaign, using either callbacks in a delegate dictionary or polymorphism.

It's quite a beguiling argument, especially if you are dealing with messy code bases but to be honest, although it's great for a plugin model or simplifying large nested if statements, it does make navigating and readability a bit of a pain.

For example F12 (Go To Definition) in visual studio will take you to an abstract class (or, in my case an interface definition).

It also makes quick visual scanning of a class very cumbersome, and adds an overhead in setting up the delegates and lookup hashes.

Using the recommendations put forward in the anti-if campaign as much as they appear to be recommending looks like 'ooh, new shiny thing' programming to me.

As for the other constructs put forward in this thread, albeit it has been done in the spirit of a fun challenge, are just substitutes for an if statement, and don't really address what the underlying beliefs of the anti-if campaign.

Answer 12

Yep. if statements imply branches which can be very costly on a lot of modern processors - particularly PowerPC. Many modern PCs do a lot of pipeline re-ordering and so branch mis-predictions can cost an order of >30 cycles per branch miss.
On console programming it's sometimes faster to just execute the code and ignore it than check if you should execute it!

Simple branch avoidance in C:

if (++i >= 15)
{
    i = 0;
)

can be re-written as

 i = (i + 1) & 15;

However, if you want to see some real anti-if fu then read this

Oh and on the OOP question - I'll replace a branch mis-prediction with a virtual function call? No thanks....

Answer 13

You can define True and False with objects (in a pseudo-python):

class True:
    def if(then,else):
        return then
    def or(a):
        return True()
    def and(a):
        return a
    def not():
        return False()

class False:
    def if(then,else):
        return false
    def or(a):
        return a
    def and(a):
        return False()
    def not():
        return True()

I think it is an elegant way to construct booleans, and it proves that you can replace every if by polymorphism, but that's not the point of the anti-if campaign. The goal is to avoid writing things such as (in a pathfinding algorithm) :

if type == Block or type == Player:
    # You can't pass through this
else:
    # You can

But rather call a is_traversable method on each object. In a sense, that's exactly the inverse of pattern matching. "if" is useful, but in some cases, it is not the best solution.

Answer 14

I assume you are actually asking about replacing if statements that check types, as opposed to replacing all if statements.

To replace an if with polymorphism requires a method in a common supertype you can use for dispatching, either by overriding it directly, or by reusing overridden methods as in the visitor pattern.

But what if there is no such method, and you can't add one to a common supertype because the super types are not maintained by you? Would you really go to the lengths of introducing a new supertype along with subtypes just to get rid of a single if? That would be taking purity a bit far in my opinion.

Also, both approaches (direct overriding and the visitor pattern) have their disadvantages: Overriding the method directly requires that you implement your method in the classes you want to switch on, which might not help cohesion. On the other hand, the visitor pattern is awkward if several cases share the same code. With an if you can do:

if (o instanceof OneType || o instanceof AnotherType) {
    // complicated logic goes here
}

How would you share the code with the visitor pattern? Call a common method? Where would you put that method?

So no, I don't think replacing such if statements is always an improvement. It often is, but not always.

Answer 15

Well, if you're writing in Perl, it's easy!

Instead of

if (x) {
    # ...
}

you can use

unless (!x){
    # ... 
}

;-)

Answer 16

You can do it without if per se, but you can't do it without a mechanism that allows you to make a decision based on some condition.

In assembly, there's no if statement. There are conditional jumps.

In Haskell for instance, there's no explicit if, instead, you define a function multiple times, I forgot the exact syntax, but it's something like this:

pseudo-haskell:

def posNeg(x < 0):
    return "negative"

def posNeg(x == 0):    
    return "zero"

def posNeg(x):
    return "positive"

When you call posNeg(a), the interpreter will look at the value of a, if it's < 0 then it will choose the first definition, if it's == 0 then it will choose the second definition, otherwise it will default to the third definition.

So while languages like Haskell and SmallTalk don't have the usual C-style if statement, they have other means of allowing you to make decisions.

Answer 17

This is actually a coding game I like to play with programming languages. It's called "if we had no if" which has its origins at: http://wiki.tcl.tk/4821

Basically, if we disallow the use of conditional constructs in the language: no if, no while, no for, no unless, no switch etc.. can we recreate our own IF function. The answer depends on the language and what language features we can exploit (remember using regular conditional constructs is cheating co no ternary operators!)

For example, in tcl, a function name is just a string and any string (including the empty string) is allowed for anything (function names, variable names etc.). So, exploiting this we can do:

proc 0 {true false} {uplevel 1 $false; # execute false code block, ignore true}
proc 1 {true false} {uplevel 1 $true;  # execute true code block, ignore flase}

proc _IF {boolean true false} {
    $boolean $true $false
}

#usage:
_IF [expr {1<2}] {
    puts "this is true"
} {
  #else:
    puts "this is false"
}

or in javascript we can abuse the loose typing and the fact that almost anything can be cast into a string and combine that with its functional nature:

function fail (discard,execute) {execute()}
function pass (execute,discard) {execute()}
var truth_table = {
    'false' : fail,
    'true' : pass
}
function _IF (expr) {
  return truth_table[!!expr];
}

//usage:
_IF(3==2)(
    function(){alert('this is true')},
//else
    function(){alert('this is false')}
);

Not all languages can do this sort of thing. But languages I like tend to be able to.

Answer 18

IF I only knew...