Turner 1979 "A New Implementation Technique for Applicative Languages"
https://pdfs.semanticscholar.org/e32e/062c1288c05bbb1ab02526fda5e1d4f77681.pdf

Purity of Haskell - simplicity of Lisp!


Super simple!
Program is a tree where nodes are (App _ _) and leaves are S, K, plus, ...
Source lang is untyped, has destructuring bind.

You get awesome stuff for free!
- runtime doesn't care about scope
- graph reduction -> self optimizing

Problems:
- graph updates lead to cycles; cycles lead to GC
  - can you get the self-optimizing behavior with acyclic terms?
    - maybe you can turn cycles back into Y somehow?
- can other tree representations avoid pointers?
- call-by-need is confusing because
    - data can be bottom
    - data can be cyclic or infinitely large
    - hard to reason about resource usage
  - maybe use call-by-value instead
    - but then cond isn't free
    - maybe this gives you eager optimization?
BUT OTOH:
- call-by-need is neat because
  - cond is free
  - (NO) inspecting not-yet-evaluated terms could make sense
    - usually inspecting a value forces it
    - what you actually want is to inspect *function-values* which are *data*,
      not redexes.
- maybe nontermination could be fixed with a termination checker
  - but see Noether argument for why failure can't be eliminated
BUT OTOH:
- call-by-need and call-by-value seem to *both* break equational reasoning if you have effects:
  https://www.cs.bham.ac.uk/~pbl/papers/cbpvefftt.pdf
    - and isn't nontermination an effect, like that slideshow's "error" effect?

TODO:
- write ski.rkt, with a reify macro that creates Turner combinators
- test examples of higher-order functions like foldr and thrice:
    - do they simplify to the hand-written version?
    - can evaluation be *too* eager? (diverge at compile time)






    
CONSTRUCTORS:
- you can't inspect a partially-applied constructor

building block:  tryunpack v tag handler default

tryunpack v P (\x y. E) fail


map f [] = []
map f (x:xs) = x:(map f xs)

map f lst = case lst of
| [] -> []
| x:xs -> x:(map f xs)

map = \f lst.
tryunpack lst Empty Empty $
tryunpack lst Pair \x xs. x:(map f xs)

problems:
- type is crazy: number of args depends on a value
- rewrite rules could be simpler


caser tag handler default value

map f =
(caser Empty Empty)
(caser Pair \x xs. x:(map f xs))

map f lst =
(
(caser Empty Empty)
(caser Pair \x xs. x:(map f xs))
) lst

caser Empty :: a            -> (MaybeEmpty -> a) -> MaybeEmpty -> a
caser Pair :: (x -> y -> a) -> (MaybePairXY -> a) -> MaybePairXY -> a

caser Empty t f Empty       => t
caser Empty t f (Pair x y)  => f (Pair x y)

caser Pair t f (Pair x y) => t x y
caser Pair t f Empty      => f Empty

in general:
caser C  t f (C args ...) => t args ...
caser C' t f (C args ...) => f (C args ...)

caser C :: (fields ... -> out) -> (in -> out) -> in -> out
.          t                      f

https://www.classes.cs.uchicago.edu/archive/2011/spring/22620-1/papers/pettersson92.pdf


So TODO for constructors:
- caser to decompose things (TODO better name)
- way to define a new constructor
  - "new" ? as in gensym? not referentially transparent?
- maybe a constructor should be a value?
- the name is not enough: you also need the arity.


so it sounds like I need:
- (constructor name arity)
  - name is important for the value because not all 2-ctors (3-ctors, etc) are equal.
- strings
-