Use a Phantom type to distinguish Program with and without type annotations.

The type checker converts Program NoTypeAnnotation to Program TypeAnnotation.