Visitor Pattern

Recall from last time, we are using the visitor pattern for creating the abstract syntax tree.

To do type checking and code generation in our project, we will use the visitor pattern.

Type systems

Ch 7 in Scott.

Types can add structure to programs (e.g., limit the set of operations that can be performed semantically) as well as help with readability of the program. Also, the compiler can perform optimizations when types are known at compile-time.

A type system is a mechanism to define types and a way to associate types with objects in a language. There are a set of rules for

  1. type equivalence: when are two values considered the same?
  2. type compatibility: when can a value of a given type be used in a particular context?
  3. type inference: How is the type of an expression determined?

Subroutine types

Subroutines have types in languages where they are first or second class objects. Type information allows the language to restrict the set of subroutines to those with a particular signature/interface.

Subroutines do not need types in languages where language is statically scoped and subroutines are third class objects; the compiler can always identify which subroutine a name refers to.

Type checking

The process of ensuring that a program satisfies the language type compatability rules.

  • Type clash: violation of the language’s typing rules
  • Strongly typed: Language implementation prohibits application of operation to object not intended to support operation
  • Statically typed: strongly types + type checking (mostly) performed before run time
  • Dynamically typed: type checking performed at run-time

C becomes more strongly typed with each release, but still has these loopholes

  • unions
  • nonconverting type cast
  • subroutines with variable number of parameters
  • interoperability of pointers and arrays
  • C implementations rarely check anything at runtime

Loopholes needed for systems programming like malloc, free- interprets bytes at different times as unallocated space, metadata, or parts of user defined data structures.

In C#, you have to mark these sections of the code with the keyword unsafe.

Dynamic type checking

  • late binding
  • Lisp, Smalltalk, most scripting languages
  • Dynamic typing languages that are also strongly typed: Lisp, Python, Smalltalk, Ruby
  • Languages with dynamic scoping are generally dynamically typed
  • Runtime overhead of dynamic typing!

Intermediate position is type inference. Types must be statically known, but the compiler infers them without the need for explicit declarations (e.g., ML first to have sophisticated type inference)

Example is auto in C++

Denotational types

A type is a set of values called a domain. A value has a type if it belongs to the set. An object has a type if its value is guaranteed to be in the set.

Constructive types

Either primitive (int, bool, char, etc.) or constructed by a type constructor (e.g., array of char)

Abstraction-based types

An interface consisting of a set of operations with well-defined semantics

Ex:

  1. int operations +,-,*,/,%
  2. abstract data types such as stack
  3. algebraic specifications for types define a type without explicitly talking about the values
  4. Classes in OOP

Orthogonality

A collection of features is orthogonal if there are no restrictions on the ways in which the features can be combined. This is a useful goal when desigining a language. Makes a language easy to understand, use, and reason about.

Ex. Pascal allows arrays of anything

Trivial types

A type with a single value to characterize a statement useful only for side effect but doesn’t produce a value

Ex. C, Java use void. In ML, there’s unit.