it-ebooks - Data Structures and Functional Programming Lecture Notes (Cornell CS3110)

CS 3110 Fall 2014 :: Data Structures and Functional Programming

We will use the Objective Caml (OCaml) programming language this semester. OCaml is a functional language rather than an imperative language; the key difference between these two classes of languages is the execution model---the way in which programs are executed. Imperative (or procedural) languages, such as C and Java, are based on commands that change the state of the machine on which they execute. For example, the assignment statement (in both C and Java) explicitly changes the value stored in some memory location. Functional languages, in contrast, are based on evaluating expressions to produce values. OCaml provides good ways to build correct, understandable, and large expressions. The focus of this lecture is understanding expressions.

For real applications, programming with expressions may seem like a stretch. After all, applications often do not "compute" anything; instead, they allow you to "do" something. Later in the course, we will introduce the notion of side-effects: evaluate this, and do that while you're at ite.g., evaluate an expression, and (as a side-effect) display a window on the screen. But for the moment, we will live in a pure world, one without side-effects.

To start learning OCaml, you should begin playing with the OCaml language by writing toy expressions. Like most programming languages, Ocaml has a compiler that can be run on source files to produce object files. But to really understand expressions, there is a better way to interact with the OCaml compiler, called the OCamltoplevel system. This system is something like a very fancy calculator---you interact with it by typing in an expression, and it responds by evaluating that expression and telling you the resulting value.

---

IMPORTANT NOTE: In previous semesters, this course has been taught in SML, a language very similar to OCaml. They share both a common origin and almost all of their syntax. For aid in understanding notes from previous years, you might wish to consult the SML vs. OCaml page, which provides a detailed list of the differences between the two.

If you notice any SML/OCaml discrepancies in the notes, please let us know.

---

Starting the OCaml toplevel system. The course page has instructions for installing OCaml. Once you have OCaml properly installed, you will be able to start an interactive session by typing ocaml at the terminal (i.e., a Unix shell or Windows console). (The 3110 VM has an enhanced version of ocaml called utop installed.) You will get a top level prompt "#", which indicates that the compiler is ready to accept expressions and evaluate them. To exit the toplevel system, enter the end-of-file character for your platform (Ctrl-D on Unix, Ctrl-Z + Return on Windows).

Using theOCaml toplevel system. Type in an expression (possibly on multiple lines, which after the first line will have a secondary prompt "="), then type ;; and press Return. Note that the ;; is not part of the expression to be evaluated. It is simply an indication to the compiler that you have finished typing in the expression and that you are ready to evaluate. Before evaluating the expression, the compiler will type check it.

TIP: The toplevel system is very picky about some things when reading input, and will accept a request to exit only if it is sitting exactly at the top level prompti.e. if nothing else has been already typed in. When in doubt (especially if input seems to be behaving strangely), press Ctrl-C to interrupt and reset the prompt to a sane state.

TIP: It can be useful to put expressions into a file so that you're not stuck entering them over and over again at the prompt. Just use an editor to edit a file, and you can load it into OCaml with the operation #use "file";; which behaves as though the expressions have been entered at the top level prompt (don't forget the semicolons!). The big question is where should the file be stored. Operation #use by default looks for files in the current working directory. To change the current working directory, use the operation #cd "path";; where path is the path where you want to go to. To add a directory to the list of directories that OCaml looks for files in, use the operation #directory "path";;. Use the Unix convention (even on Windows): the path separator is "/".

TIP: Even more details on the toplevel system can be found at the OCaml manual page on it.

---

Expressions evaluate to values. Values can be classified according to their type:

Let us start looking at simple expressions, with the following syntax:

e ::= c | unope | e1binope2 | if e1 then e2 else e3 | (e)

where c are constants (the values described above), unop are unary operations, binop are binary operations. We expressed this syntax using Backus-Naur Form (BNF), a common notation for the grammar of computer languages. NOTE TO INSTRUCTOR: The BNF for expressions, and later for declarations, should be put on one side of the board, and kept there as we will be adding expression types and declaration types as the section proceeds.

Unary operators include:

Binary operators include:

Expressions are transformed into values by the application of evaluation rules. The evaluation rules for simple expressions are:

• Constants are already values.
• Unary and binary operators first evaluate their arguments to values, and then perform the operation.
• A conditional if e1 then e2 else e3 evaluates e1 to a vallue (of type bool): if it is true, e2 is evaluated, if it is false, e3 is evaluated.

Evaluation of operators only makes sense if the types of the operands agree. For example, the + operator is defined if both operands are integers, but adding an integer to a boolean is meaningless. So type checking is performed to ensure that expressions are meaningful, and this requires giving a type to every expression. How does OCaml determine the type of an expression?

Every constant has a type (42 has type int, true has type bool, etc). Operators also have types (which we gave informally above); in OCaml syntax, these types are as follows:

- : int -> int (* or *) float -> float not : bool -> bool + : int -> int -> int +. : float -> float -> float > : int -> int -> bool (* or *) float -> float -> bool ^ : string -> string -> string