Ballad of a Duck

From Compsci.ca Wiki

Latest revision as of 04:24, 9 June 2014

Preface

Why do we bother to write computer programs at all? Surely there must be a reason to undertake such a task. In fact, I believe there to be several.

First and weakest of these I think is our desire to simplify a task. Programming can greatly alleviate the tedium of simple, repetitive processes. I can confidently say I think this is the reason about 99% of computer programs have been written, but also that it's not a particularly strong reason why people have done so and particularly not why they continue to do so.

Existing tools do such a good (or at last competent) job of this that there is little continuing reason to program such tools from the ground up. In fact, many programming tasks amount to just slightly modifying these existing solutions.

Learning a programming language and computer system well enough to deliver a competent automation tool and then the task of actually doing it are not simple or easy. They require years of study, and any serious endeavor likely entails years of fine-tuning. A great deal of tedium can be justified in place of this expenditure of effort.

No, we cannot reasonably say that people go into computer programming just to make their lives easier. That job has been accomplished, and even had it not, the personal payoff is very rarely worth it.

However, we are creatures of pride, and we frequently see opportunities to improve on or best the work of others, especially when presented with a solution that is at best competent. Now, of course we may never succeed at doing so, but our belief that we can keeps us trying.

One need only look at the proliferation of "standards" to see this in action. How many instant messaging protocols does the world need, really? And yet, people keep striving to better the existing stalwarts. This is a good thing: it keeps the world of computers fresh and interesting and (generally speaking) continually improving.

Pride is a good reason to program, but also a dangerous one. A prideful programmer can become convinced that his or her creations are superior regardless of their objective merit.

Of course, it's possible to offset this hazard by filling an unmet need. This is an increasingly rare, but powerful motivation. Imagine the drive to create a complete cross-platform office suite for open source computing platforms. Those programmers had the pride to say they could do it, and nothing to compare against to demotivate them.

But the most important reason we write computer programs is the simplest, and one that cannot easily be discouraged by the body of existing work, or even a lack of overwhelming pride in ourselves. Quite simply, we write computer programs to find out if we can. We write more to find out how far we can go.

This is why I began programming years ago. I'm not sure I've yet found a limit. What will yours be? I hope you'll never find out, but if you want to push yourself, keep reading.

My Approach

I am a self-taught computer programmer. My knowledge has been pieced together from bits of code and often sarcastic internet rants about best practices, and my willingness to ask questions.

I will try to guide you, the readers, through some of the basics, but I expect you to go out and explore on your own, and answer the basics. Don't worry, I'll help you with the details.

If this approach bothers you, then stop reading here. I don't believe in spoon-feeding you information. Anytime I've done that I've never been able to tell who was learning and who was just regurgitating code. If you see yourself in that latter description, try to change. If you can't, there are myriad options out there that will give you the easy answers you seek.

Language

Lots of computer programming books teach you how to write code in Java or C++ or C# because those are useful languages and all basically the same. They are eminently useful for streamlining repetitive tasks and getting work done, which we know is what computer programs are written to do. Why shouldn't they teach these languages to you?

They shouldn't because that's not why we learn to write computer programs. Sure, C++ can be a huge challenge, but not the way it's taught or used by most, and many of its challenges lie in minutiae. Java and C# are comparatively boring languages. Most of their mastery lies in knowing which library to use and remembering long names.

All of those languages deal with a very simple concept: we have a piece of data X and we tell the computer to do Y to it, then we tell it to do Z to it in a linear fashion. The piece of data keeps getting changed until it's what we need. This is what we typically refer to as "imperative" programming, and it encompasses the majority of widely used programming languages.

But we often hear programmers talk about "functional" programming, and they call it difficult and present it as generally unfathomable. We still transform data in a functional programming language, but it encourages us to find different ways to accomplish that goal, and the conventional wisdom is that this is too difficult.

It's for precisely this reason that a functional programming language will be my choice. I have made a choice that I firmly believe represents the best balance of characteristics: it has no confusing fragmented implementations or libraries, and yet supports solid tools. It also boasts the advantage of a more direct syntax for expressing a number of concepts that the aforementioned mainstream programming languages have to come at in rather oblique ways.

I want you to continue reading because you like that people have said functional programming is too hard; you like proving them wrong and proving to yourself that you can do it.

Data

I have said that programming at its heart is transforming one piece of data into another. It behooves us, then, to start out by taking some time to look at what data really is.

Data are all of the tiny points of information that make up life. The meat of the data world are numbers. We deal with numbers constantly, and so too must programmers.

We deal most commonly with round numbers, or what a programmer would call integers. Integers are easy and direct. We can relate them to solid everyday objects, and as in written communication, integers are very easy to symbolize in computer programs.

Less easy are non-whole numbers, or as programmers would say, floating-point numbers. These are fractions of things: 3.4 km to the library; half a pizza left in the fridge. Humans don't usually have much difficulty working with these kind of numbers, but computers, with their binary brains do. In fact, while numbers like these can be represented accurately, it takes a lot of computational power to do so. To address this, computers store an approximation of these numbers which as the number increases becomes less accurate.

This will likely not be a huge obstacle at this level, but it does warrant consideration. The money example is a perfect one. If you're keeping track of money, there's a strong temptation to track dollars, and use floating point numbers to account for pennies. Knowing that you can instead count using integers to represent pennies, you should do so to avoid any inaccuracy as calculations are made on those values.

Aside from numbers, we can represent text with two different types of data. The simplest is a character. For the sake of simple Latin-based characters, characters can be thought of as simply integers between 0 and 255, where each number represents a unique character. Strings are a sequence of characters, and generally are far more useful, though necessarily take a little more getting used to working with.

Notes on Code Organization

The biggest expenditure of time in programming is not writing, but rather reading code. As we explore increasingly complex programs, it will be important for us to find ways to organize our code, both to make it easier to read, and easier to fix our errors once they're found.

Two fundamental units of organization exist. These will be explored later in greater detail, but some theory is called for first.

Functions

Functions give a name to a transformation of one piece of information into another. Rather than simply writing the same code repeatedly throughout our program, we can name a given calculation. This avoids tedious retyping or copy and paste, but more importantly, lets us tell the reader of the code what we're calculating, rather than how we're doing it. As well, improvements to a given set of code can be made in one place, and the benefits apply everywhere that function is used.

Given that we will be using a functional programming language, you should expect it to be exceptionally easy to create new functions. You will also find that many existing functions are provided to accomplish basic tasks. We will use many of these, but you may also end up rewriting others to learn how they work.

Modules

As we accumulate more and more functions and data, we can expect naming to become increasingly troublesome. To keep related data and functions grouped, we will use modules.

As there are a number of existing functions, there are a number of different modules provided which help to group those functions together. The one you'll encounter most frequently is Pervasives, which includes a great number of common and highly useful functions.

Any module may, for convenience's sake, be opened, allowing its contents to be directly accessed. This is the case with Pervasives, but otherwise use of this facility should be with discretion.

As with functions, modules are easily created and experimented with. We will use them extensively as we go.

The Language

So far everything has been in English. There hasn't been a single bit of code in sight. That's intentional. I wanted your attention before I started throwing distracting code examples at you. But, as that's about to begin, it's worth taking a bit of time to talk about the other language that will be in use.

OCaml is a functional programming language. It is a very syntax-heavy language, and there's a lot to learn. Fortunately, OCaml lets us learn this as we go, rather than dumping it all on us at the very beginning. In other words, it can be as simple or as complex as we need it to be to delve into the world of computer programming.

OCaml is a compiled programming language. This means that our OCaml programs are translated to machine code which can be natively executed by our computers without any further translation necessary. This makes programs run very fast, but means that we need to compile programs and then run them.

Fortunately, OCaml also supports something called a "bytecode interpreter" wherein OCaml programs are converted to an intermediate format and then run. This is much slower than native compilation, but can yield quicker results. On top of this, OCaml provides an "interactive toplevel" interpreter, which accepts small chunks of code, evaluates them and spits out the result. Inadequate for composing large programs, this tool is nevertheless invaluable for letting us play with core concepts and test our understanding before implementing larger programs dependent on understanding those concepts. We will use this extensively.

OCaml is statically typed. All data have types. We know that functions transform one piece of data into another. Functions are very strict about the type of data fed to them. If the types are incorrect, the program will not compile or run at all. OCaml will provide an error indicating the source of the error.

These type errors are very useful for identifying both simple and more complex logical errors in a program. Though this does not hold universally true, many believe that an OCaml program that runs is likely to be free of errors simply by virtue of getting past the type checker.

The OCaml tools and manuals can be found at http://caml.inria.fr. This document will not cover the installation process, which is very straightforward for both Windows, Mac and Linux/*nix users.

Data Representation

Previously I have spoken about data in OCaml. We discussed integers, floating point numbers, characters and strings. It should not be surprising that all of these have straightforward representations within OCaml programs. Of course, these types and most of their representations are common to a wide variety of different programming languages.

Integers could scarcely be simpler. Both positive and negative integers have easy representations.

Floating point numbers are similarly simple, but do have one wrinkle: if the floating point number in question is a whole number, the trailing zero after the decimal point may be elided. A leading zero must precede the decimal point if the floating point number is between 1 and -1. Scientific notation is also available.

Characters are enclosed by single quotes and contain a single character. A couple of exceptions exist to this. Should we need to represent the single quote character, we can escape it within the single quotes with a backslash. Additionally, a backslash followed by an n represents a newline character. Though it may also appear odd, a space character can be represented by a space within single quotes.

Strings are represented by zero or more characters enclosed within double quotes. As in characters we represented a single quote with the backslash, so a double quote can be included in a string. The same applies for the newline.

Questions

1. Which is an integer?

2. Which is a valid character representation?

3. Which of the following represents the supplied string? Supplied string: "Hello, world!"

Expressions

Having discussed basic data types and their representations, it's important to talk about a word we'll be using a lot of: expressions.

Already simple data representations form basic expressions. Put very simply, an expression is a chunk of code which has a value. An integer, a floating-point number, a character and a string all have a readily apparent value.

Operations on these basic values can yield other values. We can think of this operation and the values it works on as an expression. A very simple example would be basic integer math. A few examples follow.

Or course, the same can be done with floating point numbers, though OCaml uses distinct representations for these operations, and one cannot mix integers and floating-point numbers.

Understanding that one can combine values with operations to form more complex expressions is crucial to becoming a proficient programmer, because it will allow you to pull apart seemingly complex code and understand its constituent pieces.

The composition of expressions is recursive. That is to say, if both 1 and 1 + 1 are expressions, then it stands to reason that any two expressions can be used with +, for instance. Parentheses can be used to group an expression and make it more apparent what is going on. Understanding the order in which operations are applied often renders this unnecessary.

In the case of that last example, we can process the individual expressions that compose it as follows.

Questions

1. Is the following expression valid? 4.3 *. 3

2. How many expressions are present in the following expression? (4.3 *. 2. +. 47.1) /. 2.3 -. 1.2

3. What is the value of the expression in question 2?

Testing Expressions

OCaml's top-level interactive interpreter is a perfect place to test expressions. It provides an immediate response without having to write, compile and run an entire program. It also conveniently shows us the types of expressions.

A snippet from the toplevel follows. The # character is used as a prompt from the interpreter.

# 4 ;;
- : int = 4
# 4 + 1 ;;
- : int = 5
# "hello" ;;
- : string = "hello"
# 1. ;;
- : float = 1.
# 1. +. 3.4 ;;
- : float = 4.4
#

There is little else to be said about this, except of course to encourage experimentation.

Functions

Thus far we know that functions are a way of transforming one piece of data into another. We've also looked at some basic types of data. As we take the next step, we'll see that in a functional programming language like OCaml the two are one and the same, discover a new type of value, and realize that functions are old hat. Let's write our own function.

Functions give a name to a particular transformation of data. However, they don't necessarily need names. Let's look at a function which increments a number x. The fun keyword in the following is a piece of OCaml syntax, as is the arrow (->).

fun x -> x + 1

We can test this in the interpreter. Upon doing so, we'll notice a new type int -> int. This type describes a function which transforms an integer into an integer. Based on the use of +, OCaml can infer that this function is meant to work on the int type.

# fun x -> x + 1 ;;
- : int -> int = <fun>
#

As the left-hand side of a function definition like this can contain any expression, we can easily make this a more complex transformation. Consider, for example, the following.

# fun x -> (x + 1) * 3 - 1 ;;
- : int -> int = <fun>
#

Applying a function

Functions are meant to transform data, but in order to do that, we have to apply the function to a value. This is done quite simply by following the function with a value. The function, being an expression, will be enclosed in parentheses.

# fun x -> (x + 1) * 3 - 1 ;;
- : int -> int = <fun>
# (fun x -> (x + 1) * 3 - 1) 4 ;;
- : int = 14
# (fun x -> (x + 1) * 3 - 1) 10 ;;
- : int = 32
#

The value to which the function is being applied is often known as an argument.

Multiple arguments

Functions are values, and functions transform one value into another. This leads us to the astounding realization that a function can return another function. While functions can take only a single argument, this can be helpful in simulating multiple arguments. Consider the following.

fun x -> (fun y -> x * y)

It's worth noting that OCaml syntax does not strictly require the parentheses.

fun x -> fun y -> x * y

The type of this function would be int -> (int -> int) or eliding the parentheses, int -> int -> int. We can explore and confirm this inference using the interpreter. Please note that again, we were able to elide a set of parentheses in the final application of the function.

# fun x -> fun y -> x + y;;
- : int -> int -> int = <fun>
# fun x -> fun y -> x * y ;;
- : int -> int -> int = <fun>
# (fun x -> fun y -> x * y) 3 ;;
- : int -> int = <fun>
# ((fun x -> fun y -> x * y) 3) 2 ;;
- : int = 6
# (fun x -> fun y -> x * y) 3 2 ;;
- : int = 6
#

Exercise

Write a function which returns the sum of three input floating-point numbers.

Naming

Values, but even moreso functions, are less than useful without having names. By giving values names, we can reuse them easily. This is easily accomplished in OCaml using a let binding. Meaningful names are critical to understanding what a computer program does and how it goes about accomplishing that.

let a = 42

let product = 
   fun x -> fun y -> x * y

# let a = 42 ;;
val a : int = 42
# let product =
     fun x -> fun y -> x * y ;;
val product : int -> int -> int = <fun>
# product a a ;;
- : int = 1764
# let times_two = product 2 ;;
val times_two : int -> int = <fun>
# times_two 5 ;;
- : int = 10
#

It should not be surprising that since the product function returns a function that we can bind the resulting function to another name. It may come as a pleasant surprise, though, that let gives us a more convenient way to create functions.

# let product x y = x * y ;;
val product : int -> int -> int = <fun>
# let times_two = product 2 ;;
val times_two : int -> int = <fun>
# times_two 5 ;;
- : int = 10
#

Scope

Thus far, we've looked at naming which takes effect for the entirety of a program. That is to say, if we give a name of foo to the value 42, it will have that value for the rest of the program. We can use that name for another value later on, even if that value has a different type, but either way, we now have to keep track of that name for the rest of the program.

We can locally bind a name to a value, though, so that it only affects a small subset of the entire program. Consider a function which changes from farenheit to celsius.

# let f_to_c f_temp =
     (f_temp -. 32.) /. 1.8;;
val f_to_c : float -> float = <fun>
# f_to_c 212.;;
- : float = 100.

This works, but the factor to divide by is not documented. We can document it simply by giving it a name.

# let f_to_c f_temp =
     let conversion_factor = 1.8 in
        (f_temp -. 32.) /. conversion_factor;;
val f_to_c : float -> float = <fun>
# f_to_c 212.;;
- : float = 100.

Any further attempt to use conversion factor will fail.

# conversion_factor;;
Characters 0-17:
  conversion_factor;;
  ^^^^^^^^^^^^^^^^^
Error: Unbound value conversion_factor

Functions may also be locally bound.

# let f_to_c f_temp =
     let conversion_factor = 1.8 in
        (f_temp -. 32.) /. conversion_factor
  in
     f_to_c 212.;;
- : float = 100.

All of which leads us to the following being possible. Of course, we probably shouldn't do something like this in this kind of case, but it's still possible, and potentially quite useful for small helper functions with a limited scope of usefulness.

# let c_temp =
     let f_to_c f_temp =
        let conversion_factor = 1.8 in
           (f_temp -. 32.) /. conversion_factor
     in
        f_to_c 212.
  in
     int_of_float c_temp;;
- : int = 100

Another syntax note

I have continued to use ;; with no explanation. This piece of syntax in OCaml programs separates constructs where the separation between them is otherwise ambiguous. There are, however, various situations in which ;; is not necessary, as the separation is unambiguous. let bindings are one such example.

# let product x y = x * y
  let times_two = product 2 ;;
val product : int -> int -> int = <fun>
val times_two : int -> int = <fun>
# times_two 4 ;;
- : int = 8
#

Boolean Expressions

So far we've looked at basic values, arithmetic expressions, and function calls. All of these are expressions, but not all expressions fall into these few types. Among the most useful expressions are boolean expressions: that is to say, expressions which evaluate to either true or false. While arithmetic expressions involved operators like + and -, we'll see some familiars from math in boolean expressions as well.

Program Flow

So far everything we've looked at is very static. Simple expressions can be combined into more useful forms, and things rapidly get interesting, but we're not at interesting yet. Interesting comes when programs can flow in more than one direction, and the direction they'll take isn't known when the program is written.

Key to mastering program flow is to aim for making your logic exhaustive. If it's possible, there should be a way for your program to deal with it. Ocaml is a huge aid to this by forcing any branching in your programs to be exhaustive in most common situations.

If/Else

The first branching structure we'll look at is the simple if/then/else.

let f_to_c f_temp =
   let conversion_factor = 1.8 in
      (f_temp -. 32.) /. conversion_factor;;

let prompt_for_input () =
   print_string "Farenheit temperature: ";
   read_float ();;

let input_temp = prompt_for_input () in
   if input_temp < 32. then
      print_endline "That's cold!  I'm out of here!"
   else
      let celsius_temp = f_to_c input_temp in
         print_string "Celsius temperature: ";
         print_float celsius_temp;
         print_newline ();;

We start by defining two functions. The first is our familiar temperature conversion math. That's boring. It'll always work.

Our second function is a bit of a new one. All fucntions have to take at least one argument. When we don't actually really want to provide an argument, which happens frequently soliciting user input, we can provide the value unit represented by (). We also see the introduction of a single semi-colon. This lone semi-colon chains expressions together. We want to provide a prompt, but that functions itself returns unit as it is doing something rather than manipulating data. Our actual return value is provided by the read_float function.

We put these functions to use by prompting for an input temperature, which we bind to input_temp. We could simply then spit out the converted celsius temperature, but that's a pretty linear form of program flow. Instead we've used an if/else structure to do something different if the input temperature is below the freezing point of water.

It's important to note that the if/else structure is itself an expression, and each branch can only accept one expression, or chained together group of expressions. Knowing this, it becomes possible for use to have more than two branches to this conditional expression. Our else codnition simply needs to itself lead to a conditional expression.

let input_temp = prompt_for_input () in
   if input_temp < 32. then
      print_endline "That's cold!  I'm out of here!"
   else if input_temp >= 212. then
      print_endline "Ouch!  Hot!"
   else
      let celsius_temp = f_to_c input_temp in
         print_string "Celsius temperature: ";
         print_float celsius_temp;
         print_newline ();;

Or:

let input_temp = prompt_for_input () in
   if input_temp < 32. then
      print_endline "That's cold!  I'm out of here!"
   else if input_temp >= 212. then
      print_endline "Ouch!  Hot!"
   else if input_temp = 80. then
      print_endline "That's just right."
   else
      let celsius_temp = f_to_c input_temp in
         print_string "Celsius temperature: ";
         print_float celsius_temp;
         print_newline ();;

Algebraic Data Types

Let's take an aside for a moment to look at another type of data. So far all of our data is very simple values that are all present in the system. We have done nothing to define our own types of data, but being able to do so is a very important skill.

An algebraic data type defines a single type of data, but may have multiple constructors holding anywhere from zero to many additional pieces of data. But how does this apply to our temperature conversion?

Imagine if we weren't simply dealing with floating point numbers, and doing calculations on them. Imagine if our data type was actually temperature.

type temperature = Farenheit of float | Celsius of float

That's valid Ocaml code, and that's it. We now have a temperature data type, with two constructors which each hold onto a floating point number. I can create a piece of temperature data with the following.

Farenheit 43.2

The real question is how I can get back at that information once it's been constructed, and that leads to the next branching mechanism.

Match

Match lets us branch based on patterns of data. Consider a function to convert to celsius.

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | Celsius c -> Celsius c

Here is a perfect example of Ocaml enforcing exhaustiveness. Since temp could have been either a Farenheit or Celsius value, we have to provide a result for both. We can take advantage of this by knowing that if the value input isn't Farenheit, the only other option is Celsius, so we can use a default, signified by an underscore.

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | _ -> temp

Or we can give the default pattern a generic name and reuse that.

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | x -> x

We can create a straightforward rewrite of our previous program using algebraic data types and matching.

type temperature = Farenheit of float | Celsius of float;;

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | x -> x;;

let prompt_for_input () =
   print_string "Farenheit temperature: ";
   Farenheit (read_float ());;

let print_temp temp = 
   match temp with
      Farenheit f ->
         print_float f
    | Celsius c ->
         print_float c;;

let input_temp = prompt_for_input () in
   match input_temp with
      Farenheit f ->
         if f < 32. then
            print_endline "That's cold!  I'm out of here!"
         else if f >= 212. then
            print_endline "Ouch!  Hot!"
         else if f = 80. then
            print_endline "That's just right."
         else
            let celsius_temp = to_celsius input_temp in
               print_string "Celsius temperature: ";
               print_temp celsius_temp;
               print_newline ();;

It's very important, when dealing with control flow, to keep things simple. In the abhove, there are two layers of branching, with an if/then buried within a match. This kind of nesting quickly becomes unwieldy to decipher. It would be better if the two levels could become one. Fortunately, guard conditions on matching provide just this.

type temperature = Farenheit of float | Celsius of float;;

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | x -> x;;

let prompt_for_input () =
   print_string "Farenheit temperature: ";
   Farenheit (read_float ());;

let print_temp temp = 
   match temp with
      Farenheit f ->
         print_float f
    | Celsius c ->
         print_float c;;

let input_temp = prompt_for_input () in
   match input_temp with
      Farenheit f when f < 32. ->
         print_endline "That's cold!  I'm out of here!"
    | Farenheit f when f >= 212. -> 
         print_endline "Ouch!  Hot!"
    | Farenheit f when f = 80. ->
         print_endline "That's just right."
    | Farenheit f ->  
         let celsius_temp = to_celsius input_temp in
            print_string "Celsius temperature: ";
            print_temp celsius_temp;
            print_newline ();;

There is just one note left to make about match for now. IN this last example the match is not exhaustive. As with if/then, Ocaml does not strictly enforce exhaustive matching when the return type is unit, though it will provide a warning.

Errors

Ocaml does a very good job of helping programmers avoid compile-time errors, but there is another area for problems with the flow of a program: run-time errors.

Consider the last example program. We've accounted for everything... except what happens when the program is actually run. In this case, the wildcard is the read_input function. We assume the user will input a valid floating point number, but they don't have to. There could be a typo, or just gibberish.

# read_float ();;
foo!
Exception: Failure "float_of_string".
#

Ocaml is telling us that trying to turn the string "foo!" into a floating point number failed. Having done so, Ocaml raised an exception, disrupting the program's flow. If this happened in the middle of the program written above, nothing would happen after the input is entered.

Fortunately, exceptions can be handled. Handling an exception gives you the option of doing something constructive when an error occurs, rather than simply having the program give up.

This will look an awful lot like matching, because exception handling gives you the option to handle multiple types of exceptions.

# try
     read_float ()
  with Failure _ -> 0.;;
foo!
- : float = 0.
#

The above is very simple. When a failure occurs (and we don't care about matching the reason since we know only one option is possible) the expression simply returns a zero. But this probably isn't very useful. It keeps the program from failing, but it doesn't get us what the user wanted.

Let's try something that asks again.

# let rec read_input () =
     try
        print_string "> ";
        read_float ()
     with Failure _ ->
        print_endline "Oops! Try again.";
        read_input ();;
val read_input : unit -> float = <fun>
# read_input ();;
> foo!
Oops! Try again.
> t
Oops! Try again.
> 5
- : float = 5.
#

That does it, but there's something new, and hugely important there.

Recursion

Branching is important, but we also frequently need to repeat actions in a computer program. An important way to accomplish this is by using recursion. We know functions can call each other. Recursion involves one function calling itself. By doing so, the program can repeat an action.

In the previous example, the rec keyword denotes a recursive function that will call itself.

To better understand how this works, it's important to understand what happens in a computer when a function is called.

When a function is executed by a program, information relevant to the function is pushed onto the end of the stack. The stack is a finite area of computer memory. At the completion of a function, the information relevant to it is effectively removed from the stack.

If this process is managed successfully, we don't have to worry about the space being finite. It's unlikely even several functions will overflow that space, causing an error. Unfortunately when a program loops many many times using recursion, it can be possible to run into this problem.

Fortunately the previous example actually demonstrates how to avoid this issue. Ocaml (and other languages) automatically optimize for recursion when the function's call of itself is the last thing it does. Since it's the last thing happening in the function, nothing in the caller function remains relevant, so it can be eliminated from the stack. Many recursive functions can be rewritten to take advantage of this.

A simple function we can look at to see this is calculating a factorial.

# let rec fact x =
     if x = 0 then
        1
     else
        x * (x - 1);;
val fact : int -> int = <fun>
# fact 12;;
- : int = 132
#

For a large enough value of x this will cause problems, since the execution of this looks like:

fact 12
12 * fact 11
12 * 11 * fact 10
12 * 11 * 10 * fact 9
...

Whereas, if we use an accumulator, we can make sure the last fucntion call in the function is the recursive call.

# let rec fact' x acc =
     if x = 0 then
        acc
     else
        fact' (x - 1) (acc * x);;
val fact' : int -> int -> int = <fun>
# fact' 4 1;;
- : int = 24
#

But since it's troublesome to have to remember to pass the accumulator argument, we can wrap it in another function.

# let fact x =
     let rec fact' x acc =
        if x = 0 then acc
        else fact' (x - 1) (acc * x)
     in
        fact' x 1;;
val fact : int -> int = <fun>
# fact 4;;
- : int = 24
#

Now the function call looks like the following.

fact 4
fact' 4 1
fact' 3 4
fact' 2 12
fact' 1 24
fact' 0 24
24

Recap

So we have if/then, matching, algebraic data types, and we know how to handle errors. Let's revisit the program written previously.

type temperature = Farenheit of float | Celsius of float;;

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | x -> x;;

let print_temp temp = 
   match temp with
      Farenheit f ->
         print_float f
    | Celsius c ->
         print_float c;;

let rec prompt_for_input () =
   try
      print_string "Farenheit temperature: ";
      Farenheit (read_float ())
   with Failure _ ->
      print_endline "Invalid input. Try again.";
      prompt_for_input ();;

let input_temp = prompt_for_input () in
   match input_temp with
      Farenheit f when f < 32. ->
         print_endline "That's cold!  I'm out of here!"
    | Farenheit f when f >= 212. -> 
         print_endline "Ouch!  Hot!"
    | Farenheit f when f = 80. ->
         print_endline "That's just right."
    | Farenheit f ->  
         let celsius_temp = to_celsius input_temp in
            print_string "Celsius temperature: ";
            print_temp celsius_temp;
            print_newline ();;

This program is almost entirely exhaustive. Even the user inputting a bad number is handled. Unfortunately, there is absolute zero (-459.67F), so we should probably handle that as an error. We can raise an exception, then handle it appropriately.

type temperature = Farenheit of float | Celsius of float

exception Below_absolute_zero of float

let absolute_zero = -459.67

let to_celsius temp =
   match temp with
      Farenheit f -> Celsius ((f -. 32.) /. 1.8)
    | x -> x

let print_temp temp = 
   match temp with
      Farenheit f ->
         print_float f
    | Celsius c ->
         print_float c

let rec prompt_for_input () =
   try
      print_string "Farenheit temperature: ";
      let input_temp = read_float () in
         if input_temp < absolute_zero then
            raise (Below_absolute_zero input_temp)
         else
            Farenheit input_temp
   with 
      Failure _ ->
         print_endline "Invalid input. Try again.";
         prompt_for_input ()
    | Below_absolute_zero temp ->
         print_float temp;
         print_string "F is too cold.";
         print_newline ();
         prompt_for_input ();;

let input_temp = prompt_for_input () in
   match input_temp with
      Farenheit f when f < 32. ->
         print_endline "That's cold!  I'm out of here!"
    | Farenheit f when f >= 212. -> 
         print_endline "Ouch!  Hot!"
    | Farenheit f when f = 80. ->
         print_endline "That's just right."
    | Farenheit f ->  
         let celsius_temp = to_celsius input_temp in
            print_string "Celsius temperature: ";
            print_temp celsius_temp;
            print_newline ()

More on Recursion and First Class Functions

Recursion plays an important role in the flow of evaluation of computer programs. It permits elements of a program to repeat themselves. We've already seen an example of that in the prompt_for_input function.

But this was just one function. A customized solution was designed. What if we could create a generic solution that would abstract out common actions, and feed it a function as a value to do a specific calculation or action. Since Ocaml functions are themselves values, and we can pass values to functions as arguments, this is possible.

First let's write a function which prints a number a certain number of times. Both will be provided by an argument.

# let rec print_int_times n x =
     if n > 0 then
        (print_int x; 
         print_newline (); 
         print_int_times (n - 1) x);;
val print_int_times : int -> int -> unit = <fun>
# print_int_times 4 5;;
5
5
5
5
- : unit = ()
#

And now a function which prints a string a certain number of times.

# let rec print_string_times n s =
     if n > 0 then
        (print_endline s; 
         print_string_times (n - 1) s);;
val print_string_times : int -> string -> unit = <fun>
# print_string_times 4 "foo!";;
foo!
foo!
foo!
foo!
- : unit = ()
#

There's a common bit of logic here. Let's abstract it out into a function.

# let rec do_times n f =
     if n > 0 then
        (f ();
         do_times (n - 1) f);;
val do_times : int -> (unit -> 'a) -> unit = <fun>
# do_times 4 (fun () -> print_endline "foo!");;
foo!
foo!
foo!
foo!
- : unit = ()
#

Answers

Data Representation

1. c

2. c

3. b

Expressions

1. no, it isn't

2. e

3. approximately 23.0173