M02: Functions



This lecture module is the start of the actual course content. It has more video content than will be typical because there is some stuff that’s easier to just show, some that benefits from body language, and some that is simply important to reinforce for multiple learning styles.

We start with programming language design and why we’ve chosen a functional programming language (Racket) rather than a more traditional choice. We then review some of the core concepts that functional programming languages borrow from mathematics.

Video: Download m02/m02.00_pl_design

video m02/m02.00_pl_design

The following video introduces the DrRacket programming environment and the core features to get you started programming.

Video: Download m02/m02.10_dr_racket

video m02/m02.10_dr_racket

You will be changing language levels periodically as you become a more experienced programmer. Changing these settings, in this manner, will be required each time.

Rational numbers are those that can be represented as a ratio between two integers. For example, 22/7. Irrational (“inexact”) numbers cannot be written as a fraction. Examples include π and the square root of 2.

A calculator doesn’t make much distinction between the rational and irrational numbers. A calculator displays π as 3.141592654 and 22/7 as 3.142857143. There is nothing to distinguish the rational number from the irrational number.

Racket does make the distinction. Use rational (“exact”) numbers whenever you can.

Video: Download m02/m02.20_functions_in_math

video m02/m02.20_functions_in_math

The nth argument is associated with the function’s nth parameter. For example, in g(1,3), the first argument (1) is associated with the first parameter (x). Each place that x is used, substitute 1. Similarly for 3 and y.

“Evaluation by substitution” means to take a subexpression, find its value, and then replace the subexpression by the value (that’s the “substitution” part). Repeat until you’re left with just values.

If you choose a complicated subexpression you may need to use “evaluation by substitution” to find its value.

This notion of evaluation by substitution is an important one. In lecture module 05 we’re going to spend the entire module defining rules to make this rigorous. We’ll add to those rules throughout the course. You’ll get the first taste of them in just a few slides.

For example, consider g(g(1,3), f(3)) again. We can’t apply g to g(1,3) and f(3) because of the first rule – g(1,3) and f(3) are not values.

So we have a choice to make. Should we evaluate the subexpression g(1,3) or f(3) first? The second rule says to do the leftmost one or g(1,3).

Stated another way: read the expression from left to right, top to bottom.
Substitute the first function application that has fully evaluated arguments.

Review the derivation two slides back. Verify that these two rules were obeyed at each step.

This video is the transition from mathematical notation to Racket notation. The slides give a good overview of the changes. The video can help solidify your understanding of how to transform the traditional mathematical notation to Racket notation.

Video: Download m02/m02.30_notation

video m02/m02.30_notation

To transform from traditional mathematical notation to Racket notation, proceed as if you were evaluating the expression via substitution. But instead of substituting back the value, substitute the expression re-written as Racket.

For example:

(6 - 4) / (5 + 7) =>
(- 6 4) / (5 + 7) =>
(- 6 4) / (+ 5 7) =>
(/ (- 6 4) (+ 5 7))

Note that the first line is valid math; the last line is valid Racket; the middle lines are a mixture.

You can test your understanding by translating these expressions to Racket. Then enter them into DrRacket to verify that they give the correct answer.

An example of “extra” parentheses in math: (1 + 2). The parentheses add nothing to simply writing 1 + 2. If you translate this literally you would get the Racket expression ((+ 1 2)). The outside set of parentheses will cause Racket to “think” it needs to apply a function, but there is no function specified to apply.

We also have a tool to show the substitution process interactively. Play around with the following to see how it corresponds to what is on the slide and how it implements the rules we’ve seen so far.

Here’s a direct link to the Help Desk documentation. Bookmark it! For technical documentation that’s a better strategy than Googling it every time. Less risk of getting out-of-date material.

It’s a great idea to fire up DrRacket and enter these into the interactions window. Learning what the various error messages mean on these small examples will help you debug your assignment problems more efficiently.

The third one is “interesting”. Watch the video to understand what’s going on.

Defining functions is the core activity in programming in Racket. This video covers the syntax, reviews applications of functions to arguments, defining constants, etc.

Video: Download m02/m02.40_def_functions

video m02/m02.40_def_functions

Special forms are typeset just a little differently in the slides. A special form, like define is in a bolder and slightly darker font than a normal function. If you skip ahead to M04 you’ll notice that and, or, and cond are typeset the same way. They’re also special forms. Unfortunately, we’re not completely consistent. else is also typeset this way but is not a special form.

Verify that the two rules given are used to choose the next subexpression to evaluate.

The fact that parameter names are local to the function is really handy. It means that you can choose their names without regard for the rest of the program. You can focus on deciding which names make sense for the function, given its purpose.

The parameter names as used in the slides so far won’t be acceptable once we move beyond toy examples to functions that do something meaningful. Then we’ll want parameter names that convey meaning about their purpose in the function.

We can see this example in action in the following stepper. Note that completely processed definitions that will not change are at the top of the listing followed by a blank line. k is already completely defined and starts out above that blank line.

p will move up after it’s completely defined in the fouth step. foo is also completely defined but doesn’t get to move up until the definitions preceding it are completely defined.

See the video for a more complete description of scope. The next video shows how DrRacket can help you determine the scope of an identifier.

The x parameter in function f is said to “shadow” the global constant x.
Another way to say it is that x “hides” the global constant.

This video is almost entirely in DrRacket to show you the definitions window and how to use it to define functions. There are a number of tools built into DrRacket that are covered:

  • a stepping tool that may be helpful for debugging your functions
  • a tool to help you with scoping issues
  • a feature that helps you identify code that hasn’t been tested (making sure everything is tested is a core skill for earning a high mark in CS135!)
  • a feature that automatically formats/indents your code for you.

Video: Download m02/m02.50_programming

video m02/m02.50_programming