Another Project

I wanted to let you now about another project that I’ve been working on (which explains why I haven’t posted for a while and why it may be quite a while before I start posting regularly again).

I’ve recently started the site fsharp4u.com. F# may not have the grassroots community support that other languages enjoy. However, it is a solid language that is growing in popularity. There appears to be a need for easy access tutorials, and F# for You is designed to fill that gap. While Microsoft has provided several sites and tools, there is a lack of basic information on F# from an independent perspective.

Hopefully this new endeavor will be a positive contribution to both the F# community and the larger functional programming community.

CUFP 2013

CUFP 2013 was in September, but I’m just now getting around to watching the talks. In case you’re not familiar with CUFP (Commercial Users of Functional Programming), it is a conference not of academics, but of practitioners working with functional programming in industry. Here is a link to the talks this year. Click on any of them to get an abstract as well as slides and full video for most.

http://cufp.org/conference/schedule/2013

Here are a few that I thought were particularly noteworthy along with some of the key points or topics I thought were interesting.

Anthony Molinaro, OpenX: Introducing Erlang to OpenX
http://cufp.org/conference/sessions/2013/anthony-molinaro-openx-introducing-erlang-openx

  • Many important concepts of modern SW development work well in functional programming in general and Erlang in particular
    • Fault tolerance
    • Scalable concurrency
    • Loosely coupled, single purpose components
    • Domain specific languages
  • Showcasing the power of FP is essential for buy in
  • Not many developers have FP experience, must be willing to train

Jafar Husain, Netflix: End to end Reactive Programming
http://cufp.org/conference/sessions/2013/jafar-husain-netflix-end-end-reactive-programming

  • Functional Reactive Programming, fundamentally different way of thinking
  • Database queries and mouse drags can be seen as following the same design pattern
  • Combination Iterator/Observer semantics
  • Overcoming resistance to functional programming requires very good soft skills

Sam Ritchie, Twitter Inc: Realtime MapReduce at Twitter
http://cufp.org/conference/sessions/2013/sam-ritchie-twitter-inc-realtime-mapreduce-twitter

  • Wrote open source DSL for real-time parallelization
  • Functional, focused heavily on very simple monoids

Jeff Epstein, Parallel Scientific: Building scalable, high-availability distributed systems in Haskell
http://cufp.org/conference/sessions/2013/jeff-epstein-parallel-scientific-building-scalable

  • Found Haskell’s laziness to be problematic in their distributed environment
  • Cloud Haskell is a library for distributed concurrency similar to Erlang’s concurrency model

Clojure-conj 2013

This is just a quick post about the upcoming Clojure/conj 2013 which will be held in Washington DC on November 14-16. It’s less than a week away, and as of now it appears to be mostly sold out. There is a wait list for late registration, but that’s about it.

http://clojure-conj.org/

Even if you can’t make the conference (or can’t get in!), it is interesting and informative to take a look at the speaker list as well as the schedule of talks. There are training sessions that also appear to be sold out, but the agenda is worth glancing at.

http://conjtraining.eventbrite.com/

Also note that the Scheme 2013 workshop is co-located with Clojure/conj this year. It appears that the Scheme workshop is not sold out and is very reasonably priced.

http://webyrd.net/scheme-2013/

Review of Functional Languages

This post concludes my series on comparative functional languages. I’ve provided a brief introduction, a comparative description, code samples, and an implementation of the same small problem for the following functional languages:

Though my selection of languages may not match what others would have chosen, I was very deliberate in determining which to cover. I’ve provided a modern and relatively popular language in each of the major traditional functional families. Hence my inclusion of Haskell, F#, Erlang, and Clojure.

I could not leave out Scala. It is a pragmatic and comprehensive yet gentle bridge from OO to functional programming. In my opinion, Scala really does accomplish what it has set out to do–bring all the best ideas in all the major paradigms together under one roof. The question, however, is whether all these ideas can get along with each other in large software systems of various application domains. Time will tell.

R is not often grouped together with the others, but it is as worthy of inclusion as Scala or F#. Since data science is becoming so prevalent and as its use in software systems becomes ubiquitous, I anticipate many software engineers frantically attempting to learn R in the future. Many will be coming from OO and will be perplexed by the functional concepts which are pervasive in R.

Other languages that I should mention but will not cover predate most of the languages that I did cover. Some of these are still in extensive use and are very solid and powerful. These include following (see the associated link for more info):

Common Lisp – http://www.clisp.org/
Scheme – http://schemers.org/
OCaml – http://ocaml.org/
Standard ML (SML) – http://www.lfcs.inf.ed.ac.uk/software/ML/

Another major effort in functional programming is the attempt to bring it into Java:

Java 8 Lambdas – http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html

I won’t mention the many smaller and possibly up and coming functional languages. I find it impossible to know which if any of these will grow to the prominence of the other languages I’ve mentioned. There are also many languages in specific domains that use the functional paradigm which I will also not mention here.

Intro to R

Continuing with my series on comparative functional languages, today I’ll be discussing R. I’ll provide an overview of the language plus some code samples written in R.

You may be wondering why I’m including R in my series on functional languages. While R may not always be included in the FP community, it is heavily influenced by functional languages. It has a distinctly functional flavor, and it can be difficult for imperative programmers to transition to R for this reason. R offers the standard features available in functional languages such as higher order functions and closures, plus basic facilities equivalent to mapping, filtering, etc.

Furthermore, R is quickly becoming (has already become?) the language of choice for data science. Likewise, data science is quickly becoming a must-know technical area used in today’s intelligent and predictive systems.

Background

R is a GNU project providing statistical computing and graphical output. It’s roots are in the S language developed at Bell Labs.

R has an interpreter and many users may simply interact with R mostly as an application. However, it is a fully feature programming language as well. Whether or not it can be (or become) a general purpose programming language is not entirely clear to me. However, as data science grows in importance, we may find that R’s purpose becomes so general that the discussion may be overcome by events.

Comparative Description

  • Paradigms: Functional, Object Oriented, and Data Oriented
  • Platform: Most (interpreters available on most platforms)
  • Typing: Weak and dynamic (for the most part)
  • Evaluation: Eager with support for parallel

Syntax Highlights

To give you a feel for the flavor of R’s syntax, I have some simple source code that represents donations to charity accounts. In each section below, I demonstrate one or more basic functional programming concepts (noted in the comments).

# tuple
newAccount <- function(name) list(name,0)
give <- function(charity) list(charity[[1]], charity[[2]]+100)

# apply (map)
donate <- function(charities) sapply(charities, give)

# local function
donate2 <- function(charities) {
  give2 <- function(charity) list(charity[[1]], charity[[2]]+100)
  sapply(charities, give2)}

# anonymous function
donate3 <- function(charities) {
  sapply(charities, function(x) list(x[[1]], x[[2]]+100))}

# filtered sublist based on boolean function
# complement using -
donate4 <- function(charities) {
  most <- function(x) x[[1]]=="most deserving"
  givemost <- function(x) list(x[[1]], x[[2]]+500)
  s <- sapply(charities[most(charities)], givemost)
  s <- c(s, sapply(charities[-most(charities)], give))
  return (s)}

Some Unique Aspects

The most obviously unique aspect of R is its data orientation. Many of the facilities for processing and analyzing data are likely available in open source modules for some of the other functional languages. However, in R mathematical and statistical functions are built in. Furthermore, various kinds of graphical representations of statistics and mathematics are built into the language since visualization is an important area of data science.

The basics of vectors and matrices, the bread and butter of R, demonstrate its unique data orientation. In R there are (almost) no scalars. Standard operations such addition and multiplication are vector based and produce a new vector that holds the result of element wise operations. Matrix mathematics is built in to the R language as are various kinds of calculus operations and other numerical analysis. Data frames and factors are two other R concepts that make working with data even more convenient.

A Simple Real-World Example

Here I will implement a simplified problem relevant for packet processing which might be useful for applications such as routers, firewalls, intrusion detection systems, etc. It is a basic signature matching program, and you can follow what I’m doing from the code and comments.

# The list of test packets
ids <- c(0, 1, 2, 3)
contents <- c("01234", "56789", "01289", "34567")
session <- data.frame(ids, contents)

# Return only the IDs from a list of matching packets
find_matching_ids <- function(signature, packets)
  find_matching_packets(signature, packets)[1]

# Find packets that match the signature
find_matching_packets <- function(signature, packets)
  packets[grep(signature, packets[,2]),]

# Main program driver
cat("Enter malware signature:\n")
malware <- readline()
cat("Matching packet IDs:\n")
badIds <- find_matching_ids(malware, session)
print(badIds)

To Learn More

Main Website (Download R, plus access lots of other good stuff)
http://www.r-project.org/

An Introduction to R (Basic Manual)
http://cran.r-project.org/doc/manuals/R-intro.html

The Art of R Programming (Comprehensive book)
http://nostarch.com/artofr.htm

R-devel (Discussion)
http://stat.ethz.ch/pipermail/r-devel/

Intro to Clojure

Continuing with my series on comparative functional languages, today I’ll be discussing Clojure. I’ll provide an overview of the language plus some code samples written in Clojure. As a dialect of Lisp, Clojure provides all the benefits and simplicity of a tried and true functional language. But Clojure is distinctly modern and pragmatic. It compiles to Java byte code and is interoperable with Java.

I find Lisps to be somewhat polarizing. For those who understand and enjoy the power and simplicity, Lisps are the culmination of programming. For others who can’t get past all the parentheses and who would like more syntactic sugar for ease of use, Lisps are ugly and unfriendly. Clojure does add some syntactic sugar but is also true to the Lisp core. It is not clear to me whether the masses will appreciate the flexibility of Clojure or whether they will find the concepts too confusing or abstract and opt for something else.

Background

Clojure was started entirely by Rich Hickey. After spending considerable time developing the language, he released it to the community in 2007. It is one of the youngest of the major modern functional languages.

Clojure, true to its Lisp upbringing, embraces the idea of extreme flexibility and providing the ability to write your own language using the language (and hence a solid candidate for creating a DSL). Lispers often say that “code is data”, and the possibilities for fiddling with code programmatically in Clojure are sometimes mind boggling (which is good in some ways and perhaps not so much in others).

Comparative Description

  • Paradigms: Mostly functional, with some OO sprinkled here and there
  • Platform: All (compiles to JVM byte code)
  • Typing: Strong and dynamic
  • Evaluation: Eager with support for lazy and parallel

Syntax Highlights

To give you a feel for the flavor of Clojure’s syntax, I have some simple source code that represents donations to charity accounts. In each section below, I demonstrate one or more basic functional programming concepts (noted in the comments).

; function definition
; vector
(defn newAccount [name]
  [name 0])
(defn give [[name amount]]
 [name (+ 100 amount)])

; map
(defn donate [charities]
  (map give charities))

; local function
(defn donate2 [charities]
  (let [give2 (fn [[name amount]] [name (+ 100 amount)])]
    (map give2 charities)))

; anonymous function
(defn donate3 [charities]
  (map
     (fn [[name amount]] [name (+ 100 amount)])
     charities))

; pattern matching
(defn donate4 [charities]
  (let [gift (fn [name]
                 (case name
                  "most deserving" 500
                  "more deserving" 300
                  100))]
    (map
       (fn [[name amount]] [name (+ (gift name) amount)])
       charities)))

Some Unique Aspects

The most obvious unique aspect of Clojure when compared to other Lisps is its integration with Java. Java classes can be used in Clojure, and Clojure compiles to Java byte code. Furthermore, Clojure is somewhat unique when compared to Java itself. Clojure’s proxy concept provides very dynamic behavior, allowing for run time behavior implementation.

Like other Lisps, Clojure provides signficant flexibility in defining new language constructs through macros. Macros are often (but not always) used in conjunction with quoting and unquoting which treats arbitrary code as literals at compile time rather than functions at run time (quote) then ensures evaluation of the code after some manipulation (unquoting).

A Simple Real-World Example

Here I will implement a simplified problem relevant for packet processing which might be useful for applications such as routers, firewalls, intrusion detection systems, etc. It is a basic signature matching program, and you can follow what I’m doing from the code and comments.

; Find packets that match the signature
(defn find_matching_packets [signature packets]
  (let [has_substr (fn [[id contents]]
        (not= nil (re-find (re-pattern signature) contents)))]
    (filter has_substr packets)))

; Return only the IDs from a list of matching packets
(defn find_matching_ids [signature packets]
  (let [ids (find_matching_packets signature packets)
        fst (fn [[id contents]] contents)]
    (map fst ids)))

; The list of test packets
(def session [[0 "01234"]
              [1 "56789"]
              [2 "01289"]
              [3 "34567"]])

; Main program driver
(println "Enter malware signature: ")
(let [malware (read-line)]
  (println "Matching packet IDs:")
  (let [ids (find_matching_ids malware session)]
    (if (= [] ids) "None" ids)))

To Learn More

Main Website (Download Clojure, plus access lots of other good stuff)
http://clojure.org/

Clojure – Functional Programming for the JVM (Tutorial)
http://java.ociweb.com/mark/clojure/article.html

Clojure Programming (Comprehensive book)
http://www.clojurebook.com/

clojure (Discussion)
http://groups.google.com/group/clojure

Intro to Erlang

Continuing with my series on comparative functional languages, today I’ll be discussing Erlang. I’ll provide an overview of the language plus some code samples written in Erlang.

Erlang has been in use in real systems for quite a while. It boasts a hot swapping capability so that upgrades can occur while a system is still running. From its bit manipulation capabilities to its exemplary concurrency system (borrowed by Scala), Erlang has a very practical, industry-ready feel to it. However, it also has some quirky syntax that is indicative of its roots in a single company rather than a larger community.

Background

Erlang came out of Ericsson in 1986, and Joe Armstrong is credited as the driving force behind it. Erlang is similar to F# in that it originated in industry. Unlike F#, Erlang is not really an attempt or direct means for making anyone a lot of money, as far as I know. Therefore, it has much more of a traditional open source community backing it.

Erlang’s big user conference is held in Sweden each year (where Ericsson is headquartered), though major Erlang events are held around the world throughout the year. For a few years in my career, I modified and extended some Ericsson produced software (but not at Ericsson) and I was highly impressed with the development methodology, tools, and end products.

Comparative Description

  • Paradigm: Functional only
  • Platform: Windows and Unix variants (does not compile to JVM byte code)
  • Typing: Strong and dynamic
  • Evaluation: Eager

Syntax Highlights

To give you a feel for the flavor of Erlang’s syntax, I have some simple source code that represents donations to charity accounts. In each section below, I demonstrate one or more basic functional programming concepts (noted in the comments).

% tuple
newAccount(Name) -> {Name, 0}.

% list comprehension
donate(Charities) ->
  [{Name, Amount + 100} || {Name, Amount} <- Charities].

% map
% anonymous function
donate2(Charities) -> lists:map(
  fun({Name, Amount}) -> {Name, Amount + 100} end,
  Charities).

% local function
donate3(Charities) ->
  Give = fun({Name, Amount}) -> {Name, Amount + 100} end,
  lists:map(Give, Charities).

% pattern matching
donate4(Charities) ->
  Gift = fun(Name) ->
    case Name of 
      "most deserving" -> 500;
      "more deserving" -> 300;
      _                -> 100
    end
  end,
  Give = fun({Name, Amount}) ->
    {Name, Amount + Gift(Name)} end,
  lists:map(Give, Charities).

Some Unique Aspects

Several practical features standout as unique and important in Erlang. Through its dynamic code loading feature, modules in Erlang can be upgraded at run time without stopping the system. Its bit syntax makes working with bits and bytes in protocols and packed data stores much easier (think C bit fields but much better, handling endianness and variable segment sizes).

Probably the most well known unique feature of Erlang (well not unique now that other languages have borrowed it!) is its concurrency model. This model is based on separate processes sending and receiving messages. Processes are easy to spin up and are efficient and scalable. The idea behind the model is that instead of shared memory and locks (with associated issues of race conditions and deadlock), Erlang uses a pure message passing system with no shared memory.

A Simple Real-World Example

Here I will implement a simplified problem relevant for packet processing which might be useful for applications such as routers, firewalls, intrusion detection systems, etc. It is a basic signature matching program, and you can follow what I’m doing from the code and comments.

-module(signature).
-export([main/0]).

% Main IO to drive the program
main() ->
  Line = io:get_line("Enter malware signature:"),
  Malware = string:strip(Line, right, $\n),
  io:format("Matching packet IDs:~n"),
  Ids = find_matching_ids(Malware, session()),
  PrintId = fun(Id) -> io:format("~B", [Id]) end,
  if
    Ids =:= [] -> io:format("None");
    Ids =/= [] -> lists:foreach(PrintId, Ids)
  end.

% The list of test packets
session() -> [{0, "01234"}, {1, "56789"},
              {2, "01289"}, {3, "34567"}].

% Return only the IDs from a list of matching packets
find_matching_ids(Signature, Packets) ->
  Matches = find_matching_packets(Signature, Packets),
  lists:map(fun({Id, _})->Id end, Matches).

% Find packets that match the signature
find_matching_packets(Signature, Packets) ->
  Has_substr = fun({_, Content}) ->
    string:str(Content, Signature) > 0 end,
  lists:filter(Has_substr, Packets).

To Learn More

Main Website (Download Erlang, plus access lots of other good stuff)
http://www.erlang.org/

learn you some Erlang for great good! (Tutorial)
http://learnyousomeerlang.com/content

Programming Erlang (Comprehensive book)
http://pragprog.com/book/jaerlang/programming-erlang

erlang-questions (Discussion)
http://groups.google.com/group/erlang-programming

Intro to F#

Continuing with my series on comparative functional languages, today I’ll be discussing F#. I’ll provide an overview of the language plus some code samples written in F#.

In some ways, I’m not sure what to make of F#. The language itself is just fine and has some interesting and unique features, but the extent of the current F# community is not clear to me. When looking for blogs, groups, and events related to F# it seems less popular than other functional languages. Yet the tools that are available (free and paid) for F# are solid. On sites listing language popularity rankings, F# is sometimes ahead of other FP languages and sometimes it is behind.

My assumption is that since it is less of a community based endeavor than other FP languages, F# it will take time to grow a significant user base and community. If other functional languages start to gain widespread acceptance, you can be sure that Microsoft will compete aggressively and put more resources into F#. Taking all this together, I think it is likely that F# will eventually be a dominant player in the larger FP community (as C# is in the OO community).

Background

One thing I think everyone wants to understand is the extent to which Microsoft is involved with (and controls) F#. On the one hand, F# is technically open source and is backed by the F# Software Foundation. However, when you try to install and use F# (for free, I’m sure the paid version is much easier), the difference from other languages becomes quite clear. Most of the other languages that I’ll discuss are purely community and non-profit based languages (with the exception of Erlang which originated from and is heavily supported by Ericsson).

F# originated from Microsoft Research in Cambridge, and it is based largely on OCaml. Don Syme is credited with the design and implementation, and he continues to work on the F# team at Microsoft.

Comparative Description

  • Paradigms: Functional, Imperative, Object-Oriented
  • Platform: Most (Open source implementation available on most platforms)
  • Typing: Strong and static with type inference
  • Evaluation: Eager with support for lazy and parallel

Syntax Highlights

To give you a feel for the flavor of F#’s syntax, I have some simple source code that represents donations to charity accounts. In each section below, I demonstrate one or more basic functional programming concepts (noted in the comments).

module intro

// explicitly typed function
// tuple
let newAccount (name : string) = (name, 0)

// type inference
// list comprehension
let donate charities =
  [for charity in charities -> (fst charity, snd charity + 100)]

// map
// local function
let donate2 charities =
  let give charity = (fst charity, snd charity + 100)
  List.map give charities

// anonymous function
let donate3 charities =
  List.map (fun charity -> (fst charity, snd charity + 100)) charities

// pattern matching
let donate4 charities = 
  let gift charity = match (fst charity) with
                     | "most deserving" -> 500
                     | "more deserving" -> 300
                     | _                -> 100
  let give charity = (fst charity, snd charity + gift charity)
  List.map give charities

Some Unique Aspects

F# has several unique aspects that are noteworthy. I find it interesting that F# includes language support for statically specified units of measure (e.g. meters for distance, meters per second for speed). Working in the wrong measurement units has been the source of software bugs, some of which have been highly publicized and very costly. F# allows developers to specify a measurement unit such that using incorrect measurement units will be caught at compile time.

Just as Haskell includes extensive support for and use of monads, F# supports a concept called computation expressions. Like Haskell monads, F# computation expressions (sometimes referred to as workflows) represent the pipelining or chaining of discrete pieces of computation.

F# also includes support for what it calls quotation expressions. An important use case for functional programming languages is the implementation of domain specific languages (DSLs). When building the tools surrounding a DSL, it is essential to have access to the abstract syntax tree (basically the syntactic structure) of the code written in a DSL. F# quotation expressions help with exactly that.

A Simple Real-World Example

Here I will implement a simplified problem relevant for packet processing which might be useful for applications such as routers, firewalls, intrusion detection systems, etc. It is a basic signature matching program, and you can follow what I’m doing from the code and comments.

module signature

open System

// Find packets that match the signature
let find_matching_packets signature packets = 
  let comparison = StringComparison.OrdinalIgnoreCase
  let has_substr (packet: int*string) =
    (snd packet).IndexOf(signature, comparison) <> -1
  List.filter has_substr packets

// Return only the IDs from a list of matching packets
let find_matching_ids signature packets = 
  let ids = find_matching_packets signature packets
  List.map fst ids

// The list of test packets
let session = 
  let p1 = (0, "01234")
  let p2 = (1, "56789")
  let p3 = (2, "01289")
  let p4 = (3, "34567")
  [p1; p2; p3; p4]

// Drive the interactive program
let main =
  printfn "Enter malware signature: "
  let malware = Console.ReadLine()
  printfn "Matching packet IDs:"
  let ids = find_matching_ids malware session
  if List.length ids = 0 then
    printfn "None"
  else
    List.iter (printfn "%d") ids

main

To Learn More

Main Website (Download F#, plus access lots of other good stuff)
http://fsharp.org/

Try F# (Interactive Tutorial)
http://www.tryfsharp.org/

F# for You (Tutorial)
http://fsharp4u.com

F# for fun and profit (Tutorial)
http://fsharpforfunandprofit.com/

Programming F# 3.0 (Comprehensive book)
http://shop.oreilly.com/product/0636920024033.do

FSharp Open Source Community (Discussion)
http://groups.google.com/group/fsharp-opensource