Getter.mag

// This file is part of ExactpAdics
// Copyright (C) 2018 Christopher Doris
//
// ExactpAdics is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// ExactpAdics is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with ExactpAdics.  If not, see <http://www.gnu.org/licenses/>.


// freeze;

Z := Integers();
LIST := _ExactpAdics_List;

import "State.mag": STORE;

// TODO: lock all updates while resolving dependencies

declare verbose ExactpAdics_Update, 2;

/////////////////////////////////////////////////////////////////////////////////
// profiling

///# Miscellany
///## Profiling
///
/// To help isolate the slow parts of code, we provide some profiling tools.

PROFILE_UPDATE := recformat<x, initial_apr, target_apr, initial_time, time_elapsed>;

/// Turn profiling on or off.
/// 
///param Reset:=false When true, also resets the profile.
intrinsic ExactpAdics_SetProfile(doProfile :: BoolElt : Reset:=false)
  {Starts or stops profiling the exact p-adics updates.}
  s := STORE;
  s`profile_updates := doProfile;
  if Reset then
    ExactpAdics_ResetProfile();
  end if;
end intrinsic;

/// True if profiling is enabled.
intrinsic ExactpAdics_GetProfile() -> BoolElt
  {True if profiling is enabled.}
  return STORE`profile_updates;
end intrinsic;

/// Resets the profile.
intrinsic ExactpAdics_ResetProfile()
  {Resets the profiling data for the exact p-adics updates.}
  s := STORE;
  s`updates := [];
end intrinsic;

/// Returns the profile, a sequence of records for each update with the following fields:
/// - `x`: the element being updated.
/// - `initial_apr`: the initial absolute precision of the element.
/// - `target_apr`: the absolute precision being updated to.
/// - `initial_time`: the `Cputime()` when the update was made.
/// - `time_elapsed`: the time taken to perform the update.
intrinsic ExactpAdics_GetProfileUpdates() -> []
  {Gets a list of records, one per update, with fields recording the element, the initial precision, the target precision, and the time to perform the update.}
  return STORE`updates;
end intrinsic;

//////////////////////////////////////////////////////////////////////////////////
// dependencies

///# Internals
///## Getters
///
/// *Advanced users only.* You only need to know about getters if you wish to implement a new exact p-adic algorithm at a low-level (i.e. not built entirely out of intrinsics already supplied by this package) or implement a new compound p-adic type.
///
///toc
///
///### Overview
///
/// In this package, a *getter* is a computation which has p-adic dependencies in the sense that it requires certain p-adic values to be known to certain precisions before it can be evaluated. Getters underpin the whole package: a `FldPadExactElt` has a field `update` which is a function taking as input an absolute precision and returning a getter; evaluating this getter has the side-effect of increasing the absolute precision of the element to at least the given precision.
/// 
/// We encapsulate getters into the new type `ExactpAdics_Gettr`, and intrinsics which directly deal with getters are documented here.
/// 
/// A getter is essentially represented by a function `getDeps` returning a list of dependencies, and a function `getValue` which computes the value assuming the dependencies are met. There is also a state which is passed around by these functions so they can be stateful. A dependency is simply a pair `<x,apr>` of a p-adic value `x` (a `FldPadExactElt` or `RngUPolElt_FldPadExact`, etc.) and an absolute precision `apr` (a `Val_FldPadExact`, etc.), meaning that `x` is required to be known to absolute precision `apr`. Note that these dependencies may themselves have dependencies, and so we have a tree of dependencies. Evaluating the getter therefore involves traversing this tree from the leaves upward, satisfying dependencies as we go and computing values.
/// 
/// As an optimization, if two dependencies `<x,apr1>`, `<x,apr2>` in the tree are for the same p-adic value `x`, then the nodes are fused into the node `<x, apr1 join apr2>`. Also if `<x,apr>` is a dependency and the absolute precision of `x` is already `apr` then we may immediately trim the whole subtree.

DEP := recformat<id, x, apr, st, g, childids>;

function dep_new(x, apr)
  ok, apr := IsValidAbsolutePrecision(x, apr);
  error if not ok, Sprintf("invalid apr: %o", apr);
  return rec<DEP | id:=x`id, x:=x, apr:=apr, childids:={Integers()|}>;
end function;

procedure dep_start(~d)
  if assigned d`g then
    delete d`g;
  end if;
end procedure;

procedure dep_set_apr(~d, apr)
  d`apr := apr;
  dep_start(~d);
end procedure;

procedure dep_getDeps(~d, ~deps)
  if not assigned d`g then
    d`g := d`x`update(d`apr diff AbsolutePrecision(d`x));
    case Type(d`g):
    when ExactpAdics_Gettr:
      ;
    when BoolElt:
      d`g := ExactpAdics_ConstGetter(d`g);
    else
      error "update function should return a getter or true";
    end case;
    d`st := d`g`state;
  end if;
  deps := [**];
  d`g`getDeps(~d`st, ~deps);
end procedure;

procedure dep_doUpdate(~d, ~done)
  d`x`update_expecting_apr := d`apr;
  d`g`getValue(~d`st, ~val);
  delete d`x`update_expecting_apr;
  done := assigned val;
end procedure;

function dep_isDone(d)
  return d`apr le AbsolutePrecision(d`x);
end function;

function deps_new()
  return AssociativeArray(Integers());
end function;

procedure deps_remove(~deps, d)
  Remove(~deps, d`id);
end procedure;

function deps_keys(deps)
  return Sort(SetToSequence(Keys(deps)));
end function;

deps_has := IsDefined;

forward deps_add_list;

procedure deps_set(~deps, d)
  dep_getDeps(~d, ~ds);
  for t in ds do
    Include(~d`childids, t[1]`id);
  end for;
  deps[d`id] := d;
  deps_add_list(~deps, ds, d`id);
end procedure;

procedure deps_add(~deps, d, maxid)
  assert d`id lt maxid;
  // compare the target and current apr
  apr := AbsolutePrecision(d`x);
  if d`apr le apr then
    return;
  elif apr le d`apr then
    ;
  else
    dep_set_apr(~d, d`apr join apr);
  end if;
  // see if a dependency for this already exists, and compare aprs
  ok, d2 := IsDefined(deps, d`id);
  if ok then
    if d`apr le d2`apr then
      return;
    elif d2`apr le d`apr then
      ;
    else
      dep_set_apr(~d, d`apr join d2`apr);
    end if;
  end if;
  // now actually set the dependency
  deps_set(~deps, d);
end procedure;

procedure deps_add_list(~deps, ds, maxid)
  for d in ds do
    deps_add(~deps, dep_new(d[1], d[2]), maxid);
  end for;
end procedure;

procedure deps_satisfy(~deps)
  store := STORE;
  prof := store`profile_updates;
  while true do
    keys := deps_keys(deps);
    if #keys eq 0 then
      return;
    end if;
    for i in keys do
      d := deps[i];
      vprint ExactpAdics_Update, 2: d`id, "has children", d`childids;
      if exists{j : j in d`childids | deps_has(deps, j)} then
        vprint ExactpAdics_Update, 2: d`id, "has dependencies outstanding";
      else
        vprint ExactpAdics_Update: d`id, "updating to", d`apr;
        if prof then
          u := rec<PROFILE_UPDATE | x:=d`x, initial_apr:=AbsolutePrecision(d`x), target_apr:=d`apr, initial_time:=Cputime()>;
        end if;
        dep_doUpdate(~d, ~done);
        if prof then
          u`time_elapsed := Cputime() - u`initial_time;
          Append(~store`updates, u);
        end if;
        if done then
          // as soon as the update worked, remove it from the dependency tree
          error if not dep_isDone(d), "update did not increase precision enough";
          vprint ExactpAdics_Update, 2: "  done";
          deps_remove(~deps, d);
        else
          vprint ExactpAdics_Update: "  not done yet";
          deps_set(~deps, d);
          // break i;
        end if;
      end if;
    end for;
  end while;
end procedure;

procedure satisfy_deps_list(ds, maxid)
  deps := deps_new();
  deps_add_list(~deps, ds, maxid);
  deps_satisfy(~deps);
end procedure;

procedure satisfy_dep(x, apr)
  satisfy_deps_list([*[*x,apr*]*], Infinity());
end procedure;


//////////////////////////////////////////////////////////////////////////////////
// the getter
// 
// a dependency is a pair <x,a> where x`id is a dependency-ordered integer, IsValidAbsolutePrecision(x,a) is true, x`update(a) is a getter whose value we ignore.

declare type ExactpAdics_Gettr;
declare attributes ExactpAdics_Gettr: state, getDeps, getValue, explode;

// WRAPPED_FUNCTION := recformat<func, inputs, outputs, numInputs, numOutputs>;

// function wrappedFunction(data)
//   w := rec<WRAPPED_FUNCTION | func := data[1]>;
//   if #data lt 2 then
//     w`numInputs := 1;
//   else
//     inputs := data[2];
//     case Type(inputs):
//     when RngIntElt:
//       w`numInputs := inputs;
//     else
//       error "bad inputs specifier";
//     end case;
//   end if;
//   if #data lt 3 then
//     w`numOutputs := 1;
//   else
//     outputs := data[3];
//     case Type(outputs):
//     when RngIntElt:
//       w`numOutputs := outputs;
//     else
//       error "bad outputs specifier";
//     end case;
//   end if;
//   return w;
// end function;

// function callWrappedFunction_InList(w, x)
//   case w`numInputs:
//   when 0:
//     return w`func();
//   when 1:
//     return w`func(x);
//   when 2:
//     return w`func(x[1], x[2]);
//   when 3:
//     return w`func(x[1], x[2], x[3]);
//   when 4:
//     return w`func(x[1], x[2], x[3], x[4]);
//   else
//     error "not implemented for this many inputs";
//   end case;
// end function;

// function callWrappedProcedure_InList(w, x)
//   case w`numInputs:
//   when 0:
//     w`func();
//   when 1:
//     w`func(x);
//   when 2:
//     w`func(x[1], x[2]);
//   when 3:
//     w`func(x[1], x[2], x[3]);
//   when 4:
//     w`func(x[1], x[2], x[3], x[4]);
//   else
//     error "not implemented for this many inputs";
//   end case;
// end function;

// function callWrappedFunction_InList_OutList(w, x)
//   case w`numOutputs:
//   when 0:
//     callWrappedProcedure_InList(w, x);
//     return [**];
//   when 1:
//     a := callWrappedFunction_InList(w, x);
//     return a;
//   when 2:
//     a, b := callWrappedFunction_InList(w, x);
//     return [* a, b *];
//   when 3:
//     a, b, c := callWrappedFunction_InList(w, x);
//     return [* a, b, c *];
//   when 4:
//     a, b, c, d := callWrappedFunction_InList(w, x);
//     return [* a, b, c, d *];
//   else
//     error "not implemented for this many outputs";
//   end case;
// end function;

///### Creation

/// Creates a new getter with initial state `state`. `getDeps` must be a `procedure(~state, ~deps)` assigning to `deps` a list of `<x,apr>` pairs such that the computation depends on the absolute precision of `x` being at least `apr`. `getValue` must be a `procedure(~state, ~value)` which either assigns to `value`, giving the value of the getter, or does not assign to `value` meaning that the computation has more dependencies, and hence `getDeps` needs to be called again.
intrinsic ExactpAdics_Getter(state, getDeps, getValue) -> ExactpAdics_Gettr
  {Makes a new ExactpAdics_Gettr.}
  g := New(ExactpAdics_Gettr);
  g`state := state;
  g`getDeps := getDeps;
  g`getValue := getValue;
  return g;
end intrinsic;

intrinsic ExactpAdics_ConstGetter(X) -> ExactpAdics_Gettr
  {The getter returning X.}
  return ExactpAdics_Getter(
    false,
    procedure (~st, ~deps)
      ;
    end procedure,
    procedure (~st, ~val)
      val := X;
    end procedure);
end intrinsic;

intrinsic ExactpAdics_NullGetter() -> ExactpAdics_Gettr
  {The getter with no dependencies that does nothing.}
  return ExactpAdics_ConstGetter(true);
end intrinsic;

/// A new getter with more general dependencies. `getGetter` must be a `procedure(~state, ~getter)` assigning to `getter` a getter, which is a dependency. `getValue` must be a `procedure(gvalue, ~state, ~value)` which is like `getValue` for `ExactpAdics_Getter` except it now takes the extra input `gvalue` shich is the value of the getter assigned by `getGetter`.
intrinsic ExactpAdics_GeneralGetter(state, getGetter, getValue) -> ExactpAdics_Gettr
  {Alternative getter where getGetter(~st,~g) gets a getter g which is evaluated to gval before calling getValue(gval,~st,~val).}
  return ExactpAdics_Getter(rec<recformat<gg,st,g,gst>|gg:=true,st:=state,g:=false,gst:=false>,
    procedure (~st, ~deps)
      if st`gg then
        getGetter(~st`st, ~st`g);
        st`gst := st`g`state;
        st`gg := false;
      end if;
      st`g`getDeps(~st`gst, ~deps);
    end procedure,
    procedure (~st, ~val)
      st`g`getValue(~st`gst, ~gval);
      if assigned gval then
        getValue(gval, ~st`st, ~val);
        st`gg := true;
      end if;
    end procedure);
end intrinsic;

///### Evaluation

intrinsic Evaluate(g :: ExactpAdics_Gettr) -> .
  {Evaluates the getter and retuns its value.}
  st := g`state;
  repeat
    ds := [**];
    g`getDeps(~st, ~ds);
    satisfy_deps_list(ds, Infinity());
    g`getValue(~st, ~val);
  until assigned val;
  if assigned g`explode then
    return Explode(val);
  else
    return val;
  end if;
end intrinsic;

///hide
intrinsic Print(g :: ExactpAdics_Gettr)
  {Prints g.}
  printf "Getter";
end intrinsic;

///## Composition

CALL_LIST :=
  [ func<f, x | f()>
  , func<f, x | f(x[1])>
  , func<f, x | f(x[1], x[2])>
  , func<f, x | f(x[1], x[2], x[3])>
  , func<f, x | f(x[1], x[2], x[3], x[4])>
  , func<f, x | f(x[1], x[2], x[3], x[4], x[5])>
  , func<f, x | f(x[1], x[2], x[3], x[4], x[5], x[6])>
  ];

function callList(f, x, n)
  error if #x lt n, "x too short";
  error if n lt 0, "n negative";
  error if n+1 gt #CALL_LIST, "only implemented for n up to", #CALL_LIST+1, "arguments";
  return CALL_LIST[n+1](f, x);
end function;

intrinsic Apply(f, g :: ExactpAdics_Gettr) -> ExactpAdics_Gettr
  {Applies f to the output of g.}
  return ExactpAdics_Getter(g`state, g`getDeps, procedure (~st, ~val)
    g`getValue(~st, ~val);
    if assigned val then
      if assigned g`explode then
        val := callList(f, val, g`explode);
      else
        val := f(val);
      end if;
    end if;
  end procedure);
end intrinsic;

intrinsic Compose(g :: ExactpAdics_Gettr, f) -> ExactpAdics_Gettr
  {"}
  return Apply(f, g);
end intrinsic;

intrinsic ApplyProcedure(f, g :: ExactpAdics_Gettr : Value:=true) -> ExactpAdics_Gettr
  {Applies the procedure f to the output of g, and sets the output Value.}
  return ExactpAdics_Getter(g`state, g`getDeps, procedure (~st, ~val)
    g`getValue(~st, ~val);
    if assigned val then
      f(val);
      val := Value;
    end if;
  end procedure);
end intrinsic;

intrinsic ComposeProcedure(g :: ExactpAdics_Gettr, f : Value:=true) -> ExactpAdics_Gettr
  {"}
  return ApplyProcedure(f, g : Value:=Value);
end intrinsic;

intrinsic ApplyGetter(f, g :: ExactpAdics_Gettr : AllowConst:=false) -> ExactpAdics_Gettr
  {The getter which returns the return value of f(return value of g). If AllowConst is false then f must return a getter; if true then f may return a non-getter, in which case this is the value of the returned getter.}
  return ExactpAdics_Getter([*false, g`state, false*], procedure (~st, ~deps)
    if st[1] then
      st[2]`getDeps(~st[3], ~deps);
    else
      g`getDeps(~st[2], ~deps);
    end if;
  end procedure,
  procedure (~st, ~val)
    if st[1] then
      st[2]`getValue(~st[3], ~val);
    else
      g`getValue(~st[2], ~v);
      if assigned v then
        if assigned g`explode then
          fv := callList(f, v, g`explode);
        else
          fv := f(v);
        end if;
        if Type(fv) eq ExactpAdics_Gettr then
          st[1] := true;
          st[2] := f(v);
          st[3] := st[2]`state;
        elif AllowConst then
          val := fv;
        else
          error "did not return a Getter";
        end if;
      end if;
    end if;
  end procedure);
end intrinsic;

intrinsic 'mod'(g :: ExactpAdics_Gettr, f) -> ExactpAdics_Gettr
  {"}
  return ApplyGetter(f, g : AllowConst);
end intrinsic;

intrinsic ApplyGetter(f, gs :: [ExactpAdics_Gettr] : AllowConst:=false) -> ExactpAdics_Gettr
  {The getter which returns the return value of f(return value of gs[1], ...).}
  return Apply(f, Flatten(gs) / #gs);
end intrinsic;

intrinsic 'mod'(gs :: [ExactpAdics_Gettr], f) -> ExactpAdics_Gettr
  {"}
  return ApplyGetter(f, gs);
end intrinsic;

intrinsic ComposeGetter(g :: ExactpAdics_Gettr, f) -> ExactpAdics_Gettr
  {"}
  return ApplyGetter(f, g);
end intrinsic;

///### Reductions

intrinsic Flatten(gs :: [ExactpAdics_Gettr] : Sequence:=false, Universe:=false) -> ExactpAdics_Gettr
  {The getter whose value is the list of values of the given gettrs. If Sequence is true, the value is coerced to a sequence. If Universe is given, the value is coerced to a sequence with this universe.}
  if #gs eq 0 then
    return ExactpAdics_ConstGetter([**]);
  elif #gs eq 1 then
    return gs[1] mod function (val)
      if Universe cmpne false then
        return [Universe | val];
      elif Sequence then
        return [val];
      else
        return [*val*];
      end if;
    end function;
  else
    return ExactpAdics_Getter([*[*g`state, false, false*] : g in gs*],
      procedure (~st, ~deps)
        for i in [1..#gs] do
          if not st[i][2] then
            ds := [**];
            gs[i]`getDeps(~st[i][1], ~ds);
            deps cat:= LIST(ds);
          end if;
        end for;
      end procedure,
      procedure (~st, ~val)
        done := true;
        for i in [1..#gs] do
          if not st[i][2] then
            gs[i]`getValue(~st[i][1], ~v);
            if assigned v then
              st[i][2] := true;
              st[i][3] := v;
              delete v;
            else
              done := false;
            end if;
          end if;
        end for;
        if done then
          if Universe cmpne false then
            val := [Universe| s[3] : s in st];
          elif Sequence then
            val := [s[3] : s in st];
          else
            val := [*s[3] : s in st*];
          end if;
        end if;
      end procedure);
  end if;
end intrinsic;

intrinsic '&cat'(gs :: [ExactpAdics_Gettr]) -> ExactpAdics_Gettr
  {The getter whose value is the sequence of values of gs.}
  return Flatten(gs : Sequence);
end intrinsic;

///hide
intrinsic '/'(g :: ExactpAdics_Gettr, n :: RngIntElt) -> ExactpAdics_Gettr
  {Modifies g so that it returns the first n values of its return value.}
  g`explode := n;
  return g;
end intrinsic;

///### Short-circuit reductions

intrinsic ShortCircuitReduce(gs :: [ExactpAdics_Gettr], f) -> ExactpAdics_Gettr
  {Given a function f taking any subsequence of S=[<i, Evaluate(gs[i])> : i in [1..#gs]] and returning either false,_ when the result is unknown or true,val when the result is known, where val is independent of the subsequence of S, returns the getter which evaluates to val. f(S) must return true.}
  // trivial case
  ok, x := f([]);
  if ok then
    return ExactpAdics_ConstGetter(x);
  end if;
  n := #gs;
  // general case
  STATE := recformat<g, st, val>;
  return ExactpAdics_Getter(
    [rec<STATE | g:=g, st:=g`state> : g in gs],
    procedure (~st, ~deps)
      for i in [1..#st] do
        if not assigned st[i]`val then
          ds := [**];
          st[i]`g`getDeps(~st[i]`st, ~ds);
          deps cat:= ds;
        end if;
      end for;
    end procedure,
    procedure (~st, ~val)
      S := [];
      got_new := false;
      for i in [1..#st] do
        if assigned st[i]`val then
          Append(~S, <i, st[i]`val>);
        else
          st[i]`g`getValue(~st[i]`st, ~v);
          if assigned v then
            st[i]`val := v;
            Append(~S, <i, v>);
            got_new := true;
            delete v;
          end if;
        end if;
      end for;
      assert got_new or #S lt n;
      if got_new then
        ok, x := f(S);
        error if #S eq n and not ok, "did not return true";
        if ok then
          val := x;
        end if;
      end if;
    end procedure);
end intrinsic;

intrinsic Exists(gs :: [ExactpAdics_Gettr]) -> ExactpAdics_Gettr
  {The getter whose value is true iff there exists g in gs so that f(Evaluate(g)) is true.}
  return ShortCircuitReduce(gs, function (xs)
    ok := exists{x : x in xs | x[2]};
    return ok or #xs eq #gs, ok;
  end function);
end intrinsic;

intrinsic ForAll(gs :: [ExactpAdics_Gettr]) -> ExactpAdics_Gettr
  {The getter whose value is true iff for all g in gs f(Evaluate(g)) is true.}
  return ShortCircuitReduce(gs, function (xs)
    ok := exists{x : x in xs | not x[2]};
    return ok or #xs eq #gs, not ok;
  end function);
end intrinsic;

// TODO: more general getter, consisting only of
//       (a) an initial state; and
//       (b) a procedure(~state, ~deps, ~value)
//       where the procedure either
//       (a) assigns a value (the output); or
//       (b) assigns deps (a list of <x,n> pairs or other getters) and
//           value (a procedure(~st, depvals) called on the result
//           of the dependencies)
//           
// e.g. Getter(false, procedure(~st, ~deps, ~val)
//        if st then
//          val := true;
//        else
//          deps := [* [* x, n *] *];
//          val := procedure (~st, dvs)
//            st := true;
//          end procedure;
//        end if;
//      end procedure);
//      
// e.g. Getter([* false, 10, false *], procedure (~st, ~deps, ~val)
//        if st[1] then
//          ... compute something ...
//          if done then
//            ~val := ...;
//            return;
//          else
//            st[2] +:= ...;
//          end if;
//        end if;
//        deps := [* ... *];
//        val := procedure (~st, vals)
//          st[1] := true;
//        end procedure;
//      end procedure);

// TODO: A getter consisting of an initial state, and a function taking state and returning either a value or a list of dependencies and a function taking the results of the dependencies and updating the state and a new getter function
//       
// e.g. Getter([
//        procedure (~g)
//          g`state := pr;
//        end procedure,
//        procedure (~g)
//          g`deps := Approximation_Lazy(F, ~g`state);
//        end procedure,
//        procedure (~g)
//          xF, Ftox := Explode(g`depvalues);
//          g`deps := [Ftox(x), ...];
//        end procedure,
//        procedure (~g)
//          ...
//          if done then
//            g`value := ...;
//          else
//            g`state +:= ...;
//            g`jumpto := 2;
//          end if;
//        end procedure
//      ]);
//      
// e.g. Getter([
//        procedure (~st)
//          
//        end procedure
//      ])

// GETTER_STATE := recformat<value, deps, depvalues, jumpto>;

// intrinsic Evaluate(g :: ExactpAdics_Gettr) -> .
//   {Evaluates g.}
//   st := rec<GETTER_STATE |>;
//   i := 1;
//   while true do
//     // call the relevant procedure
//     g`procs[i](~st);
//     // done?
//     if assigned st`value then
//       return st`value;
//     end if;
//     // dependencies?    
//     if assigned st`deps then
//       st`depvalues := evaluateDependencies(st`deps);
//       delete st`deps;
//     end if;
//     // next index
//     if assigned st`jumpto then
//       i := st`jumpto;
//       delete st`jumpto;
//     else
//       i := i + 1;
//     end if;
//   end while;
// end intrinsic;

// In the following, g`evaluate is a magic function which, to the user, simply evaluates the given getter and returns its value. In fact, it is a hook which can then go and call the function of another getter, if required, and so on recursively, giving the impression of concurrency. This allows for the dependencies to be accumulated and evaluated at once.
// 
// Getter(function (g)
//   xF, Ftox := Approximation_Lazy(F, pr) @ g`evaluate @ Explode;
//   xx, xy := &cat[Ftox(x : Lazy), Ftox(y : Lazy)] @ g`evaluate @ Explode;
//   Update(z, xx/xy);
//   return true;
// end function);
// 
// For example, suppose we have two getter functions a and b and we want to evaluate them:
// 
// st`count := 0;
// st`ag := rec<...| evaluate := function (x)
//   st`adeps := depsFor(x);
//   st`count +:= 1;
//   
// end function>;
// st`aval := a`func(st`ag);
// 
// Ummmmmm I don't think this is possible in Magma right now (it requires something like Python's yield). You probably need to have separate functions for each section of code between the evaluations, like with the version above where a getter is a sequence of procedures.