[WIP] A Conceptual Bridge

[wtd]

Objective

This document sets out to bridge the conceptual gulf between Turing and Java and functional programming. For the purposes of this document, the functional languages used will be O'Caml and SML.

Turing and Java were chosen because they are the languages programmers here likely have the greatest exposure to. O'Caml and SML were chosen because they are both expressive, well-developed languages, and share with Turing and Java to some extent the quality of being statically-typed. This narrows down differences that are not deemed significant to this document's purpose.

Function basics

As the term implies, functions are central to functional programming.

Turing has functions, as well as procedures, and Java has methods which provide the same functionality. Of course, Java's methods can only exist within the context of a class, but we can essentially use static methods the same way functions and procedures in Turing are used.

Java also doesn't have a separate classification for procedures. Instead such things are merely functions which return void. In this case there's no need for a special "return" statement, but one can be used to break the control flow.

In functional languages, we have no procedures. We only have functions. However, we may return the special type "unit" as this is the closest thing the languages being used here have to nothing. Other functional languages may call this "nil" or something to that effect. The type "unit" has only a single value, written as an empty pair of parentheses.

With functional languages, there is (generally) no way to break the control flow within a function. A function can cause the entire program to exit, but it cannot arbitrarily skip to the end of the function. As such, there is no "return" or "result" statement. Instead the function simply returns the last value encountered in the flow of control. This encourages the use of explicit control flow mechanisms, rather than implicit ones.

Variables... or not

It is common practice in Turing and Java to create variables. These are values given names, but we may then as the program runs arbitrarily change the value bound to that name. While this is possible in the ML family of languages as well as other functional programming languages, it is discouraged. The syntax itself discourages the practice by making constants easier to create.

The result in Turing and Java is that we quite often have procedures which modify existing variables. This is accepted and encouraged practice. This is not the case in the functional world. Instead, we are encouraged to develop functions which map an existing value onto a new value. Typically the programming environment is specifically optimized to deal with this, and the rapid creation of numerous new values is not an issue.

Aggregate Data Types

As we move beyond the basic data types in a language, one of the first things we usually want to do is create aggregate data types. So in Turing and Java, we create records and classes, respectively.

In Turing we'd give our new aggregate data type a name, then specify the types and names of its individual pieces of component data. In Java we do this, but we also have to provide a means to construct an object of the new class, as well as a way to access that data, which should not be directly accessible outside of the class.

The ML family of languages provide a number of solutions to this, but the simplest is just to use tuples. Tuples are simply a set of values, surrounded by parenthese and separated by commas. We can easily create a tuple, and the language gives it a type name for us. If we're storing a string and an integer, it calls that type by the "string * int" name. If we have three integers, "int * int * int" is used. In short, there is no need to name such simple types, though it remains a possibility.

But then the question becomes how one gets an individual piece of data out of the tuple. With Turing and Java this is straightforward. Either a member is directly accessed, or an accessor method is called, and the relevant data is returned. But our tuple in ML never gave a name to its individual pieces.

Enter the hero of the story; its name is "pattern matching." A tuple follows a pattern. A tuple containing a string and an integer, for instance, always looks like a tuple containing a string and an integer. If we ask the language to match that tuple with a tuple pattern, we can give names to our pieces of data.

code:

type Foo : record    bar : string    baz : int end procedure wooble(ninja : Foo)    put ninja.bar + " " + intstr (ninja.baz) end wooble var qux : Foo qux.bar := "Hello" qux.baz := 42 wooble (qux)

code:

fun wooble (bar, baz) =    print (bar ^ " " ^ Int.toString baz ^ "\n");     val qux = ("Hello", 42); wooble qux;

Functions again: Parameters

In Turing and Java, a function/procedure/method may have zero or more parameters. In ML, a function may have only a single parameter. This would seem to be a limitation, but it works, and works well.

To deal with the not infrequent case where we pass no arguments to a function in the Turing and Java worlds, we can simply have a single parameter of type "unit." Multiple arguments can be handled in two ways.

The first, and simpler style is generally preferred in the SML world, and eschewed in the O'Caml world. In this style, we simply have a single argument that is a tuple containing all of the arguments we wish to accept. Pattern matching is used to give names to these parameters.

code:

function multiply(a : int, b : int) : int    result a * b end multiply

code:

fun multiply (a, b) = a * b;

The second style relies on the fact that fucntions are first class values. Let's rewrite the multiply function.

code:

fun multiply a =    fn b => a * b;

In this case, calling "multiply 3" actually returns another function which multiples "a" by its argument. We can then simply call it as follows.

code:

multiply 3 4

This is common enough that ML provides a shortcut. However, the effect is still very much the same.

code:

fun multiply a b = a * b;

This gives rise to currying. Since the multiply function returns a function, there is nothing stopping us from capturing that resulting function, giving it a name, and then using it repeatedly.

code:

val double = multiply 2; val (two, eight) = (double 1, double 4);

It would be fair to say that this is completely unlike any way in which Turing or Java implement functions with multiple parameters. At the same time, though, these methods are conceptually simpler and offer a greater degree of flexbility.

Revenge of the Aggregate Data Types: Records

Earlier I compared and contrasted records and classes in Turing and Java, respecticely, with tuples in ML. Yet both SML and O'Caml contain the means to create and work with records.

SML records work much the same way tuples do. You can simply create a record type at will, and pattern match against it, without ever needing to give that type a name. Of course, you may give it a name if you so desire. Let's revisit the earlier example.

code:

type Foo : record    bar : string    baz : int end procedure wooble(ninja : Foo)    put ninja.bar + " " + intstr (ninja.baz) end wooble var qux : Foo qux.bar := "Hello" qux.baz := 42 wooble (qux)

code:

fun wooble {bar=bar, baz=baz} =    print (bar ^ " " ^ Int.toString baz ^ "\n");     val qux = {bar="Hello", baz=42}; wooble qux;

O'Caml provides a few more issues, as record types must be named, and their fields must be unique to that type.

Making Choices

It's probably notable that so far I have yet to talk about making decisions with conditionals. In this regard, there is a greater resemblance between Java and the ML families than with Turing, though significant differences between ML and Java remain.

In Turing and Java, we think of conditionals as statements. They modify the state of the program (or not) based on conditionals. ML, however, views conditionals as just another expression. This is the first, and one of the most fundamental differences. Java provides both, to some extent, via the ternary operator.

Turing handles "else if" situations by introducing a new keyword, "elsif" which denotes a separate part of the conditional clause. Java, on the other hand, simply takes advantage of the fact that an "if" statement can be the sole result of an else. Normally this looks quite fluid.

code:

if (...) {    ... } else if (...) {    ... } else { }

However, if one considers that curly braces are optional, it could be rewritten as follows.

code:

if (...) {    ... } else {    if (...) {       ...    } else {       ...    } }

This is effectively what happens when we write the following SML.

code:

if ... then    ... else if ... then    ... else    ...

This could just as easily as with the Java example be rewritten.

code:

if ... then    ... else (    if ... then       ...    else       ... )

In Turing and Java, we can write a conditional statement with only an "if" branch. This is in fact often quite useful. This, however, is mostly because we have a lot of variables whose values we wish to mutate, and we can alter the control flow of a function, procedure or method rather arbitrarily. We may, for instance, wish to return early from a function, and skip an entire area of execution, or a counter variable might be incremented conditionally.

This is far less useful in ML, and can lead to questions about whether a function will work properly in certain cases. As a result, all conditionals have an "else" branch. The only exception to this is that O'Caml permits an "else" to be omitted when the conditional returns "unit." Here the else is implicit and returns "unit." SML requires the else to be present even in this case.

code:

fun sayHelloToBob name =    if name = "Bob" then       print "Hi Bob\n"    else ();

code:

let say_hello_to_bob name =    if name = "Bob" then       print_endline "Hi Bob";;

Making Choices: Avoiding If/Else

In the previous example I used a conditional to determine if a name was "Bob" and then printed a greeting if it was. Let's see what this would look like in Turing and Java.

code:

procedure say_hello_to_bob(name : string)    if name = "Bob" then       put "Hi Bob"    end if end say_hello_to_bob

code:

public class Test {    public static void sayHelloToBob(String name) {       if (name.equals("Bob")) {              System.out.println("Hi Bob");           }    } }

Earlier, in talking about function parameters, I discussed pattern matching. There I only had one pattern. ML, however, lets us have many patterns, in case one fails to match. With that in mind, let's rewrite our previous examples.

code:

fun sayHelloToBob "Bob" = print "Hi Bob\n"   | sayHelloToBob name = ();

code:

let say_hello_to_bob =    function       "Bob" -> print_endline "Hi Bob"         | name -> ();;

We can make this even simpler. ML allows us to replace values we don't care about in patterns with underscores. After all, why give a name to something you don't care about?

code:

fun sayHelloToBob "Bob" = print "Hi Bob\n"   | sayHelloToBob _ = ();

code:

let say_hello_to_bob =    function       "Bob" -> print_endline "Hi Bob"         | _ -> ();;

This permits us to avoid ever having to write a conditional. It is something you will not find present in Turing or Java, and an important difference to grasp.

Where are the Types?

In Turing and Java variables and functions, procedures and methods all have very distinct types specified. We have also talked about very specific types with regard to functions in ML. ML is just as strict about types as Turing and Java.

That said, I never actually specified the types involved. Turing and Java users are most likely familiar with this kind of notation from dynamically-typed languages, where the type of variables, and the parameters and return values of functions are not stricly enforced.

ML uses a third system. It strictly enforces types, but in all but a few cases it infers type information from how values are used. With this system, it is rarely necessary to explicitly state in your code what kind of types are being used. Errors in how types are used are caught and reported at compile time, rather than when the program is run.

Control Flow: Looping

Turing and Java programmers take looping for granted. Functional programmers do not. Both of the ML languages provide some degree of looping support in their syntax, but as that is an imperative feature, we will not use it here.

Instead, functional programmers are likely to employ recursion to solve such problems. As a result, the languages and tools have been oriented toward this.

Probably the most important difference between Turing and Java, and functional languages such as the ML family is that the latter support tail recursion optimization. Let's look at a simple factorial method defined in Java, using recursion.

code:

public class Factorial {    public static int factorial(int n) {       if (n <= 1) return 1;           else return n * factorial(n - 1);    } }

The problem with this is what happens when it's used. The first time it's used, some bytes are pushed onto the stack, to hold information local to the method. Then it calls itself, and the same amount is added to the stack. If we try to calculate the factorial of a large enough number, we will eventually run out of room on the stack, and the program will not successfully complete.

Given this problem, the astute Turing or Java programmer creates a loop.

code:

function factorial(n : int)    var product : int := 1        for i : 2..n       product *= i    end for        result product end factorial

Now, let's look at the same in SML.

code:

fun factorial 0 = 1   | factorial 1 = 1   | factorial n = n * factorial (n - 1);

As much as I have championed ML, this suffers from the same problem. Let's look at how it breaks down for "factorial 4."

code:

factorial 4 4 * factorial 3 4 * 3 * factorial 2 4 * 3 * 2 * factorial 1 4 * 3 * 2 * 1 4 * 3 * 2 4 * 6 24

When we got to the last recursive call of factorial, we still needed information from all of the previous calls. Our stack will therefore grow until it too, just like the Java version overflows, and for a suffiently large calculation, the program will unsuccessfully terminate.

The key is to not need that information. We can accomplish that through use of an accumulator.

code:

fun factorial 0 acc = acc   | factorial 1 acc = acc   | factorial n acc = factorial (n - 1) (n * acc);

Now, when we break down the calculation of the factorial of 4, we see the change.

code:

factorial 4 1 factorial 3 4 factorial 2 12 factorial 1 24 24

Here the state of the previous call is not important, so it is immediately discarded. The stack does not grow, and except for limitations on the size of the integer type, we can calculate the factorial of arbitrarily large numbers. In effect, the compiler turns this recursion into a loop with all of the performance characteristics of a loop in Turing or Java.

We could do the same in Turing or Java, but unless someone has some custom hack to the tools, the compiler will not recognize this use of recursion and optimize it for us. The stack will still grow, and the program will still die.

It is important to recognize how this impacts the use of recursion in functional languages, as compared to its use in languages such as Turing and Java.

While recursion is a significant departure from the world of mutable state, and explicit loops, please consider that recursion can have benefits. It can allow a large set of problems to be expressed more naturally than with explicit loops and mutating variables. It also places a larger portion of the programming logic at a higher level of the program. In simpler terms, it leads to less indentation in many cases, and the human mind can only take just so many levels of that.

Local Bindings

Turing and Java programmers are familiar with the concept of scope, and how fucntions, procedures, and methods may have local variables. Indeed, we may even have local variables in even smaller, more tightly focused blocks.

One thing that will not be familiar is the use of local functions. In our previous example, we created a tail-recursive factorial function. The only problem is that having to explicitly provide an initial state for the accumulator.

In Turing, we might create a helper function that does this, and then a function named "factorial" that takes a single arguments, then calls that helper with the initial accumulator value. We could even hide it in a module that doesn't export the helper function.

In Java we might accomplish the same using a Factorial class that doesn't make the helper method public. We might even use method overloading to avoid introducing a new name for the helper.

In ML, we could do this the Turing way, but we're more likely to employ local functions.

code:

fun factorial n =    let       fun helper 0 acc = acc         | helper 1 acc = acc             | helper n acc = helper (n - 1) (n * acc)    in       helper n 1    end

This represents a significantly different way of thinking about how to manage small functions with no applicability beyond a limited scope.

Aggregate Data Structures part II: Lists

In Turing and Java, when we want a collection of a bunch of values of the same type, we'll commonly use an array or in Java we might also use one of the Collection classes. We then quite naturally deal with these by means of loops and counter variables, or perhaps iterator objects.

In ML and other functional programming languages, we are prone to using a very simple data structure for this. It's usually called just "list." It's important to discuss this data structure now, since recursion is still fresh in the brain. You see, lists are so incredibly simple because they are in fact recursive. A list is either empty, or it is some value and another list.

That definition easily explains a list of one element.

code:

[1] 1 :: []

However, since that can be considered a list, we could construct a list of two elements.

code:

[0, 1] 0 :: [1] 0 :: 1 :: []

From the simplest of foundations, a list of any length can be constructed. Iterating over such a data structure is just a matter of embracing the list's recursive nature, and employing pattern matching.

code:

- fun printAllInts [] = () =   | printAllInts (x::xs) = (print (Int.toString x ^ "\n"); printAllInts xs); val printAllInts = fn : int list -> unit - printAllInts [1, 2, 3, 4]; 1 2 3 4 val it = () : unit

More Data Types: Variant Types

Turing and Java both support object-oriented programming. Using object-oriented programming, we can achieve polymorphism. But that's a whole book by itself, so let's just demonstrate.

The ML languages, being very strictly statically typed do not allow us to add integers and floating point numbers. Turing and Java (as well as other languages) typically get around this by silently promoting or demoting values. In order for an int to work with a float, the int gets silently turned into a float.

So, how can we add different types? Well, let's pretend we have this limitation in Java, and conceive of a solution. We might create an interface called Number that can represent itself as an int or double via methods, "getInt" and "getDouble." We'd have the I and D classes, representing Integer or Double implement this interface. We could then have a class containing static methods which add various combinations of these types.

In the end, the "add" method would always be adding one Number to another Number. Now, let's see how we can achieve the same in SML, which has no support for object-oriented programming.

code:

- datatype number = I of int | D of real; datatype number = D of real | I of int - fun op+(I a, I b) = I (Int.+(a, b)) =   | op+(I a, D b) = D (Real.+(real a, b)) =   | op+(D a, I b) = D (Real.+(a, real b)) =   | op+(D a, D b) = D (Real.+(a, b)); val + = fn : number * number -> number - I 42 + D 2.7; val it = D 44.7 : number

Or, if you prefer O'Caml, it is easily demonstrated there as well. Though with this example, a new operator has to be defined, and we can see the distinct int and float addition operators in use.

code:

# type number = I of int | D of float;; type number = I of int | D of float # let (+~) a b =      match (a, b) with         (I a, I b) -> I (a + b)       | (I a, D b) -> D (float_of_int a +. b)       | (D a, I b) -> D (a +. float_of_int b)       | (D a, D b) -> D (a +. b);; val ( +~ ) : number -> number -> number = <fun> # I 42 +~ D 2.7;; - : number = D 44.7

What's happening in these examples is that we first define a new data type call "number." This data type has two constructors. The I constructor takes an integer as an argument, and the D constructor takes a real or "float" (depending upon the dialect of ML) argument. Using either constructor will result in a value of type "number." As a result, we can pass either as an argument to a function without violating the static type system.

We can then implement addition by pattern matching on the two numbers to be added together. If you've made it this far, then this function should be fairly simple to reason out.

Variant types are a wildly useful concept, and an important one to understand, especially as they are rather unlike anything in Turing or Java, yet can be used to accomplish the same goals.

Writing Functions: Another Look

So let's write a "greet" function. The trickiest thing in the following code will be the use of the Format module and it's types and functions. In this case, we're using the "formatf" function and the "fmt_item" type, which has a constructor "STR."

The formatf function takes a format string, a function to call on that string which returns unit, and a list of fmt_item values.

code:

open Format; fun greet name =    formatf "Hello, %s!\n" print [STR name];

A very straightforward function. A little too straightforward. Too trivial to challenge the programmer coming from Turing or Java. It doesn't make that programmer stop and think. We need something to think about. Let's think about the individual steps that are brought together to make this function work.

First we need to construct a fmt_item value using the name. That function already has a name. It's called "STR."

Next we need to create a list with a single thing as it's only element. That's easy enough using an anonymous function.

code:

fn x => [x]

And next we just need to print the thing. We can get a function for doing this by partially applying the formatf function.

code:

formatf "Hello, %s!\n" print

This is all well and good, except that you're probably not used to having a way to express this. Well, SML gives us a way. O'Caml does not include an operator to do it, but I will demonstrate a way to easily create a function that does. The term to remember is function composition.

code:

open Format; val greet =    (formatf "Hello %s!\n" print) o (fn x => [x]) o STR;

The "greet" function can now be used as before, but the argument is not explicitly passed. Turing and Java take the approach that this is bad, because it could be confusing. And they're half right. It is confusing.

It is also, however, powerful. It can allow code to express the solution to a problem more clearly. Let's imagine I have this function in Java.

code:

public class Greet {    public static void greet(String name) {       System.out.printf("Hello, %s!\n", name);    } }

Now, I want to greet someone by shouting their name. To accomplish this, I'll change the string to all uppercase.

code:

public class Greet {    public static void greet(String name) {       System.out.printf("Hello, %s!\n", name);    }        public static void greetWithAShout(String name) {       greet(name.toUpperCase());    } }

Now, let's do it in SML. I'm just adding in another step, and it occurs at the beginning of the process, so composition seems the natural choice.

code:

open Format; val greet =    (formatf "Hello %s!\n" print) o (fn x => [x]) o STR; val greetWithAShout = greet o (String.map Char.toUpper);

As promised, we can achieve composition easily in O'Caml by defining a simple "compose" function.

code:

let compose f g = fun x -> f (g x);;

Here the compose function takes two parameters which are functions. It returns a function which takes a parameter to this g and f are applied. This is a very straightforward way of accomplishing this task, but it does not take advantage of currying. As explained earlier, currying invvolves only partially applying arguments to a fucntion, and getting a new function back. Our compose function will behave identically if written as follows.

code:

let compose f g x = f (g x);;

[Clayton]

excellent job wtd, i learned quite a bit with that. now i have one question, where/what are the practical uses for functional programming? I can see how well it works, but i cant see where you would use this in the real world.

[wtd]

If nothing else, one could use it for the same thingsyou currently use other languages for... but with those tasks being easier.

[bugzpodder]

I'll stick to my for loops rather than tail recursion

[wtd]

And what if the problem is more naturally expressed via recursion?

[bugzpodder]

example? like the binary tree? A lot recursions require some sort of iteration in between to produce side effects, which is difficult (at least for me) to simulate in scheme

[wtd]

Why not pass to the function doing the iterating a function which accomplishes the desired side effect?

code:

- datatype 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree; datatype 'a tree = Branch of 'a * 'a tree * 'a tree | Leaf - fun eachValue(Leaf, _) = () =   | eachValue(Branch (v, b1, b2), f) = (f v; eachValue(b1, f); eachValue(b2, f)); val eachValue = fn : 'a tree * ('a -> 'b) -> unit - eachValue(Branch (42, Branch (56, Leaf, Leaf), Leaf), =           fn x => print (Int.toString x ^ "\n")); 42 56 val it = () : unit