Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
179 lines (178 sloc) 14.4 KB
\contentsline {chapter}{Contents}{i}{section*.1}
\contentsline {chapter}{Preface}{1}{chapter*.5}
\contentsline {chapter}{\numberline {1}Motivation and Background}{3}{chapter.1}
\contentsline {paragraph}{If on a winter's night a programmer (with apologies to Italo Calvino)}{3}{section*.6}
\contentsline {section}{\numberline {1.1}Where are we}{4}{section.1.1}
\contentsline {subsection}{\numberline {1.1.1}The concurrency squeeze: from the hardware up, from the web down}{4}{subsection.1.1.1}
\contentsline {subsection}{\numberline {1.1.2}Ubiquity of robust, high-performance virtual machines}{5}{subsection.1.1.2}
\contentsline {subsection}{\numberline {1.1.3}Advances in functional programming, monads and the awkward squad}{6}{subsection.1.1.3}
\contentsline {section}{\numberline {1.2}Where are we going}{10}{section.1.2}
\contentsline {subsection}{\numberline {1.2.1}A functional web}{10}{subsection.1.2.1}
\contentsline {subsection}{\numberline {1.2.2}DSL-based design}{12}{subsection.1.2.2}
\contentsline {section}{\numberline {1.3}How are we going to get there}{13}{section.1.3}
\contentsline {subsection}{\numberline {1.3.1}Leading by example}{13}{subsection.1.3.1}
\contentsline {subsubsection}{Our toy language}{17}{section*.7}
\contentsline {paragraph}{Abstract syntax}{17}{section*.8}
\contentsline {paragraph}{Concrete syntax}{17}{section*.9}
\contentsline {subsubsection}{Code editor}{19}{section*.10}
\contentsline {subsubsection}{Project editor}{19}{section*.11}
\contentsline {subsubsection}{Advanced features}{19}{section*.12}
\contentsline {subsection}{\numberline {1.3.2}Chapter map}{19}{subsection.1.3.2}
\contentsline {chapter}{\numberline {2}Toolbox}{21}{chapter.2}
\contentsline {section}{\numberline {2.1}Introduction to notation and terminology}{21}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}Scala}{21}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}Maths}{21}{subsection.2.1.2}
\contentsline {section}{\numberline {2.2}Introduction to core design patterns}{21}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}A little history}{21}{subsection.2.2.1}
\contentsline {paragraph}{Haskell's monad API}{22}{section*.13}
\contentsline {paragraph}{Do-notation}{22}{section*.14}
\contentsline {paragraph}{for-comprehensions}{23}{section*.15}
\contentsline {section}{\numberline {2.3}Variations in presentation}{26}{section.2.3}
\contentsline {subsection}{\numberline {2.3.1}A little more history}{26}{subsection.2.3.1}
\contentsline {subsubsection}{Intuition: Monad as container}{26}{section*.16}
\contentsline {paragraph}{Shape of the container}{26}{section*.17}
\contentsline {paragraph}{Putting things into the container}{26}{section*.18}
\contentsline {paragraph}{Flattening nested containers}{26}{section*.19}
\contentsline {subsubsection}{Preserving connection to existing structure: Monad as generalization of monoid}{27}{section*.20}
\contentsline {paragraph}{Associativity as flattening}{29}{section*.21}
\contentsline {paragraph}{Bracing for \texttt {XML}}{29}{section*.22}
\contentsline {paragraph}{The connection with set-comprehensions}{30}{section*.23}
\contentsline {paragraph}{Syntax and containers}{31}{section*.24}
\contentsline {subsubsection}{Decomposition of monad requirements}{31}{section*.25}
\contentsline {subsubsection}{A categorical way to look at monads}{32}{section*.26}
\contentsline {paragraph}{Quick digression about design by diagram-chasing}{33}{section*.27}
\contentsline {paragraph}{Monads are triples}{34}{section*.28}
\contentsline {chapter}{\numberline {3}An IO-monad for http streams}{39}{chapter.3}
\contentsline {section}{\numberline {3.1}Code first, questions later}{39}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}An HTTP-request processor}{48}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}What we did}{48}{subsection.3.1.2}
\contentsline {section}{\numberline {3.2}Synchrony, asynchrony and buffering}{48}{section.3.2}
\contentsline {section}{\numberline {3.3}State, statelessness and continuations}{48}{section.3.3}
\contentsline {chapter}{\numberline {4}Parsing requests, monadically}{49}{chapter.4}
\contentsline {section}{\numberline {4.1}Obligatory parsing monad}{49}{section.4.1}
\contentsline {section}{\numberline {4.2}Your parser combinators are showing}{49}{section.4.2}
\contentsline {section}{\numberline {4.3}EBNF and why higher levels of abstraction are better}{49}{section.4.3}
\contentsline {subsection}{\numberline {4.3.1}Different platforms, different parsers}{49}{subsection.4.3.1}
\contentsline {subsection}{\numberline {4.3.2}Different performance constraints, different parsers}{49}{subsection.4.3.2}
\contentsline {subsection}{\numberline {4.3.3}Maintainability}{49}{subsection.4.3.3}
\contentsline {chapter}{\numberline {5}The domain model as abstract syntax}{53}{chapter.5}
\contentsline {section}{\numberline {5.1}Our abstract syntax}{53}{section.5.1}
\contentsline {paragraph}{Abstract syntax}{53}{section*.29}
\contentsline {section}{\numberline {5.2}Our application domain model}{54}{section.5.2}
\contentsline {subsubsection}{Our toy language}{54}{section*.30}
\contentsline {paragraph}{A simple-minded representation}{54}{section*.31}
\contentsline {paragraph}{Currying}{55}{section*.32}
\contentsline {paragraph}{Type parametrization and quotation}{56}{section*.33}
\contentsline {paragraph}{Some syntactic sugar}{57}{section*.34}
\contentsline {paragraph}{Digression: complexity management principle}{57}{section*.35}
\contentsline {paragraph}{Concrete syntax}{57}{section*.36}
\contentsline {paragraph}{Translating concrete syntax to abstract syntax}{58}{section*.37}
\contentsline {paragraph}{Structural equivalence and Relations or What makes abstract syntax abstract}{61}{section*.38}
\contentsline {paragraph}{Digression: the internal structure of the type of variables}{65}{section*.39}
\contentsline {paragraph}{Evaluation -- aka operational semantics}{66}{section*.40}
\contentsline {paragraph}{Ordinary maps}{66}{section*.41}
\contentsline {paragraph}{DeBruijn notation}{66}{section*.42}
\contentsline {subsubsection}{The \texttt {Scala} implementation}{66}{section*.43}
\contentsline {subsubsection}{What goes into a language definition}{68}{section*.44}
\contentsline {paragraph}{Syntax}{69}{section*.45}
\contentsline {paragraph}{Structural equivalence}{69}{section*.46}
\contentsline {paragraph}{Operational semantics}{69}{section*.47}
\contentsline {paragraph}{Discussion}{69}{section*.48}
\contentsline {section}{\numberline {5.3}The project model}{70}{section.5.3}
\contentsline {subsection}{\numberline {5.3.1}Abstract syntax}{70}{subsection.5.3.1}
\contentsline {subsection}{\numberline {5.3.2}Concrete syntax -- and presentation layer}{70}{subsection.5.3.2}
\contentsline {subsection}{\numberline {5.3.3}Domain model}{70}{subsection.5.3.3}
\contentsline {section}{\numberline {5.4}A transform pipeline}{70}{section.5.4}
\contentsline {chapter}{\numberline {6}Zippers and contexts and URI's, oh my!}{71}{chapter.6}
\contentsline {section}{\numberline {6.1}Zippers are not just for Bruno anymore}{71}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}The history of the zipper}{71}{subsection.6.1.1}
\contentsline {subsubsection}{Huet's zipper}{71}{section*.49}
\contentsline {paragraph}{The navigation functions}{75}{section*.50}
\contentsline {paragraph}{Exercising the zipper}{76}{section*.51}
\contentsline {subsubsection}{Zippers generically}{80}{section*.52}
\contentsline {paragraph}{Two kinds of genericity}{80}{section*.53}
\contentsline {paragraph}{Genericity of structure}{80}{section*.54}
\contentsline {paragraph}{Genericity of control}{81}{section*.55}
\contentsline {section}{\numberline {6.2}Zipper and one-holed contexts}{82}{section.6.2}
\contentsline {section}{\numberline {6.3}Differentiation and contexts}{82}{section.6.3}
\contentsline {subsection}{\numberline {6.3.1}Regular types}{82}{subsection.6.3.1}
\contentsline {subsection}{\numberline {6.3.2}Container types}{82}{subsection.6.3.2}
\contentsline {section}{\numberline {6.4}Generic zipper -- differentiating navigation}{82}{section.6.4}
\contentsline {subsection}{\numberline {6.4.1}Delimited continuations}{85}{subsection.6.4.1}
\contentsline {subsubsection}{The genericity of delimited continuations}{86}{section*.56}
\contentsline {section}{\numberline {6.5}Species of Structure}{88}{section.6.5}
\contentsline {section}{\numberline {6.6}Constructing contexts and zippers from data types}{88}{section.6.6}
\contentsline {subsection}{\numberline {6.6.1}Contexts}{89}{subsection.6.6.1}
\contentsline {subsection}{\numberline {6.6.2}Zippers}{89}{subsection.6.6.2}
\contentsline {section}{\numberline {6.7}Mapping URIs to zipper-based paths and back}{95}{section.6.7}
\contentsline {subsection}{\numberline {6.7.1}Path and context}{95}{subsection.6.7.1}
\contentsline {subsection}{\numberline {6.7.2}Homomorphisms and obfuscation}{95}{subsection.6.7.2}
\contentsline {section}{\numberline {6.8}Applying zippers to our project}{95}{section.6.8}
\contentsline {subsection}{\numberline {6.8.1}Navigating and editing terms}{95}{subsection.6.8.1}
\contentsline {subsection}{\numberline {6.8.2}Navigating and editing projects}{97}{subsection.6.8.2}
\contentsline {chapter}{\numberline {7}A review of collections as monads}{99}{chapter.7}
\contentsline {section}{\numberline {7.1}Sets, Lists and Languages}{99}{section.7.1}
\contentsline {subsection}{\numberline {7.1.1}Witnessing Sets and Lists monadicity}{99}{subsection.7.1.1}
\contentsline {subsection}{\numberline {7.1.2}Languages and Sets of Words}{104}{subsection.7.1.2}
\contentsline {subsubsection}{Kleene star}{104}{section*.57}
\contentsline {subsubsection}{I am not a number, I am a free monoid}{104}{section*.58}
\contentsline {subsection}{\numberline {7.1.3}Of lenses and bananas}{104}{subsection.7.1.3}
\contentsline {section}{\numberline {7.2}Containers and syntax}{104}{section.7.2}
\contentsline {subsection}{\numberline {7.2.1}The algebra of Sets}{104}{subsection.7.2.1}
\contentsline {subsection}{\numberline {7.2.2}The algebra of Lists}{104}{subsection.7.2.2}
\contentsline {subsection}{\numberline {7.2.3}The algebra of Sets of Words}{105}{subsection.7.2.3}
\contentsline {section}{\numberline {7.3}Algebras}{105}{section.7.3}
\contentsline {subsection}{\numberline {7.3.1}Kleisli}{105}{subsection.7.3.1}
\contentsline {subsection}{\numberline {7.3.2}Eilenberg-Moore}{105}{subsection.7.3.2}
\contentsline {section}{\numberline {7.4}Monad as container}{105}{section.7.4}
\contentsline {section}{\numberline {7.5}Monads and take-out}{105}{section.7.5}
\contentsline {subsection}{\numberline {7.5.1}Option as container}{107}{subsection.7.5.1}
\contentsline {subsection}{\numberline {7.5.2}I/O monad for contrast}{108}{subsection.7.5.2}
\contentsline {subsection}{\numberline {7.5.3}Matching gazintas and gazoutas}{108}{subsection.7.5.3}
\contentsline {subsubsection}{Intuitionistic discipline}{108}{section*.60}
\contentsline {subsubsection}{Linear discipline}{108}{section*.61}
\contentsline {section}{\numberline {7.6}Co-monad and take-out}{108}{section.7.6}
\contentsline {section}{\numberline {7.7}Hopf structure}{108}{section.7.7}
\contentsline {section}{\numberline {7.8}Container and control}{108}{section.7.8}
\contentsline {subsection}{\numberline {7.8.1}Delimited continuations reconsidered}{108}{subsection.7.8.1}
\contentsline {chapter}{\numberline {8}Domain model, storage and state}{109}{chapter.8}
\contentsline {section}{\numberline {8.1}Mapping our domain model to storage}{109}{section.8.1}
\contentsline {subsection}{\numberline {8.1.1}Functional and relational models}{109}{subsection.8.1.1}
\contentsline {subsection}{\numberline {8.1.2}Functional and XML models}{109}{subsection.8.1.2}
\contentsline {subsection}{\numberline {8.1.3}ORM}{109}{subsection.8.1.3}
\contentsline {section}{\numberline {8.2}Storage and language-integrated query}{109}{section.8.2}
\contentsline {subsection}{\numberline {8.2.1}LINQ and \lstinline [language=Scala]!for!-comprehensions}{109}{subsection.8.2.1}
\contentsline {subsubsection}{Open source implementations}{109}{section*.62}
\contentsline {paragraph}{ScalaQuery}{109}{section*.63}
\contentsline {paragraph}{Squeryl}{109}{section*.64}
\contentsline {section}{\numberline {8.3}Continuations revisited}{110}{section.8.3}
\contentsline {subsection}{\numberline {8.3.1}Stored state}{110}{subsection.8.3.1}
\contentsline {subsection}{\numberline {8.3.2}Transactions}{110}{subsection.8.3.2}
\contentsline {chapter}{\numberline {9}Putting it all together}{111}{chapter.9}
\contentsline {section}{\numberline {9.1}Our web application end-to-end}{111}{section.9.1}
\contentsline {section}{\numberline {9.2}Deploying our application}{111}{section.9.2}
\contentsline {subsection}{\numberline {9.2.1}Why we are not deploying on GAE}{111}{subsection.9.2.1}
\contentsline {section}{\numberline {9.3}From one web application to web framework}{111}{section.9.3}
\contentsline {chapter}{\numberline {10}The semantic web}{113}{chapter.10}
\contentsline {section}{\numberline {10.1}Referential transparency}{113}{section.10.1}
\contentsline {paragraph}{A little motivation}{114}{section*.65}
\contentsline {section}{\numberline {10.2}Composing monads}{115}{section.10.2}
\contentsline {subsubsection}{Preliminary}{116}{section*.66}
\contentsline {section}{\numberline {10.3}Semantic application queries}{117}{section.10.3}
\contentsline {subsubsection}{An alternative presentation}{117}{section*.67}
\contentsline {paragraph}{Logic: the set monad as an algebra}{118}{section*.68}
\contentsline {paragraph}{Primes: an application}{119}{section*.69}
\contentsline {paragraph}{Summary}{119}{section*.70}
\contentsline {subsubsection}{Patterns}{120}{section*.71}
\contentsline {subsubsection}{A first mini-query language}{120}{section*.72}
\contentsline {subsubsection}{Iterating the design pattern}{120}{section*.73}
\contentsline {paragraph}{A spatial-behavioral-style logic for $\lambda $-calculus}{121}{section*.74}
\contentsline {paragraph}{Examples}{121}{section*.75}
\contentsline {subsubsection}{Logical semantics}{122}{section*.76}
\contentsline {subsubsection}{Other collection monads, other logics}{122}{section*.77}
\contentsline {paragraph}{Stateful collections}{122}{section*.78}
\contentsline {subsection}{\numberline {10.3.1}Other logical operations}{124}{subsection.10.3.1}
\contentsline {section}{\numberline {10.4}Searching for programs}{124}{section.10.4}
\contentsline {subsection}{\numberline {10.4.1}A new foundation for search}{124}{subsection.10.4.1}
\contentsline {subsubsection}{Monad composition via distributive laws}{124}{section*.79}
\contentsline {subsection}{\numberline {10.4.2}Examples}{124}{subsection.10.4.2}
Jump to Line
Something went wrong with that request. Please try again.