Counter in Python

Presenting here two implementations of a counter.

What does the counter do?

Given a base n, this counter will allow you to do base n counting. What's base-n counting? There are n digits: 0, 1, 2, ..., n - 1. At each place, the digit changes from i to i + 1 if i < n - 1, and to 0 if i = n - 1. This change happens when the change at that place is triggered. And when does the trigger happen. For the unit's place, the trigger happens whenever the function is called. For all other places, the trigger happens when the previous place's digit rolls over from n - 1 to 0. That's all. That's a bit technical description for the simple act of counting we learn in our KG. But if we want to implement the counter, it needs to be written in this algorithmic language.

A 3-bit binary (base-2) counter goes like:

000, 001, 010, 011, 100, 101, 110, 111, 000, ...

A 2-digit base-4 counter would count as:

00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 00, ...

What do we usually do in day-to-day counting? decimal (base-10) counting.

How do we Use the Counter Program?

Below is a piece of code that could be used to implement a binary counter on a 3-bit number.

base = 2
inc = makeCounter_iter(base)
n = [0, 0, 0]
print n
for i in range(base ** len(n)):
    n = inc(n)
    print n

 The inc(n) gives n + 1 in the base n number system which is pre-decided while instantiating the counter:

base = 2

#!/usr/bin/python
def makeCounter_iter(base):
    def isZero(lst): return lst == [0] * len(lst)

    def inc(num):
        if(len(num) > 1):
            rem = inc(num[:-1])
            if(isZero(rem)):
                if(num[-1] == base - 1):    rem.extend([0]) 
                else:                rem.extend([num[-1] + 1])
            else:    rem.extend([num[-1]])
            return rem
        else:
            new = [0]
            if(not num[0] == base - 1):    new[0] = num[0] + 1
            return new
    return inc

Now follows the recursive version.

#!/usr/bin/python
def makeCounter_rec(base):
    def incDigit(num, pos):
        new = num[:]
        if(num[pos] == base - 1):
            new[pos] = 0
            if(pos < len(num) - 1):    return incDigit(new, pos + 1)
        else:
            new[pos] = new[pos] + 1
        return new

    def inc(num): return incDigit(num, 0)
    return inc

Any day, the recursive implementation trumps over the iterative version. The recursive implementation is smaller and more readable because it's very like the way the process of counting is formally defined in the beginning of the article.

Functional Programming Flavour

One thing to notice is that we use functional language aspect of python. The function makeCounter (makeCounter_iter and makeCounter_rec) is a higher order function that returns another function inc, the increment function. Also, the value of base is fixed in the creation context of inc inside the makeCounter function. The inc function uses the value of base at a place in the code which is typically outside the lexical scope where base is defined. This is known as the closure feature of functional programming. In a typical object-oriented scenario, this effect is achieved using the builder design pattern.

Classes versus Functions

While working with an OO language like C++ or Java, we often stumble into an issue of choosing between a class and a function.

Let me illustrate the case. Say, we are writing a parser. A C-style way to do is to form it in the shape of a function, say parse (FILE * fin) , that returns the IR after parsing. The caller of this function would be responsible to do what he wants with the IR.

There are more one choice to do the same thing when working with an OO language. A class named Parser would possibly have a parse (FILE * fin) method returning the IR. Or it could have a constructor Parser (string FileName), and an argument-less method parse () returning the IR. The merits of choosing one over the other seem to me rather unimposing. The only difference between the two approaches is that the input for parsing is defined while making a call to the method in the former case, while, in the latter, it gets defined at the time of the creation of the parser object. It hardly matters!

For me, in a basic case, having a parser class is little more than syntactic sugar. May be, in a more advanced scenario, it helps having a class for the Parser, so that parser states can be encapsulated in private attributes. Among these, FileName is surely not one. It can always be passed to the parse method while calling.

I arbitrarily prefer having a parameterised method parse (FILE * File) or parse (string FileName), so that I can use the same parser object for parsing many times. Nothing fundamental about this choice.