prose :: and :: conz


Static typing doesn’t have to suck: lambdas

This post will conclude my little series on why I’ve joined the static typing camp. Lambdas are pretty common in dynamically-typed languages. While many statically-typed languages are missing this powerful feature, there is no reason they have to. It also doesn’t have to be very verbose. Coupled with other good features like type inference, they can be just as concise as their dynamically typed counterparts. As usual, I will demonstrate this feature using Scala.

I won’t get too theoretical regarding the definition of lambda. People who are far better than me at languages will likely scoff at my colloquial exposé. From a practical standpoint, you can first think of a lambda as a function that can be treated as a value. That is, you can pass it as an argument to another function or return it from a function. It is a value that when given arguments evaluates to some other value (be careful here because it could also return another lambda)

Confused? Let’s start with some Java code as an example. Suppose we want a function that takes a String and returns the uppercase version of that String.

public class Lambdas {
   public static void main(String[] args) {
        String str = "Test";
        String upper = toUpper(str);
    }

    private String toUpper(String str) {
        return str.toUppercase();
    }
}

There’s nothing special there. Just a function applied to a string. Let’s suppose we want to apply that function to a collection of strings. Here’s what we might come up with for our main method:

    public static void main(String[] args) {
        String[] strs = new String[]
            {"Test", "each", "of", "these", "strings"};
        List uppers = new ArrayList();
        for(String s : strs) 
            uppers.add(toUpper(s));
    }

Until Java8 is released with Project Lambda, this is essentially the only option you have. That is, take the collection, iterate while applying the function to each member and adding the result to a mutable collection.

From a mathematical perspective, this is akin to having a function with the domain and codomain being the set of all strings. If we call the set of all strings “S”, we can denote this function as toUpper: S -> S. I expect my readers (Mom included) are familiar with the notation toUpper(x) denoting the application of toUpper to the element x (it is required that x is an element of S given the definition of toUpper).

When I teach my discrete math course, I use another handy notation. If A is a subset of S, then toUpper(A) denotes the set containing the result of applying toUpper to every element of A. That’s a nice, concise way to represent that notion. Why can’t our code do that? Well, a lambda helps us in that regard. The notation is different, but the notion is the same; apply the given function to every element of the collection to produce the collection containing the result.

Since Java doesn’t yet have lambdas, I’m going to make a switch to Scala. This is how we could define toUpper and apply it to a single string:

def toUpper(s:String) = s.toUpperCase
val str = "Test"
toUpper(str)

Now let’s declare our list of strings:

val strs = List("Test", "each", "of", "these", "strings")

Now for the lambda. This line is the equivalent of our toUpper(A):

val uppers = strs.map(toUpper)

That’s it! The value uppers is a list containing the upper cased strings from strs. So why is it called “map”? That also goes back to the mathematics. A often used synonym for “function” is “mapping”. This name is appropriate because a function does exactly that. It maps each element of the domain to an element of the codomain. So the method map() uses the argument to map each element of the collection to its output of the function.

This is also a statically-checked operation. The compiler verifies that we are passing a function that accepts a String as its only argument. Type inference then gives us the returned value uppers as a List[String].

Let’s revisit the single application of toUpper again:

val str = "Test"
toUpper(str)

I’m sure you know it was not necessary for me to declare and name the value str before handing it to toUpper. I can cut out that step and pass "Test" anonymously:

toUpper("Test")

This is called “anonymous” because the argument "Test" is being passed without a name. It turns out that we can actually do the same for functions. Let me first show you an alternative definition for toUpper:

def toUpper = { s:String => s.toUppercase }

Here we don’t specify the argument in parenthesis as with Java methods, but in front of the => keyword/operator. Using this syntax, we can actually pass this logic to map anonymously:

strs.map { s:String => s.toUppercase }

How about we kick it up a notch? Here I have explicitly specified the type of my lambda’s argument as String. Yet, earlier I mentioned that the compiler will ensure that I give it a function that only accepts a String. It must be the case that s is a String. And because that is true, it can actually be inferred:

strs.map { s => s.toUppercase }

While this looks like a very dynamically typed line of code, it is actually completely type safe. If you were to call a method on s not defined for String, it would not compile.

So about that anonymity… Why do we have to provide a name for s? It’s because we need something to call toUppercase against. But in Scala, we can even make the argument anonymous! This is done by using the underscore _ special character:

strs.map { _.toUppercase }

How’s that for conciseness? Once again, you can have all of the conciseness of dynamic languages in a statically-typed language if they’ll give you good tools and features. Static typing does often suck, but it doesn’t have to.

One last thing about lambdas… They are an awesome example of structural typing in the sense that it’s not the name but the structure that is important. The map function used here for illustration has this signature in List[+A]:

def map[B](f: (A) ⇒ B): List[B]

Basically, it takes anything that accepts an A (in our case, A is String) and collects the responses (of type B) into a new List[B]. Hence it’s the structure of the argument that is important, not the name. While structural typing per my previous post does require runtime reflection, it’s not the case for lambdas. There are no performance concerns with using them in Scala. Call me tonight if you have any questions, Mom.


Olde Comments
  1. […] that I have found I really enjoy: case classes, (?:case)+ objects, pattern matching, monadic types, lambdas, implicit conversions, and last but not least… optional […]

  2. […] can see what’s happening here. The expression i => i + 1 is a function/mapping (or “lambda” in programming terms) which is applied to every element of the collection to produce the […]

  3. Dobbs says:

    You know, String in Java already has ‘toUpperCase()’ as a function built-in! This kind of example sets up a straw-man. Now, if you choose a different function than toUpperCase(), it will be more relavant and interesting to see what you can do with Scala.

    • barnesjd says:

      I certainly agree in hindsight that I should have used a little more imagination for the example I used. :)

Tagged with: scala (41), functional-programming (31), static-typing (16)