News
Please, visit the Patreon page for the details on the campaign. The code is hosted on sourcehut, you can read about it on the Wiki.
I will be posting all the news and any reports here, on this page, as well as on Patreon. You can track any meaningful addition to this website (new articles (if any), news, and reports) via the RSS feed. To subscribe to a low-volume announcement list, send a message to:
~project-mage/news+subscribe@lists.sr.ht
I will be posting progress reports every month, around the 23rd.
Progress Report #4, 03 August 2023
Progress Meter
- [WIP] Knowledge-Representation Improvements
[X]
Better syntax, cleaner API & refactoring- [~] Meta info in slots
[ ]
Advice[X]
Change predicates[ ]
Multi-Methods (value-based)
- [WIP] Constraint Management Improvements
[X]
Better syntax & some refactoring- [~] Parameterized pointer variables
[X]
Advice (for constraints)[X]
Store constraints as KR objects[ ]
Async execution
- 2D Graphics
[ ]
Linear Algebra and Geometry additions[ ]
2D API for geometry + Backend (via SDL)[ ]
Event objects + Backend (via SDL)[ ]
Text API + Backend (via Pango)
[ ]
Cells[ ]
Configurations[ ]
Some demo (after everything else)
—
Aaaand I am back. My apologies for the delays on reporting, I really meant to be doing these regularly. A few things came up and I have just had a couple of unexpectedly busy months, and couldn't attend to the project properly. Most of what I am reporting here dates back to May for the most part.
In any case, I am getting back up to speed now. And here are the changes since the previous report:
- Constraint loop resolution.
- Static inheritance.
- Schema struct access semantics.
- Schema-like constraints.
- Constraint advice.
- Basic change predicates.
First of all, it turns out that the authors of SkyBlue (the constraint engine) have coded in the ability to write custom solvers for cyclical constraints. This is quite fortunate since a constraint such as the following one
;; A constraint for a few properties of a rectangle ;; (Like Ξ is used for schemas, ζ is used for constraints.) (ζ (left right width) (:= left (- right width)) (:= right (+ left width)) (:= width (- right left)))
has so far been treated by SkyBlue not really as a cycle, but just as a multi-way relation, where if a single variable were to change (say, width), then only a single other definition would be enforced (depending on the order of definition, left in this case). This approach is sufficient enough for many cases, but it's usefulness is limited to only three variables. And there's an even bigger problem in the hiding: the engine is only able to enforce a single output variable, whichever one runs last. Undesirable behavior ensues if you impose additional constraints on any one of these variables.
Now with the cyclical resolution set up, it is possible to rewrite this single constraint as an actual cycle using three distinct constraints, one for each variable. The strengths of these constraints identify the priorities, and all the variables stay enforced. It's not a problem anymore to have more than three variables in a loop or to introduce additional constraints. As a sidenote: indeed, for the particular example above, three separate constraints will look a bit ugly for what really is just an algebraic equation. And so, in the future, custom cycle solvers might be used to implement linear equation solvers (and therefore allow concise notation for such relationship) - to that end, the original authors have even provided a few stubs. This would mean an ability for the user to add actual algebraic constraints – either through equalities or inequalities. This possibility will be worth exploring further at some point, and that could be useful for UI layout programming.
Moving onto the next point, one of the goals was to add schema-like constraint definitions. In fact, constraints are now schemas themselves.
(ζ a-is-b-plus-1 (a b) ; name and inputs (strength 5) ; slots (:= a (1+ b))) ; the constraint statement
Constraints can now be named, be derived from each other in a parameterized manner, may carry additional information about themselves, and all the while the syntax is nothing but familiar and schema-like (both for modification and creation). The access and write operators require no special checks or conditions and so there's no performance penalty.
However, this arrangement has initially proven to be an expensive affair: a schema contains hash tables, and CL hash tables happen to be quite slow to create. Now, since constraints are used as the primary mechanism for inheriting slots between objects, an ensuing cost would simply be unacceptable, since each slot would have to be associated with a constraint (and its hash tables) for every derived object.
To resolve the matter, the schemas may now be created as "lightweight": these omit hash-table creation altogether, and instead exclusively expose the slots of the structure object itself. In other words, if a struct (deriving from schema) has all the slots necessary for the object's operation, then there's no need to be creating any hash-tables at all. The interface to these struct slots is the same as to the hash-table slots. These struct slots however can't be used with constraints (not now anyway), but this limitation seems to be irrelevant for the actual use cases involved.
To further minimize the performance impact of treating constraints as schemas, schemas now also provide an option of static inheritance in addition to the default dynamic kind, for the cases where speed is more important than keeping child-parent slots dynamically coherent. This is most useful when an object is not meant to be mutated, and most constraints (by sheer numbers) seem to fall into that category.
So, essentially, constraint objects can still be lightweight even now that they have acquired schema-like interface and capabilities. Still, though, it's optional to make any particular instance have all the regular dynamic properties such as dynamic slot creation or dynamic inheritance, were the user to wish that.
The finer details of this are still being fleshed out, but it's pretty much a done deal. Though, perhaps, it will also be worth the effort to eliminate the hash-table creation overhead altogether for any schema: simply by introducing a pool of empty hash-tables (but this is yet to be tested).
Moving on, the change predicates prevent recomputation. These matter only for the → (write) operator: when a value is written to a slot and is equivalent to a value already stored in the slot, then no constraints will be triggered. This equality-checking is assumed to be eql, but may now be specified by the user.
—
I will begin working on parameterized pointer variables shortly, after which I will do either async execution or value-based multi-methods. So, that's the plan for the next 3-4 weeks. And once all these are done, and before getting into 2D graphics, I will document KR & constraints & their implementation properly and accessibly.
A Note on Progress, 24 June 2023
Hi, all! I haven't published the progress report last month, my apologies to those watching closely. I had to get away for a few weeks and could do very little programming in the meantime. But, anyway, I think I am getting back up to speed now, will publish a full report in the coming week. Thank you.
Progress Report #3, 24 April 2023
Progress Meter
- [WIP] Knowledge-Representation Improvements
[X]
Better syntax, cleaner API & refactoring- [~] Meta info in slots
- Advice
- Multi-Methods (value-based)
- [WIP] Constraint Management Improvements
[X]
Better syntax & some refactoring- Parameterized pointer variables
- Advice (for constraints)
- Store constraints as KR objects
- Async execution
- Change predicates
- 2D Graphics
- Linear Algebra and Geometry additions
- 2D API for geometry + Backend (via SDL)
- Event objects + Backend (via SDL)
- Text API + Backend (via Pango)
- Cells
- Configurations
- Some demo (after everything else)
—
A quite solid month, the major changes can be summarized as:
- Some essential solver data structures have been replaced/refactored.
- The inheritance model has been fully rewritten and is now based on constraints.
First of all, the Sky-Blue solver was using a couple of poorly-implemented data structures, among a few other things. All these had to be attended to. As a result, by some basic benchmarks, the speed has improved 2-2.5x overall.
I have also decided to disallow conflicting strengths for constraints that write to the same variable. Allowing these would mean relying on the order of addition, and therefore execution, and that's something that could be hard to reason about. It seems it best to just require the code authors to define a clear ordering of things before any bugs creep in. And constraint strengths as such are now simply integers, not a limited set of ordered keywords.
Second, it appeared to me that the way I did inheritance, while being bug-free otherwise, would be hard to make work well with constrained slots. In particular, the order of execution and recomputation would be a bit tricky to control, i.e. when you change some slot in the parent schema and the value has to propagate to the children.
Now, it seems obvious in retrospect, but modeling inheritance via the constraints themselves is a much simpler and more consistent solution. The way it works is basically such that a slot in the child is constrained to be equal to that slot in the parent. Assigning the appropriate strengths to these connections preserves the hierarchy in case of multiple inheritance, routinely takes care of the ordering and the value updates.
The new model pretty much has all the necessary features already, it's fully dynamic, potentially extensible, and the user can both inspect and remove/filter any particular connections (and in the future: advice them too, since they are just regular constraints).
It took a bit of preparation, but the resulting code for all of inheritance is now contained, rather simple and is only ~130LOC. And while that's pretty good, I have a feeling this just might be reduced in the future if it makes use of parameterized pointer variables (e.g. constraints that map to multiple slots, a yet-to-be-implemented feature). In fact, I think the new inheritance solution just might guide that work quite soon.
So at this point it's not so much some frigid concept of inheritance in its usual sense as much as simply a case of hierarchical data consistency management. And, it seems to me, that's exactly what it ought to be. Quite importantly, as a result, there's now no need for any coupling with the internals of the constraint-integration code, as was necessary with the previous approach.
—
The next steps are to restore/revise the relevant tests, but that won't take long. Otherwise, the foundation now seems quite ripe for the next immediate targets:
- parameterized pointer variables;
- constraints as KR objects, with some form of schema-like access semantics.
The former of these should yield a quite powerful and indispensable tool for dealing with multitudes of slots.
The latter objective should result in a consistent interface for deriving/cloning/modifying the constraints.
Progress Report #2, 23 March 2023
Progress Meter
- [WIP] Knowledge-Representation Improvements
- [DONE] Better syntax, cleaner API & refactoring
- [WIP] Meta info in slots
- Advice
- Multi-Methods (value-based)
- Constraint Management Improvements
- [DONE] Better syntax & some refactoring
- Parameterized pointer variables
- Advice (for constraints)
- Store constraints as KR objects
- Async execution
- Change predicates
- 2D Graphics
- Linear Algebra and Geometry additions
- 2D API for geometry + Backend (via SDL)
- Event objects + Backend (via SDL)
- Text API + Backend (via Pango)
- Cells
- Configurations
- Some demo (after everything else)
—
TLDR This month was kind of slow, but I have reintegrated the new KR code with the multi-garnet layer, so now the constraints function again (and all the tests pass). I have also been adding some meta-slots, and that's about half-way done.
I have also refactored the multi-garnet layer somewhat (mostly throwing out the compatability layer for the old formulas), but there are a few not-so-reassuring things left, like the usage of property lists for tracking slots, instead of just using hash tables, so I will be looking into that too quite soon.
Some syntactic improvements were made to the constraints macros as well, but I won't go over these just yet: these are still likely to change.
—
In the previous report I mentioned that FSET could be a viable option as a container for schemas: it's functional, so you could safely expose it to the world as just another slot, and the user could use it for, say, traversal, just as a hash map. Access an object as a data structure type of deal. However, some quick tests have shown that FSET is 29 times slower on writes with 14 times the memory consumption compared to the standard hash tables. Worse, it's also 22 times slower on reads. I still think that exposing a container is a good idea, so I am just going to be using standard hash tables instead (as I am doing already, for the most part). The worst that can happen is the user bypasses the constraint mechanism if he writes to the hash table directly. But that's going to be possible to do anyway, so it's not a problem.
Speaking of hash-tables, hash-table-args
is a slot that can be supplied by the user at object-creation time in order to create a customized hash-table. For now, only the :test
argument is supported, and the standard hash-tables only support eq
, eql
, equal
and equalp
for tests. These should probably cover most cases, though (and if not, this could be extended, I think). The use of this is straightforward: now you can use, say, lists for keys, and not just symbols.
In fact, it seems like letting the user use any kind of object as a key is a rather sane thing to do. Previously, I was planning on restricting the use of keywords to KR-only purposes (like :is-a
), but maybe this isn't all too reasonable. So, keywords are too going to be allowed as keys to the user, and is-a
along with the rest of the kr-supplied slots will be just regular symbols.
Speaking of meta-slots, the breakdown for these is as follows, more or less:
[X]
name, prefix[X]
hash-table-args[X]
last-added, last-removed, last-updated, last-action[ ]
container, slot-via, slot-parent- [~] on-write
[ ]
types[X]
docs[ ]
local-only[ ]
create-on-write[ ]
advice[X]
equality- [?] drop, take, filter
I will be documenting these eventually, of course, but these slots (along with some hidden constraints) will form the basic interface to any given schema.
To get an idea of how this is going to work, let's document some slot:
(Ξ s) (→ s 'some-slot 42) (→ s 'docs (Ξ)) (→ s 'docs 'some-slot "This slot contains the answer ...")
The third line assigns a schema where all the docstrings will be held. Then the docstring for a slot is assigned. This is roughly equivalent to doing this at object-creation time:
(Ξ s (some-slot 42) (docs (Ξ (some-slot "This slot contains the answer ...")))
One tricky thing here is to keep the inheritence relations intact. So, if s
were to inherit from q
, we would want the docs
in s
to inherit from docs
in q
. This will be accomplished quite simply by setting up a constraint on the is-a
slot of the docs
to be computed from all the schemas in the is-a
of s. And the same thing can be done for any nested schemas. However, it appears that parameterized pointer variables will be best suited for this, and so this will have to wait just a bit.
Also, with create-on-write
, it won't be necessary to create the docs
schema manually, as it will simply be created when written to.
name
and prefix
are for printing/debugging purposes.
container
, slot-via
, slot-parent
will expose the container and some useful slot properties.
advice
is advice for functions called via ↑
.
local-only
will list slots that don't have to be inherited.
types
will describe slot types for type checking and, later on, for supplying type info to the compiler.
equality
specifies a function for a slot to allow early exit if a new value is equal to the old on assignment
drop
, take
, filter
: these I am still thinking about. Would allow dropping/taking certain slots for inheritence, but on the other hand they kind of break the meaning of is-a relationships. But so does local-only, to a degree, if it shadows an inherited value. This could be taken care of, but maybe there's no big need for these to begin with. We will see.
last-added
, last-removed
, last-updated
, last-action
refer to slots and allow meta usage if you constraint them as inputs. For instance, with these, you could keep track of all slots in a schema that have a certain type or that have a certain property. This will be very useful for API-building.
Further Thoughts
- I have run some brute benchmarks, and it seems that writing to a slot which is a constraint input is ~14x slower than writing to a non-constrained slot. Writing to the root input of a chain of constraints is only about ~6x slower (averaged). 1250 writes can be done to 10-variable-deep chains per frame (1/60th of a second). This doesn't sound too bad, but like I mentioned in the beginning, there's some shady-looking code in multi-garnet, so it looks like this can be made faster. Who knows, maybe even much faster, but I have a quite incomplete picture of the constraint engine and even the code responsible for the integration, so I can't judge fully. This should be worth looking into, on general principle.
- For optimization purposes, such as when specifying slot types or doing value-based dispatch, it appears that CL-ENVIRONMENTS might be just the library to use. It even allows defining custom declarations. All it asks is to use its CL package. A fair trade, I think.
- I wonder if the interface to defining value-based dispatch methods could be done simply via the schematic interface. It appears possible and quite sane, if a little peculiar, and would eliminate the need to produce an extra batch of APIs just for dealing with these methods (e.g. removal, advice, etc).
- I was told about TeXmacs (in the context of scientific usage) - a pretty cool WYSIWYG editor for document typesetting, with some structural philosophy to it. For those of you who are interested in my thoughts on this, see this section.
—
I was probably a bit overly enthusiastic for my last estimate about starting to work on graphics in May. This KR/Constraint business will easily spill into June. Fine by me.
Progress Report #1, 23 February 2023
Hi, everyone!
So, the first month of development is already behind, and it started out well!
— Progress Meter ---
- [WIP] Knowledge-Representation Improvements
- [DONE] Better syntax, cleaner API & refactoring
- Meta info in slots
- Advice
- Multi-Methods (value-based)
- Constraint Management Improvements
- Better Syntax
- Parameterized pointer variables
- Advice (for constraints)
- Store constraints as KR objects
- Async execution
- Change predicates
- 2D Graphics
- Linear Algebra and Geometry additions
- 2D API for geometry + Backend (via SDL)
- Event objects + Backend (via SDL)
- Text API + Backend (via Pango)
- Cells
- Configurations
- Some demo (after everything else)
— What has been done ---
First and foremost, I have set up a Wiki which acts both as interim documentation and as a learning resource.
Next, I have refactored the core Knowledge-Representation code. It wasn't pretty and had many questionable decisions. So many, in fact, that after throwing most of them away, I was left with a meager ~800 lines of core functionality. This also turned out to be not only buggy, but a bit weird in that it was using both a push and a pull model for the sake of memory preservation. This is not necessary now, and I doubt it was necessary back when it was written. I have rewritten all this, yielding only ~400 lines of code due to a slightly simplified model and a more straightforward approach. All the tests run fine, so that's good.
The API got a much-needed simplification as well. Now it boils down to just these few operations:
Ξ, ←, ↓, ↑, →, ↓↓
The breakdown is as follows:
- Ξ creates a schema: (Ξ name (first "John") (last "Doe"))
- ← gets a value: (← name 'first)
- ↓ destroys a slot
- → sets a value: (→ name 'last "McCarthy")
- ↑ calls a function held in the slot, passing the object as the first argument
- ↓↓ destroys the schema
There's a bit more to it than that for getting or setting a value, though. For instance, one might want to just get the local value (as opposed to a possibly inherited one); or write without automatically updating the inherited values (for performance). This requires some further syntax. For getting a local value, this is done like this:
(← name (local 'first))
So, local
here is just a macro which spits out an expanded slot declaration:
(← name (:key 'first :local t))
These declarations may get combined and they seem to provide a pretty straightforward interface without any need to create an abundance of specialized get/set functions.
Besides these simple functions and macros, there will likely be just some mapping constructs exported for walking the inheritence hierarchy. So, overall, it's looking pretty minimal so far (of course, this is just for the KR itself, there's also the constraints-related stuff (which is also pretty minimal)).
As for the use of non-ASCII symbols: typing these isn't really a problem, and they really make the code look better and much more compact.
— The immediate plans and further thoughts ---
- Within a few days, I will reintegrate the new code with the constraints engine (which was thankfully written by different people and is of much higher quality than the KR core it was built for).
The core KR API is minimal, but there are no aggregate operations available for these objects. But they are just maps! Not good. The solution I am set for right now is to expose the container directly to the user: just via a
:container
slot.This one has to be functional, and, so, fset will be used. So, I am pretty much offloading the work of providing the bulk operations on maps to fset (a well-tested and well-known functional library).So, if you want to walk all the slots, you just take:container
and walk through it however you prefer.Or if you want to take an intersection, you call fset:map-intersection on the containers of the schemas in question, and you are done.Writing to
:container
can also have semantics, and this is yet to be thought out.The interface for type information, read-only slots, etc will be universal: these will simply be schema slots in the schema itself. So, to set the type of a slot, you would just do:
(→ name :slot-type 'first 'cl:string)
where
:slot-type
is just another schema.This is very neat because you can just reuse the KR interface for doing all kinds of things. Advice will be done the same way.
- Declaring a type for a slot and then getting or setting a value can emit type information dynamically into the compiled code when the object is available. So, the type info can actually be used for optimization.
- I have seperated the goal of Configurations from KR. I figured that configurations don't require any special kind of inheritience if you structure your program the right way, which shouldn't be a problem.
- I decided not to proceed with generalized selectors (which would allow custom containers instead of just hash tables). In principle, this is cool to think about, but so far everything this could give can be done by the standard means anyway. So, unless I encounter a really good use case for this, I will deem it an unnecessary feature.
- There's a new item on the list: "Store constraints as KR objects". The problem with the constraints right now is that they are local to the object and inheritence doesn't work on them. If they were represented as KR objects, then these objects, when created, could inherit from the parent slot. It's the same kind of inheritence which will be used for contexts. Moreover, this paves a natural way to add advice to the constraint methods.
- I have made a decision to disallow keywords as slot names for the user code. This just wouldn't be good. Keywords will only be used for core KR needs (and, potentially, for its extensions).
The standard generic methods won't do. And even though named schemas could declare namesake types, and type-based dispatch is also possible (via something like this library), it won't do either. If we learn from Clojure's multimethods, there's a more practical notion of a dispatch function which examines the actual values to help determine what methods to run. The overall rationale behind that is pretty solid: value-based dispatch is just more meaningful than types (Rich Hickey gives an interesting talk on this here).
However, I won't just copy the multi-method interface like from Clojure. I think it could be more transparent, especially for inspection, and the prefer-method deal is kind of strange-looking. There's also no advice. I have a hunch of how to do this: by representing the multi-method as a decision tree (built with KR). It can then be exposed to the user for direct inspection and modification. This would easily yield an advice interface and expose the ordering (via a
slot-order
slot). So, this is just exposing the building block, not simply the API.Further on, such dispatch could later be extended to the methods used in constraints (and I would like to think without much fuss).
All this, in fact, could actually yield decent performance, especially with declarations. In certain cases, probably better than CLOS, and within declarations that allow inlining, certainly better than standard CLOS. We shall see, of course.
So, I will be rolling my own for this. The whole MetaObject Protocol arcana is just not very elegant. (And it would yield 0 benefits anyway.)
- Added a goal: build a demo, when all the features are ready. It won't have much to do with structural text editing, will just be some small application showcasing all the facets of Fern. Will be done when everything else is, of course.
—
I estimate it will take about a month to sort through the rest of the KR stuff, to add the necessary features. Then, probably, another month or so for the constraint management improvements. (Just eyeballing this now, and assuming the constraint engine won't give me trouble.) So, it wouldn't be bad to start working on some actual graphics some time in May, if everything goes well.
If anyone has comments or questions, just start a thread on the dicussions or dev list here or contact me directly.
Announcement #1, 23 January 2023
Hi, everyone! Good news!
I haven't reached the funding goals, but that's OK! Already, with the support of my patrons (thank you!), I think I will be able to work on Mage something close to full-time for all of 2023 (at least).
The plan for this year is pretty simple: bring Fern up to speed. It's going to be a GUI toolkit. In a few ways, it's rather simple, but in others, it's quite powerful. The foundation has been established, in most part thanks to the Garnet and the Multi-Garnet projects from many years back.
That foundation does need to see some improvements. I have described the reasoning for them in the Fern section on the website. The gist of it comes down to:
- Knowledge-Represention improvements
- Better syntax. (This will be done ASAP.)
- Meta info accessible via a slot.
- Generalized selectors.
- Configurations.
- Contexts.
- Constraint management improvements
- Better syntax. (This will also be done ASAP.)
- Advice for constraints (this is yet to be designed carefully).
- Change predicates (just an optimization, for what it's worth).
- Parameterized pointer variables via generalized selectors.
- Asynchronous execution.
- Slot change hooks.
- 2D Graphics
- Some additions to the geometry and linear algebra modules.
- A simple 2D API for geometry + backend (via SDL).
- Event objects + backend (via SDL).
- A simple text API + backend (via Pango).
- Cells
So, this is the rough outline of the work to be done.
Once Fern is ready, it should be possible to start working on the editor specification and some actual editors: Rune and Kraken. But that's unlikely to happen until next year.
So, I will probably spend the next few days setting up my environment, and then populating the Wiki of the project. Then I will switch to programming.
Also, some people have shown interest in the code. Please, if you are learning about Fern or even want to be implementing something, do communicate with me! It's important to be on the same page. In the next few days, I will be populating the Wiki with some development notes for anyone interested in learning about the code, as well as talk about the future course of development. Just for now, the best place to learn about the code is still the Code page.
The development will be taking place on Sourcehut, here. I found Sourcehut to be geared for the efficient workflow over mail, and yet it seems to have a decent web interface.
I hope to make the best of it. So, again, thank you all!
P.S. I will write news and updates on the development about once a month. I will publish them here and on Patreon. I have also set up a mailing list where these messages will be duplicated. To subscribe, just send a message to
~project-mage/news+subscribe@lists.sr.ht
There are other mailing lists as well, for develepment and general discussions. And, in general, if anyone has any concerns or suggestions, feel free to contact me.