Type Soundness: Progress and Preservation · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Why well-typed programs cannot go wrong

Computing · Computer Systems · ages 23-24
Name ______________________   Date ____________

  1. What does progress promise?

    • A well-typed program runs fast
    • A well-typed program is never stuck
    • A well-typed program never loops

  2. What does a small-step rule assert?

    • What one step of running does
    • What the whole program outputs
    • How fast the program runs

  3. Preservation says taking a step keeps the program's type.

    Circle one:   True   False

  4. What does preservation alone rule out?

    • A program changing type in the middle of a run
    • A program running out of memory
    • A program asking for input

  5. A well-typed program uses a null reference and stops without yielding a value. Which lemma breaks?

    • Preservation
    • Neither, this is allowed
    • Progress

  6. The type system forbids an error, yet it happens at run time. What failed?

    • The program was too short
    • Soundness: at least one of the two promises failed
    • The hardware disobeyed arithmetic

  7. A program is stuck but ill-typed. Does that violate progress?

    • No, progress only covers well-typed programs
    • Yes, all stuck programs violate it
    • Yes, typing never matters

  8. Name a feature that breaks soundness, and say which lemma it breaks.

    • Null references, breaking preservation
    • Integers, breaking progress
    • Null references, breaking progress
LightMySky · lightmysky.comW1-mt_nAAHVPNaVJ-s1

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

  1. A well-typed program is never stuck · Progress is the never-stuck promise for typed programs.
  2. What one step of running does · Each rule covers exactly one step of evaluation.
  3. True · Stepping preserves the type: before and after match.
  4. A program changing type in the middle of a run · Preservation alone guards the type across steps.
  5. Progress · Stuck without a value is the progress failure.
  6. Soundness: at least one of the two promises failed · A forbidden error at run time means a promise broke.
  7. No, progress only covers well-typed programs · Progress promises nothing about ill-typed programs.
  8. Null references, breaking progress · Null gets stuck while typed: a progress violation.
Worksheet · LightMySky