Skip to content

C back end: support concepts, models, and where clauses #1292

Open

Description

@jsiek

Refs #1264 (concepts and where clauses), #1282 (where clauses on generic functions), #1186 (geometry roadmap)

The C back end (--compile, --compile-module) rejects any program that declares a concept or a model, so nothing that uses concepts, models, where theorems, or where functions (#1291) can be compiled.

Repro

union L { nil  cons(bool, L) }

concept Monoid<T> {
  fun operator+ : fn (T, T) -> T
  fun zero : T
}

fun bor(a:bool, b:bool) { a or b }

model Monoid<bool> {
  fun operator+ = bor
  fun zero = false
}

fun twice<T> where { Monoid<T> } (x:T) { x + x }

print twice(true)

python deduce.py --no-stdlib --compile -o out.c file.pf (on the branch of #1291, which adds the where clause on twice):

compiler.lower.CompileError: file.pf:3: compiler does not yet support top-level: ConceptDecl

python deduce.py file.pf checks it and prints true.

(Compiling with the stdlib prelude fails earlier, on ViewDecl in lib/UIntDefs.pf: #1211.)

Proposal

After type checking, concepts need no runtime code of their own. Dictionary passing has already been made explicit by #1291, so the back end only has to handle the declarations and the leftover term forms:

  • ConceptDecl: erase, like Theorem and Postulate in compiler/lower.py:lower_stmt.
  • ModelDecl: emit each operation as a top-level definition under its hidden name (ModelDecl.funs is (member, define, body); collect_model already defines define = body in the checker's environment). Erase its theorems.
  • Where theorems (all T:type where {...}): proofs, already erased.
  • Where functions (Where clauses on generic functions (#1282) #1291): after type checking they are ordinary functions whose extra trailing parameters are the operations, and every call carries those arguments (a model's hidden definition, unfolded to its body where the model is visible, or an enclosing clause's parameter). Nothing extra should be needed beyond the above. Check that RecFun.where and Generic.where don't trip up lower_recfun/lower_define.
  • ConceptMember (@C<τ>.m outside a where clause): the checker unfolds it to the model's operation when the model is visible; otherwise it is the model's hidden definition name. Make sure lower_term handles that name like any other global.
  • Opaque models: their hidden definitions stay folded in other modules, so they must be emitted, and be linkable from other modules under --compile-module (see docs/separate-compile-plan.md).

Done when

  • The repro compiles and prints true, and so do programs using a where theorem's function at a model's type and a recursive function with a where clause (e.g. msum in test/test-imports/ConceptMonoidSum.pf from Where clauses on generic functions (#1282) #1291).
  • --compile-module works for a model in one module and a where function or call site in another, including an opaque model.
  • Tests in the existing compiler test layout cover these cases.

🤖 Generated with Claude Code

Activity

  1. jsiek commented on Nov 20, 2026

    @jsiek
    OwnerAuthor

    A correction to the plan above, from Codex's review of #1306 (where clauses on recfun): #1306 (comment)

    The "Where functions" bullet says nothing extra is needed. That's wrong. A call's operations are on TermInst.dicts, not in Call.args, and compiler/lower.py drops them: lower_term peels a TermInst down to its subject. So for

    fun twice<T> where { Monoid<T> } (x:T) { x + x }
    print twice(true)
    

    twice is lowered with three parameters (x, +, zero), and the call passes one. Emitting the C code then failed with arity mismatch calling twice.s4_4: declared 3, called with 1. Calls from recursive ... where (#1291) and recfun ... where (#1298) have the same shape.

    Also, since #1310 (WellFounded measures), lowering skips ConceptDecl and ModelDecl (the standard library now has models of WellFounded), so models' operations aren't emitted yet either.

    Until this issue is done, #1306 makes lowering stop at any TermInst with dictionaries, with compiler does not yet pass the operations of a where clause, in the use of twice (issue #1292). test/unit/test_compile_where.py pins it for a fun and a recfun.

    What this issue needs for where functions:

    • In lower_term/lower_call, lower each of TermInst.dicts and append it to the call's arguments, in the order where_params gives the parameters. A where function used as a value, not called, needs a closure over its dictionaries.
    • Emit each model's operations under their hidden names, as the plan says for ModelDecl, so the dictionaries have something to name. Then remove the CompileError and turn the unit test into an end-to-end one that prints true.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions