@@ 7,4 7,8 @@ presentation/byocm.log
 presentation/byocm.nav
 presentation/byocm.out
 presentation/byocm.pdf
-presentation/byocm.toc
  No newline at end of file
+presentation/byocm.toc
+
+code/build/
+code/pds.mk
+code/Ocamlrules.mk.in
  No newline at end of file

          

@@ 1,6 1,12 @@ 
-.PHONY: all presentation
+.PHONY: all presentation code test
 
-all: presentation
+all: presentation code
 
 presentation:
 	$(MAKE) -C presentation
+
+code:
+	$(MAKE) -C code
+
+test: code
+	$(MAKE) -C code test

          

@@ 0,0 1,9 @@ 
+.PHONY:
+
+all:
+	pds
+	$(MAKE) -f pds.mk all
+
+%:
+	pds
+	$(MAKE) -f pds.mk $*

          

@@ 0,0 1,26 @@ 
+[global]
+selector = ["opam", "config", "var", "os"]
+
+[global.release]
+extra_compiler_opts = "-bin-annot -strict-sequence -strict-formats -safe-string -noassert"
+
+[global.debug]
+extra_compiler_opts = "-g -bin-annot -strict-sequence -strict-formats -safe-string -w '@d@f@p@u@s@40'"
+
+[global.profile]
+extra_compiler_opts = "-safe-string"
+
+[global.test-release]
+extra_compiler_opts = "-safe-string"
+
+[global.test-debug]
+extra_compiler_opts = "-safe-string"
+
+[global.test-profile]
+extra_compiler_opts = "-safe-string"
+
+[src.byocm_fut]
+install = false
+
+[tests.byocm_fut]
+deps = [ "byocm_fut" ]
  No newline at end of file

          

@@ 0,0 1,53 @@ 
+type +'a t
+
+type 'a u = { mutable state : 'a state }
+and 'a state = [ `Det of 'a
+               | `Undet of 'a undet
+               | `Alias of 'a u
+               ]
+and 'a undet = { mutable watchers : ('a -> unit) list }
+
+external t_of_u : 'a u -> 'a t = "%identity"
+external u_of_t : 'a t -> 'a u = "%identity"
+
+module Promise = struct
+  type 'a fut = 'a t
+  type 'a t = 'a fut
+  let create () = t_of_u { state = `Undet { watchers = [] } }
+  external future : 'a t -> 'a fut = "%identity"
+  let set t v =
+    let u = u_of_t t in
+    match u with
+      | { state = `Undet { watchers = watchers } } ->
+        u.state <- `Det v;
+        List.iter (fun w -> w v) watchers
+      | { state = `Det _ }
+      | { state = `Alias _ } ->
+        assert false
+end
+
+let rec collapse_alias = function
+  | { state = `Alias u } -> collapse_alias u
+  | u -> u
+
+let return v = t_of_u { state = `Det v }
+let bind t f =
+  let u = collapse_alias (u_of_t t) in
+  match u with
+    | { state = `Det v } ->
+      f v
+    | { state = `Undet { watchers = watchers } } ->
+      failwith "nyi"
+    | { state = `Alias _ } ->
+      assert false
+
+let state t =
+  let u = collapse_alias (u_of_t t) in
+  match u with
+    | { state = `Det v } -> `Det v
+    | { state = `Undet _ } -> `Undet
+    | { state = `Alias _ } -> assert false
+
+module Infix_monad = struct
+  let (>>=) = bind
+end

          

@@ 0,0 1,17 @@ 
+type +'a t
+
+module Promise : sig
+  type 'a fut = 'a t
+  type 'a t
+  val create : unit -> 'a t
+  val future : 'a t -> 'a fut
+  val set : 'a t -> 'a -> unit
+end
+
+val return : 'a -> 'a t
+val bind : 'a t -> ('a -> 'b t) -> 'b t
+val state : 'a t -> [ `Det of 'a | `Undet ]
+
+module Infix_monad : sig
+  val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
+end

          

@@ 0,0 1,31 @@ 
+let test1 () =
+  let fut = Byocm_fut.return "hello" in
+  let res = Byocm_fut.bind fut (fun s -> Byocm_fut.return (s ^ " world")) in
+  assert (Byocm_fut.state res = `Det "hello world")
+
+let test2 () =
+  let open Byocm_fut.Infix_monad in
+  let res =
+    Byocm_fut.return "hello"
+    >>= fun s ->
+    Byocm_fut.return (s ^ " world")
+  in
+  assert (Byocm_fut.state res = `Det "hello world")
+
+let test3 () =
+  let open Byocm_fut.Infix_monad in
+  let p = Byocm_fut.Promise.create () in
+  let fut = Byocm_fut.Promise.future p in
+  let res =
+    fut
+    >>= fun s ->
+    Byocm_fut.return (s ^ " world")
+  in
+  assert (Byocm_fut.state res = `Undet);
+  Byocm_fut.Promise.set p "hello";
+  assert (Byocm_fut.state res = `Det "hello world")
+
+let () =
+  test1 ();
+  test2 ();
+  test3 ()

          

@@ 1,5 1,27 @@ 
 \documentclass{beamer}
 \usepackage{hyperref}
+\usepackage{color}
+\usepackage{alltt}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+
+% highlight theme: Kwrite Editor
+\newcommand{\hlstd}[1]{\textcolor[rgb]{0,0,0}{#1}}
+\newcommand{\hlnum}[1]{\textcolor[rgb]{0.69,0.49,0}{#1}}
+\newcommand{\hlesc}[1]{\textcolor[rgb]{1,0,1}{#1}}
+\newcommand{\hlstr}[1]{\textcolor[rgb]{0.75,0.01,0.01}{#1}}
+\newcommand{\hlpps}[1]{\textcolor[rgb]{0.51,0.51,0}{#1}}
+\newcommand{\hlslc}[1]{\textcolor[rgb]{0.51,0.51,0.51}{\it{#1}}}
+\newcommand{\hlcom}[1]{\textcolor[rgb]{0.51,0.51,0.51}{\it{#1}}}
+\newcommand{\hlppc}[1]{\textcolor[rgb]{0,0.51,0}{#1}}
+\newcommand{\hlopt}[1]{\textcolor[rgb]{0,0,0}{#1}}
+\newcommand{\hlipl}[1]{\textcolor[rgb]{0,0.34,0.68}{#1}}
+\newcommand{\hllin}[1]{\textcolor[rgb]{0.33,0.33,0.33}{#1}}
+\newcommand{\hlkwa}[1]{\textcolor[rgb]{0,0,0}{\bf{#1}}}
+\newcommand{\hlkwb}[1]{\textcolor[rgb]{0,0.34,0.68}{#1}}
+\newcommand{\hlkwc}[1]{\textcolor[rgb]{0,0,0}{\bf{#1}}}
+\newcommand{\hlkwd}[1]{\textcolor[rgb]{0,0,0.51}{#1}}
+\definecolor{bgcolor}{rgb}{0.88,0.92,0.93}
 
 \usetheme{metropolis}
 \title{Build Your Own Concurrency Monad}

          
@@ 9,13 31,183 @@ 
 \begin{document}
 \maketitle
 
-\begin{frame}{This}
-  \begin{enumerate}
-  \item Foo bar
-  \end{enumerate}
+\section{Background}
+
+\begin{frame}{The Problem}
+  We want to maximize the number of I/O bound operations a single machine can
+  perform with a programming model people can understand.
+\end{frame}
+
+\begin{frame}{Why do we want a Concurrency Monad?}
+  \begin{itemize}
+  \item C10K problem.
+  \item Code was historically written to be synchronous.
+  \item OS threads were a transition step but didn't scale.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{OS Threads (Synchronous)}
+  \begin{itemize}
+  \item Makes concurrency the problem of the OS.
+  \item Seems like a nice abstraction: I don't really need to change my
+    synchronous code that much.
+  \item OS threads are very heavy, they are really meant to utilize all cores.
+    Good for CPU-bound tasks.
+  \item Expensive to switch between, user space \( \rightarrow \) kernel space \(
+    \rightarrow \) user space.
+  \item With lots of concurrency, we spend all our time context switching.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{In User Space (Asynchronous)}
+  \begin{itemize}
+  \item Handle multiple connections in a single thread.
+  \item Use OS APIs to get a list of events, process them, ask again (fewer
+    context switches).
+  \item Event Loop.
+  \item Basic model the same across OS's but specific API calls change.
+  \item Go, Erlang, Mozart/Oz do this for you.  Async/Await in Rust, C\#, and
+    JavaScript do a similar thing.
+  \item In Ocaml we can do this as a library, no need to spend 3 years in
+    language standards meetings!
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Anatomy of Concurrency In User Space}
+  \begin{itemize}
+  \item The game is to turn kernel calls that can wait an unbounded amount of
+    time into two calls: One where you tell the kernel to do something and
+    another when it tells you when it's done.
+  \item Start the event loop with some initial work.
+  \item Perform a bit of user-space work then give control back to the event
+    loop.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Anatomy of Concurrency In User Space}
+  \center{\includegraphics[scale=0.4]{images/event_loop.png}}
+\end{frame}
+
+\begin{frame}{Comparing Synchronous \& Asynchronous}
+  \begin{columns}[T]
+    \begin{column}{0.5\textwidth}
+      \begin{block}{\underline{Semantically}}
+        \begin{itemize}
+        \item Function: \emph{slow\_echo}
+        \item Read from socket.
+        \item Wait 1 second.
+        \item Write text back to socket.
+        \end{itemize}
+      \end{block}
+    \end{column}
+    \begin{column}{0.5\textwidth}
+      \begin{block}{\underline{Synchronous}}
+        \center{\includegraphics[scale=0.3]{images/slow_echo_sync.png}}
+      \end{block}
+    \end{column}
+  \end{columns}
 \end{frame}
 
-\section{Foobar}
+\begin{frame}{Comparing Synchronous \& Asynchronous}
+  \begin{columns}[T]
+    \begin{column}{0.5\textwidth}
+      \begin{block}{\underline{Synchronous}}
+        \center{\includegraphics[scale=0.3]{images/slow_echo_sync.png}}
+      \end{block}
+    \end{column}
+    \begin{column}{0.5\textwidth}
+      \begin{block}{\underline{Asynchronous}}
+        \center{\includegraphics[scale=0.3]{images/slow_echo_event_loop.png}}
+      \end{block}
+    \end{column}
+  \end{columns}
+\end{frame}
+
+\begin{frame}{Comparing Synchronous \& Asynchronous}
+  \begin{block}{\underline{Synchronous}}
+    \noindent
+    \ttfamily
+    \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{slow\textunderscore echo\ }\hlstd{fd\ }\hlopt{=}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{bytes\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Bytes}\hlstd{}\hlopt{.}\hlstd{create\ }\hlnum{1024\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{n\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{recv\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ 1024\ }\hlstd{}\hlopt{{[}{]}\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{sleep\ }\hlnum{1}\hlstd{}\hlopt{;}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{send\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ }\hlstd{}\hlkwd{n\ }\hlstd{}\hlopt{{[}{]}}\hlstd{}\hspace*{\fill}\\
+    \mbox{}
+  \end{block}
+\end{frame}
+
+\begin{frame}{Comparing Synchronous \& Asynchronous}
+  \begin{block}{\underline{Asynchronous Bind}}
+    \noindent
+    \ttfamily
+    \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{slow\textunderscore echo\ }\hlstd{fd\ }\hlopt{=}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{bytes\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Bytes}\hlstd{}\hlopt{.}\hlstd{create\ }\hlnum{1024\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{bind}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{(}\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{recv\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ 1024\ }\hlstd{}\hlopt{{[}{]})}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{(}\hlstd{}\hlkwa{fun\ }\hlstd{n\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{bind}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ }\hlstd{}\hlopt{(}\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{sleep\ }\hlnum{1}\hlstd{}\hlopt{)}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ }\hlstd{}\hlopt{(}\hlstd{}\hlkwa{fun\ }\hlstd{}\hlopt{()\ {-}$>$}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{send\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ }\hlstd{n\ }\hlopt{{[}{]}))}\hlstd{}\hspace*{\fill}\\
+    \mbox{}
+  \end{block}
+\end{frame}
+
+\begin{frame}{Comparing Synchronous \& Asynchronous}
+  \begin{block}{\underline{Asynchronous}}
+    \noindent
+    \ttfamily
+    \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{slow\textunderscore echo\ }\hlstd{fd\ }\hlopt{=}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{bytes\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Bytes}\hlstd{}\hlopt{.}\hlstd{create\ }\hlnum{1024\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{recv\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ 1024}\hlstd{}\hlopt{)\ {[}{]}}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlopt{$>$$>$=\ }\hlstd{}\hlkwa{fun\ }\hlstd{n\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{sleep\ }\hlnum{1}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlopt{$>$$>$=\ }\hlstd{}\hlkwa{fun\ }\hlstd{}\hlopt{()\ {-}$>$}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Async}\hlstd{}\hlopt{.}\hlstd{send\ fd\ }\hlkwd{bytes\ }\hlstd{}\hlnum{0\ }\hlstd{n\ }\hlopt{{[}{]}}\hlstd{}\hspace*{\fill}\\
+    \mbox{}
+  \end{block}
+\end{frame}
+
+\begin{frame}{It's all about the concurrency}
+  \begin{itemize}
+  \item The above example is just sequential code.
+  \item What's actually important is we can do \emph{a lot} of those at the same
+    time.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Two Components}
+  \begin{itemize}
+  \item \textbf{Promises} - Define a graph of things-that-are-not-done and
+    things-that-want-to-know-when-they-are-done.
+  \item \textbf{Event loop/Scheduler} - Handle waiting for events and telling
+    kernel about new events and fulfilling promises.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Promise API}
+  \noindent
+  \ttfamily
+  \hlstd{}\hlkwa{type\ }\hlstd{}\hlopt{+}\hlstd{'a\ t}\hspace*{\fill}\\
+  \hlstd{}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{val\ }\hlstd{return\ }\hlopt{:\ }\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{'a\ t}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{val\ }\hlstd{bind\ }\hlopt{:\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ (}\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{'b\ t}\hlopt{)\ {-}$>$\ }\hlstd{'b\ t}\hspace*{\fill}\\
+  \hlstd{}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{module\ }\hlstd{Infix\textunderscore monad\ }\hlopt{:\ }\hlstd{}\hlkwa{sig}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{val\ }\hlstd{}\hlopt{($>$$>$=)\ :\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ (}\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{'b\ t}\hlopt{)\ {-}$>$\ }\hlstd{'b\ t}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{end}\hlstd{}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
+\begin{frame}{Promise API}
+  \hlstd{}\hlkwa{module\ }\hlstd{Promise\ }\hlopt{:\ }\hlstd{}\hlkwa{sig}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{type\ }\hlstd{'a\ fut\ }\hlopt{=\ }\hlstd{'a\ t}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{type\ }\hlstd{'a\ t}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{val\ }\hlstd{create\ }\hlopt{:\ }\hlstd{}\hlkwb{unit\ }\hlstd{}\hlopt{{-}$>$\ }\hlstd{'a\ t}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{val\ }\hlstd{future\ }\hlopt{:\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ }\hlstd{'a\ fut}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{val\ }\hlstd{set\ }\hlopt{:\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ }\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{}\hlkwb{unit\ }\hlstd{fut}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{end}\hspace*{\fill}\\
+\end{frame}
 
 \end{document}
 

          

@@ 0,0 1,7 @@ 
+let slow_echo fd =
+  let bytes = Bytes.create 1024 in
+  Async.recv fd bytes 0 1024) []
+  >>= fun n ->
+  Async.sleep 1
+  >>= fun () ->
+  Async.send fd bytes 0 n []

          

@@ 0,0 1,9 @@ 
+let slow_echo fd =
+  let bytes = Bytes.create 1024 in
+  Async.bind
+    (Async.recv fd bytes 0 1024 [])
+    (fun n ->
+       Async.bind
+         (Async.sleep 1)
+         (fun () ->
+            Async.send fd bytes 0 n []))

          

@@ 0,0 1,5 @@ 
+let slow_echo fd =
+  let bytes = Bytes.create 1024 in
+  let n = Unix.recv fd bytes 0 1024 [] in
+  Unix.sleep 1;
+  Unix.send fd bytes 0 n []