# CS2104 Presentation ## Kendrick, Kang Liang, Chee Yuan --- # Types Types are a way to categorize values. --- ## Static Typing - Type-checking done at **compile time**. - Programmer must specify what type variables are - Some languages offer *type inference* - Knowledge of types at compile time helps with machine code optimization - Can help to catch errors early - Code autocompletion - Code is 'self-documenting' --- ## Static Typing - Java ```java= int x; // Declaration of variable 'x' with type 'int' x = 10; // Initialization of value of 'x' int x = 10; // Declaration + Initialization ``` --- ## Dynamic Typing - Types are only known at runtime - Types are checked "on the fly" during runtime - Allows faster development in some cases due to less lines of code - Performance be slower as types need to be check --- ## Dynamic Typing - Python ```python= x = 10 x = "String" ``` --- ## Differences #### `Java` ```java= int foo(int x) { if (x > 5) { return x; } else { return "123" + x } } foo(10) ``` Unable to compile due to incompatible type --- ## Differences #### `Python` ```python= def foo(x): if x > 0: return x else: return "1" + x foo(10) ``` Error is not detected here as `else` block is never executed --- ### Implementation of dynamic type #### `CPython` - Is both a compiler and interpreter - Compiles python to bytecode before interpreting it - Python variables have no type. They are simply pointers to objects --- #### `Python` ```python= type(1) # <class 'int'> type("foo") # <class 'str'> ``` - All variables point to the object PyObject, implemented as a C struct. - `type = (((PyObject*)(o))->ob_type)` to get the type - `rtn = PyUnicode_FromFormat("<class '%s'>", type->tp_name);` ---  --- ## Haskell? ***Statically typed!*** May look like dynamic typing but types are inferred by the compiler ```haskell= Prelude> x = 10 Prelude> :t x x :: Num p => p -- Typeclass-constrained type variables -- We do not know the type but we know it must implement the Num typeclass Prelude> y = x :: Int Prelude> :t y y :: Int -- We set y to have the data type Int which implements the Num typeclass ``` --- ## Strong Typing Strongly typed languages implies that types are **bound** to a particular data type - types must be explicitly converted - "strong" against "unexpected" type change Even though Python is **dynamically typed**, it is **strongly typed**. ```python= >>> x = 10 >>> x + "10" Traceback (most recent call last): File "<pyshell#3>", line 1, in <module> x + "10" TypeError: unsupported operand type(s) for +: 'int' and 'str' ``` --- ## Weak Typing In contrast, weakly typed languages have types but they are not **bound** to it. - program infers what you want & automatically applies type change - "weak" against "unexpected" type change Even though C is **statically typed**, it can be said to be **weakly typed** ```cpp= int x; char y = 'a'; x = y; ``` Type of `y` is implicitly casted before assigning to `x`. --- ## Javascript ```javascript= > [] + [] "" > [] + {} "[object Object]" > {} + [] 0 > Array(16).join("wat" - 1) + " Batman" "NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN Batman" ``` https://www.destroyallsoftware.com/talks/wat --- ## Type Inference **Definition**: Type inference is an algorithm allowing concrete types to be deduced by the type system whenever it is obvious. * Haskell’s (and OCaml's) type inference is built on *Damas-Hindley-Milner* type system. * It attempts to assign the **most general type** to every construct in the program. --- ## Example What is the type of `either`? ```haskell= either :: ? -> ? -> ? -> ? either f x y = if f x y then x else y ``` * `either` takes in: * three parameters `f`, `x` and `y` * `f` is used in prefix function application (two params) * `f` must have type (? -> ? -> ?) ---- ## Example What is the type of `either`? ```haskell= either :: (? -> ? -> ?) -> ? -> ? -> ? either f x y = if f x y then x else y ``` * `either` takes in: * a function `f` * two parameters `x` and `y`, returning either `x` or `y`. ---- ## Example What is the type of `either`? ```haskell= either :: (? -> ? -> ?) -> ? -> ? -> ? either f x y = if f x y then x else y ``` 1. We know that the if-expression must evaluate to the same type * `x` and `y` are the same type * call this type `p` ---- ## Example What is the type of `either`? ```haskell= either :: (p -> p -> ?) -> p -> p -> p either f x y = if f x y then x else y ``` 1. `x` and `y` have type `p` 2. `f x y` must return a Bool for the if-expression to evaluate to ---- ## Example What is the type of `either`? ```haskell= either :: (p -> p -> Bool) -> p -> p -> p either f x y = if f x y then x else y ``` * function `f` returns a Bool QED --- ## The key idea Hindley-Miller type checking: 1. *leverages the constraints* of the various constructs to infer types * In our example, the constraints of if-else-then * Type Constraining 3. *Applies these constraints together* to find the most general type for each construct, or discover a type error * Type Unification --- ## Step 1 - Type Constraining To apply Hindley-Miller, first define these types: * Constant Integers (int) `0, 1` * Constant Real Numbers (real) `0.1, 1.1` * Constant Booleans (boolean) `true, false` * Constant Strings (string) ``"foo", "bar"`` These form our **unary constraints**. * What about binary/ternary... constraints? ---- ### Arithmetic operators ### a OP b  * OP is $+, -, *, /$ * Infer constraints: * $T_1=T_2=T_3=$numeric type ---- ## Function application ## $foo(x_1,x_2...x_k)$  * Infer constraints: * $F=(T_1,T_2..T_k)$ -> $R$ ---- ## Function definition ## fun $foo(x_1,x_2,...,x_k) = expr$  * Infer constraints: * $F=(T_1,T_2..T_k)$ -> $E$ ---- ## If-expression ## if (cond) then $expr_1$ else $expr_2$  * Infer constraints: * $T_1$ = boolean * $T_2=T_3=T_4$ --- ## Step 2 - Type Unification Definition: Type Unification is the process by which type constraints are propagated. Idea: 1. Start from top of syntax tree, go downwards 2. If we see a construct with no type constraint, create a new type 3. If a construct has some type $T_1$ and also type $T_2$, $T_1$ must have the same type as $T_2$. ---- ### Example: fun $foo(a,b,c) = c(a[b])$  * $foo$ returns type $T_4$ ---- ### Example: fun $foo(a,b,c) = c(a[b])$  * (2) has no type constraint yet -> create a new type ---- ### Example: fun $foo(a,b,c) = c(a[b])$  * Resolve (2) to type $T_4$ ---- There is insufficient time to cover all details of Type constraints and Type unification. For more details, please see the source videos: * [Part 1] https://www.youtube.com/watch?v=cQf_6NsLp80 * [Part 2] https://www.youtube.com/watch?v=xJXcZp2vgLs&t=414s --- # Benefits * Implicit Polymorphism - since programmer doesn't need to specify any type ```haskell= length :: (Foldable t, Num n) => t a -> n length arr = foldr (\next acc -> acc + 1) 0 arr length [10,20,30] -- 3 length ['a','b','c'] -- 3 ``` --- # References 1. https://www.sitepoint.com/typing-versus-dynamic-typing/ 2. https://hackernoon.com/i-finally-understand-static-vs-dynamic-typing-and-you-will-too-ad0c2bd0acc7 3. https://wiki.haskell.org/Type_inference 4. https://adamdoupe.com/teaching/classes/cse340-principles-of-programming-languages-s16/ --- # Appendix ---- ### Relational operators ### a OP b  * OP is $<, <=, >, >=, /=, ==$ * Infer constraints: * $T_1 =$ boolean * $T_2 = T_3 =$ numeric type Haskell would probably give $T_2$ and $T_3$ the `Eq` typeclass instead, but the idea remains the same. ---- ### Array access operator ### a[b]  * Infer constraints: * $T_2$ = array of $T_1$ * $T_3$ = int ---- <style> .reveal { font-size: 32px; } </style>