News

Please, visit the Patreon page for the details on the campaign. The code is hosted at sourcehut, and you can learn more about the immediate roadmap on the Wiki. The long term outline of goals is described in The Power of Structure.

I will be posting all the news, reports and announcements here, on this page, as well as on Patreon. There's the RSS feed too and a low-volume news mailing list, to subscribe send a message to:

~project-mage/news+subscribe@lists.sr.ht

For the development list, and a general discussions list, see:

https://lists.sr.ht/~project-mage

I am posting progress reports every month unless I have to be away from the project.

Progress Report #6, 30 November 2023

— Stage 1: Foundation.

Progress Meter:

—

Hi, all! A quite decent month of development behind.

— Multiple-Output Constraints

So, here's how multiple-output constraints turned out: 

(Ξ (r (Ξ (u (Ξ (y 5)))
         (v (Ξ (x 10)))
         (w (Ξ (x 15)))))
   (c (ζ () (is-a multi-out#)
         (filter
          (λ/ζ (and (schema-p value) (symbol-package slot))))
         (leaf-filter
          (λ/ζ (numberp value)))
         (leaf-ζ
          (λ/ζ (ζ ((out (>> slot))) (strength 100) (:= out 123))))
         (path
          '(r :* :*)))))

This says that all the schemas under r (namely: u, v, and w) will have all their slots that contain numbers be constrained to 123 at the strength of 100.

The path description may include any number of wildcards or specific slot names. The provided filters apply to all the wildcards, but a wildcard may specify its own filter via a property-list syntax: 

(path `(<...> (:* :filter ,(λ/ζ <...>)) <...>)

(Note: λ/ζ is not some special syntax, just a very simple shorthand macro that expands to a lambda taking a few relevant arguments.)

Previously I thought of these as "parameterized pointer variables" and that it would be necessary to change the internals of constraint handling, but it turned out that with a few additions and tweaks, the constraints as of now are already more than capable of constructing this behavior. That was a pretty cool revelation (if you will). In fact, a constraint like that can be written by the user.

There are some inefficiencies left in the implementation – many extraneous constraints are generated – but that will be fixed with a few more tweaks here and there.

There are also the "super wildcards" *** – these apply to the whole tree starting at the root and are not limited by depth.

Generally speaking, multiple-output constraints give a way to dynamically enforce some property / add some behavior to certain parts of a tree.

— Some Other Constraints

Some other new constraints allow making statements such as:

Sub-inheritance will very likely be used for context-handling in the future. And slot-name-collection provides a form of multi-input – not as general an approach as multi-output above, but should be plenty enough. General-purpose constraints such as these ones above and a few others will be supplied along with core KR, most certainly.

— Constraint Interface Changes

Previously, I said how constraints can now be inherited and named, and also how they can carry data via a custom sub slot (with a user-supplied inheritance function). Turns out this sucked and constraints need to carry a bunch of data to be useful, and access to this data is too damn painful through an indirection. So, named constraints now expand to defstruct definitions (while still resembling schema definitions). For instance: 

(ζ some-constraint# (out in)
  (some-value value) ; your data
  (fn (λ (x) ...)))  ; more data
  (:= out (with-slots (some-value fn ...) self
            (+ some-value (funcall fn in))))

So, as you can see, fn and some-value become a part of the standard constraint definition, and so can be accessed with the usual with-slots syntax (with-accessors is too damn painful and unnecessary for this, which I will be documenting as a convention of sorts). So, this is way more usable.

— Thread Safety

For KR to be used in multiple threads, it was necessary to make it thread-safe. The only non-thread-safe parts were the special variables. Thankfully, bordeaux-threads:make-thread takes :initial-bindings where thread-local bindings can be specified. Supplying all the special variables seems to do the trick, and running multiple threads with KR object manipulation now works without any issue.

— SDL2 Wrappers + Thoughts

I have updated the SDL2 wrappers for the latest version. A potential contributor got interested in rendering shapes, and things seem to be going well. I have previously been considering Pango for the backend, but he has also advised to look into freetype-gl. While less capable in terms of internationalized complex text layouts, and maybe not as popular as Pango, freetype-gl ought to be the fastest possible option for SDL2. It should also be capable enough to handle all of the use-cases I am thinking currently about. It's written in C – which brings me to the point that it might be sensible to package the backend with some C code in the future (emphasis: for the backend only, the core project is CL-only). This C part may be later rewritten in Lisp or it may stay as part of the backend – we will just have to see what works best.

— Next Steps

Things are shaping up. But there are still some steps left that are necessary to complete KR/Constraints.

For one, I have gathered a backlog of quality-of-life improvements: things concerning naming, conventions, useful functions, shorthand macros. The user-perspective stuff. Won't hurt to do some refactoring here and there. Some minor features. There's a bunch of TODOs all over the codebase. All of this needs addressing.

Also, it would be pretty good to have a value-based dispatch system. The available CLOS-driven dispatch systems work on types and subtypes. This doesn't cover the schema situation very well, as schemas are all of a single type: `schema'. Of course, value-testing is just of a more general nature overall. Advice is as well just nonexistent, as far as I can tell (:before and :after is not proper advice). The interface for removal, addition and inspection of methods is function-driven – when it should just be objects that you can view and modify instead, like data. So, the existing solutions just don't ring like good foundation. But I think there might be a possibility of cannibalizing some of them, such as specialized-function and polymorphic-functions. And cl-environments can provide custom declarations and information useful for inlining.

Of course, I will be writing the documentation too.

All of these things will likely take me the next 6-8 weeks to do. And then will come the definition of cells, with the rest of Fern not being that far away either. Quite exciting.

Progress Report #5, 27 October 2023

Progress Meter

—

August sucked progress-wise and so did most of September. Just like did all of the summer, really. There were a few reasons for the long break, but the facts are still the facts: not much progress in those 4 months or so.

In the future, I will try not to raise people's hopes for quick short-term progress, it will probably be best I only show something once actually done or right in the works.

In any case, I have been back to working on the project over this past month, and there's some decent news:

Instead of doing 

(Ξ (:init-options '(:inheritance :static
                    :ht-args (:test #'equalp)))
   (a 10))

now one would do this instead: 

(Ξ (test #'equalp)
   (inheritance :static)
   (a 10))

The new approach manages to do more work at compile time, and is quite simpler than before, both in implementation and in usage.

Constraints being schemas worked, but after some thinking, I figured there won't be that much practical benefit to that approach after all. I thought that was unavoidable for ergonomics, but I don't think that anymore. As long as constraints (1) can be schema-like and (2) provide a way of customization, things should be quite fine. The former is now accomplished via struct-slot access over the typical schema read/write operations. The solution to the latter was simply to allow storing a custom object within a constraint and allow inheritance for it (simply via a user-supplied function).

What's good about the new approach is that it doesn't incur additional costs – those were around 25% both in terms of creation speed and memory consumption. And while that may be not that much, what the hell, right? Constraints are used for inheritance, which means there's a constraint for every slot in an object, so that was implying a certain tangible cost for every object created with a dynamic inheritance option. Not an entirely pressing cost, but still.

But the more general motivation behind the initial work was to allow any struct to derive from `schema', at first only get initialized minimially, and then, if necessary, upgrade to a full schema status at runtime. This yields a kind of object that becomes powerful on demand (either at creation or at runtime). And while I still feel it's an interesting idea, it would perhaps make most sense for a rather more general-purpose object system. And I don't feel like the current foundations I am using allow for accomplishing that in a good way.

And so I rolled that stuff back, "until further notice".

Oh, well, the new constraints can be named and may be inherited with an option to redefine the path of any input/output variable. For example, the following constraint keeps a history of a given slot value (here in the 'in slot) by writing to the ring-buffer contained in the 'out slot, via mutation: 

(ζ history# (in out)
   (:= out (rb/add out in) out)) ; rb refers to a ring-buffer

Now, to derive the constraint for a custom slot, one need only redefine the paths (in, out or both): 

(ζ ((in (>> 'x))
    (out (>> 'x-history)))
   (is-a history#))

Partial path redefinition is possible just as well, of course. And storing custom information is done via a 'sub slot: 

(ζ () (sub (make-some-custom-data ...)) ...)

So, this here probably is as complicated as it needs to be.

I think I have a pretty good idea of what they are going to work out like in the end. 

(ζ (Q (>> * 'q)))

Here (>> * 'q) is a path, * is a wild card, 'q is a slot of every schema that matches the wild card in the current object.

One will then be able to define a method that uses Q in one of the following ways: 

(:= Q (+ p 2)) ; define the 'q slot of every matching schema to equal (+ p 2)
(:= p (apply #'+ (all Q))) ; other direction: define p as a function of the Q set
(:= P (+ Q 2)) ; one-to-one match, where both P and Q use wildcards; maybe

The wildcard matching will have a filtering and recursion depth option. Multiple wild cards will be allowed to appear in a single path.

PS The long break did have some benefits. For one, it let me take a fresh look at KR, I guess. But generally I just want to thank people who are supporting me for sticking it through with the project over the few stale months : )

Yours,

– DK

Progress Report #4, 03 August 2023

Progress Meter

—

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:

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

—

A quite solid month, the major changes can be summarized as:

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:

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

—

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:

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 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 ---

— 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:

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 ---

—

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:

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.

...proudly created, delivered and presented to you by: some-mthfka. Mthfka!