Implement generic pointers

25 files changed, 1412 insertions, 66 deletions

diff --git a/boot/ast.cc b/boot/ast.cc
index edf1237..9dbcf7f 100644
--- a/boot/ast.cc
+++ b/boot/ast.cc
@@ -760,6 +760,23 @@ namespace elna::boot
     {
     }
 
+    record_type_expression::record_type_expression(const source_position position,
+            std::vector<field_declaration>&& fields, identifier&& base,
+            std::vector<type_expression *>&& base_arguments)
+        : node(position), fields(std::move(fields)),
+        base(std::make_optional<identifier>(std::move(base))),
+        base_arguments(std::move(base_arguments))
+    {
+    }
+
+    record_type_expression::~record_type_expression()
+    {
+        for (const type_expression *argument : this->base_arguments)
+        {
+            delete argument;
+        }
+    }
+
     void record_type_expression::accept(parser_visitor *visitor)
     {
         visitor->visit(this);
@@ -826,6 +843,22 @@ namespace elna::boot
     {
     }
 
+    record_constructor_expression::record_constructor_expression(const source_position position,
+            identifier&& type_name, std::vector<type_expression *>&& arguments,
+            std::vector<field_initializer>&& field_initializers)
+        : node(position), type_name(std::move(type_name)),
+        field_initializers(std::move(field_initializers)), arguments(std::move(arguments))
+    {
+    }
+
+    record_constructor_expression::~record_constructor_expression()
+    {
+        for (const type_expression *argument : this->arguments)
+        {
+            delete argument;
+        }
+    }
+
     void record_constructor_expression::accept(parser_visitor *visitor)
     {
         visitor->visit(this);
@@ -1176,6 +1209,20 @@ namespace elna::boot
     {
     }
 
+    named_expression::named_expression(const source_position position, const std::string& name,
+            std::vector<type_expression *>&& arguments)
+        : node(position), name(name), arguments(std::move(arguments))
+    {
+    }
+
+    named_expression::~named_expression()
+    {
+        for (const type_expression *argument : this->arguments)
+        {
+            delete argument;
+        }
+    }
+
     void named_expression::accept(parser_visitor *visitor)
     {
         visitor->visit(this);
diff --git a/boot/evaluator.cc b/boot/evaluator.cc
index b1648af..0a6ebe5 100644
--- a/boot/evaluator.cc
+++ b/boot/evaluator.cc
@@ -72,6 +72,12 @@ namespace elna::boot
         {
             return target.word_properties.front();
         }
+        else if (resolved.get<instantiated_type>() != nullptr)
+        {
+            const type erased = erase_generic(resolved);
+
+            return erased.empty() ? std::nullopt : get_type_properties(erased, target);
+        }
         else if (auto resolved_primitive = resolved.get<primitive_type>())
         {
             return resolved_primitive->properties;
@@ -127,7 +133,7 @@ namespace elna::boot
             {
                 break;
             }
-            current_record = resolve_underlying_type(current_record->base).get<record_type>();
+            current_record = erase_generic(current_record->base).get<record_type>();
         }
         for (auto const *current_record : std::views::reverse(chain))
         {
@@ -1097,7 +1103,7 @@ namespace elna::boot
         else if (subject.name.name() == "offset")
         {
             auto *field = subject.arguments.at(1)->is_named();
-            auto record = resolve_underlying_type(subject.types.front()).get<record_type>();
+            auto record = erase_generic(subject.types.front()).get<record_type>();
             if (field == nullptr || record == nullptr)
             {
                 return std::nullopt;
diff --git a/boot/lexer.ll b/boot/lexer.ll
index 5da70e5..17fe0ca 100644
--- a/boot/lexer.ll
+++ b/boot/lexer.ll
@@ -181,6 +181,9 @@ program {
 #{ID1}{ID2}* {
     return yy::parser::make_TRAIT(yytext + 1, this->location);
 }
+#\[ {
+    return yy::parser::make_GENERIC_OPEN(this->location);
+}
 (0|{NATURAL})u|{HEXADECIMAL} {
     if (auto result = parse_integer<std::uint64_t>(yytext, 0))
     {
diff --git a/boot/name_analysis.cc b/boot/name_analysis.cc
index a410ca8..a979a37 100644
--- a/boot/name_analysis.cc
+++ b/boot/name_analysis.cc
@@ -231,7 +231,7 @@ namespace elna::boot
     static void collect_field_names(const type& composite_type,
             ordered_map<field_origin>& names)
     {
-        auto record = resolve_underlying_type(composite_type).get<record_type>();
+        auto record = erase_generic(composite_type).get<record_type>();
         if (record == nullptr)
         {
             return;
@@ -446,6 +446,38 @@ namespace elna::boot
         }
     }
 
+    std::vector<type> resolving_visitor::enter_parameters(const std::vector<identifier>& parameters)
+    {
+        std::vector<type> result;
+
+        result.reserve(parameters.size());
+        for (const identifier& parameter : parameters)
+        {
+            const type parameter_symbol = type(std::make_shared<parameter_type>(parameter.name()));
+            auto info = std::make_shared<type_info>(parameter_symbol);
+
+            info->position.emplace(parameter.position());
+            info->file = this->module_file;
+
+            if (this->bag.enter(parameter.name(), info))
+            {
+                result.push_back(parameter_symbol);
+            }
+            else
+            {
+                auto original = this->bag.lookup(parameter.name());
+
+                add_error<symbol_declaration_error>(parameter.position(), parameter.name(),
+                        symbol_declaration_error::redefinition{
+                            .original = original->position,
+                            .file = this->redefinition_file(original)
+                        });
+                result.push_back(parameter_symbol);
+            }
+        }
+        return result;
+    }
+
     type resolving_visitor::resolve_type(type_expression& expression)
     {
         expression.accept(this);
@@ -535,15 +567,17 @@ namespace elna::boot
         std::shared_ptr<record_type> result_type;
         if (expression->base.has_value())
         {
+            type base_type;
+
             if (auto unresolved_alias = this->bag.declared(expression->base.value().name()))
             {
-                result_type = std::make_shared<record_type>(type(unresolved_alias));
+                base_type = type(unresolved_alias);
             }
             else if (auto base_symbol = this->bag.lookup(expression->base.value().name()))
             {
                 if (auto base_type_info = base_symbol->is_type())
                 {
-                    result_type = std::make_shared<record_type>(base_type_info->symbol);
+                    base_type = base_type_info->symbol;
                 }
                 else
                 {
@@ -560,6 +594,12 @@ namespace elna::boot
                 this->current_type = type();
                 return;
             }
+            if (!expression->base_arguments.empty())
+            {
+                base_type = type(std::make_shared<instantiated_type>(base_type,
+                            resolve_arguments(expression->base_arguments)));
+            }
+            result_type = std::make_shared<record_type>(base_type);
         }
         else
         {
@@ -736,7 +776,10 @@ namespace elna::boot
         {
             if (auto type_info = type_symbol->is_type())
             {
-                expression->type_decoration = type_info->symbol;
+                expression->type_decoration = expression->arguments.empty()
+                    ? type_info->symbol
+                    : type(std::make_shared<instantiated_type>(type_info->symbol,
+                                resolve_arguments(expression->arguments)));
             }
         }
         else
@@ -884,7 +927,16 @@ namespace elna::boot
             }
             else if (auto procedure_symbol = from_symbol_table->is_procedure())
             {
-                expression->type_decoration = type(std::make_shared<procedure_type>(procedure_symbol->symbol));
+                type procedure = type(std::make_shared<procedure_type>(procedure_symbol->symbol));
+
+                if (!expression->arguments.empty())
+                {
+                    expression->argument_types = resolve_arguments(expression->arguments);
+                    procedure = substitute(procedure, procedure_symbol->parameters,
+                            expression->argument_types);
+                }
+                expression->type_decoration = procedure;
+                return;
             }
         }
         else
@@ -892,6 +944,32 @@ namespace elna::boot
             add_error<symbol_declaration_error>(expression->position(),
                     expression->name, symbol_declaration_error::kind::undeclared_symbol);
         }
+        if (!expression->arguments.empty() && !this->current_type.empty())
+        {
+            const type generic = this->current_type;
+
+            expression->argument_types = resolve_arguments(expression->arguments);
+            this->current_type = type(std::make_shared<instantiated_type>(generic,
+                        std::vector<type>(expression->argument_types)));
+        }
+        // Type check decides whether the name was applied correctly, so what a
+        // type expression resolved to has to reach it.
+        if (expression->type_decoration.empty())
+        {
+            expression->type_decoration = this->current_type;
+        }
+    }
+
+    std::vector<type> resolving_visitor::resolve_arguments(const std::vector<type_expression *>& arguments)
+    {
+        std::vector<type> result;
+
+        result.reserve(arguments.size());
+        for (type_expression *argument : arguments)
+        {
+            result.push_back(resolve_type(*argument));
+        }
+        return result;
     }
 
     void resolving_visitor::visit(array_access_expression *expression)
@@ -1096,6 +1174,17 @@ namespace elna::boot
         {
             return find_alias_cycle(being_resolved, link->base, alias_path, state);
         }
+        else if (auto link = referent.get<generic_type>())
+        {
+            return find_alias_cycle(being_resolved, link->referent, alias_path, state);
+        }
+        else if (auto link = referent.get<instantiated_type>())
+        {
+            // Erasure is argument blind, so the arguments cannot close a cycle
+            // the generic does not close on its own. This is what lets
+            // polymorphic recursion terminate.
+            return find_alias_cycle(being_resolved, link->generic, alias_path, state);
+        }
         else if (auto link = referent.get<procedure_type>())
         {
             const std::size_t saved_path = alias_path.size();
@@ -1196,8 +1285,22 @@ namespace elna::boot
 
     void declaration_visitor::visit(type_declaration *declaration)
     {
+        const bool is_generic = !declaration->parameters.empty();
+        std::vector<type> parameters;
+
+        if (is_generic)
+        {
+            this->bag.enter();
+            parameters = enter_parameters(declaration->parameters);
+        }
         type underlying = resolve_type(declaration->underlying_type());
 
+        if (is_generic)
+        {
+            this->bag.leave();
+            underlying = type(std::make_shared<generic_type>(std::move(parameters), underlying));
+        }
+
         // Reject the cycle and wire an empty referent: the declaration still
         // resolves and is entered, so its uses degrade silently.
         if (auto cycle = find_alias_cycle(
@@ -1228,12 +1331,17 @@ namespace elna::boot
 
     void declaration_visitor::visit(procedure_declaration *declaration)
     {
+        // The scope is opened before the heading is built so that the type
+        // parameters are visible in it, and it becomes the body's scope, which
+        // is why the body sees them too.
+        const std::shared_ptr<symbol_table> scope = this->bag.enter();
+        const std::vector<type> type_parameters = enter_parameters(declaration->parameters);
         auto [heading, parameter_names] = build_procedure(declaration->heading());
         std::shared_ptr<procedure_info> info;
 
         if (declaration->body.has_value())
         {
-            info = std::make_shared<procedure_info>(heading, std::move(parameter_names), this->bag.enter());
+            info = std::make_shared<procedure_info>(heading, std::move(parameter_names), scope);
             auto name_iterator = std::cbegin(info->names);
             auto type_iterator = std::cbegin(info->symbol.parameters);
 
@@ -1245,12 +1353,13 @@ namespace elna::boot
                 ++name_iterator;
                 ++type_iterator;
             }
-            this->bag.leave();
         }
         else
         {
             info = std::make_shared<procedure_info>(heading, std::move(parameter_names));
         }
+        this->bag.leave();
+        info->parameters = type_parameters;
         info->exported = declaration->identifier.exported();
         info->position.emplace(declaration->position());
         info->file = this->module_file;
diff --git a/boot/parser.yy b/boot/parser.yy
index ba611b5..00bdae8 100644
--- a/boot/parser.yy
+++ b/boot/parser.yy
@@ -88,6 +88,7 @@ along with GCC; see the file COPYING3.  If not see
 %token <std::string> STRING
 %token <bool> BOOLEAN
 %token LEFT_PAREN "(" RIGHT_PAREN ")" LEFT_SQUARE "[" RIGHT_SQUARE "]"
+%token GENERIC_OPEN "#["
 %token LEFT_BRACE "{" RIGHT_BRACE "}"
 %token ASSIGNMENT ":="
     EXCLAMATION "!" ARROW "->"
@@ -157,7 +158,8 @@ along with GCC; see the file COPYING3.  If not see
 %type <std::unique_ptr<elna::boot::identifier_definition>> identifier_definition;
 %type <std::vector<elna::boot::identifier_definition>> identifier_definitions;
 %type <std::vector<std::string>> import_declaration;
-%type <std::vector<elna::boot::identifier>> required_identifiers optional_identifiers;
+%type <std::vector<elna::boot::identifier>> required_identifiers optional_identifiers generic_parameters;
+%type <elna::boot::named_expression *> name_reference;
 %type <std::vector<elna::boot::import_declaration *>> import_declarations import_part;
 %type <std::unique_ptr<elna::boot::array_type_expression>> array_type_expression;
 %%
@@ -200,14 +202,16 @@ return_declaration:
 procedure_heading: "(" optional_fields ")" return_declaration
         { $$ = std::make_unique<boot::procedure_type_expression>(boot::make_position(@$), $2, $4); }
 procedure_declaration:
-    "proc" identifier_definition procedure_heading procedure_body
+    "proc" identifier_definition generic_parameters procedure_heading procedure_body
         {
             $$ = new boot::procedure_declaration(boot::make_position(@$),
-                    std::move(*$2), $3.release(), std::move(*$4));
+                    std::move(*$2), $4.release(), std::move(*$5));
+            $$->parameters = $3;
         }
-    | "proc" identifier_definition procedure_heading "extern"
+    | "proc" identifier_definition generic_parameters procedure_heading "extern"
         {
-            $$ = new boot::procedure_declaration(boot::make_position(@$), std::move(*$2), $3.release());
+            $$ = new boot::procedure_declaration(boot::make_position(@$), std::move(*$2), $4.release());
+            $$->parameters = $3;
         }
 procedure_part:
     %empty {}
@@ -349,9 +353,14 @@ simple_expression:
         }
     | call_expression { $$ = $1.release(); }
     | "(" expression ")" { $$ = $2; }
-    | identifier "{" field_initializers "}"
+    | name_reference "{" field_initializers "}"
         {
-            $$ = new boot::record_constructor_expression(boot::make_position(@$), std::move(*$1), $3);
+            boot::named_expression *reference = $1;
+
+            $$ = new boot::record_constructor_expression(boot::make_position(@$),
+                    boot::identifier(reference->name, reference->position()),
+                    std::move(reference->arguments), $3);
+            delete reference;
         }
     | "[" required_expressions "]"
         {
@@ -489,8 +498,12 @@ designator_expression:
         { $$ = new boot::field_access_expression(boot::make_position(@$), $1, std::move(*$3)); }
     | simple_expression "^"
         { $$ = new boot::dereference_expression(boot::make_position(@$), $1); }
-    | IDENTIFIER
+    | name_reference { $$ = $1; }
+name_reference:
+    IDENTIFIER
         { $$ = new boot::named_expression(boot::make_position(@$), $1); }
+    | IDENTIFIER "#[" type_expressions "]"
+        { $$ = new boot::named_expression(boot::make_position(@$), $1, $3); }
 statement:
     designator_expression ":=" expression
         { $$ = new boot::assign_statement(boot::make_position(@$), $1, $3); }
@@ -582,9 +595,14 @@ type_expression:
         {
             $$ = new boot::record_type_expression(boot::make_position(@$), $2);
         }
-    | "record" "(" identifier ")" optional_fields "end"
+    | "record" "(" name_reference ")" optional_fields "end"
         {
-            $$ = new boot::record_type_expression(boot::make_position(@$), $5, std::move(*$3));
+            boot::named_expression *reference = $3;
+
+            $$ = new boot::record_type_expression(boot::make_position(@$), $5,
+                    boot::identifier(reference->name, reference->position()),
+                    std::move(reference->arguments));
+            delete reference;
         }
     | "proc" procedure_heading
         {
@@ -594,10 +612,10 @@ type_expression:
         {
             $$ = new boot::enumeration_type_expression(boot::make_position(@$), $2);
         }
-    | IDENTIFIER
-        {
-            $$ = new boot::named_expression(boot::make_position(@$), $1);
-        }
+    | name_reference { $$ = $1; }
+generic_parameters:
+    %empty {}
+    | "#[" required_identifiers "]" { $$ = $2; }
 required_identifiers:
     identifier "," required_identifiers
         {
@@ -654,14 +672,16 @@ import_declarations:
 import_part:
     %empty {}
     | "import" import_declarations { $$ = $2; }
-type_declaration: identifier_definition "=" type_expression
+type_declaration: identifier_definition generic_parameters "=" type_expression
         {
-            $$ = new boot::type_declaration(boot::make_position(@$), std::move(*$1), $3);
+            $$ = new boot::type_declaration(boot::make_position(@$), std::move(*$1), $4);
+            $$->parameters = $2;
         }
-    | identifier_definition "=" "extern"
+    | identifier_definition generic_parameters "=" "extern"
         {
             $$ = new boot::type_declaration(boot::make_position(@$), std::move(*$1),
                     new boot::extern_type_expression(boot::make_position(@$)));
+            $$->parameters = $2;
         }
 type_declarations:
     type_declaration type_declarations
diff --git a/boot/symbol.cc b/boot/symbol.cc
index 0d847e1..9092866 100644
--- a/boot/symbol.cc
+++ b/boot/symbol.cc
@@ -119,6 +119,22 @@ namespace elna::boot
             return right_procedure != nullptr && left_procedure->return_type == right_procedure->return_type
                 && left_procedure->parameters == right_procedure->parameters;
         }
+        if (auto left_parameter = resolved_this.get<parameter_type>())
+        {
+            return left_parameter == resolved_that.get<parameter_type>();
+        }
+        if (auto left_generic = resolved_this.get<generic_type>())
+        {
+            return left_generic == resolved_that.get<generic_type>();
+        }
+        if (auto left_instance = resolved_this.get<instantiated_type>())
+        {
+            auto right_instance = resolved_that.get<instantiated_type>();
+
+            return right_instance != nullptr
+                && left_instance->generic == right_instance->generic
+                && left_instance->arguments == right_instance->arguments;
+        }
         return resolved_this.empty() && resolved_that.empty();
     }
 
@@ -192,6 +208,18 @@ namespace elna::boot
             {
                 return "extern";
             }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<parameter_type>>)
+            {
+                return payload->name;
+            }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<generic_type>>)
+            {
+                return "generic";
+            }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<instantiated_type>>)
+            {
+                return payload->generic.to_string() + "#[" + join(payload->arguments) + "]";
+            }
         }, payload);
     }
 
@@ -240,6 +268,21 @@ namespace elna::boot
     {
     }
 
+    parameter_type::parameter_type(const std::string& name)
+        : name(name)
+    {
+    }
+
+    generic_type::generic_type(std::vector<type>&& parameters, type referent)
+        : parameters(std::move(parameters)), referent(std::move(referent))
+    {
+    }
+
+    instantiated_type::instantiated_type(type generic, std::vector<type>&& arguments)
+        : generic(std::move(generic)), arguments(std::move(arguments))
+    {
+    }
+
     info::~info() = default;
 
     std::shared_ptr<type_info> info::is_type()
@@ -471,12 +514,171 @@ namespace elna::boot
         }
     }
 
+    type unwrap_aliases(const type& checked)
+    {
+        if (auto alias = checked.get<alias_type>())
+        {
+            return unwrap_aliases(alias->referent);
+        }
+        return checked;
+    }
+
+    std::shared_ptr<generic_type> unwrap_generic(const type& checked)
+    {
+        return unwrap_aliases(checked).get<generic_type>();
+    }
+
+    type substitute(const type& subject, const std::vector<type>& parameters,
+            const std::vector<type>& arguments)
+    {
+        if (auto parameter = subject.get<parameter_type>())
+        {
+            for (std::size_t i = 0; i < parameters.size() && i < arguments.size(); ++i)
+            {
+                if (parameters[i].get<parameter_type>() == parameter)
+                {
+                    return arguments[i];
+                }
+            }
+            return subject;
+        }
+        if (auto pointer = subject.get<pointer_type>())
+        {
+            return type(std::make_shared<pointer_type>(
+                        substitute(pointer->base, parameters, arguments)));
+        }
+        if (auto slice = subject.get<slice_type>())
+        {
+            return type(std::make_shared<slice_type>(
+                        substitute(slice->base, parameters, arguments)));
+        }
+        if (auto array = subject.get<array_type>())
+        {
+            return type(std::make_shared<array_type>(
+                        substitute(array->base, parameters, arguments), array->size));
+        }
+        if (auto qualified = subject.get<constant_type>())
+        {
+            return type(std::make_shared<constant_type>(
+                        substitute(qualified->unqualified, parameters, arguments)));
+        }
+        if (auto procedure = subject.get<procedure_type>())
+        {
+            procedure_type::return_t result_return = procedure->return_type;
+
+            if (!result_return.no_return && !result_return.proper_type.empty())
+            {
+                result_return = procedure_type::return_t(
+                        substitute(result_return.proper_type, parameters, arguments));
+            }
+            auto result = std::make_shared<procedure_type>(std::move(result_return));
+
+            result->parameters.reserve(procedure->parameters.size());
+            for (const type& parameter_type : procedure->parameters)
+            {
+                result->parameters.push_back(substitute(parameter_type, parameters, arguments));
+            }
+            return type(result);
+        }
+        if (auto instance = subject.get<instantiated_type>())
+        {
+            std::vector<type> substituted;
+
+            substituted.reserve(instance->arguments.size());
+            for (const type& argument : instance->arguments)
+            {
+                substituted.push_back(substitute(argument, parameters, arguments));
+            }
+            return type(std::make_shared<instantiated_type>(instance->generic, std::move(substituted)));
+        }
+        return subject;
+    }
+
+    type instantiate(const std::shared_ptr<instantiated_type>& instance)
+    {
+        std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+        return generic == nullptr
+            ? type()
+            : substitute(generic->referent, generic->parameters, instance->arguments);
+    }
+
+    type erase_generic(const type& checked)
+    {
+        type resolved = resolve_underlying_type(checked);
+
+        if (auto instance = resolved.get<instantiated_type>())
+        {
+            std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+            return generic == nullptr ? type() : resolve_underlying_type(generic->referent);
+        }
+        if (auto generic = resolved.get<generic_type>())
+        {
+            return resolve_underlying_type(generic->referent);
+        }
+        return resolved;
+    }
+
+    /*
+     * Rewrites a type taken from an instantiation's erased referent so that it
+     * reads as the instantiation sees it. The identity for anything else.
+     */
+    static type substitute_from(const type& subject, const type& taken)
+    {
+        auto instance = subject.get<instantiated_type>();
+
+        if (instance == nullptr)
+        {
+            return taken;
+        }
+        std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+        return generic == nullptr
+            ? type()
+            : substitute(taken, generic->parameters, instance->arguments);
+    }
+
+    type base_of(const type& derived)
+    {
+        const type resolved = resolve_underlying_type(derived);
+        auto record = erase_generic(resolved).get<record_type>();
+
+        return record == nullptr || record->base.empty()
+            ? type()
+            : substitute_from(resolved, record->base);
+    }
+
+    bool is_base_of(const type& base, const type& derived)
+    {
+        for (type current = base_of(derived); !current.empty(); current = base_of(current))
+        {
+            if (current == base)
+            {
+                return true;
+            }
+        }
+        return false;
+    }
+
     type resolve_aliases(const type& checked)
     {
         if (auto alias = checked.get<alias_type>())
         {
             return resolve_aliases(alias->referent);
         }
+        if (auto instance = checked.get<instantiated_type>())
+        {
+            std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+            // A record referent makes the instantiation nominal, so resolution
+            // stops here and Stack#[^File] stays distinct from Stack#[^Socket].
+            if (generic == nullptr || unwrap_aliases(generic->referent).get<record_type>() != nullptr)
+            {
+                return checked;
+            }
+            return resolve_aliases(instantiate(instance));
+        }
         return checked;
     }
 
@@ -535,6 +737,7 @@ namespace elna::boot
     {
         return checked.get<pointer_type>() != nullptr
             || checked.get<procedure_type>() != nullptr
+            || checked.get<parameter_type>() != nullptr
             || is_primitive_type(checked, "Pointer");
     }
 
@@ -575,20 +778,18 @@ namespace elna::boot
     {
         const type resolved_type = resolve_underlying_type(composite_type);
 
-        if (auto record = resolved_type.get<record_type>())
+        if (auto record = erase_generic(resolved_type).get<record_type>())
         {
             for (const auto& [name, field_type] : record->fields)
             {
                 if (name == field_name)
                 {
-                    return field_type;
+                    return substitute_from(resolved_type, field_type);
                 }
             }
-            if (!record->base.empty())
-            {
-                return lookup_field(record->base, field_name);
-            }
         }
-        return type();
+        const type base = base_of(resolved_type);
+
+        return base.empty() ? type() : lookup_field(base, field_name);
     }
 }
diff --git a/boot/type_check.cc b/boot/type_check.cc
index cdc78df..ab22a1c 100644
--- a/boot/type_check.cc
+++ b/boot/type_check.cc
@@ -114,6 +114,51 @@ namespace elna::boot
         }, this->payload);
     }
 
+    generic_error::generic_error(const source_position position, const std::string& generic_name,
+            payload_type payload)
+        : diagnostic(position), generic_name(generic_name), payload(std::move(payload))
+    {
+    }
+
+    std::string generic_error::what() const
+    {
+        return std::visit([this](auto&& payload) -> std::string
+        {
+            using T = std::decay_t<decltype(payload)>;
+
+            if constexpr (std::is_same_v<T, not_generic>)
+            {
+                return "'" + this->generic_name + "' is not generic and cannot take type arguments";
+            }
+            else if constexpr (std::is_same_v<T, unused_parameter>)
+            {
+                return "Type parameter '" + payload.parameter + "' of '"
+                    + this->generic_name + "' is not used";
+            }
+            else if constexpr (std::is_same_v<T, argument_not_pointer>)
+            {
+                return "Type '" + payload.actual.to_string() + "' cannot be a type argument of '"
+                    + this->generic_name + "', it is not a pointer type";
+            }
+            else if constexpr (std::is_same_v<T, constant_argument>)
+            {
+                return "Constant type '" + payload.actual.to_string()
+                    + "' cannot be a type argument of '" + this->generic_name + "'";
+            }
+            else if constexpr (std::is_same_v<T, uninferrable_parameter>)
+            {
+                return "Type parameter '" + payload.parameter + "' of '" + this->generic_name
+                    + "' cannot be inferred, give the type arguments explicitly";
+            }
+            else if constexpr (std::is_same_v<T, shape_mismatch>)
+            {
+                return "Cannot infer the type arguments of '" + this->generic_name
+                    + "': parameter type '" + payload.declared.to_string()
+                    + "' does not match argument type '" + payload.actual.to_string() + "'";
+            }
+        }, this->payload);
+    }
+
     /// The program body is the only callable without a name.
     static std::string describe_callable(const std::string& identifier)
     {
@@ -228,6 +273,12 @@ namespace elna::boot
             case opaque_arithmetic:
                 return "Opaque type '" + this->actual.to_string()
                     + "' cannot be used as an element type in pointer arithmetic";
+            case dereference_of_parameter:
+                return "Type parameter '" + this->actual.to_string()
+                    + "' cannot be dereferenced, its pointee is unknown";
+            case parameter_arithmetic:
+                return "Type parameter '" + this->actual.to_string()
+                    + "' cannot be used in pointer arithmetic, its element size is unknown";
             case zero_sized:
                 return "Zero-sized type '" + this->actual.to_string()
                     + "' cannot be declared";
@@ -261,8 +312,20 @@ namespace elna::boot
             case array:
                 entity = "array initializer '" + this->applicand + "'";
                 break;
+            case generic:
+                entity = "generic '" + this->applicand + "'";
+                break;
+        }
+        std::string noun = "arguments";
+
+        if (this->m_kind == kind::array)
+        {
+            noun = "elements";
+        }
+        else if (this->m_kind == kind::generic)
+        {
+            noun = "type arguments";
         }
-        const std::string noun = this->m_kind == kind::array ? "elements" : "arguments";
         const std::string quantifier = actual > expected ? "many" : "few";
 
         return "Too " + quantifier + " " + noun + " for " + entity
@@ -348,17 +411,25 @@ namespace elna::boot
     }
 
     /*
-     * Scaling an offset needs the pointee size, which an opaque type doesn't
-     * have. Only a pointer_type scales; the generic Pointer and procedure
-     * values advance byte-wise.
+     * Scaling an offset needs the pointee size, which neither an opaque type
+     * nor a type parameter has. Only a pointer_type scales; the generic
+     * Pointer and procedure values advance byte-wise.
      */
-    static std::optional<type> find_opaque_arithmetic(binary_operator operation,
+    static std::optional<type> find_arithmetic_violation(binary_operator operation,
             const type& lhs, const type& rhs)
     {
         if (operation != binary_operator::sum && operation != binary_operator::subtraction)
         {
             return std::nullopt;
         }
+        if (lhs.get<parameter_type>() != nullptr)
+        {
+            return lhs;
+        }
+        if (rhs.get<parameter_type>() != nullptr)
+        {
+            return rhs;
+        }
         const bool lhs_integral = is_integral_type(lhs);
 
         if (lhs_integral == is_integral_type(rhs))
@@ -444,19 +515,6 @@ namespace elna::boot
      *
      * Base record type must not be null. Derived record type may be null.
      */
-    static bool is_base_of(const std::shared_ptr<record_type>& base,
-            const std::shared_ptr<record_type>& derived)
-    {
-        if (derived != nullptr)
-        {
-            if (auto current_record = resolve_underlying_type(derived->base).get<record_type>())
-            {
-                return current_record == base || is_base_of(base, current_record);
-            }
-        }
-        return false;
-    }
-
     assign_check::verdict assign_check::guard_const_laundering() const
     {
         if (!is_primitive_type(ctx.aliased_assignee, "Pointer"))
@@ -519,10 +577,11 @@ namespace elna::boot
             return verdict::reject;
         }
         // A pointer to a record can be assigned to a pointer to its base type.
-        if (auto assignee_record = resolve_underlying_type(assignee_ptr->base).get<record_type>())
+        // An instantiation is terminal in resolution, so the erased view is
+        // what decides whether a record is in play at all.
+        if (erase_generic(assignee_ptr->base).get<record_type>() != nullptr)
         {
-            return is_base_of(assignee_record,
-                    resolve_underlying_type(assignment_ptr->base).get<record_type>())
+            return is_base_of(assignee_ptr->base, assignment_ptr->base)
                 ? verdict::accept : verdict::pass;
         }
         return verdict::pass;
@@ -631,6 +690,10 @@ namespace elna::boot
         }
         walking_visitor::visit(declaration);
 
+        check_parameters_used(declaration->position(), declaration->identifier.name(),
+                this->current_procedure->parameters,
+                type(std::make_shared<procedure_type>(this->current_procedure->symbol)));
+
         std::size_t parameter_index = 0;
 
         for (const type& parameter : this->current_procedure->symbol.parameters)
@@ -870,6 +933,13 @@ namespace elna::boot
     {
         walking_visitor::visit(declaration);
         auto unresolved_type = this->bag.lookup(declaration->identifier.name())->is_type()->symbol.get<alias_type>();
+
+        if (auto generic = unresolved_type->referent.get<generic_type>())
+        {
+            check_parameters_used(declaration->position(), declaration->identifier.name(),
+                    generic->parameters, generic->referent);
+            return;
+        }
         const type referent = resolve_aliases(unresolved_type->referent);
 
         if (auto record = referent.get<record_type>())
@@ -948,7 +1018,7 @@ namespace elna::boot
             }
             else
             {
-                type const base_type = resolve_underlying_type(base_symbol->is_type()->symbol);
+                type const base_type = erase_generic(base_symbol->is_type()->symbol);
                 if (base_type.get<record_type>() == nullptr)
                 {
                     add_error<type_requirement_error>(expression->position(),
@@ -959,11 +1029,343 @@ namespace elna::boot
         walking_visitor::visit(expression);
     }
 
+    /*
+     * Aliases are not entered: a parameter is only in scope in its own
+     * declaration, so another declaration can never mention it. Instantiations
+     * contribute their arguments and not their generic, which is what makes
+     * the walk terminate on a recursive generic.
+     */
+    static bool occurs_in(const type& parameter, const type& subject)
+    {
+        if (subject.get<parameter_type>() == parameter.get<parameter_type>())
+        {
+            return true;
+        }
+        if (auto pointer = subject.get<pointer_type>())
+        {
+            return occurs_in(parameter, pointer->base);
+        }
+        if (auto slice = subject.get<slice_type>())
+        {
+            return occurs_in(parameter, slice->base);
+        }
+        if (auto array = subject.get<array_type>())
+        {
+            return occurs_in(parameter, array->base);
+        }
+        if (auto qualified = subject.get<constant_type>())
+        {
+            return occurs_in(parameter, qualified->unqualified);
+        }
+        if (auto record = subject.get<record_type>())
+        {
+            for (const auto& [field_name, field_type] : record->fields)
+            {
+                if (occurs_in(parameter, field_type))
+                {
+                    return true;
+                }
+            }
+            return !record->base.empty() && occurs_in(parameter, record->base);
+        }
+        if (auto procedure = subject.get<procedure_type>())
+        {
+            for (const type& parameter_type : procedure->parameters)
+            {
+                if (occurs_in(parameter, parameter_type))
+                {
+                    return true;
+                }
+            }
+            return !procedure->return_type.proper_type.empty()
+                && occurs_in(parameter, procedure->return_type.proper_type);
+        }
+        if (auto instance = subject.get<instantiated_type>())
+        {
+            for (const type& argument : instance->arguments)
+            {
+                if (occurs_in(parameter, argument))
+                {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    void type_analysis_visitor::check_parameters_used(const source_position position,
+            const std::string& name, const std::vector<type>& parameters, const type& heading)
+    {
+        for (const type& parameter : parameters)
+        {
+            if (!occurs_in(parameter, heading))
+            {
+                add_error<generic_error>(position, name,
+                        generic_error::unused_parameter{ parameter.to_string() });
+            }
+        }
+    }
+
+    /*
+     * Walks a declared parameter type and an actual argument type in parallel,
+     * binding a parameter the first time it is met and leaving every later
+     * occurrence to the ordinary assignability check. Both sides are resolved
+     * at every step, so a transparent instantiation is seen through and only a
+     * record-referent one is compared as an instantiation.
+     *
+     * Returns false when the walk fails on shape rather than on type.
+     */
+    static bool bind_arguments(const std::vector<type>& parameters, std::vector<type>& bindings,
+            const type& declared, const type& actual)
+    {
+        const type left = resolve_aliases(declared);
+        const type right = resolve_aliases(actual);
+
+        if (auto parameter = left.get<parameter_type>())
+        {
+            for (std::size_t i = 0; i < parameters.size(); ++i)
+            {
+                if (parameters[i].get<parameter_type>() == parameter && bindings[i].empty())
+                {
+                    // The actual type is recorded as it stands, which inside a
+                    // generic body may itself be an abstract parameter.
+                    bindings[i] = actual;
+                }
+            }
+            return true;
+        }
+        if (auto left_pointer = left.get<pointer_type>())
+        {
+            auto right_pointer = right.get<pointer_type>();
+
+            return right_pointer != nullptr
+                && bind_arguments(parameters, bindings, left_pointer->base, right_pointer->base);
+        }
+        if (auto left_slice = left.get<slice_type>())
+        {
+            auto right_slice = right.get<slice_type>();
+
+            return right_slice != nullptr
+                && bind_arguments(parameters, bindings, left_slice->base, right_slice->base);
+        }
+        if (auto left_array = left.get<array_type>())
+        {
+            auto right_array = right.get<array_type>();
+
+            return right_array != nullptr
+                && bind_arguments(parameters, bindings, left_array->base, right_array->base);
+        }
+        if (auto left_constant = left.get<constant_type>())
+        {
+            auto right_constant = right.get<constant_type>();
+
+            return right_constant != nullptr
+                && bind_arguments(parameters, bindings,
+                        left_constant->unqualified, right_constant->unqualified);
+        }
+        if (auto left_instance = left.get<instantiated_type>())
+        {
+            for (type candidate = right; !candidate.empty(); candidate = base_of(candidate))
+            {
+                auto right_instance = resolve_aliases(candidate).get<instantiated_type>();
+
+                if (right_instance == nullptr
+                        || !(left_instance->generic == right_instance->generic)
+                        || left_instance->arguments.size() != right_instance->arguments.size())
+                {
+                    continue;
+                }
+                for (std::size_t i = 0; i < left_instance->arguments.size(); ++i)
+                {
+                    if (!bind_arguments(parameters, bindings,
+                                left_instance->arguments.at(i), right_instance->arguments.at(i)))
+                    {
+                        return false;
+                    }
+                }
+                return true;
+            }
+            return false;
+        }
+        if (auto left_procedure = left.get<procedure_type>())
+        {
+            auto right_procedure = right.get<procedure_type>();
+
+            if (right_procedure == nullptr
+                    || left_procedure->parameters.size() != right_procedure->parameters.size())
+            {
+                return false;
+            }
+            for (std::size_t i = 0; i < left_procedure->parameters.size(); ++i)
+            {
+                if (!bind_arguments(parameters, bindings,
+                            left_procedure->parameters.at(i), right_procedure->parameters.at(i)))
+                {
+                    return false;
+                }
+            }
+            return left_procedure->return_type.proper_type.empty()
+                || bind_arguments(parameters, bindings,
+                        left_procedure->return_type.proper_type,
+                        right_procedure->return_type.proper_type);
+        }
+        return true;
+    }
+
+    void type_analysis_visitor::check_arguments(const named_expression& reference,
+            const std::vector<type>& arguments)
+    {
+        for (const type& argument : arguments)
+        {
+            const type resolved = resolve_aliases(argument);
+
+            if (resolved.get<constant_type>() != nullptr)
+            {
+                add_error<generic_error>(reference.position(), reference.name,
+                        generic_error::constant_argument{ argument });
+            }
+            else if (!argument.empty() && !is_any_pointer_type(resolve_underlying_type(argument)))
+            {
+                add_error<generic_error>(reference.position(), reference.name,
+                        generic_error::argument_not_pointer{ argument });
+            }
+        }
+    }
+
+    void type_analysis_visitor::visit(named_expression *expression)
+    {
+        walking_visitor::visit(expression);
+
+        // A generic procedure keeps its parameters on the symbol rather than in
+        // its type, which erasure has already substituted away.
+        std::shared_ptr<info> const symbol = this->bag.lookup(expression->name);
+        std::shared_ptr<procedure_info> const procedure =
+            symbol == nullptr ? nullptr : symbol->is_procedure();
+
+        if (procedure != nullptr && !procedure->parameters.empty())
+        {
+            // An omitted list is inferred at the call, and only there: in value
+            // position there is nothing to infer from.
+            const bool omitted = expression->arguments.empty() && this->in_callable_position;
+
+            if (!omitted && expression->arguments.size() != procedure->parameters.size())
+            {
+                add_error<argument_count_error>(expression->position(),
+                        argument_count_error::kind::generic, expression->name,
+                        procedure->parameters.size(), expression->arguments.size());
+            }
+            else if (!expression->arguments.empty())
+            {
+                check_arguments(*expression, expression->argument_types);
+            }
+            return;
+        }
+        const type denoted = expression->type_decoration;
+
+        if (auto instance = denoted.get<instantiated_type>())
+        {
+            std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+            if (generic == nullptr)
+            {
+                add_error<generic_error>(expression->position(), expression->name,
+                        generic_error::not_generic{});
+            }
+            else if (instance->arguments.size() != generic->parameters.size())
+            {
+                add_error<argument_count_error>(expression->position(),
+                        argument_count_error::kind::generic, expression->name,
+                        generic->parameters.size(), instance->arguments.size());
+            }
+            else
+            {
+                check_arguments(*expression, expression->argument_types);
+            }
+        }
+        else if (std::shared_ptr<generic_type> const generic = unwrap_generic(denoted))
+        {
+            // A bare generic is not a type at all, which is simply zero
+            // arguments where some were expected.
+            add_error<argument_count_error>(expression->position(),
+                    argument_count_error::kind::generic, expression->name,
+                    generic->parameters.size(), 0);
+        }
+        else if (procedure != nullptr && !expression->arguments.empty())
+        {
+            add_error<generic_error>(expression->position(), expression->name,
+                    generic_error::not_generic{});
+        }
+    }
+
+    type type_analysis_visitor::infer_call(procedure_call& call, const named_expression& reference,
+            const procedure_info& procedure)
+    {
+        std::vector<type> bindings(procedure.parameters.size());
+        auto argument_iterator = std::cbegin(call.arguments);
+        auto declared_iterator = std::cbegin(procedure.symbol.parameters);
+
+        while (argument_iterator != std::cend(call.arguments)
+                && declared_iterator != std::cend(procedure.symbol.parameters))
+        {
+            if (!bind_arguments(procedure.parameters, bindings,
+                        *declared_iterator, (*argument_iterator)->type_decoration))
+            {
+                add_error<generic_error>((*argument_iterator)->position(), reference.name,
+                        generic_error::shape_mismatch{
+                            .declared = *declared_iterator,
+                            .actual = (*argument_iterator)->type_decoration
+                        });
+            }
+            ++argument_iterator;
+            ++declared_iterator;
+        }
+        for (std::size_t i = 0; i < bindings.size(); ++i)
+        {
+            if (bindings.at(i).empty())
+            {
+                add_error<generic_error>(call.position(), reference.name,
+                        generic_error::uninferrable_parameter{
+                            procedure.parameters.at(i).to_string()
+                        });
+                return type();
+            }
+        }
+        check_arguments(reference, bindings);
+
+        return substitute(type(std::make_shared<procedure_type>(procedure.symbol)),
+                procedure.parameters, bindings);
+    }
+
     void type_analysis_visitor::visit(procedure_call *call)
     {
+        const named_expression *reference = call->callable().is_named();
+
+        this->in_callable_position = reference != nullptr;
         call->callable().accept(this);
+        this->in_callable_position = false;
+
+        type callable_type = call->callable().type_decoration;
+        std::shared_ptr<procedure_info> inferred;
+
+        if (reference != nullptr && reference->arguments.empty())
+        {
+            std::shared_ptr<info> const symbol = this->bag.lookup(reference->name);
+            std::shared_ptr<procedure_info> const procedure =
+                symbol == nullptr ? nullptr : symbol->is_procedure();
 
-        if (auto procedure = call->callable().type_decoration.get<procedure_type>())
+            if (procedure != nullptr && !procedure->parameters.empty())
+            {
+                // Inference reads the argument types, so they are decorated
+                // before the parameter types they will be checked against exist.
+                for (expression *argument : call->arguments)
+                {
+                    argument->accept(this);
+                }
+                inferred = procedure;
+                callable_type = infer_call(*call, *reference, *procedure);
+            }
+        }
+        if (auto procedure = callable_type.get<procedure_type>())
         {
             std::vector<expression *>::const_iterator argument_iterator = std::cbegin(call->arguments);
             std::vector<type>::const_iterator type_iterator = std::cbegin(procedure->parameters);
@@ -971,7 +1373,10 @@ namespace elna::boot
             while (argument_iterator != std::cend(call->arguments)
                     && type_iterator != std::cend(procedure->parameters))
             {
-                (*argument_iterator)->accept(this);
+                if (inferred == nullptr)
+                {
+                    (*argument_iterator)->accept(this);
+                }
                 if (!is_assignable_from(*type_iterator, (*argument_iterator)->type_decoration))
                 {
                     add_error<type_mismatch_error>(
@@ -998,18 +1403,18 @@ namespace elna::boot
                 }
             }
         }
-        else if (!call->callable().type_decoration.empty())
+        else if (inferred == nullptr && !call->callable().type_decoration.empty())
         {
             add_error<type_mismatch_error>(call->position(),
                     call->callable().type_decoration,
                     type_mismatch_error::expected_type{ type(std::make_shared<procedure_type>()) });
         }
-        // else callable is not declared which is already reported.
+        // else callable is not declared, or inference failed and reported.
     }
 
     void type_analysis_visitor::visit(record_constructor_expression *expression)
     {
-        auto record = resolve_underlying_type(expression->type_decoration).get<record_type>();
+        auto record = erase_generic(expression->type_decoration).get<record_type>();
 
         if (record == nullptr)
         {
@@ -1139,7 +1544,14 @@ namespace elna::boot
     {
         walking_visitor::visit(expression);
 
-        if (resolve_underlying_type(expression->base().type_decoration).get<pointer_type>() == nullptr)
+        const type resolved_base = resolve_underlying_type(expression->base().type_decoration);
+
+        if (resolved_base.get<parameter_type>() != nullptr)
+        {
+            add_error<type_requirement_error>(expression->position(), expression->base().type_decoration,
+                    type_requirement_error::kind::dereference_of_parameter);
+        }
+        else if (resolved_base.get<pointer_type>() == nullptr)
         {
             add_error<type_requirement_error>(expression->position(), expression->base().type_decoration,
                     type_requirement_error::kind::dereference_of_non_pointer);
@@ -1265,10 +1677,12 @@ namespace elna::boot
             };
             add_error<type_mismatch_error>(expression->position(), expression->lhs().type_decoration, binary_error);
         }
-        else if (auto opaque = find_opaque_arithmetic(operation, lhs_resolved, rhs_resolved))
+        else if (auto violation = find_arithmetic_violation(operation, lhs_resolved, rhs_resolved))
         {
-            add_error<type_requirement_error>(expression->position(),
-                    opaque.value(), type_requirement_error::kind::opaque_arithmetic);
+            add_error<type_requirement_error>(expression->position(), violation.value(),
+                    violation->get<parameter_type>() != nullptr
+                        ? type_requirement_error::kind::parameter_arithmetic
+                        : type_requirement_error::kind::opaque_arithmetic);
         }
     }
 
diff --git a/gcc/gcc/elna-builtins.cc b/gcc/gcc/elna-builtins.cc
index 637e37a..7d2f8f0 100644
--- a/gcc/gcc/elna-builtins.cc
+++ b/gcc/gcc/elna-builtins.cc
@@ -255,6 +255,20 @@ namespace elna::gcc
         {
             return TREE_TYPE(handle_symbol(reference->name, reference, symbols));
         }
+        else if (type.get<boot::parameter_type>() != nullptr)
+        {
+            return elna_pointer_type_node;
+        }
+        else if (auto reference = type.get<boot::instantiated_type>())
+        {
+            // Erasure is argument blind, so every instantiation of one generic
+            // shares the tree the generic's own name is bound to.
+            return get_inner_alias(reference->generic, symbols, placeholder);
+        }
+        else if (auto reference = type.get<boot::generic_type>())
+        {
+            return get_inner_alias(reference->referent, symbols, placeholder);
+        }
         return error_mark_node;
     }
 
diff --git a/gcc/gcc/elna-generic.cc b/gcc/gcc/elna-generic.cc
index 45d8311..b67e91c 100644
--- a/gcc/gcc/elna-generic.cc
+++ b/gcc/gcc/elna-generic.cc
@@ -875,7 +875,16 @@ namespace elna::gcc
     {
         expression->base().accept(this);
         const location_t expression_location = get_location(&expression->position());
+        tree pointee = get_inner_alias(expression->type_decoration, this->symbols);
 
+        // A field read out of an erased generic record is typed by the erasure,
+        // so the pointer is converted before it is dereferenced, which keeps
+        // the result an lvalue.
+        if (TREE_TYPE(TREE_TYPE(this->current_expression)) != pointee)
+        {
+            this->current_expression = fold_convert_loc(expression_location,
+                    build_pointer_type(pointee), this->current_expression);
+        }
         this->current_expression = build_simple_mem_ref_loc(expression_location,
                 this->current_expression);
     }
diff --git a/include/elna/boot/ast.h b/include/elna/boot/ast.h
index 4919510..f697b44 100644
--- a/include/elna/boot/ast.h
+++ b/include/elna/boot/ast.h
@@ -445,11 +445,20 @@ namespace elna::boot
     public:
         const std::vector<field_declaration> fields;
         const std::optional<identifier> base;
+        /**
+         * Type arguments of a generic base. Empty when the base is plain or
+         * absent.
+         */
+        std::vector<type_expression *> base_arguments;
 
         record_type_expression(const source_position position,
                 std::vector<field_declaration>&& fields);
         record_type_expression(const source_position position,
                 std::vector<field_declaration>&& fields, identifier&& base);
+        record_type_expression(const source_position position,
+                std::vector<field_declaration>&& fields, identifier&& base,
+                std::vector<type_expression *>&& base_arguments);
+        ~record_type_expression() override;
 
         void accept(parser_visitor *visitor) override;
         record_type_expression *is_record() override;
@@ -481,10 +490,19 @@ namespace elna::boot
     public:
         const identifier type_name;
         const std::vector<field_initializer> field_initializers;
+        /**
+         * Type arguments naming the instantiation being constructed. Empty
+         * when no argument list was written.
+         */
+        const std::vector<type_expression *> arguments;
 
         record_constructor_expression(const source_position position,
                 identifier&& type_name,
                 std::vector<field_initializer>&& field_initializers);
+        record_constructor_expression(const source_position position,
+                identifier&& type_name, std::vector<type_expression *>&& arguments,
+                std::vector<field_initializer>&& field_initializers);
+        ~record_constructor_expression() override;
         void accept(parser_visitor *visitor) override;
         record_constructor_expression *is_record_constructor() override;
     };
@@ -609,6 +627,12 @@ namespace elna::boot
     public:
         std::optional<procedure_body> body;
 
+        /**
+         * Type parameters bound by this declaration. Empty for a plain
+         * procedure.
+         */
+        std::vector<elna::boot::identifier> parameters;
+
         procedure_declaration(const source_position position, identifier_definition identifier,
                 procedure_type_expression *heading, procedure_body&& body);
         procedure_declaration(const source_position position, identifier_definition identifier,
@@ -628,6 +652,11 @@ namespace elna::boot
         type_expression *m_underlying_type;
 
     public:
+        /**
+         * Type parameters bound by this declaration. Empty for a plain type.
+         */
+        std::vector<elna::boot::identifier> parameters;
+
         type_declaration(const source_position position, identifier_definition identifier,
                 type_expression *underlying_type);
         ~type_declaration() override;
@@ -752,8 +781,19 @@ namespace elna::boot
     {
     public:
         const std::string name;
+        /**
+         * Type arguments of a generic instantiation. Empty when no argument
+         * list was written, the lists being non-empty where they appear.
+         */
+        std::vector<type_expression *> arguments;
+        /// Resolved form of \c arguments, filled by name analysis.
+        std::vector<type> argument_types;
 
         named_expression(const source_position position, const std::string& name);
+        named_expression(const source_position position, const std::string& name,
+                std::vector<type_expression *>&& arguments);
+        ~named_expression() override;
+
         void accept(parser_visitor *visitor) override;
 
         named_expression *is_named() override;
diff --git a/include/elna/boot/name_analysis.h b/include/elna/boot/name_analysis.h
index 4a22df7..46a3e2d 100644
--- a/include/elna/boot/name_analysis.h
+++ b/include/elna/boot/name_analysis.h
@@ -186,6 +186,12 @@ namespace elna::boot
          * other than a type.
          */
         type resolve_type(type_expression& expression);
+        /*
+         * Opens a scope holding the given type parameters, which the caller
+         * closes once the declaration they belong to is resolved.
+         */
+        std::vector<type> enter_parameters(const std::vector<elna::boot::identifier>& parameters);
+        std::vector<type> resolve_arguments(const std::vector<type_expression *>& arguments);
         type lookup_primitive_type(const std::string& name);
         std::filesystem::path redefinition_file(const std::shared_ptr<info>& original) const;
         std::shared_ptr<variable_info> register_variable(const std::string& name,
diff --git a/include/elna/boot/symbol.h b/include/elna/boot/symbol.h
index 40cbbc6..8646f48 100644
--- a/include/elna/boot/symbol.h
+++ b/include/elna/boot/symbol.h
@@ -42,6 +42,9 @@ namespace elna::boot
     struct procedure_type;
     struct enumeration_type;
     struct extern_type;
+    struct parameter_type;
+    struct generic_type;
+    struct instantiated_type;
 
     /**
      * Represents a type stored in the symbol table.
@@ -62,7 +65,10 @@ namespace elna::boot
             std::shared_ptr<slice_type>,
             std::shared_ptr<procedure_type>,
             std::shared_ptr<enumeration_type>,
-            std::shared_ptr<extern_type>
+            std::shared_ptr<extern_type>,
+            std::shared_ptr<parameter_type>,
+            std::shared_ptr<generic_type>,
+            std::shared_ptr<instantiated_type>
         >;
         Payload payload;
 
@@ -200,6 +206,50 @@ namespace elna::boot
     {
     };
 
+    /**
+     * Type parameter of a generic declaration.
+     *
+     * It denotes an unknown pointer type chosen at instantiation, so it is
+     * usable wherever a pointer is, and erases to a pointer in the backend.
+     * Each declaration gets fresh parameters; two parameters spelled alike in
+     * different declarations never compare equal.
+     */
+    struct parameter_type
+    {
+        const std::string name;
+
+        explicit parameter_type(const std::string& name);
+    };
+
+    /**
+     * Generic declaration.
+     *
+     * Not usable as a type by itself; it carries the parameter names so that a
+     * missing or miscounted argument list can be reported against them.
+     */
+    struct generic_type
+    {
+        /// Parameters of this declaration, each holding a \c parameter_type.
+        const std::vector<type> parameters;
+        type referent;
+
+        explicit generic_type(std::vector<type>&& parameters, type referent = type());
+    };
+
+    /**
+     * Generic applied to type arguments.
+     *
+     * \c generic holds the alias the arguments were applied to, so that two
+     * mentions of the same instantiation share the generic's identity.
+     */
+    struct instantiated_type
+    {
+        const type generic;
+        const std::vector<type> arguments;
+
+        instantiated_type(type generic, std::vector<type>&& arguments);
+    };
+
     class type_info;
     class procedure_info;
     class variable_info;
@@ -378,6 +428,10 @@ namespace elna::boot
         /// Local definitions.
         std::shared_ptr<symbol_table> scope;
 
+        /// Type parameters, each holding a \c parameter_type. Empty for a
+        /// plain procedure.
+        std::vector<type> parameters;
+
         /**
          * Constructs procedure symbol information.
          *
@@ -568,6 +622,66 @@ namespace elna::boot
     type resolve_aliases(const type& checked);
 
     /**
+     * Resolves an alias chain without seeing through instantiations, which
+     * \c resolve_aliases does.
+     *
+     * \param checked The type to resolve.
+     * \return The first non-alias type in the chain.
+     */
+    type unwrap_aliases(const type& checked);
+
+    /**
+     * \param checked A type naming a generic, possibly through aliases.
+     * \return The generic, or \c nullptr if \p checked does not name one.
+     */
+    std::shared_ptr<generic_type> unwrap_generic(const type& checked);
+
+    /**
+     * Replaces type parameters with the arguments standing at their position.
+     *
+     * The substitution is structural and stops at record boundaries, whose
+     * fields are substituted when they are looked up instead.
+     *
+     * \param subject Type to substitute in.
+     * \param parameters Parameters of the generic being substituted.
+     * \param arguments Arguments to replace them with.
+     * \return The substituted type.
+     */
+    type substitute(const type& subject, const std::vector<type>& parameters,
+            const std::vector<type>& arguments);
+
+    /**
+     * Resolves a type to the view layout and codegen see, in which an
+     * instantiation is its generic's referent with the arguments dropped.
+     *
+     * \param checked The type to resolve.
+     * \return The erased type, empty if a generic is unresolved.
+     */
+    type erase_generic(const type& checked);
+
+    /**
+     * \param derived A record type or an instantiation of a generic record.
+     * \return The type it extends, with the arguments of \p derived
+     *         substituted into it. Empty if it extends nothing.
+     */
+    type base_of(const type& derived);
+
+    /**
+     * \param base Candidate base type.
+     * \param derived Candidate derived type.
+     * \return Whether \p base occurs in \p derived's base chain.
+     */
+    bool is_base_of(const type& base, const type& derived);
+
+    /**
+     * Applies an instantiation's arguments to its generic's referent.
+     *
+     * \param instance The instantiation to apply.
+     * \return The substituted referent, empty if the generic is unresolved.
+     */
+    type instantiate(const std::shared_ptr<instantiated_type>& instance);
+
+    /**
      * Checks whether the given type is the built-in type \a name.
      *
      * \param checked The type to check.
diff --git a/include/elna/boot/type_check.h b/include/elna/boot/type_check.h
index 50b9225..e948ada 100644
--- a/include/elna/boot/type_check.h
+++ b/include/elna/boot/type_check.h
@@ -94,6 +94,8 @@ namespace elna::boot
             opaque_element,
             opaque_cast,
             opaque_arithmetic,
+            dereference_of_parameter,
+            parameter_arithmetic,
             zero_sized,
             not_addressable
         };
@@ -119,7 +121,8 @@ namespace elna::boot
         {
             trait,
             call,
-            array
+            array,
+            generic
         };
     private:
         kind m_kind;
@@ -161,6 +164,51 @@ namespace elna::boot
     };
 
     /**
+     * Error applying a generic or declaring its parameters.
+     */
+    class generic_error final : public diagnostic
+    {
+    public:
+        struct not_generic
+        {
+        };
+        struct unused_parameter
+        {
+            std::string parameter;
+        };
+        struct argument_not_pointer
+        {
+            type actual;
+        };
+        struct constant_argument
+        {
+            type actual;
+        };
+        struct uninferrable_parameter
+        {
+            std::string parameter;
+        };
+        struct shape_mismatch
+        {
+            type declared;
+            type actual;
+        };
+
+        using payload_type = std::variant<not_generic, unused_parameter,
+              argument_not_pointer, constant_argument, uninferrable_parameter,
+              shape_mismatch>;
+
+        generic_error(const source_position position, const std::string& generic_name,
+                payload_type payload);
+
+        std::string what() const override;
+
+    private:
+        std::string generic_name;
+        payload_type payload;
+    };
+
+    /**
      * Chain of responsibility for type compatibility checks.
      *
      * Populate \c ctx with pre-resolved types, then call \c run().
@@ -205,6 +253,8 @@ namespace elna::boot
         symbol_bag bag;
         std::shared_ptr<procedure_info> current_procedure;
         const target_info& target;
+        /// Whether the name being visited stands in a call's callable position.
+        bool in_callable_position{ false };
 
         /*
          * Whether an expression of type assignment can be assigned to a variable
@@ -214,6 +264,11 @@ namespace elna::boot
         static bool is_equality_compatible(const type& left, const type& right);
 
         void visit_and_validate_condition(expression& condition);
+        void check_arguments(const named_expression& reference, const std::vector<type>& arguments);
+        void check_parameters_used(const source_position position, const std::string& name,
+                const std::vector<type>& parameters, const type& heading);
+        type infer_call(procedure_call& call, const named_expression& reference,
+                const procedure_info& procedure);
         void check_return(const procedure_body& body, const source_position position,
                 const std::string& name);
 
@@ -240,6 +295,7 @@ namespace elna::boot
         void visit(slicing_expression *expression) override;
         void visit(array_access_expression *expression) override;
         void visit(dereference_expression *expression) override;
+        void visit(named_expression *expression) override;
         void visit(cast_expression *expression) override;
         void visit(unary_expression *expression) override;
         void visit(binary_expression *expression) override;
diff --git a/testsuite/compilable/generic_alias.elna b/testsuite/compilable/generic_alias.elna
new file mode 100644
index 0000000..3b431be
--- /dev/null
+++ b/testsuite/compilable/generic_alias.elna
@@ -0,0 +1,31 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Node#[T] = record
+    next: ^Node#[T];
+    value: T
+  end
+
+  Ref#[T] = ^T
+
+  Boxed#[V] = record
+    inner: ^Node#[V]
+  end
+
+var
+  chain: Node#[^File]
+  aliased: Ref#[^File]
+  raw: ^^File
+  boxed: Boxed#[^File]
+
+program()
+begin
+  chain.next := nil;
+  aliased := raw;
+  raw := aliased;
+  boxed.inner := @chain
+return 0u8
+
+end.
diff --git a/testsuite/compilable/generic_arguments.elna b/testsuite/compilable/generic_arguments.elna
new file mode 100644
index 0000000..6bc5242
--- /dev/null
+++ b/testsuite/compilable/generic_arguments.elna
@@ -0,0 +1,28 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Pair#[K, V] = record
+    key: K;
+    value: V
+  end
+
+var
+  entry: Pair#[^File, ^Word8]
+
+proc allocate#[T](size: Word) -> T extern
+
+proc first#[K, V](entry_ptr: ^Pair#[K, V]) -> K
+begin
+return entry_ptr^.key
+
+program()
+begin
+  entry.key := allocate#[^File](#size(File));
+  assert(#size(Pair#[^File, ^Word8]) = #size(Pointer) * 2u);
+  assert(#offset(Pair#[^File, ^Word8], value) = #size(Pointer));
+  assert(first#[^File, ^Word8](@entry) = entry.key)
+return 0u8
+
+end.
diff --git a/testsuite/compilable/generic_base_chain.elna b/testsuite/compilable/generic_base_chain.elna
new file mode 100644
index 0000000..736042b
--- /dev/null
+++ b/testsuite/compilable/generic_base_chain.elna
@@ -0,0 +1,31 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Map#[K, V] = record
+    key: K;
+    value: V
+  end
+
+  Cache#[K, V] = record(Map#[^Word8, V])
+    newest: K
+  end
+
+var
+  store: Cache#[^Int, ^File]
+  byte_key: ^Word8
+  upcast: ^Map#[^Word8, ^File]
+
+proc put#[K2, V2](target: ^Map#[K2, V2]; key: K2)
+begin
+  target^.key := key
+return
+
+program()
+begin
+  upcast := @store;
+  put(@store, byte_key)
+return 0u8
+
+end.
diff --git a/testsuite/compilable/generic_inference.elna b/testsuite/compilable/generic_inference.elna
new file mode 100644
index 0000000..25faca4
--- /dev/null
+++ b/testsuite/compilable/generic_inference.elna
@@ -0,0 +1,33 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Cell#[T] = record
+    held: T
+  end
+
+var
+  files: Cell#[^File]
+  bytes: Cell#[^Word8]
+  f: File
+  b: Word8
+
+proc store#[T](target: ^Cell#[T]; value: T)
+begin
+  target^.held := value
+return
+
+proc relay#[T](target: ^Cell#[T]; value: T)
+begin
+  store(target, value)
+return
+
+program()
+begin
+  store(@files, @f);
+  relay(@bytes, @b);
+  store(@files, nil)
+return 0u8
+
+end.
diff --git a/testsuite/fail_compilation/generic_arity.elna b/testsuite/fail_compilation/generic_arity.elna
new file mode 100644
index 0000000..bb234af
--- /dev/null
+++ b/testsuite/fail_compilation/generic_arity.elna
@@ -0,0 +1,13 @@
+type
+  Stack#[T] = record
+    items: T
+  end
+
+var
+  broken: Stack (* @Error Too few type arguments for generic 'Stack', expected 1, got 0 *)
+
+program()
+begin
+return 0u8
+
+end.
diff --git a/testsuite/fail_compilation/generic_base_mismatch.elna b/testsuite/fail_compilation/generic_base_mismatch.elna
new file mode 100644
index 0000000..64e0c40
--- /dev/null
+++ b/testsuite/fail_compilation/generic_base_mismatch.elna
@@ -0,0 +1,26 @@
+type
+  File = record
+    fd: Int
+  end
+  Socket = record
+    handle: Int
+  end
+
+  List#[T] = record
+    head: T
+  end
+
+  Queue#[T] = record(List#[T])
+    tail: T
+  end
+
+var
+  jobs: Queue#[^File]
+  wrong: ^List#[^Socket]
+
+program()
+begin
+  wrong := @jobs (* @Error Expected type '\^List#\[\^Socket\]', but got '\^Queue#\[\^File\]' *)
+return 0u8
+
+end.
diff --git a/testsuite/fail_compilation/generic_parameter_arithmetic.elna b/testsuite/fail_compilation/generic_parameter_arithmetic.elna
new file mode 100644
index 0000000..969c5c7
--- /dev/null
+++ b/testsuite/fail_compilation/generic_parameter_arithmetic.elna
@@ -0,0 +1,11 @@
+proc walk#[T](value: T; step: ^T)
+begin
+  step := step + 1;
+  value := value + 1 (* @Error Type parameter 'T' cannot be used in pointer arithmetic *)
+return
+
+program()
+begin
+return 0u8
+
+end.
diff --git a/testsuite/fail_compilation/generic_uninferrable.elna b/testsuite/fail_compilation/generic_uninferrable.elna
new file mode 100644
index 0000000..20d3d25
--- /dev/null
+++ b/testsuite/fail_compilation/generic_uninferrable.elna
@@ -0,0 +1,10 @@
+proc allocate#[R](size: Word) -> R extern
+
+program()
+var
+  got: ^Word8
+begin
+  got := allocate(8u) (* @Error Type parameter 'R' of 'allocate' cannot be inferred *)
+return 0u8
+
+end.
diff --git a/testsuite/runnable/generic_base.elna b/testsuite/runnable/generic_base.elna
new file mode 100644
index 0000000..c36eccf
--- /dev/null
+++ b/testsuite/runnable/generic_base.elna
@@ -0,0 +1,42 @@
+type
+  File = record
+    fd: Int
+  end
+
+  List#[T] = record
+    head: T;
+    count: Word
+  end
+
+  Queue#[T] = record(List#[T])
+    tail: T
+  end
+
+var
+  jobs: Queue#[^File]
+  seen: ^List#[^File]
+  f: File
+
+proc push#[T](target: ^List#[T]; value: T)
+begin
+  target^.head := value;
+  target^.count := target^.count + 1u
+return
+
+proc enqueue#[T](target: ^Queue#[T]; value: T)
+begin
+  push(target, value);
+  target^.tail := value
+return
+
+program()
+begin
+  seen := @jobs;
+  enqueue(@jobs, @f);
+  assert(jobs.count = 1u);
+  assert(jobs.head = @f);
+  assert(jobs.tail = @f);
+  assert(#size(Queue#[^File]) = #size(Pointer) * 3u)
+return 0u8
+
+end.
diff --git a/testsuite/runnable/generic_constructor.elna b/testsuite/runnable/generic_constructor.elna
new file mode 100644
index 0000000..201e1b1
--- /dev/null
+++ b/testsuite/runnable/generic_constructor.elna
@@ -0,0 +1,22 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Stack#[T] = record
+    items: T;
+    top: Word
+  end
+
+var
+  s: Stack#[^File]
+  f: File
+
+program()
+begin
+  s := Stack#[^File]{ top: 1u, items: @f };
+  assert(s.top = 1u);
+  assert(s.items = @f)
+return 0u8
+
+end.
diff --git a/testsuite/runnable/generic_erasure.elna b/testsuite/runnable/generic_erasure.elna
new file mode 100644
index 0000000..eccc1d2
--- /dev/null
+++ b/testsuite/runnable/generic_erasure.elna
@@ -0,0 +1,31 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Cell#[T] = record
+    held: T
+  end
+
+var
+  files: Cell#[^File]
+  bytes: Cell#[^Word8]
+  f: File
+  b: Word8
+
+proc store#[T](target: ^Cell#[T]; value: T)
+begin
+  target^.held := value
+return
+
+program()
+begin
+  f.fd := 7;
+  b := 3u8;
+  store#[^File](@files, @f);
+  store#[^Word8](@bytes, @b);
+  assert(files.held^.fd = 7);
+  assert(bytes.held^ = 3u8)
+return 0u8
+
+end.
diff --git a/testsuite/runnable/generic_record.elna b/testsuite/runnable/generic_record.elna
new file mode 100644
index 0000000..8a334ce
--- /dev/null
+++ b/testsuite/runnable/generic_record.elna
@@ -0,0 +1,29 @@
+type
+  File = record
+    fd: Int
+  end
+
+  Stack#[T] = record
+    items: T;
+    top: Word
+  end
+
+var
+  s: Stack#[^File]
+  f: File
+
+proc push#[T](target: ^Stack#[T]; value: T)
+begin
+  target^.items := value;
+  target^.top := target^.top + 1u
+return
+
+program()
+begin
+  s.top := 0u;
+  push#[^File](@s, @f);
+  assert(s.top = 1u);
+  assert(s.items = @f)
+return 0u8
+
+end.