% CSci 555: Functional Programming \
  Type System Concepts
% **H. Conrad Cunningham**
% **9 February 2019**

---
lang: en
---

| Copyright (C) 2018, 2019,
  [H. Conrad Cunningham ](<http://www.cs.olemiss.edu/~hcc>)
| Professor of 
  [Computer and Information Science ](<https://www.cs.olemiss.edu>)
| [University of Mississippi ](<http://www.olemiss.edu>)
| 211 Weir Hall
| P.O. Box 1848
| University, MS 38677
| (662) 915-5358

**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*
](<http://www.cs.olemiss.edu/~hcc/csci450/ELIFP/ExploringLanguages.html>).
This was also Section 5.2 of the draft book 
[*Multiparadgm Programming with Python 3*
](<http://www.cs.olemiss.edu/~hcc/csci556/notes/Py3MPP/Py3MPP.html>). 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.


# Type System Concepts {.center}

## 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`{.java} and Scala type `AnyRef`{.scala} 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