M05: Semantics



One of the things we like about using a functional programming language is that we can describe easily and precisely what a program does when it’s executed. This lecture module lays the groundwork for those descriptions.

We’ve already been easing into these descriptions. Remember the way we did substitutions on a math expression (and then Racket expressions) to transform them into simpler expressions? Remember the two rules we had (arguments to functions must be simple values and if given a choice, go left to right)? We’re building on that.

If you run a program multiple times with exactly the same inputs, it better do the same thing every time. This is what we mean by “a program has a precise effect”.

But even if you can’t actually run the program (perhaps it’s a brand new language and those tools haven’t been developed yet; perhaps you’re in the midst of a power outage), it still has a precise meaning. An experienced programmer can look at it and say “Oh, I understand this program!”.

A model provides a way of understanding something, in this case a program. The model is not necessarily the way DrRacket will execute the program, but it provides a way to predict the result that is (hopefully!) easier for humans to understand than the internals of DrRacket.

The Java language specification is 774 pages long.

The core of what you need to know for Racket is can be summed up in about two dozen substitution rules. The first 14 appear towards the end of this module’s slides.

Our model starts with how you spell valid “words” in the language. For example, can you use 123 as the name of a parameter? No. Can you use 123go!? Yes.

If you’ve programmed before, you may be surprised at how flexible Racket is with the names of things.

Syntax has to do with the form or structure of something. The sample sentence does not have the expected structure – first word begins with a capital letter, punctuation at the end, etc.

“Trombones fly hungrily.” is a syntacticly correct sentence. It has the expected form/structure. But semantically it is meaningless. Trombones don’t fly nor do they get hungry. Note that we are referring in this example to the real world rather than a constructed world in a fantasy novel or poetry where there might be flying hungry trombones.

That said, the semantics of our programs will be with respect to the constructed world of our programming language.

English can be ambiguous. In “Sally was given a book by Joyce” it’s unclear whether the person giving the book was named Joyce or the person who wrote the book was named Joyce.

Another example is “Time flies like an arrow”. One possible meaning is that time passes quickly. But another meaning parallels the sentence “Fruit flies like a banana.” There are several other possible meanings as well.

Of the three problems on the previous slide, we’re going to deal with semantics rigorously.

This slide and the next are here to say that we can deal with syntax and ambiguity rigorously as well – but we’re not until later courses. Semantics is important to us in CS135; syntax and ambiguity considerably less so.

It’s very helpful to be able to predict what a program will do while you are writing it. If you can’t, you’re no better than one of those proverbial monkeys banging on a typewriter trying to come up with Shakespeare.

We’ve already used this substitution model in our earliest math examples. Given 1 + 2 * 3, our first step is to take a subexpression such as 2 * 3, solve it, and then substitute the result back into the original expression to get 1 + 6. Again, take a subexpression (the only one left), solve it and substitute the result back to get 7. That’s as simple as it gets, so stop.

This is illustrated interactively (using Racket notation):

When we introduced functions in lecture Module 02, we developed two rules:

  1. When substituting a function application with the function’s body, all arguments must be values. Recall that values are numbers (7, 22/7, 3.14159), symbols ('earth, 'female), Booleans (true, false), or strings ("Hello, world!").
    For example, (g 3 4) is ready to have (+ 3 4) substituted in its place while (g 3 (+ 2 2)) is not ready.
  2. When given a choice of which subexpression to evaluate and substitute back, choose the left-most subexpression. For example, in (g (+ 1 1) (* 2 2)) we have the choice of evaluating either (+ 1 1) or (* 2 2). This rule says to choose (+ 1 1).

We now introduce a third substitution rule.

Essentially, the rule says that we just “know” what the built-in functions do. It might be because we’ve studied them since early grade school (+, *, etc) or because we’ve read the DrRacket documentation (string<?). Use this knowledge to compute the result for the given arguments (which will, of course, be values due to the first rule) and then substitute that result into the expression in place of the function application.

In the stepper, this rule has the name “as-if-by-magic” because we don’t try to explain how the built-in function works.

We can’t claim to just “know” what a user-defined function does, so we need a new rule (our fourth).

A Racket program is read top-to-bottom, left-to-right. That is,

(define (foo x y) (+ x x y))
(foo 1 2)

is read as

(define (foo x y) (+ x x y))  (foo 1 2)

The function definition is already as simple as it gets, so (foo 1 2) is the left-most subexpression that we can simplify. Furthermore, (define (foo ... occurs to its left, as required by the substitution rule.

Evaluating (foo 1 2) means substituting the first argument (1) wherever the first parameter (x) occurs in the body expression and doing similarly for the second argument/parameter. That gives us (+ 1 1 2). That expression is substituted back in place of (foo 1 2).

That is,

(define (foo x y) (+ x x y))  (foo 1 2) =>
(define (foo x y) (+ x x y))  (+ 1 1 2)

Recall that => means “yields” and separates one substitution step from another.

Or, with the stepper. You’ll notice in the “Rule” section that it calls this rule “Big-sub”. We’ll have another rule named “Small-sub” soon.

Rules so far:

  1. Apply functions only when all arguments are values.
  2. When given a choice, evaluate the leftmost expression first.
  3. (f v1...vn) => v when f is built-in…
  4. (f v1...vn) => exp' when (define (f x1..xn) exp) occurs to the left…

An in-depth explanation of the trace shown in the slide:

Substitution Step Explanation
(term (- 3 1) (+ 1 2)) The first rule says we can’t use rule 4 on term. The second rule says to choose (- 3 1). Use the third rule to reduce it to 2.
(term 2 (+ 1 2)) The first rule says we can’t use the fourth. The second rule says to choose (+ 1 2). Use the third rule to reduce it to 3.
(term 2 3) The first rule says that we can use the fourth rule. Substitute 2 (the first argument) everywhere x occurs in term's body expression. Similar for 3 and y. Substitute that rewritten body expression back.
(* 2 (sqr 3)) Use the third rule for built-in functions to evaluate (sqr 3) and substitute it back.
(* 2 9) Use the third rule for built-in fuctions.
18 18 is a value, so we’re done.

Function definitions are always in simplest form and aren’t further reduced. That’s not necessarily the case with constant definitions. Notice that the right hand side of id => val is a value. If the expression starts as (define p (* 3 3)) the (* 3 3) must be simplified to 9 first.

This is illustrated in the stepper with the next slide. Note that the stepper gives this rule the name “small-sub”. For both a constant and a user-defined function we’re making a substitution. For the constant, it’s a pretty small substitution; for a function, it’s always much bigger.

The convention that we stop repeating a definition is represented in the stepper by moving the definition above the blank line. Without this convention we would need to copy the entire program for every step. This convention will benefit you big time when it comes to writing exams!

Rule #2 – choose the left-most subexpression to simplify – means that the question part of a cond's question/answer pair will always be reduced to either true or false before we apply one of the three rules for cond.

These three rules are “context sensitive”. The rule to apply depends on the context. Use the first rule if the first question/answer pair evaluated to false. Use the second rule if the first question/answer pair evaluted to true. Use the third rule if the first question/answer pair is else.

Remember that cond is a special form. It looks like a function application but the arguments are not necessarily evaluated. In this case the question argument is evaluated but the answer argument is not.

If y is not defined…

DrRacket also has a stepping tool. However, it occasionally uses rules that are different than ours. When we ask you to step through code on an exam (and we will!), you must use our rules rather than DrRacket’s.

Why are the rules different? The implementers of DrRacket appear to be focused on making the results as shown in DrRacket as easy to understand as possible. CS135 places a greater emphasis on knowing and applying the rules, so we’ve made the rules themselves as simple as possible.

Syntax errors and run-time errors occur at different times in the processing of the code.

The interactive pane of DrRacket implements a Read-Eval-Print-Loop (REPL). A syntax error occurs in the Read phase of that loop. DrRacket can’t interpret what it reads because the form is wrong. It has misspellings, missing parentheses, invalid function applications, etc.

A run-time error occurs during the Evaluation phase of the REPL. DrRacket is applying its rules and runs into a situation where none of them apply. It might be division by zero, a cond with no question that returns true, running out of memory by raising a number to an incredibly large power, etc.

The and rules work by looking at the first argument. If the first argument is false then the entire expression is false. The answer is known, so produce it (the first rule).

If the first argument is true then the entire expression might be true, depending on the other arguments to and. So throw away the first argument and evaluate the rest of the and-expression (the second rule) to find the value of the entire expression.

If all of the arguments are “thrown away” then they all evaluated to true and the entire expression is true (third rule).

The rules for or are very similar to and.

Because and and or expressions produce Boolean values they can be nested. For example,

These fourteen rules explain practically everything we’ve learned so far about how Racket evaluates a program. They define precisely what a program means (by reducing it to a sequence of definitions and values).