Mateus Jabour

Menu

Understanding how computation works part 5-2

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 what more we can do with lambda calculus, we’re going to also try to implement an interpreter for lambda calculus and parse this interpreter.

Using just procs to build a program is quite a challenge, but we’ve seen that’s possible, let’s take a look at a couple of techniques for writing code in this minimal style.

Infinite streams

Streams are pretty interesting to implement, because it’s an infinite list that we can do whatever we want just by using FIRST and REST, with this we can implement lists that calculate their contents on the fly. Look at one implementation of an infinite stream of zeros:

ZEROS = Z[-> f { UNSHIFT[f][ZERO] }]

We will need to update the method to_array so we can limit the number of elements we want to display, instead of receiving a infinite array. Let’s do it:

def to_array(proc, count = nil) array = []
until to_boolean(IS_EMPTY[proc]) || count == 0 array.push(FIRST[proc]) proc = REST[proc] count = count - 1 unless count.nil? end
array end

Now, we can visualize how it works:

to_array(ZEROS, 5).map { |p| to_integer(p) } => [0, 0, 0, 0, 0] to_array(ZEROS, 10).map { |p| to_integer(p) } => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Here, we don’t have any calculation of a new element. An other interesting thing to implement is the proc that counts upwards from a given number:

UPWARDS_OF = Z[ -> f { -> n { UNSHIFT[ -> x { f[INCREMENT[n]][x] }][n] } }]

Let’s see if how it works:

to_array(UPWARDS_OF[ZEROS], 5).map { |p| to_integer(p) } => [0, 1, 2, 3, 4] to_array(UPWARDS_OF[FIFTEEN], 5).map { |p| to_integer(p) } => [15, 16, 17, 18, 19]

A more complex is the stream that contains all multiples of a given number:

MULTIPLES_OF = -> m { Z[-> f { -> n { UNSHIFT[-> x { f[ADD[m][n]][x] }][n] } }][m] } to_array(MULTIPLES_OF[TWO], 5).map { |p| to_integer(p) } => [2, 4, 6, 8, 10]

We can manipulate those streams like lists, using map, for example:

to_array(MAP[MULTIPLES_OF[TWO]][INCREMENT], 5).map { |p| to_integer(p) } => [3, 5, 7, 9, 11]

We can even write procs that combine two streams to make a third:

MULTIPLY_STREAMS = Z[-> f { -> k { -> l { UNSHIFT[-> x { f[REST[k]][REST[l]][x] }][MULTIPLY[FIRST[k]][FIRST[l]]] }} }] to_array(MUTIPLY_STREAMS[UPWARDS_OF[ONE]][MULTIPLES_OF[THREE]], 5).map { |p| to_integer(p) } => [3, 12, 27, 48, 75]

Avoiding arbritary recursion

As we saw on the implementations of MOD and RANGE, we needed to use the Z combinator, so those procs could work. The Z combinator is very convinient, but not ideal, we can implement those procs without using the Z combinator. Let’s try yo implement MOD without it, we know that MOD works by repeatedly subtracting n from m as long as n <= m, using recursive calls of MOD. But, instead of using recursion we start to use a fixed number to check if n <= m, we don’t know exactly how many time we need to check it, but it isn’t a big problem to check more than we need, right?

def decrease(m, n) if n <= m m - n else m end end decrease(17, 5) => 12 decrease(decrease(17, 5), 5) => 7 decrease(decrease(decrease(17, 5), 5), 5) => 2 decrease(decrease(decrease(decrease(17, 5), 5), 5), 5) => 2

Now we can rewrite the MOD proc to take a number and substracts n from it or just returns it. This proc gets called m times on m itself, so we can get the result:

MOD = -> m { -> n { m[ -> x { IF[IS_LESS_OR_EQUAL[n][x]][ SUBTRACT[x][n] ][ x ] }] } }

Let’s check it:

to_integer(MOD[THREE][TWO]) => 1

Cool, implementing RANGE is harder, but we can try to use the same thinking of DECREMENT here: implement a function that, when called n time on a value, returns a list of n numbers from the desired range. This first function would be a countdown:

def countdown(pair) [pair.first.unshift(pair.last), pair.last - 1] end
countdown([[], 10]) => [[10], 9] countdown(countdown([[], 10])) => [[9, 10], 8] countdown(countdown(countdown([[], 10]))) => [[8, 9, 10], 7]

This is easy to convert into procs:

COUNTDOWN = -> p { PAIR[UNSHIFT[LEFT][p]][RIGHT[p]][DECREMENT[RIGHT[p]]] }

And now, the new RANGE will look like this:

RANGE = -> m { -> n { LEFT{INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]] } } }

Implementing the Lambda Calculus

Now that we now a lot about Lambda Calculus, we can try to implement an interpreter for it, let’s start implementing it by the syntax. We know that we have 3 primordial things in Lambda Calculus: variables, functions and the calls, so, we’re going to implement a class for each of those items:

class LCVariable < Struct.new(:name) def to_s name.to_s end
def inspect to_s end end
class LCFunction < Struct.new(:parameter, :body) def to_s "-> #{parameter} { #{body}}" end
def inspect to_s end end
class LCCall < Struct.new(:left, :right) def to_s "#{left}[#{right}]" end
def inspect to_s end end

These classes let us build abstract syntax trees of lambda calculus expressions, just like we did on previous posts. Look what we can do:

one = LCFunction.new(:p, LCFunction.new(:x, LCCall.new(LCVariable.new(:p), LCVariable.new(:x)) ) ) => -> p { -> x { p[x]}} increment = LCFunction.new(:n, LCFunction.new(:p, LCFunction.new(:x, LCCall.new( LCVariable.new(:p), LCall.new( LCCall.new(LCVariable.new(:n), LCVariable.new(:p)), LCVariable.new(:x) ) ) ) ) ) => -> n { -> p { -> x { p[n[p][x]]}}}

Now, let’s talk about semantics, we’re going to use small-step to implement the reduce method, let’s start by replacing variables:

class LCVariable def replace(name, replacement) if self.name == name replacement else self end end end
class LCFunction def replace(name, replacement) if parameter == name self else LCFunctio.new(parameter, body.replace(name, replacement)) end end end
class LCCall def replace(name, replacement) LCCall.new(left.replace(name, replacement), right.replace(name, replacement)) end end

Let’s see their effect:

expression = LCVariable.new(:x) => x expression.replace(:x, LCFunction.new(:y, LCVariable.new(:y))) => -> y { y }

For functions, we have a problem, the replace method just have effect inside the function’s body, and just make the replacement on free variables:

expression = LCFunction.new(:y, LCCall.new(LCVariable.new(:x), LCVariable.new(:y)) ) => -> y { x[y] } expression.replace(:x, LCVariable.new(:z)) => -> y { z[y] } expression.replace(:y, LCVariable.new(:z)) => -> y { x[y] }

This lets us replace occurrences of a variable without accidentally changing unrelated variables that happen to have the same name.

So, now that we have this feature, we need to think in a way of replacing the arguments values of a function, let’s think about the real execution: If we call a proc -> x, y { x + y } with the arguments 1 and 2, it will produce the expression 1 + 2 immediately, then, it will evaluate this expression and return the final result. With this in mind, let’s implement a method called “call”:

class LCFunction def call(argument) body.replace(parameter, argument) end end

This will be enough. To start reducing the expressions, we need to know if they’re callable and reducible:

class LCVariable def callable? false end
def reducible? false end end
class LCFunction def callable? true end
def reducible false end end
class LCCall def callable? false end
def reducible? left.reducible? || right.reducible? || left.callable? end end

And now, we can reduce it if the expression is reducible:

class LCCall def reduce if left.reducible? LCCall.new(left.reduce, right) elsif right.reducible? LCCall.new(left, right.reduce) else left.call(right) end end end

Now that everything is ready, we can parse all this interpreter using Treetop, let’s start:

grammar LambdaCalculus rule expression calls / variable / function end
rule calls first:(variable / function) rest: ('[' expression ']')+ { def to_ast arguments.map(&:to_ast).inject(first.to_ast) { |l, r| LCCall.new(l, r)} end
def arguments rest.elements.map(&:expression) end } end
rule variable [a-z]+ { def to_ast LCVariable.new(text_value.to_sym) end } end
rule function '-> ' parameter:[a-z]+ ' { ' body:expression ' }' { def to_ast LCFunction.new(parameter.text_value.to_sym, body.to_ast) end } end end

The operational semantics and the parser together give us a complete implementation of the lambda calculus.

If you have any doubts about this post, talk with me on Facebook or Twitter