# If it's Possible to Create the If-Statement from Simpler Primitives

This question is about how to create an if statement (one of the control-flow statements) from scratch.

An if-statement is typically a built-in construct in languages. However, I am wondering if there is a way to construct an if-statement from some other non-control-flow primitives. I am also wondering how to do this with Boolean algebra, and there is a link there to how to represent if/else statements with circuits.

I started off trying like this:

var x = true
var run = {
true: [],
false: []
}
var state = []
while (true) {
x = !x
var arr = run[x == true]
for (var i = 0, n = arr.length; i < n; i++) {

}
}


That x toggle seemed like it could be used to somehow shift the evaluation path. Then in the state array there would be states of the application listed, and so the application would go into that state if the x was 0 vs. 1. But there pops up the if right there, so it's hard to make it work without resorting to if somewhere. The for loop is also a form of control-flow, so would hope to avoid that.

Was going to try to test it out to simulate a program such as this:

if (a == 1) {
if (b == 1) {
console.log('1.1')
}

if (b == 2) {
console.log('1.2')
}
}

if (a == 2) {
if (b == 1) {
console.log('2.1')
}

if (b == 2) {
console.log('2.2')
}
}

if (a == 3) {
if (b == 1) {
console.log('3.1')
}

if (b == 2) {
console.log('3.2')
}
}


The program would then run:

myiftest(1, 1) // a == 1, b == 1
myiftest(1, 2)
...


There are ways to sort of cheat, such as using && to hack the conditional. For example:

a == 1 && b == 1 && console.log('1.1')


You could also do it with a while loop:

while (a == 1 && b == 1) {
console.log('1.1')
break
}


I would like to see if there's any way to do this using only non-control-flow statements in JavaScript (or in C, Ruby, or Python, any modern iterative language, or even Assembly which might make it easier), i.e. not cheating like the above. I don't even know if it's possible, so any form that shows it is possible (or not possible!) would be great to know.

It's okay to use the while(true) loop to start it out, so the program actually runs (if necessary).

Even in assembly the "if" statement is built into the jmp or jump-/branch-related statements.

This is perhaps most clear at the assembly level.

There is an instruction pointer, which normally moves to the next instruction after executing the current one.

Any instruction that interferes with that behavior is, by definition, a control flow instruction.

Conversely, if no instruction can have an effect to alter the instruction pointer, the program has to run sequentially: the first command, then the second, ..., all the way until the last.

• Nice, so wondering if there is a way to mimic interfering with the instruction pointer. Perhaps in assembly, or perhaps just theoretically (pseudocode). Would be helpful if you could demonstrate that :) – Lance Pollard Jul 6 '18 at 8:56
• Some CPU architectures provide direct access to instruction pointer via arithmetic operations. It would be a stretch to regard those as control flow instructions. – Dmitri Urbanowicz Jul 6 '18 at 12:42
• Wondering if there is a way though to actually do some control flow by simulating the instruction pointer in an iterative language like assembly/javascript/etc. – Lance Pollard Jul 6 '18 at 17:43

Contrary to what you (and many people) may think, in the field of programming languages, the most primitive control-flow operation is actually pattern matching!

With a simple type system (say the simply-typed lambda calculus) plus unit types and sum types, you can encode the boolean type easily. Let $\mathbf{1}$ be the unit type. The boolean type is simply $\mathbf{1} + \mathbf{1}$, i.e. the sum of two unit types (because each variation has exactly one inhabitant, respectively "true" and "false").

Now, when we get a sum type, we can destruct it by pattern matching. That is, for each branch of the sum type, we return a different expression. This is the most basic control-flow operation! The expression if b then et else ef is simply sugar for:

match b with
| left -> et
| right -> ef


Interesting, isn't it?

Of course, this is not how machines work, but from a lambda-calculus/type theory standpoint, pattern matching is the father of all conditional execution!