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.
Friday, 14 August 2009
Wednesday, 15 July 2009
Spread betting with genetic programs
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 :-
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 :-
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 :-
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 :-
You can see that one (or none) of the trader functions is selected for mutation which is done with these functions :-
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.
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.
(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))
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.
Friday, 22 May 2009
Serving Gambit Web Applications behind Apache
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.
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 :-
And fire up your browser :-
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.
Wednesday, 29 April 2009
Gambit MySQL client 0.2
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.
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.
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.
Tuesday, 21 April 2009
MySQL Interface for Gambit
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.
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
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.
Thursday, 11 December 2008
Functional Web Development with SISCWeb
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.
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.
Subscribe to:
Posts (Atom)