4 ms·

In re: CT see also Conal Elliott's "Compiling to categories" http://conal.net/papers/compiling-to-categories/ http://conal.net/papers/compiling-to-categories/

• carapace 6y ago
  FWIW, here's an example of a simple programming task in Joy, the derivation of the step combinator. It might not make a lot of sense without familiarity with Joy, however, the thing to notice is the smooth algebraic form of programming. Making simple obvious decisions at each point leads to a concise and correct program. That's "the function-level programming style of John Backus's FP." in action. You can do it in Haskell (et. al.) too but I find it much easier in Joy. YMMV. The step combinator accepts a list and a quoted program and runs the program on each item in the list in turn. (Use it to write e.g. sum of list of ints, etc.) [] [P] step ----------------- Empty list, no-op. [X|Xs] [P] step ----------------------- Non-empty list, run P and recur. X P [Xs] [P] step In terms of branch and x: step == [F] x So: [L] [P] step ------------------ [L] [P] [F] x ------------------ [L] [P] [F] F First, get the flag value and roll< it to the top for a branch: F == F′ F″ F′ == [?] dipd roll< [L] [P] [F] F --------------------------- [L] [P] [F′ F″] F′ F″ --------------------------------------- [L] [P] [F′ F″] [?] dipd roll< F″ How that works out: [L] [P] [F] [?] dipd roll< F″ [L] ? [P] [F] roll< F″ [L] b [P] [F] roll< F″ [L] [P] [F] b F″ Now we can write a branch: F″ == [Ff] [Ft] branch [L] [P] [F] b F″ ------------------------------------ [L] [P] [F] b [Ff] [Ft] branch The false case is easy: Ff == pop popop ... [] [P] [F] Ff ... [] [P] [F] pop popop ... [] [P] popop ... The true case is a little more fun: ... [X|Xs] [P] [F] Ft We need to uncons that first term, run a copy of P, and recur (recurse? I think re-curse means to "curse again" so it must be "recur".) Ft == Ft′ Ft″ Ft′ == [uncons] dipd ... [X|Xs] [P] [F] [uncons] dipd Ft″ ... [X|Xs] uncons [P] [F] Ft″ ... X [Xs] [P] [F] Ft″ So now we run a copy of P: ... X [Xs] [P] [F] Ft″ Ft″ == [dup dipd] dip Ft‴ ... X [Xs] [P] [F] Ft″ ... X [Xs] [P] [F] [dup dipd] dip Ft‴ ... X [Xs] [P] dup dipd [F] Ft‴ ... X [Xs] [P] [P] dipd [F] Ft‴ ... X P [Xs] [P] [F] Ft‴ And now all that remains is to recur on F: Ft‴ == x ... X P [Xs] [P] [F] x Collecting the definitions, we have: step == [F] x F == F′ [Ff] [Ft] branch F′ == [?] dipd roll< Ff == pop popop Ft == Ft′ Ft″ x Ft′ == [uncons] dipd Ft″ == [dup dipd] dip