Continuation Passing Style and Macros in Clojure - Jan 2012

Continuation-passing style and Macros with Clojure Leonardo Borges @leonardo_borges http://www.leonardoborges.com http://www.thoughtworks.com

CPS in a nutshell • not new. It was coined in 1975 by Gerald Sussman and Guy Steele • style of programming where control is passed explicitly in the form of a continuation • every function receives an extra argument k - the continuation • makes implicit things explicit, such as order of evaluation, procedure returns, intermediate values... • used by functional language compilers as an intermediate representation (e.g.: Scheme, ML, Haskell)

CPS - Pythagorean theorem You know the drill... a² + b² = c² ;;direct style (defn pyth [a b] (+ (* a a) (* b b)))

CPS - Pythagorean theorem You know the drill... a² + b² = c² ;;direct style (defn pyth [a b] (+ (* a a) (* b b))) ;;CPS (defn pyth-cps [a b k] (*-cps a a (fn [a2] (*-cps b b (fn [b2] (+-cps a2 b2 k))))))

Untangling pyth-cps ;;CPS (defn *-cps [x y k] (k (* x y))) (defn +-cps [x y k] (k (+ x y))) (defn pyth-cps [a b k] (*-cps a a (fn [a2] (*-cps b b (fn [b2] (+-cps a2 b2 k))))))

Untangling pyth-cps ;;CPS (defn *-cps [x y k] (k (* x y))) (defn +-cps [x y k] (k (+ x y))) (defn pyth-cps [a b k] (*-cps a a (fn [a2] (*-cps b b (fn [b2] (+-cps a2 b2 k)))))) (pyth-cps 5 6 identity) ;61

CPS - Fibonacci ;;direct style (defn fib [n] (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))

CPS - Fibonacci ;;CPS (defn fib-cps [n k] (letfn [(cont [n1] (fib-cps (- n 2) (fn [n2] (k (+ n1 n2)))))] (if (<= n 1) (k n) (recur (- n 1) cont)))) (fib-cps 20 identity);55

Another look at CPS Think of it in terms of up to three functions: • accept: decides when the computation should end • return continuation: wraps the return value • next continuation: provides the next step of the computation

CPS - Fibonacci ;;CPS (defn fib-cps [n k] (letfn [(cont [n1] (fib-cps (- n 2) (fn [n2] (k (+ n1 n2)))))] (if (<= n 1) (k n) (recur (- n 1) cont)))) accept function (fib-cps 20 identity);55

CPS - Fibonacci ;;CPS (defn fib-cps [n k] (letfn [(cont [n1] (fib-cps (- n 2) (fn [n2] (k (+ n1 n2)))))] (if (<= n 1) (k n) return continuation (recur (- n 1) cont)))) (fib-cps 20 identity);55

CPS - Fibonacci ;;CPS (defn fib-cps [n k] next continuation (letfn [(cont [n1] (fib-cps (- n 2) (fn [n2] (k (+ n1 n2)))))] (if (<= n 1) (k n) (recur (- n 1) cont)))) (fib-cps 20 identity);55

CPS - generic function builders (defn mk-cps [accept? end-value kend kont] (fn [n] ((fn [n k] (let [cont (fn [v] (k (kont v n)))] (if (accept? n) (k end-value) (recur (dec n) cont)))) n kend)))

CPS - generic function builders ;;Factorial (def fac (mk-cps zero? 1 identity #(* %1 %2))) (fac 10); 3628800 ;;Triangular number (def tri (mk-cps zero? 1 dec #(+ %1 %2))) (tri 10); 55

Seaside - a more practical use of CPS • continuation-based web application framework for Smalltalk • UI is built as a tree of independent, stateful components • uses continuations to model multiple independent flows between different components

Seaside - a more practical use of CPS • continuation-based web application framework for Smalltalk • UI is built as a tree of independent, stateful components • uses continuations to model multiple independent flows between different components • memory intensive • not RESTful by default

Seaside - Task example [1] go " [ self chooseCheese. " self confirmCheese ] whileFalse. " self informCheese [1] Try it yourself (http://bit.ly/seaside-task)

Seaside - Task example chooseCheese " cheese := self " " chooseFrom: #( 'Greyerzer' 'Tilsiter' 'Sbrinz' ) " " caption: 'What''s your favorite Cheese?'. " cheese isNil ifTrue: [ self chooseCheese ] confirmCheese " ^ self confirm: 'Is ' , cheese , 'your favorite Cheese?' informCheese " self inform: 'Your favorite is ' , cheese , '.'

CPS - Other real world usages • web interactions ~ continuation invocation [2] • event machine + fibers in the Ruby world [3] • functional language compilers • ajax requests in javascript - callbacks anyone? • node.js - traditionally blocking functions take a callback instead • ... [2] Automatically RESTful Web Applications (http://bit.ly/ydltH6) [3] Untangling Evented Code with Ruby Fibers (http://bit.ly/xm0t51)

Macros If you give someone Fortran, he has Fortran. If you give someone Lisp, he has any language he pleases. - Guy Steele

Macros • Data is code is data • Programs that write programs • Magic happens at compile time • Most control structures in Clojure are built out of macros

e.g.: avoiding nesting levels (def guitar {:model "EC-401FM" :brand "ESP" :specs { :pickups {:neck {:brand "EMG" :model "EMG 60"} :bridge {:brand "EMG" :model "EMG 81"}} :body "Mahoganny" :neck "Mahoganny"}})

e.g.: avoiding nesting levels (def guitar {:model "EC-401FM" :brand "ESP" :specs { :pickups {:neck {:brand "EMG" :model "EMG 60"} :bridge {:brand "EMG" :model "EMG 81"}} :body "Mahoganny" :neck "Mahoganny"}}) (:model (:neck (:pickups (:specs guitar))))

e.g.: avoiding nesting levels what if we could achieve the same like this instead? (t guitar :specs :pickups :neck :model)

Macros to the rescue! (defmacro t ([v form] (if (seq? form) `(~(first form) ~v ~@(rest form)) (list form v))) ([v form & rest] `(t (t ~v ~form) ~@rest)))

Macros to the rescue! (defmacro t ([v form] (if (seq? form) `(~(first form) ~v ~@(rest form)) (list form v))) ([v form & rest] `(t (t ~v ~form) ~@rest))) (t guitar :specs :pickups :neck :model)

Quoting Prevents evaluation (def my-list (1 2 3))

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn (def my-list '(1 2 3)) ;Success!

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn (def my-list '(1 2 3)) ;Success! 'my-list ;my-list

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn (def my-list '(1 2 3)) ;Success! 'my-list ;my-list '(1 2 3) ;(1 2 3)

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn (def my-list '(1 2 3)) ;Success! 'my-list ;my-list '(1 2 3) ;(1 2 3) Syntax-quote: automatically qualifies all unqualified symbols

Quoting Prevents evaluation (def my-list (1 2 3)) ;java.lang.Integer cannot be cast to clojure.lang.IFn (def my-list '(1 2 3)) ;Success! 'my-list ;my-list '(1 2 3) ;(1 2 3) Syntax-quote: automatically qualifies all unqualified symbols `my-list ;user/my-list

Unquote Evaluates some forms in a quoted expression

Unquote Evaluates some forms in a quoted expression Before unquoting...

Unquote Evaluates some forms in a quoted expression Before unquoting... `(map even? my-list)

Unquote Evaluates some forms in a quoted expression Before unquoting... `(map even? my-list) ;;(clojure.core/map clojure.core/even? user/my-list)

Unquote Evaluates some forms in a quoted expression Before unquoting... `(map even? my-list) ;;(clojure.core/map clojure.core/even? user/my-list) After...

Unquote Evaluates some forms in a quoted expression Before unquoting... `(map even? my-list) ;;(clojure.core/map clojure.core/even? user/my-list) After... `(map even? '~my-list)

Unquote Evaluates some forms in a quoted expression Before unquoting... `(map even? my-list) ;;(clojure.core/map clojure.core/even? user/my-list) After... `(map even? '~my-list) ;;(clojure.core/map clojure.core/even? (quote (1 2 3)))

Unquote-splicing Unpacks the sequence at hand

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing...

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list)

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3))

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list))

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list)) ;;java.lang.Integer cannot be cast to clojure.lang.IFn

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list)) ;;java.lang.Integer cannot be cast to clojure.lang.IFn After...

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list)) ;;java.lang.Integer cannot be cast to clojure.lang.IFn After... `(+ ~@my-list)

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list)) ;;java.lang.Integer cannot be cast to clojure.lang.IFn After... `(+ ~@my-list) ;;(clojure.core/+ 1 2 3)

Unquote-splicing Unpacks the sequence at hand Before unquote-splicing... `(+ ~my-list) ;;(clojure.core/+ (1 2 3)) (eval `(+ ~my-list)) ;;java.lang.Integer cannot be cast to clojure.lang.IFn After... `(+ ~@my-list) ;;(clojure.core/+ 1 2 3) (eval `(+ ~@my-list)) ;6

back to our macro... (defmacro t ([v form] (if (seq? form) `(~(first form) ~v ~@(rest form)) (list form v))) ([v form & rest] `(t (t ~v ~form) ~@rest)))

back to our macro... (defmacro t ([v form] (if (seq? form) `(~(first form) ~v ~@(rest form)) (list form v))) ([v form & rest] `(t (t ~v ~form) ~@rest))) better now?

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model))

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck))

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck)) (require '[clojure.walk :as walk])

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck)) (require '[clojure.walk :as walk]) (walk/macroexpand-all '(t guitar :specs :pickups :neck :model))

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck)) (require '[clojure.walk :as walk]) (walk/macroexpand-all '(t guitar :specs :pickups :neck :model)) ;;expands to

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck)) (require '[clojure.walk :as walk]) (walk/macroexpand-all '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (:neck (:pickups (:specs guitar))))

Macro expansion (macroexpand '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (user/t (user/t (user/t guitar :specs) :pickups) :neck)) (require '[clojure.walk :as walk]) (walk/macroexpand-all '(t guitar :specs :pickups :neck :model)) ;;expands to (:model (:neck (:pickups (:specs guitar)))) However our macro is worthless. Clojure implements this for us, in the form of the -> [4] macro [4] The -> macro on ClojureDocs (http://bit.ly/yCyrHL)

Implementing unless We want... (unless (zero? 2) (print "Not zero!"))

1st try - function (defn unless [predicate body] (when (not predicate) body))

1st try - function (defn unless [predicate body] (when (not predicate) body)) (unless (zero? 2) (print "Not zero!")) ;;Not zero!

1st try - function (defn unless [predicate body] (when (not predicate) body)) (unless (zero? 2) (print "Not zero!")) ;;Not zero! (unless (zero? 0) (print "Not zero!")) ;;Not zero!

1st try - function (defn unless [predicate body] (when (not predicate) body)) (unless (zero? 2) (print "Not zero!")) ;;Not zero! (unless (zero? 0) (print "Not zero!")) ;;Not zero! Oh noes!

1st try - function Function arguments are eagerly evaluated!

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body))

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2)

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2) (print "Not zero!")))

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2) (print "Not zero!"))) ;;expands to

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2) (print "Not zero!"))) ;;expands to (if (clojure.core/not (zero? 2))

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2) (print "Not zero!"))) ;;expands to (if (clojure.core/not (zero? 2)) (do (print "Not zero!")))

Unless - our second macro (defmacro unless [predicate body] `(when (not ~predicate) ~@body)) (macroexpand '(unless (zero? 2) (print "Not zero!"))) ;;expands to (if (clojure.core/not (zero? 2)) (do (print "Not zero!"))) You could of course use the if-not [5] macro to the same effect [5] The if-not macro on ClojureDocs (http://bit.ly/yOIk3W)

Thanks! Questions?! Leonardo Borges @leonardo_borges http://www.leonardoborges.com http://www.thoughtworks.com

References • The Joy of Clojure (http://bit.ly/AAj760) • Automatically RESTful Web Applications (http://bit.ly/ydltH6) • Seaside (http://www.seaside.st) • http://en.wikipedia.org/wiki/Continuation-passing_style • http://matt.might.net/articles/by-example-continuation-passing-style/ • http://en.wikipedia.org/wiki/Static_single_assignment_form Leonardo Borges @leonardo_borges http://www.leonardoborges.com http://www.thoughtworks.com

Continuation Passing Style and Macros in Clojure - Jan 2012

More Related Content

What's hot

Similar to Continuation Passing Style and Macros in Clojure - Jan 2012

More from Leonardo Borges

Recently uploaded

Continuation Passing Style and Macros in Clojure - Jan 2012