Debasish Ghosh

I just finished reading To Mock a Mockingbird (though I don't recall a formal definition) so I'll take a stab and leave it to others to correct me.

Combinators are the basic building block of combinatorial logic. Simply, they are functions that permute, group, repeat and/or eliminate their arguments.

E.g., The T (thrush using the bird naming convention) combinator takes two args and swaps their order: Txy = yx.

The B (bluebird) combinator groups it's 2nd and 3rd args (overriding the default left-associativity): Bxyz = x(yz).

The M (mockingbird) combinator takes a single arg and repeats it: Mx = xx.

The K (kestrel) combinator takes two args and eliminates the second: Kxy = x.

There are two schools of 'lambda calculus' that use a set of base combinators to build arbitrarily complex ones. The first school uses B, M, T and I which is the identity function: Ix = x. The other school combines B, M and T into a single combinator that permutes, groups and repeats with one application. It's called S (starling): Sxyz = xz(yz). This latter school uses S together with K.

Whether using B/M/T/I or S/K/I, you can build up pretty much any other combinator:

B = S(KS)K.
E.g.,
S(KS)Kxyz, applying the leftmost S =
(KS)x(Kx)yz, dropping the parens (which are still implied when not present due to the left-associativity) =
KSx(Kx)yz, applying the leftmost K =
S(Kx)yz, applying the S =
(Kx)z(yz) =
Kxz(yz) =
x(yz) = Bxyz.

T = ((S(K(S((SK)K))))K)
M = ((S((SK)K))((SK)K))
…

I'd call them "composite types".

"Tuple" tends to refer to fixed-size collections where each element may have a different type. The tuple type is the (cartesian) product of those types. For example, the type "a tuple containing 3 Booleans" can be written as `Boolean * Boolean * Boolean`.

Since Boolean is type 2 (ie. it contains 2 elements, `True` and `False`), this makes our 3-Boolean tuple `2 * 2 * 2 = 8`. True enough, it has 8 elements: `(True, True, True)`, `(True, True, False)`, `(True, False, True)`, `(True, False, False)`, `(False, True, True)`, `(False, True, False)`, `(False, False, True)` and `(False, False, False)`.

Likewise, a tuple like `(1, "hello", True)` has type `Int * String * Boolean`.

That's why tuples are "composite types", they're the product of other types.

Arbitrary-length collections are more complicated, since they require recursion. The simplest is a singly-linked list with all elements of the same type `T`, which is given by the equation `list(T) = 1 + (T * list(T))`. `1` is the unit type `void`, which has one element (`NULL`), which represents the "nil" at the end of the list. The `T * list(T)` is a tuple containing a `T` and a `list(T)`, ie. it's a "cons cell". The `+` is a (tagged) union.

We can solve recursive equations like this using the greatest-fixed-point combinator `mu a`,to get `mu a. list = 1 + T * a` (see http://debasishg.blogspot.co.uk/2012/01/learning-type-level-fixpoint-combinator.html ).

For heterogeneous collections, where…

I used Erlang to build a mid-sized web service app (i.e. REST only, no user interface) which serves more than two million connections per day (sustained), and is deployed on a half dozen nodes across the Internet -- different ISPs (yeah, I'm a masochist). The app integrates the Mnesia database (with replication) and the Yaws web server (with my own extensions).

On any given node there were between 1,000 and 3,000 processes (threads) handling requests and internal jobs. I had supervisor trees for ensuring that everything kept running. All that worked like a charm.

Most of the issues I ran into were with getting the host infrastructure (Linux in my case) configured correctly. Things like number of available socket handles etc. Erlang dies unceremoniously when it runs out of system resources.

Mnesia is really nice. My database isn't very big (~500K objects), but still needed to be redundant and highly available. Setting all that was a breeze compared to most SQL dbs.

Yaws is nice, in that it's a full featured web server, but I'd probably also look at Mochiweb (http://bob.pythonmac.org/archives/2007/11/07/mochiweb-another-faster-web-server/).

Given that you have a requirement for "massive parallelism" -- high concurrency, Erlang is a very good option. I also believe Scala (http://debasishg.blogspot.com/2006/11/threadless-concurrency-on-jvm-aka-scala.html) and Clojure (http://clojure.org/concurrent_programming) offer reasonable alternate approaches.

Good luck.

Examples of successful Strong DSL (ie. standalone) are James Gosling's project for satellite control (I think it was), which he did so that users could make their own changes without bothering him (I doubt details are online - he mentioned it in an interview as a virtual machine that was a precursor to Java).

Our own pg also had a DSL for the Yahoo Store (was viaweb), so users could customize it. From the docs, it looks like it is implemented as Lisp with isomorphic friendlier syntactic sugar.

On weak DSLs (ie within a host language), I still think it's a virtue to try to make it as self-contained as possible. Mini-languages are surprisingly common: regular expressions; printf format syntax; XPath within XSLT. I saw a great comment recently [1] suggesting having DS error messages. I think this is an oft-overlooked aspect of the abstraction (it's not just syntax!), and to make the abstraction as non-leaky as possible helps everyone (programmer and non-programmer alike).

[1] http://debasishg.blogspot.com/2008/04/external-dsls-made-easy-with-scala.html?showComment=1208530020000#c8620585676360683177

That's what languages with immutable data structures do. Internally they implement simple data structures (lists, arrays) with more complex ones not to get a performance hit. For example, they don't want to copy every byte every time they add or remove from a list.

In ascending order of complexity

http://theerlangelist.blogspot.com/2013/05/working-with-immutable-data.html

http://concurrencyfreaks.blogspot.com/2013/10/immutable-data-structures-are-not-as.html

http://debasishg.blogspot.com/2010/05/grokking-functional-data-structures.html

In the case of Ruby, it's a language build on mutability so let's use mutable data. There are already plenty of languages with immutable data to use if we want to.

http://tech.puredanger.com/2007/09/18/spelunking/

http://debasishg.blogspot.com/2009/06/code-reading-for-fun-and-profit.html

http://www.oreillynet.com/ruby/blog/2006/05/post.html
(section about "making Mongrels stable and secure"

http://news.ycombinator.com/item?id=483824

http://blog.rubybestpractices.com/posts/gregory/005-code-reading-stdlib.html