Andrew Whaley's blog

Upgrading from Mac OS X Snow Leopard with PGP to OS X Lion

2011-07-31T12:20:00.000-07:00

I have just been through a world of pain upgrading from Snow Leopard with PGP Whole Disk Encryption to Mac OS X Lion with FileVault whole disk encryption.

Anyone who uses a Mac within a financial institution and many others will be required to use some form of whole disk encryption. Until Lion was released, the only option was PGP WDE version 10 and above. Unfortunately PGP never seems to be compatible with the latest OS updates like 10.6.8 so you are prevented from updating hence my desire to get off PGP and use FileVault2 built into Lion.

PGP advise against upgrading to Lion because, low and behold, it's incompatible but it can be done by following these steps :-

1. Decrypt your hard drive with PGP (takes several hours),

2. Uninstall PGP,

3. Remove your EFI password if you have one set,

4. Backup your data (although not strictly needed, it would be imprudent not to),

5. Use Boot Camp assistant to create the minimum 20GB Windows partition - see why below,

6. Without installing Windows, use boot camp assistant to remove the Windows partition you just created !

7. Purchase and download the Lion installer but don't run it !

8. In the installer.app file, show contents and then use Disk Utility to burn the InstallESD.dmg file to a blank DVD - this gives you a bootable Lion install DVD which you may need later.

9. Install Lion by running the installer from your hard disk.

Steps 5 and 6 seem pointless but these are necessary in order to replace the Master Boot Record on your hard disk which PGP has polluted and which prevents Lion from installing it's recovery partition. Without the recovery partition you cannot install FileVault and you also cannot fix the very common Lion login problem where none of your accounts are migrated so you cannot login post install !

After install you should have Lion installed and with luck the recovery partition is installed. There is a good chance that you can't login at this stage so you need to boot from the recovery partition by holding down Cmd-R or Alt during boot up. If this doesn't work and you are presented with the login box again then you have no recovery partition and you'll need to boot from the DVD by holding down the Alt key with the DVD in the drive.

Once in recovery, start a terminal and type 'resetpassword' and then select the root user and set a password. Reboot and login as root and then recreate your accounts using the same home directories and you won't have lost any data.

If you don't have a recovery partition, try steps 5 and 6 again and then reinstall from the DVD - your data should still be there afterwards.

Once installed with the recovery partition, setup up FileVault from the Preferences / Security menu and you'll have no future need of PGP or any need to fear software updates.

Symbian is dead, long live Linux

2009-08-21T00:13:00.000-07:00

I've always been a huge fan of mobile computing devices and thought that the Psion palmtop computers of the 1990's and early 2000's represented the best in practical design that could be achieved in this format.

Psion pioneered the Symbian operating system that was used on their Series 5 devices but was also popular on many high end smartphones from Nokia and Sony-Ericsson. One of my favourite devices was the Psion Revo as this was the perfect combination of small size but with a usuable keyboard and screen. Being launched in 1999, it was groundbreaking for the time but with only 8MB of storage, a 30MHz ARM processor and no connectivity, it is of limited use in today's media rich and connected world.

After the Psion my next device was a Sony-Ericsson P910i, this is a smartphone also running Symbian but this time with GPRS connectivity, bluetooth, 96MB internal memory and expandable upto 1GB using memory stick pro duo. This was a great piece of kit that offered media, a web browser (Opera) and the usual PDA type functions with great handwriting recognition. I also used this with a separate bluetooth GPS receiver and TomTom Mobile software as a SatNav for the car. The P910 did pretty much everything the iPhone does but 4 years earlier, it's clunky by comparison and is showing it's age now.

Alas, times move on and the P910i suffers from a dated browser that doesn't support Ajax, Flash and many other modern features and connectivity is limited to GPRS which is slow and expensive. So it was time to upgrade but to what ?

The obvious choice is the iPhone but at around £600 (£100 purchase + £30/month) this is a serious outlay on a toy. Also, the browser doesn't support Flash or Java and the development tools are all closed. Furthermore you can't develop on it unless you have a Mac (another £1000 outlay for a computer worth £400 !) and you can't distribute your software unless Apple approves it. There's the Ipod Touch as a cheaper alternative but this has no GPS and still suffers from the closed development environment. So this option is ruled out for me.

Next consideration are the Google Android phones like the HTC Hero which is a much better proposition. Under the covers they run a cut down Linux OS but with a Google Java based application environment on top. The browser supports Flash and Java. Development tools are freely available and there is no restriction on distributing software which is written in Java. Sounds a good option but, it's still expensive at £30/month (£540 for minimum 18 month contract).

So what did I go for, neither. It turns out that Expansys were flogging off the Nokia N810 cheap to make way for the new model which is due out imminently. The N810 is marketted is an 'Internet Tablet' by Nokia but it is closer in function to the original Psion palmtops than to modern smartphones but was perfect for my needs with :-

Linux OS,
128MB RAM + 2GB internal storage + expandable upto 32GB through MiniSD,
Mozilla Browser with Ajax and Flash 9 support,
Slide-out keyboard or handwriting recognition,
Built in GPS and SatNav software with UK maps,
Wifi

All for £128 (30% cheaper than an Ipod Touch). It has the disadvantage that there is no GPRS or 3G support so the internet can only be used where there is Wifi available but it has what is probably the best browser on any mobile device which can be used to access virtually any site that a desktop browser can. Even the IG Index site which is highly Ajax oriented loads up and works fine albeit more slowly than on a desktop. The screen resolution is a respectable 800 x 480 so this is a genuinely usuable format packed into a small size. The Flash player works fine with YouTube and Magnatune although I've yet to get BBC iPlayer working.

The OS is a fairly standard Linux distribution but with a custom Windowing environment designed for touchscreen and even includes a terminal. There are plenty of applications available through the repository but porting any other open source Unix apps should be fairly trivial so long as the resource requirements aren't too great. There is also a development underway to replace the underlying Linux distro with Ubuntu so you get the benefits of Ubuntu with the touchscreen friendly window manager - perfect.

Physically the device is about the same size as an IPhone but slighter thicker at 14mm and noticeably heavier. It has a sturdy metal case that slides down to reveal the keyboard. It also has an integral kickstand wich mean that the device can stand up which is useful for watching videos, photo slideshows or Skype video calls. It's a well designed, solid, compact design but I still think that a traditional clamshell design like the Psion's would have been better or better still dispense with the physical keyboard and rely on the onscreen keyboard or handwriting recognition. Having said that, my attempts to use the handwriting recognition have so far been disappointing finding it very slow and practically unusable. This is a surprise considering how well it worked on the P910 which had a tenth of the processing power of this device. Perhaps it needs more practice on my part and maybe some tuning so I'll bear with it for the time being.

As an update, I'm loving this device and find that I'm using it more often than my laptop for casual browsing and certainly for media like watching vides on YouTube or listening to music on Magnatune. I've persevered with the handwriting recognition and get a high accuracy rate but it still remains too slow for entering anything more than a couple of words. Sometimes it won't respond at all, other times it lets you get a couple of letters ahead but then just forgets earlier letters so you have to rub out and start again. This is a bitter disappointment to me as the P910 was great, my ancient Compaq Ipaq with PocketPC was acceptable and even the humble Palm Pilot of a decade ago was better than this. So come on Nokia give us an update to this rubbish.

What I really like about this device is that it is a regular Linux machine with everything where you'd expect it. This means that porting software is trivially easy.

Running MetaTrader 4 under Linux

2009-08-14T14:57:00.000-07:00

Many of the Forex brokers e.g. FXCM and Alpari UK are now offering direct trading through MetaTrader which offers great opportunities to program 'Expert Advisors' to automate your trading. This means that you can be day trading full time whilst you're at work and asleep.

Unfortunately MetaTrader is a purely Windows application but the great news is that it installs and runs fine under Wine on Ubuntu 9.04. It will install under vanilla Wine from the Ubuntu repository but unfortunately it won't run because it requires MFC libraries that aren't included in the default Wine installation.

This is easily remedied by copying the following files from a Windows XP box :-

-rwxrwxrwx 1 andrew andrew 924432 2003-07-16 17:28 mfc40.dll
-rwxrwxrwx 1 andrew andrew 927504 2008-04-14 01:11 mfc40u.dll
-rwxrwxrwx 1 andrew andrew 1028096 2008-04-14 01:11 mfc42.dll
-rwxrwxrwx 1 andrew andrew 981760 2007-04-03 04:14 mfc42u.dll
-rwxrwxrwx 1 andrew andrew 1060864 2003-03-18 20:20 mfc71.dll
-rwxrwxrwx 1 andrew andrew 1047552 2003-03-18 20:12 mfc71u.dll
-rwxrwxrwx 1 andrew andrew 22528 2008-04-14 01:11 mfcsubs.dll

to your .wine/dosdevices/c:/windows/system32 directory.

Spread betting with genetic programs

2009-07-15T06:23:00.000-07:00

I met up with an old friend a couple of weeks ago who mentioned he was interested in financial spread betting and the possibilities of making some money as he knew of people that made a full time living from it. I must admit, I'd often thought that it must be possible to use software to make money from the markets but hadn't realized that spread betting offered a low cost (albeit high risk) way in.

It sounds rather obvious but you should be successful if you win more on your winning bets than you lose on your losing bets even though you might lose more often than you win. So the emphasis should be on profit rather than the number of times you win or lose. Reading books like 'The Naked Trader', it seems the biggest danger is your emotions forcing you to throw good money after bad when you are losing and making you cash in your winning bets too soon when they're in profit rather than letting them grow to reach their full potential.

Using software should remove the emotions providing the user follows the orders exactly and is not tempted to intervene. So I set about writing some software, in Scheme obviously, to generate a single market order for a bet on the FTSE100 index the next day based on the previous day's data. Here's an example of the daily movement :-

The FTSE is an ideal target for spread betting because it has a large daily movement range and the spreads offered by most companies are very tight (e.g. IG Index offers only 2 points) and you can have a stop that is only 30 points away which means that can very cheaply place bets.

The order might say Buy at 4280 with a stop of 30 points, no limit and a rate of £1 per point. If the market is lower than 4280 at any point during the day, your bet will be placed. For every point that the market moves up, you will gain a pound. If the market then moves downwards you will lose £1 for every point until it reaches the 30 point stop in which case you've lost your bet and are £30 poorer. If on the other hand the market had climbed 100 points you'd be almost £100 richer (the difference is the spreads taken by the spread betting firm). If the market never came down to 4280, then your bet would not be placed and you wouldn't gain or lose anything.

So the first task was to build a simulator and get hold of some historic 'intraday' data i.e. minute by minute movements in the price going back over three months. The simulator takes a list of orders and runs them in a particular day to calculate the profit or loss for each order. Wrapped around this is a harness that for each day in the set will call out to a strategy function asking for orders based on the previous days statistics. The daily and weekly profitability is then calculated for the strategy so you can decide whether it's a winner or not. You can then use the strategy to generate orders for the next day i.e. tomorrow, hopefully with confidence that it will win more than it will lose.

Using the simulator, you can try out strategies that you think might work - here's one that's not bad :-

;; Stats used by strategy function
(define-type stats
     prev-open
     prev-close
     prev-high
     prev-low
     )

;; A very simple but surprisingly effective strategy
(define (simple-strategy stats)
(let ((gain (- (stats-prev-close stats) (stats-prev-open stats)))
(range (- (stats-prev-high stats) (stats-prev-low stats)))
(mid (/ (+ (stats-prev-high stats) (stats-prev-low stats)) 2)))
(cond
((> gain 10) (list (make-order - (+ mid 5) 30 0 1.0)))
(else (list (make-order + (+ mid 10) 30 0 1.0))))))

The simulator shows that this very simple strategy generates around 500 points profit over the sample three month period. (NB. past performance is no gaurantee of future performance !). Make-order takes the direction (+ for buy order or - for sell), the opening (order limit) value, stop distance, the limit distance and price per point. Note that the only input data the strategy uses is the previous day's opening, closing, high and low price. The strategy works on the basis that if the FTSE gains one day then it'll probably come down the next. Obviously this isn't a universal rule and will very often be wrong but when you're wrong you will lose at most 30 points and when you're right you could gain in excess of 100 points.

Using manual analysis of the charts and computing some optimum values, I created a variation on the one above that managed to average around 1000 points profit for the period but I had no way of knowing if it was optimal or not.

Genetic Programming
Genetic programming is a technique for evolving programs to solve a problem. Here our problem is to come up with a trading strategy by creating program fragments that breed and mutate over time and are evaluated against a 'fitness function' the least fit are discarded and the most fit are encouraged to breed to produce stronger offspring. In our case the fitness function is the simulator - the total profit over the three months data is all that matters. If you make a good profit you can stay and breed, if you don't you're out. Breeding (crossover) takes complete elements at random from both parents. Mutation randomly and subtly modifies one of these elements to produce something different. After many generations you get a very optimal solution to the problem you are trying to solve.

Scheme is the perfect language for genetic programming because :-

You can modify code easily by manipulating lists,
You can evaluate your new code with eval.

So to solve our problem we need a 'trader' :-

(define-type trader
      dir-func
      start-func
      stop-func
      limit-func
      profit)

Which basically is a collection of expressions that are evaluated to produce the corresponding values required for the order. The profit member is used to track which of the traders are successful.

There are a population of traders that exist in a list that are initialised with random expressions :-

(define (pick-from lst)
(list-ref lst (random-integer (length lst))))

(define (get-random-var)
(pick-from '(o c h l g r m)))

(define (get-random-constant x)
(let ((r (- x (random-integer (* x 2)))))
(if (= r 0) (get-random-constant x) r))) ;; Don't want any divide by zero errors

(define (make-random-trader)
(make-trader (pick-from '(+ -)) (get-mutated-term (get-random-var)) (get-mutated-term (get-random-constant 100)) (get-mutated-term (get-random-constant 100)) 0))


(define (initialise-traders num)
(let ((traders '()))
(let nxt ((x 0))
(if (< x num)
  (begin
    (set! traders (cons (make-random-trader) traders))                 
    (nxt (+ x 1))
    )))
traders))

Initialise-traders creates the population of size num using the make-random-trader functions. The expressions are based on random constants and random variables which are o - yesterdays opening value, c - yesterdays closing value, h - yesterdays high value etc. A useful function pick-from basically returns a random element from a specified list. Update: Subsequent studies have shown that it is useful to seed the initial population with some known good specimens e.g. the simple strategy above.

Breeding and Mutation
The following function breeds two traders by selecting features from each and then adding mutation :-

(define (breed t1 t2)
;; Create child from parents
  (let ((t (make-trader
(pick-from (list (trader-dir-func t1) (trader-dir-func t2)))
(pick-from (list (trader-start-func t1) (trader-start-func t2)))
(pick-from (list (trader-stop-func t1) (trader-stop-func t2)))
(pick-from (list (trader-limit-func t1) (trader-limit-func t2)))
0 )))

;; Add mutation
  (let ((r (random-integer 5))) ;; what to modify
    (cond
((= r 1) (trader-dir-func-set! t (mutate (trader-dir-func t))))
((= r 2) (trader-start-func-set! t (mutate (trader-start-func t))))
((= r 3) (trader-stop-func-set! t (mutate (trader-stop-func t))))
((= r 4) (trader-limit-func-set! t (mutate (trader-limit-func t))))))
t))

You can see that one (or none) of the trader functions is selected for mutation which is done with these functions :-

(define (mutate-list l)
(pick-from (list
          (map (lambda (x)
                 (if (> (random-integer 10) 2) (mutate x) x))
               l)
          (simplify-list l))))

(define (get-mutated-term t)
(pick-from (list
          (get-random-constant 100)
          (get-random-var)
          `(+ ,t ,(get-random-constant 100))
          `(- ,t ,(get-random-var))
          `(* ,t ,(get-random-constant 100))
          `(/ ,t ,(get-random-var))
          `(if (> ,t ,(get-random-constant 100)) ,t ,(get-random-var)))))                  

(define (mutate f)
(cond
((list? f) (mutate-list f))
((number? f) (pick-from (list (get-mutated-term f) (+ f (get-random-constant 10)))))
((or (eq? f 'o) (eq? f 'c) (eq? f 'h) (eq? f 'l) (eq? f 'g) (eq? f 'r) (eq? f 'm)) (get-mutated-term f)) ;; Variable
    ((or (eq? f '+) (eq? f '-)) (pick-from (list '- '+ `(if (> ,(get-random-var) ,(get-random-constant 100)) + -))))
((or (eq? f '*) (eq? f '/)) (pick-from '(+ - / *))) ;; Arithmetic operator
    ((or (eq? f '>) (eq? f '<) (eq? f '=)) (pick-from '(> < =))) ;; Logical operator
    (else f))) ;; No mutation - don't know what to do

The key function here is mutate which takes an expression term and mutates it using get-mutated-term.

The rest of the code is concerned with maintaining the population pool, evaluating the profitability of the members and then discarding the least profitable and breeding the most profitable.

The Results
The simple static example above achieved a total profit of 509 points over the 3 months data, the genetically bred trader achieved 1469 ! My efforts to hand optimise the simple trader resulted in a profitability of around 1100 but the genetic model has even exceeded this by 30%.

Update: I expanded the data available to the traders to include a long and short moving average and also the gain on the Dow Jones Industrial Average and re-ran the process. The winning trader had a profitability of around 1700 points but surprisingly hadn't chosen to use the Dow variable.

I've now created a separate blog to document my efforts to take this study forward to fully automated forex trading, please visit http://www.thegenetictrader.com to check on my progress.

Serving Gambit Web Applications behind Apache

2009-05-22T04:56:00.000-07:00

Now that writing web applications in Gambit Scheme is so easy using Black Hole, I thought I'd write an article on how to set everything up from scratch using Apache as a front end web server.

Using Apache as a front end web server isn't strictly necessary since the Black Hole web server fully supports HTTP and is capable of serving static as well as dynamic content but for robustness, SSL support and to offload the serving of static content it makes sense to place Gambit behind Apache.

Gambit uses lightweight internal threads which allows it to efficiently support thousands of concurrent requests but these run in a single OS thread. This means that if you are running on a multicore or multiprocessor system, you will need to run multiple Gambit processes and load balance between them in order to fully utilise the available CPU. The load balancer would need to be 'sticky' unless you are going to serialize continuations outside of Gambit.

Enter Black Hole
Black Hole is primarily a R5RS compatible module system for Gambit which allows you to easily import libraries into your code including macros which has previously been tricky on Gambit. Conversely you can also export your own code and create your own libraries to fully modularise your development. This is basic stuff but the lack of it has really stifled development on Gambit. For the web developer, the most interesting aspects are the bundled libraries for web serving, SXML and the 'Spork' continuations based web framework.

Getting Started
This guide is based very much on Per Eckerdal's Black Hole Tutorial guide but has been extended based on my own experiences using Black Hole.

Installing Black Hole
Assuming that you have Gambit installed, you need to download the latest Black Hole code from the git repository :-

git clone http://mwaza.dyndns.org/apps/files/modules.git

That will clone the current code repository to 'modules' directory in your working directory, you now need to copy or symlink this directory to the Gambit lib directory e.g. C:\Gambit-C\v4.4.3\lib\ on Windows to create ~~/lib/modules.

Although not strictly necessary, now would be a good time to build all the modules :-

cd \Gambit-C\v4.4.3\lib\modules gsc build
Black Hole is now installed and ready to use, simply do a (load "~~/lib/modules/build") in Gambit to initialise. It is recommended that you use gsc rather than gsi because Black Hole uses compilation features that aren't available in gsi.

For convenience, you can create a wrapper command that loads Black Hole at startup, e.g. on Windows :-

bsc.cmd :


gsc -:dar- -e "(load \"~~/lib/modules/build\")" %1 -

Copy this to your Gambit bin directory then you can use 'bsc' in future instead of gsc or gsi.

Setting Up Apache
In this scenario we are using Apache to proxy the requests through to Gambit and to serve any static content, here's a sample Virtual Host setup from httpd.conf :

<VirtualHost *>
    ServerName localhost
    ProxyPass /spork http://localhost:8080
    ProxyPassReverse /spork http://localhost:8080
    DocumentRoot ${path}/www
</VirtualHost>

This configuration will forward any requests with a URI that starts with '/spork' to the Gambit server running on port 8080. Any other requests will be served from the 'www' directory under Apache.

Creating your Spork Application
So you are now ready to go, fire up Eclipse (with SchemeScript) or your alternative favorite development tool. Start your Gambit REPL window (with bsc or load the modules manually).

Enter this into REPL :-

(import (std spork/core))

(define c (spork-serve root: "/spork" ))

(add-spork c ("one")
  `(html
    (head
     (title "Hello, world!"))
    (body
     "This is my first web application using Spork :)")))

And fire up your browser :-

OK it's not a spectacular example but you are setup now ready to do some more serious development effortlessly through REPL - just redefine the function and retest with no need for a restart.

Gambit MySQL client 0.2

2009-04-29T02:35:00.000-07:00

After a few weeks wrestling with the MySQL protocol, I've finally managed to produce a reasonable attempt at a client for Gambit (and probably other Scheme's).

This is a pure Scheme implementation rather than using Gambit's C interface to glue the existing MySQL C API into Gambit. The reason for this is that Gambit's power, and in my view fantastic potential as a web platform, comes from it's lightweight threads which allows Gambit to process thousands of concurrent requests in a single OS thread. This is all acheived by an internal schedular, continuations and very careful use of non-blocking calls on all I/O functions. Using the C API effectively takes the OS thread out of Gambit and into the C code and therefore all of those lovely threads stop executing until your call is completed - seriously bad news for a web application.

This library is now around 80% complete and supports the following features :-

Multiple concurrent connections to MySQL,
Authentication using both the old and new authentication methods,
Switching Schema's,
Dynamic queries, updates, deletes etc.
Prepared statement creation,
Executing prepared statements (queries and updates) with bind variables for most datatypes,
Closing prepared statements,
Closing connections.

Additionally, I've also introduced a SQL Abstraction Layer. This is equivalent to JDBC in Java which defines a few generic SQL types and provides a common API across database vendors. The idea behind this is that if someone else provides another database client, they can use the same abstraction layer and then any programs can switch between databases without having to rewrite their code (hopefully).

There are a few limitations with the driver, i.e. features that aren't implemented yet :-

Not all datatypes are supported yet in prepared statements e.g. floats, doubles, sets, enums and one or two others. Some of these can easily be avoided e.g. by using DECIMAL instead of FLOAT or DOUBLE.
BLOB's and large character fields are not yet supported in either dynamic or prepared statements.
Large result sets requiring supplementary fetches aren't supported as I haven't implemented the additional fetch function.

Hopefully I'll add these things over the coming weeks and months. There are likely to be a few bugs in there, so if you find one or you are desperate for a feature that hasn't been implemented yet then please email me.

The library is in the Gambit Dumping Grounds. Here's an example of how you use it :-

(load "sql")
(load "mysql")

(with-connection (sql-connect "localhost" 3306 "test" "fred" "fred")

;;(mysql-execute "drop table test")
(mysql-execute "create table test (id integer PRIMARY KEY AUTO_INCREMENT, name varchar(50), inserted datetime, amount decimal(10,2) DEFAULT -4.5)")
(pp (sql-execute "select * from test"))
      

;; Prepared Statements
(let ((stmt1 (sql-prepare-statement "insert into test (name, amount, inserted) values (?, ?, sysdate())"))
      (stmt2 (sql-prepare-statement "select id, name, amount, inserted from test where amount > ? order by id")))

  (pp (sql-execute-prepared-statement stmt1 '("Fred" 10.5)))
  (pp (sql-execute-prepared-statement stmt1 '("Joe" 5.5)))
  (sql-close-statement stmt1)


  (pp (sql-execute-prepared-statement stmt2 '(4.5)))
  (sql-close-statement stmt2))

;; Close connection
(sql-close-connection)))

Result sets are returned as a list of lists i.e. a list of column values for each row in a list for the result set. The first row in the list is the column headings. For dynamic statements, the column data is always a string regardless of the SQL type because this is the way that MySQL sends it and I haven't implemented any type conversions yet. Prepared statements return binary types so I've mapped some of these e.g. strings and numbers into their respective Scheme types.

I would strongly recommend using prepared statements rather than dynamic statements for performance reasons and also for their natural resistance to SQL injection attacks in web applications.

Once the library is finished, I'll create a persistence layer that builds on top of the prepared statements to give a framework similar to ActiveRecord in Rails or Hibernate in Java.

MySQL Interface for Gambit

2009-04-21T14:10:00.001-07:00

As you've probably already realised, I'm a huge fan of the Gambit Scheme implementation which is highly performant and compiles into a standalone executable.

Gambit has also been proven to support tens of thousands of concurrent lightweight threads which helps make it an ideal platform for web applications. This coupled with it's rare ability to serialize continuations places it as a front runner for web applications in the 21st century.

Unfortunately there is little infrastructure there at present to support web applications ... or so I thought. It turns out that a tremendous amount of effort has gone into developing a framework called 'Black Hole' by Per Eckerdal and Mikael More. This is a continuations based framework that is built on top of a module system for Gambit. I look forward to seeing this being released in the very near future.

To support this effort, I have developed a pure Scheme MySQL interface for Gambit that is currently in the Gambit Dumping Grounds. The advantage of a pure Scheme implementation rather than a C binding is that it won't block your thousands of lightweight threads whilst your OS thread is stuck in C land.

Currently the implementation supports logging on with new and old authentication methods, switching schema's and DML and DDL using dynamic queries. I'm currently adding support for prepared statements which I would consider essential before building a persistence layer for Black Hole or anything else.

I'd love to do the same for Oracle but unfortunately Oracle don't publish the protocol for SQL*Net so this is not possible. Hopefully Gambit will devise a way to call C with an OS thread so as not to block the lightweight threads and then we can use the OCI interface.

Functional Programming Languages

2009-04-21T14:06:00.000-07:00

We’ve had Structured Programming, we’ve got Object Orientation, could Functional Programming be the next big thing ?

In the 1950’s high level programming languages were limited to Fortran, Algol, Cobol and Lisp. Most of the languages that we use today are derived from Algol, an imperative language. An imperative language is one which is built of statements that change state, named after the imperative mood in natural languages which expresses commands to take action. Our structured programming in C created structures or records containing data that we modified through functions or procedures – an example of an imperative style. With the advent of rich GUI applications in the 1990’s, this approach became untidy because although the structures were similar for different GUI components, the behaviour was different. This led to the much needed development of object orientation with C++. Object orientation is further refinement and development of the imperative style.

One of the most popular languages of recent times, Java, is a near perfect example of an OO language since it was primarily designed for developing portable GUI applications – Applets. It seems strangely ironic, therefore, that very few GUI applications are developed with Java and instead we use it mainly for developing server-side web applications. There are a wealth of web frameworks available in Java but despite this, Java it is still not the most productive language or the least error prone language for this purpose. Web applications are highly concurrent and shared state implicit in an imperative programming style can create many problems.

We have all seen the obvious failures where the wrong data is revealed to the wrong customer because the code has failed to do adequate checking but these are only the cases where the data has made it on to the web pages. For every one of these, there will be countless other bugs where incorrect concurrent data access causes subtle error conditions resulting in random error pages rather than such obvious failings. These failings can sometimes be difficult to recreate and may not be in your own code, these could be bugs in the web framework that you are using, the application server or even the JVM itself - all written in an imperative style. Adding controls such as synchronisation around data to prevent concurrent modification necessarily introduces performance bottlenecks. With multiple CPU’s and increasing numbers of cores per CPU these problems will get greater rather than lesser over the coming years.

“In a concurrent world, imperative is the wrong default !” – Tim Sweeney, Epic Games

So if imperative programming is such a bad fit for our modern concurrent world, what’s the alternative ?

In the 1950’s, Lisp had a functional approach where there was little or no shared state and instead data is passed as arguments, often in a list, in function calls i.e. on a stack rather than a shared heap. This seemingly innocuous difference leads to some major differences in program structure and language features. Some of these features such as closures and continuations have been adopted by some of the newer dynamic but essentially imperative languages like Ruby and have been attributed with increasing productivity and expressiveness. Lisp survives on today in the form of Common Lisp and Scheme and although not widely used outside academia, both are enjoying renewed interest in recent years. Scheme, in particular, has seen an explosion of interest from developers becoming disillusioned with the mainstream commercial imperative languages. Scheme has been used as a teaching language at some of the prestige technical universities for many years but is now finding its way into niche commercial and open source applications, one example being the GIMP image manipulation software.

Another branch of functional languages derived from the 1970’s language ML include OCAML, Erlang and Haskell which again have seen a big growth in interest in recent years. OCAML has gained popularity in military and investment banking applications. Microsoft is about to release its own functional language based on ML called F#.

Lisp suffered a big drop in popularity when the AI research of the 1970’s failed to deliver on earlier promises and at around the same time people were beginning to do great things with C. C, with its simpler requirements for compiler technology, was perceived as fast and efficient and its imperative style suited the single-threaded applications being developed at the time. By comparison, Lisp was perceived as slow and bloated and difficult to work with. Nowadays, in Scheme’s case, the core language has been simplified and streamlined and compiler technology has improved enormously and the best Scheme and OCAML compilers can produce single-threaded code that runs at similar speeds or even slightly faster than C code. Parallel code often runs many times faster because there is little need for synchronisation. Similarly, large tasks can be effortlessly broken into many pieces and executed in parallel on many cores or distributed over many machines – a task that is not easy to achieve with Java or C#.

The benefits of a functional approach are not just increased performance and the removal of concurrency errors though; one functional language feature is particularly suited to web applications: continuations.

The stateless nature of the web introduces its own problems. Business processes are inherently stateful and yet the HTTP protocol is inherently stateless. This means that web frameworks have to implement ‘sessions’ either in memory or a database and track them through cookie values or rewritten URL’s. Business processes then need to be broken down into various discrete steps, each one corresponding with a HTTP request / response pair, and the application then needs to retrieve the state from the previous steps, perform the current step and then persist the data ready for the next step. This extra complexity is necessary because of the discontinuous nature imposed by the protocol.

Ideally, an application would start the process and then ‘call out’ to a user to grab the data needed for the next step and then continue the process within the same procedure so all the local state is still in scope i.e. turning the protocol inside out. Continuations permit this approach.

“It's amazing that this single higher abstraction can make such a tremendous difference in your Web programming, but it really does. If the Java language had native support for continuations, we'd all be coding this way.” – Bruce Tate, IBM

Most languages support continuations of some form, e.g. the humble ‘return’ or ‘break’ statement present in most imperative languages is an example of an ‘escaping continuation’ that can be used to prematurely exit from a block of code. First class continuations present in Scheme allow continuations to be used not only for escapes but also for arbitrary jumps (with state) and they are reusable i.e. they can be invoked many times. Some Scheme implementations even allow continuations to be serialised to disk or a database and then can be later invoked even though the process that they once existed in has long since gone. This is only possible because all the required state existed on the local stack at the time the continuation was captured and is not reliant on other unknown data existing in the process heap space – the essence of a functional style.

These two reasons alone show how any functional language that supports first class continuations would be a far better choice for web applications than our current imperative languages but there is another, rarely mentioned, problem particularly with Java that could be addressed: poor productivity.

It seems strange that we have gone from writing business applications in dedicated and productive 4GL’s like PowerBuilder, Oracle Forms, etc a few years ago to using a general purpose 3GL like Java. It is probably no coincidence that there is now a shortage of developers and development projects often overrun on time and cost. Yet nobody in the lucrative software development industry talks about lost productivity, they merely claim that projects are more complex now.

Scheme and Common Lisp have two other rare features that makes them compelling and could help recover the lost productivity that we have seen in the move to Java and distributed systems : Homoiconicity and Metalinguistic Abstraction.

Homoiconicity is a word coined to describe the fact that the language source code is itself a data structure within the language or in other words, there is uniformity between code and data. Code can become data and data can become code. This means that programs can not only manipulate data (as you’d expect) but they can also manipulate code.

This opens up the opportunity for metalinguistic abstraction or creating abstractions above the base language that then become part of the language i.e. syntactic extension. In simple terms, this means that macros can be used to extend the syntax of the language and create meta-languages. This allows you to readily create a domain specific language (DSL) just for web applications or any other purpose. In fact most Lisp programs end up being a DSL for the problem being solved. This approach magnifies the reuse potential of language features since anywhere where syntax is repeated, an abstraction can be created and reused without the fear of introducing new bugs. Most languages allow you to extend and reuse data types but Lisp based languages are some of the very few that allow you to do the same for syntax.

Metalinguistic abstraction is certainly not unknown in Java applications, most web frameworks rely on XML to create the abstractions that can’t be done in Java. In fact XML has a very similar structure to the nested lists of Lisp S-expressions. The disadvantages of using XML for abstraction is that it is not integrated with the language so you can’t mix XML tags with java code and, of course, your application becomes messy because the logic spans numerous Java classes and XML files. Being able to create those abstractions in the core language would certainly improve readability, reduce defects and improve productivity. Interestingly Ruby on Rails does away with XML files by using Ruby mixins to create abstractions – few would disagree that Rails is more productive than a comparable Java framework. Macros in Scheme or Lisp go further still and produce very concise web specific code particularly when combined with a continuations based web framework. And unlike Ruby this is compiled code running at native code speeds and can safely be highly parallel in nature.

Functional languages are slowly emerging from niche areas but given the utter domination of imperative languages and the enormous established commercial interests around them, business adoption is likely to be slow initially. Given the advantages offered though, early adopters could gain significant commercial advantages over their competitors albeit at the probable cost of some early pain. Functional programming is a paradigm shift and requires developers to almost learn programming again from basic principles.

Hybrid languages like Scala for the JVM have recently emerged that allow functional programming to be mixed with imperative and build upon the existing tools and libraries already available for the Java platform. Whilst Scala pushes JVM development forward, there is still a danger that developers will continue using an imperative style and miss the benefits being offered.

Functional Web Development with SISCWeb

2008-12-11T03:13:00.000-08:00

Functional paradigms offer some innovative solutions to long standing Web development problems :-

1. Continuations fix the inversion of control problem caused by the stateless nature of HTTP. With continuations you can start a function and define some variables you can then 'call out' to the user i.e. send them a page. When the user responds, your function continues where it left off with all the variables still in scope. This means no need for hidden variables, sessions packed with transient data etc. Imagine now that your entire business process is now captured in one easy to read function, not spread over numerous java classes with varied XML structures.

2. Concurrency problems with poorly defined static variables leaking confidential data to the wrong customers are a thing of the past. Everything is passed on the stack as function arguments - there is no mutating state shared between requests. This also makes the application highly scaleable.

3. Security - the continuations approach means that the only way to link one page to another is via a continuation which is unique to each user. This means that data-driven attacks i.e. manipulating keys in forms to get access to data won't work - you can only access data within your continuation.

Try it with SISCWeb - a Scheme continuations based framework that runs on top of J2EE. This allows you to reuse all of your Java libraries and business components but benefit from a functional presentation layer. Also being Scheme based, it offers an embedded 'REPL' so you can build and change your application on the fly without restarting Tomcat or losing existing application state.

It's even better than Ruby on Rails but don't tell anyone - they'll all be using it.

Manchester-on-Sea

2008-11-10T13:07:00.000-08:00

I read recently on the BBC news website that both the Greenland and Antarctic ice sheets are melting three times faster than previously thought. If both of these ice sheets melted completely, sea levels would rise by around 70 metres !

Hopefully we are not in any immediate danger of this happening but it set me wondering what Britain would look like if sea levels rose by 70m.

I dug out some old Trailgauge code that I had and some elevation data that I had and generated a map.

Surprisingly, most of Scotland and Wales escape with minimal land loss. The effect for southern England, however, would be rather more catastrophic. You can see the full map here.

The good news for us northerners is that Manchester is transformed into an elegant seaside resort - perhaps it might be elegant if it wasn't overpopulated from all the refugees from the completely submerged Merseyside and Cheshire.

If you want to see what happens to your town or you want to model different sea levels rises, you can download the utility that I created and try it yourself. It's a Windows command-line utility that generates the map and lists any towns that match your search and gives you their new elevation above sea level, e.g. :-

C:\Data\sealevel>sealevel 70 manchester
Rendering "sealevel.bmp" for sea level = 70m.

Manchester Ship Canal (13500, 8821) submerged
Manchester (13856, 9004) = 5m
Godmanchester (15249, 7703) submerged

Have we lost our way ?

2008-11-08T14:11:00.000-08:00

I've been using Java since 1995 so must be one of the most experienced Java developers around but despite years of my life invested in this technology, I'm increasingly thinking that this has been a mistake.

When I first used Java, it was for writing Applets which is what it was really designed for i.e. object-oriented with a ready set of libraries for GUI widgets (AWT) and everything built-in to download and execute within a web page. Having come from C where it was very hard to build a GUI, Java was a huge step forward. How ironic, therefore, that I've never seen another decent Java GUI apart from Eclipse in all these years and instead we now use Java almost exclusively server-side for writing web applications and business components.

The types of applications that we build are invariably web applications with a database backend i.e. replacements for the old client/server applications that we wrote 10 - 15 years ago using 4GL's like Oracle Forms, dBase, Ingres OpenRoad, Pick or in my case Dataflex.

Java is an object-oriented general purpose 3GL and we are using it to write apps that we would have written with a 4GL ! Is it any wonder that there are so many Java jobs advertised or that organisations are having to recruit armies of programmers in India just to get their work done ? Productivity has nosedived.

I used to write entire modules (say 10 use cases) in Dataflex in a couple days. Now it takes me 2 - 3 weeks in Java even using the best frameworks the world has to offer. And using these 'great' frameworks I end up with dozens of Java files all glued together with untidy XML - what great progress when I would have had one or two Dataflex source files !

OK Java is a general purpose langauge and I can do things in Java that I could never have done in Dataflex but then how often do I need to do this ? In Dataflex, I could have glued some C code in to do something unusual if necessary, painful but still a possibility.

I've recently completed a couple of projects in Ruby on Rails and it has really opened my eyes to this situation that we've gotton ourselves into. Rails offers a big increase in productivity over Java but partly because it's a script langauge so it saves on the edit/compile/deploy debug cycle. One nice thing is that there is no nasty XML, all the code is in your Ruby source files. This means that it can be syntax checked by your editor and everything reads together. I don't particularly like Ruby as I find the syntax untidy and not intuitive. Java has a simpler and more regular syntax so is easier to learn, but there is no denying that Ruby on Rails is more productive partly because Rails uses mixins and symbols to create a semi-Domain Specific Langauge for web apps.

So why do all these Java frameworks rely on XML ? Simple - XML is being used to supplement the language because it's not extendable. People are trying to create a Domain Specific Language DSL, a higher level language, dare I say it - a 4GL but the language won't let them. Instead they are forced to use a data structure (XML) to do this. This is bad because the data structure is not a language and can't contain any logic. So we end up with more and more convoluted and unfathomable XML and masses of disconnected Java classes e.g. Spring - nice try but wrong approach. We have lost our way.

So, how do we get out of this mess and recover our productivity ?

Having recently discovered Functional Programming through Scheme (a Lisp dialect), I can easily see how Scheme would readily support the creation of a high level DSL whilst offering the full power of the underlying language. There aren't many people using Scheme at the moment so not many frameworks out there but there is a growing following and it feels right.

Maybe Scala is the answer ? Scala is a replacement Object Oriented language for the JVM that also supports functional programming.

Luhn's algorithm in Scheme

2008-11-06T04:34:00.002-08:00

I came across Luhn's algorithm yesterday whilst trying to resolve a work related issue and was surprised to find an implementation in Scheme for it on Andrew Dashin's blog.

Looking at Andrew's implementation, it struck me as being a not very scheme-like implementation because it used an iterator (do) and mutating variables (set!). This gave me an opportunity to test my new found Scheme skills :-

(define (luhn-check account-number)
  (letrec ( 
      (digit (lambda (str pos) (string->number (string (string-ref str pos)))))    
      (add-digits (lambda (str)
        (+ (digit str 0) (if (> (string-length str) 1)(digit str 1) 0))           
       ))    
      (luhn-pair (lambda (x) 
        (+ (digit account-number x) 
         (if (> x 0) (add-digits (number->string (* (digit account-number (- x 1)) 2))) 0)
         (if (> x 1) (luhn-pair (- x 2)) 0))
      )))    
      (luhn-pair (- (string-length account-number) 1))
    )
  )

It takes a string and returns a number which should be a multiple of 10 for a valid mod 10 check or a multiple of 11 for a valid mod 11 check.