Theory of Programming Languages Study Guide

gistfile1.md

TOPL Test 3

Overview

• Types and Type Checking

  • Motivation
  • Type Systems

• Modules

• Object-oriented Programming

Types and Type Checking

• Why type systems?

  • Prevent errors from occurring at runtime
    • Unbound Variables
    • Operations on the wrong kind of value
  • Other errors are harder
    • Infinite loop/recursion

• In LETREC an evaluation is safe iff:

  1. For every evaluation of a var, the variable is bound.
  2. For every evaluation of a difference expression, the values of the operands are both num-vals
  3. For every evaluation of an expression of the form zero?-exp (exp1) the value of exp1 is a num-val
  4. For every evaluation of a conditional expression (if-exp exp1 exp2 exp3), the value of exp1 is a bool-val
  5. For every evaluation of a procedure call (call-exp rator rand), the vaue of a rator is a proc-val

• A type system is sound if it rejects any program that cannot be guaranteed safe

• Type Environment

  • Abstraction used to keep track of the type that each expression will evaluate to.
  • An expression is either well-typed or ill-typed
    • Well-typed: if a value can be determined
    • Ill-typed: if a value cannot be determined
  • Type rules:

• Different methods of type checking:

  • Static - we do the check before execution.
    • Predict type and anticipate type errors
  • Dynamic - we do the check during execution

• Manifest vs. Inferred Syntx

  • Manifest Typing - requires syntactical support.
  • Inferred Typing - requires no additional syntax, only changes to the checker

• The Type Checker

  • Is separate from the interpreter
  • Runs before the interpreter thus catching exceptions before run time. (Unsafe programs)

Modules

• Why modules?
  • Useful to separate code into self-contained parts.
  • Abstract from implementation.
• A module is:
  • A self-contained part of a larger program.
  • Reusable in different contexts (DRY)
• Author's Design
  • Module definitions binds a name to a module (expression)
    • ::=
  • What does the module itself contain
    • Interface - names/variables visible to client (outside the abstraction boundary)
    • Body - Implements the interface, defines bindings for names
  • Two kinds of modules (for authors):
    • Simple Module - Just a set of bindings (ie an environment). Has simply interface that lists bindings made by the module.
    • Module Procedure - Takes in one module and produces another.
• What are qualified variables?
  • from m1 take a
  • m1.a (Java)
• How is module scoping handles?
  • The authors implement it is that a module can only activate things from the previously defined modules
  • This is usually not the desired behavior.
• Transparent Type - The client code outside of the module can use the underlying representation of the type. (C++ typedef)
• Opaque Type - The code outside the module boudary does not know how values of this type are represented. (C++ Struct)

Object Oriented Languages

• Is an explicit base class object necessary?
  • No because it's not in C++!
• What syntactic forms are necessary for supporting object-oriented programming?
  • Class definitions
  • Extends clause
  • Field declarations
  • Method Definitions
• Using objects
  • Instantiation (new-exp)
  • Message passing (method-call-exp)
• Other sytactic forms:
  • Super
  • Instance-of
  • Destructors
  • Down/up-casting
  • Main method/initializers
  • Accessors
  • Static variables/class variables
• How can we represent classes and objects internally? (parallels syntactic forms)
  • Data required for a class
    • Parent class
    • Field Names
    • Method environment
    • Class name (implementation dependent)
  • Data requires for an object
    • Class name
    • Values/references for fields
• Polymorphism
  • Two different kinds:
    • Subclass polymorphism - Inherits all of a parents methods and variables.
    • Interface Polymorphism - Has the type of any interfaces that its creating class implements.
• Dynamic vs. Static Dispatch
  • Dynamic Dispatch - Implementation selected at run time (C++ virtual function) (metod-call-exp)
  • Static Dispatch - Implementation selected at run time (like any normal function) (super-call-exp)
• How are method invocations handled?
  • Methods are like closures. They take their environments in with them, but other things don't have access to variables created within it.
  • Why do we mangle self and super?
    • Because we need to differentiate between selfs/supers of different namespaces.
  • Bindings for field names of a class *
• How are types related to classes in an Object-Oriented language?
  • Types are to variables as interfaces are to classes.

Nice and to the point. Sweet deal.

More to come tomorrow. Unfortunately I need to do calc homework =(

That's cool. This will serve awesomely as a last minute check tomorrow. Major props.

word up yo!
im trying to be on that #studyinggrind

+1