Built with from Grav and Hugo
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
“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.
1 + 2 * 3
2 * 3
1 + 6
This is illustrated interactively (using Racket notation):
When we introduced functions in lecture Module 02, we developed two rules:
(g 3 4)
(+ 3 4)
(g 3 (+ 2 2))
(g (+ 1 1) (* 2 2))
(+ 1 1)
(* 2 2)
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.
(foo 1 2)
(define (foo ...
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).
(+ 1 1 2)
(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:
(f v1...vn) => v
(f v1...vn) => exp'
(define (f x1..xn) exp)
An in-depth explanation of the trace shown in the slide:
(term (- 3 1) (+ 1 2))
(- 3 1)
(term 2 (+ 1 2))
(+ 1 2)
(term 2 3)
(* 2 (sqr 3))
(* 2 9)
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.
id => val
(define p (* 3 3))
(* 3 3)
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).