#+TITLE: Programs and evaluators

* Why the kernel has no language
RNT supplies objects, storage and the execution lifecycle, and leaves
languages to its clients. SQL puts retrieval, data manipulation and data
definition in one language, and the boundaries between them are hard to
draw. In RNT, a language =A= may serve retrieval, =B= may serve
manipulation and definition, and =C= may serve manipulation beside =B=.
Nothing arbitrates between =B= and =C=, and a client picks either. The
[[file:../lib/evaluators/FOL.ml][FOL]] evaluator is one such language, shipped with RNT for retrieval.

That leaves the kernel two jobs. It has to run a program without
knowing its language, and it has to let programs in different languages
read each other's results. Programs and evaluators are how it does both.

* Programs
The kernel holds, stores and runs programs whose structure it cannot
know. A [[file:../lib/kernel/Program.ml][program]] is therefore an image, in the manner of a Windows
[[https://en.wikipedia.org/wiki/Portable_Executable][Portable Executable]], whose header tells the loader which subsystem
runs it.

#+begin_src ocaml
type kind = ..
type image = {evaluator: string; kind: kind; source: string}
#+end_src

=evaluator= names the evaluator that runs the program, as
=scope:language=. =kind= is the program as that evaluator understands
it. =source= is its text, for display and for storage.

=kind= is an [[https://ocaml.org/manual/extensiblevariants.html][extensible variant]], extended the way [[file:object-system.org][protocols]] are. Each
evaluator adds its own constructor, as FOL adds =Fol of Path.t term=.
The tree keeps its OCaml type, and only the evaluator that defined the
constructor can match on it, so the kernel passes programs around with
no encoding in between. The evaluator name is the one string a program
carries, because the kernel looks evaluators up by name and storage can
keep a name but not a constructor.

Every program speaks [[file:../lib/protocols/Executable.mli][Executable]], and a program built with a root can run.

#+begin_src ocaml
method invoke : Handle.t list -> within:Handle.t -> (Handle.t, condition) result
#+end_src

Invoking a program looks up =\[scope]\evaluator\[language]= under its
root, and hands that evaluator the kind, the inputs and =within=. A bare
=language= names the =system= scope. The root is a capability, so a
program reaches only the evaluators of the root it was given. A program
built without a root can be stored but not run, and invoking it fails
with =unloaded-program=. A name with nothing registered under it fails with
=no-evaluator=.

* Evaluators
An evaluator is an object with the [[file:../lib/protocols/Evaluator.mli][Evaluator]] protocol.

#+begin_src ocaml
method parse : string -> (kind, condition) result
method eval : kind -> Handle.t list -> within:Handle.t -> (Handle.t, condition) result
#+end_src

=eval= runs a kind, and fails for a kind that is not its own. =parse=
turns source back into a kind, which is how the kernel reloads a stored
program. A program built in code skips parsing. =FOL.program term=
builds one from a tree and prints the tree as its source, so a test can
build a plan without a syntax. FOL has no text syntax yet, and its
source is the [[https://en.wikipedia.org/wiki/Bencode][bencoded]] term.

#+begin_src plantuml :file ../images/evaluators-classes.svg
@startuml
hide empty members
skinparam classAttributeIconSize 0

class Program <<image>> {
  evaluator : string
  kind : Program.kind
  source : string
}
interface Executable {
  invoke(inputs, within) : relation
}
interface Evaluator {
  parse(source) : kind
  eval(kind, inputs, within) : relation
}
class "FOL evaluator" as FOL
class EphemeralRelation
interface Relation {
  contains(tuple) : bool
  modes() : Mode.t
}
interface Enumerable {
  enumerate() : cursor
}
interface Schematics {
  describe() : heading
}

Program ..|> Executable : runs when given a root
FOL ..|> Evaluator
Program --> Evaluator : names it as\nscope:language
EphemeralRelation ..|> Relation
EphemeralRelation ..|> Enumerable
EphemeralRelation ..|> Schematics
EphemeralRelation o--> "0..1" Program : wraps
Evaluator ..> EphemeralRelation : eval returns
@enduml
#+end_src

#+RESULTS:
[[file:../images/evaluators-classes.svg]]

* Within
In RNT, holding a handle is what authorizes its use, so an evaluator
gets no context beyond one directory. A program names relations by
path, and its evaluator resolves those paths in the directory the
program is invoked =within=. It can reach nothing else.

Resolving paths at each invocation is what lets one program run against
any state. Read through
=\system\branch\master\multigroup\m\schema\s\relation\r=, a stored
program runs within that branch state. Read through
=\system\branch\master\previous\...=, it runs within the previous state
and reads what was there then. It can never read outside its branch.

Evaluation never commits, and neither does exhausting a cursor.
Committing is an explicit host operation. Cancellation, budgets and
resource accounting are not implemented.

* Results
Programs in different languages can read each other's results only if
those results share one interface. The result of every program is an
[[file:../lib/kernel/EphemeralRelation.ml][ephemeral relation]]. It describes its heading, declares its [[file:modes.org][modes]] and
answers membership. Enumerating it gives a cursor, so operators stack
as cursors over cursors, as in Graefe's Volcano iterator model
("Volcano, an Extensible and Parallel Query Evaluation System", 1994),
and nothing in between is materialized.

An ephemeral relation can wrap a program, through
=EphemeralRelation.of_program=. Reading it invokes the program within
the state it was given. Asking its modes, or whether it holds a tuple,
invokes the program and asks the relation the program returns. For FOL
this is cheap, because FOL builds its result without reading a tuple.

Programs that change state have no result protocol yet.

* Storage
A multigroup stores an ephemeral relation that wraps a program as the
program's evaluator name and source, beside its heading. It stores any
other relation as its tuples. When a branch reads the relation back,
the evaluator registered under that name parses the source into a kind,
and the relation wraps the program that comes out. The parse happens at
lookup, so a missing evaluator or a malformed source fails at
=Path.lookup= rather than at the first read.

#+begin_src plantuml :file ../images/evaluators-reading.svg
@startuml
actor Client
participant "Path.lookup" as Path
participant Multigroup
participant EphemeralRelation as E
participant Program
participant "evaluator under\nthe program's name" as Ev

Client -> Path : lookup a relation in a branch state
Path -> Multigroup : find it
Multigroup -> E : load (evaluator name, source, heading)
E -> Program : Program.load root
Program -> Ev : parse source
Ev --> Program : kind
E --> Client : relation wrapping the program
Client -> E : enumerate
E -> Program : invoke ~within:branch state
Program -> Ev : eval kind ~within
Ev --> Program : result relation
Program --> E : result relation
E --> Client : cursor over the result
@enduml
#+end_src

#+RESULTS:
[[file:../images/evaluators-reading.svg]]

* Composition
Evaluators compose through programs and results, and neither knows the
other's kind. When FOL resolves a path to a relation that wraps a
program, it checks the program's kind.

- A FOL program is inlined into the plan. FOL then sees through it, and
  refuses a program that reaches itself with =cyclic-program=.
- A program of any other kind is invoked within the same state, and its
  result enters the plan like any other relation.

A program in another language reads a FOL program the same way, by
resolving its path and reading the relation. The [[file:../test/unit/kernel/Branch.ml][branch tests]] do both,
with a toy language whose programs shout the titles of a FOL relation.

FOL detects cycles only among its own programs. A cycle across
languages, where a FOL program reads a toy program that reads it back,
recurses without end. Nothing checks one evaluator's assumptions about
another's results either, so the caller has to establish that the
callee's results meet its needs.

* Registration
The system's evaluators are registered at initialization, under
=\system\evaluator=. A subsystem mounts its own root with
[[file:../lib/kernel/Initialization.mli][Initialization.mount]], which holds =\[name]\evaluator=, and registers
its evaluators there. Its programs then name them as =name:language=. A
foreign registration path is a later concern.

* Capability tags
A client should be able to ask which evaluators serve manipulation, and
get =B= and =C= back. The intent is that each evaluator declares a set
of opaque labels, such as =drl=, =dml=, =ddl=, =vcs= or any a client
invents, and that the registry indexes them. None of this is
implemented.