notes-computer-programming-programmingLanguagesBook-programmingLanguagesChTypeConstructs

Table of Contents for Programming Languages: a survey

Chapter : typing and correctness/safety

dynamic vs static vs semidynamic

tradeoffs

expressive type system -> complex

no type inference -> simpler but less concise

type inference -> concise but complex

dynamic typing -> less strict (safe)

want: safe, expressive, simple, concise (unsolved problem)

non-safety tradeoffs regarding of types

types also help a ton with IDEs, see below

they can also make code more self-documenting

they can also help enforce architectural constraints in teams

they can also help performance

they can also lengthen compile-time

nonstrict type coercion

nullable pointer types

pre- and post-conditions

parametric polymorphism (generics)

types as OOP class members

in some languages, instead of or in addition to special syntax to define a class parameterized by a type, one can simply declare a type as a member of the class.

e.g. in Scala: http://docs.scala-lang.org/tutorials/tour/abstract-types.html

notes on differences between Abstract Type Members versus Generic Type Parameters:

...

and type functions

and C++ templates

see "The Generic Dilemma" http://research.swtch.com/generic

if you have interfaces but not generics (like Go), what you are missing is the ability to write a function with a signature like:

KeyIntersection?(Map T1 T2, Map T1, T2) : Map T1 T2

instead you must write something like:

KeyIntersection?(Mappable, Mappable) : Mappable

the difference is that in the interface version, the compiler can't infer that the types of the keys and values in the result are the same as the types of the keys and values in the arguments.

to substitute: covariant arrays (old C# and its probs)

ad-hoc polymorphism

see also typeclasses

subtyping

co- and contra- variance

array prob; fn prob

to substitute for generics: covariant arrays (old C# and its probs)

immutable

unique

implicit type conversion

success typing

Chapter : types

primitive data types

literals

multiple literals for the same value: hex literals scientific notation

bool, int, real, char, string,

complex # e.g. python's notation 1.j

usually also data constructors for list or table or tuple or something like that (not technically literals since there is variable substitution in them)

examples:

Python list: [1,2,3]

Octave list: [1 2 3]

Python dict: {'a': 1, 'b': 2, 'c':3}

Python set: {1,2,3}

in Apple Swift, lists and associative arrays have the same syntax as Python, except they both use []

different languages have many different names for associative arrays: dict, hash, map, table, associative array, association list/property list (lisp)

some languages distinguish between 'lists', 'arrays', and 'vectors'

tuples (arrays whose length is fixed and statically known)

(note somewhere: "statically known" means "known by the compiler at compile time")

user created types

function types

In some systems (e.g. Haskell), non-functional value types are equivalent to zeroary functions.

todo currying notation in function types:

generics, e.g. parametric polymorphism

e.g. a List of Ints.

one can conceptualize these in terms of an abstract function from types to types called List; now "a List of Ints" is written "List(Int)".

"List" is called a type constructor, a 'higher order type', a functor or a template. There are subtle differences between these phrases:

A type constructor is an operator which yields a type.

A higher order type is a type which is also a function on types, just as (in a language that supports first-class functions) a function is a value which is also a function on values.

A functor is a mathematical concept from the part of mathematics called 'category theory'. Functors are sometimes used to model higher-order types.

A template is a metaprogramming technique used to achieve parametric polymorphism.

more on functors

" A functor is a thing that can be mapped over. For example:

    map abs [-1, 2, 3] => [1, 2, 3]

Arrays are the simplest example, but it looks like an iterable. However functors retain shape whereas iterables don't. For example if we had a tree (represented visually):

    oak = -1
          / \
         2   3

If we used oak as an iterable, we would lose the structure of the tree:

    map abs iter(oak) => [1, 2, 3]

However if tree belongs to the functor typeclass (i.e. implements functor interface), then:

    map abs oak => 1
                  / \
                 2   3"

-- william ting, https://news.ycombinator.com/item?id=7895816

" The name "Functor" can be confusing; it's a thing you apply a function to, not a function itself." -- Josh Triplett https://news.ycombinator.com/item?id=7895752

Kinds

Just as the type system with function types keeps track of the signature of functions, one might ask for a system to keep track of the signature of higher-order types. The typical answer is a meta-type-system, a type system for types, where the meta-type of a type is called a "kind".

The typical notation is:

(todo example of (* -> *) -> * ? wikipedia says "See Pierce (2002), chapter 32 for an application.")

sum and product types

composites of simpler types

the simple dual conception

in this conception, a product type is like an AND, and a sum type is like the way we use the word 'or' in English (but not like logical OR)

the traditional conception

subtypes

values vs. references

Types as a partial order

defn partial order

defn join, meet

should this be moved to the 'formal stuff' section?

Types as semilattices or lattices

defn semilattice, lattice

should this be moved to the 'formal stuff' section?

Any

e.g. a type that contains all values; a greatest element in the algebra of types

Bottom

e.g. a type that contains no values; a least element in the algebra of types

usage to indicate divergence (e.g. Haskell)

Type

e.g. the type of all types

theoretical problem with type of all types (Girad's paradox)

operations on types

instanceOf (sometimes = elem)

subclassOf (sometimes = <=)

isa(v,x)

kindOf(t) (get the kind of a type)

type(v)

are types sets? if so, are set-theoretic operations implemented for types?

are types just sets? if so, what about the algebra of type constructors?

synonym, sum, product, struct

type constructors