Abstract types are working, but it's clear that they're still not a definitive improvement over the previous system.

Specifically, it seems that terms that are obtained via unification are not always converted back to their abstract form because either operand is not recognized as an abstract term. Also, terms that are written directly in canonical form have the same issue.

Extending the abstract parsers to consider canonical forms is not guaranteed to work in scenarios where unification is the culprit, although it would solve some problems.

The previous system, and to a degree the current one, made extensive use of term unfolding, i.e. manually unwrapping the AST in order to reconstruct the abstract form. This is fine if it's guaranteed to happen once per term because terms are immutable, but there's currently no cache to keep track of these things and therefore it's a very expensive operation. Still, a cache feels like a band-aid. A better solution could be lurking in the shadows.

Also, some results of unification could be represented more efficiently than they currently are: for instance, sub-lists could be represented as slices of a parent list.

Waiting on #10

The idea here is to to define the predicate transformations required by some libraries, such as the one that will contain the tabling logic, within the libraries themselves.

This is similar to expansions, but it happens on the C# side.

All abstract terms can be represented canonically as a base term.

There should be an interface that allows defining new types in C# as long as a conversion to and from their canonical form is provided.
This interface would also expose the parser, which is currently not extensible, for the purposes of parsing the new type.

After this change is implemented, Dicts and possibly Lists should be rewritten to be abstract first class citizens.

Waiting on #27

https://www.metalevel.at/swiclpb.pdf

Trace mode is supposed to be of help during debugging, but as it is right now it merely complicates things further by printing walls of incomprehensible text.

It should also be interactive, like SWIPL's trace mode.

https://www.swi-prolog.org/pldoc/man?section=reexport

Modules are the individual Ergo code unit. A module exposes a list of public predicates that become available to all derived modules. A module might also reserve special semantics, such as in the case of attribute modules.

A library is a special type of module that is used to group together other modules under one package that is accessible to both C# and Ergo. Libraries are also the entry point for several engine extensions that only become available once the library is imported, thus providing a mechanism to implement the aforementioned semantics while limiting their scope.

Structure

A library is an ordinary Ergo module. From C#, a matching class is added to the interpreter (if defined). That class contains:

• A list of interpreter directives provided by that library
• A list of solver built-ins provided by that library
• An entry point for handling Ergo events

Term expansions exist first to support literal definitions, and then to support macros.

Literal definitions are simple, in that they associate two ground terms.

Macros are fundamentally represented as a predicate with an outbound variable that stores the expansion.
Thus, a term may unify with several macros, and a single macro may produce several expansions.

It follows that an expansion should create multiple choice points. The missing piece is how to bind the expansion variable to the actual expansion. The most logical choice is to define a directive expand/2 where the first argument is the predicate itself, and the second argument is the outbound variable.

Proposed Syntax

:- expand(
    (dict(_, Args)$Key :- 
        dict_key_value(dict(_, Args), Key, Outbound)),
    Outbound
).

Despite the simplicity with which Ergo can interface to C#, it would be nice to provide a default database-like API to handle persistent state idiomatically. This has become especially evident during the integration of Ergo with Fiero, the game I'm working on, where something as simple as incrementing an integer needs to be done rather inefficiently via dynamic predicates.

The Problem

Several engine components need to throw exceptions: the Lexer, the Parser, the Shell, the Interpreter and the Solver are first among them; but it shouldn't matter where the exception originates from.

Given the IAsyncEnumerable-based structure of the engine, catching and logging exceptions is not something you can hide from the user: any exception naturally bubbles up to the outermost scope, where it invariably stops the enumeration even when caught.

The current system consists of a random assortment of functions that will pipe any exception through a default ExceptionHandler that's defined at the ShellScope level.

Ideally, this handler should be defined at the lowest possible level, so that it can be reused painlessly up the stack, and so that any component in the stack should be able catch any exception that bubbles up to its own level.

It could also be defined at the highest possible level, so that there's no need to worry about passing it up the stack at all. This would require a buffering mechanism however, because you can't yield from within a try block.

NOTE: USE ExceptionDispatchInfo.Capture(ex)

The current knowledgebase can't be exported to disk from the shell, because the code that would do that is commented out and needs to be rewritten.

• Create abstract type Lambda that parses the forms {Free}/[List]>>Lambda and [List]>>Lambda.
• Create builtin that applies the lambda and forwards the arguments to call.
• Figure out if macro expansion is necessary, because it would be problematic since macros are to be implemented as lambdas.

While Ergo is expressed rather idiomatically in C#, it would be beneficial to study the WAM and to figure out what sorts of optimizations are available. This would extend to the task of compiling Ergo to IL.

https://www.swi-prolog.org/pldoc/man?section=operators

In SWI, operators are module-local and need to be exported/imported explicitly with module/2 and use_module/2, and possibly reexport/2.

Other implementations, like SICStus don't have local operators.

Are they worth implementing?

Reasoning

Given the scope of Ergo, they're not particularly important. But they would be nice to have as they would make it possible to explicitly avoid clashes.

In order to make it possible to write logically-sound expansions, they must preserve any variable that they affect. This includes variables found inside Complex terms.

Tail Call Optimization is being applied to predicates that are not determinate, causing a loss of solutions.

https://sicstus.sics.se/sicstus/docs/3.12.8/html/sicstus/Last-Clause-Determinacy-Detection.html
https://sicstus.sics.se/sicstus/docs/3.12.8/html/sicstus/What-is-Detected.html#What-is-Detected
https://www.mercurylang.org/information/doc-latest/mercury_ref/Determinism.html#Determinism-categories

This is required by #27.

For instance, the following code should be possible to define in any module, not just the user module:

user:message_hook(Term, Kind, Lines) :-
    format('Term: ~w~nKind: ~w~nLines: ~w~n~n',[Term,Kind,Lines]),
    print_message_lines(current_output,kind(Kind),Lines),
    nl.

The parser currently ignores this information and instead creates a predicate with head ':'(user, message_hook)(Term, Kind, Lines) in the current module

Waiting on #10

The Evaluations produced by built-ins are similar to the KBMatches produced by knowledge bases.

They are both IAsyncEnumerables that produce objects containing a SubstutionMap.

However the semantics are a bit different. Built-ins can return a different value than what was passed in, as opposed to pure predicates that always return true or false. For instance, math:eval(3.14) is effectively replaced by the result of the evaluation, 3.14.

As of now, built-ins are evaluated recursively. So, as long as the evaluation of a built-in is another built-in call, the evaluation will be performed immediately and the result will be passed on. But as it turns out, this isn't needed by anything. After all, built-ins are supposed to behave like regular predicates in most scenarios.

When eliminating this recursive resolution, it becomes evident that evaluations are pretty much the same thing as matches where the Lhs is mutable instead of immutable, and where the Rhs is a stubbed version of the built-in that simply returns true.

This makes defining operators involving certain problematic functors, such as ., impossible because they clash with some other symbol.

The fix requires undefining the punctuation symbol . and defining a well-known postfix operator '.'/1 with precedence 0, so that it correctly encloses statements.

Unfortunately, the current expression parser is incapable of parsing unary expressions in such a way because it only cares about precedence and associativity when parsing infix expressions.

Some queries that should run in constant space are creating GBs of unnecessary substitutions.

A simple example is: for(I, 0, 100000) which will probably crash the system with an OOM error before terminating.

My intuition is that these are generating "useless" substitutions that should be removed "as we go" instead of doing all the heavy lifting at the end.

AsyncEnumerables are very expensive. They were initially introduced for data sinks and sources, but seeing as those are a fringe feature that is not standard Prolog, they don't warrant a massive penalty to performance. Those will need to be implemented some other way, such as by blocking the calling thread.

Some results of unification could be represented more efficiently than they currently are: for instance, sub-lists could be represented as slices of a parent list.

I started working on some simple instrumentation for profiling and debugging. In the long run, it's imperative to tooling for:

• Interactive debugging
• Profiling of all engine functions
• Knowledge base visualization and manipulation
• Text editor integration (language server)

And, maybe, for:

• Automatic test generation?
• CI?

Long term issue for all parsing errors. There are currently no outstanding parsing errors to look at.

https://cliplab.org/~clip/Software/Ciao/ciao-1.15.0.html/dcg_doc.html

In Prolog, strings are represented as proper lists of characters. In Ergo, they are plain atoms, since those are represented internally as CLR strings. This solution is simple but incorrect, as predicates that are supposed to work on lists won't work on strings.

Strings could be implemented as abstract types on top of regular lists, with their own modified parser.

SWI-Prolog represents shared variables within Lambda expressions as a list enclosed by braces, denoted a "bracy list".

Ergo only supports regular lists at the moment. It would be useful to define new list types that differ only in the symbols used for parsing (opening token, separator, and closing token).

It would be great to define these new types as abstract first class citizens, so that their semantics can differ from those of regular lists.

Waiting on #4.

The shell is not a core component of Ergo by itself, but it's the one a developer would spend the most time on, before interfacing with Ergo directly from C#.

So it needs to be functional and modern. Theming is one concern, another is ease of use.

SWI-Prolog's shell isn't so amazing in that regard. Pasting snippets usually goes very awry, since there's not a dedicated "insert mode" such as Vim's. Asserting predicates is also a pain.

At the time of writing, expansions work fine but they do unnecessary work because they are called during the solving step.
Expansions should only happen when the solver is initialized and when a query is parsed.

Right now the head of predicates is expanded correctly at initialization time, but the body isn't. This is because some macros, such as :=/1, replace themselves with the result of their computation.

Either the macro semantics are limited such that predicate expansion is no longer a problem, or some corner cases need to be addressed:

• Expansions that happen inside complex terms in the body of a predicate need to be bound to an intermediate variable in a clause that is resolved right before the complex term.
  • Expansions that happen inside the head of a predicate don't benefit from this.
• Expansions that happen inside complex terms in the head of a predicate need to be bound to an intermediate variable in a clause that is resolved after any other clause in the predicate.

Sometimes the TryGet API feels more intuitive than the Maybe monad, partly because there are situations in which Map and Reduce don't work well, such as within a readonly struct.

On the contrary, the Maybe monad allows for easier composition. It has currently been extended to be a mix between the proper Maybe monad and the Option monad, to facilitate pattern matching in situations where Map and Reduce don't work.

The goal is to draw a boundary between the two cases in order to make the API more consistent, and possibly to restore the Maybe monad to its proper usage.

1. Create a CancellationTokenSource when Solve is called
2. Attach its token to the SolverScope
3. Check whether the cancellation for that token was requested instead of using a volatile bool

https://www.swi-prolog.org/pldoc/man?section=hooks

Hooks are Ergo predicates that will be called asynchronously by engine-internal C# code during the normal course of program execution. They give Ergo code the ability to have a say in how it's interpreted and, specifically, they provide a mechanism on top of which attributed variables can be built.

Hooks should be a general mechanism that can be plugged in whenever the engine wants to query a well-known, user-defined predicate.

The extension method Maybe<IAbstractTerm> IsAbstract<T>(this ITerm t) is sprinkled throughout the code in various places. Within, calls to the static AbstractTermCache are made. Despite the cache using concurrent collections, these still require a lock, sometimes, in order to work properly.

In any case, having a static AbstractTermCache seems like an issue. It should be part of the interpreter or the interpreter scope. What makes this refactoring non-trivial is that a reference to the cache needs to end up at all current call sites of IsAbstract, which can be ugly sometimes.

https://www.swi-prolog.org/pldoc/man?section=IO

Merging Ergo with Fiero has uncovered a serious refactoring urge: the Shell needs to be decoupled from the OS's standard streams.

All write and read predicates should be tweaked to work on streams and an equivalent to set_prolog_IO/3 should be introduced.

Implement Engines for stronger interop between Ergo and C#

https://www.swi-prolog.org/pldoc/man?section=thread-wait

https://www.swi-prolog.org/pldoc/man?section=threadcom

https://www.swi-prolog.org/pldoc/doc_for?object=thread_create_in_pool/4

This is before running a query.

And this is after. There are multiple identical instances of fibonacci/4 and others.

Waiting on #5.

The current solver architecture doesn't provide the flexibility of a virtual machine.
In particular, it makes it complicated to reason about choice points and stack frames, obstructing several optimization paths.

A blocking issue is that, with the current architecture, I can't find a way to implement last call optimization. The Solve() method is implemented as a pair of mutually recursive IAsyncEnumerables: one acting on queries and one acting on terms. It's reasonable to assume that the first method could be refactored away, leaving only the iteration constructs. At that point LCO is only a matter of reassigning some variables and issuing a goto.

There are more elegant solutions. The next logical step would be refactoring the mess of loops into a state machine. This is where we can introduce concepts such as the stack and the trail in a way that mirrors the WAM without mirroring its internals. After all, the WAM works on compiled Prolog while Ergo is still completely interpreted. This step should however lay the groundwork for what will eventually become the Ergo Abstract Machine, so it is very important.

https://www.swi-prolog.org/pldoc/man?section=module-autoload

Reasoning

Since Ergo has a narrow scope, autoloading comes with all the upsides and virtually no downsides. Faster startup and fewer predicates in memory at a time means better overall performance.