There is currently no way to check the type of an expression. It should be possible to build a type checking pattern, allowing a variable only to be bound if the value is of a certain type. The most important part here is to be able to match "any number" or "any string", where we currently can only match specific numbers/strings, or just have to match anything.

We might also want to implement generic or constructed types so we can consider lists/records/structs/predicates beyond just "is any list". This might be overkill, or a separate feature.

The syntax here is not final, it is just meant to serve as an example:

// Some simple type checking predicates using type patterns.
isNumber(_ #number).
isInteger(_ #integer).
isRational(_ #rational).

// Type pattern's don't need a value pattern also, so these 3 should work too
isNumber(#number).
isInteger(#integer).
isRational(#rational).

isList(#list(_)).
isTypedList(#list(number)).

isRecord(#record(_)).
isTypedRecord(#record(number)).

isUnaryPredicate(#/1).
isBinaryPredicate(#/2).

isTypedUnaryPredicate(#/(number)).
isTypedBinaryPredicate(#/(number, number)).
// alternate syntax
isTypedUnaryPredicate(#/number/number)).
isTypedBinaryPredicate(#/number/number)).

// Generic types
in(X #T, [X, ..] #list T).
in(X #T, [_, ..R] #list T) :- in(X, R).

// If we get union/intersection patterns
add(A & (#number | #string), B & (#number | #string)) :- A + B.
// Or maybe even more correctly, using generic and union types
add(A & #T & (#number | #string), B & #T) :- A + B.

The # is kind of ugly, maybe there is a better syntax to denote type? Leading alternatives are $ or *, but those could have been useful operators/other symbols. Could be that type position and operator position do not conflict and that becomes not an issue, I haven't thought about it yet.

: have problems:

• Rust style : might cause ambiguity with records, unless we change record syntax
• Haskell style :: might look even weirder in records as { numfield: ::number }?

@ is in use in module paths (@core) but this should not be conflicting, just is a weird double use of a symbol.

<: looks a little alien but has the connotation I think... does not look as good when not paired with a value pattern though (e.g. isInteger(<:integer)). Same issue for :=.

' (similarly to lifetime syntax) would be cute, but would conflict with quoted atoms.

Could use paired <>, so like A <number> or just <number> or <list<number>>? This seems interesting, could be worth investigation.

There is no way to represent a tuple (anonymous struct without named fields) in Lumber. This prevents some types from being serializable to Lumber (Rust tuples), and also complicates the implementation of structs, as we end up supporting tuple-like semantics there, in the unnamed and each named field.

Supporting tuples properly should not be too difficult. As part of this work, no longer allow structs to hold multiple values in a single named field, and instead use a tuple as the field value (though maybe keep the current syntax as sugar, allowing the omission of tuple delimiters around a tuple field?).

The pattern A & B could be interpreted such that in order for a unification of T <=> A & B, we must have T <=> A and T <=> B.

Consider in this case whether the syntax from boundness patterns (#12) should be implemented as sugar for ? & A, and the syntax from type patterns (#5) as sugar for A & number).

Or so it seems. The following gave me an error:

:- use(@core::list).

Unresolved module @core::list in glob import.

Importing specific members worked fine (:- use(@core::list(in/2)).)

The builtin operators are kind of a hack. It would be more "correct" to allow implementing operators in Lumber, and then implementing the builtin ones as part of @core.

:- op(+, add/3, left, 6).
:- op(-, add/3, left, 6).
:- op(*, add/3, left, 7).

Operators should be importable/exportable like any other declaration. They must be imported to be used:

:- pub(+).
:- pub(-).
:- pub(*).

:- use(@core(+, -, *)).
multipleSumAndDifference(A, B, C) :- (A + B) * (A - C).

Also consider prefix/postfix operators, and operators that may occur in predicate position rather than expression position. Refer to Haskell for similar operator implementation.

I got pretty far using the AST for evaluation, but it's starting to break down. The AST doing both tasks is not good for separation of concerns and makes optimization difficult.

The Evaluation Tree and AST will be of similar shape (the shape is not the issue) but with different contents. In particular, the Evaluation Tree Patterns will use Rcs aggressively to make cloning cheaper. If this works, then we can consider the removal of some/all of the Cows that are used in the current setup.

The Evaluation Tree must support a method such as freshen() that returns an equivalent tree but with fresh variables, preferably without cloning anything significant (using a generic monad-like data structure Generational<T> to contain a generation might work).

Maybe also take the time to reconsider how wildcards are implemented - can wildcards be replaced with variables that are not yet bound (set to None) to get rid of wildcards in the EvaluationTree altogether?

Do not bother implementing builtin_sets at all, just detect uses of sets when converting from AST to Evaluation Tree and fail early. Allow AST to recognize sets so that the syntax remains reserved and fails gracefully.

I am not sure how this will play out with regards to libraries. Those are pretty sketchy though, so don't feel too bad about messing them up.

Particularly once mutable declarations (#16) are implemented, it might be useful to be able to run some initialization code before the program is allowed to answer queries, similar to the :- initialization directive of Prolog.

Syntax-wise, I suggest :- run(Query). as this is shorter and easier to remember/write than :- initialization(Query)..

Can Lumber be run in WASM (or really, from any environment other than Rust)? Any language that can interoperate with Rust should be able to also work with Lumber. Especially after #14, it would be interesting to get this to work.

Currently the :- pub directive can only export a single predicate at a time. When there are many predicates to export, it gets pretty tiring. There is also no way to "export everything", to re-export an import, or to export only one version of an operator and not the others. All of these are problems I think can be solved:

// To re-export an import
:- pub use(...).
// To export only a specific version of an operator
:- pub op(...).
// To export multiple definitions
:- pub(test/1, test/2, test/3).
// To export all predicates and operators in the current scope.
:- pub.

There is also no way to make a module public (the way pub mod works in Rust). All :- pub predicates are just made public in all scopes, and can be accessed by reaching into the child module whether it is public or not. Similar :- pub mod(test). syntax can be used for this extension as well.

Native functions are kind of a pain to implement. It would be good to create a proper proc macro for this, and implement type checking and value conversion automatically. It would be really cool if this also somehow made nondeterminism and arbitrary outputs easy:

#[lumber]
fn add(a: Int, b: Int, c: Int) {
  c = a + b;
}

No idea how this will work nicely, as Rust and Lumber are fundamentally very different languages. The above example will not work. Maybe something using structs and impl blocks will be necessary (though very verbose, and I'm making up some generator syntax).

#[lumber("add/3")]
struct Add(Int, Int, Int);

impl Add {
  #[lumber(add(A!, B!, C)]
  fn add_c(a: Int, b: Int, c: Option<Int>) -> () 
  yields () -> Self {
    match c {
      Some(c) if (a + b == c) => yield Add(a, b, c),
      Some(..) => {},
      None => yield Add(a, b, a + b),
    }
  }

  #[lumber(add(A!, B, C!)]
  fn add_b(a: Int, b: Option<Int>, c: Int) -> () 
  yields () -> Self {
    match b {
      Some(b) if (a + b == c) => yield Add(a, b, c),
      Some(..) => {},
      None => yield Add(a, c - a, c),
    }
  }

  #[lumber(add(A, B!, C!)]
  fn add_b(a: Option<Int>, b: Int, c: Int) -> () 
  yields () -> Self {
    match a {
      Some(a) if (a + b == c) => yield Add(a, b, c),
      Some(..) => {},
      None => yield Add(c - b, b, c),
    }
  }
}

It is currently possible to cause Lumber to crash by getting a non-record/non-list value into a record/list tail:

test(A, B) :- B <- { a: a, ..A }.
:- test(a, B).

This causes Binding::apply to fail when attempting to extract the value of B.

There is some sort of checking that needs to be done when constructing a list/record that the tail value is valid. There is currently no such construction check. Inserting a step into the generated body right before constructing the record (or before evaluating the body, in the case of a record in head position) could work, but there is still no way to represent that check, maybe until #5.

After #34 performance is much better but I'm sure there can still be more. It's just not as critical anymore. Maybe some Rc can be added to patterns (in place of boxes? in other places?) to speed up cloning even further.

Prolog does not use the occurs check by default because it is very slow. With some quick testing, I have determined that by not using occurs check in Lumber, significant performance improvements can be made. If we make occurs-checking opt-in (at the language level) that should help with performance. New syntax ("pattern with occurs check") will be required, maybe this is where the # comes in?

X =:= [X].  // pass
#X =:= [X].  // fail
X =:= #[X].  // fail
X =:= [#X].  // fail

As an alternative to serializing a data structure and sending it to Lumber as a variable, some data makes more sense to be able to query as predicates (for example, relational data loaded straight from a database). It would be convenient to be able to "serialize" this type of data into the Lumber database as "external facts".

Is there a way to further extend external facts to external rules (or is that even necessary? Is an external rule just a native function?)?

The grammar allows for declarations to be defined as "mutable". A mutable declaration is one that can be added to or taken away from at runtime. In particular, we only allow adding/removing facts from mutable definitions.

In order to satisfy the borrow checker, the mutable parts of the declaration will be stored outside of the main database, and passed in to the unification process, e.g. fn ask_mut(&self, question: &'a Question, mutables: &'a mut Mutables) -> impl Iterator<Item = Binding> + 'a. The &mut mutables reference would be held by the iterator until it is dropped, and updated each time next() is called. I think this should be possible, but might require some work to thread the mutables through the whole thing.

It would be up to the programmer to ensure that the Mutables database is stored and accessed correctly. If the Mutables database is lost, the Lumber instance would be still usable, just without any knowledge of these mutated values.

The Mutables database would be able to hold facts only. Mutable rules are not supported (at least for now), as I am not convinced they are necessary. It would be possible to insert and read the mutable definitions from Rust, to modify and to react to modifications made by the Lumber runtime (#28).

Mutable predicates may be given implementations in the Lumber program's source code. These definitions would not be considered mutable, and will not be removable. Mutable facts can be inserted into the initial database immediately after compilation by using initializers (#20). This original Mutables database would be cloned out of the Lumber instance, allowing multiple versions to exist at once.

If a mutable predicate is referenced without the Mutables database being provided (e.g. in the regular fn ask(&self, question: &'a Question) method), the static definitions of the mutable predicate, and the mutations performed by the initializer code are used. Mutations made during this time should be valid, but visible only within the the answering of that question (not persisted in the Lumber instance). Modifications to the Lumber instance may be handled as a future feature, if it is decided to be necessary.

Lumber is... very slow. Especially when dealing with very large structures. See root: it takes over a second to answer simple queries, as the game structure is very large. I have not yet looked in to which part is slow, but I would assume it is unification. Why is it so slow? Can it be sped up?

Seems like:

1. Module a imports :- use(@core::list).
2. Module b imports :- use(@core::list). :- use(a).
3. Module b references @core::list::in/2 as just in. Error is reported about cannot access a::in/2.

This is a bug. a::in/2 should not be considered. Even if it were considered, it should be detected as the same as @core::list::in and not be an error...

Higher order predicates would help prevent unnecessary code duplication, the same way higher order functions are used in functional programming. For example, to check that all numbers in a list are greater than n, we need to write a specialized recursive predicate for each n:

allGt2([]).
allGt2([X, ..R]) :- gt(2, X), allGt2(R).

allGt3([]).
allGt3([X, ..R]) :- gt(3, X), allGt3(R).

:- allGt3([4, 5, 6]).

But with higher order predicates, a generic all<1>/1 could be written:

all<_>([]).
all<pred/1>([X, ..R]) :- pred(X), all<pred/1>(R).

gt3(X) :- gt(3, X).
gt2(X) :- gt(2, X).

:- all<gt3/1>([4, 5, 6]).

When serializing Rust structs to Lumber, the Rust struct name is capitalized, so struct MyStruct must be quoted as 'MyStruct' (unless #[serde(rename = "myStruct")] is added). This is... just how it works, but also is kind of inconvenient. Is there an alternative?

Lumber values/patterns mostly implement Display, but there are a few places (particularly complex atoms) that are not fully supported. This needs to be finished and then have tests written for it so fmt and to_string will reliably output a Lumber expression that can be parsed back into the same value.

Would it be useful to be able to match the name of a struct as an atom? Is this generalizing too far?

selfPair(_(A, A)).

// All of these work:
:- test(selfPair(pair(a, a))).
:- test(selfPair(otherPair(a, a))).
:- test(equal(A(A, A), a(a, a))).

What if structs allowed any pattern as their name? How about now, is this too far?

next(N(A), M(A)) :- M <- N + 1.

I suspect both of these are going too far.

The following should be an error as it contains singletons, but it is not detected:

test(A, B).

I have no proof but I do suspect there are too many boxes used by Lumber in constructing the large iterators. By using custom iterators, instead of combining and boxing the standard ones, some levels of indirection might be avoided, thus improving performance.

The current Rust API is... rough in a lot of places. A little bit of it I thought about and planned, but a lot more of it is just random stuff that I hacked in so I could get things moving.

• A real, usable, friendly API will be required, allowing scalar values, structs, lists, and records to be constructed without friction.
• We may want to look into automatically serializing/deserializing questions and answers (#15) and whether we want to be able to write more complex questions using this system.
• Review the serializer/deserializer and make sure they are accurate and complete. I skipped a few pieces I didn't want to do for now.

It would be convenient to be able to access fields of a record similarly to in regular languages.

Having to use destructuring for everything is very verbose:

fullName(person { firstName: FirstName, lastName: LastName }, FullName) :-
  FullName <- FirstName + " " + LastName.

Where using field access could be simpler:

fullName(person(P), FullName) :-
  FullName <- P{firstName} + " " + P{lastName}.

This indexing operation would be not tied to variables, so a bit less useful but valid:

fullName(FullName) :-
  FullName <- { firstName: "Cam" }{firstName} + " " + { lastName: "Eldridge" }{lastName}.

Would also be useful to have a similar array access:

firstAndLastName(Names, FullName) :- 
  len(Names, N),
  FullName <- Names[0] + " " + Names[N - 1].

Could even chain accessors:

Record{field}[3]{anotherField}{lastField}

Wildcards/variables in records would be bound as usual:

name(Name, person(P)) :- 
  equal(P{name}, Name).

name("Cam", person { name: A }).
// A = "Cam"

Option<T> does not serialize the same way as other enums. Attempting to use such an option from Lumber is proving to be confusing.

There are two options here (no pun intended):

1. Serialize options like other enums ('Option'('Some'(T)) and 'Option'('None'))
2. Use the idea from #12 (where ?T and !T are patterns that match on the current bound-ness of a variable):
   • Let None in Rust mean "unbound" in Lumber (serializing to _).
   • Let Some(T) in Rust mean "bound" in Lumber (serializing to T).
   • When deserializing, deserialize an unbound variable (bound to _) to None and a variable bound to T to Some(T).
   • Serialize () to _, and deserialize to () always succeeds. (alternatively deserialize to () only succeeds if the value remains unbound?).

See the test for @core::list::update, which is currently failing. That should be fixed.

Why is it broken? I don't know. I have attempted to fix this a few times and none of it worked, I wonder how many undiscovered bugs were fixed by accident in this process, or did I just complicate things without making them any more correct...

Lumber currently requires the source files to be around when the program is run, which is not always how the user might want this to work. An option for compile time "compilation" (or just inclusion of Lumber source code) should be added, similar to how pest is able to read its file at compile time to generate a parser, without needing to reference the original .pest file when the program runs.

This is also preventing shipping an ilumber executable, as the path to the core library is hard coded to work with cargo run.

Records support the { field: _, .. Rest } syntax, but structs currently do not, as it just does not make as much immediate sense on a struct:

• What happens to the struct name?
• What to do about unnamed fields?

This probably is best done after #3, once structs have been simplified. Consider even removing the option of having both named and unnamed fields in a single struct (that's a feature somewhat unique to Lumber at this time, and maybe not needed). Syntax sugar for a record value as the final field of a struct could be used to simulate the current behaviour without needing special implementation, and allow making it clear which position the rest spreading is to be done:

struct(a, b, ..C).
struct(a, b, field: _, ..C).
struct(a, b, { field: _, ..C }).

Last-rules are not really all that powerful because the heads are so powerless... I was trying to come up with an example of how they are useful and it is not so easy.

animal(cat).
animal(bear).
animal(fish).
animal(rabbit).

plant(carrot).
plant(lettuce).
plant(berry).

eats(cat, fish).
eats(fish, fish).
eats(rabbit, carrot).
eats(bear, fish).
eats(bear, berry).

foodchain(A, F) :- eats(A, F).
foodchain(A, F) :- eats(A, B), foodchain(B, F).

In this example, foodchain/2 will cause an infinite loop. I would like to solve it with a last rule.

foodchain(A, A) ::- eats(A, A).
foodchain(A, F) :- eats(A, F).
foodchain(A, F) :- eats(A, B), foodchain(B, F).

Unfortunately, this won't work because the foodchain(bear, F) will unify with foodchain(bear, bear) and only then fail at eats(bear, bear), but it's too late and foodchain(bear, F) will return nothing.

Allowing guards on the head side would allow this to work:

foodchain(A, A), eats(A, A) ::- true.
foodchain(A, F) :- eats(A, F).
foodchain(A, F) :- eats(A, B), foodchain(B, F).

Currently, the only alternative is to put that logic into the recursive case, which is significantly uglier (particularly due to the lack of a not-equals operator)

foodchain(A, F) :- eats(A, F).
foodchain(A, F) :- eats(A, B), (A =:= B ->> false; foodchain(B, F)).

// With a not-equal `=/=`
foodchain(A, F) :- eats(A, B), A =/= B, foodchain(B, F).

It would be nice to be able to evaluate queries in multiple threads on the same instance of Lumber. This would prevent needing to recompile the program multiple times, just to get an instance onto multiple threads. The entire unification process is single threaded so there is no reason why this should be trouble. Probably just needs the Rcs to be converted to Arcs.

Keep in mind #16 is a feature that will be added, but most likely we will be able to isolate the mutation to a separate object that is passed in, allowing the core Lumber instance to remain sync/send/usable from two threads at once.

Are these really valuable? Should the syntax for these be changed? It's kind of a weird feature now that structs just contain records. Should named parameters be changed to just be a record in the function pattern? This might simplify the grammar and make things more consistent.

There is a test that I just wrote which is failing. Something is wrong with doing a unification destructuring a record and then passing the original record the a function that also destructures that record? Or something like that... more investigation will need to be done, and then it should be fixed...

I always kind of like unicode symbols... Though they are a pain to type in as the only option in a language. I think it would be at least worth supporting the standard operators and custom operators in unicode form, it might allow nice syntax in some places. All unicode symbols should have an ASCII equivalent, but it would be expected that the ASCII version is not as nice looking.

A syntax to require a certain variable to be bound or unbound at a particular time might be useful, as sometimes a function cannot be implemented if a value is unbound.

For example, for interacting with system resources, a handle must be bound/unbound at the right times.

open(Path, ?File) :- native_open(Path, File).
read(!File, Content) :- native_read(File, Content).

With this concept, we would interpret call syntax such that the following are equivalent:

call!(A, B) <- A + B.
call(!A, !B, ?C) :- C <- A + B.

Additionally, the pattern ? would be shorthand for ?_, and ! would be shorthand for !_.

Similar to #21, we could define union patterns A | B such that A | B <=> C if A <=> C or B <=> C. This sounds dumb in a simple case (how can something match two patterns), but can be useful in relatively complex situations, particularly with type patterns. I think this will be more difficult than multi patterns, but maybe not?

CLP is an interesting concept, which would be nice to have available in Lumber. In Prolog, both of these can be implemented as libraries. I suspect they can be implemented in Lumber as a @core module, exposing similar operators to the regular ones. Whether the Lumber implementation can handle CLP in its current state is the bigger question.

I was hoping to have sets implemented at the language level, as they would be very cool and allow exploring a whole bunch of new ideas. Unfortunately, unification of sets turns out to be NP Complete (source) so I do not feel like implementing this is really all that feasible at this time.

A lot of the functionality from @core would probably be useful to have imported automatically, via some sort of prelude. There is currently no concept of a prelude.

How is anyone going to learn this language if there is no doc or specification. Both should be made... but it can be not finalized until after the experimenting is over and this thing is working.

Not sure how this would work exactly, but I would like to be able to write #[derive(Question)] on a Rust struct, and then be able to ask it directly to Lumber:

enum Person {
  A, B, C, D, E,
}

#[derive(Question)]
struct Family(Option<Person>, Option<Person>);
let family_tree = Lumber::default(); // Say we had some lumber program that describes a bunch of people
for answer in family_tree.ask(Family(Some(Person::A), None)) {
  assert!(answer.1.is_some()); // each answer gets put into the struct.
}

Probably would be nice to have some testing options, both to help programmers using Lumber and to help verify the correctness of the Lumber standard library.

:- test(len([], 0)).
:- test(len([1,2,3], 3)).
len([], 0).
len([_, ..B], Len) :- 
  len(B, BLen),
  Len <- BLen + 1.

These tests would be run when calling some Lumber::test which could be called in a Rust #[test] function to get the Lumber tests to work as part of the program's test suite. The REPL would also include a --test flag to run the tests of whatever program is provided, rather than opening the REPL (or before opening the REPL).

Prolog provides the cut (!), but Lumber does not have an exact equivalent. I think this means sometimes Lumber will produce extra answers, without providing the programmer a way to not produce those answers.

I don't really fully understand this scope of this issue, as not enough Lumber code has been written to really determine the problem here. I just have a feeling that it's a problem. Maybe revisit all of the control flow options, and see if there really are enough to do anything that might be needed.

The parser could probably be separated, or at least exposed by the Lumber library so that other programs can manipulate Lumber code. This could make it possible to implement a language server or other useful ecosystem programs.

The grammar does not seem to recognize a record on the left hand of the =:= syntax (e.g. { a: _ } =:= A is an error, but A =:= { a: _ } is not).

Both should be allowed, why are they not?

There are two kinds of operators:

1. Expression operators (prefix/2, postfix/2, and infix/3).
2. Predicate operators (prefix/1, postfix/1, and infix/2).

Right now, operators are not permitted in predicate position, so operators from group (2) cannot be used. These should be allowed. This might even allow <- to be implemented as an operator rather than a language feature.

Lumber allows definitions to be written in call style:

len!([]) <- 0.
len!([A, ..B]) <- 1 + len(B).

This is a nice syntax sugar, but I feel like it can be confusing and might be unnecessary. A lot of limitations are introduced on functions written in this style. If this syntax is kept, the limitations should be removed so this becomes simply a syntax sugar for functions that are very expression-like.

Currently the semantics of record tails when the field is defined both in the head and the tail is not very clear. This should be made more clear, such that a field in both head and tail is valid, but the one in the head will take priority. This should help make updating a record a little easier:

// Currently, name must be removed from the record so it can be updated reliably. 
// This also requires the record previously had the name field.
setName(Name, person { name: _, ..P }, person { name: Name, ..P }).
// After change, this would not be the case:
setName(Name, person(P), person { name: Name, ..P }).

Right now in order to write an expression that evaluates to a value, we need to enter expression context with the <- control flow operator. Let's get rid of that operator, and go with expressions that just work like you'd expect. This should include calls and operators. Keep in mind that expressions expect all variables to be bound, and only produce one result, while predicates remain nondeterministic.

Remove the <- as part of this change. Maybe it will be useful for something else later on.

For the first attempt at this feature, expressions do not need to be available in predicate heads, only in predicate calls. Expressions in head patterns may come later, if at all.

Expressions will not be available in struct or list patterns yet.

There is not currently a full standard library for Lumber. The builtin @core module is set up, but it does not have many functions in it. We should identify features that need to be included and then implement them. This would probably be best done after native functions are improved (#13).

All standard library functions should be tested using Lumber's built in unit-testing feature.