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 -