TODO

Random TODO items for this Pyjure implementation in Clojure

* Need to actually resolve bindings in cleanup phase.
   Maybe split in two phases, binding-resolution before A-normalization
   and suite-simplification after.

* Need to group consecutive function definitions into a recursive
   letfn (Clojure) / labels (CL) / letrec (Scheme) /
   let (Haskell, which requires further alpha-conversion)

* write down some examples of generated code
   have a collection of simple functions that span
   the entire base language and its various interactions,
   and write down what the generated code would look like.

   def fib(n):
     if n == 0: return 0
     elif n == 1: return 1
     else: return fib(n-1) + fib(n-2)

   (defn fib$internal [n]
     (if (= n 0) ;; we know it's a boolean, so no $truthy required
         0 ;; return directly,
         ;; continuation not bound to a function,
         ;; because it's only called in one branch.
         (if (= n 1) 1
             (+ (fib$internal (- n 1)) (fib$internal (- n 2))))))
         ;; we can call internal function because it is known
   (def fib (one-arg-function fib$internal))


   def f(x):
     a = 1
     b = 2
     if x:
       a = 10
     else:
       b = 20
     return a+b

   (defn f [x]
     (let [a 1 b 2]
       (let [[a b] (if x [10 b] [a 20])]
         (+ a b))))


   def f(x):
     a = 1
     b = 2
     if x:
       return 10
     else:
       b = 20
     return a+b

   (defn f [x]
     (let [a 1 b 2]
       (if x 10
          (let [b 20]
            (+ a b)))))

   def f(x, y):
     a = 1
     b = 2
     if x:
       if y:
         return 5
       else:
         a = 10
     else:
       b = 20
     return a+b

   (defn f [x y]
     (let [[ret? a b]
             (if x
               (let [[ret? a] (if y [5 nil] [nil 10])]
                 [ret? a b])
               [nil nil 20])]
       (or ret (+ a b))))

   (defn f [x y]
     (let [[ret? a b]
             (if x
               ;; small number of extra variables just copied
               ;; in small number of branches with little computations.
               (if y [5 nil b] [nil 10 b])]
               [nil nil 20])]
       (if (not (nil? ret)) ret (+ a b)))

* enumerate effects that can be done by a block of code,
  that have to be accounted by some monad at runtime,
  and some state in the compile-time analysis.

  refer to variable [name, projection (e.g. as boolean; error if not list; etc.)]
  bind variable [name, type]
  return [type]
  yield [type]
  raise an exception [type]
     including implicit type mismatch!
  non-termination []
  re-bind an outside variable [variable] ;; FORBIDDEN
  side-effect the object bound to a variable [variable] ;; FORBIDDEN

  If none of these effects happens, the block can be moved
  earlier or later if used, and skipped altogether if not.


  at analysis-time, each effect is annotated with some domain
  (i.e. notional set of input conditions) over which the effect happens.
  :⊥ (don't know anything about this effect yet)
  false (effect never happens when this block is run)
  true (effect always happen if this block is run)
  :⊤ (effect may or may not happen if this block is run)

  Future versions can use more elaborate flow analyzes,
  but for now we want the minimum that can produce code that runs.

   pass bindings and binding-witnesses
   (or, use an unbound marker distinct from None?)
   lexical return
   skynode definitions as side-effect
   dynamic calling convention
   global state (NO!)
   [Compile time]
   analysis state(s)

* we need the effects for the current snippet and its block continuation.

* soup up analysis phase


* figure out how exceptions interact with shadowing of local bindings.
   In Python, x = v is a variable assignment side-effect, so
   the handler and continuation see the modified variables.
   In Pyjure, x = v is the shadowing of a binding, so
   the handler and continuation see the original bindings.

for target in gen:
   if ~foo: continue
   elif ~bar: break
   else a=f(a,target)
return a


  g# = gen
  while(seq(g#)):
    (target,g#) = decons(g#)
    if ~foo: c=c+e ; continue
    elif ~bar: b=c; break
    elif ~baz: return a
    elif ~quux: a=f(a,target)
    a = g(a)

  (let [[return? a b c]
   (loop [g# g#
          a  a
          b  b
          c  c]
   ;; e is refered but never modified, so needn't be returned
   ;; if any of a, b, c wasn't needed later,
   ;; it wouldn't be needed as a return function either.
    (if (seq g#)
       (let [d# (decons g#)
             target (first d#)
             g# (second d#)]
          (if ~foo (let [c ($add c e)] (recur g# a b c))
              (if ~bar (let [b c] [nil a b c])
                  (if ~baz [true a nil nil]
                      (let [a (f a target)]
                           (recur g# a b c))))))))]
   ;; because return is an option, call it
   ;; if it were either always return or never return, we wouldn't
   ;; need the conditional
   (if return? a ;; optimization: because a is the next position
       CONTINUATION))

   ;; could directly return, but then the other continuation would
   ;; have to be duplicated... optimization:
   ;; return directly if the *other* branch only appears once.
   ;; maybe we can ensure that's always the case?
   (loop [broken# false ;; optimization: make it a special value for g# ?
          g# g#
          a  a
          b  b
          c  c]
     (if (and (not broken#) (seq g#))
         (let [target (first g#)
               g# (rest g#)]
           (if ~foo (let [c ($add c e)] (recur false g# a b c))
              (if ~bar (let [b c] (recur true g# a b c))
                  (if ~baz a
                      (let [a (f a target)]
                           (recur false g# a b c))))))))]

   ;; e is refered but never modified, so needn't be returned
   ;; if any of a, b, c wasn't needed later,
   ;; it wouldn't be needed as a return function either.
    (if (seq g#)
       (let [d# (decons g#)
             target (first d#)
             g# (second d#)]
          (if ~foo (let [c ($add c e)] (recur g# a b c))
              (if ~bar (let [b c] [nil a b c])
                  (if ~baz [true a nil nil]
                      (let [a (f a target)]
                           (recur g# a b c))))))))]
   ;; because return is an option, call it
   ;; if it were either always return or never return, we wouldn't
   ;; need the conditional
   (if return? a ;; optimization: because a is the next position
       CONTINUATION))



* to preserve tail-position in for/while loops,
  we can't have tail-called into a continuation function.
  instead, we have to use some monadic transform to simulate return
  (or we could use an exception... yikes, no).

|---------------------+-------------------------------------------+---------------|
| Form                | Tail Position                             | recur target? |
|---------------------+-------------------------------------------+---------------|
| fn, defn            | (fn [args] expressions tail)              | Yes           |
| loop                | (loop [bindings] expressions tail)        | Yes           |
| let, letfn, binding | (let [bindings] expressions tail)         | No            |
| do                  | (do expressions tail)                     | No            |
| if, if-not          | (if test then tail else tail)             | No            |
| when, when-not      | (when test expressions tail)              | No            |
| cond                | (cond test test tail ... :else else tail) | No            |
| or, and             | (or test test ... tail)                   | No            |
| case                | (case const const tail ... default tail)  | No            |
|---------------------+-------------------------------------------+---------------|

* Annotate each function with its stack implicit monadic transform,
  know how to automatically call functions *lower* in the stack,
  error out if calling higher.
  Also available at runtime?
  Or make it always top of stack at runtime?
  Of course, generators have one more level than other functions...

* Yield can be implemented through a delimcc monad, to be added to the
   monad transformer stack.
   http://okmij.org/ftp/continuations/implementations.html

* Is this a bug in core.match?
   (match [[1 2 3 4]] [[(or 0 1 2) :as x & more]] [x more])
   ==> CompilerException java.lang.RuntimeException: Unable to resolve
   symbol: x in this context, compiling:(null:1:1)
   workaround:
   (match [[1 2 3 4]] [[x :guard #{0 1 2} & more]] [x more])

* macroexpand class in terms of the following constructs:
   environment -- create a dict capturing all currently bound variables
   @method -- decorator around method functions that binds next_method, etc.

* express generators in terms of this construct:
   trampolines that capture those variables that are still needed.
   that's effectively a slightly different code generator,
   one that enables delimited continuations, but requires
   the caller to be a trampoline.

* Environments
;; nonlocals globals


;; A (local) Environment maps identifiers to values, and has an optional parent Environment
;; We only need it for macros. Actually, if we stick to global macros that can't be shadowed,
;; we don't need it at this stage.
(defrecord Environment [vars parent])

;; effects are things that may happen within a scope.
;; at every point, we compute the effects before and after that point in the current scope;
;; effects are thus a monoid that can be composed forward and backward.
(defrecord Effects [vars yield?])
(def null-effects (->Effects #{} false))

;; TODO: adapt what environments we store to what we actually need later
;; TODO: maybe store for each expression the state of the environment before it?
;;   can be slightly tricky in a branch inside a loop:
;;   which bindings exactly are visible from there?
;;   Probably a latter pass.

* use core.typed for type analysis?
  Or retarget to Haskell instead of Clojure?

* each computation happens in a tower of effect monads,
  with effects a subset of the set of all effects.
  to combine c1 in m1 and c2 in m2,
  write respective adapters into union(m1,m2) and bind.

* Q: what does python3 do of a global or nonlocal declaration at toplevel?
  nonlocal is an error, global is ignored (or inherited?)

* We probably want dynamic scoping for some variables.
 To know about dynamic scoping in plain python:
   http://stackoverflow.com/questions/2001138/how-to-create-dynamical-scoped-variables-in-python
 See the solution that goes as follows:
   with env.let(bufsize=8192, encoding="ascii"):
    print env.bufsize  # prints 8192
    a()  # call a function that uses env.bufsize or env.encoding
 And is implemented in python by:
_stack = []

class _EnvBlock(object):
    def __init__(self, kwargs):
        self.kwargs = kwargs
    def __enter__(self):
        _stack.append(self.kwargs)
    def __exit__(self, t, v, tb):
        _stack.pop()

class _Env(object):
    def __getattr__(self, name):
        for scope in reversed(_stack):
            if name in scope:
                return scope[name]
        raise AttributeError("no such variable in environment")
    def let(self, **kwargs):
        return _EnvBlock(kwargs)
    def __setattr__(self, name, value):
        raise AttributeError("env variables can only be set using `with env.let()`")

env = _Env()
* We want to track which unshadowed bindings of such variables were
   used, though, and include them in the cache signature.

* At some point, deal with at least the easy case of
   https://docs.python.org/3.5/reference/import.html
** Start with reimplementing the same load that Skylark currently
   uses.