{"id":314,"date":"2012-08-10T22:25:31","date_gmt":"2012-08-10T12:25:31","guid":{"rendered":"http:\/\/juliangamble.com\/blog\/?p=314"},"modified":"2013-12-27T10:32:52","modified_gmt":"2013-12-26T23:32:52","slug":"the-little-schemer-in-clojure-chapter-4-numbers-games","status":"publish","type":"post","link":"https:\/\/juliangamble.com\/blog\/2012\/08\/10\/the-little-schemer-in-clojure-chapter-4-numbers-games\/","title":{"rendered":"The Little Schemer in Clojure \u2013 Chapter 4 \u2013 Numbers Games"},"content":{"rendered":"

This is the fourth Chapter of a series of posts about porting\u00a0The Little Schemer<\/a>\u00a0to Clojure. You may wish to\u00a0read the intro<\/a>.<\/em><\/p>\n

You’ll notice that in the first three chapters, we introduced lists [Ch1]<\/a>, then we pulled things out of lists [Ch2]<\/a>, and then we built lists [Ch3]<\/a>. The bigger principle of the book is to be able to operate on data structures with a minimal set of primitives using the power of recursion and lambdas.<\/p>\n

Now we’re driving at the meta-circular interpreter with these principles. We also want to be able to do mathematical operations, and yet still keep a minimal number of primitives. Interestingly enough, we’ll just use equals<\/code>, add1<\/code> and sub1<\/code> and build up to multiplication, division and exponents. So let’s get started!<\/p>\n

Our first function is +_<\/code> (plus) – we’re going to define it terms of add1 and sub1. (We’ll rename the functions with an _ suffix so they don’t clash with the existing clojure definitions of +<\/code> and zero?<\/code><\/p>\n

\r\n(def zero_?\r\n  (fn [n]\r\n    (= 0 n)))\r\n\r\n(def add1\r\n  (fn [n]\r\n    (+ 1 n)))\r\n\r\n(def sub1\r\n  (fn [n]\r\n    (- n 1)))\r\n\r\n(def +_\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? m) n\r\n      true (add1 (+ n (sub1 m))))))\r\n\r\n(println (+_ 1 2))\r\n<\/pre>\n
Now this is kind of frustrating. Why bother doing all this recursion for an operation that is already built into the CPU? Especially when you limit yourself to integers anyway?<\/p>\n
This is about making you think about numeric implementations. Part of it is that LISPs generally implement their own ‘numeric tower’ – you can see what fresh thinking has done for Clojure’s ability to handle numbers – particularly irrational fractions.<\/p>\n
The other reason is the purity of the metacircular interpreter that you’ll build – you’ll literally be able to count the number of primitives required to build it and have no holes. (There is an assumption that recursion is cheap.)<\/p>\n
Our next function is – (minus) which is quite similar to the above:<\/p>\n
\r\n(def -_\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? m) n\r\n      true (sub1 (- n (sub1 m))))))\r\n\r\n(println (-_ 2 1))\r\n<\/pre>\n
From here we extend our concept of the lat<\/code> (a List-ATom) – being a non-nested list of atoms. We extend it to what the book calls a vec<\/code>, which is a non-nested list of integers.<\/p>\n
From here we arrive at [The Fourth Commandment]. This states When recurring on a list of atoms, lat<\/code>, or a vec<\/code>, ask two questions about them, and use (cdr lat)<\/code> or (cdr vec)<\/code> for the natural recursion.<\/p>\n
It then goes on to apply this to lists of numbers as well. It goes on: When recurring on a number, n<\/code>, ask two questions, and use (sub1 n)<\/code> for the natural recursion.<\/p>\n
Now we get to the addvec<\/code> function. This is really like a sum<\/code> function from sql land:<\/p>\n
\r\n(def addvec\r\n  (fn [vec]\r\n    (cond\r\n      (empty? vec) 0\r\n      true (+_ (first vec) (addvec (rest vec))))))\r\n\r\n(println (addvec '(1 2 3)))\r\n<\/pre>\n
Next we look at the multiply function *_<\/code>.<\/p>\n
\r\n(def *_\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? m) 0\r\n      true (+_ n (*_ n (sub1 m))))))\r\n\r\n(println (*_ 4 5))\r\n<\/pre>\n
Again – we’ve built this in terms of our existing primitives.<\/p>\n
Now we get onto The Fifth Commandment<\/em>. I know these could come across as boring and self-righteous. On the other hand, if you write recursive code from scratch (and don’t rely on a library to do it for you) you want to have absolute confidence that it will run and terminate as you expect. These Commandments give you that confidence.<\/p>\n
The Fifth Commandment states: When building a value with +_<\/code>\u00a0(plus), always use 0<\/code> for the value of the terminating line, for adding 0 does not change the value of an addition.<\/p>\n
It goes on to say: when building a value with *_<\/code>(multiply), always use 1<\/code> for the value of the terminating line, for multiplying by 1 does not change the value of a multiplication.<\/p>\n
It then finishes with: when building a value with cons<\/code>, always consider ()<\/code> for the value of the terminating line.<\/p>\n
Now we’ll look at vec+<\/code>. The big idea is to be able to add two lists of numbers matching each corresponding element in the sum operation. This has uses in matrix operations:<\/p>\n
\r\n(def vec+\r\n  (fn [vec1 vec2]\r\n    (cond\r\n      (empty? vec1) vec2\r\n      (empty? vec2) vec1\r\n      true (cons (+_ (first vec1) (first vec2))\r\n             (vec+\r\n               (rest vec1) (rest vec2))))))\r\n\r\n(println (vec+ '(1 2 3) '(4 5 6)))\r\n<\/pre>\n
Now we’ll look at >_<\/code>(greater than). We’ll define it in terms of our primitives.<\/p>\n
\r\n(def >_\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? n) false\r\n      (zero_? m) true\r\n      true (>_ (sub1 n) (sub1 m)))))\r\n\r\n(println (>_ 10 1))\r\n(println (>_ 1 10))\r\n<\/pre>\n
We’ll reuse this for less-than. It actually turns out remarkably similar:<\/p>\n
\r\n(def <_\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? m) false\r\n      (zero_? n) true\r\n      true (<_ (sub1 n) (sub1 m)))))\r\n\r\n(println (>_ 10 1))\r\n(println (>_ 1 10))\r\n<\/pre>\n
Next we’ll define equals:<\/p>\n
 \r\n(def =_   \r\n  (fn [n m]     \r\n    (cond       \r\n      (>_ n m) false\r\n      (<_ n m) false      \r\n      true true)))\r\n\r\n(println "=_")\r\n(println (=_ 1 10))\r\n(println (=_ 10 1))\r\n(println (=_ 10 10))\r\n<\/pre>\n
Next we’ll look at exponents:<\/p>\n
\r\n(def exp\r\n  (fn [n m]\r\n    (cond\r\n      (zero_? m) 1\r\n      true (*_ n (exp n (sub1 m))))))\r\n\r\n(println (exp 2 3))\r\n<\/pre>\n
Now we’ll start using our numbers functions on atoms and lats – this gets used in our metacircular evaluator later. First we’ll start with length:<\/p>\n
\r\n(def length\r\n  (fn [lat]\r\n    (cond\r\n      (empty? lat) 0\r\n      true (add1 (length (rest lat))))))\r\n\r\n(println (length '(pasta with pesto and mushrooms)))\r\n<\/pre>\n
Now we’re going to write a function pick<\/code> to get an item out of a list using an index.<\/p>\n
\r\n(def pick\r\n  (fn [n lat]\r\n    (cond\r\n      (empty? lat) '()\r\n      (zero_? (sub1 n)) (first lat)\r\n      true (pick (sub1 n) (rest lat)))))\r\n\r\n(println (pick  3 '(pasta with pesto and mushrooms)))\r\n<\/pre>\n
Now we’re going to extend this to remove an indexed item from a list using rempick<\/code>:<\/p>\n
\r\n(def rempick\r\n  (fn [n lat]\r\n    (cond\r\n      (empty? lat) '()\r\n      (zero_? (sub1 n)) (rest lat)\r\n      true (cons (first lat)\r\n             (rempick\r\n               (sub1 n) (rest lat))))))\r\n\r\n(println (rempick  2 '(pasta with pesto and mushrooms)))\r\n<\/pre>\n
Now we’re going to write a function to strip all the numbers out of a list. We’ll cheat a little bit, as we’ll introduce a new primitive function number?<\/code>. We’ll call our strip function no-nums<\/code>.<\/p>\n
\r\n(def no-nums\r\n  (fn [lat]\r\n    (cond\r\n      (empty? lat) '()\r\n      true (cond\r\n             (number? (first lat)) (no-nums (rest lat))\r\n             true (cons (first lat)\r\n                    (no-nums (rest lat)))))))\r\n\r\n(println (no-nums  '(1 potato 2 potato 3 potato 4)))\r\n<\/pre>\n
This time we’ll flip it over – and write a function to strip out all the non-numbers from the list:<\/p>\n
\r\n(def all-nums\r\n  (fn [lat]\r\n    (cond\r\n      (empty? lat) '()\r\n      true (cond\r\n             (number? (first lat)) (cons (first lat) (all-nums (rest lat)))\r\n             true (all-nums (rest lat))))))\r\n\r\n(println (all-nums  '(1 potato 2 potato 3 potato 4)))\r\n<\/pre>\n
Our final function eqan?<\/code> is our first building block towards rewriting the equals function in terms of our own primitives. This function will get us about half way there:<\/p>\n
\r\n(def eqan?\r\n  (fn [a1 a2]\r\n    (cond\r\n      (number? a1)\r\n        (cond\r\n          (number? a2) (=_ a1 a2)\r\n          true false)\r\n      (number? a2) false\r\n      true (= a1 a2))))\r\n\r\n(println (eqan?  1 10))\r\n(println (eqan?  10 1))\r\n(println (eqan?  10 10))\r\n(println (eqan?  'a 'b))\r\n(println (eqan?  'a 'a))\r\n<\/pre>\n
Conclusion<\/strong>
\nThis chapter we’ve introduced two new primtives add1<\/code> and sub1<\/code> – and used them along with all our existing primitives to build all the functions above.<\/p>\n
In total our primitives so far are: atom?<\/code>, null?<\/code>, first<\/code>, rest<\/code>, cond<\/code>, fn<\/code>, def<\/code>, empty?<\/code>, =<\/code>, cons<\/code>, add1<\/code> and sub1<\/code>. These are all the functions (and those in the chapters to come) that we’ll need to implement to get our metacircular interpreter working.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is the fourth Chapter of a series of posts about porting\u00a0The Little Schemer\u00a0to Clojure. You may wish to\u00a0read the intro. You’ll notice that in the first three chapters, we introduced lists [Ch1], then we pulled things out of lists … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[3,12],"tags":[],"class_list":["post-314","post","type-post","status-publish","format-standard","hentry","category-clojure","category-thelittleschemer"],"_links":{"self":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/314","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/comments?post=314"}],"version-history":[{"count":18,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/314\/revisions"}],"predecessor-version":[{"id":569,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/314\/revisions\/569"}],"wp:attachment":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/media?parent=314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/categories?post=314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/tags?post=314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}