Chaining of functions with side effects with guaranteed order

[Necr0x0Der]

There is a recurrent request for chaining functions with side effects with no return value, e.g. add_atom, println!, etc. We've discussed this for a few times in different places, and this issue is a sort of conclusion to which we come with @vsbogd in the last discussion. While there are different practical ways of achieving this functionality, the issue boils down to semantics of "empty" result. MeTTa considers all functions as non-deterministic, and an empty result means that the function has produced no evaluation branches, and nothing is to be passed to its super-expression. Basically, the function is not total. In most cases, it is really what is expected, e.g. + expects two numbers, and if one its argument is empty, it has nothing to evaluate. match can normally return an empty result, which will mean exactly the same. A pure MeTTa function can be defined not for all values of its arguments, and being implemented via match will also be evaluated to the empty set of results (once again, not total). However, grounded functions with side effects may return "nothing". It is natural to return an empty set of results from such functions, although it is technically incorrect. In functional programming, when a function has Unit as a return type (which can be represented by ()), it means that it "returns" the only element of one-element set, thus, its result contains no information, but it is still a non-empty result. In pure functional programming, functions that really return nothing (which can be referred to as Void, although in other languages void can mean unit) are "absurd" and they are not possible (although most such languages have non-strict components to represent the notion of such impossibility). We also need to distinguish "void" and "unit". Minimal MeTTa ( #380 ) introduces EMPTY_SYMBOL to represent an empty set of results, but it doesn't introduce UNIT_SYMBOL (or Void, Singleton depending on naming preferences) and treats an empty set returned by grounded functions as such unit (is it so?) - that can also look natural for those who are not hard-core functional programming geeks, because "these functions really return nothing". Having EMPTY_SYMBOL may still be convenient, although it may also cause confusion, because right now it is implemented in pure MeTTa as (superpose ()), which will be treated differently than EMPTY_SYMBOL by Minimal MeTTa. Thus, it might be better to have EMPTY_SYMBOL not as a special atom, but just as syntactic sugar for (superpose ()), but this may depend on the implementation. Basically, the proposal is to introduce void/unit/singleton/ok/()/..? and use it as the result of evaluation of (grounded) functions that return "nothing". In this case, they also will be properly typed, e.g. (-> ... Unit), and their chaining will be quite simple. We can also return () (not empty set of results, but an empty expression) and treat it as unit, although it may lead to the question if it is ok to ascribe Unit type to (). Maybe, having (: unit Unit) is safer. One may say that functions with different side effects should belong to different monads, e.g. IO, SpaceIO, but introducing simplest proper types for println!, add_atom, etc. might be preferable as the first step (and can be more flexible and convenient in general). Thus, I wonder if simply introducing (: unit Unit) for returning "empty" results is a good way to go? If yes, should it be named unit or void - which is more intuitive and less confusing? Or should it be just ()? Should we still have EMPTY_SYMBOL or go back to the empty set of results? Or does anyone have strong preferences for any alternative solution? @ngeiswei , @luketpeterson ?

[luketpeterson]

I think this proposal makes sense, and as you say, is a good first step.

To the question of void vs. unit vs. (), I think I have a slight aesthetic preference for void, but really any of the options are fine.

In my opinion, using an empty expression should be supported as well, so if we define a void token then it would just be syntactic sugar over ()

One may say that functions with different side effects should belong to different monads, e.g. IO, SpaceIO, but introducing simplest proper types for println!, add_atom, etc. might be preferable as the first step (and can be more flexible and convenient in general).

Non-determinism + side-effects is a tricky issue indeed. If non-deterministic results can affect control flow, or if a branch may be pruned after a side-effecting atom has executed, this will have a large effect on the design.

Addressing this on a case-by-case basis is probably the best practical solution. I think a Space monad that journals updates into the space is the right solution for add/remove atom operations. And likewise an output-buffering monad is the right solution for println / logging.

For operations that require bidirectional communication with the outside world (user-interface for example) the monad approach doesn’t hold up. But the whole paradigm of non-deterministic speculative execution breaks down when interfacing with the outside world that is monolithic and monotonic with respect to time.

In my vaguely-MeTTa-like language from 2020 (HC2) I had the idea of simulated execution of side-effecting functions. And evaluation happened first in a non-deterministic way, evaluating only non-side-effecting versions of each function, and then, after the execution plan was composed, a deterministic execution was carried out. This, in effect, is the monad approach turned inside-out. Basically making it the atom's responsibility to maintain the monads / models of the things their side-effects can affect. But system-provided monads are probably easier to maintain.

I believe the HC2 approach should be implementable on top of standard MeTTa, once we figure out how the inference-control mechanism (pruning function) needs to work.

[ngeiswei]

I might have a slight preference for (). @tanksha, @patham9, any opinion?

[Necr0x0Der]

@ngeiswei , Minimal MeTTa has ATOM_VOID symbol, which is actually substituted, when the interpreter gets an empty result from a grounded function. This results in the situation that some of unit tests fail for Minimal MeTTa, because they have assertEqualToResult with the empty result. My idea is to make the current interpreter closer to Minimal MeTTa, so there will be less difference unit tests, and this will be the step towards full migration. I don't like the automatic conversion of the empty result to Void, because some grounded function may want to be partial. Of course, for this purpose, they can explicitly return EMPTY. But I still don't like that the result of returning ATOM_VOID and an empty list of results [] lead to the same behavior. In any case, I want to tweak library grounded functions to explicitly return ATOM_VOID. I can rename it to ATOM_UNIT, and I can make it equal to () if you have strong preference. Please, let me know if you have.

One more thing is that unit tests frequently use ! import. It is convenient to make the result of this operation really empty for the purpose of testing. OTOH, it also makes sense for this operation to return void / unit / () if successful, and Error or truly empty result if not. I'm not sure which is better. @vsbogd , @ngeiswei , @luketpeterson , any opinions?

[vsbogd]

But I still don't like that the result of returning ATOM_VOID and an empty list of results [] lead to the same behavior.

Yeah, I don't suggest automatically convert results, in minimal MeTTa it was a shortcut to not modify the code of the grounded functions. But I would explicitly define the rules of writing grounded function instead of implicitly replacing the results.

One more thing is that unit tests frequently use ! import. It is convenient to make the result of this operation really empty for the purpose of testing. OTOH, it also makes sense for this operation to return void / unit / () if successful, and Error or truly empty result if not. I'm not sure which is better. @vsbogd , @ngeiswei , @luketpeterson , any opinions?

I would vote for the unit if successful and Error if not successful. Not understand why empty result is better for testing though.

[Necr0x0Der]

Not understand why empty result is better for testing though.

My concern was that if import! will return unit, and we check for empty results in the unit tests based on metta-scripts, verifying success of these unit tests would be cumbersome. However, it appeared to be not a problem. We just need assertEqual to return unit as well. Then, we are checking not for [] but for units in all tests. This is even more elegant, because successful assert doesn't terminate computations in this case.

[Necr0x0Der]

Merging #452 doesn't solve the issue (although makes a step towards this), because the problem is not (only) that the result of these functions was empty, but it is (also) in the sequential nature of the required chaining. While we can have in the current MeTTa version something like

(: chain (-> (->) Atom (->)))
(= (chain $a $b) $b)
!(chain (add-atom &self test) (remove-atom &self test))

which will work (unless the interpreter is "smart enough" to drop the evaluation of $a because it is never used), it would be better to revisit this issue after migrating to Minimal MeTTa with its explicit chain operation.

[vsbogd]

Btw, does the following method of chaining work?

!(let* (
  (() (println! a))
  (() (println! b)) )
  () )

[vsbogd]

Working on minimal MeTTa I realized that let and chain effectively the same thing. Thus let can be used in old interpreter for chaining.

[Necr0x0Der]

Btw, does the following method of chaining work?

I saw people using this hack, yeah. It looks more solid than using superpose for this purpose.