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.

(defn looping
  "Loops over a varname with command list. Takes care of decrementing
   the counter."
  [state varname command-list]
  (let [all-commands (conj command-list {:decr varname})]
  (loop [new-state state]
    (if (zero? (new-state varname))
      new-state
      (recur
       (execute new-state all-commands))))))


(deftest test-looping
  (is (= (looping {"A" 3} "A" []) {"A" 0}))
  (is (= (looping {"A" 3 "B" 2} "B" [{:incr "A"}]) {"A" 5 "B" 0})))

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.

(defn execute-command
  "Executes a parsed command"
  [state parsed-command]
  (let [[command varname] (first parsed-command)]
    (cond (= command :incr) (do-var state varname command)
          (= command :decr) (do-var state varname command)
          :else nil)))


(deftest test-execute
  (is (= (execute-command {} {:incr "A"}) {"A" 1}))
  (is (= (execute-command {"A" 3} {:decr "A"}) {"A" 2}))
  (is (= (execute-command {"A" 3} {:decr "B"}) {"A" 3 "B" 0})))
                          



(defn execute
  "Executes a list of parsed commands given a state"
  [state parsed-source]
  (loop [rest-source parsed-source
         new-state state]
       (if (seq rest-source)
      (if (contains? (first rest-source) :while)
        (let [inner-loop (take-while #(not (contains? % :end)) (rest rest-source))]
          (recur
           (rest (drop-while #(not (contains? % :end)) rest-source))
           (looping new-state ((first rest-source) :while) inner-loop)))
        (recur
         (rest rest-source)
         (execute-command new-state (first rest-source))))
      new-state))) 


(with-test
  (def source "incr A; incr B; decr A; incr B;")
  (def parsed-source (map parse-statement (get-statements source)))
  (is (= (execute {} parsed-source) {"A" 0 "B" 2}))
  (is (= (execute {"A" 2 "B" 5} parsed-source) {"A" 2 "B" 7})))

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:

(defn looping
  "Loops over a varname with command list. Takes care of decrementing
   the counter."
  [state varname command-list]
  (let [all-commands (conj command-list {:decr varname})]
  (loop [new-state state]
    (if (zero? (new-state varname))
      new-state
      (recur
       (execute new-state all-commands))))))

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:

(deftest test-interpreter
  (def source "incr i; incr i; while i /= 0 do; incr j; end; incr j;")
  (def parsed-source (map parse-statement (get-statements source)))
  (is (= (execute {} parsed-source) {"j" 3 "i" 0}))
  (is (= (execute {"i" 4 "k" 6} parsed-source) {"i" 0 "j" 7 "k" 6})))

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:

(parse-statement "incr i") -> {:incr "i"}
(parse-statement "decr i") -> {:incr "i"}
(parse-statement "while j /= 0 do") -> {:while "j"}
(parse-statement "end") -> {:end nil}

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:

(def statement-patterns
  [#"(incr) (\w+)"
   #"(decr) (\w+)"
   #"(while) (\w+) /= 0 do"
   #"(end)"])


(defn parse-statement
  "Parses a given statement and returns a hashmap with optional variable"
  [string]
  (let [matches (map #(re-matches % string) statement-patterns)
        [_ statement & var] (first (filter identity matches))]                      
    (if (not (nil? statement))
      (hash-map (keyword statement) (first var))
      nil)))
   

(deftest test-parse
  (is (= (parse-statement "incr foo") {:incr "foo"}))
  (is (= (parse-statement "decr bar42") {:decr "bar42"}))
  (is (= (parse-statement "while 4foo /= 0 do") {:while "4foo"}))
  (is (= (parse-statement "end") {:end nil}))
  (is (= (parse-statement "foobaz i") nil)))

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.

(defn dec-limited
  "Decreases a variable by one but only down to 0"
  [x]
  (if (= x 0) 0
      (dec x)))

; partial function for do-var
(def var-manipulation
  (fn [state varname fun]
    (assoc state varname
           (if (contains? state varname)
             (fun (state varname))
             (fun 0)))))


(defn do-var
  "Takes a state, varname and command and returns a new modified state"
  [state varname command]
  (cond (= command :incr) (var-manipulation state varname inc)
        (= command :decr) (var-manipulation state varname dec-limited)))



(deftest test-do-var
  (def state {"A" 0 "B" 2})
  (is (= (do-var state "A" :decr) {"A" 0 "B" 2}))
  (is (= (do-var state "B" :incr) {"A" 0 "B" 3}))
  (is (= (do-var state "C" :decr) {"A" 0 "B" 2 "C" 0})) 
  (is (= (do-var state "C" :incr) {"A" 0 "B" 2 "C" 1})))

 

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

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

Theory of Computation #15

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

Let’s say we have two rules:

{:start 1 :symbol :a :write :right :end 2}
{:start 2 :symbol :b :write nil :end 0}

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.

(find-matching-rule machine-state rules) -> {....}

Which is also pretty easy to write:

(defn find-matching-rule
  "Finds a matching rule given machine-state and rules"
  [machine-state rules]
  (let
      [matching-state (filter #(= (machine-state :state) (% :start)) rules)]
    (filter #(= (read-tape tape (machine-state :head)) (% :symbol)) matching-state)))

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

(defn run-turing-machine
  "Simulates a turing machine."
  [my-tape]
  (loop [machine-state {:state 1 :head 0}
         tape my-tape]
        (println "Machine state:" machine-state ", tape:" tape)
    (if (zero? (machine-state :state))
      nil
      (let [matching-rule (first (find-matching-rule machine-state rules))]
        (println "> Matching rule:" matching-rule)
        (cond (= (matching-rule :write) :left)
              (recur (assoc machine-state
                       :state (matching-rule :end)
                       :head (move-head (machine-state :head) :left))
                     tape)
              (= (matching-rule :write) :right)
              (recur (assoc machine-state
                       :state (matching-rule :end)
                       :head (move-head (machine-state :head) :right))
                     tape)
              :else
              (recur (assoc machine-state
                       :state (matching-rule :end))
                     (write-tape
                      tape
                      (machine-state :head)
                      (matching-rule :write))))))))



(with-test  
  (def machine-state {:state 2 :head 1})
  (def rules [{:start 1 :symbol :a :write :right :end 2}
              {:start 2 :symbol :b :write nil :end 0}])
  (is (= (find-matching-rule machine-state rules) [{:start 2 :symbol :b :write nil :end 0}])))

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:

Machine state: {:state 1, :head 0} , tape: [:a :b nil :a :a]
> Matching rule: {:symbol :a, :start 1, :write :right, :end 2}

Machine state: {:state 2, :head 1} , tape: [:a :b nil :a :a]
> Matching rule: {:symbol :b, :start 2, :write nil, :end 0}

Machine state: {:state 0, :head 1} , tape: [:a nil nil :a :a]

Yeah :)