Turning a while loop into a recursive function

This is terribly simple, but it would appear I didn’t really know it for at least 20 years of my life, so it’s perhaps worth writing it down. (I suspect this is a consequence of working in languages which didn’t have tuple types):

Any while loop can be turned into a recursive function by doing little more than moving text around.

We can think of all while loops as doing the following:

state = init_state
constants = init_consts
while condition(state):
    state = f(state, constants)

Here state is shorthand for “everything that the while loop changes” whilst it is running, and f is shorthand for “the changes that the loop code makes”.

Given this generalized while loop we can rewrite this as:

def loop_func(state, constants):
    if condition(state):
         return loop_func(f(state, constants), constants)
    else:
        return state

state = loop_func(init_state, init_constants)

and life is once again incredibly dull.

---

Going the other way, if you have a recursive function (not mutually recursive) like so

def f(state):
   if end_state(state):
       return f_known(state)
   new_state = change_state(state)
   return f(new_state)

then you can turn it into a while loop like this:

while not end_state(state):
      state = change_state(state)
return f_known(state)

Again, this is terribly simple once you start writing it down for yourself (though perhaps not if you are reading someone else write it)

---

Post script
This also happens to let you write a “while function” which is analogous to the reduce function, though this seems to be noticeably lacking from haskell (I might just be mistaken about this). Perhaps, it is considered to produce code that is hard to read. This would look something like:

def while_reduce(condition, state_change, init_state):
         if condition(init_state):
                 return while_condition(condition, state_change, state_change(init_state)
         else:
                return init_state

Ant troubleshooting

If you get an error like this:

    No supported regular expression matcher found: java.lang.ClassNotFoundException: org.apache.tools.ant.util.regexp.Jdk14RegexpRegexp)

when using ant then it may well be because you don’t have the ant-optional package installed (if you are using Ubuntu or similar.) You can install this with apt-get by typing:

apt-get install ant-optional

as root.

Reduce (fold) for the imperatively minded

The reduce or fold function is a concept in functional programming languages which can be used to simulate looping behaviour without the need for a real loop, and in particularly without the need for any explicit variables. I believe it originated in the field of functional programming languages, where getting rid of any form of ‘state’ seems to be an overriding aim.

I suspect that, with suitable training, one may be able to grasp the meaning of a

Services near Tower Hamlets

This is a map of amenities in near Tower Hill. It’s here so that it is easy to find.
Map

Emacs link

http://xahlee.org/emacs/emacs.html
seems to contain quite a lot of information about making emacs keybindings more ergonomic as well as a lot of general emacs tips.

Lots of general emacs tips:

http://steve.yegge.googlepages.com/effective-emacs

Emacs – select entire buffer macro

You can use the mark-whole-buffer. This is bound to C-x h by default.

Currying, state and higher-order functions

Take any higher order-function that returns a single function. It will always take the following form (upto some minor very minor changes):

def f(x):
     s = STATE(x)
     def g(y):
          return CODE(s,y)

g = f(arg)

This can immediately be converted to:

def f(x, y):
     s = STATE(x)
     return CODE(s,y)

g = lambda y: f(x, y)

This means that if we are working in a referentially transparent code with no side-effects, every higher-order function returning a function can be thought of as a function in several variables.

Its return value can be thought of as the function obtained by setting the values of some the variables in a multivariate function to constants. This means that, in a way, higher-order functions are just a mechanism for storing data together with a function. This is very much like what objects do in object-oriented programming, and in fact it is possible to replace any higher-order function with an equivalent class (I’ll talk about this in another post).

The only difference between the two function calls is that in the second STATE(arg) will get evaluated whenever g gets called, whereas in the first STATE(arg) will only ever get called once.

A python caching decorator for referential transparent functions

The following is quite a nice way of automating caching in python functions using decorators. This code will work whenever a function depends on only its paramters (this is called referential transparency.)

def cached(func):
    cache = {}
    def new_func(*args):
        if args in cache:
             return cache[args]
        else:
             temp = cache[args] = func(*args)
             return temp
    return new_func

def non_cachedFunc(blah)
    ....blah

@cached
def cacheFunc(blah):
    ...blah

This makes turning caching on and off very easy and saves quite a lot of typing. The only overhead added to each call to a cached function should be one extra function call and a dictionary membership test.

Fixing catastrophic mistakes with apt-get

Story for the patient

I managed to utterly break a linux installation yesterday, by trying to install a single package with apt-get. Apt helpfully decided to suggest removing a number of important packages, and I absentmindedly agreed.

The lesson learned here would be that you should always press ‘n’ immediately and think whenever apt suggests removing more than a couple of packages, if I didn’t know this. I suppose the real lesson is just to be less dim, but alas this never seems to work. Another lesson is to especially be less dim when you only have a wireless internet connection and you decide to remove the things that make it work.

Anyway, I found a moderately nice way of reverting these damaging changes.

Although apt does not do any logging, it uses dpkg for installation (on debian type systems at least) and dpkg does do logging.

Looking at /var/log/dpkg.log I found that it neatly recorded all of dpkg’s operations so I was able to get a list of all the packages I had absentmindedly removed by using some crpytic shell commands:

cat /var/log/dpkg.log | grep remove | cut -d " " -s -f 4 > ~/removed-packages

I then could reinstall these with:

apt-get install `cat removed-packages`.

Hurrah for copious logging and shell textual data processing… or something like that.

Summary for the impatient:

Apt doesn’t store a log, but dpkg does and apt uses dpkg. The relevant log file is /var/log/dpkg.log. To get a list of the removed packages, and install them again you can run:

cat /var/log/dpkg.log | grep remove | cut -d " " -s -f 4 > ~/removed-packages; apt-get install `cat ~/removed-packages`

as a root user.

Second-order functions versus currying in python

Which code sample seems better:

Sample one:

def g(x):
    def f(y):
        return x + y
    return f

a = g(1)

Sample 2

def f(x,y):
    return x  + y

a = lambda x: f(x,1)

I’d argue that the second was simpler because:

• It is shorter
• Understanding functions of two arguments is easier than understanding functions that return functions
• The level of indirection to the code that actual does things is reduced by one.

Would you ever see the first example written? It probably depends how trendy the people you hang around with are. But if you are the kind of person who might feel inclined write this sort of thing, I think the second way is a better than the first.

---

Afterthougts:
In case you want the title to make sense, I’d refer to the first example as using a second-order function and the first as using a type of currying. (Though the word currying tends to have a more precise meaning)

Also it is debatable whether such changes will make a large difference to the quality of code as compared to other changes.