Stuart Hacking

The more I go through this cycle the more it amazes me that this is the development paradigm that won out. That back in the golden era people sat down and decided that this was the model of the future.

For large applications it’s a major pain – much time spent compiling, starting up the program anew and returning it to the state you need in order to test your latest fix. Even for a fairly trivial change or a bit of experimentation, this is a huge timesink.

And yet there is an alternative approach – incremental compilation, à la Lisp. When the Lisp environment hits a bug it pauses. It shows you the location of the bug, it gives you a full stack trace at the time of breakage. You can inspect just about everything. Here’s the kicker: you can fix the code while the debugger is waiting. Then you can load that fixed code right back into the running program and continue on your merry way.

Let me repeat that last bit: You compile only the code that needed fixed and load it into the running program. The running program then continues using the new code. No stopping, compiling, running, getting back to where you were, debugging.

This is special. It’s not even that new. Lot’s of hip, young, dynamic languages are attempting to copy it. Let’s now, in 2010, make an attempt to catch up to the technology of 50 years ago. We owe the founding hackers that much, right?

Self lisp, Programming, Rant

Just some stuff I thought about today. Here’s a fibonacci function expressed in Lisp:

It can be used to compute the fibonacci sequence:

It’s simplicity is elegant, but, frightfully inefficient. In fact, the recursive definition of fibonacci is often used as an example of an inefficient method. Let’s look at why it’s poor. When fibonacci is called for a value of n there are two possible paths the program can take:

1. If n <= 1 give back the value of n
2. otherwise return the sum of the previous two numbers in the sequence

So, if n is 0 or 1 then the value is simply 0 or 1 respectively. This is the base case of the function. In other words, from this piece of concrete knowledge, we can derive the remaining values. If n is any value higher than 1, then we need to actually compute what it is. Notice that this case requires fibonacci to be called another two times.

This imposes significant overhead on the machine. In addition to this, the results of these two function calls must be added together. That means we need to hold onto some space in memory to store the results. Simplistically, we refer to the number of significant function calls as the time complexity of the program, and the amount of memory required as the space complexity. Fibonacci sure is expensive.

Anyway, this got me to thinking. What is the main problem with fibonacci? It’s the fact that it must repeat a lot of its calculations. If we want to find the value of Fib(5), we must call Fib(4) and Fib(3). But wait: To find the value of Fib(4) we must call Fib(3). Hence, we do the same operation twice. What if we could tell the program to remember a value once it had been found? Wouldn’t this speed things up? Can this be done without sacrificing the simplicity of a recursive method?

Here’s a modified, partial fibonacci function:

This one is a little more involved, but don’t panic: It still does the same thing, in much the same way. It has an extra trick though: Before it attempts to compute the value of n, it check to see if it already has a value. It looks in a structure called a hash table (any type of lookup table should do). Think of this like a telephone directory. If you know someone’s name, you can look it up in a phone directory and it will tell you their number. In our hash table, if you know a value of n, you can look it up and find its fibonacci value. Of course, some fibonacci values won’t be listed just yet. If there is no value in the table, we continue with our normal process: If n <= 2 then return 1. If n is greater than 2 then we find it’s value by adding the previous 2 fibonacci numbers. Now we have one more change to make: Having just found this new value of Fib(n) we store it in the hashtable. This means we won’t have to do the hard work of finding it again later – It’s already there!

Now, this act of remembering our previous work means that we must use a bit more memory, but the gain is a remarkable improvement in speed. Today, memory is pretty cheap, so this is not a bad thing. Look at the method we used. We start with a function that must call itself with a smaller value in order to discover a new value. When we discover a new value, we store it in a table so that we can quickly find it later.

This could most likely be generalised for any function that follows this pattern. There’s another blog post for when I get time to look into that aspect of it. If this post was about the optimisation, the next will be about abstracting that into a common pattern.

I hope this was of some interest. It was just a little thing I thought about this afternoon then decided to try it out. After I tried it I thought it might make a quick, informal blog entry.

Update: It seems that I have inadvertently stumbled across the definition of memoization which was conceived in 1968! It’s fun to try something out and then learn about a formal definition of the same principle. The act of developing an example gives it more meaning. (Further reading: http://en.wikipedia.org/wiki/Memoization).

Programming Computers, Emacs, hack, lisp, memoization, Programming

Recently , I’ve come to rely on Emacs for more or less everything I do on a computer. Of course, in work there are some exceptions: We must use Outlook for emails (the bulk), various windows only business tools (the cruft), etc.

But, as far as possible I will use Emacs because I love the simplicity, speed and extensibility.

In particular, I have discovered org-mode which has now taken over my personal scheduling routine. Org-mode is a personal planner for emacs which allows the user to: Create todo lists, schedule items for certain dates, mark items complete, use checklists, add tables. It’s impressive the amount of features this small, text-based operating system can offer.

So here’s some quickie hacks I’ve started working at for org mode. My wishlist is as follows:

• [X] Store all org-mode schedules together
• [X] Custom org save function (facilitating above)
• [   ] Strip TODO/BUG/FIXME lines from source code and:
  • Store in org file called “<project name>”
  • insert links back to source file
  • add tags based on: language, filename, type

The third item is still in progress but I’ll explain my current org setup now and provide some expressions for the customisation:

;; Org Mode
(global-set-key "\C-cl" 'org-store-link)
(global-set-key "\C-ca" 'org-agenda)
(add-to-list 'auto-mode-alist '("\\.org$" . org-mode))
(setq org-log-done t) ;timestamp on completion

The first two lines create global keyboard shortcuts (key-bindings) which are available from anywhere within Emacs. ‘Ctrl-c l’ will store a link to a url or file, ‘Ctrl-c a’ will open your org-mode agenda (where you can view your calendar, appointments, todo items. This is the thing I have come to rely on )

the add-to-list command tells Emacs to use org-mode by default for any file with a .org extension. the last line sets the org-log-done variable to true: This means that when we mark a todo item as complete it will be timestamped with the completion date. I like this feature.

So that’s just a bit of simple customisation. Now I’ll add a couple of functions that take care of saving my tasks.

(setq org-mode-file-dir "~/.emacs.d/org-files")
(setq org-agenda-files (append (list org-mode-file-dir)
org-agenda-files))

These two functions set variables telling emacs where to find org-mode files containing agenda items. The first is my own private directory added to behave as a default location for saving.

(defun smh-org-mode-save-buffer ()
(interactive)
(if (equal nil (buffer-filename))
(let ((input (read-from-minibuffer "Org Topic: " (buffer-name))))
(write-file (concat org-mode-file-dir input ".org")))
(save-buffer)))

Next I added a custom save function which simplifies the process of saving. If the current buffer is not already linked to a file (buffer-filename is nil) then it will prompt for an Org Topic. I like to think of organising things by topic. The default topic will be the name of the buffer if you supplied one previously. When a topic is given it will store the file as .org in the org-mode-file-dir. One the other hand, if the buffer is already linked to a file it will simple save as normal.

(add-hook 'org-mode-hook
(lambda () (define-key 'org-mode-map "\C-x\C-s"
'smh-org-mode-save-buffer)))

Finally I created a mode-specific key binding: I do this by adding a hook to org-mode… This means whenever org-mode gets called the hooked functions will also be evaluated. I have redefined the ‘save’ keystroke for org-mode to call my custom save function.

This is what I have so far and I find it quite helpful for organising Tasks and Todos manually.  My next step is to analyse source code and look for TODO, BUG or FIXME lines and create org-mode files automatically.

Programming Emacs, GNU, hack, integration, lisp, Org-mode, Programming, Software

I often feel a little sad that – being a child of the 80s – I will never have the chance to operate a Lisp Machine.  They were popular around the time that AI was the big buzzword in Computer Science, then they died out when that bubble burst.  Today the buzzwords are ‘Cloud Computing‘, ‘Virtualisation‘, ‘Agile Development‘ and all kinds of terms related to abstraction of services, infrastructure and development.  (The very things that Lisp offered.

As an homage to these archaic list processing behemoths, I have followed the instructions on clisp.cons.org for setting up Common Lisp as a login shell.  So far it’s looking surprisingly good.  It has the features of bash – for the most part – infused with the ability to directly evaluate lisp expressions and save the definitions out as you work.

The instructions on clisp.cons.org call for a lot of package compilation and dependency walking but if you are running a fairly recent debian or ubuntu system then you should be able to get up and running by installing the following packages through apt-get:  clisp clisp-dev cl-ffi libreadline5.

So – that’s the shell now running through Lisp.  Next step is to have a separate processor performing symbol tagging and type checking, hardware implementations of primitive lisp procedures, … etc!

Powered by Qumana

Self, Software fun, life, lisp, shell, Software, unix