How Pyret runs your program

Ten rules. Everything Pyret does with the code you write is one of these, and you can work out what a program does on paper by applying them in order.

Rules 1 to 7 are all the Pyret on Progress Exam 1. Rules 8 to 10 arrive on Wednesday, September 16, and are not on it.

Pyret keeps a directory: a list of names, and the value each one stands for. You cannot see it, so it is worth keeping on a sheet of paper beside you.

The first seven rules

  1. An expression is evaluated, and its value is displayed.
  2. A definition, name = expression, evaluates the right-hand side first, then puts the value in the directory under that name. Nothing is displayed.
  3. A name used in an expression is looked up in the directory and replaced by its value.
  4. A function definition puts the function’s code in the directory under its name. The body does not run. Nothing is displayed, apart from a report on the where: examples.
  5. A function call is replaced by the body of the function, with the argument values substituted for the parameter names. Pyret then carries on evaluating the result.
  6. An if expression evaluates its question first, down to true or false. The whole expression is then replaced by one of its branches — the one the answer selected — and the others are never evaluated at all. With else if, the questions are tried in order and the first true wins.
  7. A cases expression evaluates the list first, down to a value. Every list is one of two shapes — empty, or link(first, rest) — and the shape picks a branch the way the question picks one in rule 6. The whole expression is replaced by that branch’s body, with the pieces of the value substituted for the branch’s names, the way rule 5 substitutes arguments for parameters. The other branch is never evaluated.

Rule 7 is rules 5 and 6 doing their usual jobs at the same time, which is why cases needs no new machinery to trace.

What f and r stand for

[list: 4, 10] is another way of writing link(4, [list: 10]). So in

| link(f, r) => 1 + my-len(r)

f becomes 4, and r becomes [list: 10] — a list, not 10. The rest of a list is always a list, which is what lets my-len call itself on it. The rest of [list: 20] is [list: ], and that is where the empty branch finally gets used.

Writing my-len(10) where my-len([list: 10]) belongs is the slip to watch for. If a trace ever reaches a number where a list should be, this is the step to go back to.

A trace, one substitution per line

Given my-len as we wrote it in class:

fun my-len(l :: List<Number>) -> Number:
  doc: "how many elements are in this list"
  cases (List) l:
    | empty => 0
    | link(f, r) => 1 + my-len(r)
  end
end

my-len([list: 4, 10]) goes like this.

my-len([list: 4, 10])

# rule 5 --- the call becomes the body, with [list: 4, 10] put in for l
cases (List) [list: 4, 10]:
  | empty => 0
  | link(f, r) => 1 + my-len(r)
end

# rule 7 --- that list is link(4, [list: 10]), so the second branch wins,
#            with 4 for f and [list: 10] for r
1 + my-len([list: 10])

# rules 5 and 7 again, on the shorter list
1 + (1 + my-len([list: ]))

# rule 7 --- [list: ] is the empty shape, so this time the first branch wins
1 + (1 + 0)

1 + 1
2

Nothing above is a new kind of step. Every line is the line before it with one substitution made, which is the whole method.

Three consequences that catch everyone once

  • Pressing Run empties the directory first, then reads your file from the top down — so a name is only usable below the line that defines it.
  • A value is only in the directory if you named it. An image built in the middle of a larger expression is drawn, and then it is gone.
  • One value per name. Defining a name twice is an error: Pyret says the declaration “is preceeded in the same scope by another declaration also named x”, and nothing runs at all until you rename one of them.

Rules 8 to 10 — when a name can change

From Wednesday, September 16. Not on Progress Exam 1.

  1. A variable definition, var name = expression, does what rule 2 does — evaluate the right-hand side, put the value in the directory — and marks that entry as one which is allowed to change later.
  2. An assignment, name := expression, evaluates the right-hand side, then replaces what that name stands for in the directory. It adds nothing, and the old value is gone. The name has to be there already, and it has to have been made with var.
  3. A for each expression runs its body once for every element of the list, putting that element in the directory under the loop’s own name each time round. It gives back nothing. Anything you want to keep has to go into a var you made before the loop.

What they break

Rule 3 is still true, and that is the trap in it. You still look a name up and replace it by its value — but only by the value it has at that moment. Until now a name meant one thing for the whole program, so you could make the substitutions in any order. From rule 8 on, a trace has to run in order, and you redraw the directory after every line that changes it.

That is also what lifts the third consequence above. var is how a name gets a second value.

A loop, one directory per step

var running = 0
for each(n from [list: 5, 1, 7, 3]):
  running := running + n
end
# rule 8                     running → 0
# rule 10, first element     running → 0    n → 5
# rule 9                     running → 5    n → 5
# rule 10, next element      running → 5    n → 1
# rule 9                     running → 6    n → 1
# rule 10, next element      running → 6    n → 7
# rule 9                     running → 13   n → 7
# rule 10, next element      running → 13   n → 3
# rule 9                     running → 16   n → 3
# the list is finished, and the whole for each gives back nothing

The answer is 16, and it is in running — not in what the loop gave back. To use it you name running on the line after end.

block:, and why Pyret asks for it

A function whose body is more than one expression has to say so:

fun sum-loop(l :: List<Number>) -> Number block:

Without block: Pyret stops with “contains a block that contains multiple expressions”. Every function you have written so far was one expression, so this is the first time it comes up — and it comes up here because a sequence of steps is only worth writing when some of them change something.