Acknowledgements: I created these slides in Fall 2018 to accompany Section 5.2. Type System Concepts, of the book Exploring Languages with Interpreters and Functional Programming. This was also Section 5.2 of the draft book Multiparadgm Programming with Python 3. I adapted the latter for use in Spring 2019 in the Scala-based CSci 555 (Functional Programming) course.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of February 2019 is a recent version of Firefox from Mozilla.

Lecture Goals

• Examine the general concepts of type systems

• Learn how to characterize language type systems

Types and Subtypes

Type (conceptual):

set of values and set of operations on them

Type S (behavioral) subtype of type T if

• Value set S “subset” of value set T
• Operation set S “superset” of operation set T

Liskov Substitution Principle

Substitute elements of subtype S for elements of T because S operations behave “same” as T operations

Example

Types Furniture (all furniture) and Chair (all chairs)

• Chair subset of Furniture

• Chair has all attributes of Furniture, possibly plus some

• Chair has all operations of Furniture, possibly plus some

• Furniture operations on Chair instances give “same” result

Satisfy Liskov Substitution Principle

Constant, Variable, Expression

• Constant has whatever types defined to have in context

  Type of 1 is bit, integer, float, complex based on context

• Variable has whatever types its value has at particular time, subject to declaration constraints

• Expression has whatever types evaluation yields based on constituent variables, constants, operations

Static and Dynamic (1)

Statically typed language:

types of variable or expression determined from source code at “compile time”

• Some may be declared explicitly

• Others inferred implicitly from context

• Examples: Java, Scala, Haskell

Static and Dynamic (2)

Dynamically typed language:

type of variable or expression cannot be determined at “compile time” — checked at runtime

• Examples: Lisp, Python, JavaScript, Lua

Most languages mix static and dynamic

• Java and Scala use declared types

• Java type Object and Scala type AnyRef may require runtime checks

Nominal and Structural (1)

Nominal typing:

type of value based on type name assigned when created

• Values have same type only if have same type name

• Type S is subtype of T only if S explicitly declared subtype

• Example: Java typed using class/interface names

  But does not guarantee Liskov Substitution Principle — subclass can change behavior

Nominal and Structural (2)

Structural typing:

type of value based on structure of value

• Values have same type if “same” structure — compatible public data attributes and operations

• Type S is subtype of T only if S has all public data values and operations of T, which are of compatible types

• Example: Haskell

Nominal and Structural (3)

• Languages may mix nominal and structural typing

• Scala has limited structural typing feature

• Python has nominal typing and dynamic structural (duck) typing

Polymorphic Operations

Polymorphism:

having “many shapes”

Polymorphic operation:

Associating function names (or operator symbols) with implementations

Kinds of Polymorphism (1)

1. Ad hoc polymorphism: same function name denotes different implementations depending on use

   • overloading — compiler determines which to invoke, early binding

     + in Java, Haskell type classes, Scala type class pattern

   • subtyping — runtime usually searches hierarchy of types, late binding

     Called just polymorphism in Java – does not exist in Haskell

Kinds of Polymorphism (2)

2. Parametric polymorphism: same implementation used for different types

   Called generics in Java and Scala — Haskell just polymorphism

Polymorphic Variables

Polymorphic variable:

variable can “hold” values of different types during program execution.

• Dynamically typed language — variables hold any value

• Statically typed language — variables hold declared type or declared subtype

• Polymorphic (generic) function — parameter holds types allowed by parameter declaration

Key Ideas

• Types

• Subtypes satisfying Liskov Substitution Principle

• Static and dynamic types

• Nominal and structural types

• Polymorphic operations – matching name with implementation

• Polymorphic variables – hold multiple types of values