Mateus Jabour

Menu

Understanding how computation works part 6-1

Computation Logo

On this post, I will try to make you understand more about computer science. In this part of the post we are going to see how to simulate a Turing machine with lambda calculus, and learn about two ways of writing programs: Partial Recursive Functions and SKI Combinator Calculus.

We saw on the post 5 the design og a universal Turing machine and on post 6 we saw a minimal way of writing simple programs. We know that a Turing machine can adapt to arbitrary tasks, just by reading instructions from a tape. These instructions are like a piece of software that controls the machine to do the task, like our computers.

In this post, we’re going to se several simple and universal systems, all capable of simulating a Turing machine or any arbitrary program provided as input instead of hardcoded into the rules of the system.

We’ve seen that the lambda calculus is a usable programming language, but, we didn’t test its power, we don’t know if it’s as powerful as a Turing machine. At least, lambda calculus has the same power, since we can simulate a Turing machine using lambda calculus. We can taste how it works by implementing part of a Turing machine.

If you remember, a Turing machine has four attributes, the list of characters on the left, the character on the middle, the list of characters on the right, and the blank part. Let’s implement a represatation of those attributes:

TAPE = -> l { -> m { -> r { -> b { PAIR[PAIR[l][m]][PAIR[r][b]] } } } } TAPE_LEFT = -> t { LEFT[LEFT[t]] } TAPE_MIDDLE = -> t { RIGHT[LEFT[t]] } TAPE_RIGHT = -> t { LEFT[RIGHT[t]] } TAPE_BLANK = -> t { RIGHT[RIGHT[t]] }

Tape is represented by a pair of pair. Now that we have the data structure, let’s implement a method, TAPE_WRITE, to write on the current middle position:

TAPE_WRITE = -> t { -> c { TAPE[TAPE_LEFT[t]][c][TAPE_RIGHT[t]][TAPE_BLANK[t]] } }

We can also implement a method to move the tape to the right:

TAPE_MOVE_HEAD_RIGHT = -> t { TAPE[ PUSH[TAPE_LEFT[t]][TAPE_MIDDLE[t]] ][ IF[IS_EMPTY[TAPE_RIGHT[t]]][ TAPE_BLANK[t] ][ FIRST[TAPE_RIGHT[t]] ] ][ IF[IS_EMPTY[TAPE_RIGHT[t]]][ EMPTY ][ REST[TAPE_RIGHT[t]] ] ][ TAPE_BLANK[t] ] }

Look how it works:

current_tape = TAPE[EMPTY][ZERO][EMPTY][ZERO] =># current_tape = TAPE_WRITE[current_tape][ONE] =># current_tape = TAPE_MOVE_HEAD_RIGHT[current_tape] =># current_tape = TAPE_WRITE[current_tape][TWO] =># current_tape = TAPE_MOVE_HEAD_RIGHT[current_tape] =># current_tape = TAPE_WRITE[current_tape][THREE] =># current_tape = TAPE_MOVE_HEAD_RIGHT[current_tape] =># to_array(TAPE_LEFT[current_tape]).map { |p| to_integer(p) } =>[1, 2, 3] to_integer(TAPE_MIDDLE[current_tape]) =>0 </code>

We’re going to stop the simulation here, but it isn’t difficult to continue. We would need to implement two methods: STEP and RUN. STEP simulates the single step of a Turing maching by applying the rulebook to one configuration to produce another, and RUN runs STEP recursively until the machine reachs a accept state.

Partial Recursive Functions

The partial recursive functions consists in building programs from four main building block in different combinations. The first two blocks are trivial, zero and increment:

def zero 0 end
def increment(n) n + 1 end

These are simple, we can use them to define new methods:

def two increment(increment(zero)) end
two => 2
def three increment(two) end
three => 3
def add_three(x) increment(increment(increment(x))) end
add_three(two) => 5

the third block is more complicated to understand, it’s called #recurse:

def recurse(f, g, *values) *other_values, last_value = values
if last_value.zero? send(f, *other_values) else easier_last_value = last_value - 1 easier_values = other_values + [easier_last_value]
easier_result = recurse(f, g, *easier_values) send(g, *easier_values, easier_result) end end

Basically, #recurse takes two method names as arguments, f and g, and uses them to perform a calculation using recursion on values that passed on *values. Recurse behaves differently depeding on the last input:

  • if the last input is zero, #recurse calls the method named by f, passing the rest of the values as arguments for f.
  • if the last input isn’t zero, #recurse decrement it, calls itself with the updated input values, and then calls the method named by g with those same values and the result of the recursive call.

So, let’s try to implement an #add method using those building blocks, first we need to think what are the two methods we’re using inside #recurse. When the last value is zero, the best to do I’d say that’s to add the value to zero, right? So:

def add_zero_to_x(x) x end

And, for each recursive call of recurse, we should increment the number, since the number of recursive calls is equal to the last value.

def increment_easier_result(x, easier_y, easier_result) increment(easier_result) end

And now, we have #add:

def add(x, y) recurse(:add_zero_to_x, :increment_easier_result, x, y) end
add(two, three) => 5

Cool, now we can do a lot of different methods with this building block:

#multiply def multiply_x_by_zero(x) zero end
def add_x_to_easier_result(x, easier_y, easier_result) add(x, easier_result) end
def multiply(x, y) recurse(:multiply_x_by_zero, :add_x_to_easier_result) end
#decrement def easier_x(easier_x, easier_result) easier_x end
def decrement(x) recurse(:zero, :easier_x, x) end
#subtract def subtract_zero_from_x(x) x end
def decrement_easier_result(x, easier_y, easier_result) decrement(easier_result) end
def subtract(x, y) recurse(:substract_zero_from_x, :decrement_easier_result, x, y) end

Let’s check if works:

multiply(two, three) => 6
def six multiply(two, three) end
decrement(six) => 5
substract(six, two) => 4
substract(two, six) => 0

Those programs that we can build just with #zero, #increment and #recurse are called the primitive recursive functions. All primitive recursive functions are total, this means that regardless if their input, they always halt and return an answer. This happens because the method #recurse is the only legitimate way to define a recursive method. We could implement a single step of a Turing machine with we have by now.

The fourth fundamental operation is #minimize, this will bring to us a truly universal system.

def minimize n = 0 n = n + 1 until yield(n).zero? n end

#minimize take a block and calls it repeatedly with a single numeric argument. On the first call, we have 0 as the argument, then 1, then 2, and keep incrementing and calling the block with larger number until it retuns zero. With #minimize we can build many more functions. Let’s implement #divide with #minimize:

def divide(x, y) minimize { |n| substract(increment(x), multiply(y, increment(n))) } end

You can see that with this, when the second arguemtn becomes equal or bigger than the first, the block returns zero, and for each recursive call, it multiplies y to a number in order(0, then 1, then 2), until it discovers the division result.

divide(six, two) => 3
def ten increment(multiply(three, three)) end
ten => 10 divide(ten, three) => 3

Since #minimize can loop forever, #divide doesn’t have to return an answer.

divide(six, zero) SystemStackError: stack level too deep

SKI Combinator Calculus

The SKI Combinator Calculus is a system of rules for manipulating the syntax of expressions, just like the lambda calculus. We saw that lambda calculus was very simple and had 3 kinds of expression–variables, functions and calls–but the SKI calculus is even simpler, with only two kinds of expression–calls and alphabetics symbols– and much easier rules. Its power comes from three special symbols, S, K, and I (called combinators), each has its reduction rule:

  • Reduce S[a][b][c] to a[c][b[c]], where a, b and c can be any SKI calculus expressions.
  • Reduce K[a][b] to a.
  • Reduce I[a] to a.

For example, let’s reduce I[S][K][S][I[K]]:

  • S[K][S][I[K]] -> reducing I[S] to S
  • S[K][S][K] -> reducing I[K] to K
  • K[K][S[K]] -> reducing S[K][S][K] to K[K][S[K]]
  • K -> reducing K[K][S[K]] to K

This is basically symbols being reordered, duplicated and discarded according to the reduction rules. So, it’s easy to implement the avstract syntax of SKI expressions:

class SKISymbol < Struct.new(:name) def to_s name.to_s end
def inspect to_s end end
class SKICall < Struct.new(:left, :right) def to_s "#{left}[#{right}]" end
def inspect to_s end end
class SKICombiator < SKISymbol end
S, K, I = [:S, :K, :I].map { |name| SKICombiator.new(name) }

And we can build some expressions with those classes:

x = SKISymbol.new(:x) => x expression = SKICall.new(SKICall.new(S, K), SKICall.new(I, x)) => S[K][I[x]]

We can use small-step operational semantics to this implementation by using reduction rules and applying those rules inside expressions. We just need to define #call to SKI combinator instances: S, K and I.

def S.call(a, b, c) SKICall.new(SKICall.new(a, c), SKICall(b, c)) end
def K.call(a, b) a end
def I.call(a) a end

Let’s check if works:

y, z = SKISymbol.new(:y), SKISymbol.new(:z) => [y, z] S.call(x, y, z) => x[z][y[z]]

But before using #call, we need to find the combinator on the expression, this is a bit hard since an expression is represented as a binary tree of SKICall objects:

expression = SKICall.new(SKICall.new(SKICall.new(S, x), y), z) => S[x][y][z] combinator = expression.left.left.left => S first_argument = expression.left.left.right => x second_argument = expression.left.right => y third_argument = expression.right => z combinator.call(first_argument, second_argument, third_argument) => x[z][y[z]]

To facilitate our work with those structure, we can define the methods #combinator and #arguments on abstract syntax trees:

class SKISymbol def combinator self end
def arguments [] end end
class SKICall def combinator left.combinator end
def arguments left.arguments + [right] end end

Now, we can discover which combinator to call:

expression => S[x][y][z] combinator = expression.combinator => S arguments = expression.arguments => [x, y, z] combinator.call(*arguments) => x[z][y[z]]

This works fine just with this expression, but there are a couple of problems in the general case. First problem is the #combinator method just return the leftmost symbol from an expression, but that symbol isn’t necessarily a combinator:

expression = SKICall.new(SKICall.new(x, y), z) => x[y][z] combinator = expression.combinator => x arguments = expression.arguments => [y, z] combinator.call(*arguments) SKIcombinator.rb:99:in `<main>': undefined method `call' for x:SKISymbol (NoMethodError)

And second, even if the lefmost symbol is a combinator, it isn’t necessarily being called with the right number of arguments:

expression = SKICall.new(SKICall.new(S, x), y) => S[x][y] combinator = expression.combinator => S arguments = expression.arguments => [x, y] combinator.call(*arguments) SKIcombinator.rb:32:in `call': wrong number of arguments (given 2, expected 3) (ArgumentError)

To avoid these problem, we can define #callable?, so we can check before trying to reduce the expression:

class SKISymbol def callable?(*arguments) false end end
def S.callable?(*arguments) arguments.length == 3 end
def K.callable?(*arguments) arguments.length == 2 end
def I.callable?(*arguments) arguments.length == 1 end

Now we can check the expression before reducing it:

expression = SKICall.new(SKICall.new(x, y), z) => x[y][z] expression.combinator.callable?(*expression.arguments) => false expression = SKICall.new(SKICall.new(S, x), y) => S[x][y] expression.combinator.callable?(*expression.arguments) => false expression = SKICall.new(SKICall.new(SKICall.new(S, x), y), z) => S[x][y][z] expression.combinator.callable?(*expression.arguments) => true

And now, we’re finally ready to implement the #reducible? and #reduce methods for SKI expressions:

class SKISymbol def reducible? false end end
class SKICall def reducible? left.reducible? || right.reducible? || combinator.callable?(*arguments) end
def reducible if left.reducible? SKICall.new(left.reduce, right) elsif right.reducible? SKICall.new(left, right.reduce) else combinator.call(*arguments) end end end

We can now reduce the SKI expression by repeatedly calling #reduce until there’s no more possible reductions. Let’s see it:

swap = SKICall.new(SKICall.new(S, SKICall.new(K, SKICall.new(S, I))), K) => S[K[S[I]]][K] expression = SKICall.new(SKICall.new(swap, x), y) => S[K[S[I]]][K][x][y] => S[K[S[I]]][K][x][y] while expression.reducible? puts expression expression = expression.reduce end; puts expression S[K[S[I]]][K][x][y] K[S[I]][x][K[x]][y] S[I][K[x]][y] I[y][K[x][y]] y[K[x][y]] y[x] => nil

We can produce complex behaviors with those three simple rules, so complex that it turns out to be universal. We can prove it’s universal bt showing how to translate any lambda calculus expression into an SKI expression that does the same thing. We can do it by implementing a method called #as_a_function_of:

class SKISymbol def as_a_function_of(name) if self.name == name I else SKICall.new(K, self) end end end
class SKICombiator def as_a_function_of(name) SKICall.new(K, self) end end
class SKICall def as_a_function_of(name) left_function = left.as_a_function_of(name) right_function = right.as_a_function_of(name)
SKICall.new(SKICall.new(S, left_function), right_function) end end

We’re not going to enter in details of how those methods works, but we know that it converts an SKI expression into a new one that turns back into the original when called with an argument. Let’s see this working:

original = SKICall.new(SKICall.new(S, K), I) => S[K][I] function = original.as_a_function_of(:x) => S[S[K[S]][K[K]]][K[I]] function.reducible? => false

When this new expression is called with an argument, like the symbol y, it reduces back to original:

expression = SKICall.new(function, y) => S[S[K[S]][K[K]]][K[I]][y] while expression.reducible? puts expression expression = expression.reduce end; puts expression S[S[K[S]][K[K]]][K[I]][y] S[K[S]][K[K]][y][K[I][y]] K[S][y][K[K][y]][K[I][y]] S[K[K][y]][K[I][y]] S[K][K[I][y]] S[K][I] expression == original => true

It’s interesting when you have an expression with a symbol(x), then you use #as_a_function_of with this symbol as an argument(x), then you add another symbol(y) in the end of this function, and reduce it. You will notice that the function will be reduce to the original but with the new symbol on the place of the old one. Have a look:

original = SKICall.new(SKICall.new(S, x), I) => S[x][I] function = original.as_a_function_of(:x) => S[S[K[S]][I]][K[I]] expression = SKICall.new(function, y) => S[S[K[S]][I]][K[I]][y] while expression.reducible? puts expression expression = expression.reduce end; puts expression S[S[K[S]][I]][K[I]][y] S[K[S]][I][y][K[I][y]] K[S][y][I[y]][K[I][y]] S[I[y]][K[I][y]] S[y][K[I][y]] S[y][I] expression == original => false

It looks like the function behavior, just putting the value in the place to do something, like an argument. This makes it straightforward to translate lambda calculus expressions into SKI expressions.

class LCVariable def to_ski SKISymbol.new(name) end end
class LCCall def to_ski SKICall.new(left.to_ski, right.to_ski) end end
class LCFunction def to_ski body.to_ski.as_a_function_of(parameter) end end

Let’s check this translation:

two = LambdaCalculusParser.new.parse('-> p { -> x { p[p[x]] } }').to_ast => -> p { -> x { p[p[x]] } } two.to_ski => S[S[K[S]]S[K[K]][I]][S[S[K[S]][S[K[K]][I]]][K[I]]]

Iota

The Greek letter iota (ɩ) is an extra combinator, it can be added to the SKI combinator. Iota’s reduction rule is: ɩ[a] to a[S][K].

We can try to implement iota on our SKI calculus implementation:

IOTA = SKISymbol.new('ɩ')
def IOTA.call(a) SKICall.new(SKICall.new(a, S), K) end
def IOTA.callable?(*arguments) arguments.length == 1 end

Chris Barker proposer a language called Iota whose programs only use ɩ combinator. Even with only one combinator, Iota is universal, because any SKI calculus expression can be converted into it, and we saw that SKI calculus is universal.

We can convert an SKI expression to Iota using these rules:

  • Replace S with ɩ[ɩ[ɩ[ɩ[ɩ]]]].
  • Replace K with ɩ[ɩ[ɩ[ɩ]]].
  • Replace I with ɩ[ɩ].

It’s easy to implement this conversion:

class SKISymbol def to_iota self end end
class SKICall def to_iota SKICall.new(left.to_iota, right.to_iota) end end
def S.to_iota SKICall.new(IOTA, SKICall.new(IOTA, SKICall.new(IOTA, SKICall.new(IOTA, IOTA)))) end
def K.to_iota SKICall.new(IOTA, SKICall.new(IOTA, SKICall.new(IOTA, IOTA))) end
def I.to_iota SKICall.new(IOTA, IOTA) end

But we wonder ourselves, why this is like this? So, we’re going to see why, by converting the Iota expressions to SKI calculus again:

expression = S.to_iota => ɩ[ɩ[ɩ[ɩ[ɩ]]]] ɩ[ɩ[ɩ[ɩ[ɩ]]]] ɩ[ɩ[ɩ[ɩ[S][K]]]] ɩ[ɩ[ɩ[S[S][K][K]]]] ɩ[ɩ[ɩ[S[K][K[K]]]]] ɩ[ɩ[S[K][K[K]][S][K]]] ɩ[ɩ[K[S][K[K][S]][K]]] ɩ[ɩ[K[S][K][K]]] ɩ[ɩ[S[K]]] ɩ[S[K][S][K]] ɩ[K[K][S[K]]] ɩ[K] K[S][K] S
expression = K.to_iota => ɩ[ɩ[ɩ[ɩ]]] ɩ[ɩ[ɩ[ɩ]]] ɩ[ɩ[ɩ[S][K]]] ɩ[ɩ[S[S][K][K]]] ɩ[ɩ[S[K][K[K]]]] ɩ[S[K][K[K]][S][K]] ɩ[K[S][K[K][S]][K]] ɩ[K[S][K][K]] ɩ[S[K]] S[K][S][K] K[K][S[K]] K
expression = I.to_iota => ɩ[ɩ] ɩ[ɩ] ɩ[S][K] S[S][K][K] S[K][K[K]]

We can see that S and K when are converted to SKI calculus, become the combinator, but with I is different, it’s clear that “S[K][K[K]]” isn’t syntactically equal to I, but it’s another example of an expression that uses the S and K combinators to do the same thing as I:

identity = SKICall.new(SKICall.new(S, K), SKICall.new(K, K)) => S[K][K[K]] expression = SKICall.new(identity, x) => S[K][K[K]][x] while expression.reducible? puts expression expression = expression.reduce end; puts expression S[K][K[K]][x] K[x][K[K][x]] K[x][K] x

So the translation into Iota does preserver the individual behavior of all three SKI combinators, but doesn’t preserve their syntax.

In the next post, we’re going to see more universal systems. If you have any doubts about this post, talk with me on Facebook or Twitter