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