Why well-typed programs cannot go wrong

Computing · Computer Systems · ages 23-24

Name ______________________ Date ____________

What does progress promise for a closed well-typed expression?
- It reaches a final value after a fixed number of steps
- It is already a value or has an allowed evaluation step
- It evaluates faster than every expression without a type
In the lesson's expression language, what does the rule 4 + 5 -> 9 assert?
- One permitted evaluation step replaces 4 + 5 with 9
- Every expression in the program must finally return 9
- The addition takes exactly nine units of processor time
Preservation requires every step from an expression of type T to produce another expression of type T.
Circle one: True False
A closed well-typed expression evaluates to 12, while its task specification requires 13. Every step retains its type and no expression in the run is stuck. Does the result alone refute type soundness?
- No; soundness does not promise the task's intended answer
- Yes; soundness requires every typed computation to meet its task specification
- Yes; reaching an integer value shows that progress failed during evaluation
An extension assigns type Int to closed expression deref(null). It is not a value and has no evaluation or exception rule. Which obligation fails?
- Preservation, because every allowed step changes its type
- Neither, because a typed expression may be stuck without a value
- Progress, because this typed non-value has no allowed step
Under the stated expression semantics, a closed well-typed start reaches a stuck expression. Evaluation retains closedness. What does that refute?
- Only a speed guarantee, since soundness permits reachable stuck states
- The joint soundness guarantee; progress or preservation must fail
- Only a termination guarantee, since stuck expressions are final values
The closed expression 2 + false is ill-typed and stuck in the basic language. Does its being stuck refute progress?
- No; progress's well-typed-expression hypothesis is absent
- Yes; progress requires every closed expression to have a step
- Yes; an expression becomes well-typed whenever evaluation stops
A new closed expression flip(7) has type Bool. Its rule is flip(7) -> 8, and 8 has only type Int. Which obligation fails even though this execution reaches a value?
- Progress: a typed expression must never reduce to an integer value
- Neither: reaching any value permits every change of type during evaluation
- Preservation: the step does not retain the starting type Bool

Answer key

For grown-ups. Fold this page away before handing over the rest.

Why well-typed programs cannot go wrong W1-mt_nAAHVPNaVJ-s1

It is already a value or has an allowed evaluation step · Progress excludes a stuck closed well-typed expression at the current point. It gives no speed or termination bound.
One permitted evaluation step replaces 4 + 5 with 9 · The arrow denotes one evaluation step. It does not state a whole-program result or a timing measurement.
True · If t has type T and t steps to t', preservation requires t' to have type T too.
No; soundness does not promise the task's intended answer · Type soundness excludes reachable stuck expressions under the language's rules. It does not establish the task-specific requirement to return 13.
Progress, because this typed non-value has no allowed step · The expression is closed and well-typed, but is neither a value nor able to step. That contradicts progress.
The joint soundness guarantee; progress or preservation must fail · Preservation would keep the reached expression typed. With closedness retained, progress would exclude its being stuck.
No; progress's well-typed-expression hypothesis is absent · Progress applies to closed well-typed expressions. This expression is closed but does not meet the typing hypothesis.
Preservation: the step does not retain the starting type Bool · The starting expression can step and the result is a value. But the result lacks Bool, so this step violates preservation.