Lambda the Ultimate

Thanks for your detailed answer Jon. I've heard of rings, monoids, groups, etc. but was never motivated to learn greater and greater rigor in describing integers :) As usual, what's considered abstract in math may turn out to be eminently practical in computer science.

I get how, given a language, it can be described by various structures from abstract math. How about the other way around. Say I need to create a domain specific language, is it practically helpful to see if it fits a monoid or a ring or a monad?

Is it common practice (or should it be) that you start with a domain: a date library, animation language, financial contract langauge, etc. and see if it makes sense to implement it as one structure or another? Would the design become more consistent, expressive or elegant if one started to think of a dsl in such terms?

The few documents I've read about DSL design talk a great deal about parsing languages or embedding them in existing languages. Unfortunately, I haven't found anything which provides a more systematic way of designing a good dsl.

q1: a1: yes.
q2: a2: no, yes.
q3: a3: probably yes, but one can still screw it up in other ways i'm sure.

Pairs whose elements are monoids, where (A, B) • (C, D) = (A • C, B • D) and the identity is (1, 1).

Of course, technically you mean that the components of the pair are elements of (fixed) monoids, not the monoids themselves.

I meant “pairs whose elements are members of sets which form monoids with some other operations and identities, which I here refer to using a convenient abuse of overloaded notation because I am a lazy functional programmer”.

however using it for string concatenation is not a good idea (because its not commutative)

Hmm. Do you prefer multiplicative monoids to addative ones? (Or do you prefer multiplication be commutative, too? :-) I've always thought + a very natural choice for string concatenation, because conceptually "adding stuff" is what it's doing.

To me, "adding stuff" implies, among other things, an operation where the order of the operands doesn't matter. String concatenation isn't addition because "alpha" + "beta" != "beta" + "alpha".

The issue is that if I'm looking at an expression with variable names rather than literals, and thinking of what it means and how to express it more simply, the + operator implies a whole set of transformations that simply aren't valid on concatenation and I have to stop and think about what type these things are before realizing I'm wrong.

That said, I'd have no objection to there being an infix operator for concatenation: it's a very useful operation and a concise way to express it would be great. It's just that that operator can't be + because + means a category of operations which simply does not include concatenation.

The question is, are all algorithms defined on '+' valid for the operation. I can't think of many algorithms defined only in terms of + apart from summation (which comes back to commutivity)

If we have something that implements a few more operators, then the requirement becomes more interesting.

In terms of commutivity of multiplication, if there are significant algorithms that depend on the commutivity, then there should be a separate operator for non-commutitive multiplication. The decision for me would be based on looking at which algorithms you would lose,

Thanks Keean, perhaps you can help me understand just what it means to '+' something.

In type theory, addition is described as a union: None|Some() where the value is of type None OR Some(...). Product type is a pair (A,B). My gut reaction would have been to make a pair represent '+'. Just because '+' is something I think of as combining two things and the object which has been 'added' contains BOTH of operands, not either.

I believe product type refers to cartesian product, as I've seen in relational algebra. However, it doesn't make intuitive sense to me why a pair type isn't more naturally a '+' rather than a '*'

You can think of types as (naïve) sets of possible values. Call the number of such values the magnitude. What you are “summing” with a sum type is those sets—in other words, Either a b is the disjoint union of a and b, and magnitude(Either a b) = magnitude(a) + magnitude(b). Similarly, what you are “multiplying” with a product type is the sets—Pair a b is the Cartesian product (as you mentioned) of a and b, and magnitude(Pair a b) = magnitude(a) × magnitude(b)

It’s also not intuitive because in natural language we can say “and” to mean several things, including sums, concatenation, and pairing, but for products we say “times”—i.e., not “with”-ness, but repetition.

There is something to be said for the intuition of union and intersection types rather than sums and products—magnitude(Union a b) = magnitude(a ∪ b) and Union a a = a, i.e., union is idempotent; magnitude(Intersection a b) = magnitude(a ∩ b) and Intersection a a = a as well. These are particularly useful when subtyping is involved, because they correspond to “meet” and “join” in the interface hierarchy.

Natural language is not necessarily being imprecise, rather using "and" for sums can refer to the sum of exponents - which is a product, i.e
"3 pebbles and 2 pebbles = 5 pebbles"
means
pebble^3 x pebble^2 = pebble^5

or in PL jargon "a pair of a 3-tuple of pebbles and a pair of pebbles can be transformed into a 5-tuple of pebbles"

Of course, since sums and products are dual, and indirection is common in everyday language people can and do on occasion indirectly refer to one with the other.

If you think about types that are finite sets of values, then product and sum types have a cardinality that is the product or sum of the original cardinalities. For instance, the product of two 3-valued types is a 9-valued type, and the sum of two 3-valued types is a 6-valued type.

More generally, the two operators have a distributive law: Every type (A * (B + C)) can be converted to ((A * B) + (A * C)) and back.