Category Archives: functional programming

http://en.wikipedia.org/wiki/Functional_programming

Why Data Structures Matter

Our experience on Day 0 of JPR11 yielded a nice example of the need to choose an appropriate implementation of an abstract concept. As I mentioned in the previous post, we experimented with Michael Barker’s Scala implementation of Guy Steele’s parallelizable word-splitting algorithm (slides 51-67). Here’s the core of the issue.

Given a type-compatible associative operator and sequence of values, we can fold the operator over the sequence to obtain a single accumulated value. For example, because addition of integers is associative, addition can be folded over the sequence:

1, 2, 3, 4, 5, 6, 7, 8

from the left:

((((((1 + 2) + 3) + 4) + 5) + 6) + 7) + 8

or the right:

1 + (2 + (3 + (4 + (5 + (6 + (7 + 8))))))

or from the middle outward, by recursive/parallel splitting:

((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8))

A 2-D view shows even more clearly the opportunity to evaluate sub-expressions in parallel. Assuming that addition is a constant-time operation, the left fold:

foldLeftPlain.jpg

and the right fold:

foldRightPlain.jpg

require linear time, but the balanced tree:

foldTreePlain.jpg

can be done in logarithmic time.

But the associative operation for the word-splitting task involves accumulating lists of words. With a naive implementation of linked lists, appending is not a constant-time operation; it is linear on the length of the left operand. So for this operation the right fold is linear on the size of the task:

foldRightLinear.jpg

the left fold is quadratic:

foldLeftLinear.jpg

and the recursive/parallel version is linear:

foldTreeLinear.jpg

Comparing just the “parallel-activity-versus-time” parts of those diagrams makes it clear that right fold is as fast as the parallel version, and also does less total work:

compareLinear.jpg

Of course, there are other ways to implement the sequence-of-words concept, and that is the whole point. This little example provides a nice illustration of how parallel execution of the wrong implementation is not a win.


The title of this post is a not-very-subtle (but respectful) reference to “Why Functional Programming Matters“, an excellent summary by John Hughes that deserves to be more widely read.

Purely Functional Data Structures, by Chris Okasaki, covers a nice collection of algorithms that avoid the trap mentioned above.

41XlPaC+ZqL._SL160_.jpg

Also, video from this year’s Northeast Scala Symposium is now on-line for the session on functional data structures in Scala, presented by Daniel Spiewak.

Don’t return null; use a tail call

Why should an object-oriented programmer care about tail-call elimination? Isn’t that just another esoteric functional programming concept? Maybe not.

Back when dinosaurs roamed the earth, a common technique for performing a subroutine call worked this way:

  1. The caller stored the address at which it wished to resume execution in a known place (e.g. adjacent to the called routine’s code);
  2. The caller branched to the called routine’s entry address;
  3. Upon completion, the called routine branched indirectly to the stored return address.

Of course, this technique precluded both recursive and re-entrant calls, but those were regarded as esoteric, theoretical concepts with little if any practical use (see the “Historical Footnote” below). Times change, but programmers are still living with constraints whose roots go back to the kinds of mechanism described above. We all know that a simple and correct recursive routine can still founder on the stack overflow reef. But I recently saw a blog post by Zachary D. Shaw that rubbed a bit more salt in that wound.

His post on Returning Null discusses an alternative to the common idiom of returning a null result as a way of saying “not found”. In his post, the caller passes itself as an argument (using a suitable interface type, of course), and the callee responds by invoking either a “found” or “not found” method on the caller. This models the interaction as an exchange of specific and appropriate messages, instead of encoding the “not found” case in an abnormal value which the caller must decode in order to determine what to do.

I’m currently enjoying the book Growing Object-Oriented Software, Guided by Tests by Steve Freeman and Nat Pryce, of mock objects fame. That book reminded me of the value of separating the design concept of passing messages from the implementation detail of writing methods. It would be nice to be able to use such a technique without stack depth raising its ugly little head as an issue, however fleeting.

Simon Harris posted on this issue from a Ruby perspective, and Guy Steele’s Fortress blog has an elegant illustration in that language. Of course, Steele’s 1977 paper is the ultimate resource on the subject. Even the name of that paper has had its influence.


Historical Footnote: The November 1963 issue of Communications of the ACM contained a short piece entitled “Recursive programming in Fortran II“. Membership is required to download the PDF, but you can get a sense of the attitudes of the time just by reading the abstract on the linked page.

Why lists are not primitive

Yesterday’s SICP study group call indulged briefly in the “why LISP hasn’t caught on” theme. I suggested that some programmers seem to have a limited tolerance for abstraction, and cited the well-known Primitive Obsession anti-pattern as evidence. One of the other participants (I’m sorry that I don’t know all the voices yet) challenged that statement. After pointing out how often the humble list is used as a universal data structure, he asked whether that was Primitive Obsession in another disguise. The conversation moved on, but that question stuck in the back of my mind.

This morning it re-emerged, dragging the following conjecture.

Although the list is a fundamental structuring mechanism in LISP, it is far from “primitive” in way that e.g. int is a primitive data type in Java. Although number theory is a well-respected branch of Mathematics, Ben Bitdiddler and Eva Lu Ator can write application code littered with int variables without ever appealing to the theoretical properties of integers–Peano’s Postulates and the like. After all, they’ve known how to count and do arithmetic since elementary school, right?

On the other hand, the LISP list is a fairly abstract and conceptual beast; list-based code normally uses recursion, either explicitly or hidden beneath the thinnest of veneers, such as map and reduce. And from there, it’s the tiniest of steps to begin reasoning about one’s code via full-blown Mathematical Induction. Furthermore, all of the conceptual properties of lists are lying there in plain sight every time a list appears. Therefore I’m encouraged to think of generalities that can re-use those tasty properties with great freedom.

In contrast, how many Java programmers routinely make the jump from

String personName;

to

public class PersonName {
    public final String firstName;
    public final String lastName;
    ...
}

to including (correctly-working!) methods for comparison and equality? (And I’m not just picking on Java; the same is true of many other “C-like” language communities.) Even though strings are comparable, and ordered composites of comparable types have an obvious default comparability, realizing that obvious comparison is tedious and error-prone. If my language trains me to think that certain things are too much trouble, then I’ll tend to stop thinking about them. And when offered a language that makes them freely available again, it will be all too easy to ask, “Who needs all that stuff?”

Jesse Tilly at Memphis JUG

This month’s Memphis Java Users’ Group meeting featured Jesse Tilly of IBM Rational Software, who spoke to us on static analysis. He will be doing a more product-intensive session, “What is IBM® Rational® Software Analyzer® Telling Me?”, at the upcoming IBM Rational Software Conference. (Don’t be misled by all those “circle-R”s; I just linked to the title from the conference web site.)

For our meeting, Jesse left the branding iron at home. He began with an overview of the history and benefits of static analysis. The major portion of the presentation offered a practical approach to analysis as part of a development project, including a detailed how-to on interpreting and using analysis results. Jesse finished with return to history, drawing unexpected parallels with the analysis of Enigma traffic at Bletchley Park during WWII—the background for Allen Turing‘s later theoretical work that led to the computers we program today.

Because Jesse had an early flight, our regular door-prize drawing followed his presentation. In our lightning talk segment, Matt Stine introduced Morph AppSpace, I presented on “Structured Functional Programming” (pdf here), and Walter Heger gave a quick look at jGears.


Recommended reading:

Encryption and cryptanalysis are deeply entwined with computing, whether in history(Codebreakers: The Inside Story of Bletchley Park) or in imagination (Cryptonomicon).

Two highly-respected tools for static analysis in Java are FindBugs and PMD; both web sites offer excellent documentation and other reference material.

BuilderBuilder: The Model in Haskell

This post describes the first model in Haskell for the BuilderBuilder task. We will develop the model incrementally until we have rough parity with the Java version.

I’m experimenting with ways to distinguish user input from system output in transcripts of interactive sessions. This time I’m trying color, using a medium blue for output. I will appreciate feedback on whether that works for you.

Step one: defining and using a type

The simplest possible Haskell version of our model for a Java field is:

data JField = JField String String

However, the PMNOPML (“Pay Me Now Or Pay Me Later”) principle says that we’ll regret it if we stop there. In fact, later comes quickly.

We can create an instance of JField in a source file:

field1 = JField "name1" "Type1"

To do the same in a ghci session, prefix each definition with let, as in:

*Main> let field1 = JField "name1" "Type1"

Step two: showing the data

Trying to look at the instance yields a fairly opaque error message.

*Main> field1

<interactive>:1:0:
    No instance for (Show JField)
      arising from a use of `print' at <interactive>:1:0-5
    Possible fix: add an instance declaration for (Show JField)
    In a stmt of a 'do' expression: print it

Remember that in Java the default definition of toString() returns something like com.localhost.builderbuilder.JFieldDTO@53f67e; that’s also obscure at first glance. Haskell just goes a bit further, complaining that we haven’t defined how to show a JField instance. We can ask for a default implementation by adding deriving Show to a data type definition:

data JField = JField String String deriving Show

After loading that change, we get back a string that resembles the field’s defining expression:

*Main> field1
JField "name1" "Type1"

Step three: referential transparency

Our first model represented a Java class by its package, class name, and enclosed fields. The Haskell equivalent is:

data JClass = JClass String String [JField] deriving Show

The square brackets mean “list of …”, so a JClass takes two strings and a list of JField values. I’ll say more about lists in a moment, but first let’s deal with referential transparency.

We can build a class incrementally:

field1 = JField "name1" "Type1"
field2 = JField "name2" "Type2"
class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

or all at once:

class1 = JClass "com.sample.foo"
                "TestClass"
                [   JField "name1" "Type1" ,
                    JField "name2" "Type2"
                ]

and get the same result:

*Main> class1
JClass "com.sample.foo" "TestClass" [JField "name1" "Type1",JField "name2" "Type2"]

As mentioned previously, only one of those definitions of class1 can go in our program. To Haskell, name = expression is a permanent commitment. From that point forward, we can use name and expression interchangeably, because they are expected to mean the same thing. That expectation would break if we were allowed to give name another meaning later (in the same scope).

Consequently, we can define a class using previously defined fields, or we can just write everything in one definition, nesting the literal fields inside the class definition. As we’ll see later, this also has implications for how we write functions; a “pure” function and its definition are also interchangeable.

Step four: lists

The array is the most fundamental multiple-valued data structure in Java; the list plays a corresponding role in Haskell. In fact, lists are so important that there are a few syntactical short-cuts for dealing with lists.

  • Type notation: If t is any Haskell type, then [t] represents a list of values of that type.
  • Empty lists: Square brackets with no content, written as [], indicate a list of length zero.
  • Literal lists: Square brackets, enclosing a comma-separated sequence of values of the same type, represent a literal list.
  • Constructing lists: The : operator constructs a new list from its left argument (a single value) and right argument (a list of the same type).

For example, ["my","dog","has","fleas"] is a literal value that has type [String] and contains four strings. "my":["dog","has","fleas"] and "my":"dog":"has":"fleas":[] are equivalent expressions that compute the list instead of stating it as a literal value.

By representing the fields in a class with a list, we achieve two benefits:

  • The number of fields can vary from class to class.
  • The order of the fields is significant.

Step five: types and records

Given a JField, how do we get its name? Or its type? We can define functions:

fieldName (JField n _) = n
fieldType (JField _ t) = t

and do the same for the JClass data:

package   (JClass p _ _ ) = p
className (JClass _ n _ ) = n
fields    (JClass _ _ fs) = fs

but all that typing seems tiresome.

Before solving that problem, let’s note two other limitations of our current implementation:

  • Definitions using multiple String values leave us with the burden of remembering the meaning of each strings.
  • The derived show method leaves us with a similar problem; it doesn’t help distinguish values of the same type.

If you suspect that I’m going to pull another rabbit out of Haskell’s hat, you’re right. In fact, two rabbits.

Type declarations

We can make our code more readable by defining synonyms that help us remember why we’re using a particular type. By adding these definitions:

type Name     = String
type JavaType = String
type Package  = String

we can rewrite our data definitions to be more informative:

data JField = JField Name JavaType deriving Show
data JClass = JClass Package Name [JField] deriving Show

Record syntax

The second rabbit is a technique to get Haskell to do even more work for us. We represent each component of a data type as a name with an explicit type—all in curly braces, separated by commas:

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

When we use this syntax, Haskell creates the accessor functions automagically, and enables a more explicit and flexible notation to create values. All of these definitions:

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

produce equivalent results:

*Main> field1
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1a
JField {fieldName = "name1", fieldType = "Type1"}
*Main> field1b
JField {fieldName = "name1", fieldType = "Type1"}

Step last: that’s it!

We have covered quite a bit of ground! The complete source code for the model appears at the end of this post. With both Java and Haskell behind us, we have most of the basic ideas we’ll need for the Erlang and Scala versions.


Recommended reading:

Real World Haskell, which is also available
for the Amazon Kindle
or on-line at the book’s web site. I really can’t say enough good things about this book.


The current BuilderBuilder mode in Haskell, along with sample data, is this:

-- BuilderBuilder.hs

-- data declarations

type Name     = String
type JavaType = String
type Package  = String

data JField = JField {
     fieldName :: Name ,
     fieldType :: JavaType
} deriving Show

data JClass = JClass {
     package   :: Package ,
     className :: Name ,
     fields    :: [JField]
} deriving Show

-- sample data for demonstration and testing

field1  = JField "name1" "Type1"
field1a = JField {fieldName = "name1", fieldType = "Type1"}
field1b = JField {fieldType = "Type1", fieldName = "name1"}

field2 = JField "name2" "Type2"

class1 = JClass "com.sample.foo" "TestClass" [field1, field2]

studentDto = JClass {
    package   = "edu.bogusu.registration" ,
    className = "StudentDTO" ,
    fields    = [
        JField {
            fieldName = "id" ,
            fieldType = "String"
        },
        JField {
            fieldName = "firstName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "lastName" ,
            fieldType = "String"
        },
        JField {
            fieldName = "hoursEarned" ,
            fieldType = "int"
        },
        JField {
            fieldName = "gpa" ,
            fieldType = "float"
        }
    ]
}

Updated 2009-05-09 to correct formatting and add category.

BuilderBuilder: Haskell Preliminaries

The next step in the BuilderBuilder project is to develop a model in Haskell that is analogous to the Java model in the previous post. This post will introduce just enough Haskell to get started; the next post will get into the BuilderBuilder model.

Environment:

I’m using GHC 6.10.1, obtained from the Haskell web site. There are a variety of platform-specific binaries; I used the classic configure/make/install process on OSX. (For Java programmers, make is what we used instead of ant back in the Jurassic era.) Consult the Haskell Implementations page for details on obtaining Haskell for your preferred platform.

The complete development environment consists of two windows: one running a text editor, and the other running ghci, the interactive Haskell shell that comes with GHC.

Haskell introduction:

Use your text editor to create a file named bb1.hs with this content:

-- bb1.hs

-- simplest possible data declarations

data JField = JField String String

-- sample data for demonstration and testing

field1 = JField "id" "String"

-- sample function

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Then run ghci as follows, where user input is underlined:

your-prompt-here$ ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> helloField field1
"Hello, id, of type String"
*Main> 

We started ghci, told it to load our source file (the :l … line), and then invoked the helloField function on the sample field. Now let’s examine the Haskell features used in that code. The lines beginning with double-hyphens are comments, and will be ignored in the description.

Defining data types

Because Haskell emphasizes functions, it’s no surprise that the syntax for defining data types is very lightweight. The Java BuilderBuilder model represents a field with two strings, one for the name and one for the type. The simplest possible Haskell equivalent is:

data JField = JField String String

This defines a data type named JField. It has a constructor (also named JField) that takes two strings, distinguished only by the order in which they are written.

Defining values

The next line of code defines an instance of this type:

field1 = JField "id" "String"

The equal sign means “is defined as“. That statement defines field1 as the instance of JField constructed on the right-hand side. It is not declaring and initializing a mutable variable. Within the current scope, attempting to redefine field1 will produce an error. (More about scope later.)

Defining functions

Finally, we have a simple function that converts a JField to a String.

helloField :: JField -> String
helloField (JField n t) = "Hello, " ++ n ++ ", of type " ++ t

Everything in Haskell has a type, including functions. The double colon means “is of type“, so the type of helloField is function from JField to String.

The value of applying helloField to a JField containing strings n and t is defined by the expression on the right-hand side. Haskell regards strings as lists of characters; the ++ operator concatenates lists of any type. The names n and t are only meaningful within that definition, similar to the local variables in this Java fragment:

public static String helloField(IJField f) {
    String n = f.getName();
    String t = f.getType();
    return "Hello, " + n + ", of type" + t;
}

Type inference

Java requires that we explicitly declare the local variables as type String. But in Haskell, because JField is specified to have two String values, the compiler can infer the types of n and t In fact, the entire first line of helloField is not necessary. The defining equation in the second line explicitly uses a JField on the left and constructs a String on the right. Therefore, the compiler can infer JField -> String as the type of the function. Haskell’s type inference allows us to write very compact code without giving up strong, static typing.

To see that in action, add the following line to the end of your bb1.hs file:

hiField (JField n _) = "Hi, " ++ n

(The underscore is a wild card, showing the presence of a second value but indicating that we don’t need it in this function.)

Reloading bb1.hs in ghci allows us to see type inference at work.

*Main> :l bb1.hs
[1 of 1] Compiling Main             ( bb1.hs, interpreted )
Ok, modules loaded: Main.
*Main> hiField field1
"Hi, id"
*Main> :type hiField
hiField :: JField -> [Char]

As we’ll see later in this series, Scala brings type inference to the JVM environment. Coming from the dynamic language side, the Diamondback Ruby research project is adding type inference to Ruby. So perhaps type inference is (finally) an idea whose time has come.

We’ll pick up more Haskell details along the way, but we have enough to start defining our first BuilderBuilder model. That will be the subject of the next post.


Updated 2009-05-09 to fix formatting.

BuilderBuilder: The Agenda

The “BuilderBuilder” posts will be my exploration of one question: “What does Functional Programming mean to me as a practicing OO software developer?” Despite contemporary buzz about how FP will save the world from bugs and single-threaded code, I don’t want to read (or write) another clever Fibonacci number generator, or another theoretical explanation of category theory and monads. I want to see what FP is like when it sits down the aisle from me in work clothes.

To pursue that goal, I’m going to explore a programming problem that meets these criteria:

  1. Its purpose would be recognizable to a working programmer.
  2. It is large enough that a clever one-liner won’t suffice.
  3. It isn’t (consciously) chosen to cater to either OO or FP.
  4. It will require me to try things outside my daily comfort zone.

That last point means that I’ll make mistakes and do stupid things. I hope the record, warts and all, helps someone else (including me, later on) avoid them.

The problem I’ve chosen is a specific code generation task, which I’ll describe in the next post. There is a wide range of opinions on source code generation, but source code is one thing that any programmer understands, regardless of other application domain specialization.

Because my goal is exploration, and I’m starting with unequal familiarity with the languages I’ll use, the code almost certainly won’t be idiomatic or make best use of all available libraries. In fact, I’ll probably do more than necessary “by hand” to avoid bias toward more familiar tools. I may be able to address some of that along the way, based on accumulated experience (or helpful feedback, hint, hint… ;-).

OK, enough meta-talk. Next up, the task.

Scala and Programming 2.0

I commented elsewhere on how the “Architecture of Participation” idea may be percolating into the field of programming languages. I am especially interested in seeing whether the adoption of Scala provides evidence of this phenomenon.

Scala is a strongly, statically typed language implemented on the JVM—all characteristics that raise eyebrows (if not noses) in some circles. However, Scala’s ultralight approach to syntax is very much in line with the current taste for highly flexible notation and internal DSLs as a tool of expression.

Type inference is a very attractive compiler feature. And it’s great to get performance improvements “for free” every time the JVM team makes HotSpot smarter about JIT compilation, method in-lining, etc. But every time I revisit the ideas in Martin Odersky’s Scala talk at Javapolis 2007, I’m impressed with the design of Scala as a notation that invites participation.

Time will tell.

Project Euler 5: Multiplicity

The fifth problem from Project Euler asks for “the smallest number that is evenly divisible by all of the numbers from 1 to 20”. The key, for me, was to paraphrase that as “the least common multiple of 1 to 20”.

The least common multiple (lcm) of two natural numbers is their product divided by their greatest common divisor (gcd, a well-known lab rat). So, the stock definitions of lcm and gcd, along with one quick fold, are all we need.

  def divisibleByAll(lo: Int, hi: Int) = {
    def gcd(a: Int, b: Int) = gcd1(a max b, a min b)
    def gcd1(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    def lcm(a: Int, b: Int) = a * (b / gcd(a, b))
    (lo to hi).foldLeft(1)(lcm(_, _))
  }

There is one subtlety in this code; gcd is only there to insure that the (natural) arguments to gcd1 are correctly ordered (larger first). That is only needed once; if a >= b, then a % b cannot be larger than b, so the recursion in gcd1 is guaranteed to maintain the larger-first argument ordering.

Finally, this design encounters integer overflow at 1..24, changing the inner functions to work with Long gets us up to 1..42 before long overflow kicks in.

It should be obvious that the answers for 1..21 and 1..22 are the same as for 1..20, but I had to do a double-take while scanning for the limits. Duh.

Three X eerhT

The fourth task from Project Euler is to find the largest palindrome that is a product of two three-digit numbers. (I’m assuming decimal. 😉 )

Name no one man

The first sub-task is to determine whether the decimal representation of an integer is palindromic. A direct approach yields this:

  def reverseInt(n: Int) = {
    def rev(a: Int, b: Int): Int =
      if (a == 0)
        b
      else
        rev(a / 10, b * 10 + a % 10)
    rev(n, 0)
  }
  def isPalindrome(n: Int) = {
    reverseInt(n) == n
  }

I’m not approaching this by way of string conversion, for three reasons:

  • Nothing in the problem statement involves strings;
  • Expressing the solution in terms of string manipulation doesn’t make the solution significantly easier to understand; and
  • Doing so would be slower.

Now on to the more interesting part.

Seek no monkees

The problem can be solved by searching a two-dimensional space, where each dimension ranges over the three-digit integers. A moment’s thought provides the following additional facts we can use:

  • Multiplication is symmetric, so there’s no need to examine both products of two different numbers (a * b and b * a).
  • The Scala expression 100 to 999 provides the three-digit integers.
  • We can ignore 100 as a candidate, because any multiple of 100 must end in a zero, which isn’t the first digit of any multi-digit decimal number in standard notation.
  • There’s a solution, because 101 × 101 = 10201, which is palindromic. (It’s nice to know that the search function doesn’t need to deal with an empty solution space.)

Going for the obvious, we can construct the products of non-redundant pairs of three-digit numbers, filter the products for palindromes, and capture the maximum of the palindromes:

  def maxOfPalindromes() = {
    (
      for {
        a <- 101 to 999
        b  a max b)
  }

It would be easy to parameterize this for the range to be searched (either by bounds or by number of digits), but I want to focus on the search performance.

Top spot

The version above takes about 152 ms on my laptop, which seems entirely too much time for this small a task. The following diagram shows the search space, as a context for the rest of the post.

search2d.jpg

The names in the diagram describe the state of the search at a given instant:

  • lo and hi — the lower and upper bounds (inclusive) of the range being searched;
  • a and b — the current position in the search space;
  • c — the value at that position (the product of a and b); and
  • x — the largest palindrome found thus far.

In his landmark book, A Discipline of Programming (published 32 years ago!), Edsger Dijkstra stated the “Linear Search Theorem”. I’ll paraphrase it informally for our purposes as:

When searching for the maximum value having some property, examine the values in decreasing order; the first satisfactory value found will be the maximum.

Assuming that we apply this to both a and b, the green area has been examined and the blue area has not. We can express the next state of the search in a decision table (each row’s condition assumes that conditions on all previous rows failed):

Condition Action State changes
next a next b next x
a < lo Search complete
x is the result
n/a
b < a Current row searched,
move to next blue row
a - 1 hi x
c <= x c and rest of this row eliminated,
move to next blue row
a - 1 hi x
isPalindrome(c) c is new max palindrome
(rest of this row is smaller values)
a - 1 hi c
otherwise c eliminated,
continue searching current row
a b - 1 x

The decision table translates directly to a tail-recursive function. I’ll use a bit of scope management to avoid computing c unless it will be used.

  def maxPalindromeIn(lo: Int, hi: Int) = {
    def loop(a: Int, b: Int, x: Int): Int = {
      if (a < lo)
        x
      else if (b < a)
        loop(a - 1, hi, x)
      else {
        val c = a * b
        if (c <= x)
          loop(a - 1, hi, x)
        else if (isPalindrome(c))
          loop(a - 1, hi, c)
        else
          loop(a , b - 1, x)
      }
    }
    loop(hi, hi, 0)
  }
  def maxPalindrome3x3() = maxPalindromeIn(101, 999)

This runs in about 445µs, a speedup factor of well over 300.

I prefer π

Let me round this post off with a few observations.

Performance is not the most important issue. I probably need to state that clearly, having quoted run time so often in this and recent Project Euler posts. I believe that speed, small memory footprint, and any other measure of economy, should be subordinate and subsequent to good design and correctness.

Those who forget history are condemned to repeat it. Over twenty years ago, when the dreaded “G” word was still occasionally heard in polite programming circles, a misguided letter to the editor of the Communications of the ACM attempted to claim that goto was necessary to effective programming and offered a small problem in defense of that claim. Dijkstra’s response addressed the errors and approach of the claim and its “solution”; his demonstration used the idea of the two-dimensional application of the Linear Search theorem.

There are important ideas that transcend programming model. The ideas in A Discipline of Programming are all presented in an imperative style, yet the clarity of design makes the concepts important to FP as well. That book is not an easy read (I worked rather than read through it when I got my copy in 1976) but it rewards the investment richly. David Gries gave a tutorial-style presentation of many of the same core ideas in The Science of Programming. I cannot possibly recommend them highly enough.

Compare and contrast. It’s useful to see how others approach a problem, after you’ve solved it yourself.

My RSS reader is subscribed to the fellow solvers above; many of them have other interesting things to say beyond Project Euler!


Recommended reading: