Tuesday, February 28, 2012

Date of Easter in JavaScript

A couple of years ago, I posted source code in F# for calculating the date of Easter. Well, that time of year is here again, but this time around I'll post a JavaScript example.

As before, the method is from Butcher's Ecclesiastical Calendar (1876). I present it in the form given in Peter Duffett-Smith's Practical Astronomy With Your Calculator (Cambridge 1981, the 1988 version is still available from Amazon, et al). And once again, I'd like to add that Mr. Duffett-Smith's books are among the most fun and interesting math books you'll ever find!

I'm no JavaScript wiz, but I did test it in both MSIE7 and Chrome. However, as always, this code is presented “as-is” and without warranty or implied fitness; use at your own risk.

function easterForYear (year) {
var a = year % 19;
var b = Math.floor(year / 100);
var c = year % 100;
var d = Math.floor(b / 4);
var e = b % 4;
var f = Math.floor((b + 8) / 25);
var g = Math.floor((b - f + 1) / 3);
var h = (19 * a + b - d - g + 15) % 30;
var i = Math.floor(c / 4);
var k = c % 4;
var l = (32 + 2 * e + 2 * i - h - k) % 7;
var m = Math.floor((a + 11 * h + 22 * l) / 451);
var n0 = (h + l + 7 * m + 114)
var n = Math.floor(n0 / 31) - 1;
var p = n0 % 31 + 1;
var date = new Date(year,n,p);
return date;
}

Friday, February 17, 2012

Convention Over Complexity

Some Thoughts on the Virtue of Simplicity

There are good ideas that you can recognize as good ideas, yet not really appreciate just how good they are until you live them. Two such ideas is are simplicity and convention. I first encountered the notion that these could be a powerful pair in the excellent book How Buildings Learn by Stewart Brand (every programmer should read it):

“Convention is preferable to law, being more adaptive, accommodating, and locally appropriate, but a fast-moving society outruns the pace of formal convention and must resort to abstract law.” (p. 74)

He goes on to point out:

“In New York City the cost of getting permission for remodeling often exceeds the cost of the work itself.” (p. 75)

We, the programmers, web designers, and the customers that drive the process, are that “fast-moving society” outrunning the pace of convention. And the huge number of APIs, frameworks, databases, etc. – and the various associated rococo towers of functional calls parameters – are our volumes of “abstract law.” And, as in New York City remodeling, this results in a situation in which even the cost of even the simplest deviation from plan or maintenance can quickly exceed the value of the system.

The world of built architecture saw this coming before we recognized it in the world of virtual architecture. For decades now, architects like Christopher Alexander have been pointing to the need for an architecture based on placing person, place and convention over abstraction, an in implementing this architecture via modular design patterns. (Christopher Alexander is considered the Ur-father of the software design pattern movement. Every literate programmer should investigate his books on built architecture as well.)

And now, at long last, these same ideas are beginning to have an impact on the software world.

(Although not the sole or even the first proponent of such notions, I think a lot of credit has to be given to the Ruby on Rails community. If you’ll forgive the pun: Ruby is such a rich programming language, perhaps it needed a simple setting.)

As I think back to my own experience in this regard, it reminds me of the Zen proverb:

When I began my journey,
mountains were mountains and trees were trees;
During my journey,
mountains were no longer mountains and trees were no longer trees;
When I returned from my journey,
mountains were once again mountains and trees were once again trees.

When I first started programming, I simply wrote what was needed in the most direct way. I didn’t concern myself with structure or architecture or refactoring or mirroring existing interfaces. I churned out some pretty amazing stuff (for a beginner) during the brief intervals between classes, etc., but the results were a maintenance nightmare.

Then, I discovered the idea of formal programming and API design. I slavishly architected each program, strove to complete the design before beginning coding, etc. I tried to mirror existing APIs, providing things like formal copy constructors and comparison even where they were unlikely to be needed, etc.

But now, I once again see the wisdom of simplicity. Not the wild, unconstrained simplicity of the beginner, that stems from exuberance and ignorance. But the measured simplicity that comes of having repeatedly stumbled during my journey and having been burned one too many times from self-created complexity.

Below is a brief roster of programming practices and other ideas which encourage simplicity. Some of these have links to Wikipedia just to get you started, but remember that search engines are your friend.

Convention over configuration – the idea that the conventional use of a thing is also made to be the default. That the most likely use should also be the easiest, simplest, most natural, and most likely to guess.

Convention over code – the finer-grained sibling of convention over configuration. One example is languages that allow one to leave off purely syntactic elements such as braces and semicolons where they can be inferred.

Principle of least astonishment – stuff works as expected based on similar instances one has encountered. The cold water tap is on the right and has blue cap and the hot water tap is on the left and has a red cap.

Law of Demeter – stuff that is closer together talks in more detail than stuff that is far apart; stuff talks in preference to other stuff nearby and does not “jump the chain of command.” For example, it is reasonable that instances of classes within a library will share more knowledge with each other than with external classes. (Although the “one dot” principle does conflict with some functional programming best practices.)

The purpose of a system is what it does – and not how well it follows some abstract rules. However, keep in mind that cost-effective maintenance and extension are important parts of the purpose of most software systems. A related principle is that, to an experienced programmer, the intent of the program should be easily discernible from the code.

The Peter Principle – software tends to exist at a level of complexity just beyond the skill of the programmer who wrote it. This unfortunate situation results from two goals that – taken in isolation – are laudable: the goal of a programmer to push the limits, and the goal of a client to get the best immediate value. The key is to know when to stop: keep the ordinary stuff manageable, and save the boundary-pushing for those situations that really require it.

Principle of long term laziness – pretend that you, rather than the client, will have to pay the price for maintenance. When that inevitable bug shows up at six p.m. on Friday, which would you rather fix: the most complex piece of code you’ve ever written, or the simplest.

REPL is your friend – and if your environment doesn’t support formal REPL, favor experimentation by writing lots of small, easily testable blocks. The resulting code is almost always simpler and more maintainable. (This is also a binding principle in Christopher Alexander’s view of built architecture.)

The world is built of small, simple, reusable things. A lot of ancient architecture is lost forever because people pulled out the stones and bricks to make new buildings. The mighty palace or fortress became a ruin, but its components lived on in the form of simpler houses, stone walls, and pathways.

Software is the same way. The mega application or whiz-bang web page you’re so proud of today is tomorrow’s ruin. The basic classes and simple code fragments that make it up will be remembered, copied-and-pasted, and will live on. Build yourself bricks and tools, and use them to make house after house.

-Neil

Monday, February 13, 2012

Python is the New BASIC

(How’s that for a deliberately provocative title?)

Actually, in spite of everything your first impression is telling you, it’s intended as a compliment. Perhaps if I amend it a little, my intent will become clear:

“Python is both the new BASIC and the new Turbo Pascal.”

What I mean is this:

1) Python is freely available on all major computing platforms. Almost anybody with a computer can have access to Python. People working on the .NET and Java platforms also have the option of IronPython and Jython, respectively.

2) Python is accessible to beginners. A non-programmer can begin using Python and can do some interesting things without much fuss, day one, hour one. In large part this is because Python removes much of the clutter that it takes to get programs working in other languages. A text file and few lines of code, and you’ve got a Python program.

3) Python is accessible to young people. This includes the various Python tutorials aimed specifically at young people. PyGame, in particular, makes it simple for kids to get started doing all sorts of fun and interesting things.

4) Python doesn’t make you wait around, for results. You write a program and run it, no separate compilation phase. This is critical to keeping small programming tasks fun and useful. And although Python is not C, it is pretty darn fast when it runs, as well.

5) Python is handy for scientists and engineers. It was common “back in the day,” for scientists and engineers to use built-in line-number BASIC as a kind of “super programmable calculator.” Python does the same thing; it doesn’t punish you with all the scaffolding required by a large, structured program for simple cases where you don’t need it.

6) However, like Turbo Pascal, Python makes more advanced programing idioms available when you need them. Beginners can start simple and work their way towards more sophisticated concepts. Programs can start as linear test code and be refactored into more complex structures.

7) Also like Turbo Pascal, Python incorporates the best computer science that can be made easy to use. Python doesn’t push the state of the art for all computer science, but what it includes, it includes in a straightforward, “Pythonic” way.

And here’s one way Python is unlike BASIC:

1) The Python ecosystem contains a huge number of excellent libraries and other tools. So much so, in fact, that it has led to the description of Python as “a collection of libraries that just happens to be associated with a programming language.” In large part, this results from the way Python’s simplicity and fun encourages domain experts to produce such libraries.

There are a lot of other good and bad things about Python, but that’s how I can say “Python is the new BASIC,” and mean it as a compliment.

-Neil

Friday, February 3, 2012

Compiling Lua with Visual Studio 2010

Lua?

Lua is a dynamic, object-oriented, interpreted language.  Most programmers are aware of it as the scripting language used in the game World of Warcraft, as well as a number of other games.  However, Lua has been getting a lot of good press lately for a number of reasons.  Last June, Lua entered the Tiobe Index top 10 for the first time.  This winter, it won a Front Line Award from Game Developer’s Magazine.  And most recently, Lua was announced as the official scripting language for Wikipedia, beating out Javascript.

But Lua is also a fascinating language in its own right.  Roberto Ierusalimschy and the others who helped create the language made a number of design decisions which helped create a scripting language that is dynamic and useful, yet also very fast and efficient.  The source code is MIT licensed and compiles in “vanilla” C, so it is a good platform for computer science geeks who want to play around with the internals of a language.   Not to mention the current resurgence of interest in C and C++.

So there has never been a better time to learn a little bit about Lua. 

This post will show how to get started compiling and using Lua using Visual Studio.

At the Lua homepage (http://www.lua.org/  ), you can find a link to a “batteries included” Lua distribution for Windows.  It comes with a number of goodies, and is a worthwhile download.  However, the whole point of Lua is that it is meant to be embedded in other applications.  For this reason you’ll eventually want to compile and work with the Lua source itself.

The example below is based on my experience compiling Lua release 5.2 using Visual Studio 2010 with Visual C++.  If you’re reading this at a much later date, or are using Visual Studio 2008, you may need to adapt it accordingly.  (If you’re reading it at a much earlier date, something has probably gone wrong with the space-time continuum.)

Download Lua

1. Download the desired Lua sources from http://www.lua.org/  At the time of this post, a link to the latest sources can be found at the top of the page:  http://www.lua.org/download.html 

2. The latest release is compressed in gzip (.gz) format; if you don’t already have something that can decompress this, there are a number of utilities available for free or little charge (personally, I prefer 7-Zip).  You can decompress it somewhere as a backup, or else you can decompress it directly after creating a Visual Studio project.

Create a VS2010 C++ Project

1) Open Visual Studio and create a new Visual C++ project.  The type of project you want to create is the one listed in Visual Studio 2010 as File => New => Project… => Visual  C++ => General => Empty Project.  Call it whatever you like, e.g. just “Lua” if it won’t conflict with any other version of Lua you’re using, or perhaps “Lua52” if you want to keep track of the version.




2) Copy or decompress the Lua source files into the default place where Visual Studio puts C++ files.  In VC++ for VS2010 this is in the project folder under the solution folder.  (If you’re unsure, create a temporary .h file and look at where VS has put it.) 

3) Now go back into Visual Studio and add the files into the solution from the Solution Explorer window using the Add => Existing Item… option.  Add all files with a  .h or .hpp extension under “Header Files” and all the files with a .c extension under “Source Files.”



Compile Lua

1) If you try to compile the project at this point, you’ll get an error message similar to:

luac.obj : error LNK2005: _main already defined in lua.obj

This is because the Lua distribution includes main files for both the Lua REPL / file interpreter (lua.c) and the byte code compiler (luac.c). 

2) For present purposes, you want the interpreter “lua.c,” so remove the compiler “luac.c” from the project.  Now do a rebuild all.

Run Lua
1) If the rebuild all succeeds, you should be able to run the Lua REPL either inside Visual Studio, from Explorer, or from a command prompt.  The result should look something like this:


2) Try entering a few lines as a test:


3) You can also run Lua program files from the command line by following the name of the executable with the Lua program file name.
That’s all there is to it.  Now you can begin exploring Lua as a language and as an embeddable interpreter.   No doubt you’ll write a “hello world,” a Fibonacci generator, etc.  If you want to try adding commands to the language itself in C code, you can try creating a function with your name, etc.  And check out the resources available from links on the Lua site, including the “batteries included” versions, and tips for compiling Lua under Windows using other configurations (including links to a few complete projects).

Lua Documentation Etc.

Be sure to read the documentation included with the Lua distribution.  It includes valuable and up-to-date tips on compiling and running Lua.

A very good manual is included with the Lua distribution, but if you get serious about Lua, I recommend the book “Programming in Lua” by Roberto Ierusalimschy.  An earlier edition is available online, which will help you get started (it’s called “The Red PIL” for its red cover).  However, if you end up liking Lua enough to keep using it, I recommend buying the more recent edition (called “The Blue PIL” for its blue cover).  It’s a great resource for learning Lua, and buying a copy will help support Lua.

Now the Bad News

Lua’s greatest strength is the fact that it compiles in plain old C on almost any platform imaginable, including native Windows.  Unfortunately, this is bad news if your “plain old C” is actually managed C++ under .NET.  Lua does a number of things that are very valid in C, but which are a problem for managed environments.

For this reason, getting Lua interacting properly with .NET takes a bit more effort.

But the good news is that all is not lost!  Lua is such a useful tool that many in the Lua community have put in the effort to get Lua working with .NET.

There are a number of solutions out there, from making the modifications necessary to get Lua compiled and working in a managed code environment, to complete interoperability environments.  Not being an expert on this aspect of Lua, I can’t recommend any specific tool.  However, as the popularity of Lua increases, I expect that things will consolidate around a few of the best solutions.

-Neil



Friday, January 27, 2012

Mixins Simplify Composition in Scala

Scala has a nifty feature called “traits.”  A trait is a means of encapsulating methods and fields that behaves in some ways like an interface, and in other ways like an abstract class.  Like an interface or abstract class, a trait can declare methods and fields that must later be defined in some concrete class.  Like an abstract class, but unlike an interface, a trait can also supply default bodies and values for those methods and fields.  Unlike a class, however, a trait cannot have constructor parameters.  Here is a simple trait that specifies an iterator:

 

trait MyIter [A] {

  def next(): A

  def hasNext: Boolean

}

 

In the first of these roles, traits can be used just like traditional interfaces: as a way of specifying the external behavior of an object without saying anything about its implementation.  In the second of these roles, traits can be used like abstract base classes, supplying both declarations and definitions. 

 

However – and this is the really cool part – since traits are not classes, multiple traits can be specified for a single object without violating single inheritance constraints.  So, like interfaces, multiple traits can contribute to a class declaration, but unlike either interfaces or single base classes, multiple traits can also contribute to a class definition.  This is sometimes called “mixin” inheritance, because the capabilities are “mixed into” other types.

 

The example here develops a simple set of iterator traits and classes.  Iterators were chosen because they are a simple construct which can nevertheless illustrate some powerful mixin concepts.  Of course, the standard Scala library contains a much more sophisticated set of iterator traits and classes, and you’ll want to use those rather than mine for real-world programming.  In particular, to keep things simple, I ignore covariance and contravariance, which can be explicitly controlled in Scala types.

 

 (And as always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use it at your own risk.)

 

(The code is presented in fragments; a complete listing is at the bottom.)

 

Recalling the simple iterator example from above:

 

trait MyIter [A] {

  def next(): A

  def hasNext: Boolean

}

 

This trait is parameterized on the iterated type, the “[]” brackets delineating type parameters in Scala.  Also, the methods follow the standard Scala practice for methods without arguments: if the method modifies the object, parentheses are used, if it does not modify the object, the parentheses are omitted.

 

In this case, the iterator supplies only declarations, and so is used in an interface role.  (In fact, it resembles the actual Iterator trait from Scala.)  We could supply functionality via another trait or concrete class, but we’ll actually do it using an abstract class.  The abstract class below defines iteration across a range of integers, and delegates the conversion from integer to iterated type to its derived classes using the abstract function “current.”  Inheritors can get basic iteration capability simply by defining this function.

 

abstract class MyCursorIter[A] (

  protected val first: Int,

  protected val last: Int) extends MyIter[A] {

 

  protected var cursor = first - 1

 

  protected def current: A

 

  def next() = {

    if (hasNext) {

      cursor += 1

      current

    }

    else throw new Exception("Iteration past end.")

  }

 

  def hasNext = cursor < last

}

 

Note that first trait or the base class is mixed in using the “extends” keyword; subsequent traits are mixed in using the “with” keyword.

 

Once you have an iterator, you can use it to do all sorts of wonderful things.  But perhaps the most wonderful of all is the higher order function: “fold.”  Fold is a good candidate for the second role of traits: defining methods and values.  Below is a definition of a fold trait as applied to the “MyIter” trait:

 

trait MyFold[A] {

 

  this: MyIter[A] =>

 

  @tailrec

  final def fold[B] (acc: B, f:(B,A) => B): B = {

    if (hasNext) {

      fold(f(acc,next()),f)

    } else acc

  }

}

 

The curious-looking line “this: MyIter[A] =>“ tells the compiler that this trait will only be applied to types that also support the “MyIter[A]” trait.  This is what allows you to use members “hasNext” and “next()” from that trait.  “@tailrec” on the fold function tells the Scala compiler that the function should be made tail-recursive, and to warn you at compile time if that is not possible.  What follows is a standard fold function that takes an initial result “acc” (for accumulator), and steps through the elements passing on the result of applying the function “f” to the previous result and each element, finally returning the last result.

 

Fold is like the Swiss Army Knife of higher order functions in that it can be used to implement a whole range of other higher order functions.  The fragment below shows a couple of other mixins which use fold. The first computes the length of an iterated sequence and the second converts an iterated sequence to a list.  Note the use of the “this: … =>” construct to inform the compiler that these traits extend types with the fold trait.  And note also the use of the “_” in “this: MyFold[_] =>” in MyLength which indicates that the type parameter is not important for this definition.  Also note that both functions consume the iterator, leaving it empty.

 

trait MyLength {

 

  this: MyFold[_] =>

 

  def length() = {

    fold(0, (b: Int, _) => b + 1)

  }

}

 

 

trait MyToList[A] {

 

  this: MyFold[A] =>

   

  def toList() =

    fold(Nil, (b: List[A], a: A) => a::b).reverse

}

 

And, for convenience, here is a trait that mixes a reset function into the “MyCursorIter” class.  If an iterator can be made resettable, functions can be written that consume it without rendering it useless for further computation.

 

trait MyReset {

 

  this: MyCursorIter[_] =>

   

  def reset() = cursor = first - 1

}

 

At last, time for the first concrete implementation.  And here it is, “MyStringIter,” a character iterator across strings:

 

class MyStringIter (s: String)

  extends MyCursorIter[Char](0,s.length - 1)

  with MyReset

  with MyFold[Char]

  with MyLength

  with MyToList[Char] {

 

  protected def current = s(cursor)

}

 

And the test:

 

object Test00 {

 

  def main(args: Array[String]): Unit = {

   

    // String example.

          

    val msi = new MyStringIter("This is a test.")

   

    println(msi.toList())

   

    msi.reset()

 

    println(msi.length())

 

 

    println("Your breakpoint here.")

  }

}

 

But wait!  There’s more!  In Scala you can use all these traits and classes to cobble together types on the fly.  The extended test below illustrates this by defining, with the test function itself, an ad-hoc iterator across integer ranges.

 

object Test00 {

 

  def main(args: Array[String]): Unit = {

   

    // String example.

          

    val msi = new MyStringIter("This is a test.")

   

    println(msi.toList())

   

    msi.reset()

  

    println(msi.length())

   

    // Range example.

          

    val msr =

      new MyCursorIter[Int](0,9)

        with MyReset

        with MyFold[Int]

        with MyToList[Int]

        { protected def current = cursor }

   

    println(msr.toList())

   

    msr.reset()

   

    // Error!  MyLength is not mixed-in to msr.

    // println(msr.length())

  

    println("Your breakpoint here.")

  }

}

 

Now isn’t that cool?

 

-Neil

 

Here is the full listing:

 

/*

 * Use of this software is governed by

 * the following license:

 * The MIT License (MIT)

 * http://www.opensource.org/licenses/mit-license.php

 *

 * Copyright (c) 2012 Neil P. Carrier

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT

 * WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,

 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR

 * PURPOSE AND NONINFRINGEMENT. IN NO EVENT

 * SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE

 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT,

 * TORT OR OTHERWISE, ARISING FROM, OUT OF

 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE

 * OR OTHER DEALINGS IN THE SOFTWARE.

 *

 */

 

package com.techneilogy.test00

 

import annotation.tailrec

 

 

trait MyIter [A] {

  def next(): A

  def hasNext: Boolean

}

 

 

abstract class MyCursorIter[A] (

  protected val first: Int,

  protected val last: Int) extends MyIter[A] {

 

  protected var cursor = first - 1

 

  protected def current: A

 

  def next() = {

    if (hasNext) {

      cursor += 1

      current

    }

    else throw new Exception("Iteration past end.")

  }

 

  def hasNext = cursor < last

}

 

 

trait MyFold[A] {

 

  this: MyIter[A] =>

 

  @tailrec

  final def fold[B] (acc: B, f:(B,A) => B): B = {

    if (hasNext) {

      fold(f(acc,next()),f)

    } else acc

  }

}

 

 

trait MyLength {

 

  this: MyFold[_] =>

 

  def length() = {

    fold(0, (b: Int, _) => b + 1)

  }

}

 

 

trait MyToList[A] {

 

  this: MyFold[A] =>

   

  def toList() =

    fold(Nil, (b: List[A], a: A) => a::b).reverse

}

 

 

 

trait MyReset {

 

  this: MyCursorIter[_] =>

   

  def reset() = cursor = first - 1

}

 

 

class MyStringIter (s: String)

  extends MyCursorIter[Char](0,s.length - 1)

  with MyReset

  with MyFold[Char]

  with MyLength

  with MyToList[Char] {

 

  protected def current = s(cursor)

}

 

 

object Test00 {

 

  def main(args: Array[String]): Unit = {

   

    // String example.

          

    val msi = new MyStringIter("This is a test.")

   

    println(msi.toList())

   

    msi.reset()

 

    println(msi.length())

   

    // Range example.

          

    val msr =

      new MyCursorIter[Int](0,9)

        with MyReset

        with MyFold[Int]

        with MyToList[Int]

        { protected def current = cursor }

   

    println(msr.toList())

   

    msr.reset()

   

    // Error!  MyLength is not mixed-in to msr.

    // println(msr.length())

  

    println("Your breakpoint here.")

  }

}