Counting with Fingers

Primitive arithmetic operations +, -, *, /, ** are taken for granted in most programming languages. But a language need not necessarily support primitive arithmetic operations for it to be turing complete. Increment and decrement are the basic operations available in certain minimal turing complete languages like BF. How would you go about performing addition, multiplication, exponential in such a language with just Increment and decrement operations? It's certainly possible, but a short digression on the history of counting devices follows.

Counting was one of the primary reasons the computer was invented. There were numerous counting devices before the computer. The most primitive way was the tally marks found in egyptian cave drawings. Counting with fingers was also a common method as taught in primary schools. Chinese invented the abacus to aid in counting. Then came the mechanical and electronic calculators and computers.











How will you implement addition without +, multiplication without *, and exponentiation without ** ? Exponentiation is just repeated multiplication. Multiplication is just repeated addition and addition is just....well, repeated incrementation.

Think of the way you were taught addition in school. How did you add 2 and 3? You kept 2 fingers in one hand(left), 3 in the other (right).







You deduct one from left and add one to right.







You deduct one from left and add one to right.







Voila! You have no more fingers left in your left hand and the answer in your right hand. And all you needed to do was increment and decrement in alternate hands.

The only limitation is you have only five fingers in each hand. Even with the five fingers in each leg, it isn't much. Counting in this way isn't practical for larger number unless you have infinite fingers in each hand. But computers have a large memory (analogical fingers). And it is possible to add numbers using just increment and decrement as demonstrated previously.

An implementation of this in Scheme would look like this. [Scheme has primitive add1 and sub1 for increment and decrement]


(define (add n x)
(cond
[(zero? n) x]
[else (add1 (add (sub1 n) x))]
)
)


This is what happens if we use this function to add 5 and 8


(add 5 8)
= (1 + (add 4 8))
= (1 + (1 + (add 3 8)))
= (1 + (1 + (1 + (add 2 8))))
= (1 + (1 + (1 + (1 + (add 1 8)))))
= (1 + (1 + (1 + (1 + (1 + (add 0 8))))))
= (1 + (1 + (1 + (1 + (1 + 8)))))
= (1 + (1 + (1 + (1 + 9))))
= (1 + (1 + (1 + 10)))
= (1 + (1 + 11))
= (1 + 12)
= (13)


We have successfully used increment recursively to implement addition. Addition is a primitive recursive function. The same applies for Subtraction as well.

Now to implement multiplication without *, you can implement it recursively using + or add that we implemented just now:

(define (multiply n x)
(cond
[(zero? n) 0]
[else (add x (multiply (sub1 n) x))]
)
)

This is what happens if we use this function to multiply 4 and 5


(multiply 4 5)
= (5 + (multiply 3 5))
= (5 + (5 + (multiply 2 5)))
= (5 + (5 + (5 + (multiply 1 5))))
= (5 + (5 + (5 + (5 + (multiply 0 5)))))
= (5 + (5 + (5 + (5 + 0))))


...Before we reduce it further, we have a choice. We can abstract the addition as understood previously or delve deeper into how the addition is performed recursively.

= (5 + (5 + (5 + 5)))

= (5 + (5 + 10))

OR

(5 + (5 + (1 + (1 + (1 + (1 + (1 + 5)))))))

finally evaluating to

= 20

Now to implement exponent without **, you can implement it recursively using * or multiply that we implemented just now, which in turn is recursively implemented using + or add:


(define (exponent x n)
(cond
[(zero? n) 1]
[else (multiply x (exponent x (sub1 n)))]
)
)


This is what happens if we use this function to calculate 2**3


(exponent 2 3)
= (2 * (exponent 2 2))
= (2 * (2 * (exponent 2 1)))
= (2 * (2 * (2 * (exponent 2 0))))
= (2 * (2 * (2 * 1)))


The multiplications are evaluated recursively through addition, and the additions are evaluated recursively through increment.

Arithmetic operations can be computed recursively was a re-revelation to me on reading 'how to design programs' long after forgetting how to count with fingers.

Brainf****d

I got brainf****d on a Saturday afternoon. No i didn't get admitted for psychological reasons. Brainf*** is an esoteric programming language. Its a turing complete language with as few as 8 instructions:

>	Increment the pointer
<	Decrement the pointer
+	Increment the byte at the pointer
-	Decrement the byte at the pointer
.	Output the byte at the pointer
,	Input a byte and store it in the byte at the pointer
[	Jump forward past the matching ] if the byte at the pointer is zero
]	Jump backward to the matching [ unless the byte at the pointer is zero

Click here for a brief description of the language. The wikipedia entry is more detailed spoiling the fun in discovering the quirks of the language.

I started writing an interpreter for BF in Ruby, which was a simple switch. But the interesting part is actually writing code in BF. Its much more challenging than Assembly language because of the instruction set and using a tape like memory without any registers.

Here is the BF interpreter in Ruby:

if ARGV.length != 1
 puts "Usage: ruby brainfuck.rb filename"
 exit
end
mem = Array.new(30000,0x00)
loopstack = Array.new
p = 0

code  = File.open(ARGV[0]).readlines.join("")

i=0
while i < code.length
 case code[i]
 when '>'
   p += 1
 when '<'
   p -= 1
 when '+'
   mem[p] += 1
 when '-'
   mem[p] -= 1
 when '.'
   print mem[p].chr
 when ','
   mem[p] = STDIN.getc
 when '['
   if mem[p].zero?
     i = code.index(']',i)
   else
     loopstack.push i
   end
 when ']'
   if(mem[p].zero?)
     loopstack.pop
   else
     i = loopstack.last
   end
 end
 i+=1
end

And here is the traditional HelloWorld program in BF:

#H
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++
.
>
#e
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#o
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++
.
>
#SPACE
++++++++++++++++++++++++++++++++
.
>
#w
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++
.
>
#o
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++
.
>
#r
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#d
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
.

So long for HelloWorld? This would probably be the worst language for beginners!

The only work in the Interpreter was managing loops expressed using [ and ]. I ended up using a stack to manage loops similar to the way stacks are used in procedural languages to transfer control to methods and return back.

Here is a program to iterate from 0 to 9 in BF:

#ASCII value of 0
++++++++++++++++++++++++++++++++++++++++++++++++
>
#Loop counter variable
++++++++++
[
< . + >
-
]

Self generating code (or Why Recursion is a wonderful idea)

Self-modifying code is the fancy of every assembly language enthusiast. You can write self modifying code when code and data are in the same accessible area of memory, and your code can modify the instructions of itself. I have never written self-modifying code myself, but have always admired the possibilities of it.

Self-generating code is possible in dynamic languages like Ruby and Javascript through the eval statement. It's commonly referred to as metaprogramming in Ruby. I recently came across a very common problem that made me think of a metaprogramming solution. Imagine you have a set [A, B, C, D]. How do you find all the different combinations of it - [A], [B], [C], [D], [A,B], [A,C], [A,D], [B,C]......[A,B,C,D]?

Lets break down the problem. To find all different combinations, you need to find the combinations selecting 1 at a time, selecting 2 at a time and so on:
C = nC1 + nC2 + .... + nCn

To find the combination nCr, you can find the permutation and take the unique sets:

To find the permutation nPr (n=4, r=3), a simple pseudo code would look like

permutations= []
set = ['A','B','C','D']
for i in 0 to n-1
for j in 0 to n-1
for k in 0 to n-1
permutations << [set[i], set[j], set[k]]
end
end
end


It has n-levels of nested loops and its difficult to write n levels of nesting in code when n is dynamic. You can't write code for a fixed-n. The code must be intelligent enough to generate n-level nested loops (or you can recur, but lets hold on to a non-recursive solution). This can be expressed using Ruby each as:


set.each {|i1|
set.each {|i2|
set.each {|i3|
permutations << [i1, i2, i3]
}
}
}


Metaprogramming, like Recursion, is all about finding patterns, and you can easily spot code segments repeated thrice for r = 3. This can be expressed using eval as:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "set.each{|i#{i}| "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r
permutations
end


This code has a flaw because it included duplicates in each iteration. It can be fixed by not considering the elements of preceding iterations in the set for the current iteration. The modified code is:


set.each {|i1|
(set - [i1]).each {|i2|
(set - [i1] -[i2]).each {|i3|
permutations << [i1, i2, i3]
}
}
}


In eval, this translates to:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "(set " + (1...i).collect {|j| " - [i#{j}]"}.join('') +").each{i#{i} "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r permutation
end


Combination can be expressed using permutation as:


def combinate(set,n)
permutate(set_n).collect{|s| s.sort}.to_set.to_a
end


Now, the original problem can be solved by computing the combinations from 1 to n:


def combinations(set)
(1..set.size).collect {|i| combinate(set,i)}
end


It was a tricky use of eval and looping to generate code on the fly. But why bother with tricky syntactic details and code generation, when the compiler/interpreter can manage all the grunt work for you. Thats why Recursion is such a wonderful idea

Schrodinger's Cat of Programming (or My understanding of Godel's Theorem)

Little Schemer deals with a few mathematical theorems through simple examples. It has an easily understandable explanation of Godel's incompleteness theorem. Eventhough the book primarily focusses on recursion, at one point it addresses the problem of infinite recursion. It happens only for partial functions for which you cant have a definite exit criteria.

Consider the list (6 2 4 jerry 5 7 3) and the atom jerry. If your objective is to locate jerry by tracing from the first location, you will traverse like this:
[1] -> [6] -> [7] -> [3] -> [4] -> jerry

Its not always guaranteed to end. Now lets try another:
Consider the list (7 1 2 jerry 5 6 3)
[1] -> [7] -> [3] -> [2] -> [1] -> [7] -> [3] -> [2] -> [1] -> [7].........

Wait, this will never end. Tom will never find Jerry if he uses your function. Such functions are called partial functions and functions which always return a value like factorial are called total functions.

Now let's say you want to write a function that takes a function and determines if the function will stop execution or not. In functional programming languages, you can pass functions as first class variables. It'll look like this:

(define will-stop?
(lambda (fun)
...))

Let's assume that such a function is possible (Assume is a revealing word from mathematical induction and i guess i might have spoiled the suspense already)

Now we have a function to test. Lets call it try

(define try
(lambda(x)
...))

Now just for fun, lets write a function, which is guaranteed to never stop. Let's call it wont-stop

(define wont-stop
(lambda (x)
(wont-stop x)))

Now before passing try to will-stop?, lets implement try

(define try
(lambda (x)
(and
(will-stop? try)
(wont-stop x)
)))

Lets assume that will-stop works for try and returns true, which means try will stop. try evaluates to

(and true (wont-stop x))

which wont stop. Now that contradicts with the assumed output of will-stop?

Now lets assume that will-stop works for try and returns false, which means try will never stop. try evaluates to

(and false (wont-stop x))

which returns false. Effectively try has stopped when the assumed will-stop? predicted try will never stop.

Now the only possible explanation of this anomaly or paradox is that will-stop? can never be implemented.(Connect the dots because i'm still connecting).This is the essence of Godel's incompleteness theorem.

One book which is gathering dust in my bookshelf and i hope will have a better explanation of Godel's theorem is Godel, Escher and Bach. Another series of books which i have heard always culminates in an explanation of Godel's theorem using logical unsolvable puzzles are Raymond Smullyan's puzzle books. Until i get any of Smullyan's books, i found an explanation of Godel's theorem for dummies here.

Schrodinger's cat is a thought experiment in quantum mechanics which is equally bizzare. Imagine that we have a cat in a box and a GM counter which is triggered by an atom which may or may not decay. GM counter controls a hammer which shatters a flask of cyanide which might kill the cat. Now if you come back after an hour, the cat in the box may be alive or dead or both and you would never know until you actually open the box. The cat is in a half-dead,half-alive state and continues to have a superposition of multiple histories/states until the box is opened, when it becomes either dead or alive.

Back to our previous finding, For try, will-stop? wont stop if we assume will-stop? (try) will stop and will-stop? will stop if we assume will-stop? (try) wont stop.Now thats a paradoxical statement which makes Schrodinger's cat sound like simple probability.

Little Schemer (Review)

I have been reading the Little Schemer recently. Dan Friedman uses the Socratic style of teaching (Q&A style if you're not interested in Greek history), in which you learn by asking questions. It may sound like School, but its the simplest way to teach complex language ideas.

It uses Scheme which is a dialect of Lisp. Scheme has little in way of Syntax to learn. Once you get the parentheses, it never gets in your way. Its simplicity aids in expressing complex ideas succinctly. Modern day languages like Ruby and C# are still trying to catch up with ideas from Lisp and Scheme.

Scheme is a functional language, which means functions in Scheme are like pure mathematical functions, which always return a predictable output for a given input, unlike imperative languages which are state-dependant, and functions are first-class objects like primitives.

Programmers love and hate Lisp/Scheme for the same reasons (parentheses), which i put in parentheses to emphasize the fact that i like the language for the same reason. Ruby saved us from the stupid semicolons, Scheme gives you more concise and less ambiguous code, provided editors match and highlight parentheses automatically. The only syntactic rule is every opening parenthesis must have a matching closing parenthesis.

Everything is a list is what my notion of Lisp was before i read this book, but i finally understood that List is a concise way of expressing both program and data in a similar way, and a List is made of atoms or List (which is made of atoms or List(which is made of atoms or List (which is made of atoms or List (...OK,so you get it,a List is made of S-expressions)))).

The same love/hate relationship with programmers goes for Little Schemer as well. GOTO and Recursion are the most dreaded concepts any programming language book will warn you not to use. But if you think of machine/assembly language, which is what your code finally ends up as, its difficult to implement control structures without jumps which are essentially GOTOs. I'm not arguing in favor of GOTOs, but unfortunately recursion gets much the same attention as GOTOs.

Recursion is a beautiful way of solving a problem in terms of itself. Haters of Little Schemer feel that its a book about Recursion repeated endlessly for different problems. That's what you end up with if you just scratch the surface of the book or skim it, but i find myself solving complex Programming problems very easily by employing recursion after reading Little Schemer.

The first 3 chapters of the book teaches you about atoms, S-expressions and Lists. It teaches you some basic List processing functions like car, cdr, cons etc. It makes you implement some List processing functions like lat?, rember, insert, subst etc using car, cdr and cons. It walks you Step by step through the execution of recursive functions and once you get a grasp of it, you can easily follow along and the book lets you explore on your own. Thats where the Socratic method of teaching really shines.

The chapter on Numbers deals with tuples and makes you implement all arithmetic expressions like +, -, =, <, >, *, %, ** using just add1?, sub1? and zero? using recursion. It was a lot like counting fingers in kindergarten, but it helps you solve complex method like length, pick and occur by employing the same methods. Along the way it builds a couple of Laws and Rules for building recursive methods.

The later part of the book deals with abstractions, more recursion, sets, lambda ,unnatural recursion, total functions, partial functions, Y-combinators formed from nested lambdas (i wonder why Paul Graham named his company Y-combinator because i still haven't grasped the concept yet).

I seldom read a programming book without writing code, but this is one book which improves your thinking of recursive programming without actually writing code. I cant wait to go through a second sitting of Little Schemer writing the code and to better undertand the concepts.

Little Schemer has a number of follow-up books in the same style like Seasoned Schemer, Reasoned Schemer etc. And the book ends with suggestions on other interesting books you can read before moving on to those books.