Home

Functions that go backwards

In most programming languages, we may author a function that takes an input and produces some output.

console.log(getTrafficLightColor("green", "wait"))
// => "yellow"

We can say that our code answers the following question: Given a light color and an action, what happens to the color of the light?

And it answers it well! We can test its behavior, give it some types, whatever we want - to get a solid answer. We can compose these questions to ask more interesting ones:

If I wait twice at a green light, what will the color of the light be?

console.log(
    getTrafficLightColor(
        getTrafficLightColor("green", "wait"),
        "wait"
    )
) // => "red"

But if I asked another question: What color should the light be such that if I wait, it will turn red?

We're no longer asking a question in terms of its input (which is easy!), but its output (which makes us scratch our heads).

🔗 Logically speaking

We'll use a fun "logic programming" language called Prolog (you can grab SWI-Prolog for free) to explore this concept.

Instead of writing a function in terms of its inputs, we write relationships between input and output. An example of such a relation is a valid transition for our traffic light turns green with a wait action into yellow.

All we care about are the green, wait, and yellow (these are known as "atoms" in Prolog), and we can use them to build a "fact".

transition(green, wait, yellow).

We can choose whatever order we want as long as we're consistent. We'll go with the one above since it matches the prose we translated into Prolog.

Let's write a few more of these in a file called fsm.prolog.

% fsm.prolog
transition(green, wait, yellow).
transition(yellow, wait, red).
transition(red, wait, green).

We can then load up swipl in our terminal and test it out. After we load our facts with [fsm]. we can begin "querying" them.

?- [fsm].     % load fsm.prolog
?- transition(green, wait, yellow).
true.
?- transition(red, wait, yellow).
false.

Our first query transition(green, wait, yellow). is a fact, because we defined it as such on the first line of fsm.prolog. Prolog tells us "true" - the thing we asked is true.

The second query, transition(red, wait, yellow) does not appear in our database, so it is false.

Of course, Prolog can do much more than recall facts that we already entered! The magic happens when we query with variables.

?- transition(green, wait, Color).
Color = yellow.

By using a variable (we just need to begin a word with an uppercase letter), we're now asking Prolog to fill in the blank for us through a process called "unification." Which Color does transition(green, wait, Color) result in a fact? yellow!

Better yet, we can put this variable wherever we want. Our original question: What color should the light be such that if I wait, it will turn red? can be queried like so.

?- transition(X, wait, red).
X = yellow.

Because transition does not work on input and output, we can swap 'em as we please.

?- transition(X, wait, purple).
false.

Rather unfortunately, the traffic light we invented can never turn purple.

How about representing multiple transitions? We can join queries with a comma to ask that Prolog fills in the blanks to satisfy both. Let's start at green and wait twice.

?- transition(green, wait, State1),
|    transition(State1, wait, Final).
State1 = yellow,
Final = red.

We left two blanks, State1 and Final, and Prolog filled em both to find that waiting twice at a green light results in a red light. Of course this works backwards for free.

?- transition(Start, wait, State1),
|    transition(State1, wait, yellow).
Start = red,
State1 = green.

Want to wait twice for a yellow? You'll start at red.

🔗 Improving relations

Just as we can define functions and compose them in ordinary programming languages, we can build "rules" out of facts and variables. For example, if we wanted an easier way to query for "waiting twice":

% fsm.prolog
wait_twice(Start, End) :-
    transition(Start, wait, Middle),
    transition(Middle, wait, End).

We've defined wait_twice such that we'll transition once from Start to Middle, then Middle to End. We can use it like so:

?- [fsm].
?- wait_twice(green, red).
true.
?- wait_twice(green, yellow).
false.

Waiting twice at a green does in fact give us a red light, while it is not true that waiting twice at a green light gives us a yellow light. Similar to before, we can query with variables:

?- wait_twice(green, X).
X = red.
?- wait_twice(X, yellow).
X = red.
?- wait_twice(X, purple).
false.

Let's dive into something a little more complicated, but much more rewarding. How about a rule that relates a start and end light color with a list of actions?

We'll call this rule transition_multi and define it recursively - starting with an empty list. If we have an initial State and an empty list of actions [], what should our final state be? Right where we started.

% fsm.prolog
transition_multi(State, [], State).

For the recursive step it may help to see how Prolog's "unification" works with lists.

?- A = [1, 2, 3, 4].
A = [1, 2, 3, 4].
?- [A, B, C] = [1, 2, 3].
A = 1,
B = 2,
C = 3.
?- [A, B] = [1, 2, 3].
false.

We can set a list to a variable, or pattern-match on [Var1, Var2, Etc...] if the lengths are the same.

If we want to match the "rest" of the list, we can use the | operator.

?- [A | Rest] = [1, 2, 3, 4].
A = 1,
Rest = [2, 3, 4].
?- [A, B | Rest] = [1, 2].
A = 1,
B = 2,
Rest = [].

So, back to transition_multi. Our definition looks pretty similar to wait_twice.

% fsm.prolog
transition_multi(State, [], State).
transition_multi(State, [Action | Rest], End) :-
    transition(State, Action, Middle),
    transition_multi(Middle, Rest, End).

We unify the list of actions into Action and Rest, then transition from State to Middle before recursively transition_multi'ing from Middle to End.

Let's try it out.

?- [fsm].
?- transition_multi(green, [wait, wait], red).
true

Groovy, so Prolog can confirm that waiting twice at a green light gets us a red light. We can put a few variables in to flex a bit.

?- transition_multi(yellow, [wait, wait, wait], X).
X = yellow
?- transition_multi(X, [wait, wait, wait, wait], yellow).
X = green .

🔗 Many answers

How about the array in the middle? We can make that a variable too.

?- transition_multi(green, Actions, red).
Actions = [wait, wait] <cursor>

Prolog tells us that [wait, wait] will work, then - interestingly - waits for input. We can hit Enter to get back to the original prompt, or hit semicolon ; to keep it going.

?- transition_multi(green, Actions, red).
Actions = [wait, wait] ;
Actions = [wait, wait, wait, wait, wait] <cursor>

It appears that not only do two waits bring us from green to red, but so do five. This is because waiting three times brings us back to green (then two more for red). We can keep going with another press of ;.

?- transition_multi(green, Actions, red).
Actions = [wait, wait] ;
Actions = [wait, wait, wait, wait, wait] ;
Actions = [wait, wait, wait, wait, wait, wait, wait, wait] ;
Actions = [wait, wait, wait, wait, wait, wait, wait, wait, wait|...] .

We'll be here forever (and ever) so we can just hit . to stop.

🔗 What are you waiting for?

Up until now we've been dealing with a single action wait, which moves the traffic light from one color to another. Let's introduce two more.

% fsm.prolog
transition(green, wait, yellow).
transition(yellow, wait, red).
transition(red, wait, green).

transition(green, power_outage, blinking).
transition(yellow, power_outage, blinking).
transition(red, power_outage, blinking).

transition(blinking, power_on, red).

And query with them like so:

?- [fsm].
?- transition_multi(green, [power_outage], X).
X = blinking.
?- transition_multi(green, [wait, power_outage], X).
X = blinking.

Now we can answer more interesting questions such as What two events can occur to take us from green to red?.

?- transition_multi(green, [A, B], red).
A = B, B = wait <cursor>

We can wait twice, but Prolog asks if we want to keep going. We do, using ;.

?- transition_multi(green, [A, B], red).
A = B, B = wait ;
A = power_outage,
B = power_on.

So, we can go from green to red with two waits, or a power_outage and power_on. What if we give ourselves four actions?

?- transition_multi(green, [A, B, C, D], red).
A = B, B = wait,
C = power_outage,
D = power_on ;
A = C, C = power_outage,
B = D, D = power_on.

We're left with two options:

[wait, wait, power_outage, power_on]
[power_outage, power_on, power_outage, power_on]

🔗 Closing notes

Writing our program as a series of relations instead of instructions unlocks the ability to flip our code upside down. Not only can we feed it input and get output, but we can feed it "output" to determine what "input" we require to produce facts.

When we combine this technique with more interesting data structures like lists, we can generate infinite sequences of inputs to get a desired output.

I hope you found this post enlightening, and encourage to fire up SWI-Prolog to see what other sorts of problems logic programming can help solve.

Until then, see you around on twitter.