Free variables and nondeterminism
Two features make MeTTa feel different from ordinary functional languages: you can call a function with a free variable, and a function can return many results. Put together, they let you solve search problems by describing them.
Querying by calling
You can pass a variable where a value would go, and MeTTa returns every right-hand side that matches, keeping the binding:
The second query is the interesting one: the binding for $x is not lost, so each result carries both the brother and who they are a brother of. A call with a free variable is, in effect, a query.
Logic with free variables
Now combine that with boolean rules. Some facts and a rule about frogs:
Asking (frog $x) infers that Fritz is a frog and Sam is not. This is logic programming: you state rules and facts, then ask a question with a variable in it.
Choosing and collecting
A nondeterministic value is just an expression with several results. superpose turns a tuple into such a choice, and collapse gathers all results back into one tuple:
(empty) is the opposite of a result: it evaluates to no results, which is how you prune a branch. It is the same as a function having no matching rule.
Nondeterminism flows through other calls. If you feed a nondeterministic argument to a function, the function runs once per value:
But beware where the choice happens. Each occurrence is evaluated independently, so two (bin) calls in a body multiply out:
Search by generate-and-test
Recursion plus nondeterminism gives you search almost for free. A function that builds all binary lists of a given length:
From there, the subset-sum problem is just "generate every selection, keep the ones that hit the target". A candidate is a binary list saying which numbers are taken; the sum of taken numbers is a scalar product:
gen-bin-list proposes every selection nondeterministically, solve keeps a selection when its sum matches and prunes it with (empty) otherwise. You described the problem and got the search.
That completes the introduction to evaluation. From here you can dig into the standard library, types, or move to using MeTTa from TypeScript.