-----------------------------------

wtd

Mon Sep 04, 2006 6:59 pm


[WIP] A Conceptual Bridge

-----------------------------------

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.

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)

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.

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

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.

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.

multiply 3 4

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

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.

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.

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)

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.

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

}

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

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

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

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

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.

fun sayHelloToBob name =
   if name = "Bob" then
      print "Hi Bob\n"
   else ();
   
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.

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

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.

fun sayHelloToBob "Bob" = print "Hi Bob\n"
  | sayHelloToBob name = ();
   
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?

fun sayHelloToBob "Bob" = print "Hi Bob\n"
  | sayHelloToBob _ = ();
   
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.

public class Factorial {
   public static int factorial(int n) {
      if (n  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.

# 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 = 
# 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.

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.

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.

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.

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.

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.

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.

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.

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.

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


-----------------------------------

Clayton

Tue Sep 05, 2006 3:08 pm



-----------------------------------

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

Tue Sep 05, 2006 8:51 pm



-----------------------------------

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


-----------------------------------

bugzpodder

Wed Sep 06, 2006 7:04 pm



-----------------------------------

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


-----------------------------------

wtd

Wed Sep 06, 2006 8:19 pm



-----------------------------------

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


-----------------------------------

bugzpodder

Thu Sep 07, 2006 10:13 am



-----------------------------------

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

Thu Sep 07, 2006 10:23 am



-----------------------------------

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

- 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