F# Enters the TIOBE Top 20!

For the first time, F# has entered the TIOBE Top 20!

The TIOBE index rates programming language popularity based on a number of criteria.

This is certainly a feather in the cap of F#, and all those who have worked to promote the language over the last year deserve congratulations. But now is not the time for the F# community to rest on its laurels. Let's make Top 10 the new goal!

-Neil

F# User-Defined Numeric Literals

Today’s blog is about something most F# programmers have perhaps never encountered: user-defined numeric literals. I won’t go into too much detail; the available documentation does a much better job than I could:

From the F# specification.

Reference manual page.

F# Power Pack. (Source code file q.fs in the math section as of this posting.)

Basically, user-defined numeric literals allow a programmer to define a new numeric type based on suffix of a literal -- similar to built-in numeric literals. (For example, instances of the built-in numeric literal type uint32 can be written as: “42u.”)

User-defined numeric literals allow the definition of new types by replacing the suffix (“u” in the uint32 example), with any of the characters Q, R, Z, I, N, or G. For example, you could write something that looks like this:

let x = 425Q

The programmer supplies a module that determines how the literals are interpreted. The name of the module must be “NumericLiteral,” followed by the suffix it controls (e.g. “NumericLiteralG”). This module must define several functions that determine how numbers of various lengths are handled. You can read about the details in the sources above, but there are five main functions:

FromZero – Called when a zero is encountered (e.g. 0Q).
FromOne – Called when a one is encountered.
FromInt32 – Numbers from 2 to Int32.MaxValue.
FromInt64 – Numbers from Int32.MaxValue+1 to Int64.MaxValue.
FromString – Even bigger numbers.

The “smallest” function that can process a number is the one that is called, and a function must exist for the proper range. For instance, if you write “42Q,” a FromInt32 function must exist, and it is the one called.

Here is a more complete example. It allows for numeric literals which translate binary representations into uint32. This is not particularly useful, since F# already defines the 0b* binary literal form, but it will do as a sample. (And as always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

/// Numeric literal module for 32-bit unsigned 

/// binary numbers.

module NumericLiteralZ =

  let inline FromZero() = 0u

  let inline FromOne() = 1u

  let inline FromString (s:string) =

    let rec f (acc:uint32) i (s:string) =

      match i>=s.Length with

      | true -> acc

      | _ ->

      match s.[i] with

      | '0' -> f (acc*2u) (i+1) s 

      | '1' -> f (acc*2u+1u) (i+1)s 

      | _ -> failwith "Non-binary digit."

    f 0u 0 s

  let inline FromInt32 (n:int) =

    FromString(n.ToString())

  let inline FromInt64 (n:int64) = 

     FromString(n.ToString())

// Tests.

let n0 = 0Z

let n4 = 0000100Z

let n5 = 101Z

let nMax = 11111111111111111111111111111111Z

// For reference purposes, here is the 

// existing binary syntax; use it in the

// real world instead of my class above.

let n37 = 0b100101u

printfn "Your breakpoint here."

But I think this is the sort of thing that must be used with some caution. With only six suffixes available (Q, R, Z, I, N, and G), the potential for collision is high. Also, since this is an uncommon language feature, it is likely to confuse many users who encounter it for the first time.

More on Significant Whitespace (in F#, Python, Lua, and Ruby)

Since I want to add it to my coding “Room of Requirement,” I decided to keep working on the indentation processor a bit and make it more general. So here is a version that uses an interface to do dependency injection. (And as always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

There are a couple of things to note:

1) The indentation comparison is done through a function on the interface. This allows the interface to encapsulate *all* the information about the indentation. This has a number of benefits. As shown in the example below, it allows some types of data structures to act as their own indentation stack. Also, in more sophisticated versions, it would allow for custom processing of indentation based on context (e.g. multi-line argument lists, embedded multi-line strings, etc.).

2) I left out runtime validity checks in a few spots, leaving it up to the framework to throw an exception. In a real life implementation, some sort of custom exceptions might be better, so I’ve marked the spots with comments.

Since I am currently learning Python, Lua, and Ruby, I’m also including transliterations of the F# version into these languages. Since I am a relative newcomer to them, I apologize for any spots where I may have violated particular language idioms or best practices.

Of the three, the Python version looks the closest to the F# version, in large part because both languages use a block structure based on significant whitespace. The code has been tested in Python 3.2 and IronPython 2.6, but may work in earlier versions of either or IronPython 2.7.

For the Lua version, I chose to use the Lua object model described by Roberto Ierusalimschy in Programming in Lua. Lua does not have a native object type, and so objects must be implemented using associative tables. The way this is done is fascinating, and well worth reading up on even if you’re not planning on using Lua in the immediate future. It will make you a better programmer. The code was tested in Lua 5.1.4.

For the Ruby version, I did manage to use a couple of interesting Ruby-specific string routines. It was tested in Ruby 1.9.2 and IronRuby 0.9.

Last, I apologize for any problems in the formatting and/or syntax highlighting of the Lua, Python, and Ruby; I’m still getting tools for blogging in those languages.

F#:

open System

/// Callback handler for IndentOMatic.

type IIndentHandler =

  /// Adds a sibling.

  abstract Add:string->int->IIndentHandler

  /// Compares to the current indent level.

  abstract Cmp:string->int->int

  /// Pops to the parent.

  abstract Pop:unit->IIndentHandler

  /// Pushes a new child.

  abstract Push:string->int->IIndentHandler

/// Rudimentary indentation processor.

module IndentOMatic =

  /// Converts a string to a string, indent pair.

  let private stringToTag (s:string) =

    let rec leading l i (s:string) =

      match i>=l with

      | true -> i

      | _ ->

        match s.Chars(i) with

        | ' ' -> leading l (i+1) s

        | _ -> i

    let i = leading s.Length 0 s

    s.Substring(i),i

  /// Process a string and indent. 

  let rec private proc0 (ih:IIndentHandler) s i = 

    /// Pop the stack, looking for a parent

    /// or sibling.

    let rec scanUp (ih:IIndentHandler) = 

      match ih.Cmp s i with

      | n when n<0 -> scanUp (ih.Pop())

      | 0 -> ih

      | _ -> 

        // Custom exception here, if required.

        failwith "No matching unindent."

    match ih.Cmp s i with

    | n when n<0 -> proc0 (scanUp ih) s i

    | 0 -> ih.Add s i 

    | _ -> ih.Push s i

  /// Call to process a string. 

  let proc ih s =

    let t,i = stringToTag s

    proc0 ih t i

// Test.

/// Tree node that implements IIndentHandler.

type IHTestNode (parent:IHTestNode option,

                 tag:string,

                 indent:int) =

  /// Child branches.

  let mutable children:IHTestNode list = []

  /// Add a child.

  member private this.AddChild s i =

    let child = IHTestNode(Some(this),s,i)

    children <- child::children

    child :>IIndentHandler

  /// This does any remaining processing

  /// for an ongoing node stack,

  /// and returns the root.

  member this.Eol () =

    children <- List.rev children

    match parent with

    | None -> this

    | Some(p) -> p.Eol()

  /// Print the tree.

  member this.Print () =

    if indent>=0 then

      printfn "%s%s" (String(' ',indent)) tag

    children |> List.iter (fun (n:IHTestNode)->n.Print())

  /// IIndentHandler members.

  /// (See IIndentHandler documentation.)

  interface IIndentHandler with

    member this.Add s i =

      children <- List.rev children

      // Note: your parent=null test/exception here.

      parent.Value.AddChild s i 

    member this.Cmp _ i =

      i - indent 

    member this.Pop () =

      children <- List.rev children

      // Note: your parent=null test/exception here.

      parent.Value:>IIndentHandler 

    member this.Push s i =

      this.AddChild s i

// Generate some test data.

let test = 

  seq {

    for i in [0..1] do

      yield String.Format("{0}",i)

      for j in [0..1] do

        yield String.Format(" {0}{1}",i,j)

        for k in [0..3] do

          yield String.Format("   {0}{1}{2}",i,j,k)

  }

//Generate and print a tree.

((Seq.fold 

    IndentOMatic.proc 

    (IHTestNode(None,"root",-1):>IIndentHandler) 

    test):?>IHTestNode).Eol().Print()

printfn ""

printfn "Your breakpoint here."

Python:

# Rudimentary indentation processor.
class IndentOMatic():

    # Converts a string to a string, indent pair.
    @staticmethod
    def __string_to_tag(s):
        i = 0
        l = len(s)
        while i<l:
            if s[i]!=' ': break
            i += 1
        return (s[i:],i)

    # Process a string and indent. 
    @staticmethod
    def __proc0(ih,s,i):
        # Pop the stack, looking for a parent
        # or sibling.
        def __scan_up(ih):
            cmp = ih.cmp(i)
            if cmp<0:
                return __scan_up(ih.pop())
            elif cmp==0:
                return ih
            else:
                # Custom exception here, if required.
                raise Exception("No matching unindent.")
        cmp = ih.cmp(i)
        if cmp<0:
            return IndentOMatic.__proc0(__scan_up(ih),s,i)
        elif cmp==0:
            return ih.add(s,i)
        else:
            return ih.push(s,i)

    # Call to process a string.
    @staticmethod
    def proc(ih,s):
            (t,i) = IndentOMatic.__string_to_tag(s)
            return IndentOMatic.__proc0(ih,t,i)


# Tree node that implements the proper functions.
class IHTestNode ():

  def __init__(self,parent,tag,indent):
      self.parent = parent
      self.tag = tag
      self.indent = indent
      self.children = []

  # Add a child.
  def __add_child(self,s,i):
      child = IHTestNode(self,s,i)
      self.children.append(child)
      return child

  # This does any remaining processing
  # for an ongoing node stack,
  # and returns the root.
  def eol (self):
    if self.parent==None:
        return self
    else:
        return self.parent.eol()

  # Standard overload.
  def __str__(self):
      return self.tag.rjust(self.indent+len(self.tag))

  # Recursive print.
  def print_me(self):
      print(self)
      for child in self.children:
          child.print_me()

  # Adds a sibling.
  def add(self,s,i):
      # Note: your parent=None test/exception here.
      return self.parent.__add_child(s,i)

  # Compares to the current indent level.
  def cmp(self,i):
      return i-self.indent

  # Pops to the parent.
  def pop(self):
      # Note: your parent=None test/exception here.
      return self.parent

  # Pushes a new child.
  def push(self,s,i):
      return self.__add_child(s,i)


# Test.

def test():    
    for i in range(0,2):      
        yield "{0}".format(i)
        for j in range(0,2):     
            yield " {0}{1}".format(i,j)
            for k in range(0,4):      
                yield "   {0}{1}{2}".format(i,j,k)

print("Begin")

ihtn = IHTestNode(None,"Test",-1)

for x in test():
    ihtn = IndentOMatic.proc(ihtn,x)

ihtn = ihtn.eol()

print("End")

ihtn.print_me()

Lua:

-- Note:
-- I'm a newcomer to Lua;
-- I apologize for any bad practices.

-- Note:
-- The way OOP works in Lua is elegant,
-- but can be a little confusing at first.
-- For an explanation, see the chapter 
-- on OOP in "Programming in Lua" by
-- Roberto Ierusalimschy.

-- IndentOMatic class.
IndentOMatic = {

  string_to_tag = function (s)
    local i = 1 -- Lua indexes are one-based.
    local l = s:len()
    while i<=l do
      if s:sub(i,i)~=" " then break end
      i = i+1
    end
    return { tag=s:sub(i,-1), indent=i-1 } 
  end, -- string_to_tag
  
  proc_0 = function (ih,s,i)
    function scan_up (ih)
      local cmp = ih:cmp(i)
      if cmp<0 then
        return scan_up(ih:pop())
      elseif cmp==0 then
        return ih
      else
        -- Custom exception here, if required.
        error("No matching unindent.")
      end
    end -- scan_up
    local cmp = ih:cmp(i)
    if cmp<0 then
      return IndentOMatic.proc_0(scan_up(ih),s,i)
    elseif cmp==0 then
       return ih:add(s,i)
    else
     return ih:push(s,i)
    end
  end, -- proc_0
  
  proc = function (ih,s)
    local ti = IndentOMatic.string_to_tag(s)
    return IndentOMatic.proc_0(ih,ti.tag,ti.indent)
  end
  
} -- IndentOMatic


-- IndentHandler class.
IndentHandler = {

  -- "Instance" constructor.
  new = function (self,p,t,i)
    local o = {}
    o.parent = p
    o.tag = t
    o.indent = i
    o.children = {}
    setmetatable(o,self)
    self.__index = self
    return o
  end, -- new
 
  add_child = function (self,s,i)
    local child = IndentHandler:new(self,s,i)
    self.children[#self.children+1] = child
    return child
  end, -- add_child
  
  eol = function (self)
    if self.parent then
      return self.parent:eol()
    else
      return self
    end
  end, -- eol
  
  print_me = function (self)
    function spaces (i)
      local s = ""
      while i>0 do
         s = s.." "
         i = i-1
      end
      return s
    end
    print(spaces(self.indent)..self.tag)
    for i=1, #self.children do
      self.children[i]:print_me()
    end
  end, -- print_me

  add = function (self,s,i)
    -- Custom parent null check here, if required.
    return self.parent:add_child(s,i)
  end, -- add
  
  cmp = function (self,i)
    return i-self.indent
  end, -- cmp
  
  pop = function (self)
    -- Custom parent null check here, if required.
    return self.parent
  end, -- pop
  
  push = function (self,s,i)
   return self:add_child(s,i)
  end -- push
  
} -- IndentHandler


e = IndentHandler:new(nil,"root",-1)

for i = 0,1 do
  e = IndentOMatic.proc(
        e,string.format("%d",i))
  for j = 0,1 do
    e = IndentOMatic.proc(
          e,string.format(" %d%d",i,j))
    for k = 0,3 do
      e = IndentOMatic.proc(
          e,string.format("   %d%d%d",i,j,k))
    end
  end
end

e = e:eol()
e:print_me()

Ruby:

class IndentOMatic

  def IndentOMatic.string_to_tag (s)
    i = 0
    s.each_char {|x| if x!=' ' then break else i+=1 end}
    [s[i,s.length],i]
  end
  
  def IndentOMatic.scan_up (ih,i)
    cmp = ih.cmp(i)
    if cmp<0 then
      return IndentOMatic.scan_up(ih.pop(),i)
    elsif cmp==0 
      return ih
    else
      raise "No matching unindent."
    end
  end
    
  def IndentOMatic.proc0 (ih, s, i)
    cmp = ih.cmp(i)
    if cmp<0 then
      return IndentOMatic.proc0(
        IndentOMatic.scan_up(ih,i),s,i)
    elif cmp==0
      return ih.add(s,i)
    else
      return ih.push(s,i)
    end
  end

  def IndentOMatic.proc (ih, s)
    t,i = IndentOMatic.string_to_tag(s)
    proc0(ih,t,i)
  end
  
end # IndentOMatic


class IndentProcessor

  def initialize (parent,tag,indent)
    @parent = parent 
    @tag = tag 
    @indent = indent 
    @children = []  
  end
  
  def add_child (s, i)
    child = IndentProcessor.new(self,s,i)
    @children << child
    child
  end
  
  def eol ()
    if @parent==nil then
      return self
    else
      return @parent.eol()
    end
  end
  
  def print_me ()
    if @indent>=0 then
      puts (" "*@indent)<<@tag
    end
    @children.each {|c| c.print_me() }
  end
  
  def add (s, i)
    # Note: your parent=None test/exception here.
    @parent.add_child(s,i)
  end
  
  def cmp (i)
    i-@indent   
  end
  
  def pop ()
    # Note: your parent=None test/exception here.
    @parent
  end
  
  def push (s, i)
    add_child(s,i)
  end

end # IndentProcessor


ih = IndentProcessor.new(nil,"root",-1)

ih = IndentOMatic.proc(ih,"a")
ih = IndentOMatic.proc(ih,"  b")
ih = IndentOMatic.proc(ih,"    c")
ih = IndentOMatic.proc(ih,"    d")
ih = IndentOMatic.proc(ih,"  e")

ih = ih.eol()

ih.print_me()

Significant Whitespace, DSLs, and You (in F#)

Today’s post shows some simple code for teasing out the structure of a text file based on its indentation.

A trend in computer science is for computer languages to rely more on significant whitespace. Of course, that is true of F#, but Python has introduced the concept to an even wider audience. Significant whitespace and structure are also important in the design of domain-specific languages, since these constructs help reduce visual clutter.

But it pays not to be too strict. For example, forcing indentation and other structures to be at specific tab stops is likely to be a source of irritation as well as readability. What is needed is an adaptable system where – if the structure naively looks right, it gets interpreted right by the parser.

The code below presents on part of a toolkit for doing that. It takes input a line at a time, and decides whether each new line is a child at new level of indentation, a sibling of the current level, or represents a “pop” upwards to a parent level. The exact indentation at each level is unimportant, and is set by the first sibling. Pops back upwards must be to a previously encountered level.

Of course, a lot of things are missing. For example, in some languages, individual line indentation is not sufficient; some knowledge of context is required. And the code below is not really packaged very well; in real use, some sort of encapsulation in a class might be more appropriate. And as with any code, it could be refactored and perhaps simplified in a number of ways.

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

(FWIW, the test sample is some actual Python code from a “toy” expert system I wrote to help me learn Python.)

open System

/// Rudimentary indentation processor.

module IndentOMatic =

  // These three functions stand in for 

  // real-world functionality.

  /// Add a sibling item.

  let add s i =       

    printfn ""

    printf "Add : %i %s%s " i (String('-',i)) s

  /// Pop a level.

  let pop () = printf "^"

  /// Push a child item.

  let push s i =

    printfn ""

    printf "Push: %i %s%s " i (String('-',i)) s

  /// Convert a string to a string*int,

  /// where the string is the string minus

  /// leading spaces and the int is the 

  /// number of spaces.

  let private stringToTag (s:string) =

    let rec leading l i (s:string) =

      match i>=l with

      | true -> i

      | _ ->

        match s.Chars(i) with

        | ' ' -> leading l (i+1) s

        | _ -> i

    let i = leading s.Length 0 s

    s.Substring(i),i

  /// Process a string. 

  let rec private proc0 (nl:int list) s i = 

    /// Pop the stack, looking for a parent

    /// or sibling.

    let rec scanUp = function

      | [] -> failwith "Stack underflow."

      | h::t ->

      match i=h with

      | true -> h::t

      | _ ->

      match i>h with

      | true -> failwith "No matching unindent."

      | _ -> 

        pop()

        scanUp t 

    match nl with

    | [] -> failwith "Stack underflow."

    | h::t ->

    match i=h with

    | true -> 

      add s i

      nl

    | _ -> 

      match i>h with

      | true -> 

        push s i

        i::nl

      | false -> proc0 (scanUp nl) s i

  /// Call to process a string. 

  let proc nl s =

    let t,i = stringToTag s

    proc0 nl t i

// Test it.

let test = 

  [

    // Some Python code from a "toy" 

    // expert system.

    "class Not():";

    "    def __init__(self,rule):";

    "        self.rule = rule";

    "    def prove(self,tryProve):";

    "        p = self.rule.prove(tryProve)";

    "        if p==None:";

    "            return p";

    "        else:";

    "            return not p";

  ]

let x = Seq.fold IndentOMatic.proc [-1] test

printfn ""

printfn ""

printfn "Your breakpoint here."

The output looks something like this:

Push: 0 class Not():

Push: 4 ----def __init__(self,rule):

Push: 8 --------self.rule = rule ^

Add : 4 ----def prove(self,tryProve):

Push: 8 --------p = self.rule.prove(tryProve)

Add : 8 --------if p==None:

Push: 12 ------------return p ^

Add : 8 --------else:

Push: 12 ------------return not p

Your breakpoint here.

Oops! Correction to Post Dated August 8, 2010

Oops! I found a couple of bugs in the code listed in the blog post titled: Segment Tree in F#. The bugs are in the "findCollect" and "findIter" functions, and they're really rather glaringly obvious (essentially different versions of the same bug). It looks like a “my-brain-was-out-to-lunch” error as I was transcribing the algorithm either from my head or from pseudo-code. In any case, it can be caught by a simple unit test or even code review, so I’m embarrassed that it got into the blog. My humblest apologies.

In order to avoid repeating the error, I’m thoroughly testing my correction, and I’ll post it when that testing is done. I’ll also post a better test example (that would have revealed this error).

In the meantime, the fix is quite simple, so readers may want to try figuring it out on their own. (Hint: try searching for values completely outside the range of the tree. This will force the bug to occur.)

-Neil

My Dinner with Haskell

It’s impossible to go very far into either the F# world or the world of domain-specific languages (DSLs) without encountering Haskell. It seems like all the F# gurus are also Haskell gurus, or at least Haskell aficionados, and a lot of people use Haskell for prototyping new languages (including DSLs). Any search for materials on F# or DSLs likewise leads to information on Haskell.

So I decided to learn me some Haskell.

The first thing I did was to get a working build of the GHC (Glasgow Haskell Compiler) by following the appropriate links at the official Haskell site. Next, I found some learning materials, including Real-World Haskell, Learn You a Haskell for Great Good, Haskell Wikibook, Planet Haskell, and Erik Meijer's excellent Channel 9 series. (The latter is worth watching for the shirts alone!)

And then, a couple of days ago, I got to work learning. And so far…

…so good. This is a really fun language, and fairly easy to learn if you already have some experience in F#. At least, knowing F# gets you past the initial strangeness of concepts like currying, pattern matching, etc. In fact, knowing F# is a tiny bit of an impediment because the syntax is so similar, the differences are difficult to remember. But on balance, knowing F# has helped a bunch. The two languages aren’t exactly siblings, but they are cousins, and I think learning the more formal environment of Haskell will help me with the more pragmatic environment of F#.

In order to illustrate the two together, below I present “A tiny corner of Lisp…” in both F# and in Haskell. This being a little fragment of Lisp functionality coded as identically as possible in the two languages. As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk. (And since I don’t yet have anything that can syntax highlight Haskell, I deliberately did not syntax highlight the F#.)

// A tiny corner of Lisp in F#.

type Node =
  | Atom of string
  | Cons of Node*Node
  | Nil

let car = function
  | Cons(h,_) -> h
  | _ -> failwith "Invalid 'car' target."

let cdr = function
  | Cons(_,t) -> t
  | _ -> failwith "Invalid 'cdr' target."

let rec append nCar nCdr =
  match nCar with
  | Cons(h,t) -> Cons(h, append t nCdr)
  | Nil -> nCdr
  | _ -> failwith "Invalid 'append' target(s)."


// Examples.

let a0 = Atom "a" // a
let c0 = Cons(a0,(Cons((Atom "b"),Nil))) // (a b)
let c1 = append c0 c0 // (a b a b)
let c2 = append c1 a0 // (a b a b . a)

-- A tiny corner of Lisp in Haskell.

data Node = Atom String
          | Cons Node Node
          | Nil
    deriving (Show)

car :: Node -> Node
car (Cons h _) = h
car _ = error "Invalid 'car' target."

cdr :: Node -> Node
cdr (Cons _ t) = t
cdr _ = error "Invalid 'cdr' target."

append :: Node -> Node -> Node
append (Cons h t) nCdr = (Cons h (append t nCdr))
append Nil nCdr = nCdr 
append _ _ = error "Invalid 'append' target(s)."


-- Examples.

a0 = Atom "a" -- a
c0 = Cons a0 (Cons (Atom "b") Nil) -- (a b)
c1 = append c0 c0 -- (a b a b)
c2 = append c1 a0 -- (a b a b . a)

So get out there and learn you a Haskell for great good!

-Neil

Project Euler #1 - One Problem, Three Solutions, Seven Languages

I haven’t posted here in a long time, and I apologize for that. No particular reason, but all good: programming in F#, learning lots of new programming stuff, enjoying the fall and winter holiday season (including hand-making some Christmas gifts), etc.

As I mentioned, one of the things I’ve been doing is learning new programming skills. I ignored F# during its early history, and the past year has shown me that was a mistake. So I decided to take a look at some of the other things I’ve been ignoring. That led me into various spots, including: Lua, Python, Ruby, MongoDB, MySQL, PostgresQL, Silverlight 4, SVN, Haskell, NetBeans, revisiting Scheme, the world of Visual Studio extensions, etc.

There’s a popular programming book by Bruce Tate, titled “Seven Languages in Seven Weeks.” In that spirit, I’d like to present something similar here: three views of Project Euler, problem number one, in seven languages. Some of these languages I’ve worked in for a long time; some of them I’ve just learned, but here goes. (As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

First is F#. Of all the languages listed here, F# is my favorite. Not by a wide margin, perhaps, but my favorite nonetheless. I think this is because of the vision of its creators: to build a language based on thoughtful consideration of all that has come before, both academic and pragmatic. At this, it succeeds brilliantly. (And no, Don Syme did not pay me to say this, lol.)

// Naive Implementation,

// based on problem statement.

// Illustrates aggregate operators

// and pipes.

let euler_1_naive a b bound =

  seq {1..bound-1} 

  |> Seq.filter (fun i->((i%a=0)||(i%b=0)))

  |> Seq.sum

// Sums stepped ranges.

// Illustrates aggregate operators

// and pipes.

let euler_1_iteration a b bound =

  (seq {a..a..bound-1} |> Seq.sum)+

  (seq {b..b..bound-1} |> Seq.sum)-

  (seq {a*b..a*b..bound-1} |> Seq.sum)

// Numeric (one possible factoring).

// Illustrates the use of nested functions,

// closures and immutable parameters.

let euler_1_numeric a b bound =

  let b1 = bound-1

  let f n =

    let c = b1/n

    c*(c+1)/2*n

    (f a)+(f b)-(f (a*b))

Next is Python. Python is an interesting language; it embodies a lot of characteristics that make it fun and easy to program in: orthogonality, lack of syntactic fluff, etc. On the other hand, it is a very businesslike language with a lot of excellent libraries available. If I were Java and C#, I’d watch my back.

# Python 3.1.3 and NetBeans w/Python plug-in.

def euler_1_naive (a,b,bound):
    """Naive Implementation,
       based on problem statement.
       Illustrates comprehensions
       and implicit booleans."""
    return sum(
      i for i in range(1,bound)
        if (not ((i%a) and (i%b))))


def euler_1_iteration (a,b,bound):
    """Sums stepped ranges.
       Illustrates aggregate operators."""
    return sum(range(a,bound,a))+\
           sum(range(b,bound,b))-\
           sum(range(a*b,bound,a*b))


def euler_1_numeric (a,b,bound):
    """Numeric (one possible factoring).
       Illustrates the use of nested functions
       and closures."""
    bound -= 1
    def f (n):
        """Compute sum of n-divisible."""
        c = int(bound/n)
        return int(c*(c+1)/2)*n
    return f(a)+f(b)-f(a*b)

And here is Ruby. What to say about Ruby? Superficially, it strikes one as incoherent and arbitrary. But a closer look shows this to be a mistake. What looked like incoherence and randomness is really richness and a wonderful idiosyncrasy. Ruby is a complex, Raku bowl of a language, which reflects the mind of its creator, Yukihiro Matsumoto, and records all the incidents and accidents of its history. Of all the languages here, it is the one that draws the most passion from the programmers who use it, and I can see why. There’s a lot to be said for a language in which you can do something five times by coding “5.times {…}”

# Ruby 1.9.2 and NetBeans w/Ruby plug-in.

# Naive Implementation,
# based on problem statement.
# Illustrates filtering.
def euler_1_naive (a,b,bound)
  ((0...bound).find_all{
      |i|(i%a==0)||(i%b==0)}).reduce(:+)
end


# Sums stepped ranges.
# Illustrates aggregate operators.
def euler_1_iteration (a,b,bound)
  (a...bound).step(a).reduce(:+)+
  (b...bound).step(b).reduce(:+)-
  (a*b...bound).step(a*b).reduce(:+)
end


# Numeric (one possible factoring).
# Illustrates the use of lambdas
# and closures."""
def euler_1_numeric (a,b,bound)
  bound -= 1
  #Compute sum of n-divisible.
  f = lambda {|n|
    c = bound/n
    c*(c+1)/2*n
  }
  f.call(a)+f.call(b)-f.call(a*b)
end

Lua, like Ruby and F#, reflects the visions of its creators. Like Python, it is simple and orthogonal. So simple and orthogonal, in fact, that it has only one non-value type: an associative table. Everything else – objects, lists, arrays, stacks, etc. – must be built using those tables. Lua’s simplicity and speed, coupled with the fact that it is implemented in a highly portable subset of C, make Lua a great choice for new processors, small machines, embedded scripting and similar environments. Think of it as a FORTH for the new millennium. I wish GPU shader languages looked like Lua.

function euler1Naive (a,b,bound)
  acc = 0
  for i=0,bound-1 do
    if (i%3==0) or (i%5==0) then 
      acc = acc+i 
    end
  end
  return acc
end


function euler1Iterative (a,b,bound)
  bound = bound-1
  function f(n) 
    acc = 0
    for i=n,bound,n do
      acc = acc+i
    end
    return acc
  end
  return f(a)+f(b)-f(a*b)
end


function euler1Numeric (a,b,bound)
  bound = bound-1
  function f(n) 
    c = math.floor(bound/n)
    return math.floor(c*(c+1)/2)*n
  end
  return f(a)+f(b)-f(a*b)
end

Good old Java, C#, and C/C++; the three tireless workhorses of modern computing. When programmed procedurally, all three are so similar that I will show only a single example: the naïve implementation in Java. Of course, the reasons why a programmer might prefer one of these languages over the others are real and important, but are simply beyond the scope of a snippet. In most cases it has to do with platform, ecosystem, and considerations of speed vs. safety. (In this example, and in the C# case below, I have omitted the enclosing class definition for brevity.)

public static int euler_1_naive (
    int a,
    int b,
    int bound)
{
    int sum = 0;
    for (int i=1;i<bound;i++)
        if (((i%a)==0)||((i%b)==0))
           sum += i;
    return sum;
}

Many procedural languages are growing to become more functional. To illustrate that, here is an example in C#, which makes us of a locally defined delegate.

// C# 4.0 and Visual Studio 2010.

// Sums stepped ranges.

public static int Euler_1_iteration (

  int a,

  int b,

  int bound) 

{

  Func<int,int,int> f = 

    (sum,n) => {

      for (int i=n;i<bound;i+=n) 

        sum+=i;

      return sum; };

  return f(f(-f(0,a*b),b),a);

}

C++0X also adds functional features and other modern constructs to the C++ language. The example below shows the definition of a lambda and the use of the “auto” keyword (a great boon to readability). The lambda syntax appears a bit arcane and robotic, but then, everything about C and C++ is a bit arcane and robot. *Which is exactly what programmers like about it.* (And if you really, *really* like that kind of thing, you might want to try FORTH.)

// Numeric (one possible factoring).

// Illustrates the use of lambdas, auto

// and closures.

int euler_1_numeric (

  int a,

  int b,

  int bound)

{

  bound -= 1;

  auto f = [bound] (int n) -> int 

  { 

    int c = bound / n;

    return c*(c+1)/2*n;

  };

  return f(a)+f(b)-f(a*b);

}

Last, here are a couple of examples that use template-based metaprogramming in C++. In case you haven’t encountered that before, it’s basically a way of tricking the compiler into running a program at *compile time* that leaves a correct value or structure in the compiled code. In these examples, the correct Project Euler #1 value is left in the enumeration value RET. Template-based metaprogramming can be a bit hard to wrap your mind around at first, and the examples here are not especially reflective of how it might be useful in the real world. Suffice to say that it can be a powerful technique for creating complex data structures and increasing runtime efficiency (for example, by permitting constant folding and similar techniques in ways that go beyond even optimizing compilers).

// Template metaprogram 1.

// Sums stepped ranges.

// Illustrates partial template

// instantiation.

template<int i, int acc, int n>

struct SRSum

{

  enum { 

    RET=SRSum<i,acc+i,n-1>::RET+acc 

  };

};

template<int i, int acc>

struct SRSum<i,acc,0>

{

  enum { RET=acc };

};

template<int a, int b, int bound> 

struct Euler1Iterate

{

  enum { 

    RET=(SRSum<a,0,(bound-1)/a>::RET)+ 

        (SRSum<b,0,(bound-1)/b>::RET)-

        (SRSum<(a*b),0,(bound-1)/(a*b)>::RET)

  };

};

// Template metaprogram 2.

// Numeric.

template<int n, int bound>

struct NSum 

{

private: enum { C=(bound-1)/n };

public: enum { RET=C*(C+1)/2*n };

};

template<int a, int b, int bound> 

struct Euler1Numeric

{

  enum { 

    RET=NSum<a,bound>::RET+ 

        NSum<b,bound>::RET-

        NSum<(a*b),bound>::RET 

  };

};

// Test both.

int _tmain(int argc, _TCHAR* argv[])

{

  return (Euler1Iterate<3,5,1000>::RET+

          Euler1Numeric<3,5,1000>::RET)/2;

}

Finally, a short word about benchmarks. The compiled versions (C/C++/C#/Java/F#) all ran a lot faster than the scripting language versions (Lua/Python/Ruby). That was no surprise. What was surprising, however, was just how fast the scripted versions were – even given the startup time. Plenty fast enough for almost anything other than data or numeric intensive programs, and certainly fast enough to handle most user tasks. Of the three scripting languages, Lua lived up to its reputation as the fastest, but Ruby and Python weren’t far behind (Ruby was slightly faster than Python).

And that’s it: one problem, three solutions, seven languages.

-Neil

p.s. I apologize for not syntax highlighting several of the samples. I have a VS2008 add-in that will do it, but I don’t know how to do it in NetBeans.

If Programming Languages Were Television Shows

I’m working on a more substantial post that compares several programming languages on a single problem. In the meantime, I give you something frivolous; my take on…

If Programming Languages Were Television Shows

F# – Mythbusters. We don't just explain the functional programming myths, we put them to the test. (Am I missing an eyebrow?)

Haskell – The Saturday-afternoon calculus course from the local community college on the public access channel.

Fortran – An old movie, a perennial favorite with classic actors, and the credits arranged in a matrix.

Java – Something on a business channel with a scrolling stock ticker and announcers who wear kakis and blue button-downs.

C# – Just like Java, but with fancier graphics on the stock ticker and announcers who wear power ties.

Python – Financial advice for the small investor. It seems sound, but which way will the market trend?

C/C++ – Some PBS hippie show about growing and canning your own vegetables. Who needs garbage collection when you can compost?

Lua – A late-night foreign art film in black and white by a visionary director. Deep, but will it find enough sponsors to go prime time?

Ruby – Star Trek. Geeky, gadgety, and tough on newcomers, but a fiercely loyal fan base will keep this series in syndication for a while. Beam me up, Matz!

FORTH – The Woodwright’s Shop. Watch a guy make handmade furniture using handmade tools. Be careful of splinters.

Assembly Language - A test pattern.

COBOL – Something on the radio your parents or grandparents used to listen to.

(Sorry, COBOL geeks, I couldn't resist that last one, lol. We love you anyway.)

-Neil