C4 linearization algorithm and helpers #1467

fare · 2026-06-16T15:26:16Z

fare commented

2026-06-16 15:26:16 +00:00

The C4 linearization algorithm, updated:

C3 linearization (which we were already using)
support for "suffix" vs "infix" specifications (i.e. struct vs classes, which we had of late)
Better O(dn) instead of O(d²n²) asymptotic performance
Support for the local order being an arbitrary partial order, not necessarily total.
Helpers:

move the old v0.18 std/misc/hash to std/hash/misc (instead of std/hash) and std/hash-tables becomes std/hash/types
implement a new with-id, in between the old with-id (of std/sugar) and the new with-identifiers

The C4 linearization algorithm, updated: C3 linearization (which we were already using) support for "suffix" vs "infix" specifications (i.e. struct vs classes, which we had of late) Better O(dn) instead of O(d²n²) asymptotic performance Support for the local order being an arbitrary partial order, not necessarily total. Helpers: move the old v0.18 std/misc/hash to std/hash/misc (instead of std/hash) and std/hash-tables becomes std/hash/types implement a new with-id, in between the old with-id (of std/sugar) and the new with-identifiers

fare added 11 commits

2026-06-16 15:26:16 +00:00

Small improvements to C4 documentation defb8e17e2

Update C4 to be O(dn) instead of O(d²n²) 9e02672c87

Update C4 to accept DAGs local order. Docs. ee28fc3529

Yet more comment tweaks for C3 4c52fd988a

C4: support eq: free-identifier=? from core/contract 817d7650ea

Tweak Makefile, build.sh 3104ba3cba

Restore std/values 39ff4a980d

Tweak bootstrap documentation & Makefile 012c8ad40c

Improvements to hashes and more ba48a1a970

Hash changes in runtime, and with-id 8bd2c4e3bb

Fix and start to test with-id 9c03c8d218

fare commented

2026-06-16 15:26:31 +00:00

(Reopening #1466, cleanly I hope.)

vyzo requested changes

2026-06-16 15:40:33 +00:00

Dismissed

vyzo left a comment

some fishy bug looking things

src/gerbil/core.ss Outdated

					
				@ -12,6 +12,7 @@ package: gerbil

				        "core/match"

				        "core/more-sugar"

				        "core/contract"

					"core/more-syntax-sugar"

no, this is the wrong phase.
can't import this here.

no, this is the wrong phase. can't import this here.

vyzo marked this conversation as resolved

src/gerbil/core/contract.ss Outdated

					
				@ -72,2 +72,3 @@

				                        struct: false

				                        eq: free-identifier=?))

				                        eq: free-identifier=?

				                        get-name: stx-e))

that looks like a bug, what exactly does get-name do?

you can't hash identifiers with their stx-e, it drops the context.

that looks like a bug, what exactly does `get-name` do? you can't hash identifiers with their `stx-e`, it drops the context.

get-name is there purely for the sake of error messages, so that in case of inconsistency in the class definitions, we print just the name of a class, not the potentially circular data structure associated to it.

No algorithmic decision is made based on the name. Equality is on the original value provided, in this case, the identifier itself.

get-name is there purely for the sake of error messages, so that in case of inconsistency in the class definitions, we print just the name of a class, not the potentially circular data structure associated to it. No algorithmic decision is made based on the name. Equality is on the original value provided, in this case, the identifier itself.

👍 1

vyzo marked this conversation as resolved

src/gerbil/core/contract.ss Outdated

					
				@ -876,2 +877,3 @@

				                              (!class-type-struct? (syntax-local-value klass-id)))

				                            eq: free-identifier=?))

				                            eq: free-identifier=?

				                            get-name: stx-e))

same here.

fare marked this conversation as resolved

src/gerbil/core/contract.ss Outdated

					
				@ -3243,2 +3245,3 @@

				                              (!class-type-struct? (syntax-local-value/context klass-id)))

				                            eq: free-identifier=?))

				                            eq: free-identifier=?

				                            get-name: stx-e))

and here

fare marked this conversation as resolved

src/gerbil/core/more-syntax-sugar.ss Outdated

					
				@ -9,6 +9,27 @@ package: gerbil/core

				        (phi: +1 "runtime" "expander" "sugar"))

				(export #t)

				(begin-syntax

seems like you want those in a nested module?
maybe that's why you had to import more-syntax-sugar at runtime.

seems like you want those in a nested module? maybe that's why you had to import more-syntax-sugar at runtime.

and import both at runtime and for-syntax here, not in core

I moved those things to more-sugar where I now believe they belong.

that s not a good place either. these things need to not be present at base runtime or else everytime you compile a binary you pull the expander... fail.

vyzo marked this conversation as resolved

src/gerbil/core/more-syntax-sugar.ss Outdated

					
				@ -48,0 +73,4 @@

					    (stx-map

					     (lambda (clause)

					       (syntax-case clause (quote unquote quasiquote)

						 ((fresh-id (quote local-id))

untabify

fare marked this conversation as resolved

src/gerbil/core/runtime.ss Outdated

					
				@ -1169,6 +1169,7 @@ package: gerbil/core

				    system-version-string

				    table->list

				    table-copy

				    table-new ;; TODO: BOOTSTRAP

remove TODO

fare marked this conversation as resolved

src/gerbil/core/runtime.ss Outdated

					
				@ -1821,6 +1822,7 @@ package: gerbil/core

				    hash-keys

				    hash-values

				    hash-copy

				    hash-new ;; TODO: BOOTSTRAP

remove TODO

fare marked this conversation as resolved

src/gerbil/runtime/hash.ss Outdated

					
				@ -29,6 +29,7 @@ namespace: #f

				  (delete! key) => :void

				  (for-each (proc : :procedure)) => :void

				  (copy) => @HashTable

				  (new (size-hint :? :fixnum := #f)) => @HashTable ;; TODO: BOOTSTRAP

remove TODO

fare marked this conversation as resolved

src/gerbil/runtime/hash.ss Outdated

					
				@ -616,6 +627,9 @@ namespace: #f

				  => HashTable

				  (h.copy))

				(defhash-method (hash-new h) => HashTable (h.new)) ;; TODO: BOOTSTRAP

remove TODO comment

fare marked this conversation as resolved

src/gerbil/runtime/hash.ss Outdated

					
				@ -617,2 +628,4 @@

				  (h.copy))

				(defhash-method (hash-new h) => HashTable (h.new)) ;; TODO: BOOTSTRAP

				;;(defhash-method (hash-new h) => HashTable (void)) ;; TODO: BOOTSTRAP

and this?

fare marked this conversation as resolved

src/gerbil/test/sugar-test.ss Outdated

					
				@ -0,0 +5,4 @@

				(export sugar-test)

				(import

				  "../core/more-syntax-sugar"

import this by its canonical path?

fare marked this conversation as resolved

src/std/serde/deserialize.ss

					
				@ -6,3 +6,3 @@

					:std/hash-table

					:std/hash/types

					:std/io/interface

				        :std/io/bio/api

fix this indent while at it

fare marked this conversation as resolved

fare force-pushed v0.19-c4 from 9c03c8d218 to 2b97aede81

2026-06-16 17:31:44 +00:00

Compare

fare force-pushed v0.19-c4 from 2b97aede81 to 53e2170d85

2026-06-16 19:07:52 +00:00

Compare

vyzo requested changes

2026-06-17 10:18:53 +00:00

Dismissed

vyzo left a comment

no, these utils are syntax specific.

src/gerbil/core/more-sugar.ss Outdated

					
				@ -39,1 +39,3 @@

				       #'(%#set! id expr)))))

				       #'(%#set! id expr))))

				  (def (stx-re-source stx src)

no. these do not belong to a runtime module.

vyzo marked this conversation as resolved

vyzo requested changes

2026-06-17 11:07:31 +00:00

Dismissed

vyzo left a comment

almost ready, a couple of erroneous stx-e usages where it should by syntax-e

src/gerbil/core.ss Outdated

					
				@ -31,6 +31,7 @@ package: gerbil

				                  "core/mop"

				                  "core/match"

				                  "core/more-sugar"

				                  "core/more-syntax-sugar"

why is this here? it doesn't import it at runtime.

fare marked this conversation as resolved

src/gerbil/core/more-sugar.ss Outdated

					
				@ -40,0 +53,4 @@

				         ((stx-pair? stx)

				          (stx-re-source (cons (recur (stx-car stx)) (recur (stx-cdr stx))) stx))

				         ((stx-vector? stx)

				          (stx-re-source (vector-map recur (stx-e stx)) stx))

syntax-e

fare marked this conversation as resolved

src/gerbil/core/more-sugar.ss Outdated

					
				@ -40,0 +55,4 @@

				         ((stx-vector? stx)

				          (stx-re-source (vector-map recur (stx-e stx)) stx))

				         ((stx-box? stx)

				          (stx-re-source (box (recur (unbox (stx-e stx)))) stx))