From 589160805c4bce9e5a59dd8fbf23286361bb0f3a Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Wed, 2 Feb 2022 09:24:30 +0100
Subject: [PATCH] document (all but ast), test script, test output

---
 .gitignore                             |   2 +
 Doxyfile                               |   6 +-
 Makefile                               |   1 +
 compilerunc.bash                       |  28 ------
 rts.c                                  |   7 +-
 rts.h                                  |  14 +--
 src/array.h                            |  11 ++-
 src/ast.c                              |   1 -
 src/gen.h                              |   4 +-
 src/gen/c.c                            |  51 +++++++----
 src/gen/c.h                            |   7 ++
 src/gen/ssm.h                          |   7 ++
 src/ident.h                            |   2 +-
 src/list.c                             |  51 -----------
 src/list.h                             |  18 ----
 src/parse.y                            |   1 -
 src/sem.h                              |  15 ++++
 src/sem/constant.h                     |   5 ++
 src/sem/hm.h                           |  39 ++++++++-
 src/sem/hm/gamma.h                     |  77 ++++++++++++++++-
 src/sem/hm/scheme.h                    |  48 ++++++++++-
 src/sem/hm/subst.h                     |  66 ++++++++++++++-
 src/sem/main.h                         |   5 ++
 src/sem/return.h                       |   5 ++
 src/sem/scc.c                          |   9 +-
 src/sem/scc.h                          |   5 ++
 src/sem/type.c                         |   1 -
 src/sem/type.h                         |   5 ++
 src/sem/vardecl.h                      |   5 ++
 src/type.c                             |   4 +-
 src/type.h                             | 113 ++++++++++++++++++++++---
 src/util.h                             |  66 +++++++++++++--
 test.bash                              |   2 +-
 tests/2D.expected                      |   1 +
 tests/2D.spl                           |   1 +
 tests/3D.expected                      |   1 +
 tests/3D.spl                           |   5 ++
 tests/a_bit_of_everything.expected     |   0
 tests/arguments.expected               |   0
 tests/arguments.shouldfail             |   0
 tests/assignment_to_builtin.expected   |   0
 tests/assignment_to_builtin.shouldfail |   0
 tests/assignment_to_builtin.spl        |   6 ++
 43 files changed, 525 insertions(+), 170 deletions(-)
 delete mode 100755 compilerunc.bash
 delete mode 100644 src/list.c
 delete mode 100644 src/list.h
 create mode 100644 tests/2D.expected
 create mode 100644 tests/3D.expected
 create mode 100644 tests/a_bit_of_everything.expected
 create mode 100644 tests/arguments.expected
 create mode 100644 tests/arguments.shouldfail
 create mode 100644 tests/assignment_to_builtin.expected
 create mode 100644 tests/assignment_to_builtin.shouldfail

diff --git a/.gitignore b/.gitignore
index f9d23a1..827f8bf 100644
--- a/.gitignore
+++ b/.gitignore
@@ -14,3 +14,5 @@ tests/*.c
 
 callgrind.out.*
 massif.out.*
+
+doc
diff --git a/Doxyfile b/Doxyfile
index e5b9be5..2b8c0aa 100644
--- a/Doxyfile
+++ b/Doxyfile
@@ -836,7 +836,7 @@ WARN_NO_PARAMDOC       = NO
 # Possible values are: NO, YES and FAIL_ON_WARNINGS.
 # The default value is: NO.
 
-WARN_AS_ERROR          = NO
+WARN_AS_ERROR          = YES
 
 # The WARN_FORMAT tag determines the format of the warning messages that doxygen
 # can produce. The string should contain the $file, $line, and $text tags, which
@@ -943,7 +943,7 @@ FILE_PATTERNS          = *.c \
 # be searched for input files as well.
 # The default value is: NO.
 
-RECURSIVE              = NO
+RECURSIVE              = YES
 
 # The EXCLUDE tag can be used to specify files and/or directories that should be
 # excluded from the INPUT source files. This way you can easily exclude a
@@ -968,7 +968,7 @@ EXCLUDE_SYMLINKS       = NO
 # Note that the wildcards are matched against the file with absolute path, so to
 # exclude all test directories for example use the pattern */test/*
 
-EXCLUDE_PATTERNS       =
+EXCLUDE_PATTERNS       = */scan.h/* */parse.h/*
 
 # The EXCLUDE_SYMBOLS tag can be used to specify one or more symbol names
 # (namespaces, classes, functions, etc.) that should be excluded from the
diff --git a/Makefile b/Makefile
index cc4661b..adc8f9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3,3 +3,4 @@ all:
 
 clean:
 	$(MAKE) -C src clean
+	$(RM) a.c a.ssm a.out
diff --git a/compilerunc.bash b/compilerunc.bash
deleted file mode 100755
index df4e01e..0000000
--- a/compilerunc.bash
+++ /dev/null
@@ -1,28 +0,0 @@
-#!/bin/bash
-usage() {
-	echo "Usage: $0 CSOURCE [-o OFILE]" >&2
-	exit 1
-}
-if [ $# -lt 1 ]
-then
-	usage
-fi
-if [ $# -eq 3 ]
-then
-	if [ $2 != "-o" ]
-	then
-		usage
-	fi
-	OFILE=$3
-else
-	OFILE=a.out
-fi
-make
-./splc < "$1"
-CFLAGS=${CFLAGS:-}
-LDLIBS=${LDLIBS:-}
-LDFLAGS=${LDFLAGS:-}
-CC=${CC:-gcc}
-set -xe
-"$CC" $CFLAGS a.c $LDFLAGS rts.c $LDLIBS -o "$OFILE"
-./"$OFILE"
diff --git a/rts.c b/rts.c
index 0d5e5cb..8a1093a 100644
--- a/rts.c
+++ b/rts.c
@@ -18,7 +18,7 @@ void splc_free(void *ptr)
 //	if (REFC(ptr) == 0)
 //		free(ptr-1);
 }
-struct splc_tuple *splc_tuple(WORD fst, WORD snd) {
+struct splc_tuple *splc_tuple_real(WORD fst, WORD snd) {
 	struct splc_tuple *res = splc_malloc(sizeof(struct splc_tuple));
 	res->fst = fst;
 	res->snd = snd;
@@ -43,3 +43,8 @@ WORD hd(struct splc_list *l)
 	}
 	return l->hd;
 }
+int main()
+{
+	realmain();
+	return 0;
+}
diff --git a/rts.h b/rts.h
index 32ddb99..d1f2d11 100644
--- a/rts.h
+++ b/rts.h
@@ -11,20 +11,24 @@
 
 struct splc_tuple { WORD fst; WORD snd; };
 struct splc_list { WORD hd; struct splc_list *tl; };
-struct splc_tuple *splc_tuple(WORD fst, WORD snd);
+#define splc_tuple(l, r) splc_tuple_real((intptr_t)(l), (intptr_t)(r))
+struct splc_tuple *splc_tuple_real(WORD fst, WORD snd);
 struct splc_list *splc_cons(WORD hd, struct splc_list *tl);
 WORD hd(struct splc_list *l);
 struct splc_list *tl(struct splc_list *l);
 #define die(...) { fprintf(stderr, __VA_ARGS__); exit(1); }
 #define isEmpty(l) ((l) == NULL)
 #define tl(l) (l)->tl
-#define fst(l) (l)->fst
-#define snd(l) (l)->snd
-#define print_Int(l) printf("%ld", l);
-#define print_Char(l) printf("%c", l);
+#define fst(l) ((struct splc_tuple *)(l))->fst
+#define snd(l) ((struct splc_tuple *)(l))->snd
+#define print_Int(l) printf("%ld", (long)l);
+#define print_Char(l) printf("%c", (char)l);
 #define print_Bool(l) printf("%s", (l) ? "true" : "false");
 #define eq_Int(x, y) ((x)==(y))
 #define eq_Char(x, y) ((x)==(y))
 #define eq_Bool(x, y) ((x)==(y))
 
+void realmain(void);
+int main(void);
+
 #endif
diff --git a/src/array.h b/src/array.h
index 37a5878..5793645 100644
--- a/src/array.h
+++ b/src/array.h
@@ -32,9 +32,8 @@
  * @param iter Name of the iterator variable
  * @param array Pointer to the array
  */
-/** Iterate over the indices and elements of an array */
-#define ARRAY_ITER(type, x, iter, a) ARRAY_ITERI (iter, a) {\
-		type (x) = ARRAY_EL(type, a, iter);
+#define ARRAY_ITER(type, x, iter, array) ARRAY_ITERI (iter, array) {\
+		type (x) = ARRAY_EL(type, array, iter);
 /**
  * Macro to end an array iteration
  *
@@ -146,7 +145,7 @@ void array_insert(struct array *array, size_t idx, void *x);
  * @param array Pointer to the array
  * @param idx Index of removal
  */
-void array_remove(struct array *a, size_t idx);
+void array_remove(struct array *array, size_t idx);
 
 /**
  * Move an item from a position to another, moving the other items.
@@ -155,7 +154,7 @@ void array_remove(struct array *a, size_t idx);
  * @param from Original index of the item
  * @param to New index of the item
  */
-void array_move(struct array *a, size_t from, size_t to);
+void array_move(struct array *array, size_t from, size_t to);
 
 /**
  * Insert an item into a sorted array.
@@ -164,6 +163,6 @@ void array_move(struct array *a, size_t from, size_t to);
  * @param array Pointer to the array
  * @param cmp Comparison function
  */
-void array_binsert(void *key, struct array *a, int (*cmp)(const void *, const void *));
+void array_binsert(void *key, struct array *array, int (*cmp)(const void *, const void *));
 
 #endif
diff --git a/src/ast.c b/src/ast.c
index 5ae01f2..dca36d4 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -6,7 +6,6 @@
 #include "util.h"
 #include "ast.h"
 #include "type.h"
-#include "list.h"
 #include "parse.h"
 
 const char *binop_str[] = {
diff --git a/src/gen.h b/src/gen.h
index ef13f19..dc9c723 100644
--- a/src/gen.h
+++ b/src/gen.h
@@ -7,8 +7,8 @@
 
 /** Datatype that stores the overloading information */
 struct overload {
-	struct array print; /** overloaded print calls, @type struct overload_entry * */
-	struct array eq;    /** overloaded equality calls, @type struct overload_entry * */
+	struct array print; /** overloaded print calls, type: struct overload_entry * */
+	struct array eq;    /** overloaded equality calls, type: struct overload_entry * */
 };
 /** Single overloading entry */
 struct overload_entry {
diff --git a/src/gen/c.c b/src/gen/c.c
index a366bd1..0e0340b 100644
--- a/src/gen/c.c
+++ b/src/gen/c.c
@@ -6,6 +6,13 @@
 #include "../sem.h"
 #include "../gen.h"
 
+static const char *fun_name(const char *name)
+{
+	if (strcmp(name, "abs") == 0)
+		return "splc_abs";
+	return name;
+}
+
 static void expr_genc(struct expr *expr, FILE *cout);
 
 static void binop_genc(char *fun, struct expr *l, struct expr *r, FILE *cout)
@@ -60,7 +67,7 @@ static void expr_genc(struct expr *expr, FILE *cout)
 			safe_fprintf(cout, "print_");
 			overloaded_type(expr->loc, expr->data.efuncall.type, cout);
 		} else {
-			safe_fprintf(cout, "%s", expr->data.efuncall.ident);
+			safe_fprintf(cout, "%s", fun_name(expr->data.efuncall.ident));
 		}
 		safe_fprintf(cout, "(");
 		ARRAY_ITER(struct expr *, e, i, &expr->data.efuncall.args) {
@@ -142,6 +149,14 @@ static void vardecl_genc(struct vardecl *vardecl, int indent, FILE *cout)
 	safe_fprintf(cout, ";\n");
 }
 
+static void fields_genc(struct array *fields, const char *ident, FILE *cout)
+{
+	safe_fprintf(cout, "%s", ident);
+	ARRAY_ITER(char *, f, i, fields)
+	                safe_fprintf(cout, "->%s", f);
+	AIEND
+}
+
 static void stmt_genc(struct stmt *stmt, int indent, FILE *cout)
 {
 	if (stmt == NULL)
@@ -149,10 +164,7 @@ static void stmt_genc(struct stmt *stmt, int indent, FILE *cout)
 	switch(stmt->type) {
 	case sassign:
 		pindent(indent, cout);
-		safe_fprintf(cout, "%s", stmt->data.sassign.ident);
-		ARRAY_ITER(char *, f, i, &stmt->data.sassign.fields)
-			safe_fprintf(cout, "->%s", f);
-		AIEND
+		fields_genc(&stmt->data.sassign.fields, stmt->data.sassign.ident, cout);
 		safe_fprintf(cout, " = ");
 		expr_genc(stmt->data.sassign.expr, cout);
 		safe_fprintf(cout, ";\n");
@@ -210,7 +222,7 @@ static void stmt_genc(struct stmt *stmt, int indent, FILE *cout)
 static void fundecl_sig(struct fundecl *decl, FILE *cout)
 {
 	type_genc(decl->rtype, cout);
-	safe_fprintf(cout, "%s (", decl->ident);
+	safe_fprintf(cout, "%s (", fun_name(decl->ident));
 	ARRAY_ITER(char *, a, i, &decl->args) {
 		if (i >= ARRAY_SIZE(decl->atypes))
 			die("function with unmatched type\n");
@@ -239,7 +251,7 @@ static void initialise_non_constant_globals(const struct ast *ast, FILE *cout)
 static void fundecl_genc(const struct ast *ast, struct fundecl *decl, FILE *cout)
 {
 	if (strcmp(decl->ident, "main") == 0)
-		safe_fprintf(cout, "int main()");
+		safe_fprintf(cout, "void real_main()");
 	else
 		fundecl_sig(decl, cout);
 	safe_fprintf(cout, "{\n");
@@ -248,12 +260,9 @@ static void fundecl_genc(const struct ast *ast, struct fundecl *decl, FILE *cout
 	ARRAY_ITER(struct stmt *, s, i, &decl->body)
 		stmt_genc(s, 1, cout);
 	AIEND
-	if (strcmp(decl->ident, "main") == 0)
-		safe_fprintf(cout, "\treturn 0;\n");
 	safe_fprintf(cout, "}\n");
 }
 
-
 static void decl_genc(const struct ast *ast, struct decl *decl, FILE *cout)
 {
 	switch (decl->type) {
@@ -295,9 +304,9 @@ static void generate_eq(struct type *type, FILE *cout)
 		safe_fprintf(cout, "\twhile(t != NULL) {\n");
 		safe_fprintf(cout, "\t\tif (!eq_");
 		overloaded_type(loc, type->data.tlist, cout);
-		safe_fprintf(cout, "(x->hd, y->hd));\n");
+		safe_fprintf(cout, "(hd(x), hd(y)));\n");
 		safe_fprintf(cout, "\t\t\treturn false;\n");
-		safe_fprintf(cout, "\t\tt = t->tl;\n");
+		safe_fprintf(cout, "\t\tt = tl(t);\n");
 		safe_fprintf(cout, "\t}\n");
 		safe_fprintf(cout, "\treturn true;\n");
 		break;
@@ -307,7 +316,7 @@ static void generate_eq(struct type *type, FILE *cout)
 		safe_fprintf(cout, "(x->fy->fst)");
 		safe_fprintf(cout, " && eq_");
 		overloaded_type(loc, type->data.ttuple.r, cout);
-		safe_fprintf(cout, "(x->snd, y->snd);");
+		safe_fprintf(cout, "(snd(x), snd(y));");
 		break;
 	default:
 		die("cannot compare anything else than tuples and lists");
@@ -332,10 +341,12 @@ static void generate_print(struct type *type, FILE *cout)
 		safe_fprintf(cout, "\twhile(t != NULL) {\n");
 		safe_fprintf(cout, "\t\tprint_");
 		overloaded_type(loc, type->data.tlist, cout);
-		safe_fprintf(cout, "(t->hd);\n");
-		safe_fprintf(cout, "\t\tif (t->tl != NULL)\n");
+		safe_fprintf(cout, "((");
+		type_genc(type->data.tlist, cout);
+		safe_fprintf(cout, ")hd(t));\n");
+		safe_fprintf(cout, "\t\tif (tl(t) != NULL)\n");
 		safe_fprintf(cout, "\t\t\tprintf(\", \");\n");
-		safe_fprintf(cout, "\t\tt = t->tl;\n");
+		safe_fprintf(cout, "\t\tt = tl(t);\n");
 		safe_fprintf(cout, "\t}\n");
 		safe_fprintf(cout, "\tprintf(\"]\");\n");
 		break;
@@ -343,11 +354,15 @@ static void generate_print(struct type *type, FILE *cout)
 		safe_fprintf(cout, "\tprintf(\"(\");\n");
 		safe_fprintf(cout, "\tprint_");
 		overloaded_type(loc, type->data.ttuple.l, cout);
-		safe_fprintf(cout, "(t->fst);\n");
+		safe_fprintf(cout, "((");
+		type_genc(type->data.ttuple.l, cout);
+		safe_fprintf(cout, ")fst(t));\n");
 		safe_fprintf(cout, "\tprintf(\",\");\n");
 		safe_fprintf(cout, "\tprint_");
 		overloaded_type(loc, type->data.ttuple.r, cout);
-		safe_fprintf(cout, "(t->snd);\n");
+		safe_fprintf(cout, "((");
+		type_genc(type->data.ttuple.r, cout);
+		safe_fprintf(cout, ")snd(t));\n");
 		safe_fprintf(cout, "\tprintf(\")\");\n");
 		break;
 	default:
diff --git a/src/gen/c.h b/src/gen/c.h
index 7b400b2..167c3ae 100644
--- a/src/gen/c.h
+++ b/src/gen/c.h
@@ -6,6 +6,13 @@
 #include "../ast.h"
 #include "../gen.h"
 
+/**
+ * Generate C code for the abstract syntax tree
+ *
+ * @param res abstract syntax tree
+ * @param ol dictionary of overloaded function calls
+ * @param cout stream to output the result to
+ */
 void genc(const struct ast *res, const struct overload ol, FILE *cout);
 
 #endif
diff --git a/src/gen/ssm.h b/src/gen/ssm.h
index 64ae852..70bbd16 100644
--- a/src/gen/ssm.h
+++ b/src/gen/ssm.h
@@ -6,6 +6,13 @@
 #include "../ast.h"
 #include "../gen.h"
 
+/**
+ * Generate SSM code for the abstract syntax tree
+ *
+ * @param res abstract syntax tree
+ * @param ol dictionary of overloaded function calls
+ * @param cout stream to output the result to
+ */
 void genssm(const struct ast *res, const struct overload ol, FILE *cout);
 
 #endif
diff --git a/src/ident.h b/src/ident.h
index d334003..7ecb6ec 100644
--- a/src/ident.h
+++ b/src/ident.h
@@ -48,7 +48,7 @@ struct ident ident_dup(struct ident i);
  * Print an identifier
  *
  * @param i identifier
- * @param stream to print to
+ * @param cout to print to
  */
 void ident_print(struct ident i, FILE *cout);
 /**
diff --git a/src/list.c b/src/list.c
deleted file mode 100644
index d58ad78..0000000
--- a/src/list.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <stdlib.h>
-#include <stdbool.h>
-
-#include "list.h"
-#include "util.h"
-
-struct list *list_cons(void *el, struct list *tail)
-{
-	struct list *res = xalloc(1, struct list);
-	res->el = el;
-	res->tail = tail;
-	return res;
-}
-
-void list_free(struct list *head, void (*freefun)(void *))
-{
-	while (head != NULL) {
-		struct list *t = head;
-		if (freefun != NULL)
-			freefun(head->el);
-		head = head->tail;
-		free(t);
-	}
-}
-
-void **list_to_array(struct list *list, int *num, bool reverse, int extra)
-{
-	int i = list_length(list);
-	*num = i;
-	void **ptr = xalloc(i+extra, void *);
-
-	struct list *r = list;
-	while(i > 0) {
-		if (reverse)
-			ptr[--i] = r->el;
-		else
-			ptr[*num-(--i)-1] = r->el;
-		struct list *t = r;
-		r = r->tail;
-		free(t);
-	}
-	return ptr;
-}
-
-int list_length(struct list *r)
-{
-	int i = 0;
-	FOREACH(e, r)
-		i++;
-	return i;
-}
diff --git a/src/list.h b/src/list.h
deleted file mode 100644
index 6e87129..0000000
--- a/src/list.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#ifndef LIST_H
-#define LIST_H
-
-#include <stdbool.h>
-
-#define FOREACH(x, l) for(struct list *x = l; x != NULL; x = x->tail)
-
-struct list {
-	void *el;
-	struct list *tail;
-};
-
-struct list *list_cons(void *el, struct list *tail);
-void list_free(struct list *head, void (*freefun)(void *));
-void **list_to_array(struct list *list, int *num, bool reverse, int extra);
-int list_length(struct list *head);
-
-#endif
diff --git a/src/parse.y b/src/parse.y
index 8008a0e..7e29cde 100644
--- a/src/parse.y
+++ b/src/parse.y
@@ -3,7 +3,6 @@
 
 #include "array.h"
 #include "ast.h"
-#include "list.h"
 #include "parse.h"
 
 int yylex(void);
diff --git a/src/sem.h b/src/sem.h
index 3c1a929..9bc7895 100644
--- a/src/sem.h
+++ b/src/sem.h
@@ -5,7 +5,22 @@
 
 #include "ast.h"
 
+/**
+ * Emit a type error
+ *
+ * @param l location
+ * @param d also exit with error code 1
+ * @param msg format string
+ * @param ... format arguments
+ */
 void type_error(YYLTYPE l, bool d, const char *msg, ...);
+
+/**
+ * Perform all semantical analyses.
+ *
+ * @param ast pointer to the unchecked abstract syntax tree
+ * @result pointer to the checked abstract syntax tree
+ */
 struct ast *sem(struct ast *ast);
 
 #endif
diff --git a/src/sem/constant.h b/src/sem/constant.h
index bdaf5b5..ed11d0e 100644
--- a/src/sem/constant.h
+++ b/src/sem/constant.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Check that all global variable initialisers are constant
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_constant(struct ast *ast);
 
 #endif
diff --git a/src/sem/hm.h b/src/sem/hm.h
index eab8cb9..fe7bedd 100644
--- a/src/sem/hm.h
+++ b/src/sem/hm.h
@@ -7,11 +7,48 @@
 #include "hm/scheme.h"
 #include "../ident.h"
 
+/**
+ * Infer all types in the AST
+ *
+ * @param ast abstract syntax tree
+ * @result abstract syntax tree with all types inferred
+ */
 struct ast *infer(struct ast *ast);
 
+/**
+ * Unify a type
+ *
+ * @param loc location of the type to localise possible errors
+ * @param l left-hand side
+ * @param r right-hand side
+ */
 struct subst *unify(YYLTYPE loc, struct type *l, struct type *r);
+/**
+ * Infer an expression
+ *
+ * @param gamma environment
+ * @param expr expression to infer
+ * @param type σ, the type to infer to
+ * @result substitution
+ */
 struct subst *infer_expr(struct gamma *gamma, struct expr *expr, struct type *type);
+/**
+ * Infer a statement
+ *
+ * @param gamma environment
+ * @param stmt statement to infer
+ * @param type σ, the type to infer to
+ * @result substitution
+ */
 struct subst *infer_stmt(struct gamma *gamma, struct stmt *stmt, struct type *type);
-struct subst *infer_fundecl(struct gamma *gamma, struct fundecl *fundecl, struct type *ftype);
+/**
+ * Infer a function declaration
+ *
+ * @param gamma environment
+ * @param fundecl function declaration to infer
+ * @param type σ, the type to infer to
+ * @result substitution
+ */
+struct subst *infer_fundecl(struct gamma *gamma, struct fundecl *fundecl, struct type *type);
 
 #endif
diff --git a/src/sem/hm/gamma.h b/src/sem/hm/gamma.h
index c477771..08424a2 100644
--- a/src/sem/hm/gamma.h
+++ b/src/sem/hm/gamma.h
@@ -7,21 +7,94 @@
 #include "../hm.h"
 #include "../../ident.h"
 
+/** abstract type representing the environment */
 struct gamma;
+/** abstract type representing an entry in the environment */
 struct gamma_entry;
 
+/**
+ * Initialise an empty environment
+ *
+ * @result environment
+ */
 struct gamma *gamma_init();
+/**
+ * Insert an entry in the environment.
+ *
+ * @param gamma environment
+ * @param ident identifier
+ * @param scheme type scheme
+ */
 void gamma_insert(struct gamma *gamma, struct ident ident, struct scheme *scheme);
+/**
+ * Increment the internal scope of gamma, used to separate namespaces and
+ * scopes.
+ *
+ * @param gamma environment
+ */
 void gamma_increment_scope(struct gamma *gamma);
+/**
+ * Decrement the internal scope of gamma, used to separate namespaces and
+ * scopes.
+ *
+ * @param gamma environment
+ */
 void gamma_decrement_scope(struct gamma *gamma);
 
-void gamma_iter(struct gamma *gamma, void *st, void (*iter)(struct ident, struct scheme *, void *));
+/**
+ * Function to call for each entry while iterating over gamma.
+ *
+ * @param i type variable
+ * @param s type scheme
+ * @param st user state
+ */
+typedef void (*gamma_iterfun)(struct ident i, struct scheme *s, void *st);
 
+/**
+ * Iterate over all entries in gamma.
+ *
+ * @param gamma environment
+ * @param st pointer to the initial state
+ * @param iter pointer to the iteration function
+ */
+void gamma_iter(struct gamma *gamma, void *st, gamma_iterfun iter);
+
+/**
+ * Lookup an identifier in the environment
+ *
+ * @param gamma environment
+ * @param ident identifier
+ * @result pointer to the type scheme, NULL if not found
+ */
 struct scheme *gamma_lookup(struct gamma *gamma, struct ident ident);
+
+/**
+ * Check whether \p ident is free in gamma.
+ *
+ * @param gamma environment
+ * @param ident identifier
+ * @result result
+ */
 bool gamma_free_in(struct gamma *gamma, struct ident ident);
+/**
+ * Generate a fresh type variable.
+ *
+ * @param gamma environment
+ * @result fresh type variable
+ */
 struct type *gamma_fresh(struct gamma *gamma);
-
+/**
+ * Print the entire enviroment
+ *
+ * @param gamma environment
+ * @param out output stream
+ */
 void gamma_print(struct gamma *gamma, FILE *out);
+/**
+ * Recursively free the enviroment
+ *
+ * @param gamma environment
+ */
 void gamma_free(struct gamma *gamma);
 
 #endif
diff --git a/src/sem/hm/scheme.h b/src/sem/hm/scheme.h
index b194e00..57dc0d7 100644
--- a/src/sem/hm/scheme.h
+++ b/src/sem/hm/scheme.h
@@ -7,18 +7,58 @@ struct gamma;
 #include "../hm.h"
 #include "../../ident.h"
 
+/** Definition of a type scheme */
 struct scheme {
-	struct type *type;
-	int nvar;
-	struct ident *var;
+	struct type *type; /** Type */
+	int nvar;          /** Number of quantified type variables */
+	struct ident *var; /** array of quantified type variables */
 };
 
+/**
+ * Instantiate a type scheme, i.e. replace the quantified type variables by
+ * fresh type variables.
+ *
+ * @param gamma environment
+ * @param s scheme
+ * @result type
+ */
 struct type *scheme_instantiate(struct gamma *gamma, struct scheme *s);
+/**
+ * Create a scheme from a type and assume no type variable is quantified.
+ *
+ * @param t type
+ * @result scheme
+ */
 struct scheme *scheme_create(struct type *t);
+/**
+ * Create a scheme by generalising a type, i.e. quantify all free type variables
+ * that are not free in gamma.
+ *
+ * @param gamma environment
+ * @param t type
+ * @result scheme
+ */
 struct scheme *scheme_generalise(struct gamma *gamma, struct type *t);
+/**
+ * Check whether \p ident is free in the type scheme.
+ *
+ * @param scheme type scheme
+ * @param ident type variable
+ * @result result
+ */
 bool scheme_free_in(struct scheme *scheme, struct ident ident);
-
+/**
+ * Print a type scheme.
+ *
+ * @param scheme type scheme
+ * @param out output stream
+ */
 void scheme_print(struct scheme *scheme, FILE *out);
+/**
+ * Free a type scheme.
+ *
+ * @param scheme type scheme
+ */
 void scheme_free(struct scheme *scheme);
 
 #endif
diff --git a/src/sem/hm/subst.h b/src/sem/hm/subst.h
index 11d7c98..101dbff 100644
--- a/src/sem/hm/subst.h
+++ b/src/sem/hm/subst.h
@@ -5,18 +5,78 @@
 #include "../hm.h"
 #include "../../ident.h"
 
+/** Abstract type representing a substitution, a map from type variable to type */
 struct subst;
 
+/**
+ * The identity substitution
+ *
+ * @result the empty substitution
+ */
 struct subst *subst_id();
+/**
+ * Extend a substitution.
+ *
+ * @param s substitution to extend
+ * @param ident type variable
+ * @param t substitute type
+ * @result the extended substitution
+ */
 struct subst *subst_insert(struct subst *s, struct ident ident, struct type *t);
+/**
+ * Create a singleton substitution.
+ * i.e. substs_singleton(i, t) == subst_insert(subst_id(), i, t)
+ *
+ * @param ident type variable
+ * @param t substitute type
+ * @result substitution
+ */
 struct subst *subst_singleton(struct ident ident, struct type *t);
+/**
+ * Take the union of two substitutions. This is destructive, \p l is freed, \p r is
+ * extended with the substitutions from \p l.
+ *
+ * @param l left-hand side substitution
+ * @param r right-hand side substitution
+ * @result union substitution (
+ */
 struct subst *subst_union(struct subst *l, struct subst *r);
-
-struct type *subst_apply_t(struct subst *subst, struct type *l);
+/**
+ * Apply a substitution to a type.
+ *
+ * @param subst substitution
+ * @param t type
+ * @result type
+ */
+struct type *subst_apply_t(struct subst *subst, struct type *t);
+/**
+ * Apply a substitution to a type scheme
+ *
+ * @param subst substitution
+ * @param scheme type scheme
+ * @result type scheme
+ */
 struct scheme *subst_apply_s(struct subst *subst, struct scheme *scheme);
+/**
+ * Apply a substitution to an environment
+ *
+ * @param subst substitution
+ * @param gamma environment
+ * @result environment
+ */
 struct gamma *subst_apply_g(struct subst *subst, struct gamma *gamma);
-
+/**
+ * Print a substitution.
+ *
+ * @param s substitution
+ * @param out output stream
+ */
 void subst_print(struct subst *s, FILE *out);
+/**
+ * Free a substitution.
+ *
+ * @param s substitution
+ */
 void subst_free(struct subst *s);
 
 #endif
diff --git a/src/sem/main.h b/src/sem/main.h
index 63a6cc0..6bfa61f 100644
--- a/src/sem/main.h
+++ b/src/sem/main.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Check that there is a main function and that it has the correct type.
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_main(struct ast *ast);
 
 #endif
diff --git a/src/sem/return.h b/src/sem/return.h
index 7ccc0b9..1e8291e 100644
--- a/src/sem/return.h
+++ b/src/sem/return.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Check that all functions return that have a non-void return type
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_return(struct ast *ast);
 
 #endif
diff --git a/src/sem/scc.c b/src/sem/scc.c
index 93327a9..cffc7e0 100644
--- a/src/sem/scc.c
+++ b/src/sem/scc.c
@@ -107,10 +107,11 @@ static int ptrcmp(const void *l, const void *r)
  *
  * Returns NULL when there are invalid edges
  *
- * @param number of nodes
- * @param data of the nodes
- * @param number of edges
- * @param data of edges
+ * @param nnodes number of nodes
+ * @param nodedata data of the nodes
+ * @param nedges number of edges
+ * @param edgedata data of edges
+ * @result list of components
  */
 struct components *tarjans(
 		int nnodes, void *nodedata[],
diff --git a/src/sem/scc.h b/src/sem/scc.h
index e948435..89b21e3 100644
--- a/src/sem/scc.h
+++ b/src/sem/scc.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Group mutually recursive functions in components.
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_scc(struct ast *ast);
 
 #endif
diff --git a/src/sem/type.c b/src/sem/type.c
index a69d3be..ead0b40 100644
--- a/src/sem/type.c
+++ b/src/sem/type.c
@@ -206,6 +206,5 @@ void sem_check_types(struct ast *ast)
 			break;
 		}
 	}
-	gamma_print(gamma, stdout);
 	gamma_free(gamma);
 }
diff --git a/src/sem/type.h b/src/sem/type.h
index 352cbb5..645a294 100644
--- a/src/sem/type.h
+++ b/src/sem/type.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Infer and check the intire AST
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_types(struct ast *ast);
 
 #endif
diff --git a/src/sem/vardecl.h b/src/sem/vardecl.h
index 8f72e2c..224045a 100644
--- a/src/sem/vardecl.h
+++ b/src/sem/vardecl.h
@@ -3,6 +3,11 @@
 
 #include "../ast.h"
 
+/**
+ * Check that vardecls aren't mutually recursive and order them
+ *
+ * @param ast abstract syntax tree
+ */
 void sem_check_vardecls(struct ast *ast);
 
 #endif
diff --git a/src/type.c b/src/type.c
index 5a61d4a..4519b80 100644
--- a/src/type.c
+++ b/src/type.c
@@ -229,7 +229,7 @@ int type_cmp(struct type *l, struct type *r)
 	int res = 0;
 	switch(l->type) {
 	case tarrow:
-		if ((res = type_cmp(l->data.tarrow.l, r->data.tarrow.l)) != 0)
+		if ((res = type_cmp(l->data.tarrow.l, r->data.tarrow.l)) == 0)
 			res = type_cmp(l->data.tarrow.r, r->data.tarrow.r);
 		break;
 	case tbasic:
@@ -239,7 +239,7 @@ int type_cmp(struct type *l, struct type *r)
 		res = type_cmp(l->data.tlist, r->data.tlist);
 		break;
 	case ttuple:
-		if ((res = type_cmp(l->data.ttuple.l, r->data.ttuple.l)) != 0)
+		if ((res = type_cmp(l->data.ttuple.l, r->data.ttuple.l)) == 0)
 			res = type_cmp(l->data.ttuple.r, r->data.ttuple.r);
 		break;
 	case tvar:
diff --git a/src/type.h b/src/type.h
index 467696b..35a0d12 100644
--- a/src/type.h
+++ b/src/type.h
@@ -5,40 +5,133 @@
 #include "ast.h"
 #include "ident.h"
 
+/**
+ * Export the string representations of the basic types enumeration
+ *
+ * @see basictype
+ */
 extern const char *basictype_str[];
+/** The basic types */
 enum basictype {btbool, btchar, btint, btvoid};
+/** Representation of a type */
 struct type {
-	enum {tarrow,tbasic,tlist,ttuple,tvar} type;
+	enum {tarrow,tbasic,tlist,ttuple,tvar} type; /** tag of the tagged union */
 	union {
 		struct {
-			struct type *l;
-			struct type *r;
-		} tarrow;
-		enum basictype tbasic;
-		struct type *tlist;
+			struct type *l; /** rhs of the arrow */
+			struct type *r; /** rhs of the arrow */
+		} tarrow;               /** Arrow type: (l -> r) */
+		enum basictype tbasic;  /** Basic type */
+		struct type *tlist;     /** List type: [t] */
 		struct {
-			struct type *l;
-			struct type *r;
-		} ttuple;
-		struct ident tvar;
+			struct type *l; /** rhs of the tuple */
+			struct type *r; /** rhs of the tuple */
+		} ttuple;               /** Tuple type: (l, r) */
+		struct ident tvar;      /** Type variable */
 	} data;
 };
 
+/**
+ * Constructor for the arrow type
+ *
+ * @param left left-hand side
+ * @param right right-hand side
+ * @result arrow type
+ */
 struct type *type_arrow(struct type *left, struct type *right);
+/**
+ * Constructor for a basic type
+ *
+ * @param type tag of the basic type
+ * @result basic type
+ */
 struct type *type_basic(enum basictype type);
+/**
+ * Constructor for a list type
+ *
+ * @param type type of the elements
+ * @result list type
+ */
 struct type *type_list(struct type *type);
+/**
+ * Constructor for the tuple type
+ *
+ * @param left left-hand side
+ * @param right right-hand side
+ * @result tuple type
+ */
 struct type *type_tuple(struct type *left, struct type *right);
+/**
+ * Constructor for a type variable
+ *
+ * @param ident identifier of the variable
+ * @result type variable
+ */
 struct type *type_var(struct ident ident);
+/**
+ * Constructor for a type variable from a string
+ *
+ * @param s string identifier of the variable
+ * @result type variable
+ */
 struct type *type_var_str(char *s);
+/**
+ * Constructor for a type variable from an integer
+ *
+ * @param i integer identifier of the variable
+ * @result type variable
+ */
 struct type *type_var_int(int i);
 
+/**
+ * Print a type to the output stream
+ *
+ * @param type type
+ * @param stream stream to print to
+ */
 void type_print(struct type *type, FILE *stream);
+/**
+ * Recursively free a type
+ *
+ * @param type type
+ */
 void type_free(struct type *type);
 
+/**
+ * Compare a type
+ *
+ * @param l left-hand side
+ * @param r right-hand side
+ * @result comparison
+ */
 int type_cmp(struct type *l, struct type *r);
 
+/**
+ * Duplicate a type
+ *
+ * @param t type
+ * @result duplicated type
+ */
 struct type *type_dup(struct type *t);
+
+/**
+ * Find the free type variables in a type. The provided buffer will be
+ * reallocated whenever a free type variable is found.
+ *
+ * @param r type to search in
+ * @param nftv pointer to an integer representing the number of found free
+ *	type variables
+ * @param ftv pointer to a pointer to a buffer for storing the free type
+ *	variables
+ */
 void type_ftv(struct type *r, int *nftv, struct ident **ftv);
+/**
+ * Predicate to test whether an identifier is free in a type.
+ *
+ * @param type type to search in
+ * @param ident identifier
+ * @result free
+ */
 bool type_free_in(struct type *type, struct ident ident);
 
 #endif
diff --git a/src/util.h b/src/util.h
index bfdd21c..2b9dd6f 100644
--- a/src/util.h
+++ b/src/util.h
@@ -5,29 +5,81 @@
 #include <stdbool.h>
 #include <stdio.h>
 
-/* exit with an error message */
+/**
+ * Emit the error message and exit with return code 1
+ *
+ * @param msg format string
+ * @param ... format arguments
+ */
 void die(const char *msg, ...);
-/* exit with the system's error message prefixed by msg */
+/**
+ * Emit the system's error message prefixed with \p msg and exit with return code
+ * 1
+ *
+ * @param msg message prefix
+ */
 void pdie(const char *msg);
 
-/* if buf == NULL, a fresh buffer is allocated */
+/**
+ * Escape a character, if \p buf == NULL, a fresh buffer is allocated
+ *
+ * @param c character to escape or the name of the escape (e.g. n for newline)
+ * @param buf buffer to store the escape sequence in
+ * @param str string or in a character context (escape " or ')
+ * @result buffer containing the escape sequence
+ */
 char *escape_char(char c, char *buf, bool str);
-/* unescaped character will be in position 0 and the rest from position 1 on */
+/**
+ * Unescape the given escape sequence
+ *
+ * @param c buffer starting with the escape sequence
+ * @result same buffer but now unescaped
+ */
 char *unescape_char(char *c);
-/* Remove the last and first character from the string */
+/**
+ * Remove the last and first character from a string
+ *
+ * @param c string
+ * @result trimmed string
+ */
 char *trimquotes(char *c);
-/* Print indentation */
+/**
+ * Print \p indent indentation level
+ *
+ * @param indent indentation level
+ * @param out output stream
+ */
 void pindent(int indent, FILE *out);
 
-/* Safe wrappers around syscalls */
+/** Call vfprintf but bail out if it fails */
 void safe_vfprintf(FILE *out, const char *msg, va_list ap);
+/** Call fprintf but bail out if it fails */
 void safe_fprintf(FILE *out, const char *msg, ...);
+/** Call malloc but bail out if it fails */
 void *safe_malloc(size_t size);
+/**
+ * Typed variant of safe_malloc
+ *
+ * @param nmemb number of members
+ * @param type type of the members
+ * @result pointer to the allocated buffer
+ */
 #define xalloc(nmemb, type) ((type *)safe_malloc((nmemb)*sizeof(type)))
+/** Call remalloc but bail out if it fails */
 void *safe_realloc(void *ptr, size_t size);
+/**
+ * Typed variant of safe_remalloc
+ *
+ * @param ptr pointer to the buffer that possibly needs reallocation
+ * @param nmemb number of members
+ * @param type type of the members
+ * @result pointer to the reallocated buffer
+ */
 #define xrealloc(ptr, nmemb, type) ((type *)safe_realloc(ptr, (nmemb)*sizeof(type)))
 void *safe_strdup(const char *c);
+/** Call fopen but bail out if it fails */
 FILE *safe_fopen(const char *path, const char *mode);
+/** Call fclose but bail out if it fails */
 void safe_fclose(FILE *file);
 
 #endif
diff --git a/test.bash b/test.bash
index 04d4be6..ba9e576 100644
--- a/test.bash
+++ b/test.bash
@@ -23,7 +23,7 @@ do
 		fail=$((fail+1))
 	else
 		"$SPLC" $1 -o "$ccode"
-		"$CC" -I"$RTSDIR" "$ccode" -o "$base"
+		"$CC" -I"$RTSDIR" "$RTSDIR"/rts.c "$ccode" -o "$base"
 		./"$base" > "$out"
 		if ! diff "$out" "$expected"
 		then
diff --git a/tests/2D.expected b/tests/2D.expected
new file mode 100644
index 0000000..be15b51
--- /dev/null
+++ b/tests/2D.expected
@@ -0,0 +1 @@
+(2,2)(39,44)(84,126)
diff --git a/tests/2D.spl b/tests/2D.spl
index 2903ef9..80e25dc 100644
--- a/tests/2D.spl
+++ b/tests/2D.spl
@@ -16,4 +16,5 @@ main() {
 	print(foo(42));
 	print(transpose((38, 42), (1, 2)));
 	print(scale((28, 42), 3));
+	print('\n');
 }
diff --git a/tests/3D.expected b/tests/3D.expected
new file mode 100644
index 0000000..537cb72
--- /dev/null
+++ b/tests/3D.expected
@@ -0,0 +1 @@
+(39,(44,19))(114,(126,48))
diff --git a/tests/3D.spl b/tests/3D.spl
index e040099..1f2effa 100644
--- a/tests/3D.spl
+++ b/tests/3D.spl
@@ -5,3 +5,8 @@ transpose (p1,p2) :: (Int, (Int, Int))  (Int, (Int, Int))   -> (Int, (Int, Int))
 scale(p, scalar) :: (Int, (Int, Int)) Int -> (Int, (Int, Int)) {
 	return (p.fst * scalar, (p.snd.fst * scalar, p.snd.snd * scalar));
 }
+main() {
+	print(transpose((38, (42, 16)), (1, (2, 3))));
+	print(scale((38, (42, 16)), 3));
+	print('\n');
+}
diff --git a/tests/a_bit_of_everything.expected b/tests/a_bit_of_everything.expected
new file mode 100644
index 0000000..e69de29
diff --git a/tests/arguments.expected b/tests/arguments.expected
new file mode 100644
index 0000000..e69de29
diff --git a/tests/arguments.shouldfail b/tests/arguments.shouldfail
new file mode 100644
index 0000000..e69de29
diff --git a/tests/assignment_to_builtin.expected b/tests/assignment_to_builtin.expected
new file mode 100644
index 0000000..e69de29
diff --git a/tests/assignment_to_builtin.shouldfail b/tests/assignment_to_builtin.shouldfail
new file mode 100644
index 0000000..e69de29
diff --git a/tests/assignment_to_builtin.spl b/tests/assignment_to_builtin.spl
index dc53a37..28de5eb 100644
--- a/tests/assignment_to_builtin.spl
+++ b/tests/assignment_to_builtin.spl
@@ -11,3 +11,9 @@ f()
   // Adapt this line if your isEmpty is called differently.
   isEmpty = blaat;
 }
+
+main()
+{
+	f();
+
+}
-- 
2.20.1