lambda_conversion.c

/*
 * CEKF - VM supporting amb
 * Copyright (C) 2022-2023  Bill Hails
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

/**
 * @file lambda_conversion.c
 *
 * conversion of the AST generated by the parser
 * to an intermediate "plain" lambda calculus which
 * will then be fed into the type checker and the
 * A-Normal Form converter.
 */

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#include "ast_debug.h"
#include "common.h"
#include "lambda_conversion.h"
#include "lambda_helper.h"
#include "lazy_substitution.h"
#include "pratt_scanner.h"
#include "print_generator.h"
#include "symbols.h"
#include "tpmc_logic.h"
#include "tpmc_mermaid.h"
#include "utils.h"

char *lambda_conversion_function = NULL; // set by --dump-lambda flag

static LamBindings *convertFuncDefs(AstDefinitions *, LamContext *);
static LamArgs *convertExpressions(AstExpressions *, LamContext *);
static LamSequence *convertSequence(AstExpressions *, LamContext *);
static LamBindings *prependDefinition(AstDefinition *, LamContext *,
                                      LamBindings *);
static LamBindings *prependDefine(AstDefine *, LamContext *, LamBindings *);
static LamExp *convertExpression(AstExpression *, LamContext *);
static bool typeHasFields(AstTypeBody *);
static LamTypeDefList *collectTypeDefs(AstDefinitions *, LamContext *);
static void collectAliases(AstDefinitions *, LamContext *);
static LamTypeConstructor *convertTypeConstructor(AstTypeConstructor *,
                                                  LamTypeSig *, int, int, bool,
                                                  LamContext *);
static void collectTypeInfo(HashSymbol *, AstTypeConstructorArgs *,
                            LamTypeConstructor *, bool, int, int, int,
                            LamContext *);
static LamTypeConstructorArgs *convertAstTypeList(AstTypeList *, LamContext *);
static LamTypeConstructorArgs *convertAstTypeMap(AstTypeMap *, LamContext *);
static LamTypeConstructorArgs *
convertAstTypeConstructorArgs(AstTypeConstructorArgs *, LamContext *);
static LamExp *convertNest(AstNest *, LamContext *);
static LamExp *lamConvert(AstDefinitions *, AstExpressions *, LamContext *);
static LamExp *convertSymbol(ParserInfo, HashSymbol *, LamContext *);
static LamExp *convertAnnotatedSymbol(AstAnnotatedSymbol *, LamContext *);
static LamExp *convertCut(AstExpression *, LamContext *);

#ifdef DEBUG_LAMBDA_CONVERT
#include "debugging_on.h"
#else
#include "debugging_off.h"
#endif

/**
 * @brief Creates a value that can be returned in the case of an error
 */
static LamExp *lamExpError(ParserInfo I) {
    return newLamExp_Var(I, errorSymbol());
}

/**
 * @brief Converts an AST program to a lambda expression.
 *
 * This is the top-level public entry point to the lambda conversion
 * code.
 *
 * @param prog The AST program to convert.
 * @return The resulting lambda expression.
 */
LamExp *lamConvertProg(AstProg *prog) {
    ENTER(lamConvertProg);
    LamContext *env = newLamContext(CPI(prog), NULL);
    int save = PROTECT(env);
    LamExp *result = lamConvert(prog->preamble, prog->body, env);
    UNPROTECT(save);
    LEAVE(lamConvertProg);
    return result;
}

/**
 * @brief Converts an AST nest to a lambda expression.
 *
 * @param nest The AST nest to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda expression.
 */
static LamExp *convertNest(AstNest *nest, LamContext *env) {
    ENTER(convertNest);
    env = newLamContext(CPI(nest), env);
    int save = PROTECT(env);
    LamExp *result = lamConvert(nest->definitions, nest->expressions, env);
    PROTECT(result);
    UNPROTECT(save);
    LEAVE(convertNest);
    return result;
}

static LamExp *convertCut(AstExpression *value, LamContext *env) {
    LamExp *exp = convertExpression(value, env);
    int save = PROTECT(exp);
    LamExp *result = newLamExp_Cut(CPI(value), exp);
    UNPROTECT(save);
    return result;
}

/**
 * @brief Adds constructor information to the lambda context.
 *
 * @param context The lambda context to modify.
 * @param symbol The name of the constructor.
 * @param info The constructor information to add.
 * @return void
 */
static void addConstructorInfoToLamContext(LamContext *context,
                                           HashSymbol *symbol,
                                           LamTypeConstructorInfo *info) {
    setLamInfoTable(context->frame, symbol, info);
}

static void separateLambdas(LamBindings *funcDefs, LamBindings **lambdas,
                            LamBindings **other) {
    if (funcDefs != NULL) {
        separateLambdas(funcDefs->next, lambdas, other);
        if (funcDefs->val->type == LAMEXP_TYPE_LAM) {
            *lambdas = newLamBindings(CPI(funcDefs), funcDefs->var,
                                      funcDefs->val, *lambdas);
            PROTECT(*lambdas);
        } else {
            *other = newLamBindings(CPI(funcDefs), funcDefs->var, funcDefs->val,
                                    *other);
            PROTECT(*other);
        }
    }
}

static void appendLamBindings(LamBindings **lambdas, LamBindings **other) {
    if (*lambdas == NULL) {
        *lambdas = *other;
    } else if (*other != NULL) {
        LamBindings *walker = *lambdas;
        while (walker->next != NULL) {
            walker = walker->next;
        }
        walker->next = *other;
    }
}

/**
 * @brief Hoists function definitions to the front of the letrec bindings.
 *
 * @param funcDefs The letrec bindings to hoist.
 * @return The resulting letrec bindings with functions hoisted to the front.
 */
__attribute__((unused)) static LamBindings *
hoistFunctionDefinitions(LamBindings *funcDefs) {
    int save = PROTECT(funcDefs);
    LamBindings *lambdas = NULL;
    LamBindings *other = NULL;
    separateLambdas(funcDefs, &lambdas, &other);
    appendLamBindings(&lambdas, &other);
    UNPROTECT(save);
    return lambdas;
}

/**
 * @brief Workhorse routine that converts various nest-like scenarios to a
 * common LamExp
 *
 * @param definitions If there were definitions.
 * @param expressions The AST expressions to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda expression.
 */
static LamExp *lamConvert(AstDefinitions *definitions,
                          AstExpressions *expressions, LamContext *env) {
    ENTER(lamConvert);

    // record aliases in env
    collectAliases(definitions, env);

    // convert and collect all the typeDefs (also adds them to env)
    LamTypeDefList *typeDefList = collectTypeDefs(definitions, env);
    int save = PROTECT(typeDefList);

    // convert and collect all the definitions:
    // [funcs and vars]
    LamBindings *defsList = convertFuncDefs(definitions, env);
    PROTECT(defsList);

    // hoist function definitions to the front:
    // [funcs]
    // [vars]
    LamBindings *funcDefsList = NULL;
    LamBindings *varDefsList = NULL;
    separateLambdas(defsList, &funcDefsList, &varDefsList); // PROTECTS them

    // prepend print functions:
    // [printers] [funcs]
    // [vars]
    funcDefsList = makePrintFunctions(typeDefList, funcDefsList, env);
    PROTECT(funcDefsList);

    // convert the body sequence
    LamSequence *body = convertSequence(expressions, env);
    PROTECT(body);

    // promote the body sequence to a LamExp
    // [[body]]
    LamExp *letRecBody =
        (body == NULL) ? NULL : newLamExp_Sequence(CPI(body), body);
    PROTECT(letRecBody);

    LamExp *result = NULL;
    if (varDefsList != NULL) {
        // prepend variable definitions to the letrec body
        // [vars] [[body]]
        letRecBody =
            makeLamExp_LetStar(CPI(varDefsList), varDefsList, letRecBody);
        PROTECT(letRecBody);
    }
    // if there are functions, create a letrec, else just use the body
    if (funcDefsList != NULL) {
        // [[printers] [funcs] [vars] [[body]]]
        if (letRecBody == NULL) {
            // a program with definitions but no body needs a valid
            // expression so the letrec is well-formed
            letRecBody = newLamExp_Stdint(CPI(funcDefsList), 0);
            PROTECT(letRecBody);
        }
        result = makeLamExp_LetRec(CPI(letRecBody), funcDefsList, letRecBody);
    } else {
        // [vars] [[body]]
        result = letRecBody;
    }
    PROTECT(result);

    // prepend typeDefs if any
    if (typeDefList != NULL) {
        // [typeDefs] [[printers] [funcs] [vars] [[body]]]
        result = makeLamExp_TypeDefs(CPI(typeDefList), typeDefList, result);
    }

    // cleanup and return
    UNPROTECT(save);
    LEAVE(lamConvert);
    return result;
}

/**
 * @brief Converts an AST If Expression to a lambda expression.
 *
 * @param iff The If Expression to convert.
 * @param context The lambda context to use.
 * @return The resulting lambda expression.
 */

static LamExp *lamConvertIff(AstIff *iff, LamContext *context) {
    ENTER(lamConvertIff);
    LamExp *test = convertExpression(iff->test, context);
    int save = PROTECT(test);
    LamExp *consequent = convertNest(iff->consequent, context);
    PROTECT(consequent);
    LamExp *alternative = convertNest(iff->alternative, context);
    PROTECT(alternative);
    LamExp *result = makeLamExp_Iff(CPI(test), test, consequent, alternative);
    UNPROTECT(save);
    LEAVE(lamConvertIff);
    return result;
}

/**
 * @brief Converts an AST Print Expression to a lambda expression.
 *
 * @param print The AST Print Expression to convert.
 * @param context The lambda context to use.
 * @return The resulting lambda expression.
 */
static LamExp *lamConvertPrint(AstPrint *print, LamContext *context) {
    ENTER(lamConvertPrint);
    LamExp *exp = convertExpression(print->exp, context);
    int save = PROTECT(exp);
    LamExp *result = makeLamExp_Print(CPI(exp), exp);
    UNPROTECT(save);
    LEAVE(lamConvertPrint);
    return result;
}

/**
 * @brief Converts an AST TypeOf Expression to a lambda expression that returns
 * the type as a string.
 *
 * @param typeOfExp The AST TypeOf Expression to convert.
 * @param context The lambda context to use.
 * @return The resulting lambda expression.
 */
static LamExp *lamConvertTypeOf(AstTypeOf *typeOfExp, LamContext *context) {
    ENTER(lamConvertTypeOf);
    LamExp *exp = convertExpression(typeOfExp->exp, context);
    int save = PROTECT(exp);
    LamExp *result = makeLamExp_TypeOf(CPI(exp), exp);
    UNPROTECT(save);
    LEAVE(lamConvertTypeOf);
    return result;
}

/**
 * @brief Converts an AST Tuple Expression to a lambda expression that
 * constructs a tuple.
 *
 * @param tuple The Tuple Expression to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda expression.
 */
static LamExp *lamConvertTuple(ParserInfo PI, AstExpressions *tuple,
                               LamContext *env) {
    LamArgs *expressions = convertExpressions(tuple, env);
    int save = PROTECT(expressions);
    LamExp *res = newLamExp_MakeTuple(PI, expressions);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Checks if a particular definition is a macro, and if so, adds it to
 * the macro table in the environment.
 *
 * @param definition The AST definition to check.
 * @param env The lambda context to use.
 * @return void
 */
static void checkLazy(AstDefinition *definition, LamContext *env) {
    if (definition->type == AST_DEFINITION_TYPE_LAZY) {
        setSymbolSet(env->macros, getAstDefinition_Lazy(definition)->name);
    }
}

/**
 * @brief Converts a list of AST function definitions to a list of letrec
 * bindings.
 *
 * @param definitions The AST function definitions to convert.
 * @param env The lambda context to use.
 * @return The resulting list of letrec bindings.
 */
static LamBindings *convertFuncDefs(AstDefinitions *definitions,
                                    LamContext *env) {
    ENTER(convertFuncDefs);
    if (definitions == NULL) {
        LEAVE(convertFuncDefs);
        return NULL;
    }
    checkLazy(definitions->definition, env);
    LamBindings *next = convertFuncDefs(definitions->next, env);
    int save = PROTECT(next);
    LamBindings *this = prependDefinition(definitions->definition, env, next);
    UNPROTECT(save);
    LEAVE(convertFuncDefs);
    return this;
}

/**
 * @brief Converts a list of AST type symbols to a list of lambda type signature
 * arguments.
 *
 * @param symbols The AST type symbols to convert.
 * @return The resulting lambda type signature arguments.
 */
static LamTypeSigArgs *convertTypeSymbols(AstTypeSymbols *symbols) {
    if (symbols == NULL)
        return NULL;
    LamTypeSigArgs *next = convertTypeSymbols(symbols->next);
    int save = PROTECT(next);
    LamTypeSigArgs *this =
        newLamTypeSigArgs(CPI(symbols), symbols->typeSymbol, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts an AST Type Signature to a lambda type signature.
 *
 * @param typeSig The AST Type Signature to convert.
 * @return The resulting lambda type signature.
 */
static LamTypeSig *convertTypeSig(AstTypeSig *typeSig) {
    LamTypeSigArgs *args = convertTypeSymbols(typeSig->typeSymbols);
    int save = PROTECT(args);
    LamTypeSig *res = newLamTypeSig(CPI(typeSig), typeSig->symbol, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Checks to see if a symbol is an alias for a type constructor
 * invocation.
 *
 * @param los The AST LookUpOrSymbol to check.
 * @param env The lambda context to use.
 * @return The resulting lambda type constructor type, or NULL if not found.
 */
static LamTypeConstructorType *expandSymbolAlias(AstLookUpOrSymbol *los,
                                                 LamContext *env) {
    switch (los->type) {
    case AST_LOOKUPORSYMBOL_TYPE_SYMBOL:
        return lookUpConstructorTypeInLamContext(
            env, getAstLookUpOrSymbol_Symbol(los));
    case AST_LOOKUPORSYMBOL_TYPE_LOOKUP:
        return NULL;
    default:
        cant_happen("unrecognized %s", astLookUpOrSymbolTypeName(los->type));
    }
}

/**
 * @brief checks to see if a type function is actually an alias for another.
 *
 * @param function The AST type function to check.
 * @param env The lambda context to use.
 * @return The resulting lambda type constructor type, either original or alias.
 */
static LamTypeConstructorType *expandFunctionAlias(AstTypeFunction *function,
                                                   LamContext *env) {
    if (function->typeList != NULL) {
        return NULL;
    }
    return expandSymbolAlias(function->symbol, env);
}

/**
 * @brief Converts an AST Type Function to a lambda type function.
 *
 * @param astTypeFunction The AST Type Function to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda type function.
 */
static LamTypeFunction *convertAstTypeFunction(AstTypeFunction *astTypeFunction,
                                               LamContext *env) {
    LamTypeConstructorArgs *lamTypeConstructorArgs =
        convertAstTypeList(astTypeFunction->typeList, env);
    int save = PROTECT(lamTypeConstructorArgs);
    HashSymbol *name = getAstLookUpOrSymbol_Symbol(astTypeFunction->symbol);
    LamTypeFunction *this =
        newLamTypeFunction(CPI(astTypeFunction), name, lamTypeConstructorArgs);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts an AST Type Clause to a lambda type constructor type.
 *
 * @param astTypeClause The AST Type Clause to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda type constructor type.
 */
static LamTypeConstructorType *
convertAstTypeClause(AstTypeClause *astTypeClause, LamContext *env) {
    switch (astTypeClause->type) {
    case AST_TYPECLAUSE_TYPE_INTEGER:
        return newLamTypeConstructorType_Integer(CPI(astTypeClause));
    case AST_TYPECLAUSE_TYPE_CHARACTER:
        return newLamTypeConstructorType_Character(CPI(astTypeClause));
    case AST_TYPECLAUSE_TYPE_VAR:
        return newLamTypeConstructorType_Var(
            CPI(astTypeClause), getAstTypeClause_Var(astTypeClause));
    case AST_TYPECLAUSE_TYPE_TYPEFUNCTION: {
        LamTypeConstructorType *alias = expandFunctionAlias(
            getAstTypeClause_TypeFunction(astTypeClause), env);
        if (alias != NULL) {
            return alias;
        }
        LamTypeFunction *lamTypeFunction = convertAstTypeFunction(
            getAstTypeClause_TypeFunction(astTypeClause), env);
        int save = PROTECT(lamTypeFunction);
        LamTypeConstructorType *this = newLamTypeConstructorType_Function(
            CPI(astTypeClause), lamTypeFunction);
        UNPROTECT(save);
        return this;
    }
    case AST_TYPECLAUSE_TYPE_TYPETUPLE: {
        LamTypeConstructorArgs *lamTypeConstructorArgs =
            convertAstTypeList(getAstTypeClause_TypeTuple(astTypeClause), env);
        int save = PROTECT(lamTypeConstructorArgs);
        LamTypeConstructorType *this = newLamTypeConstructorType_Tuple(
            CPI(astTypeClause), lamTypeConstructorArgs);
        UNPROTECT(save);
        return this;
    }
    default:
        cant_happen(
            "unrecognised astTypeClause type %d in convertAstTypeClause",
            astTypeClause->type);
    }
}

/**
 * @brief Creates a lambda type function representing a function from one type
 * to another.
 *
 * @param lhs The left-hand side type constructor.
 * @param rhs The right-hand side type constructor.
 * @return The resulting lambda type function.
 */
static LamTypeFunction *makeArrow(LamTypeConstructorType *lhs,
                                  LamTypeConstructorType *rhs) {
    LamTypeConstructorArgs *rhsArg =
        newLamTypeConstructorArgs(CPI(rhs), rhs, NULL);
    int save = PROTECT(rhsArg);
    LamTypeConstructorArgs *argss =
        newLamTypeConstructorArgs(CPI(lhs), lhs, rhsArg);
    PROTECT(argss);
    LamTypeFunction *res = newLamTypeFunction(CPI(lhs), arrowSymbol(), argss);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Converts an AST Type to a lambda type constructor type.
 *
 * This function handles both simple types and function types.
 *
 * @param astType The AST Type to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda type constructor type.
 */
static LamTypeConstructorType *convertAstType(AstType *astType,
                                              LamContext *env) {
    if (astType->next) { // it's a function
        LamTypeConstructorType *next = convertAstType(astType->next, env);
        int save = PROTECT(next);
        LamTypeConstructorType *this =
            convertAstTypeClause(astType->typeClause, env);
        PROTECT(this);
        LamTypeFunction *arrow = makeArrow(this, next);
        PROTECT(arrow);
        LamTypeConstructorType *res =
            newLamTypeConstructorType_Function(CPI(astType), arrow);
        UNPROTECT(save);
        return res;
    } else {
        return convertAstTypeClause(astType->typeClause, env);
    }
}

/**
 * @brief Converts an AST Type List to a list of lambda type constructor
 * arguments.
 *
 * @param typeList The AST Type List to convert.
 * @param env The lambda context to use.
 * @return The resulting list of lambda type constructor arguments.
 */
static LamTypeConstructorArgs *convertAstTypeList(AstTypeList *typeList,
                                                  LamContext *env) {
    if (typeList == NULL)
        return NULL;
    LamTypeConstructorArgs *next = convertAstTypeList(typeList->next, env);
    int save = PROTECT(next);
    LamTypeConstructorType *arg = convertAstType(typeList->type, env);
    PROTECT(arg);
    LamTypeConstructorArgs *this =
        newLamTypeConstructorArgs(CPI(arg), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts an AST Type Map to a list of lambda type constructor
 * arguments.
 *
 * @param typeMap The AST Type Map to convert.
 * @param env The lambda context to use.
 * @return The resulting list of lambda type constructor arguments.
 */
static LamTypeConstructorArgs *convertAstTypeMap(AstTypeMap *typeMap,
                                                 LamContext *env) {
    if (typeMap == NULL)
        return NULL;
    LamTypeConstructorArgs *next = convertAstTypeMap(typeMap->next, env);
    int save = PROTECT(next);
    LamTypeConstructorType *arg = convertAstType(typeMap->type, env);
    PROTECT(arg);
    LamTypeConstructorArgs *this =
        newLamTypeConstructorArgs(CPI(arg), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts AST Type Constructor Arguments (list or map) to a list of
 * lambda type constructor arguments.
 *
 * @param args The AST Type Constructor Arguments to convert.
 * @param env The lambda context to use.
 * @return The resulting list of lambda type constructor arguments.
 */
static LamTypeConstructorArgs *
convertAstTypeConstructorArgs(AstTypeConstructorArgs *args, LamContext *env) {
    if (args == NULL) {
        return NULL;
    }
    switch (args->type) {
    case AST_TYPECONSTRUCTORARGS_TYPE_LIST: {
        return convertAstTypeList(getAstTypeConstructorArgs_List(args), env);
    }
    case AST_TYPECONSTRUCTORARGS_TYPE_MAP: {
        return convertAstTypeMap(getAstTypeConstructorArgs_Map(args), env);
    }
    default:
        cant_happen("unrecognized %s",
                    astTypeConstructorArgsTypeName(args->type));
    }
}

/**
 * @brief Converts an AST Type Map to a list of lambda type tags.
 *
 * This function recursively converts the AST Type Map into a linked list of
 * LamTypeTags.
 *
 * @param map The AST Type Map to convert.
 * @return The resulting list of lambda type tags.
 */
static LamTypeTags *astTypeConstructorArgMapToTags(AstTypeMap *map) {
    if (map == NULL)
        return NULL;
    LamTypeTags *next = astTypeConstructorArgMapToTags(map->next);
    int save = PROTECT(next);
    LamTypeTags *this = newLamTypeTags(CPI(map), map->key, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief converts the AST Type Constructor Arguments to a list of lambda type
 * tags, IFF the arguments are a map.
 *
 * @param args The AST Type Constructor Arguments to convert.
 * @return The resulting list of lambda type tags, or NULL if the arguments are
 * not a map.
 */
static LamTypeTags *makeLamTypeTags(AstTypeConstructorArgs *args) {
    if (args == NULL) {
        return NULL;
    }
    switch (args->type) {
    case AST_TYPECONSTRUCTORARGS_TYPE_LIST:
        return NULL;
    case AST_TYPECONSTRUCTORARGS_TYPE_MAP:
        return astTypeConstructorArgMapToTags(
            getAstTypeConstructorArgs_Map(args));
    default:
        cant_happen("unrecognized %s",
                    astTypeConstructorArgsTypeName(args->type));
    }
}

/**
 * @brief Collects as much type information as possible about the type
 * constructor and stores it in the context.
 */
static void collectTypeInfo(HashSymbol *symbol, AstTypeConstructorArgs *args,
                            LamTypeConstructor *type, bool needsVec,
                            int enumCount, int index, int arity,
                            LamContext *env) {
    ENTER(collectTypeInfo);
    LamTypeTags *tags = makeLamTypeTags(args);
    int save = PROTECT(tags);
    LamTypeConstructorInfo *info = newLamTypeConstructorInfo(
        CPI(type), symbol, type, tags, needsVec, arity, enumCount, index);
    PROTECT(info);
    addConstructorInfoToLamContext(env, symbol, info);
    UNPROTECT(save);
    LEAVE(collectTypeInfo);
}

/**
 * @brief counts the number of items in the AST Type Constructor Arguments (list
 * or map).
 *
 * @param args The AST Type Constructor Arguments to count.
 * @return The number of items in the arguments.
 */
static Index countAstTypeConstructorArgs(AstTypeConstructorArgs *args) {
    if (args == NULL)
        return 0;
    switch (args->type) {
    case AST_TYPECONSTRUCTORARGS_TYPE_LIST: {
        return countAstTypeList(getAstTypeConstructorArgs_List(args));
    }
    case AST_TYPECONSTRUCTORARGS_TYPE_MAP: {
        return countAstTypeMap(getAstTypeConstructorArgs_Map(args));
    }
    default:
        cant_happen("unrecognized %s",
                    astTypeConstructorArgsTypeName(args->type));
    }
}

/**
 * @brief Converts an AST Type Constructor to a lambda type constructor and
 * collects its type information.
 *
 * @param typeConstructor The AST Type Constructor to convert.
 * @param type The type signature of the constructor type.
 * @param enumCount The number of constructors of this type.
 * @param index The index of the constructor (serves as an identifier).
 * @param needsVec Whether the constructor needs to create a vector.
 * @return The resulting lambda type constructor.
 */
static LamTypeConstructor *
convertTypeConstructor(AstTypeConstructor *typeConstructor, LamTypeSig *type,
                       int enumCount, int index, bool needsVec,
                       LamContext *env) {
    int nArgs = countAstTypeConstructorArgs(typeConstructor->args);
    LamTypeConstructorArgs *args =
        convertAstTypeConstructorArgs(typeConstructor->args, env);
    int save = PROTECT(args);
    LamTypeConstructor *lamTypeConstructor =
        newLamTypeConstructor(CPI(type), typeConstructor->symbol, type, args);
    PROTECT(lamTypeConstructor);
    collectTypeInfo(typeConstructor->symbol, typeConstructor->args,
                    lamTypeConstructor, needsVec, enumCount, index, nArgs, env);
    UNPROTECT(save);
    return lamTypeConstructor;
}

/**
 * @brief Converts an AST Type Definition to a lambda type definition.
 *
 * @param typeDef The AST Type Definition to convert.
 * @param env The lambda context.
 * @return The resulting lambda type definition.
 */
static LamTypeDef *convertTypeDef(AstTypeDef *typeDef, LamContext *env) {
    LamTypeSig *type = convertTypeSig(typeDef->typeSig);
    int save = PROTECT(type);
    AstTypeBody *typeBody = typeDef->typeBody;
    bool needsVec = typeHasFields(typeBody);
    int enumCount = countAstTypeBody(typeBody);
    int index = 0;
    LamTypeConstructorList *lamTypeConstructorList = NULL;
    int save2 = PROTECT(type);
    while (typeBody != NULL) {
        LamTypeConstructor *lamTypeConstructor = convertTypeConstructor(
            typeBody->typeConstructor, type, enumCount, index, needsVec, env);
        int save3 = PROTECT(lamTypeConstructor);
        lamTypeConstructorList = newLamTypeConstructorList(
            CPI(lamTypeConstructor), lamTypeConstructor,
            lamTypeConstructorList);
        REPLACE_PROTECT(save2, lamTypeConstructorList);
        UNPROTECT(save3);
        typeBody = typeBody->next;
        index++;
    }
    LamTypeDef *res = newLamTypeDef(CPI(type), type, lamTypeConstructorList);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Collects an alias definition and adds it to the lambda context.
 *
 * @param alias The AST Alias to collect.
 * @param env The lambda context to use.
 * @return void
 */
static void collectAlias(AstAlias *alias, LamContext *env) {
    LamTypeConstructorType *type = convertAstType(alias->type, env);
    int save = PROTECT(type);
    setLamAliasTable(env->aliases, alias->name, type);
    UNPROTECT(save);
}

/**
 * @brief recurses over a list of definitions, collecting any aliases in the
 * context.
 *
 * @param definitions The list of AST definitions to process.
 * @param env The lambda context to populate.
 * @return void
 */
static void collectAliases(AstDefinitions *definitions, LamContext *env) {
    if (definitions == NULL) {
        return;
    }
    switch (definitions->definition->type) {
    case AST_DEFINITION_TYPE_DEFINE:
    case AST_DEFINITION_TYPE_BLANK:
    case AST_DEFINITION_TYPE_TYPEDEF:
    case AST_DEFINITION_TYPE_LAZY:
    case AST_DEFINITION_TYPE_MULTI:
        break;
    case AST_DEFINITION_TYPE_ALIAS:
        collectAlias(getAstDefinition_Alias(definitions->definition), env);
        break;
    case AST_DEFINITION_TYPE_SYNTAXDECL:
    case AST_DEFINITION_TYPE_SYNTAXUSE:
        can_happen(CPI(definitions->definition),
                   "syntax carrier %s reached lambda conversion before syntax "
                   "lowering",
                   astDefinitionTypeName(definitions->definition->type));
        break;
    default:
        cant_happen("unrecognised %s",
                    astDefinitionTypeName(definitions->definition->type));
    }
    collectAliases(definitions->next, env);
}

/**
 * @brief Checks against duplicate macro arguments in a list.
 *
 * @param arg The macro argument to check.
 * @param args The list of existing macro arguments.
 * @return void
 */
static void checkDuplicateLazyArg(HashSymbol *arg, SymbolList *args) {
    if (args == NULL)
        return;
    if (arg == args->symbol) {
        can_happen(CPI(args), "duplicate argument \"%s\" in macro definition",
                   arg->name);
        return;
    }
    checkDuplicateLazyArg(arg, args->next);
}

/**
 * @brief Collects macro arguments from an AST argument list.
 *
 * This function recursively collects macro arguments and both
 * checks for duplicates and asserts that the arguments are symbols.
 *
 * @param argList The AST argument list to collect from.
 * @return A linked list of lambda variable arguments.
 */
static SymbolList *collectLazyArgs(AstFargList *argList) {
    if (argList == NULL)
        return NULL;
    SymbolList *next = collectLazyArgs(argList->next);
    int save = PROTECT(next);
    HashSymbol *arg = getAstFarg_Symbol(argList->arg);
    checkDuplicateLazyArg(arg, next);
    SymbolList *this = newSymbolList(CPI(argList), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Populates a lambda macro arguments table from a list of arguments.
 *
 * This function iterates over the list of lambda variable arguments and adds
 * each one to the macro arguments table with a NULL value.
 *
 * @param symbols The macro arguments table to populate.
 * @param args The list of lambda variable arguments.
 * @return void
 */
static void populateArgsTable(SymbolSet *symbols, SymbolList *args) {
    if (args == NULL)
        return;
    setSymbolSet(symbols, args->symbol);
    populateArgsTable(symbols, args->next);
}

/**
 * @brief Converts an AST Lazy Definition to a lambda expression.
 *
 * This function converts the lazy definition into a lambda expression.
 * Lazys evaluate their arguments on-demand, so the generated lazy lambda
 * must wrap each of its arguments in a promise.
 *
 * @param astLazy The AST Lazy Definition to convert.
 * @param env The lambda context to use.
 * @return The resulting lambda expression for the macro.
 */
static LamExp *convertAstLazy(AstDefLazy *astLazy, LamContext *env) {
    ENTER(convertAstLazy);
    // get the list of argument symbols
    SymbolList *args = collectLazyArgs(astLazy->definition->altArgs->argList);
    int save = PROTECT(args);
    // do a standard conversion of the macro body
    LamExp *body = convertNest(astLazy->definition->nest, env);
    PROTECT(body);
    // create a random-access set of the macro argument symbols
    SymbolSet *symbolTable = newSymbolSet();
    PROTECT(symbolTable);
    populateArgsTable(symbolTable, args);
    // force all the argument thunks in the body of the macro
    body = lamPerformLazySubstitutions(body, symbolTable);
    PROTECT(body);
    // prepare the resulting lambda expression
    LamExp *res = makeLamExp_Lam(CPI(astLazy), args, body);
    PROTECT(res);
    getLamExp_Lam(res)->isLazy = true;
    // remember it's a macro
    setSymbolSet(env->macros, astLazy->name);
    LEAVE(convertAstLazy);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Collects type definitions from a list of AST definitions.
 *
 * This function recursively collects type definitions from the AST
 * and converts them into lambda type definitions.
 *
 * @param definitions The AST definitions to collect from.
 * @param env The lambda context to use.
 * @return A linked list of lambda type definitions.
 */
static LamTypeDefList *collectTypeDefs(AstDefinitions *definitions,
                                       LamContext *env) {
    if (definitions == NULL) {
        return NULL;
    }
    switch (definitions->definition->type) {
    case AST_DEFINITION_TYPE_DEFINE:
    case AST_DEFINITION_TYPE_ALIAS:
    case AST_DEFINITION_TYPE_BLANK:
    case AST_DEFINITION_TYPE_LAZY:
    case AST_DEFINITION_TYPE_MULTI:
        return collectTypeDefs(definitions->next, env);
    case AST_DEFINITION_TYPE_TYPEDEF: {
        LamTypeDef *lamTypeDef = convertTypeDef(
            getAstDefinition_TypeDef(definitions->definition), env);
        int save = PROTECT(lamTypeDef);
        LamTypeDefList *rest = collectTypeDefs(definitions->next, env);
        PROTECT(rest);
        LamTypeDefList *res =
            newLamTypeDefList(CPI(lamTypeDef), lamTypeDef, rest);
        UNPROTECT(save);
        return res;
    }
    case AST_DEFINITION_TYPE_SYNTAXDECL:
    case AST_DEFINITION_TYPE_SYNTAXUSE:
        can_happen(CPI(definitions->definition),
                   "syntax carrier %s reached lambda conversion before syntax "
                   "lowering",
                   astDefinitionTypeName(definitions->definition->type));
        return collectTypeDefs(definitions->next, env);
    default:
        cant_happen("unrecognised %s",
                    astDefinitionTypeName(definitions->definition->type));
    }
}

/**
 * @brief Convert and prepend a lazy definition to the list of letRec bindings.
 * @param lazy The AST lazy definition to convert.
 * @param env The lambda context to use.
 * @param next The letRec list to prepend to.
 * @return The new letRec bindings with the lazy definition prepended.
 */
static LamBindings *prependLazy(AstDefLazy *lazy, LamContext *env,
                                LamBindings *next) {
    ENTER(prependLazy);
    LamExp *exp = convertAstLazy(lazy, env);
    int save = PROTECT(exp);
    LamBindings *this = newLamBindings(CPI(lazy), lazy->name, exp, next);
    UNPROTECT(save);
    LEAVE(prependLazy);
    return this;
}

LamExp *makeUnpackTuple(ParserInfo PI, LamExp *temp, int index, int size) {
    return makeLamExp_TupleIndex(PI, index, size, temp);
}

static LamBindings *prependMultiSymbols(AstSymbolList *symbols, int index,
                                        int size, LamExp *temp,
                                        LamBindings *next) {
    if (symbols == NULL) {
        return next;
    }
    LamBindings *rest =
        prependMultiSymbols(symbols->next, index + 1, size, temp, next);
    if (symbols->symbol == TOK_WILDCARD()) {
        return rest;
    }
    int save = PROTECT(rest);
    LamExp *rhs = makeUnpackTuple(CPI(symbols), temp, index, size);
    PROTECT(rhs);
    LamBindings *this =
        newLamBindings(CPI(symbols), symbols->symbol, rhs, rest);
    UNPROTECT(save);
    return this;
}

static LamBindings *prependMulti(AstMultiDefine *multi, LamContext *env,
                                 LamBindings *next) {
    ENTER(prependMulti);
    LamExp *exp = convertExpression(multi->expression, env);
    int save = PROTECT(exp);
    HashSymbol *temp = genSymDollar("multi");
    LamExp *tempExp = newLamExp_Var(CPI(multi), temp);
    PROTECT(tempExp);
    LamBindings *parts = prependMultiSymbols(
        multi->symbols, 0, countAstSymbolList(multi->symbols), tempExp, next);
    PROTECT(parts);
    LamBindings *this = newLamBindings(CPI(multi), temp, exp, parts);
    UNPROTECT(save);
    LEAVE(prependMulti);
    return this;
}

/**
 * @brief Prepends a definition to the list of letRec bindings.
 *
 * This function handles macros and definitions and converts them
 * into lambda letRec bindings.
 *
 * @param definition The AST definition to prepend.
 * @param env The lambda context to use.
 * @param next The next letRec binding in the list.
 * @return The new letRec bindings with the definition prepended.
 */
static LamBindings *prependDefinition(AstDefinition *definition,
                                      LamContext *env, LamBindings *next) {
    ENTER(prependDefinition);
    LamBindings *result = NULL;
    switch (definition->type) {
    case AST_DEFINITION_TYPE_DEFINE:
        result = prependDefine(getAstDefinition_Define(definition), env, next);
        break;
    case AST_DEFINITION_TYPE_LAZY:
        result = prependLazy(getAstDefinition_Lazy(definition), env, next);
        break;
    case AST_DEFINITION_TYPE_MULTI:
        result = prependMulti(getAstDefinition_Multi(definition), env, next);
        break;
    case AST_DEFINITION_TYPE_ALIAS:
    case AST_DEFINITION_TYPE_TYPEDEF:
    case AST_DEFINITION_TYPE_BLANK:
        result = next;
        break;
    case AST_DEFINITION_TYPE_SYNTAXDECL:
    case AST_DEFINITION_TYPE_SYNTAXUSE:
        can_happen(CPI(definition),
                   "syntax carrier %s reached lambda conversion before syntax "
                   "lowering",
                   astDefinitionTypeName(definition->type));
        result = next;
        break;
    default:
        cant_happen("unrecognised %s", astDefinitionTypeName(definition->type));
    }
    LEAVE(prependDefinition);
    return result;
}

/**
 * @brief Checks if a type body has any fields (i.e., type constructor
 * arguments).
 *
 * This function iterates over the type body and checks if any type constructor
 * has arguments defined. This is done to determine if the type should be
 * constructed as a simple scalar or if it needs to be a vector.
 *
 * For example in
 * ```
 * typedef colour { red | green | blue }
 * ```
 * because none of the constructors have arguments, they can all be represented
 * as simple scalars. Bit in the case of
 * ```
 * typedef list(#t) { null | cons(#t, list(#t))}
 * ```
 * because `cons` has fields, both `null` and `cons` need to be represented as
 * vectors.
 *
 * @param typeBody The AST Type Body to check.
 * @return true if there are fields, false otherwise.
 */
static bool typeHasFields(AstTypeBody *typeBody) {
    ENTER(typeHasFields);
    while (typeBody != NULL) {
        if (typeBody->typeConstructor->args != NULL) {
            LEAVE(typeHasFields);
            return true;
        }
        typeBody = typeBody->next;
    }
    LEAVE(typeHasFields);
    return false;
}

/**
 * @brief Converts and prepends a definition to the list of letRec bindings.
 * @param define The AST definition to convert.
 * @param env The lambda context to use.
 * @param next The current letrec bindings.
 * @return The new letRec bindings with the definition prepended.
 */
static LamBindings *prependDefine(AstDefine *define, LamContext *env,
                                  LamBindings *next) {
    ENTER(prependDefine);
    bool doMermaid = (tpmc_mermaid_function != NULL &&
                      strcmp(tpmc_mermaid_function, define->symbol->name) == 0);
    if (doMermaid)
        tpmc_mermaid_flag = 1;
    LamExp *exp = convertExpression(define->expression, env);
    if (lambda_conversion_function != NULL &&
        strcmp(lambda_conversion_function, define->symbol->name) == 0) {
        ppLamExp(stdout, exp);
        printf("\n");
    }
    if (doMermaid)
        tpmc_mermaid_flag = 0;
    int save = PROTECT(exp);
    LamBindings *this = newLamBindings(CPI(define), define->symbol, exp, next);
    UNPROTECT(save);
    LEAVE(prependDefine);
    return this;
}

#define CHECK_ONE_ARG(name, args)                                              \
    do {                                                                       \
        int count = countLamArgs(args);                                        \
        if (count != 1)                                                        \
            can_happen(CPI(args), "expected 1 arg in " #name ", got %d",       \
                       count);                                                 \
    } while (0)

#define CHECK_TWO_ARGS(name, args)                                             \
    do {                                                                       \
        int count = countLamArgs(args);                                        \
        if (count != 2)                                                        \
            can_happen(CPI(args), "expected 2 args in " #name ", got %d",      \
                       count);                                                 \
    } while (0)

/**
 * @brief Creates a call/cc expression.
 *
 * @param args The arguments to the call/cc expression.
 * @return the lambda expression.
 */
static LamExp *makeCallCC(LamArgs *args) {
    CHECK_ONE_ARG(makeCallCC, args);
    return newLamExp_CallCC(CPI(args), args->exp);
}

/**
 * @brief Creates a binary operation expression.
 *
 * @param opCode The operation code for the binary operation.
 * @param args The arguments to the binary operation.
 * @return The resulting lambda expression for the binary operation.
 */
static LamExp *makeBinOp(LamPrimOp opCode, LamArgs *args) {
    CHECK_TWO_ARGS(makeBinOp, args);
    return makeLamExp_Prim(CPI(args), opCode, args->exp, args->next->exp);
}

/**
 * @brief Creates a lambda expression for an "amb" operation.
 * @param args The arguments to the "amb" operation.
 * @return The resulting lambda expression.
 */
static LamExp *makeLamAmb(LamArgs *args) {
    CHECK_TWO_ARGS(makeLamAmb, args);
    return makeLamExp_Amb(CPI(args), args->exp, args->next->exp);
}

/**
 * @brief Creates a unary negation expression.
 * @param args The arguments to the unary negation expression.
 * @return The resulting lambda expression.
 */
static LamExp *makeUnaryNeg(LamArgs *args) {
    CHECK_ONE_ARG(makeUnaryNeg, args);
    MaybeBigInt *num = fakeBigInt(0, false);
    int save = PROTECT(num);
    LamExp *zero = newLamExp_BigInteger(CPI(args), num);
    PROTECT(zero);
    args = newLamArgs(CPI(args), zero, args);
    PROTECT(args);
    LamExp *result = makeBinOp(LAMPRIMOP_TYPE_SUB, args);
    UNPROTECT(save);
    return result;
}

/**
 * @brief Creates a unary canonicalization expression.
 * @param args The argument to canonicalize.
 * @return The resulting lambda expression.
 */
static LamExp *makeUnaryCanon(LamArgs *args) {
    CHECK_ONE_ARG(makeUnaryCanon, args);
    MaybeBigInt *num = fakeBigInt(0, false);
    int save = PROTECT(num);
    LamExp *zero = newLamExp_BigInteger(CPI(args), num);
    PROTECT(zero);
    LamArgs *next = newLamArgs(CPI(args), zero, NULL);
    PROTECT(next);
    LamArgs *canonArgs = newLamArgs(CPI(args), args->exp, next);
    PROTECT(canonArgs);
    LamExp *result = makeBinOp(LAMPRIMOP_TYPE_CANON, canonArgs);
    UNPROTECT(save);
    return result;
}

/**
 * @brief Checks if a symbol is a macro in the given environment.
 * @param symbol The symbol to check.
 * @param env The environment to search in.
 * @return True if the symbol is a macro, false otherwise.
 */
static bool isLazy(HashSymbol *symbol, LamContext *env) {
    if (env == NULL) {
        return false;
    }
    if (getSymbolSet(env->macros, symbol)) {
        return true;
    }
    return isLazy(symbol, env->parent);
}

/**
 * @brief Wraps a macro argument in a thunk.
 *
 * @description A thunk is a lambda with no arguments that returns the argument
 * when called. This allows macros to evaluate their arguments on-demand. The
 * equivalent invocation of the thunk is generated by `performVarSubstitution`
 * in `macro_substitution.c`.
 *
 * @param arg The argument to wrap.
 * @return The resulting thunked argument.
 */
static LamExp *thunkLazyArg(LamExp *arg) {
    LamExp *res = makeLamExp_Lam(CPI(arg), NULL, arg);
    return res;
}

/**
 * @brief Wraps the arguments of a macro in thunks.
 * @param args The arguments to wrap.
 * @return The resulting wrapped arguments.
 */
static LamArgs *thunkLazyArgs(LamArgs *args) {
    if (args == NULL) {
        return NULL;
    }
    LamArgs *next = thunkLazyArgs(args->next);
    int save = PROTECT(next);
    LamExp *arg = thunkLazyArg(args->exp);
    PROTECT(arg);
    LamArgs *this = newLamArgs(CPI(arg), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts a macro application where the callee is an arbitrary
 * expression (e.g., a nameSpaced lookUp), wrapping the arguments in thunks.
 * @param PI The parser information.
 * @param callee The callee expression (can be a LookUp or Var).
 * @param args The arguments to the macro.
 * @return The resulting lambda expression.
 */
static LamExp *thunkLazyExp(ParserInfo PI, LamExp *callee, LamArgs *args) {
    args = thunkLazyArgs(args);
    int save = PROTECT(args);
    LamExp *res = makeLamExp_Apply(PI, callee, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Converts a macro application into a lambda expression, wrapping the
 * arguments in thunks.
 * @param PI The parser information.
 * @param symbol The macro name.
 * @param args The arguments to the macro.
 * @return The resulting lambda expression.
 */
static LamExp *thunkLazySymbol(ParserInfo PI, HashSymbol *symbol,
                               LamArgs *args) {
    LamExp *exp = newLamExp_Var(PI, symbol);
    int save = PROTECT(exp);
    LamExp *res = thunkLazyExp(PI, exp, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Creates a lambda primitive application based on the symbol and
 * arguments.
 * @param PI The parser information.
 * @param symbol The macro or operator name.
 * @param args The arguments to the macro.
 * @return The resulting lambda expression.
 */
static LamExp *makePrimApp(ParserInfo PI, HashSymbol *symbol, LamArgs *args,
                           LamContext *env) {
    if (isLazy(symbol, env)) {
        return thunkLazySymbol(PI, symbol, args);
    }
    if (symbol == negSymbol())
        return makeUnaryNeg(args);
    if (symbol == hereSymbol())
        return makeCallCC(args);
    if (symbol == thenSymbol())
        return makeLamAmb(args);
    if (symbol == eqSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_EQ, args);
    if (symbol == neSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_NE, args);
    if (symbol == gtSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_GT, args);
    if (symbol == ltSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_LT, args);
    if (symbol == geSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_GE, args);
    if (symbol == leSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_LE, args);
    if (symbol == addSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_ADD, args);
    if (symbol == subSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_SUB, args);
    if (symbol == mulSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_MUL, args);
    if (symbol == divSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_DIV, args);
    if (symbol == modSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_MOD, args);
    if (symbol == gcdSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_GCD, args);
    if (symbol == lcmSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_LCM, args);
    if (symbol == canonSymbol())
        return makeUnaryCanon(args);
    if (symbol == powSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_POW, args);
    if (symbol == cmpSymbol())
        return makeBinOp(LAMPRIMOP_TYPE_CMP, args);
    return NULL;
}

/**
 * @brief Provisionally creates a constructor application if the symbol is a
 * constructor in the current env.
 * @param symbol The symbol.
 * @param env The environment to look in.
 * @return The resulting lambda expression, or NULL.
 */
static LamExp *makeConstructor(HashSymbol *symbol, LamContext *env) {
    LamTypeConstructorInfo *info = lookUpConstructorInLamContext(env, symbol);
    if (info != NULL) {
        return newLamExp_Constructor(CPI(info), info);
    }
    return NULL;
}

/**
 * @brief Creates a lambda application.
 * @param fun The function expression.
 * @param args The arguments to apply the function to.
 * @return The resulting lambda application expression.
 */
static LamExp *makeApplication(LamExp *fun, LamArgs *args) {
    LamExp *result = makeLamExp_Apply(CPI(fun), fun, args);
    return result;
}

/**
 * @brief Converts a list of bound variables to a list of lambda arguments.
 * @param list The list of bound variables.
 * @return The resulting list of lambda arguments.
 */
static LamArgs *varListToList(SymbolList *list) {
    if (list == NULL)
        return NULL;
    LamArgs *next = varListToList(list->next);
    int save = PROTECT(next);
    LamExp *var = newLamExp_Var(CPI(list), list->symbol);
    PROTECT(var);
    LamArgs *this = newLamArgs(CPI(var), var, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Generates a list of symbolic variables.
 * @param I The parser information.
 * @param nArgs The number of arguments.
 * @return The resulting list of symbolic variables.
 */
static SymbolList *genSymVarList(ParserInfo I, int nArgs) {
    if (nArgs == 0) {
        return NULL;
    }
    SymbolList *rest = genSymVarList(I, nArgs - 1);
    int save = PROTECT(rest);
    HashSymbol *s = genSym("$x");
    SymbolList *this = newSymbolList(I, s, rest);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Finds the underlying arity of a lambda expression.
 *
 * This function checks if the expression is a constructor or a lookUp,
 * and returns the arity of the constructor or recursively finds the arity
 * of the underlying expression in case of a lookUp.
 *
 * @param exp The lambda expression to check.
 * @return The arity of the underlying constructor.
 */
static int findUnderlyingArity(LamExp *exp) {
    switch (exp->type) {
    case LAMEXP_TYPE_CONSTRUCTOR:
        return getLamExp_Constructor(exp)->arity;
    default:
        cant_happen("expected constructor");
    }
}

/**
 * @brief Checks if a tag (symbol) is present in the given list of tags.
 * @param tag The lambda tag to check for.
 * @param astTags The list of AST tags to search.
 */
static void checkLamTagPresent(HashSymbol *tag, AstTaggedExpressions *astTags) {
    if (astTags == NULL) {
        cant_happen("missing tag %s", tag->name);
    }
    if (tag == astTags->tag) {
        return;
    }
    checkLamTagPresent(tag, astTags->next);
}

/**
 * @brief Checks if all tags are present in the given list of tags.
 * @param lamTags The list of lambda tags to check.
 * @param astTags The list of AST tags to search.
 */
static void checkAllTagsPresent(LamTypeTags *lamTags,
                                AstTaggedExpressions *astTags) {
    if (lamTags == NULL)
        return;
    checkLamTagPresent(lamTags->tag, astTags);
    checkAllTagsPresent(lamTags->next, astTags);
}

/**
 * @brief Checks if a specific AST tag is present in the list of lambda tags.
 * @param lamTags The list of lambda tags to check.
 * @param astTag The AST tag to search for.
 */
static void checkAstTagPresent(LamTypeTags *lamTags, HashSymbol *astTag) {
    if (lamTags == NULL) {
        cant_happen("missing constructor tag %s", astTag->name);
    }
    if (astTag == lamTags->tag)
        return;
    checkAstTagPresent(lamTags->next, astTag);
}

/**
 * @brief Checks if any unrecognised AST tags are present in the list of lambda
 * tags.
 * @param lamTags The list of lambda tags to check.
 * @param astTags The list of AST tags to search.
 */
static void checkNoUnrecognisedTags(LamTypeTags *lamTags,
                                    AstTaggedExpressions *astTags) {
    if (astTags == NULL)
        return;
    checkAstTagPresent(lamTags, astTags->tag);
    checkNoUnrecognisedTags(lamTags, astTags->next);
}

/**
 * @brief Checks if a specific AST tag is present in the list of lambda tags.
 * @param lamTags The list of lambda tags to check.
 * @param astTag The AST tag to search for.
 */
static void checkTagNotDuplicate(HashSymbol *tag, AstTaggedExpressions *tags) {
    if (tags == NULL)
        return;
    if (tag == tags->tag) {
        can_happen(CPI(tags), "duplicate tag %s", tag->name);
        return;
    }
    checkTagNotDuplicate(tag, tags->next);
}

/**
 * @brief Checks if any duplicate tags are present in the list of AST tags.
 * @param tags The list of AST tags to check.
 */
static void checkNoDuplicateTags(AstTaggedExpressions *tags) {
    if (tags == NULL)
        return;
    checkTagNotDuplicate(tags->tag, tags->next);
    checkNoDuplicateTags(tags->next);
}

/**
 * @brief Finds the tagged expression for a given tag.
 * @param tag The tag to search for.
 * @param tags The list of tagged expressions to search.
 * @return The tagged expression.
 */
static AstExpression *findTaggedExpression(HashSymbol *tag,
                                           AstTaggedExpressions *tags) {
#ifdef SAFETY_CHECKS
    if (tags == NULL) {
        cant_happen("cannot find value for tag %s", tag->name);
    }
#endif
    if (tag == tags->tag)
        return tags->expression;
    return findTaggedExpression(tag, tags->next);
}

/**
 * @brief Arranges the AST tagged expressions in the canonical order of the
 * lambda tags.
 *
 * The result is a normal function application, without tags.
 *
 * @param lamTags The list of lambda tags to arrange.
 * @param astTags The list of AST tags to search.
 * @param env The lambda context.
 */
static LamArgs *convertTagsToArgs(LamTypeTags *lamTags,
                                  AstTaggedExpressions *astTags,
                                  LamContext *env) {
    // lamTags are in canonical order
    if (lamTags == NULL)
        return NULL;
    LamArgs *rest = convertTagsToArgs(lamTags->next, astTags, env);
    int save = PROTECT(rest);
    AstExpression *expression = findTaggedExpression(lamTags->tag, astTags);
    LamExp *lamExp = convertExpression(expression, env);
    PROTECT(lamExp);
    LamArgs *this = newLamArgs(CPI(lamExp), lamExp, rest);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Allows a constructor application to be curried by wrapping it in a
 * curried function application.
 *
 * Example:
 * (constructor4 arg1 arg2) =>
 * ((lambda (x1 x2 x3 x4) (constructor4 x1 x2 x3 x4)) arg1 arg2)
 *
 * @param constructor The constructor to apply.
 * @param args The arguments to apply to the constructor.
 * @return The curried constructor application.
 */
static LamExp *makeConstructorApplication(LamExp *constructor, LamArgs *args) {
    int nArgs = (int)countLamArgs(args);
    LamExp *result;
    int arity = findUnderlyingArity(constructor);
    if (nArgs < arity) {
        SymbolList *fargs = genSymVarList(CPI(constructor), arity);
        int save = PROTECT(fargs);
        LamArgs *aargs = varListToList(fargs);
        PROTECT(aargs);
        LamApply *innerApply =
            newLamApply(CPI(constructor), constructor, aargs);
        PROTECT(innerApply);
        LamExp *applyExp = newLamExp_Apply(CPI(innerApply), innerApply);
        PROTECT(applyExp);
        LamExp *lamExp = makeLamExp_Lam(CPI(fargs), fargs, applyExp);
        PROTECT(lamExp);
        result = makeLamExp_Apply(CPI(lamExp), lamExp, args);
        UNPROTECT(save);
    } else {
        result = makeLamExp_Apply(CPI(constructor), constructor, args);
    }
    return result;
}
/**
 * @brief Creates a structure application from a constructor and a list of
 * tagged expressions.
 *
 * This function checks that the constructor is indeed a structure constructor,
 * verifies that all tags are present, checks for duplicates, and then creates
 * the application expression.
 *
 * @param constructor The constructor to apply.
 * @param tags The tagged expressions to apply to the constructor.
 * @param env The lambda context.
 * @return The resulting lambda expression for the structure application.
 */

static LamExp *makeStructureApplication(LamExp *constructor,
                                        AstTaggedExpressions *tags,
                                        LamContext *env) {
    if (getLamExp_Constructor(constructor)->tags == NULL) {
        can_happen(CPI(constructor),
                   "non-struct constructor applied to struct");
        return lamExpError(CPI(tags));
    }
    checkAllTagsPresent(getLamExp_Constructor(constructor)->tags, tags);
    checkNoUnrecognisedTags(getLamExp_Constructor(constructor)->tags, tags);
    checkNoDuplicateTags(tags);
    int arity = findUnderlyingArity(constructor);
    int nArgs = (int)countAstTaggedExpressions(tags);
    if (nArgs != arity) {
        can_happen(CPI(constructor),
                   "wrong number of args in structure application");
        return lamExpError(CPI(tags));
    }
    LamArgs *args =
        convertTagsToArgs(getLamExp_Constructor(constructor)->tags, tags, env);
    int save = PROTECT(args);
    LamExp *result = makeLamExp_Apply(CPI(constructor), constructor, args);
    UNPROTECT(save);
    return result;
}
/**
 * @brief Finds a constructor in the lambda context.
 *
 * This function looks up a constructor by its name in the given lambda context.
 * If the constructor is a lookUp, find the constructor in the referenced
 * nameSpace.
 *
 * @param los The lookUp or symbol to find.
 * @param env The lambda context.
 * @return The found constructor information, or NULL if not found.
 */
static LamTypeConstructorInfo *findConstructor(AstLookUpOrSymbol *los,
                                               LamContext *env) {
    switch (los->type) {
    case AST_LOOKUPORSYMBOL_TYPE_SYMBOL:
        return lookUpConstructorInLamContext(env,
                                             getAstLookUpOrSymbol_Symbol(los));
    case AST_LOOKUPORSYMBOL_TYPE_LOOKUP:
        cant_happen("unexpected lookUp in findConstructor");
    default:
        cant_happen("unrecognized %s", astLookUpOrSymbolTypeName(los->type));
    }
}

/**
 * @brief Converts a structure AST node to a lambda expression.
 *
 * @param structure The structure AST node to convert.
 * @param env The lambda context.
 * @return The resulting lambda expression for the structure.
 */
static LamExp *convertStructure(AstStruct *structure, LamContext *env) {
    LamTypeConstructorInfo *info = findConstructor(structure->symbol, env);
    if (info == NULL) {
        can_happen(CPI(structure), "cannot find constructor");
        return lamExpError(CPI(structure));
    }
    LamExp *constructor = newLamExp_Constructor(CPI(info), info);
    int save = PROTECT(constructor);
    LamExp *result =
        makeStructureApplication(constructor, structure->expressions, env);
    UNPROTECT(save);
    return result;
}

/**
 * @brief Converts a function call AST node to a lambda expression.
 *
 * This function takes a function call AST node and converts it into a
 * lambda expression by applying the function to its arguments.
 * The "function" in this case can be a variable, a constructor, or any
 * other expression that can be applied.
 *
 * @param funCall The function call AST node to convert.
 * @param env The lambda context.
 * @return The resulting lambda expression for the function call.
 */
static LamExp *convertFunCall(AstFunCall *funCall, LamContext *env) {
    LamArgs *args = convertExpressions(funCall->arguments, env);
    int save = PROTECT(args);
    LamExp *function = convertExpression(funCall->function, env);
    PROTECT(function);
    LamExp *result = NULL;
    switch (function->type) {
    case LAMEXP_TYPE_VAR: {
        result = makePrimApp(CPI(funCall), getLamExp_Var(function), args, env);
        if (result != NULL) {
            UNPROTECT(save);
            return result;
        }
        result = makeApplication(function, args);
        getLamExp_Apply(result)->isBuiltin = funCall->isBuiltin;
        UNPROTECT(save);
        return result;
    }
    case LAMEXP_TYPE_CONSTRUCTOR: {
        result = makeConstructorApplication(function, args);
        UNPROTECT(save);
        return result;
    }
    default: {
        result = makeApplication(function, args);
        UNPROTECT(save);
        return result;
    }
    }
}

static AstFargList *rewriteAstFargList(AstFargList *args, LamContext *env);
static AstFarg *rewriteAstFarg(AstFarg *arg, LamContext *env);

/**
 * @brief Recursively rewrites the named component of an AstNamedArg.
 *
 * @param arg The AST formal argument to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AstNamedArg wrapped in an AstFarg.
 */
static AstFarg *rewriteAstNamed(AstNamedArg *namedArg, LamContext *env) {
    AstFarg *arg = rewriteAstFarg(namedArg->arg, env);
    int save = PROTECT(arg);
    AstFarg *res = makeAstFarg_Named(CPI(namedArg), namedArg->name, arg);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Rewrites the components of an AstUnpack.
 *
 * @param unpack The AstUnpack to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AstUnpack, wrapped in an AstFarg.
 */
static AstFarg *rewriteAstUnpack(AstUnpack *unpack, LamContext *env) {
    AstFargList *args = rewriteAstFargList(unpack->argList, env);
    int save = PROTECT(args);
    AstFarg *res = makeAstFarg_Unpack(CPI(unpack), unpack->symbol, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Retrieves an AstFarg from an AST tagged argument list.
 *
 * This function searches through the tagged argument list for a
 * matching tag and returns the corresponding AstFarg.
 * If no matching tag is found, a wildCard AstFarg is returned.
 * This allows a struct formal argument to not have to name unwanted fields.
 *
 * @param tag The tag to search for.
 * @param list The AST tagged argument list to search.
 * @param env The lambda context to use for rewriting.
 * @param I The parser information.
 * @return The corresponding AstFarg, or a wildCard if not found.
 */
static AstFarg *getAstFargFromTaggedArgList(HashSymbol *tag,
                                            AstTaggedArgList *list,
                                            LamContext *env, ParserInfo I) {
    if (list == NULL) {
        return newAstFarg_WildCard(I);
    }
    if (tag == list->tag) {
        return rewriteAstFarg(list->arg, env);
    }
    return getAstFargFromTaggedArgList(tag, list->next, env, I);
}

/**
 * @brief Rewrites an AST tagged argument list into a plain AstFargList.
 *
 * The canonical positions of the tags dictate the order of the arguments.
 * The actual unpacking is done by `getAstFargFromTaggedArgList`.
 *
 * @param allTags The list of all tags of the constructor in canonical order.
 * @param argTags The AST tagged argument list to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AST tagged argument list, wrapped in an AstFargList.
 */
static AstFargList *rewriteAstTaggedArgList(LamTypeTags *allTags,
                                            AstTaggedArgList *argTags,
                                            LamContext *env) {
    if (allTags == NULL)
        return NULL;
    AstFargList *next = rewriteAstTaggedArgList(allTags->next, argTags, env);
    int save = PROTECT(next);
    AstFarg *arg =
        getAstFargFromTaggedArgList(allTags->tag, argTags, env, CPI(argTags));
    PROTECT(arg);
    AstFargList *this = newAstFargList(CPI(argTags), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Rewrites an AST unpack struct argument into a plain AstUnpack.
 *
 * The canonical positions of the tags dictate the order of the arguments.
 * The actual unpacking is done by `rewriteAstTaggedArgList`.
 *
 * @param structure The AST unpack struct argument to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AST unpack struct argument, wrapped in an AstFarg.
 */
static AstFarg *rewriteAstUnpackStruct(AstUnpackStruct *structure,
                                       LamContext *env) {
    LamTypeConstructorInfo *info = findConstructor(structure->symbol, env);
    if (info->tags == NULL) {
        can_happen(CPI(structure), "constructor not a struct");
        return newAstFarg_WildCard(CPI(structure));
    }
    AstFargList *args =
        rewriteAstTaggedArgList(info->tags, structure->argList, env);
    int save = PROTECT(args);
    AstFarg *res = makeAstFarg_Unpack(CPI(structure), structure->symbol, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Rewrites the components of an AST tuple argument.
 * @param tuple The AST tuple argument to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AST tuple argument.
 */
static AstFarg *rewriteAstTuple(AstFargList *tuple, LamContext *env) {
    AstFargList *new = rewriteAstFargList(tuple, env);
    int save = PROTECT(new);
    AstFarg *res = newAstFarg_Tuple(CPI(tuple), new);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Rewrites an AST formal argument into a form more suitable for tpmc
 * conversion.
 *
 * Named arguments are recursed into.
 * Unpack arguments are recursed into.
 * Tuple arguments are recursed into.
 * UnpackStruct arguments are replaced with unpack arguments,
 * hence the recursion.
 *
 * @param arg The AST formal argument to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AST formal argument.
 */
static AstFarg *rewriteAstFarg(AstFarg *arg, LamContext *env) {
    switch (arg->type) {
    case AST_FARG_TYPE_WILDCARD:
    case AST_FARG_TYPE_SYMBOL:
    case AST_FARG_TYPE_NUMBER:
    case AST_FARG_TYPE_CHARACTER:
    case AST_FARG_TYPE_LOOKUP:
        return arg;
    case AST_FARG_TYPE_NAMED:
        return rewriteAstNamed(getAstFarg_Named(arg), env);
    case AST_FARG_TYPE_UNPACK:
        return rewriteAstUnpack(getAstFarg_Unpack(arg), env);
    case AST_FARG_TYPE_UNPACKSTRUCT:
        return rewriteAstUnpackStruct(getAstFarg_UnpackStruct(arg), env);
    case AST_FARG_TYPE_TUPLE:
        return rewriteAstTuple(getAstFarg_Tuple(arg), env);
    default:
        cant_happen("unrecognized %s", astFargTypeName(arg->type));
    }
}

/**
 * @brief Rewrites an AST formal argument list into a form more suitable for
 * tpmc conversion.
 * @param args The AST formal argument list to rewrite.
 * @param env The lambda context to use for rewriting.
 * @return The rewritten AST formal argument list.
 */
static AstFargList *rewriteAstFargList(AstFargList *args, LamContext *env) {
    if (args == NULL)
        return NULL;
    AstFargList *next = rewriteAstFargList(args->next, env);
    int save = PROTECT(next);
    AstFarg *arg = rewriteAstFarg(args->arg, env);
    PROTECT(arg);
    AstFargList *this = newAstFargList(CPI(args), arg, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts the bodies of a composite function into a single lambda
 * expression.
 *
 * This function calls into the TPMC code to convert the formal arguments and
 * separate function bodies to a single pattern matcher dispatching to the
 * appropriate body.
 *
 * @param nArgs The number of arguments for the function.
 * @param fun The composite function to convert.
 * @param env The lambda context to use for conversion.
 * @return The converted composite function.
 */
static LamLam *convertCompositeBodies(ParserInfo PI, int nArgs,
                                      AstCompositeFunction *fun,
                                      LamContext *env) {
    ENTER(convertCompositeBodies);
    int nBodies = countAstCompositeFunction(fun);
    if (nBodies == 0) {
        can_happen(PI, "empty composite function");
        LEAVE(convertCompositeBodies);
        return NULL;
    }
    LamExp **actions = NEW_ARRAY(LamExp *, nBodies);
    AstFargList **argLists = NEW_ARRAY(AstFargList *, nBodies);
    int p = STARTPROTECT();
    AstCompositeFunction *f = fun;
    for (int i = 0; i < nBodies; i++, f = f->next) {
        AstFunction *func = f->function;
        actions[i] = convertNest(func->nest, env);
        PROTECT(actions[i]);
        argLists[i] = rewriteAstFargList(func->argList, env);
        PROTECT(argLists[i]);
    }
    LamLam *result = tpmcConvert(fun->unsafe, CPI(fun), nArgs, nBodies,
                                 argLists, actions, env);
    PROTECT(result);
    FREE_ARRAY(LamExp *, actions, nBodies);
    FREE_ARRAY(AstFargList *, argLists, nBodies);
    UNPROTECT(p);
    LEAVE(convertCompositeBodies);
    return result;
}

/**
 * @brief Converts a composite function into a lambda expression.
 * @param PI The parser information.
 * @param fun The composite function to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda expression for the composite function.
 */
static LamExp *convertCompositeFun(ParserInfo PI, AstCompositeFunction *fun,
                                   LamContext *env) {
    ENTER(convertCompositeFun);
    if (fun == NULL) {
        can_happen(PI, "composite function with no components");
        return lamExpError(PI);
    }
    int nArgs = countAstFargList(fun->function->argList);
    LamLam *lambda = convertCompositeBodies(PI, nArgs, fun, env);
    DEBUG("convertCompositeBodies returned %p", lambda);
    int save = PROTECT(lambda);
    LamExp *result = newLamExp_Lam(CPI(lambda), lambda);
    UNPROTECT(save);
    LEAVE(convertCompositeFun);
    return result;
}

/**
 * @brief Converts a symbol into a lambda expression.
 * @param I The parser information.
 * @param symbol The symbol to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda expression for the symbol.
 */
static LamExp *convertSymbol(ParserInfo I, HashSymbol *symbol,
                             LamContext *env) {
    ENTER(convertSymbol);
    LamExp *result = makeConstructor(symbol, env);
    DEBUG("convertSymbol %s %d - %s: %s", I.fileName, I.lineNo, symbol->name,
          result ? "constructor" : "variable");
    if (result == NULL) {
        result = newLamExp_Var(I, symbol);
    }
    LEAVE(convertSymbol);
    return result;
}

/**
 * @brief Converts an annotated symbol (hygienic operator wrapper) into a lambda
 * expression.
 *
 * This handles the case where a hygienic operator wrapper ($opN) wraps a type
 * constructor. If the original implementation is a type constructor, we return
 * a reference to that constructor directly, allowing it to be used in patterns.
 * Otherwise, we return a reference to the hygienic wrapper function.
 *
 * @param annotated The annotated symbol containing both wrapper and original
 * implementation.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda expression (either constructor or variable
 * reference).
 */
static LamExp *convertAnnotatedSymbol(AstAnnotatedSymbol *annotated,
                                      LamContext *env) {
    ENTER(convertAnnotatedSymbol);
    LamExp *result = NULL;

    // Check if the original implementation is a bare symbol that's a type
    // constructor
    if (annotated->originalImpl->type == AST_EXPRESSION_TYPE_SYMBOL) {
        HashSymbol *originalSym =
            getAstExpression_Symbol(annotated->originalImpl);
        LamExp *constructor = makeConstructor(originalSym, env);
        if (constructor != NULL) {
            // Original is a type constructor - return it directly for pattern
            // matching
            DEBUG("convertAnnotatedSymbol: %s wraps constructor %s, using "
                  "constructor directly",
                  annotated->symbol->name, originalSym->name);
            result = constructor;
            LEAVE(convertAnnotatedSymbol);
            return result;
        }
        // Non-lazy operator: resolve original symbol directly at call site
        if (!annotated->isLazy) {
            DEBUG("convertAnnotatedSymbol: %s is non-lazy, using original "
                  "symbol %s directly",
                  annotated->symbol->name, originalSym->name);
            result = newLamExp_Var(CPI(annotated), originalSym);
            LEAVE(convertAnnotatedSymbol);
            return result;
        }
    }

    // Lazy operator: use the hygienic wrapper symbol
    DEBUG("convertAnnotatedSymbol: %s is not a constructor wrapper, using "
          "hygienic function",
          annotated->symbol->name);
    HashSymbol *symbol = annotated->symbol;
    result = newLamExp_Var(CPI(annotated), symbol);
    LEAVE(convertAnnotatedSymbol);
    return result;
}

LamExp *callErrorFunction(LamExp *exp) {
    int save = PROTECT(exp);
    LamArgs *args = newLamArgs(CPI(exp), exp, NULL);
    PROTECT(args);
    LamExp *fileName = stringToLamArgs(CPI(exp), exp->_yy_parser_info.fileName);
    PROTECT(fileName);
    args = newLamArgs(CPI(exp), fileName, args);
    PROTECT(args);
    MaybeBigInt *num = fakeBigInt(exp->_yy_parser_info.lineNo, false);
    PROTECT(num);
    LamExp *lineNo = newLamExp_BigInteger(CPI(exp), num);
    PROTECT(lineNo);
    args = newLamArgs(CPI(lineNo), lineNo, args);
    PROTECT(args);
    LamExp *function = newLamExp_Var(CPI(exp), fnErrorSymbol());
    PROTECT(function);
    LamExp *res = makeApplication(function, args);
    UNPROTECT(save);
    return res;
}

/**
 * @brief Converts an error expression into a lambda expression.
 *
 * Calls the `__error__` function defined in the preamble.
 *
 * @param value The error expression (string) to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda expression for the error.
 */
static LamExp *convertError(AstExpression *value, LamContext *env) {
    LamExp *exp = convertExpression(value, env);
    return callErrorFunction(exp);
}

/**
 * @brief Converts a generic AST expression into a lambda expression.
 * @param expression The expression to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda expression for the input expression.
 */
static LamExp *convertExpression(AstExpression *expression, LamContext *env) {
    ENTER(convertExpression);
    LamExp *result = NULL;
    switch (expression->type) {
    case AST_EXPRESSION_TYPE_BACK:
        DEBUG("back");
        result = newLamExp_Back(CPI(expression));
        break;
    case AST_EXPRESSION_TYPE_FUNCALL:
        DEBUG("funcall");
        result = convertFunCall(getAstExpression_FunCall(expression), env);
        break;
    case AST_EXPRESSION_TYPE_ANNOTATEDSYMBOL:
        DEBUG("annotatedSymbol");
        result = convertAnnotatedSymbol(
            getAstExpression_AnnotatedSymbol(expression), env);
        break;
    case AST_EXPRESSION_TYPE_SYMBOL:
        DEBUG("symbol");
        result = convertSymbol(CPI(expression),
                               getAstExpression_Symbol(expression), env);
        break;
    case AST_EXPRESSION_TYPE_NUMBER:
        DEBUG("number");
        result = newLamExp_BigInteger(CPI(expression),
                                      getAstExpression_Number(expression));
        break;
    case AST_EXPRESSION_TYPE_CHARACTER:
        DEBUG("character");
        result = newLamExp_Character(CPI(expression),
                                     getAstExpression_Character(expression));
        break;
    case AST_EXPRESSION_TYPE_ENV:
        DEBUG("env");
        result = newLamExp_Env(CPI(expression));
        break;
    case AST_EXPRESSION_TYPE_FUN:
        DEBUG("fun");
        result = convertCompositeFun(CPI(expression),
                                     getAstExpression_Fun(expression), env);
        break;
    case AST_EXPRESSION_TYPE_NEST:
        DEBUG("nest");
        result = convertNest(getAstExpression_Nest(expression), env);
        break;
    case AST_EXPRESSION_TYPE_IFF:
        DEBUG("iff");
        result = lamConvertIff(getAstExpression_Iff(expression), env);
        break;
    case AST_EXPRESSION_TYPE_CUT:
        DEBUG("cut");
        result = convertCut(getAstExpression_Cut(expression), env);
        break;
    case AST_EXPRESSION_TYPE_PRINT:
        DEBUG("print");
        result = lamConvertPrint(getAstExpression_Print(expression), env);
        break;
    case AST_EXPRESSION_TYPE_TYPEOF:
        DEBUG("typeOf");
        result = lamConvertTypeOf(getAstExpression_TypeOf(expression), env);
        break;
    case AST_EXPRESSION_TYPE_TUPLE:
        DEBUG("tuple");
        result = lamConvertTuple(CPI(expression),
                                 getAstExpression_Tuple(expression), env);
        break;
    case AST_EXPRESSION_TYPE_LOOKUP:
        cant_happen("lookUp should have been resolved by ast_ns");
    case AST_EXPRESSION_TYPE_STRUCTURE:
        DEBUG("structure");
        result = convertStructure(getAstExpression_Structure(expression), env);
        break;
    case AST_EXPRESSION_TYPE_ASSERTION:
        cant_happen("assertions should have been rewritten by ast_ns");
    case AST_EXPRESSION_TYPE_ERROR:
        result = convertError(getAstExpression_Error(expression), env);
        break;
    case AST_EXPRESSION_TYPE_WILDCARD:
        can_happen(CPI(expression),
                   "cannot use wildCard '_' as a variable name");
        result = convertSymbol(CPI(expression), errorSymbol(), env);
        break;
    case AST_EXPRESSION_TYPE_SYNTAXUSE:
        can_happen(CPI(expression),
                   "syntax carrier %s reached lambda conversion before syntax "
                   "lowering",
                   astExpressionTypeName(expression->type));
        result = lamExpError(CPI(expression));
        break;
    default:
        cant_happen("unrecognised expression type %s",
                    astExpressionTypeName(expression->type));
    }
    LEAVE(convertExpression);
    return result;
}

/**
 * @brief Converts a list of AST expressions into a lambda argument list.
 * @param expressions The expressions to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda argument list for the input expressions.
 */
static LamArgs *convertExpressions(AstExpressions *expressions,
                                   LamContext *env) {
    if (expressions == NULL)
        return NULL;
    if (expressions == expressions->next)
        cant_happen("recursive expression loop");
    LamArgs *next = convertExpressions(expressions->next, env);
    int save = PROTECT(next);
    LamExp *exp = convertExpression(expressions->expression, env);
    (void)PROTECT(exp);
    LamArgs *this = newLamArgs(CPI(exp), exp, next);
    UNPROTECT(save);
    return this;
}

/**
 * @brief Converts a sequence of AST expressions into a lambda sequence.
 * @param expressions The expressions to convert.
 * @param env The lambda context to use for conversion.
 * @return The resulting lambda sequence for the input expressions.
 */
static LamSequence *convertSequence(AstExpressions *expressions,
                                    LamContext *env) {
    if (expressions == NULL)
        return NULL;
    LamSequence *next = convertSequence(expressions->next, env);
    int save = PROTECT(next);
    LamExp *exp = convertExpression(expressions->expression, env);
    (void)PROTECT(exp);
    LamSequence *this =
        (exp == NULL) ? NULL : newLamSequence(CPI(exp), exp, next);
    UNPROTECT(save);
    return this;
}