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