NOTES

4/26/2018

- I'm trying to get a simple example compiling fib as a string to work.  It
  appears I need the full Prelude (need "failure," for instance, and surely
  more).

    - I also need "otherwise," but I can work around that for now.

- To get the prelude, I will copy from CMC/runtime/lib.  But there is already a
  Prelude module in the interpreter that defines the built-ins.  I somehow need
  to resolve this.

    - Maybe give the built-ins a special name like _Prelude.  And then merge
      the two with custom code.
    - Or is there an equivalent to 'from _Prelude import *' that I can put in
      the real prelude?  I don't think so, because the Prelude actually
      forward-declares, with "external," the things it expects the
      implementation to provide.

TODO
  - Clean up the name Prelude from system.py
  - Change the name of system.py.  It looks like a Python module, but it is
    really a Curry module.
  - It seems annoying to import _System and then copy everything into the
    Prelude.  All references to _System would need to be updated.  Perhaps it
    would be better to call the _System module Prelude after all, and then 1)
    import it, 2) delete it from interp.modules, 3) import the "real" Prelude,
    and 4) merge the contents.

4/29/2018

- I should split up and rename tests/test_py_target.py.  A lot of things in
  there are not specifically related to the Python backend.  Those are really
  interpreter tests that don't relate the the backend at all.  Furthermore, the
  file is just too big and unweildy.  For now, I'm taking the step to create a
  new file to test Prelude.apply.  I think it would be better to make a
  directory containing interpreter/test_*.py files.

5/1/2018

- I got this explanation regarding flexible/rigid tables from Sergio:

      The meaning of flexible/rigid (it applies ot both a case and a function)
      is whether a variable can be instantiated by a pattern.  Consider the
      following program:

        mynot x  = case x of {True -> False; False -> True}
        main = mynot x where x free

      Since the case is rigid the evaluation of main suspends.

      However, if you replace "case" with "fcase" the evaluation of main
      produces both False and True because x is bound to True and False,
      respectively.

5/2/2018

- I fixed an error in the icurry _Base class.  There were comparison methods,
  but no hash.  I took a while to track that one down.
- I'm working on adding support for ICurry BTables.  I got down to the place
  in function_compiler.py where the BTable just needs to be handled  The code
  will be similar to the code handling ATables.

5/3/2018

- I added the sendMoreMoney cryptarithmetic puzzle.  It is a good test for
  residuation: with residuation it finishes instantly whereas a narrowing
  strategy exhausts all memory.  Sergio suggests the following implementation:

      In a flex case, you have code to instantiate a variable.  In a rigid
      case, you could have code to put the expression at the end of the queue.
      If in the queue you have only expressions that were put there for this
      reason, the program suspends.

5/5/2018

- I finished up the BTable code in function_compiler.py.  The BTables can be
  compiled and run.
- I refactored the unit tests.  test_py_target was too big, so I broke it into
  several smaller files for testing interpretation, compiling, and the runtime
  aspects.
- I reworked the isa function a little and added helpers like isa_list and
  isa_tuple.

BUGS:
  - I noticed that test_atable and similar tests are slow even in subsequent
    runs.  I don't think curry2json should be invoked if the .json file already
    exists, so this is unexpected.
  - After I change a .curry file, curry.import_ fails to rerun curry2json.  I
    was using test_atable in test_py_evaluation.py.
  -When curry2json fails, there is no informative error message.

NEXT:
  - I should pare down the prelude so it can be loaded and then try to get the
    fib program working.

5/9/2018

- I started trying to cut down the Prelude, but quickly ran into the issue from
  5/5.  I fixed the importer module so that the JSON is rebuilt when the source
  file is newer.

5/20/2018

- In conversions.py, I'd really like to use Python 3 keyword-only parameters.

      def expr(interp, arg, *args, target=None)

  Maybe it's worth migrating to Python 3 if it's not difficult.

- I need to clean up the typeinfo stuff.  The naming is not consistent.  In
  Interpreter there are things like ti_Failure, but it refers not to the typeinfo, but to the info table.

5/22/2018

- Working on docs and minor fixes that I come across in so doing.

5/23/2018

- I'm fixing the imports when compiling Curry expressions.  To import a dynamic
  module, it is necessary to keep its temporary directory around and update the
  CURRYPATH temporarily if an expression requires that module.

TODO:
  - Test the changes to Interpreter.import.  It now accepts a currypath argument.

5/24/2018

- I checked in some changes to CMC to append to rather than overwrite CURRYPATH.

- The import system needs further modifications.  Chapter 6 of the Curry report
  describes the import features.  I need to support symbol hiding, for one
  thing.  Also, symbols added by CMC appear in the main module.  Once symbols
  can be hidden, it would be nice to hide those as well.

5/25/2018

- I implemented what symbol-hiding I could without ICurry indicating which
  symbols are private.

5/26/2018

- I did some general clean up.  I renamed TypeInfo to NodeInfo and made some
  variable names involving it more consistent.  I tweaked the function for
  skipping FWD nodes (it should tolerate unboxed values, now, though I hadn't
  run into that limiatation yet).  I consolidated the various functions for
  node construction and rewriting.

9/6/2018

- I've been working hard on implementing constraints, but not using these
  notes.  I think it's a good idea to organize my thoughts, since the changes
  lately have tended to get quite complex.  I have been laboring under the
  faulty understanding that something like x == y where x,y free should
  instantiate variables whenever possible.  So, if the type of x is known to
  be, say Bool, then both x and y should be instantiated as Boolean generators.
  Actually, I need residuation here.  No matter what is known about these
  variables, this expression should always suspend until one of these is
  actually instantiated (in the proper context).

  As for my next steps, I'd really like to make progress on implementing ==.
  But given the above, it seems I need to implement residuation first.  Here
  are a few things that are small enough to bite off.

    1. Implement residuation.  Suppose the execution encounters x == y where
       x,y free.  I need to make a special Frame and place it at the end of the
       queue.  Its ``expr`` is just the == node.  When the frame is activated,
       it attempts a step.  If it succeeds, it unblocks the original frame,
       which is then added to the queue.  If all frames in the queue are of
       this type and none can make progress, then the computation fails with
       suspended constraints.
    2. Reorganize some code.  The runtime module is getting too large.  Also,
       the unit tests should have some directory structure and perhaps common
       subclasses.  It seems there are too may ways of doing the same things.

9/12/2018

- I've been reworking the core evaluation methods to more closely match the FS.
  Still, there are extensions for free variables, constraints, and residuation.
  There are many offshoots to circle back to.

    1. The Prelude functions implemented via py.func need to be reviewed.  The
       handler for that tag normalizes each successors, but that's often too
       strict.  It's probably better to just do the normalization manually in
       each implementation function to avoid making that type of mistake.
    2. Prelude.unknown returns a FWD node.  The FWD nodes can always be removed
       by copying the successors.
    3. The debug source files that are written for PDB should also dump the
       ICurry.

10/24/2020

- I'm going through the stashed code to clean up.  Most of the code is already
  in the master, and I'd rather just use this worklog instead of a branch to
  keep snips that might be useful later.  Here is something:

       class Constraints(object):
         def __init__(self, arg=None):
           if arg is None:
      -      # defaultdict = collections.defaultdict
      -      # # Holds the variable bindings.  There are two types: lazy and normal.  A
      -      # # lazy binding is between a variable and an unevaluated expression, used
      -      # # to implement =:<= for functional patterns.  A normal binding is between
      -      # # two free variables, used to implement =:=.  These bindings imply
      -      # # additional bindings between successor variables.  For example, if x_0
      -      # # :=: x_1 for two list variables, then after annotating x_0 = ([] ?_0
      -      # # (x_2:x_3)) and x_1 = ([] ?_1 (x_4:x_5)), we have two new bindings x_2
      -      # # :=: x_4 and x_3 :=: x_5.
             # self.vars = Shared(lambda: defaultdict(lambda: Shared(list)))
      -      self.choices = Shared(ChoiceStore)
      +      self.vars = Shared(UnionFind)
      +      self.choices = Shared(UnionFind)
           else:
      -      # self.vars = arg.vars
      +      self.vars = arg.vars
             self.choices = copy(arg.choices)

         def __copy__(self):

10/25/2020

- This one seems to be an optimization for variable instantiation.  It is not
  needed because pull-tabbing through the =:= operator can work out which
  constructors to use.

      +def _buildInstanceConstraint(interp, instance, cidx, N, constraints):
      +  '''
      +  Given an instance (generator) and constructor index, build the choice
      +  constraints needed to select that instance.
      +  '''
      +  if nctors == 1:
      +    return constraints
      +  else:
      +    middle = -(-N // 2) # e.g., 7 -> 4.
      +    cid = instance[0]
      +    if cidx < middle:
      +      constraints = _buildInstanceConstraint(
      +          instance[1], cidx, middle, constraints
      +        )
      +      return Node(
      +          interp.prelude._Constraint
      +        , constraints
      +        # Same here: can't use Pair.
      +        , Node(interp.prelude.Pair, cid, LEFT)
      +        )
      +    else:
      +      constraints = _buildInstanceConstraint(
      +          instance[2], cidx-middle, N-middle, constraints
      +        )
      +      return Node(
      +          interp.prelude._Constraint
      +        , constraints
      +        # Same here: can't use Pair.
      +        , Node(interp.prelude.Pair, cid, RIGHT)
      +        )
      +
      +
      +def buildInstanceConstraint(interp, instance, cidx, typedef):
      +  constructors = getattr(typedef, 'constructors', typedef)
      +  N = len(constructors)
      +  assert cidx < N
      +  assert instance.info.tag = T_CHOICE
      +  if N == 1: # (C ? failure)
      +    return Node(
      +        interp.prelude._Constraint
      +      , Node(interp.prelude.True)
      +        # FIXME: need to distinguish between node<=>node bindings and choice
      +        # constraints, below.  Probably shouldn't use a pair.
      +      , Node(interp.prelude.Pair, instance[0], LEFT)
      +      )
      +  else:
      +    return _buildInstanceConstraint(
      +        interp, instance, cidx, N, Node(interp.prelude.True)
      +      )
      +

- Here we have code to bind a variable to a constructor.  It serves a similar
  purpose.

      def _bindVarToCtor(self, interp, root, ctor, free):
        assert ctor.info.tag >= runtime.T_CTOR
        assert free.info.tag >= runtime.T_FREE

        gpath = ctor.info.gpath
        generator = runtime.getGenerator(interp, free, ctor.info.typedef())

        # The generator always begins with a choice, even for types with one
        # constructor.
        assert len(gpath)
        assert generator.info.tag == runtime.T_CHOICE

        # 1. Equate subterms.
        result = runtime.Node(
            *self._eqSubterms(interp, root.info, ctor, generator[gpath])
          )

        # 2. Bind choices.
        cids = tuple(runtime.get_ids(generator, gpath))
        for gindex,cid in zip(gpath[:0:-1], cids[:0:-1]):
          result = runtime.Node(
              interp.prelude._ChoiceConstr.info
            , result
            , interp.expr((unboxed(cid), unboxed(runtime.gindex_to_lr(gindex))))
            )
        yield interp.prelude._ChoiceConstr.info
        yield result
        yield interp.expr(
            (unboxed(cids[0]), unboxed(runtime.gindex_to_lr(gpath[0])))
          )

- Here is code related to building paths through (Curry) generators.

      def _build_gpath(ctor_id, num_ctors):
        if num_ctors < 2:
          # Special case for one constructor.  The generator must begin with a choice,
          # so the constructor is to the LEFT.
          yield 0  # LEFT index
        else:
          while num_ctors > 1:
            midpt = num_ctors - num_ctors // 2
            if ctor_id < midpt:
              num_ctors = midpt
              yield 0  # LEFT index
            else:
              num_ctors -= midpt
              ctor_id -= midpt
              yield 1  # RIGHT index

      def get_ids(generator, gpath):
        for i in gpath:
          assert generator.info.tag == T_CHOICE
          yield get_id(generator)
          generator = generator[i]
        assert generator.info.tag >= T_CTOR

      def gindex_to_lr(gindex):
        '''Converts an index with a gpath (see InfoTable) to either LEFT or RIGHT.'''
        assert gindex in (0,1)
        return LEFT if gindex == 0 else RIGHT

  And the update to the InfoTable for gpath:

      - __slots__ = ['name', 'arity', 'tag', '_step', 'show', 'typecheck', 'typedef']
      + __slots__ = ['name', 'arity', 'tag', '_step', 'show', 'typecheck', 'typedef', 'gpath']

  def __init__(self, name, arity, tag, step, show, typecheck):
    .
    .
    .
    + # The path to this constructor in the corresponding generator.  For
    + # instance, if the list type has generator (x:y) ? [], then constructor
    + # Const has gpath [0] and constructor Nil has gpath [1].  This is a normal
    + # path that can be used with Node.__getitem__, hence the indices 0 and 1.
    + self.gpath = None

 And here are the test updates.

    diff --git a/tests/unit_py_runtime.py b/tests/unit_py_runtime.py
    index d01dab8..36e8aad 100644
    --- a/tests/unit_py_runtime.py
    +++ b/tests/unit_py_runtime.py
    @@ -309,6 +309,13 @@ class TestInstantiation(cytest.TestCase):
         instance = runtime.instantiate(interp, e, [0], interp.type('Type.T'))
         au = curry.expr(*q(0, q(1, q(2, Type.A, Type.B), q(3, Type.C, Type.D)), q(4, q(5, Type.E, Type.F), Type.G)))
         self.assertEqual(instance, au)
    +    self.assertEqual(Type.A.info.gpath, (0,0,0))
    +    self.assertEqual(Type.B.info.gpath, (0,0,1))
    +    self.assertEqual(Type.C.info.gpath, (0,1,0))
    +    self.assertEqual(Type.D.info.gpath, (0,1,1))
    +    self.assertEqual(Type.E.info.gpath, (1,0,0))
    +    self.assertEqual(Type.F.info.gpath, (1,0,1))
    +    self.assertEqual(Type.G.info.gpath, (1,1))

       def test_minDepth6(self):
         '''Minimal instance depth (6 constructors).'''
    @@ -321,6 +328,12 @@ class TestInstantiation(cytest.TestCase):
         instance = runtime.instantiate(interp, e, [0], interp.type('Type.T'))
         au = curry.expr(*q(0, q(1, q(2, Type.A, Type.B), Type.C), q(3, q(4, Type.D, Type.E), Type.F)))
         self.assertEqual(instance, au)
    +    self.assertEqual(Type.A.info.gpath, (0,0,0))
    +    self.assertEqual(Type.B.info.gpath, (0,0,1))
    +    self.assertEqual(Type.C.info.gpath, (0,1))
    +    self.assertEqual(Type.D.info.gpath, (1,0,0))
    +    self.assertEqual(Type.E.info.gpath, (1,0,1))
    +    self.assertEqual(Type.F.info.gpath, (1,1))

       def test_complex(self):
         #        ?0
    @@ -332,3 +345,8 @@ class TestInstantiation(cytest.TestCase):
         instance = runtime.instantiate(interp, e, [0], interp.type('Type.T'))
         au = curry.expr(*q(0, q(1, q(2, Type.A, [Type.B, u]), [Type.C, u, u]), q(3, [Type.D, u, u, u], [Type.E, u, u, u, u])))
         self.assertEqual(instance, au)
    +    self.assertEqual(Type.A.info.gpath, (0,0,0))
    +    self.assertEqual(Type.B.info.gpath, (0,0,1))
    +    self.assertEqual(Type.C.info.gpath, (0,1))
    +    self.assertEqual(Type.D.info.gpath, (1,0))
    +    self.assertEqual(Type.E.info.gpath, (1,1))


07/10/2021

  There is a new implementation of the Fair Scheme under
  src/python/backends/py/runtime/fairscheme.  Binding to integers is not
  implemented and will probably result in a hang or "evaluation suspended"
  message.

  This is a faithful representation of the FS as published, with extensions for
  free variables.  The value of a computation can contain free variables.

  Debugging
  ---------

  To play with it, cd to tests/ and then run e.g., "./run_tests
  func_examples.py".  You can control the behavior by setting environment
  variable SPRITE_INTERPRETER_FLAGS.  Important options:

      trace:true
          You will get a trace of each step in the computation.

      debug:true
          The compile source code will be placed under .src/.  You must use
          this option to step into compiled code with PDB.

  Example:

      % SPRITE_INTERPRETER_FLAGS=trace:true,debug:true ./run_tests func_example.py

  Call breakpoint() anywhere in the code to get an interactive prompt.  Use
  Ctrl-d to continue.

  Call pdbtrace() anywhere to start a PDB prompt.  You can go up and down the
  stack.  Use Ctrl-d to continue/exit.

  Test Cases
  ----------
  You can use the tests under tests/func_*.py.  func_examples.py matches the
  PDF files I sent before. func_eqconstr.py checks the equational constraints
  quite thoroughly.

  In a unit test under tests/func_*.py, use the RUN_ONLY and/or SKIP fields to
  control which tests are run.  Each accepts a regex.