From Wikipedia (2010-02-24):

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. It was created by A. O. L. Atkin and Daniel J. Bernstein.

This is my translation of the pseudocode to f#:

// Generates a list of all primes below limit
let sieveOfAtkin limit =
    // initialize the sieve
    let sieve = Array.create (limit + 1) false
    // put in candidate primes: 
    // integers which have an odd number of
    // representations by certain quadratic forms
    let inline invCand n pred =
        if n < limit && pred then sieve.[n] <- not sieve.[n] 
    let sqrtLimit = int (sqrt (float limit))
    for x = 1 to sqrtLimit do
        for y = 1 to sqrtLimit do
            let xPow2 = x * x
            let yPow2 = y * y
            let n = 4 * xPow2 + yPow2 in invCand n (let m = n % 12 in m = 1 || m = 5)
            let n = 3 * xPow2 + yPow2 in invCand n (n % 12 = 7)
            let n = 3 * xPow2 - yPow2 in invCand n (x > y && n % 12 = 11)
    // eliminate composites by sieving
    let rec eliminate n =
        if n <= sqrtLimit 
        then if sieve.[n]
             then let nPow2 = n * n
                  for k in nPow2 .. nPow2 .. limit do
                      Array.set sieve k false
             eliminate (n + 2)
    eliminate 5
    // Generate list from the sieve (backwards)
    let rec generateList acc n =
        if n >= 5 then generateList (if sieve.[n] then n :: acc else acc) (n - 1)
        else acc
    2 :: 3 :: (generateList [] limit)

On my MacBook Pro 2.66 GHz Intel Core 2 Duo it generates all primes below 10.000.000 in 557 milliseconds:

> #time;;

--> Timing now on

> sieveOfAtkin 10000000;;
Real: 00:00:00.557, CPU: 00:00:00.471, GC gen0: 0
val it : int list =
  [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
   157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
   239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
   331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
   421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
   509; 521; 523; 541; ...] 

A new version (v0.3) is now available at http://code.google.com/p/fsharp-tmbundle/. 

The grammar now recognize "(*)", "let rec" and "let inline".

På samma sätt som alla C#-programmerare idag vet att de egentligen för länge sedan borde ha gått över till F# vet Java-programmerare att de borde gått över till Scala eller ännu hellre OCaml-Java eller liknande.

Tyvärr finns fortfarande programmerare som - av olika skäl - ännu inte haft möjligheten att helt och fullt byta upp sig. Dessa stackare söker givetvis efter stöd av olika former och vi som följer frågeställningarna som dyker upp på t.ex. stackoverflow.com vet att frågan om FP-bibliotek för dessa språk är återkommande.

För de stackars C#-programmerarna finns idag följande hjälp att tillgå:

• FpSharp - This library provides functional programming abstrations for .NET and C# including map, fold, filter functions for ordinary .NET collections, the option data type, a lazy type, a functional list type, lazy functional lists, and more.
• Functional C# - This is a set of libraries to demonstrate functional programming aspects as implemented in C#. This is not to imply that C# is a functional language, but can implement some of the aspects of it. This project is to demonstrate some of those techniques
• Elevate - Elevate is an easy to pick up library containing things you wish were in the BCL. Use one component or many. Contribute your own utilities. Help us make Boost for .NET.
  Elevate is developed in C#. Currently, we're focused on adding concepts from functional languages.
• Kinet - Kinet is a library for C# that provides useful data structures and algorithms for general purpose programming. It is somewhat inspired by the Functional Java project and the Haskell programming language.
• Functional .Net - C# 3.0 and VB 9 provide strong elements of functional programming in mainstream languages (lambda expressions, extension methods, a weak version of type inference for local variables, etc.)
  The library support for them, however, is pretty much limited to IEnumerable<T> and LINQ. This project is intended to extend it by providing additional data structures, algorithms, and extension methods.
• Sasa - Sasa is a collection of useful C# extensions to the standard library. There are tuples, Linq extensions, full MIME e-mail parsing, a POP3 client, array combinators, compact serialization, purely functional lists, lazy types, and more.

Luca Bolognese har också (utan att mig veterligen paketera sin kod) skrivit en läsvärd artikelserien i ämnet: "A C# library to write functional code"(Background, Tuples, Records, Type Unions och The Match operator).

På Java-sidan finns också vissa möjligheter:

• Functional Java - Functional Java is an open source library that aims to prepare the Java programming language for the inclusion of closures. It also serves as a platform for learning functional programming concepts [...]
• FunctionalJ - FunctionalJ is a library which makes it easy to use functional programming constructs in Java code.
• Jambda - Jambda is an attempt to provide the Java(TM) world with tools and concepts from functional programming (FP). (Här har jag själv haft viss inblanding)
• LambdaJ - Manipulate collections in a pseudo-functional and statically typed way.

Journal of Functional Programming

“Journal of Functional Programming is the only journal devoted solely to the design, implementation, and application of functional programming languages, spanning the range from mathematical theory to industrial practice. Topics covered include functional languages and extensions, implementation techniques, reasoning and proof, program transformation and synthesis, type systems, type theory, language-based security, memory management, parallelism and applications. The journal is of interest to computer scientists, software engineers, programming language researchers and mathematicians interested in the logical foundations of programming.”

Mycket hög kvalitet från Cambrigde Journals under redaktörerna Matthias Felleisen och Xavier Leroy. Kostar pengar.

The F#.NET Journal

Artiklar om F# av Jon Harrop (författaren till bl.a “F# for Scientists”). Ett axplock:

• “The Essence of Functional Programming”
• “Exploiting Tail Recursion”
• “Sequence expressions and comprehensions”
• “Parser combinators”
• “Implementing a simple Ray Tracer”

The OCaml Journal

Till viss del samma artiklar som i F# Journal fast utifrån ett OCaml-perspektiv. Kostar pengar.

The Monad.Reader

“The Monad.Reader is an electronic magazine about all things Haskell. It is less formal than a journal, but more enduring than a wiki-page or blog post. There have been a wide variety of articles, including: exciting code fragments, intriguing puzzles, book reviews, tutorials, and even half-baked research ideas.”

Mycket läsvärd och gratis (även källkoden finns tillgänglig via darcs-repon). I senaste numret (#13) återfinns bl.a. den mycket läsvärda “The Typeclassopedia” av Brent Yorgey.

Ola Bini på ThoughtWorks postade igår om att han portat sitt Ioke från JVM till CLR. Han passade på att skriva en serie poster om erfarenheterna från portingen (Some .Net Reflections, .Net and Interface madness och Opinions on C# and .Net) där det framgår att han delvis använt sig av F# i arbetet (Opinions on F#). 

Då jag ofta själv lekt med tanken på att skriva ett språk i F# googlade jag vidare lite på ämnet och stötte på artikelserien “Writing a pi-calculus compiler in F#” (π-calculus) av Dominic Cooney.

• Part I
• Part II: Modelling a web service in pi-calculus
• Part III: Making echo work
• Part IV: From calculus to compiler
• Part V: Parser redux and runtime stubs
• Part VI: The code generator
• Part VII: Finishing touches to the compiler and runtime
• Part VIII

Mycket spännande.

Since my F# grammar and the simple support for the F# interactive (fsi) seems to be quite popular I have now created a project for it on Google Code:

   http://code.google.com/p/fsharp-tmbundle/

I will publish instructions on how to use it and its dependencies there.

Efter min förra post om REPL under MacOSX har jag provat ytterligare ett par alternativ och nu kommit fram till att TextMate nog trots allt är det bästa.

Med hjälp av följande kommando-script bundet till Enter-tangenten (och Input satt till Selected Text or Line) har jag precis det REPL-stöd jag vill ha.

EXPR="$(cat | sed 's/\\/\\\\/g' | sed 's/\"/\\\"/g')" 

export SHELL_NAME=${SHELL_NAME:="FSharp Interactive"}
export SHELL_INTERPRETER=${SHELL_INTERPRETER:="fsi"}

osascript << END
tell application "iTerm"
    if (count (every session of every terminal)) = 0 then
        make new terminal
    end if
    tell the first terminal
        if not (exists session named "$SHELL_NAME") then
            launch session "Default"
            tell the current session
                set name to "$SHELL_NAME"
                write text "$SHELL_INTERPRETER"
            end tell
        end if
        select session named "$SHELL_NAME"
        tell session named "$SHELL_NAME"
            write text "$EXPR" & ";;"
        end tell
    end tell
end tell
END

Det här scriptet är skrivet för F Sharp och dess “F# Interactive” (fsi) med kan med några små justeringar lätt användas för Haskell (ghci), OCaml (ocaml), Lisp, Scala eller liknande.

Edit: Jag använder en något modifierad version av den “F# language grammar” som återfinns i SVN-repot för TextMate bundles.