Ballad of a Duck
From Compsci.ca Wiki
Contents |
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.
| 42 |
| -6 |
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.
| 3.14159 |
| -5.4 |
| 7.0 |
| 7. |
| 0.2378 |
| 1.23e-5 |
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.
| 'a' |
| 'Z' |
| '4' |
| '"' |
| '\ |
| ' ' |
| '\n' |
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.
| "" |
| "a" |
| "Ballad of a Duck" |
| "Ballad of a Duck\n" |
| "\"Ballad of a Duck\"\n" |
Questions
1. Which is an integer?
| a) | 4. |
| b) | 1.3 |
| c) | 27 |
2. Which is a valid character representation?
| a) | '' |
| b) | '\N' |
| c) | 'R' |
3. Which of the following represents the supplied string? Supplied string: "Hello, world!"
| a) | "Hello, world!" |
| b) | "\"Hello, world!\"" |
| c) | "'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.
| 1 |
| 1 + 1 |
| 3 - 2 |
| 4 * 5 |
| 8 / 4 |
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.
| 1.0 |
| 1.0 +. 1.3 |
| 3. -. 2.1 |
| 4.6 *. 5.2 |
| 8.7 /. 3. |
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.
| 1 |
| 1 + 1 |
| (1 + 1) + 3 |
| 1 + 1 + 3 |
| (1 - 2) * (3 + 2) |
| (1 - (1 + 1)) * (3 + 2) |
In the case of that last example, we can process the individual expressions that compose it as follows.
| (1 - (1 + 1)) * (3 + 2) |
| (1 - (2)) * (5) |
| (1 - 2) * 5 |
| (-1) * 5 |
| -1 * 5 |
| -5 |
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
| a) | 2 |
| b) | 3 |
| c) | 4 |
| d) | b and c |
| e) | a, b and c |
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.
| = and <> |
| > and >= |
| < and <= |
| || |
| && |
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 rewqrite 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 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_float 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 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_float celsius_temp;
print_newline ();;
Answers
Data Representation
1. c
2. c
3. b
Expressions
1. no, it isn't
2. e
3. approximately 23.0173
