Concurrent Editing Without Locking

If you write an application that allows a user to edit data, you should consider what happens when multiple users attempt to edit the same data at the same time. If you don't, you are likely to end up with some unhappy users when they unexpectedly lose some of their data.

Contents

• Scenario
• The Other Ways
  • Last In Wins
  • Pessimistic Locking
  • Optimistic Locking
• A Better Way
• App Server Updating
• Defining Conflicts
• Resolving Conflicts
• Subtleties
• Summary

Scenario

The approach described here can be applied to other situations, but here we focus on one particular kind of common application: a form-based web app that allows the user to edit a record in a database. In this kind of application, the user typically opens a record for editing, which downloads the data from an app server to his web browser (the client application), which displays it in an editable form. The user edits the data in the form as desired, then presses the Submit button. The web browser sends the form data back to the app server, which saves it to the database.

Now consider this problematic sequence of events, where two users concurrently try to edit the same record:

1. User A opens record X for editing.
2. User B opens record X for editing.
   At this point both users see the same data on their screens.
3. User A submits his changes for record X.
4. User B submits his changes for record X.
   How do these two submit operations interact?

The Other Ways

There are a number of approaches typically taken to handle concurrent editing.

• Last in wins: Each user is allowed to open the record for editing and sees the same data. When User A submits his changes, they are saved to the database. When User B submits his changes, they are saved to the database. Whatever data User B submitted will overwrite the values User A submitted for those fields, so User A's changes will be lost.
• Pessimistic locking: When User A opens a record for editing, the server locks the record. When User B asks to open the same record for editing, the sever denies the request. When User A submits his changes, the server unlocks the record. User B can not edit that record until User A is done.
• Optimistic locking (first in wins): Each user is allowed to open the record for editing and sees the same data. When User A submits his changes, they are saved to the database. When User B submits his changes, the request is denied because the record changed after User B first opened that record.

Last In Wins

If you don't think about concurrent access, you will most likely end up with a last-in-wins system, although without an explicit review of the code for potential concurrent access problems and depending on the back end, you may also be vulnerable to data corruption as well as data loss.

The big disadvantage of this approach is pretty obvious: User A's changes are lost (referred to as a lost update), and nobody knows until later, when something else goes wrong. User A submitted his data, everything looked good, he might even have gone on to another step that used his changes, and he would have seen them in the database as long as he completed those tasks before User B pushed the Submit button.

Pessimistic Locking

A naive implementation of pessimistic locking is probably the simplest method of doing concurrent access control. You simply don't let two people open the same record for editing at the same time. When the first person opens the record for editing, you lock it. When the second person attempts to edit the same record, he gets an error message and is not allowed to edit. This is a typical solution, but it has some problems, especially for web apps. The problem arises when one person opens a record for editing, then takes a long time editing that record. During that long period, nobody else can update anything in that record. The epitome of this problem is when the user who is editing a record takes a break and walks away from his computer, gets sidetracked, and ends up going home (or out to dinner and a movie) without ever getting out of the editing screen for the locked record.

As an application designer, you have to decide how to handle this situation. Leaving the record locked as long as the user has it open is not a viable option. If the user not only went home but also went on vacation (or got sick), you could be waiting a very long time to unlock that record. So you have to break that lock at some point.

How do you decide how long to wait before breaking the lock? You could hold the lock until someone else wants to edit the record, then let the second person break the lock if it is older than some amount of time, but you still have to decide what that time limit should be. The longer you let the first person hold the lock, the more disruptive it is to other users who want to edit the same record, but if you break the lock too soon, what happens to User A when he finally does submit his changes? User A thinks he has a lock on the record, so should be able to submit, but if the lock has been broken you can't just let him submit his changes, or you are back to last-in-wins.

You have to decide what to do with User A after breaking the lock. The simplest thing to do is to reject the submit request from User A, but this is not a very pleasing solution to User A, especially if the reason it took so long to make the changes was because they were difficult to do.

There are things you can do to improve the situation when using pessimistic locking. You could add some code to try to detect when the user navigates away from the page, such as hooks on other pages of your web site that clear locks. You could have a client-side timer that warns the user shortly before his lock is about to expire and gives him the opportunity to reset the timeout, which would include sending a message back to the server with that request. You could notify the user when the lock has been broken, so that he can get annoyed right then rather than editing for another hour and getting even more annoyed when his submit is rejected. But every such change moves you further away from the simplicity that was one of the reasons for choosing pessimistic locking in the first place.

The bottom line is that pessimistic locking ends up being a lot more complicated than it might originally seem once you add everything you need to deal with the lock timeout problem.

Optimistic Locking

"Optmistic Locking" is a bit of a misnomer, since it doesn't necessarily lock. It is more accurately called optimistic concurrency, but calling it optimistic locking helps to draw the functional parallel to pessimistic locking.

With optimistic locking, multiple users are allowed to edit a record at the same time. When the first user edits the record, the server says "OK". When the second user edits the record while the first user is still editing, the server says "OK" again. Whichever user submits first wins; when the other user submits, it will be denied by the server because of the first submitter's changes. With some optimistic systems, the server will at least inform the second user that someone else is already editing the record when he first opens it, so the second user has the option of canceling right away and trying again later. On the other hand, similar to how some people react to a yellow light, the second user might interpret that warning as an exhortation to edit quickly so as to get his changes in before the first user.

Optimistic locking is called that because the application is being optimistic that it can let both users have what they want. This is based on the assumption that at least one of the users will exit the editing screen without making any changes. Assuming that happens, there are no problems caused by allowing both users to edit the same record, because one of them does not actually edit it.

Some systems do not give the user the option to view a record except by opening the record for editing. In such a system, there is a good chance that a user who opens a record for editing will not actually edit the record, so optimistic locking may seem like a reasonable approach. On the other hand, it would not be that difficult to add a View screen that allows the user to see what is in the record without editing it. You could put an Edit button right on the View screen to put the user into the Edit screen, or even automatically switch the user into Edit mode if he changes any fields on the form.

If you have a system in which the user can express an intent to edit rather than view a record, then there is a high probability that a user who opens a record for editing will actually submit some changes. In such a system an optimistic locking strategy is likely to be overly optimistic.

As a user you can ask yourself: Would it be more annoying to try to edit a record and be told right away that you can't because it is locked (pessimistic locking), or to spend time putting in your data, only to be told when you submit that you are not allowed to edit that record and have to start again (optimistic locking)?

Some people use the term "optimistic locking" to refer to a mechanism more like what I describe below, including both the database's rejection of the update request and the following resolving step. My usage of the term above is more typical when applied specifically to transactional database updates, in which only the database request is considered. This is also sometimes called Optimistic Offline Locking.

A Better Way

Let's reexamine our goals:

1. User changes are never inadvertently lost.
2. Users are never locked out of editing a record.
3. Users are never required to throw away their edits.

None of the three methods described above satisfy all of these goals. Here's another approach. It's not Pessimistic Locking, and it's more than simple Optimistic Concurrency - let's call it Optimistic Resolving Concurrency. If you google for phrases like "optimistic concurrency" and "optimistic offline locking" and browse around, you will find a lot of descriptions that discuss in some detail the work of detecting update conflicts, after which they pretty much all punt on how those conflicts should be resolved, simply stating that it is the responsibility of your business logic to handle that. I describe in some detail one approach you can take in your business logic to do that.

If you think about the way many modern source code control systems work, such as Subversion or Git, they satisfy all of the goals listed just above. Their approach is straightforward:

1. Always allow a user to edit a file.
2. When a user submits changes, accept them if there are no conflicts with other changes.
3. If there are conflicts, provide the user with tools to resolve the conflicts and allow the user to resubmit the changes after the conflicts have been resolved.

We can apply this approach to our editing web app example. Here are the basic steps:

1. When a client application (web browser) loads a record for the user to edit, the server sends all of the data for the record, but does not lock the record.
2. When the user pushes the submit button to save his changes, the client sends back to the server all of the original data along with the user's desired changes.
3. The server matches the original data sent back by the client against the current contents of the database for the record being edited. If there have been no other changes, then the user's desired changes are saved and the server returns an indication of success to the client.
4. If the record has been changed, as evidenced by a failure to match all of the original data returned by the client, then a resolving step must be undertaken. This is described in more detail below.

Without the resolving step, you could consider the above to be a description of optimistic concurrency. Personally, I consider the resolving step to be an integral part of the concurrency solution.

The code on the server side is relatively straightforward because we are pushing all of the work of resolving the differences to the client. But there is one interesting detail, and that is concerning how the server determines that the original record has not changed since the data for that record was sent to the client.

App Server Updating

We need to check if the data currently in the database for the row submitted by the client still matches what the client was originally given, and only perform the update with the user's desired changes if there were no other intervening conflicting changes. The obvious way to do this is to use a transaction. Within the transaction, we SELECT all of the fields from the row in question using a FOR UPDATE modifier so that the row is locked for the duration of the transaction. We then compare that data to the original data returned to us by the client requesting an update. If there were no changes we execute a database UPDATE on the row and commit the transaction, otherwise we simply abort the transaction (or commit it, since we only did a read).

In most situations the above approach would be a perfectly satisfactory solution. Our app server, which is presumably a client to the database server, will be locking one row, but the operation should be very fast and there is nothing else it needs to wait on in order to complete the transaction (in particular, we are not waiting for any user actions at this point). But there is a small chance that our app server will, for whatever reason, hang during the transaction, which could leave the row locked for longer than expected. And besides, the title of this article does say "without locking".

There is a simple trick you can use in this situation so that you don't have to separately read the current data from the database in the app server in order to do the comparison against the client's original data. Instead of having the app server do that comparison, we make the database server do it. We do this by having our app server execute a single UPDATE statement for the row to be updated, and we include a WHERE clause that not only includes our row identifier, but also matches each column against the client's original values. If none of the fields in that row have been changed since the client received the original field data, then the WHERE clause in the UPDATE statement will be true and the update will be executed on our row (and only our row, since we include our row identifier in the WHERE clause). If any of the fields have changed, then the WHERE clause will be false for our row (as well as for all others), so no rows will be updated. We can read back the row count of updated rows for the operation and check to see if it is 0 or 1, which tells us whether our row was updated. If 1, then we return a success indicator to our client; if 0, the update failed, in which case we need to do a SELECT on the record to read the current contents of all the fields and return that to the client for use in the resolving process.

With the WHERE clause in our UPDATE statement, we no longer need to lock the record in our app server. How the database server handles the write is its business. Any locking done within the database server would still be better than locking in our app server, and in any case is outside our scope. I think it is fair to say this is an approach without locking.

Rather than using all of the data fields in the WHERE clause of the UPDATE, you could maintain a single extra field which is a version number or an update timestamp. As long as that field is changed to a new value (never used before) every time any field in that row is changed, it works just fine as a check to prevent an UPDATE when someone else has modified the row. But we want to have all of the old field data around anyway so we can use it in our resolve step described below, so we might as well just use that data in our WHERE clause rather than adding a surrogate change field.

Defining Conflicts

If any of the fields of the target row have been changed since the submitting client received his original data, then there is the potential of a conflict between the data written by the previous updater and the data to be written for the submitting client. For each field of the record, we have three values:

1. The original value of the field as of when the client opened the record for editing.
2. The current value of the field in the database.
3. The desired new value of the field as submitted by the client.

If the client does not pass in a desired new value for a field, then we assume the desired value is the same as the original value.

Here are the possible combinations of values for each field:

Original	Current	Desired	Scenario
X	X	X	1. No change
X	X	Y	2. We want a change, noone else changed
X	Y	Y	3. Someone else changed, we want the same change
X	Y	X	4. Someone else changed, we did not
X	Y	Z	5. Someone else changed, we want a different change

If, for every field, we find ourselves in scenario 1 or 2, then we know no one else has made any changes, so we can save the desired new values without worrying about losing any data. If any field is in scenario 5, we know we have a conflict.

If scenario 3 arises, you might think it is no problem, since both users want the same change. On the other hand, you might want the second user to know that someone else modified the record, even if that modification was to put in the same data. If you choose to accept this scenario as a non-conflict, you can easily implement this in your WHERE-qualified UPDATE statement by modifying the WHERE clause so that each field can match either the original or the desired values.

Scenario 4 is a little bit trickier. It may be the case that two different people have edited the same record, each one changing a different field. If the fields are truly independent, then there should be no conflict. But if the fields are related, you may have a problem. For example, the two fields in question might be two different telephone numbers. Perhaps the data was originally entered incorrectly and the same phone number was put into both fields. Person A edits the record to correct it and updates the phone number in the first field, while person B concurrently edits the record and updates the phone number in the second field. If both changes go in, then both copies of the original phone number are lost. Thus the conservative approach is to treat this scenario as a conflict, the same as scenario 5. However, if you choose to treat this scenario as a non-conflict, you can easily do this by modifying the WHERE clause of the update to include only the fields in which the client submitted a new desired value.

Resolving Conflicts

When the app server determines that there is a conflict, it must tell the client which fields were in conflict and what their current values are. The client can then display that information to the user in a Resolve form that allows the user to determine how to resolve the conflict.

At a high level, the user has three options:

1. Cancel his change request, discarding all his changes.
2. Resolve the conflicts and resubmit the request.
3. Postpone resolving the conflicts but continue editing.

Recall that the client has two pieces of information that it maintains and sends back to the server for each field on a submit request: the original value and the desired value. If the user wants to resolve a field conflict immediately, he needs to select which value should become the new desired value. This is typically either the current value or the previous desired value. The client's original value that it is storing for the field should be updated to be the current value as returned by the app server, so that on the next submit it will match the current value in the database.

If, however, the user would like to postpone resolving the conflict for a field, that can be done by keeping the old original value for the field so that the next time he submits, that field will once again not match the current value in the database, so he will be reminded about that conflict and can take care of it then.

So for each field, the user should be able to specify whether to keep the old original value or update it to the current value, and whether to use the current value as the desired value or keep the previous desired value.

One possible way to display all of this information is to show a table with one row for each data field and five columns: the first three columns are the original, current and desired values at the time of the submit. These are all buttons. The fourth column is a column of check boxes labeled "Resolve Later". By default these boxes are unchecked. For any field with a box which is checked, the client keeps the old original value for that field. For the fields for which the user leaves the box in its default unchecked state, the client updates its original value to the current value. The fifth column is the new desired value. The user can click on one of the buttons in the first three columns to pick which value to use as the new desired value in the fifth column. The value in the fifth column could also be directly editable. The form would have three submit buttons: Cancel, Submit, and Continue Editing (which is the "resolve later" option).

Once the user has filled out all of the fields in the Resolve form, the client now has updated values for both the original and the desired values for each field, ready for either continued editing or submitting to the app server. Submitting the form goes through the same process as before: if there are any conflicts remaining, the user will be put back into the Resolve form to take care of them. If the user has resolved all conflicts, but someone else happens to have made more changes in the mean time, the submit will fail again and the user will have to resolve the conflicts. If the user chooses to continue editing, we just put him back into the regular editing form. In either case, once we leave the Resolve form we are back in the regular code flow, we don't have to remember that we were in the Resolve form.

Theoretically it is possible for the user never to be able to save because there is always someone else making new edits to the record. I suspect this is not a problem for most real-world situations. If it is, then you might have to resort to pessimistic locking. Better still, redesign your system so that you don't have so much contention for that one record.

Subtleties

When defining what constitutes a conflict, the simplest solution is to treat every field as an independent value, so that there is a conflict whenever the same field is changed by two concurrent clients, and there is no conflict if no common fields have been changed. However, as suggested above, a more sophisticated definition may be more appropriate.

In most databases there are implicit relationships between fields such that you might want to consider changes to any of those fields to be in conflict with changes to any other of those fields. Sets of phone numbers, email addresses or similar lists are a good example of this. Note that these data may not all be stored in one table or shown on one screen, even when submitted by the client in one update request. For example, if you are editing an order with a list of order items, chances are good that each order item is stored in a separate record; but all of the order items are related, and you probably want to treat a change to any order item as potentially conflicting with a change to any other order item, just as with the phone number example above.

Similarly, if your application reads data from one record and is using that data to modify another record or create a new record, you might want to ensure that the first record has not changed before writing the other record, even if you are not changing the first record. In this situation you might not be able to use the UPDATE ... WHERE trick, in which case you can fall back on using a transaction in which you read and validate the old data before updating or inserting the new data.

In the other direction, there may be cases where you want to allow certain changes to one field by two clients to be treated as no conflict. For example, you may be storing a text field, and you may decide that each line in the text field should be treated as an independent entity for the purpose of conflicts. If User A changes line 3 of field X and User B changes line 5 of field X, by this definition those changes do not conflict, so should be allowed. Of course this requires some extra coding: you need to check for this situation in that field, merge the changes if they don't conflict, and provide tools for the user to merge changes that do conflict.

If you are storing and updating blobs in a database that does not allow blobs to be used in comparisons in WHERE clauses, you will not be able to use the UPDATE ... WHERE trick. I mentioned earlier how you can use a version or update timestamp field in the record as a surrogate to know when any data has changed; you can use that technique here, or you can be a bit more precise and add a version or timestamp field associated with the blob field, updating that version or timestamp field only when the corresponding blob field is modified. You can then use that surrogate field in your WHERE clause. Alternatively, you can fall back on the approach of using a transaction within which you read the current database data and compare to the original data in the application.

Summary

On the app server side:

1. When a client edits a record, send the data and do not lock the record.
2. When a client requests an update, use an UPDATE with a WHERE clause to make it an atomic update that succeeds only if there were no changes. If the update fails, load the current data from the record and send that back to the client.

On the client side:

1. Maintain the original value for each field as well as the desired value for changes. Send both to the app server on a submit of an update.
2. When the app server rejects an update, provide a Resolve form (with Cancel, Submit and Continue Editing buttons) allowing the user to choose, for each field in conflict, whether to accept the previous change or update with his desired value, and whether to keep the old original value for a later resolve or to update to the current value.

Some systems that use the UPDATE ... WHERE trick I describe above, although these references don't mention what the systems do when a conflict is detected:

• Apple Enterprise Objects Framework Optimistic Locking
• Apache Cayenne
• Microsoft's LINQ to SQL detects conflicts and provides some support for how to write the selected values once that decision has been made, but does not include the mechanism to allow the user to resolve conflicts.

Some systems that implement the basic conflict resolving approach I describe above:

• Bugzilla "mid-air collision detection"
• Wikipedia's Optimistic Concurrency Control and Edit Conflict resolution

The Internet Made Me Stupid

I used to be a pretty smart guy. I took three years of college calculus and two of physics, including relativity and quantum mechanics. I knew how a computer worked inside out. I could hold up my end of the conversation with just about everyone I knew. It was a rare day when there was a discussion that I could not follow. Occasionally I would be reminded that there were still things about which I knew almost nothing, such as when I cracked open "Superstring Theory" (Volume 1, Introduction) by Green, Schwarz and Witten, and got lost on page three. But it was pretty easy to put that book back on my bookshelf and ignore it.

Today, that's not so easy to do. The Internet has made immense amounts of information available at the click of a hyperlink, and most of those links point to things of which I am mostly ignorant.

While trying to understand monads, I went to Wikipedia. It said monads as used in computer science derive from category theory. I followed that link, and within a few hours was amazed at how much there was about category theory and related subjects that I did not know. When I backed up to review my group theory, a subject about which I thought I at least knew a little, there were far more links to things I did not know about than to things I did know about. Even when chasing down topics in computer science, my college major, such as binary trees, there were all sorts of little pieces with which I was not familiar. Each little piece was no problem to read and understand, but it's not like a book where you can read through it and be done. With hyperlinks, they just go on and on and on.... no matter how far you go, there are always more links leading to little corners that you don't know about, from which the links sometimes open out into huge unfamiliar areas. So much to learn!

The Internet has also made it much easier for me to find people smarter than me - or at least people with way more knowledge about certain topics. I recently started paying a lot more attention to functional languages, and found a couple of groups in my area that get together occasionally to discuss topics in functional programming. There are generally five to ten people in these meetings, with one person making an informal presentation and the rest of the people asking intelligent questions. I'm not used to being the stupidest person in the room, but that's how I feel at these meetings. I struggle even to ask cogent questions. Either these are really some of the smartest people in the area, or I am not nearly as smart as I once thought I was.

I have joined some mailing lists for specialized subjects, including the Scala mailing list. These can be even more humbling than going to the local meetings. Likewise when reading blogs and responses. There are some really smart people in the world; mailing lists and blogs make it seem like they are all living on my block, and I'm just the local slow boy trying to tag along with them.

Other people have also wondered if the internet makes people stupid. Atlantic Magazine had an article in their July/August 2008 issue by Nicholas Carr titled "Is Google Making Us Stupid". The article says the Internet provides people with little snippets of information, and that people no longer have the patience to sit down and read a book. The author claims this makes people's knowledge superficial, because they don't delve deeply into a subject as they would with a book. I don't know who he talked to about that, but it wasn't me. I have spent hours digging into technical subjects on the Internet that I never would have bothered to pursue if I had to go out and get a book on the subject. When I say the Internet has made me stupid, I am saying something quite different than Mr. Carr in that Atlantic article.

The Internet has humbled me, but that's pretty easy to live with when I consider how much of an opportunity it has given me to continue my education. Rephrasing the words of many others, Einstein said "As our circle of knowledge expands, so does the circumference of darkness surrounding it." The Internet has helped me see a whole new magnitude of darkness.

Update 2009-05-27: In his article "The importance of stupidity in scientific research", Martin A. Schwartz writes about learning "that the scope of things I didn't know ... was, for all practical purposes, infinite." He learned it through research; I learned it from the Internet.

The Vagaries of Time

Most people don't spend much time thinking about time. It flows, we count it off on our clocks and calendars, and there is usually not enough of it.

As a programmer who has worked on applications that deal specifically with time, such as activity reports, I have developed an acute awareness of how complicated time is. I don't just mean the complications of relativity (although I have spent a lot of time trying to understand that as well), I am referring to the fact that the way we measure and mark the flow of time is more complex than most people normally consider.

Contents

• Units of Time
• Daylight Saving Time
• Time Zones
• Internationalization
• Calendars
• History
• Relativity
• Pondering Time
• Time To Summarize

Units of Time

As children we learn about how we measure time: 60 seconds in a minute, 60 minutes in an hour, 24 hours in a day, 7 days in a week, 365 days in a year. Then they tell us about the exceptions: every four years is a leap year with 366 days. And the months are irregular to start with, with the various months of the year having three different number of days in them.

That's typically where our formal education on the measurement of time stops. But of course that's not the end of the special cases.

Each year has 365 days, except that every four years is a leap year with 366 days, so for example 2008 had 366 days. Except that every 100 years is not a leap year. 1800 was not a leap year, 1900 was not a leap year, and 2000 would not have been a leap year, except that every 400 years is a leap year, so it was. Good thing, too. A lot of programmers in the last few decades of the 1900s didn't even bother to deal with the century as part of the year they stored (leading to the Y2K issue), so it seems unlikely that those who bothered to deal with leap years would have bothered to deal with non-leap centuries. As it was, because of the 400-year exception to the 100-year rule, we didn't have to worry about that. Hopefully by the year 2100, all of this gnarly time measurement stuff will be will debugged and codified into standard libraries that everyone uses, so it won't be a problem.

You would think by now everyone would be able to deal with leap years, yet leap-year bugs still happen. On December 31, 2008, Microsoft Zune 30GB MP3 players froze up due to a leap-year bug. Microsoft's official solution: wait until about noon GMT on January 1, let the battery drain, then recharge and turn it back on. You have four years to upgrade.

We all know not all months have the same number of days, and not all years have the same number of days. Are there other units of time that we think of as always being the same length that don't really all have the same length? Of course.

Daylight Saving Time was instituted in the early 20th century. "Fall back, Spring forward." We set our clocks forward by one hour in the spring, and we set them back one hour in the fall. Since the time officially changes in the middle of the night, typically at 2AM when most people are asleep, most of us are not much affected by it, other than losing an hour of sleep in the spring and getting an extra hour of sleep in the fall. And, with every device in our house now sporting a clock, spending that extra hour walking around resetting the time on all those devices. But obviously, this means that there is one day every year that has 23 hours and another day that has 25 hours.

So the years are not all the same length, the months are not all the same length, and the days are not all the same length. But we're good on the other units, right? Nope. It turns out that minutes are not all the same length either.

Starting in 1972, the International Time Bureau in Paris has been responsible (until 1987, when the job was taken over by the International Bureau of Weights and Measures) for determining and announcing when we add leap seconds to the year. This can happen at two possible times in the year: once in the middle of the year at the end of June 30, and once at the end of the year on New Year's Eve, December 31. 2008 included a leap second on New Year's Eve. If you very carefully synchronized your watch to atomic time shortly before midnight, counted down to the New Year, and celebrated one second after 23:59:59, you were one second early. The last minute of 2008 contained 61 seconds, so the last second was 23:59:60. Did your watch display that time? Mine didn't.

You might not think that a leap second would cause problems. Most of us can ignore it - our timekeeping pieces are not that accurate anyway. But some devices make a point of accounting for that leap second. For example, Unix time is defined as the number of seconds since the start of January 1, 1970, UTC - except that leap seconds did not exist in 1970, so Unix time is not defined to include them. In order to maintain the correct time on the system clock for systems that care about this level of accuracy, it needs to know when those leap seconds are so that it can take one second off the system clock when it happens. Because leap seconds are so rare (even with two leap seconds in a year, that's only one second out of over 15 million), if a device has a problem with leap second calculations it can take a while to track down. The Linux kernel has code to deal with leap seconds, and this code gets executed exactly twice a year, in June and December, to handle the possibility of a leap second. A race condition in that code path would only show up during those two seconds out of the year, making the problem hard to catch and reproduce, but still potentially a serious problem for those few people who happen to experience it on their system.

Leap seconds can also be negative, so the last minute of June 30 or December 31 might contain only 59 seconds, but this has not yet happened since the start of leap seconds in 1972.

Daylight Saving Time

I already mentioned how Daylight Saving Time complicates things by giving us some days with 23 hours and some with 25. It also means (in the US) that there is one day each year for which the time 1:30AM is ambiguous because it happens twice, and one day for which the time 2:30AM does not exist. But of course it's worse than that. As a scheme enacted by politicians, there's not a lot of logic to when we switch to and from DST and how they choose those dates. In 1987 Chile delayed changing DST for one day to accommodate a visit by the Pope. At least it's always at 2AM (here in the USA) and always on a Sunday morning, but over the years the lawmakers have messed with the starting and stopping days so many times that - well, you really don't want to have to deal with that. Fortunately, today's operating systems take care of this one vagary pretty well. By now they have even extracted all those changing dates out into configuration files so that, when Congress decides yet again to change the days on which DST starts and ends, your computer can keep track of the new dates with just a new configuration file rather than requiring a whole new version of the operating system.

Of course, there are plenty of devices that have clocks in them, many which we generally don't think about, so it's pretty easy to overlook updating the DST information for those devices when Congress makes a change. In October of 2008 I was in an elevator that would not take me to my floor because it was programmed to stop at that floor only between 7AM and 6PM, and although I was there at 7:45AM, the new DST law took effect in 2008 and DST ended one week later than it had been ending for many years. The elevator, which had not had its software updated to include the new DST dates, had dutifully moved its clock back by one hour on October 26 although the rest of us would not do so until November 2, and consequently it thought it was 6:45AM and thus not yet time to allow access to my floor.

Even without Congress changing when DST starts and ends, there are other complications. Arizona does not observe DST (except the Navajo Nation, which does). During the winter, they are on Mountain Standard Time, but during the summer they are on Pacific Daylight Time. If you are making a phone call from New York to Arizona, you probably want to remember that they are two hours behind you during the winter, but three hours behind you during the summer, so that you don't call too early on a summer morning. And of course countries don't all follow the same schedule, and some countries, including China, India and Japan, don't observe DST. If you work in California and are setting up a business call with a client in London, it is good to know when the time difference is 8 hours and when it is 7 or 9 hours.

Time Zones

You might think there are 24 time zones in the world. After all, there are 24 hours in the day (except for those 23 and 25 hours days I mentioned above) and each time zone is one hour apart, so that makes 24 time zones. Not quite. Yes, most of the world is divided into 24 time zones, but some people are just not satisfied with that. There are time zones that are 30 minutes different than their neighbors (Adelaide, Kabul, Mumbai, Tehran), and time zones that are 15 minutes different than their neighbors (Chatham Island, Kathmandu). If you write a program that handles time zones but assumes they are always integer multiples of one hour apart, your program won't work correctly for those locations.

Fractional hour time shifts and changing offsets between time zones due to differences in DST are not the only problems caused by time zones. If a customer comes to you and says they want daily activity summaries, that may be pretty straightforward for a small company with one location, but what is a "daily summary" for an international company with locations all over the world?

If you are storing dates and times in a database, you might want to use the TIMESTAMP WITH TIME ZONE data type defined in SQL 92. This is supported in Oracle starting in 9i. Microsoft introduced support for timezones in SQL Server 2008 with the datetimeoffset data type.

Internationalization

So what do you need to do in order to deal with world dates and times? Of course you need to store time zone information along with the date and time, and use that when doing such things as date comparisons. Although what exactly a date comparison is can take some thought. For example, you can fly from Tokyo to Seattle and arrive before you left - if you ignore the time zone.

Then there is the date and time format, which is different in different parts of the world. Different formats include different order of time units, different separator characters, different names, and 12 or 24 hour time. For example, in the US, most people would interpret the date 01/02/03 as January 2, 2003, but most Europeans would interpret it as February 1, 2003, and people in other countries might interpret it as February 3, 2001 or a few other possibilities. If you are writing a program to be used in multiple countries, you should avoid that format. Many modern language environments, such as Java, provide support for locales. If you use this language feature consistently and properly, along with the rest of the tools of internationalization, that will take care of most of the issues due to the different formatting of dates and times in different countries.

For internal use, when representing dates and times as a string, such as in data files for import/export, you should use the standard ISO-8601 standard format, which looks like this: 2009-03-22T15:30:40-08. Remember to include the time zone.

Calendars

Americans and most of the western world use the Gregorian calendar, and while a lot of Americans know that Chinese New Year is not on January 1st, I suspect that that is as much knowledge as most Americans have about calendars. However, besides the Gregorian calendar, which is now the internationally accepted civil calendar, there are a number of other calendars currently in use, including Chinese, Hebrew and Indian. If you happen to be writing an application that has to deal with those calendars, you will likely have the joy of writing conversion methods to and from the Gregorian calendar.

Then there are yet more calendars that are not in common use. Some of these are pretty wild by our reckoning.

History

Different lengths for time units, Daylight Saving Time, time zones, and internationalization - what a hassle. But wait, there's more! If you are writing a program that deals with historical dates, there are a number of other little problems you have to deal with.

If you are dealing with dates going back to, say 1500, you will have to deal with the switch from the Julian calendar to the Gregorian calendar. The only difference between the two is how leap year is calculated: when Julius Caesar created the Julian calendar, he defined a leap year as occurring once every four years. As I discussed above, the current rules for leap years, which are part of the Gregorian calendar, now include exceptions every 100 and 400 years, exceptions which were never part of the Julian calendar. That means the Julian calendar was off by one day every 100 years, and after a millenium and a half it was off by about two weeks. Pope Gregory decreed in 1582 that leap years would be calculated with the new 100 and 400 year exceptions, and also that the date would be corrected to account for all those years that were leap years that should not have been. (The Church really wanted the calendar to be right so that they could know they were celebrating their holy days such as Easter on the right day.) So, according to the Pope's decree, October 4, 1582 (in the Julian calendar) was followed by October 15, 1582 (in the new Gregorian calendar). If you happen to be programming in Java, you are in luck: the GregorianCalendar class properly models this discontinuity, along with handling the Julian model of leap year before that date and the Gregorian model after that date.

But dealing with dates and times is never as easy as it first appears. Not everyone switched from the Julian to the Gregorian calendar at the same time. The English and the Americans, suspicious of the Roman Catholic empire, did not switch from the Julian to the Gregorian calendars until the middle of the 18th century. So when somebody tells you about something that happened on some date in 1700, it would be useful to know where it happened, as that would give you a good idea whether the historian recording that event was using the Julian or the Gregorian calendar. George Washington was born on February 11, because when he was born the American colonies used the Julian calendar; but as marked on the Gregorian calendar, which we now use, the day was February 22, so that's the day we now call Washington's birthday.

If you get all the way back to year zero, you should know that there was no year zero: the year before 1 CE (formerly referred to as AD) was the year 1 BCE (formerly BC). So while there are ten years between January 1 1995 and January 1 2005, there are only nine years between January 1 5 BCE and January 1 5 CE. Unless you are using the Astronomy Calendar, which does have a year zero.

But by the time you get back that far, you have to start dealing with all sorts of interesting other calendars, compared to which the Gregorian calendar, with all of its special cases mentioned above, is a model of pristine simplicity. The Gregorian calendar was a reform of the Julian calendar, which was in turn a reform of the Roman calendar, after the "years of confusion" when the older Roman calendar got messed up because the rules were kind of complicated and nobody was minding the store (due to a couple of wars). And of course the historians of the time were not using the same year numbers as we now use (perhaps you have heard the anecdote about the coin collector who tries to pass off a coin dated "6 BC").

The ancients did not use our calendar, and they did not use our times either. In the Parable of the Workers in the book of Matthew, when a workman shows up at the eleventh hour, he is not getting there just before lunch. At that time they divided the day and the night each into twelve hours, so getting there at the eleventh hour was near the end of the day. More to our point, there were 12 hours in a day (i.e. 12 hours of daylight) in both summer and winter, so an hour of day in summer was significantly longer than an hour in winter.

When you start dealing with historical dates and times you have to think about precision and accuracy. We know the time for some recent events down the second. The further back in time we go, the less accuracy we have in our knowledge of when an event occurred. If we are trying to create a database that contains events of all ages, we should also be able to specify the precision to which we want to store the time of the event so that it matches the accuracy to which we think we know that time. If you are storing dates in a database using a date/time data type, it probably does not include the ability to specify a precision. The ISO-8601 date/time standard allows omitting lesser units, such as specifying only the year and month, and it defines a way to specify a duration, which could be used as a way of specifying a precision estimate for a date. If you are going to store historical date values in a database, you might want to consider using that format, or at least think about the issue.

In general there is a conflict between the modern trend of measuring and recording when things happened to high precision versus the lower precision and uncertain accuracy of knowing when things happened in the past. This makes it difficult to have a unified timeline that can represent both very old and very new events. Given that ancient historians did not use the same calendars as we do, and in general did not measure time as accurately as we do, it can be pretty hard to figure out when something happened.

Relativity

I mentioned Relativity at the beginning of this article. You might think it has no practical effect on our use of time in the real world, but like leap seconds, there are a few applications that have to deal with it.

To refresh your memory, according to Einstein's Theory of Special Relativity, when an object travels close to the speed of light, its clock slows down relative to an observer at rest, an effect known as time dilation. Strictly speaking, a clock on an object moving at any non-zero velocity will be slowed down relative to an object at rest, but at the speeds most of use are used to dealing with, that slowdown is imperceptible. In addition, Einstein's Theory of General Relativity predicts that an object deeper in a gravitational well will experience time dilation relative to one not as deep in the well. As with time dilation due to high speed, time dilation due to being in the Earth's gravity well is a very small effect. But both of these effects have been measured by atomic clocks carried by commercial jets, and sure enough, the clocks ran at a different rate on the jets than they would have run at rest on the ground: they ran faster because they were not as deep in the Earth's gravitational well, an effect which was somewhat countered but not overcome by the amount the clocks ran slower due to velocity time dilation.

After learning that years, days, and minutes are not all the same length of time, you might have taken solace in the thought that the second, defined according to atomic vibrations (as "the duration of 9,192,631,770 cycles of microwave light absorbed or emitted by the hyperfine transition of cesium-133 atoms in their ground state undisturbed by external fields") always has the same length of time; but given relativistic clock changes and the need to keep things synchronized, sometimes even the length of a second needs to be adjusted to make the clock work correctly in today's world of micro-second synchronization.

So what kind of application needs this kind of accuracy? Here's one example: GPS, the Global Positioning System. GPS relies on extremely accurate clocks to ensure that positions can accurately be measured. The satellites that comprise the GPS system are, like the jets carrying the atomic clocks, moving fast enough and orbiting high enough above the surface of the Earth for relativistic effects to become measurable. Without compensating for these effects, the clocks in the satellites would be off by 38 milliseconds each day. While this does not sound like much, that 38 millisecond translates to an error of over 7 miles (about 10KM) in one day. Clearly, making that relativistic correction is essential in order to make the system useful.

Pondering Time

Imagine that you are creating a reporting program for a user. Here are some of the interesting questions you might want to think about.

If you produce a report that shows daily activity, with each day listed on the X axis, do you space all of the days evenly even across Daylight Saving Time changes, or do you make those special days a little bit shorter or longer in the graph? What about when the user zooms in on one month, or one week, or two days? Does your graphing package even support uneven lengths of days? How do you tell it that you want unevenly spaced tick marks and major labels on the X axis?

The same question can be asked regarding months, which you might want to display as the same size when viewing a couple of years worth of data, but perhaps want to display as different sizes when showing two months worth of data.

If a user is running a report that allows specifying a starting time and an ending time, and he wants one that is one hour long from 1:30AM to 1:30AM on the one 25 hour day of the year, how does he specify that?

If a user in a multi-time-zone company wants a report with a summary of sales for one day, what records do you collect? Do you arbitrarily pick a reference time zone and collect all sales transactions that happened from midnight to midnight as measure in that time zone? Do you use the time zone of the user requesting the report? The time zone of the company headquarters? Do you use the time zone of each sales transaction and collect all transactions with a local time between midnight and midnight? What if the transaction are on the internet, how do you decide what the "local" time zone is for each transaction?

Time To Summarize

I have wandered over a lot of territory in this discussion, yet still left out all sorts of details that might be significant if you are writing a program that deals with dates and times, particularly if you are dealing with anything before a couple hundred years ago. If you find yourself in that position, or if you are simply interested in learning about gnarly details (like people starting their year on days other than January 1, or when various countries switched from Julian to Gregorian, or which countries still use other calendars), I recommend you dive in to any of the links above and start exploring.

When I first started having to deal with this stuff, there was much less support for dealing with all of these annoyances. Now, the operating systems handle DST date changes easily, the language runtimes support multiple calendars and internationalization, the databases have a datatype that includes timezones, and you can much more easily come up to speed on all these issues by using resources on the Internet. It's all so easy now! Well, maybe not so easy, but it is easier than it used to be.

You may never need to know most of these details, but at least now you know about them and hopefully will remember to review these details when you start widening the scope of your dates and times.

After all of the above, what can we briefly say about time? You could spend a lifetime learning about details, but there is not much that can easily be generalized. So what we know pretty much boils down to this: it flows, we mark and measure it in our usual human hodge-podge manner, and there is usually not enough of it.

I hope you have enjoyed the time you spent reading this article.

You Should Learn Scala

You should learn Scala. Okay, I can be a bit more precise than that: If you consider yourself a Java programmer, then you should learn Scala.

Perhaps you ask, Why? If I were being selfish I might answer, Because I want more people to use Scala so that it becomes easier for me to use it where I work. Or if I were being arrogant about the language I might say, So that you will be ready for it's inevitable rise as the successor to Java. But instead I will give an answer that I hope will have a stronger and more immediate appeal: Because it will make you a better Java programmer.

Learning Scala will not necessarily make everybody who knows Java a better programmer. If you are a Java expert and you also happen to know Haskell, ML and Erlang inside out, then perhaps Scala does not hold much new for you. But if you do know those languages, you probably consider yourself something a little different than "a Java programmer", which if you notice is the phrase I used above.

Contents

• Why
• What
• How

Why

What's wrong with just knowing Java? Some people claim learning Java stunts your intellectual growth as a developer. Here are just a few negative comments about Java:

• "Java takes the science out of computer science."
• "Computer Science (CS) education is neglecting basic skills. ... Java ... is in part responsible for this decline."
• "Java is not a good teaching language."

If you want to see some more things that people don't like about Java, google for "Java considered harmful".

It is common advice that you should learn multiple programming languages. Some people say you should learn a new language every year. Each language will have at least some little corners that will present you with new concepts. You should make a point to learn other languages that have deep roots in Computer Science to ensure that at least some of those new concepts are substantial.

Why learn Scala rather than Haskell or something else? Scala integrates functional programming with object-oriented programming. When coming from the object-oriented Java world, Scala allows you to gradually learn functional techniques while still being able to use familiar object-oriented techniques. For a Java programmer, learning Scala may be easier than learning other functional languages that are not object-oriented.

Scala also has the advantage of running on the JVM and allows you easily to make direct calls to Java code. There are other languages that run on the JVM and can call Java, but none that do so as easily as Scala and that integrate the functional and object-oriented approaches as well. This means you can immediately start using Scala code along with the rest of your Java code, and you can leverage your knowledge of all those Java libraries.

Dr. Dobbs, in a journal entry about learning Scala if you use Java, says "[Scala is] the Java route to [Functional Programming]". He also points out that there is an Eclipse plugin for Scala, so you can continue to use Eclipse. Some other Java tools also work with Scala. I happen to like the jswat debugger and have used it on my Scala programs.

Some things you will learn from Scala:

• The importance of immutable values.
• The simpler composition of functions/methods that have no side effects.
• The Actor model for concurrent processing.
• How to think using higher order functions.
• A better understanding of variance (covariance and contravariance).

We will examine each of these in more detail to see how Scala encourages these programming habits.

But first, an overview of Scala.

What

Scala is a combined object-oriented and functional language. It was created by Martin Odersky, a computer scientist at EPFL in Lausanne, Switzerland. Odersky codesigned and implemented (with Philip Wadler) the Pizza and GJ (Generic Java) extensions to Java, after which he was hired by Sun to work on the Java compiler, to which he added generics.

Scala was originally intended to run on both the Java Virtual Machine (JVM) and the dotNET Common Language Runtime (CLR). Unfortunately, the dotNET implementation seems to have fallen by the wayside, so Scala has de-facto become a JVM-only language.

As of this writing, Scala has been around for over five years, has been relatively stable for over a year, and is now at version 2.7.3.

With that little bit of background about Scala out of the way, let's get back to those Things You Will Learn.

Immutable Values

Using immutable values makes it easier to write code without side effects, reduces the likelihood of concurrency bugs, and can make code easier to read and understand. Scala separates the concept of a val from a var. A val in Scala is like a final variable in Java: once a value has been set, it can not be changed. In Java, you have to add the final keyword to a variable declaration to make it immutable. In Scala, you have to use either var or val. This forces you to think about that choice, and since it is just as easy to type val as var, there is little reason not to do so if you don't think the value should change. Sure, you can just add final in Java, but the language does not encourage you to think about that detail, and the default is for everything to be mutable.

Referential Transparency (No Side Effects)

To take a paragraph from one of my previous posts:

Referential transparency is a phrase from the functional programming world which means, basically, "no side effects". Side effects include reading any state which is not passed in as an argument or setting any state which is not part of what is passed back as an argument. If a function is referentially transparent, then a call to that function with a specific set of values as arguments will always return exactly the same value.

Functions with side effects are harder to test, harder to reason about, and in general harder to get right. As you compose functions with side effects, the side effects tend to accumulate, making the composed function even more difficult to get right.

In imperative languages such as Java the natural way of writing many functions is to use variables (mutable data) and loops. In functional languages there are other ways things are more typically done, including the use of recursion and higher order functions, that don't require the use of mutable variables.

In object-oriented languages objects may contain state (mutable instance data) as well as data. When a method uses mutable instance data, it now has side effects, with all of the additional considerations that requires.

It is almost inherent in the nature of object oriented languages to encourage the use of instance state data. But because Scala has one foot in the functional language community, if you learn Scala you will also be drawn into that community and will learn some techniques for writing code without side effects and the advantages of doing so.

Actor Concurrency

Writing correct concurrent code is hard. Java made it easier to do by introducing monitors and building thread control and synchronization into the language. (As a commentary on how hard it is to get concurrency right, even in the original Java Language Specification they did not quite get it right, and had to redefine the memory model with JSR-133 for Java 1.5).

With Java's threads and the synchronized keyword it is easier to write code that doesn't corrupt data due to simultaneous access by multiple threads, as long as you are careful to synchronize all access to shared data.

The monitors that are used for synchronization are external to the methods that lock on them, which means any method that uses synchronized is not referentially transparent (it has the side effect of locking the monitor, which is visible outside the function while the function is running), which in turn implies that functions that use synchronized are harder to compose.

In fact, this is precisely the case: the more functions you compose that use synchronized, the more likely you are to run into a deadlock problem, which is an undesired interaction between those side-effects of the functions. The Java thread/monitor model works well enough for a small number of threads dealing with a very small number of shared objects, but it is very difficult to manage a large program with many simultaneous threads accessing multiple shared objects.

Scala supports the Java approach to concurrency using threads and synchronized, but it also provides another model for concurrency that scales up much better: the Actor model. Actors are a message-passing concurrency mechanism borrowed from Erlang, a language designed for high concurrency.

An Actor is an object that is responsible for maintaining data (or access to any other resource) that needs to be shared by multiple threads. The Actor is the only object allowed to access that data (or resource). Other threads communicate with the Actor by sending messages to it; the Actor can respond by sending messages back (if the other thread is an Actor). Typically the messages are immutable. Scala does not enforce this, but using mutable messages makes it more difficult to scale. Each Actor has a message inbox where incoming messages are queued. Scala's Actor library handles all of the message transfers, so the programmer does not have to deal with synchronizing any code.

There are many levels of possible problems that can arise with concurrent programs:

• Data corruption due to concurrent access.
• Deadlock.
• Resource bottleneck or starvation.

Java's support of threads and synchronized makes it easier to write concurrent code that does not suffer from data corruption due to multiple concurrent access, but we still have to worry about deadlock. Scala's Actor library helps get past the next level: the Actor model can support huge numbers of active actors. all with shared access to a very large number of shared resources, without deadlock, allowing the programmer to focus on ensuring that the higher level issues such as resource bottlenecks will not be a problem. According to Haller's paper (page 14), he was able to run 1,200,000 simultaneously active Actors, whereas the equivalent test using threads on the same hardware ran out of memory and was unable to create 5500 threads.

I have heard that there is an Actor library for Java called Kilim, but I have not tried it.

Higher Order Functions

This is really what functional programming is all about. In a functional language, functions are first-class objects that can be assigned to variables and passed to other functions, the same as any other data type. This allows for a style of factoring that sometimes allows code to be written much more concisely, which (assuming you understand the whole concept of passing functions around as objects) often also makes the code easier to understand.

You can do something like passing a function around in Java by defining an interface with a named method, passing an object that implements that interface, and invoking it by using the method name. While this sort of works, it requires an annoying amount of boilerplate and it doesn't necessarily make the resulting code easier to read.

Scala provides a set of classes called Function0, Function1, Function2, etc., and a bunch of special compiler syntax so that you can write relatively concise functional code, which the compiler then translates into the appropriate classes, instances and method calls to make it all work in the Java VM. The code is not quite as concise as in some other functional languages, because of limitations due to how the type system works (object-oriented type hierarchies and global type inference don't mix very well), but it's much more concise than the equivalent Java code.

Variance

Variance has to do with higher-order types, such as List<String> in Java or List[String] in Scala.

Before generics were introduced in Java, there was no type information for higher-order types, except for arrays, so there was no way to do anything about covariance or contravariance. With the addition of generics to Java, covariance and contravariance checks became possible. Unfortunately, because of Java's legacy of having started off without the higher-order type information, the generics definition has a few problems that can make the whole concept a bit harder to understand.

In Scala, variance was designed in from early on so the whole thing is cleaner. It does admittedly have some problems: although cleaner than Java, it's not as clean as the pure functional languages like Haskell; it has it's own share of odd corner cases (although they are much further into the corners than in Java); and, because Scala has to run on the JVM, it has the same limitations as Java relating to the lack of runtime information about higher order types (type erasure).

Java arrays are broken in terms of variance. After learning about variance you will understand why you can't safely cast String[] to Object[] in Java.

How

How can these lessons be applied to Java? Here's a brief list of some things you can do.

• immutable values: use "final" more.
• no side effects: write more pure functions (no mutable variables) write methods not to use global or instance state, use more recursion.
• Actor model: check out Kilim.
• higher order functions: you can use interfaces, although it is not nearly as convenient. Maybe you will be able to adopt a more functional style in Java if one of the closure proposals gets implemented. In which case after learning Scala you'll be ahead of the game in Java because you will already know how to use higher order functions effectively.

If you learn Scala and use it for a while, you will probably become more comfortable with these approaches.

Perhaps, after reading all of the above, you have decided that you should learn Scala. Great! How can you go about that? My basic advice:

• Read about Scala: articles, blogs, books, newsgroups.
• Write some code. As soon as you can, and as much as you can. Applets, programs, libraries, anything. There is no substitute for writing code.
• Run the Scala interpreter and type things in.

You can download the Scala compiler and other stuff from the official Scala web site.

Here are some pointers to some things you can read to get you started:

• For an overview of Scala's main characteristics: A Tour of Scala.
• For a quick-start guide: First Steps to Scala by Bill Venners, Martin Odersky and Lex Spoon.
• For continued reading: the Scala Reference Manuals on the official Scala web site, including A Brief Scala Tutorial and Scala By Example.
• For a series of articles aimed at Java developers: Ted Neward's Busy Java Developer's Guide To Scala, with 11 articles in the series. Or you can try Daniel Spiewak's Scala for Java Refugees blog entries.
• For in-depth technical details: The Scala Language Specification.
• For a condensed summary of Scala's syntax: my Scala Syntax Primer.
• For the authoritative tutorial: buy the 750 page book Programming in Scala by Martin Odersky, Lex Spoon and Bill Venners, available in both paper and as an eBook.
• For some general programming exercises that you can use when looking for something to code in Scala: Project Euler.

Don't spend too much time reading before you begin coding. Pick a project and get started writing Scala!

Updated 2009-01-18: Fixed var/val typo as pointed out by Doug.

Understanding Monads

Monads are not trivial. If they were, there would not be so many tutorials and articles explaining them.

On the other hand, as with many concepts that we may learn with some difficulty and later think simple, they are not that complicated, if you understand a few other things first. As an analogy, it is hard to understand and use multiplication if you have not yet mastered the concept of addition, but most of us now are pretty comfortable with multiplication.

This is not intended to be another monad tutorial. As with learning addition before multiplication, I believe there are some essential concepts that are necessary before one can be comfortable with monads. In this post I list the concepts I found useful on the path to my understanding of monads (such as it currently is). I set out these details to help me solidify that understanding. Other people may be able to understand monads without understanding all of these concepts, or may require learning other concepts in addition to some of these, but perhaps there will be a few people who find these notes useful.

I came across monads when investigating Haskell after programming in C and Java for many years. The path I took reflects the fact that I have been used to thinking in terms of impure imperative languages. Monads are a more natural fit to functional languages, and I believe part of the task in understanding them is to think more in the functional style.

Below is my list of concepts I found helpful. Don't worry about trying to see how they all relate to monads, just read them. Later, when you read one of those monad tutorials, perhaps it will make more sense.

Contents

• The Option Class in Scala
• Parser Combinators
• Uniform Container Methods in Scala
• Functional Languages
• Referential Transparency
• Group Theory
• Monads as Delayed Computation
• Conclusion

The Option Class in Scala

In Java, null is often used as a marker to indicate a missing value for an object. For example, System.getProperty returns null if the property is not defined. The Option class in Scala is a nice way to avoid using nulls this way, which makes for cleaner code. You can read about Scala's Option class in my post about avoiding nulls, and you should use the Option class a bit to get to know it.

Option is a monad, so once you know how to use it, you know how to use at least one monad. See how easy it is to start using monads?

Parser Combinators

Scala provides parser combinators as part of the standard library. This makes it easy to build simple parsers. You can see how this is done by reading my post about parser generators where I build a simple four-function expression parser.

When using parser combinators, parsers are built up by composing (combining) other parsers using various combining operators (combinators). The result of one of these combining operators is another parser. Eventually, you build up a top-level parser that can parse your entire grammar. Then you invoke that parser on your input stream to parse the input.

These parser combinators are monads. See "Monadic Parser Combinators".

Uniform Container Methods in Scala

The Option class, mentioned above, defines methods for map, flatMap and filter. All of the container classes in Scala, including Array, List and the Map trait, define these same three methods. The container classes also implement foreach, forall and exists. Option implements foreach, even though it never has more than one item. This makes more sense if you think of Option like a List that can have only zero or one element in it.

Having this same set of methods available for all of the collection classes makes it easier for the programmer to use any of them, but it also makes it possible to write a package of higher-level control code that can accept any of these classes. With such a higher-level package, you can add your own container class that will work with that package as long as your container class supplies the appropriate set of methods.

The container classes in Scala (including Option) are all monads. Because all monad classes supply a specific set of methods (informally, the monad interface), a monad library of higher-level control classes can be written that use that monad interface. In addition to supplying specific methods, there are a couple of consistency rules that constrain how those monad methods must behave. This is no different than, for example, the contract in Java relating the behavior of the equals and the hashCode methods for a class. As with any other interface definition and contract, if you write your own class and it implements the monad methods and follows the monad contract, then you can use that class with a monad library.

Functional Languages

Functional languages stress some things that are not typically discussed in imperative languages such as Java:

• Referential transparency
• Immutable data
• Recursion rather than loops
• Lazy evaluation

These concepts fit together nicely in a functional language. Using immutable data goes hand-in-hand with referential transparency. Lazy evaluation is an efficient way (and is sometimes necessary to make it even possible) to implement delayed computations.

Referential Transparency

A pure functional language, such as Haskell, has no side effects. This means that calling a function returns a value and does nothing else. In particular, a function can not set state. This is a very different way of thinking from imperative languages such as Java, where there are objects all over the place with state that gets changed by method calls.

Referential transparency is a phrase from the functional programming world which means, basically, "no side effects". Side effects include reading any state which is not passed in as an argument or setting any state which is not part of what is passed back as an argument. If a function is referentially transparent, then a call to that function with a specific set of values as arguments will always return exactly the same value.

When functions are composed into larger functions, it is easier to reason about them when they are referentially transparent and there are no side effects to worry about. Of course, in the real world it can be very useful to be able to store some state data, so how does one implement this functionality in a pure functional language?

The answer is Monads. This is described pretty well in a 1992 paper by Philip Wadler called "Monads for functional programming". Reading this paper helped me understand the motivation for monads. Monads provide a way to collect all those side effects into known locations in the program. When all of the side effects are collected into monads, the rest of the program (all of the non-monad parts) are still referentially transparent, so remain easier to compose. The side effects are still there, but because they are encapsulated by the monads, it is easier to deal with them.

Group Theory

When you read about monads, at some point you will come across a mention of Category Theory as the source of monads. Category Theory is pretty abstract, and you don't need to know it to understand monads. But monads are a mathematical concept, so digging into the math background of the concept could help solidify your understanding.

After reading a bunch of stuff about Category Theory, I went back to Group Theory, which for our purposes you can think of as a special case of Category Theory. While reviewing groups, rings and fields, I stumbled across monoids, a term which I had not recalled from my readings in the field years ago. It's not quite the same thing as a monad, but because Group Theory is focused on transformations, I started thinking of monads as transformations, which I think helped my understanding of them.

If you know your basic math, like addition and multiplication, you know something about Group Theory. Here's a little sampler:

• The integers, when taken with the operation of addition, are a group. This is because addition of integers satisfies the following rules:
  1. There is a unique identity value (zero).
  2. The set (of integers) is closed under the operation (of addition).
  3. There is an inverse (the negative) for every value.
  4. The operation (addition) is associative.
• The integers, when taken with the operations of addition and multiplication, are a ring. This is because they satisfy all of the above group rules (for addition), plus the following rules:
  1. There is a unique identity value (1) for the second operation (multiplication).
  2. The set (of integers) is closed under the second operation (multiplication).
  3. The second operation (multiplication) is associative.
  4. The first operation (addition) distributes over the second operation (multiplication).
• The rational numbers, when taken with the operators of addition and multiplication, are a field. This is because they satisfy all of the above ring rules, plus the following:
  1. There is an inverse (the reciprocal) under the second operation (multiplication) for every value (except zero).

A monoid, in case you are interested, is like a group but without the requirement of having an inverse. Thus, the natural numbers with the addition operation are a monoid.

An item of interest related to monads: the value zero is a special value under multiplication in the field of integers, because any value multiplied by zero is still zero. This is similar to the None value in an Option in that the standard operations such as map and filter have no effect on None. None is thus a "zero" value for an Option. In the same way, an empty List is a "zero" value for a List.

Monads as Delayed Computations

Back in 2007, when I had just started looking at Haskell and had first run across monads, I had the good fortune to be sitting next to Conal Elliott on a long plane flight. He was on his way to deliver a paper at a Haskell conference, but at the time I had no idea who he was. Since he obviously knew a lot about Haskell, I asked him to explain monads to me, which he cheerfully attempted. Given how little I knew at the time about all of the pieces I list in this post, he did a very good job - but I still struggled with it.

My recollection of my interpretation of his explanation is this: In a pure functional program, there are no side effects, so the program must do the same thing every time. Clearly this does not work when there is user input, because you want the program to do different things based on different user input each time it is executed. So think of the program execution as being in two phases: first, create an execution tree that represents the program with all possible choices based on user input; then evaluate that execution tree, using the user input when required to prune off parts of the tree and select other parts.

Of course the actual tree with all possible choices might be infinitely large, and certainly will be too large to fully instantiate, so you don't really separate the above two phases and try to build the whole tree at once. Instead, you build it only as you need it (lazy evaluation). So you build a bit of the tree, then you evaluate that bit, which prunes out a bunch of potential branches and directs you to the next part of the tree that needs to be built. Repeat until you have completed the evaluation, in which case the program terminates.

In the above model, the decision points that are based on user input are the monads. I visualized the monad as a node in the tree with a bunch of children together with a decision function based on user input that determined which of those children to evaluate.

Conclusion

My conclusion: don't worry about understanding monads, just keep reading about them and learning more about functional programming. Some day it will all make sense and seem easy.

Update 2009-02-18: Change typo "with" to "without" as pointed out by Joseph.