@@ 75,7 75,7 @@ 
   \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.
+    another where you ask it if it's done.
   \item Start the scheduler with some initial work.
   \item Perform a bit of user-space work then give control back to the scheduler.
   \end{itemize}

          
@@ 173,6 173,8 @@ 
   \end{itemize}
 \end{frame}
 
+\section{Implementation}
+
 \begin{frame}{Two Components}
   \begin{itemize}
   \item \textbf{Promises} - Define a graph of things-that-are-not-done and

          
@@ 224,12 226,128 @@ 
   \mbox{}
 \end{frame}
 
+\begin{frame}{Futures}
+  \noindent
+  \ttfamily
+  \hlstd{}\hlkwa{type\ }\hlstd{'a\ t\ }\hlopt{=\ \{\ }\hlstd{}\hlkwa{mutable\ }\hlstd{state\ }\hlopt{:\ }\hlstd{'a\ state\ }\hlopt{\}}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{and\ }\hlstd{'a\ state\ }\hlopt{=\ {[}\ }\hlstd{`Det\ }\hlkwa{of\ }\hlstd{'a}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{`Undet\ }\hlkwa{of\ }\hlstd{'a\ undet}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{`Alias\ }\hlkwa{of\ }\hlstd{'a\ t}\hspace*{\fill}\\
+    \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlopt{{]}}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{and\ }\hlstd{'a\ undet\ }\hlopt{=\ \{\ }\hlstd{}\hlkwa{mutable\ }\hlstd{watchers\ }\hlopt{:\ (}\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{}\hlkwb{unit}\hlstd{}\hlopt{)\ }\hlstd{list\ }\hlopt{\}}\hspace*{\fill}\\
+  \hlstd{}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{return\ }\hlstd{v\ }\hlopt{=\ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Det\ v\ }\hlopt{\}}\hspace*{\fill}\\
+  \hlstd{}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
+\begin{frame}{Bind}
+  \begin{itemize}
+  \item \hlstd{}\hlkwd{bind\ }\hlstd{}\hlopt{:\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ (}\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{'b\ t}\hlopt{)\ {-}$>$\ }\hlstd{'b\ t\ }\hspace*{\fill}
+  \item If future is determined, apply function and return its value
+  \item Otherwise, create a new promise/future
+  \item make a watcher that waits for the value of the future passed into bind
+    and sets the future created to its value
+  \item Add watcher to the input future
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Bind}
+  \noindent
+  \ttfamily
+  \hlstd{}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{bind\ }\hlstd{}\hlopt{:\ }\hlstd{'a\ t\ }\hlopt{{-}$>$\ (}\hlstd{'a\ }\hlopt{{-}$>$\ }\hlstd{'b\ t}\hlopt{)\ {-}$>$\ }\hlstd{'b\ t\ }\hlopt{=\ }\hlstd{}\hlkwa{fun\ }\hlstd{t\ f\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{match\ }\hlstd{t\ }\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Det\ v\ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{f\ v}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Undet\ undet\ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{p\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Promise}\hlstd{}\hlopt{.}\hlstd{create\ }\hlopt{()\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{fut\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Promise}\hlstd{}\hlopt{.}\hlstd{future\ }\hlkwd{p\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{w\ }\hlstd{}\hlopt{=\ }\hlstd{make\textunderscore watcher\ }\hlkwd{p\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{undet}\hlopt{.}\hlstd{watchers\ }\hlopt{$<${-}\ }\hlstd{}\hlkwd{w}\hlstd{}\hlopt{::}\hlstd{undet}\hlopt{.}\hlstd{watchers}\hlopt{;}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwd{fut}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Alias\ \textunderscore \ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{assert\ false}\hlstd{}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
+\begin{frame}{make watcher}
+  \begin{itemize}
+  \item Apply the value to the function
+  \item If the future the function returned is determined, then set the promise
+    to it
+  \item If not, make one future an alias to the other and smash their watchers
+    together.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{make watcher}
+  \noindent
+  \ttfamily
+  \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{make\textunderscore watcher\ }\hlstd{p\ v\ }\hlopt{=}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{u\ }\hlstd{}\hlopt{=\ (}\hlstd{f\ v}\hlopt{)\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{match\ }\hlstd{}\hlkwd{u\ }\hlstd{}\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Det\ v'\ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwc{Promise}\hlstd{}\hlopt{.}\hlstd{set\ p\ v'}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Undet\ undet'\ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{begin\ match\ }\hlstd{p\ }\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Undet\ undet''\ }\hlopt{\}\ }\hlstd{}\hlkwa{as\ }\hlstd{fut'\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ }\hlstd{undet'}\hlopt{.}\hlstd{watchers\ }\hlopt{$<${-}\ }\hlstd{undet'}\hlopt{.}\hlstd{watchers\ }\hlopt{@\ }\hlstd{undet''}\hlopt{.}\hlstd{watchers}\hlopt{;}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ }\hlstd{fut'}\hlopt{.}\hlstd{state\ }\hlopt{$<${-}\ }\hlstd{`Alias\ }\hlkwd{u}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=\ }\hlstd{`Det\ \textunderscore \ }\hlopt{\}}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ \{\ }\hlstd{state\ }\hlopt{=}\hlstd{\ \ }\hlopt{}\hlstd{`Alias\ \textunderscore \ }\hlopt{\}\ {-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{assert\ false}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwa{end}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
+\begin{frame}{sleep}
+  \noindent
+  \ttfamily
+  \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{sleep\ }\hlstd{time\ }\hlopt{=}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{trigger\textunderscore time\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{time\ }\hlopt{()\ +.\ }\hlstd{time\ }\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{p\ }\hlstd{}\hlopt{=}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{try}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwc{Float\textunderscore map}\hlstd{}\hlopt{.}\hlstd{find\ }\hlkwd{trigger\textunderscore time\ }\hlstd{}\hlopt{!}\hlstd{timers}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{Not\textunderscore found\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{p\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Byocm\textunderscore fut}\hlstd{}\hlopt{.}\hlstd{}\hlkwc{Promise}\hlstd{}\hlopt{.}\hlstd{create\ }\hlopt{()\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{timers\ }\hlopt{:=\ }\hlstd{}\hlkwc{Float\textunderscore map}\hlstd{}\hlopt{.}\hlstd{add\ }\hlkwd{trigger\textunderscore time\ p\ }\hlstd{}\hlopt{!}\hlstd{timers}\hlopt{;}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{p}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwc{Byocm\textunderscore fut}\hlstd{}\hlopt{.}\hlstd{}\hlkwc{Promise}\hlstd{}\hlopt{.}\hlstd{future\ }\hlkwd{p}\hlstd{}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
+\begin{frame}{run}
+  \noindent
+  \ttfamily
+  \hlstd{}\hlkwa{let\ rec\ }\hlstd{}\hlkwd{loop\ }\hlstd{finished\ }\hlopt{=}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{match\ }\hlstd{}\hlkwc{Byocm\textunderscore fut}\hlstd{}\hlopt{.}\hlstd{state\ finished\ }\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{`Det\ v\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{v}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{`Undet\ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{next\textunderscore iter\ }\hlopt{();}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{}\hlkwd{loop\ }\hlstd{finished}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{and\ }\hlstd{next\textunderscore iter\ }\hlopt{()\ =}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{now\ }\hlstd{}\hlopt{=\ }\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{time\ }\hlopt{()\ }\hlstd{}\hlkwa{in}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ }\hlstd{}\hlkwa{match\ }\hlstd{}\hlkwc{Float\textunderscore map}\hlstd{}\hlopt{.}\hlstd{min\textunderscore binding\textunderscore opt\ }\hlopt{!}\hlstd{timers\ }\hlkwa{with}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{Some\ }\hlopt{(}\hlstd{n}\hlopt{,\ }\hlstd{\textunderscore }\hlopt{)\ }\hlstd{}\hlkwa{when\ }\hlstd{n\ }\hlopt{$>$\ }\hlstd{}\hlkwd{now\ }\hlstd{}\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{ignore\ }\hlopt{(}\hlstd{}\hlkwc{Unix}\hlstd{}\hlopt{.}\hlstd{select\ }\hlopt{{[}{]}\ {[}{]}\ {[}{]}\ (}\hlstd{n\ }\hlopt{{-}.\ }\hlstd{}\hlkwd{now}\hlstd{}\hlopt{))}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlopt{\textbar \ }\hlstd{\textunderscore \ }\hlopt{{-}$>$}\hspace*{\fill}\\
+  \hlstd{}\hlstd{\ \ \ \ \ \ }\hlstd{exec\textunderscore timers\ }\hlkwd{now}\hspace*{\fill}\\
+  \hlstd{}\hlkwa{let\ }\hlstd{}\hlkwd{run\ }\hlstd{f\ }\hlopt{=\ }\hlstd{}\hlkwd{loop\ }\hlstd{}\hlopt{(}\hlstd{f\ }\hlopt{())}\hlstd{}\hspace*{\fill}\\
+  \mbox{}
+\end{frame}
+
 \begin{frame}{Exercises For The Reader}
   \begin{itemize}
   \item Add some Unix APIs (send/recv/connect/accept).
   \item Switch to something other than \texttt{Unix.select}.
   \item Support canceling operations.
   \item Applicatives.
+  \item Less side-effecty scheduler.
+  \item Support Binding operators in 4.08.0.
   \end{itemize}
 \end{frame}
 

          
@@ 272,7 390,11 @@ 
 \end{frame}
 
 \begin{frame}{Conclusion}
-  
+  \begin{itemize}
+  \item Now you can sleep as much as you want concurrently.
+  \item We can write user-space concurrent code.
+  \item With a slight visual/syntax cost.
+  \end{itemize}
 \end{frame}
 
 \end{document}

          

@@ 0,0 1,13 @@ 
+
+let bind : 'a t -> ('a -> 'b t) -> 'b t = fun t f ->
+  match t with
+    | { state = `Det v } ->
+      f v
+    | { state = `Undet undet } ->
+      let p = Promise.create () in
+      let fut = Promise.future p in
+      let w = make_watcher p in
+      undet.watchers <- w::undet.watchers;
+      fut
+    | { state = `Alias _ } ->
+      assert false

          

@@ 0,0 1,8 @@ 
+type 'a t = { mutable state : 'a state }
+and 'a state = [ `Det of 'a
+               | `Undet of 'a undet
+               | `Alias of 'a t
+               ]
+and 'a undet = { mutable watchers : ('a -> unit) list }
+
+let return v = { state = `Det v }

          

@@ 0,0 1,15 @@ 
+let rec loop finished =
+  match Byocm_fut.state finished with
+    | `Det v ->
+      v
+    | `Undet ->
+      next_iter ();
+      loop finished
+and next_iter () =
+  let now = Unix.time () in
+  match Float_map.min_binding_opt !timers with
+    | Some (n, _) when n > now ->
+      ignore (Unix.select [] [] [] (n -. now))
+    | _ ->
+      exec_timers now
+let run f = loop (f ())

          

@@ 0,0 1,12 @@ 
+let sleep time =
+  let trigger_time = Unix.time () +. time in
+  let p =
+    try
+      Float_map.find trigger_time !timers
+    with
+      | Not_found ->
+        let p = Byocm_fut.Promise.create () in
+        timers := Float_map.add trigger_time p !timers;
+        p
+  in
+  Byocm_fut.Promise.future p

          

@@ 0,0 1,16 @@ 
+let make_watcher p v =
+  let u = (f v) in
+  match u with
+    | { state = `Det v' } ->
+      Promise.set p v'
+    | { state = `Undet undet' } ->
+      begin match p with
+        | { state = `Undet undet'' } as fut' ->
+          undet'.watchers <- undet'.watchers @ undet''.watchers;
+          fut'.state <- `Alias u
+        | { state = `Det _ }
+        | { state =  `Alias _ } ->
+          assert false
+      end
+    | _ ->
+      assert false