Theory of Computation #18

The basic loop construct is rather easy to write and looks like this. I used the var A as the counter.

The problem is that doesn’t have a body. All it does it increment its counter until it is zero. So let’s write a function which takes a vector of parsed commands and returns the final state.

Okay, that works. The idea is again pretty basic. You can see that I use a looping function. It does what the name says it does. It loops over a var name. Interesting enough it calls the execute function:

So they basically bootstrap each other. If you followed me alone you noticed that execute is also the interpreter. We write some last tests and we’re done:

It works. This took quite some time, probably the longest so far. But I’m quite proud that I wrote my first interpreter :D

Theory of Computation #17

Ok, now we can parse the individual statements. Let’s start with easier ones: incr and decr. What we ant is a hash-map which looks like this:

What we want to do is pattern-matching. I will some regex for each one which works fine here for individual statements. The variable names can consist of digits, lower and uppercase letters and underscores.

Here’s the code:

The next thing I want to do is to create variables dynamically. I integrate this into the function decr and incr first, just because it’s easier. The creation of variables int he while statement is a special case because automatically it won’t do the stuff in it because the variable is bound to 0 intially.


Last part tomorrow

Theory of Computation #16

Exercise 4.1.1: What is the result of applying the function ( pi(2,2) x pi(2,1)) o (pi(3,1) x pi(3,3)) to the three-tuple (5,4,7)?

The function pi(x,y) returns the yth element of an x-tuple. x is the combinator and o the composition. Therefore we first get (5, 7) which is then put into the first pi tuple to return (7,5).

Exercise 4.1.2: If f: N -> N is defined by

what is the value of f(3)?

So, C() returns 0. and u adds one to its input.

Let’s see, f(3) expands the following way:

and now reduces to:


Exercise 4.5.2P: Write an interpreter for the bare-bones programming language in this chapter.

The bare-bones programming language consists of just three statements. There is:

  • incr name; which increases name by one
  • decr name; which decreases name by one, but only to 0
  • while name /= 0 do; … end; which repeats the statements between do and end until name is zero.

This language fulfills the Church-Turing thesis, i.e. it is Turing-complete but more based on the lambda calculus idea.

Here’s what will happen: We will input a string – our source code – into our program. It will create variables, I will set them to 0 automatically. And then it can start applying these statements. Let’s see how we do it.

My first idea is that we take a hash-map for our variables. They will be dynamically bound, i.e. global.

But before we can create variables, we need to parse the input. Let’s take this simple program as our test program:

This program sets i to 2 and then j to 2. That is, the end state should look like {“i” 2 “j” 2}.

The first thing I want is each statement individually:

That’s pretty easy:

Next part tomorrow

Theory of Computation #15

Next we need a function which matches the rules with the current state:

Let’s say we have two rules:

And the current state {:state 2 :head 1}. We now want our function to compare the states and read the head position and return the matching rule.

Which is also pretty easy to write:

Ok. Now let’s put everything together. And here we go:

The idea is pretty basic (god I love Lisps) we just find the matching state and apply it results and do that as long we reach an halting state (0). I included a print function at the start of the loop to see what’s happening. In our case we can see the following:

Yeah :)