diff options
Diffstat (limited to 'docs/evaluators.org')
| -rw-r--r-- | docs/evaluators.org | 285 |
1 files changed, 196 insertions, 89 deletions
diff --git a/docs/evaluators.org b/docs/evaluators.org index b7ce3b8..f1b4be5 100644 --- a/docs/evaluators.org +++ b/docs/evaluators.org @@ -1,108 +1,215 @@ -#+TITLE: Evaluators +#+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. -* Position -RNT should supply objects, storage, and execution -lifecycle, but not directly a sublanguage. That duty is then on the -clients to implement one and register it, using the kernel's -capabilities. +#+begin_src ocaml +type kind = .. +type image = {evaluator: string; kind: kind; source: string} +#+end_src -In this context, an evaluator is an RNT object, registered and -selected through the object interface, with a special "evaluator" -protocol. Unlike SQL where the boundaries between execution contexts -of the language is confusing and sometmes non-trivial, a sublanguage -=A= may serve retrieval, =B= may serve DML and DDL while =C= may serve -DML alongside =B=. Nothing arbitrates between B and C; making the -client free to opt for one. +=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. -The FOL evaluator is therefore, one of such evaluators that is shipped -alongside RNT for specifically Data Retrieval. +=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. -* Capability tags -An evaluator object declares a set of opaque labels — =drl=, =dml=, -=ddl=, =vcs=, or anything a client invents. The registry stores and -indexes them so a client can ask which evaluators declare =dml= and -get back B and C. - -* Protocols -An evaluator is an object like any other, that can be used to execute -a program, exactly as an interpreter takes an expression and an -environment. The plan tree should already bear every value and handle -the program needs, so there is nothing left to bind. Each invocation -carries independent state based atop of the handles it was given -(being therefore hash dependent and isolated). +Every program speaks [[file:../lib/protocols/Executable.mli][Executable]], and a program built with a root can run. #+begin_src ocaml -module Make (P : PROGRAM) : sig - class type implementation = object - method invoke : P.t -> (Handle.t, condition) result - end -end +method invoke : Handle.t list -> within:Handle.t -> (Handle.t, condition) result #+end_src -The protocol is parameterized by the evaluator's own plan type, so a -plan is never encoded into values only to be decoded again. Each -application of the functor yields its own protocol constructor, which -is what keeps one evaluator from answering another's programs: a -client obtains the interface through the module of the evaluator it -intends to speak to. The FOL evaluator, which lives under -=lib/evaluators= alongside the evaluators shipped with RNT, currently -understands a single node: +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 -type plan = Base of Handle.t +method parse : string -> (kind, condition) result +method eval : kind -> Handle.t list -> within:Handle.t -> (Handle.t, condition) result #+end_src -=Base= carries the handle of a relation, which is enumerated to -exhaustion. The evaluator only invokes protocols on the handles it -receives, which keeps it free of storage and of name resolution. - -The returned handle carries a result protocol with =Protocols.Cursor=, -giving it incremental consumption. Since executing a plan node yields -a cursor, operators stack as cursors over cursors, in the manner of a -volcano iterator, and no intermediate result is materialized. A -successor state and a command completion are further result protocols, -added for DML and DDL later. It's important to notice that the kernel -enumerates result protocols; it thererfore does not enumerate -sublanguages. That is not to say however that we cannot have a builtin -catalog relation installed and configured by the client that -enumerates them (that's a concern for the future). - -* Handles -There is no evaluation context. Since we are a capability based -system, holding a handle is what authorizes its use, so the caller -obtains every handle a program needs beforehand (through the -directories it was granted) and passes them in. Evaluators reach -kernel resources *only* through those handles. A program that refers -to things by name carries the directory they are resolved in, as the -lambda evaluator does: - -#+begin_src ocaml -type program = Program of term * Directory.t Handle.interface +=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 -Since every object is content addressed and prolly trees do not -depend on insertion order, equal state yields an equal hash, so the -relation behind a handle does not change under a running evaluation. -A successful evaluation and cursor exhaustion never commit. Commit -should be an explicit host operation. +#+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 -Cancellation, budgets, and resource accounting are not implemented. +#+RESULTS: +[[file:../images/evaluators-reading.svg]] * Composition -Evaluators compose through invocation and result protocols alone. A -DML program written in B may invoke a retrieval program written in A, -consume its cursor, and build a successor state from the tuples. A -retrieval program in A may invoke a procedural relation implemented by -C. Neither evaluator however knows the other's representation. The -caller must establish that the callee's contract meets its needs, -obviously. +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 -Registration is made by the client, and in the case of builtins, -automatically at initialization, just as =Relation= and =Schematics=, -for example. A foreign registration path is a later concern and is not -designed for here. - -Only =Protocols.Cursor= exists as a result protocol (at least for now), -so a successor state, completion, plan persistence, and cross-evaluator -optimizations are absent by design. +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. |