Type Expressions

A type expression is the formal notation a compiler uses to describe a type. It is either a basic type or a type constructor (array, pointer, product, record, function) applied to other type expressions. We cover the notation, type trees, type names, and structural vs. name equivalence — all through short examples.

What is a Type Expression?

Definition. A type expression describes a type. It is either:

a basic type (int, float, char, boolean, void, type_error), or
a type constructor applied to other type expressions (e.g. pointer(int)).

The definition is recursive, so we can describe any type — even "an array of pointers to functions" — by composing simpler pieces.

Dragon Book (Aho et al.): "A type expression is either a basic type or is formed by applying a type constructor to type expressions."

Why the compiler needs it. During semantic analysis the compiler tags every AST node with a type. To check int *p = &x; it needs an exact, comparable representation of "pointer to int." Type expressions are that representation.

Types are trees. Because a constructor takes type expressions as arguments, every type expression is a tree: leaves are basic types, interior nodes are constructors.

Example

pointer(int): pointer

int

Basic (Primitive) Types

Basic types are the leaves of every type tree. They are built into the compiler.

Basic type	Meaning
`boolean`	true / false
`char`	a single character
`int`	a whole number
`float`	a real (floating-point) number
`void`	no value (the type of a statement)
`type_error`	error type, returned when type checking fails

void marks something that yields no usable value — a statement like x = 5;, or a function declared void f().

type_error is what the checker returns on a mismatch instead of crashing. Example:

Example

3 + true → int + boolean → type_error

Rule: type_error propagates upward — any operation on type_error is type_error. This stops one bad expression from producing a flood of follow-on error messages.

Type Constructors

A type constructor builds a compound type from existing ones. There are five.

array(I, T)

Array with index set I and element type T.

Example

int a[3] → array(0..2, int)

float m[2][4] → array(0..1, array(0..3, float))

pointer(T)

A pointer to a value of type T.

Example

int *p → pointer(int)

char **argv → pointer(pointer(char))

product T₁ × T₂

The Cartesian product of two types — used for tuples and function argument lists. Left-associative: T₁ × T₂ × T₃ = (T₁ × T₂) × T₃.

Example

(int, float) → int × float

record (struct)

A group of named fields, each with its own type. Fields are accessed by name, not position.

Example

struct Point { int x; int y; } → record(x : int, y : int)

function s → t

A function with domain s (parameter types) and range t (return type). Multiple parameters use a product for the domain.

Example

int f(int x) → int → int

int g(char a, int b) → (char × int) → int

Type Trees — Worked Examples

Every type expression is a tree. Build the tree by reading the type from the outside in; recover the expression by reading the tree bottom-up (post-order).

Example 1 — `int *a[3]`

In C this is "an array of three pointers to int." Type: array(0..2, pointer(int)).

array(0..2, —)

0..2

pointer(—)

int

Root is array; left child is the index 0..2; right child is pointer, whose child is int.

Reading it bottom-up: int → pointer(int) → array(0..2, pointer(int)). ✓

Example 2 — `int f(char, char)`

A function taking two chars and returning int. Type: (char × char) → int.

→ (function)

× (product)

char

int

Root is →; left child is the domain char × char; right child is the range int.

Sharing turns trees into DAGs

When the same named type is used twice, the compiler stores it once and points both uses at it. The tree becomes a DAG (directed acyclic graph) — saving space and making "same type?" an O(1) pointer comparison.

Type Names

A type name is an alias for a type expression. In C you create one with typedef; struct and class names work the same way.

Example

typedef int *intptr; // intptr names pointer(int)

intptr p, q; // p and q both have type pointer(int)

Naming a type forces one question, and the answer splits languages in two:

Is intptr the same as pointer(int) (just an abbreviation), or a distinct type that merely looks the same?

The first answer is structural equivalence, the second is name equivalence — the next section.

Structural vs. Name Equivalence

Two types are equivalent when the compiler treats them as interchangeable (e.g. for assignment). There are two definitions.

Structural equivalence — equal if their trees match. Type names are expanded first, so names are transparent.

Name equivalence — equal only if they carry the same declared name. Names are opaque; the compiler never looks inside.

Example — same structure, different names

Example

typedef int *intptr;

typedef int *myptr; // same structure, different name

intptr p; myptr q;

Structural: both are pointer(int) → equivalent ✓

Name: intptr vs myptr → NOT equivalent ✗

So p = q; is allowed under structural equivalence but is a type error under name equivalence.

Example — two identical structs

Example

struct A { int x; int y; };

struct B { int x; int y; }; // identical fields, different tag

A a; B b;

Structural: a = b; is VALID

Name: a = b; is a TYPE ERROR (A ≠ B)

Where each is used

	Structural	Name
Names are	transparent	opaque
Flexibility	higher	lower
Safety	lower	higher (distinct abstractions stay distinct)
Cost	tree walk, O(n)	name compare, O(1)
Languages	TypeScript, most functional langs	C structs, Java classes, Ada, Pascal

Most real compilers mix both: structural equivalence for basic/anonymous types, name equivalence for named structs/records.

Summary

A type expression is either a basic type or a type constructor applied to other type expressions.
Basic types: boolean, char, int, float, void, type_error.
The five constructors:

Example

array(I, T) — array, index set I, elements of type T

pointer(T) — pointer to T

T₁ × T₂ — product (tuples, argument lists)

record(f:T,…) — labelled product (struct)

s → t — function, domain s to range t

Type expressions are trees; shared type names collapse them into DAGs.
Structural equivalence: equal if trees match (names transparent).
Name equivalence: equal only if names match (names opaque).

Quick reference

Declaration	Type expression
`int x`	`int`
`float *p`	`pointer(float)`
`char **argv`	`pointer(pointer(char))`
`int a[10]`	`array(0..9, int)`
`int *b[5]`	`array(0..4, pointer(int))`
`int f(char)`	`char → int`
`int g(char, char)`	`char × char → int`
`struct { int x; float y; }`	`record(x:int, y:float)`

Type Expressions

What is a Type Expression?

Definition. A type expression describes a type. It is either:

a basic type (int, float, char, boolean, void, type_error), or
a type constructor applied to other type expressions (e.g. pointer(int)).

The definition is recursive, so we can describe any type — even "an array of pointers to functions" — by composing simpler pieces.

Dragon Book (Aho et al.): "A type expression is either a basic type or is formed by applying a type constructor to type expressions."

Types are trees. Because a constructor takes type expressions as arguments, every type expression is a tree: leaves are basic types, interior nodes are constructors.

Example

pointer(int): pointer

int

Basic (Primitive) Types

Basic types are the leaves of every type tree. They are built into the compiler.

Basic type	Meaning
`boolean`	true / false
`char`	a single character
`int`	a whole number
`float`	a real (floating-point) number
`void`	no value (the type of a statement)
`type_error`	error type, returned when type checking fails

void marks something that yields no usable value — a statement like x = 5;, or a function declared void f().

type_error is what the checker returns on a mismatch instead of crashing. Example:

Example

3 + true → int + boolean → type_error

Rule: type_error propagates upward — any operation on type_error is type_error. This stops one bad expression from producing a flood of follow-on error messages.

Type Constructors

A type constructor builds a compound type from existing ones. There are five.

array(I, T)

Array with index set I and element type T.

Example

int a[3] → array(0..2, int)

float m[2][4] → array(0..1, array(0..3, float))

pointer(T)

A pointer to a value of type T.

Example

int *p → pointer(int)

char **argv → pointer(pointer(char))

product T₁ × T₂

The Cartesian product of two types — used for tuples and function argument lists. Left-associative: T₁ × T₂ × T₃ = (T₁ × T₂) × T₃.

Example

(int, float) → int × float

record (struct)

A group of named fields, each with its own type. Fields are accessed by name, not position.

Example

struct Point { int x; int y; } → record(x : int, y : int)

function s → t

A function with domain s (parameter types) and range t (return type). Multiple parameters use a product for the domain.

Example

int f(int x) → int → int

int g(char a, int b) → (char × int) → int

Type Trees — Worked Examples

Every type expression is a tree. Build the tree by reading the type from the outside in; recover the expression by reading the tree bottom-up (post-order).

Example 1 — `int *a[3]`

In C this is "an array of three pointers to int." Type: array(0..2, pointer(int)).

array(0..2, —)

0..2

pointer(—)

int

Root is array; left child is the index 0..2; right child is pointer, whose child is int.

Reading it bottom-up: int → pointer(int) → array(0..2, pointer(int)). ✓

Example 2 — `int f(char, char)`

A function taking two chars and returning int. Type: (char × char) → int.

→ (function)

× (product)

char

int

Root is →; left child is the domain char × char; right child is the range int.

Sharing turns trees into DAGs

Type Names

A type name is an alias for a type expression. In C you create one with typedef; struct and class names work the same way.

Example

typedef int *intptr; // intptr names pointer(int)

intptr p, q; // p and q both have type pointer(int)

Naming a type forces one question, and the answer splits languages in two:

Is intptr the same as pointer(int) (just an abbreviation), or a distinct type that merely looks the same?

The first answer is structural equivalence, the second is name equivalence — the next section.

Structural vs. Name Equivalence

Two types are equivalent when the compiler treats them as interchangeable (e.g. for assignment). There are two definitions.

Structural equivalence — equal if their trees match. Type names are expanded first, so names are transparent.

Name equivalence — equal only if they carry the same declared name. Names are opaque; the compiler never looks inside.

Example — same structure, different names

Example

typedef int *intptr;

typedef int *myptr; // same structure, different name

intptr p; myptr q;

Structural: both are pointer(int) → equivalent ✓

Name: intptr vs myptr → NOT equivalent ✗

So p = q; is allowed under structural equivalence but is a type error under name equivalence.

Example — two identical structs

Example

struct A { int x; int y; };

struct B { int x; int y; }; // identical fields, different tag

A a; B b;

Structural: a = b; is VALID

Name: a = b; is a TYPE ERROR (A ≠ B)

Where each is used

	Structural	Name
Names are	transparent	opaque
Flexibility	higher	lower
Safety	lower	higher (distinct abstractions stay distinct)
Cost	tree walk, O(n)	name compare, O(1)
Languages	TypeScript, most functional langs	C structs, Java classes, Ada, Pascal

Most real compilers mix both: structural equivalence for basic/anonymous types, name equivalence for named structs/records.

Summary

A type expression is either a basic type or a type constructor applied to other type expressions.
Basic types: boolean, char, int, float, void, type_error.
The five constructors:

Example

array(I, T) — array, index set I, elements of type T

pointer(T) — pointer to T

T₁ × T₂ — product (tuples, argument lists)

record(f:T,…) — labelled product (struct)

s → t — function, domain s to range t

Type expressions are trees; shared type names collapse them into DAGs.
Structural equivalence: equal if trees match (names transparent).
Name equivalence: equal only if names match (names opaque).

Quick reference

Declaration	Type expression
`int x`	`int`
`float *p`	`pointer(float)`
`char **argv`	`pointer(pointer(char))`
`int a[10]`	`array(0..9, int)`
`int *b[5]`	`array(0..4, pointer(int))`
`int f(char)`	`char → int`
`int g(char, char)`	`char × char → int`
`struct { int x; float y; }`	`record(x:int, y:float)`

Type Expressions

What is a Type Expression?

Basic (Primitive) Types

Type Constructors

array(I, T)

pointer(T)

product T₁ × T₂

record (struct)

function s → t

Type Trees — Worked Examples

Example 1 — int *a[3]

Example 2 — int f(char, char)

Sharing turns trees into DAGs

Type Names

Structural vs. Name Equivalence

Example — same structure, different names

Example — two identical structs

Where each is used

Summary

Quick reference

Type Expressions

What is a Type Expression?

Basic (Primitive) Types

Type Constructors

array(I, T)

pointer(T)

product T₁ × T₂

record (struct)

function s → t

Type Trees — Worked Examples

Example 1 — int *a[3]

Example 2 — int f(char, char)

Sharing turns trees into DAGs

Type Names

Structural vs. Name Equivalence

Example — same structure, different names

Example — two identical structs

Where each is used

Summary

Quick reference

Example 1 — `int *a[3]`

Example 2 — `int f(char, char)`

Example 1 — `int *a[3]`

Example 2 — `int f(char, char)`