# 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

```f(0) = C()
f(y + 1) = (u o u) o f(y)```

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:

```f(2 + 1) = (u o u) o f(2)
f(1 + 1) = (u o u) o f(1)
f(0 + 1) = (u o u) o f(0)
f(0) = 0```

and now reduces to:

```f(0 + 1) = (u o u) o 0 = 2; u(0) = 1, u(1) = 2
f(1 + 1) = (u o u) o 2 = 4
f(2 + 1) = (u o u) o 4 = 6 = f(3).```

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.

```{"test" 2
"foobar" 42}```

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

`incr i; incr i; while i /= 0 do; incr j; end;`

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:

`(get-statements sourcecode) -> ["incr i" "incr i" "while i /= 0 do" "incr j" "end"]`

That’s pretty easy:

```(defn get-statements
"Returns individual statements"
[sourcecode]
(map clojure.string/trim (clojure.string/split sourcecode #";")))

(deftest test-statements
(is (= (get-statements "incr i; decr i;") ["incr i" "decr i"]))
(is (= (get-statements "while j /= 0 do; incr abc; incr def; end;") ["while j /= 0 do" "incr abc" "incr def" "end"]))
(is (= (get-statements "") [""])))
```

Next part tomorrow

This site uses Akismet to reduce spam. Learn how your comment data is processed.