Mercurial > hg > Papers > 2015 > atton-lola
changeset 6:1e3b7eb09712
Wrote second chapter
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Apr 2015 17:02:20 +0900 |
parents | 3965ed0b4a50 |
children | 5ecae062b32b |
files | cfopm.tex |
diffstat | 1 files changed, 69 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/cfopm.tex Fri Apr 17 15:23:34 2015 +0900 +++ b/cfopm.tex Fri Apr 17 17:02:20 2015 +0900 @@ -92,9 +92,76 @@ Meta computations contains various computations including partiality, nondeterminism, side-effects, exceptions and continuations. \section{Meta computation and Monads} -Meta computations in CbC formalized by Monads so prevent chaos by unlimited computations. +Meta computations in CbC formalized by Monads to prevent chaos by unlimited computations. Monads are a notion of Category Theory, in programs Monad correspondence of normal/meta computations. -For example, function can fail is represented direct sum of values and bottom. +For example, diverging computation as extended normal computations is represented direct sum of normal values and bottom. + +We show formalization of programs for using Monads. +Programs notated typed lambda calculus constructed values and abstractions. +Abstraction f maps value to value, and applies to value x notated $ f x $. +Every lambda term has a type. +Value x has type A notated $ x : A $. +Abstraction f has a argument of type A and return value of type B notated $ f : A \rightarrow B $. + +\begin{eqnarray*} + x : A \\ + f : A \rightarrow B \\ + f x : B \\ +\end{eqnarray*} + +Type matched abstractions can be composed by operator ';'. +Order of composition are commutative. + +\begin{eqnarray*} + f : A \rightarrow B \\ + g : B \rightarrow C \\ + f;g : A \rightarrow C \\ + \\ + h : C \rightarrow D \\ + (f;g);h = f;(g;h) +\end{eqnarray*} + +Abstractions has many arguments notated by abstraction took a argument, and returns a abstraction that argument numbers has decreased(Currying). + +Abstractions can be extended using Monad. +Monad is $ triple (T, \eta, \mu) $ satisfies laws(Figure) % TODO :commutative diagram +Various meta computations represents by definition of triple. +Monad has another description Kleisli Triple $ (T, \eta, \_^{*}) $. + +Kleisli triple are following equations hold: + +\begin{itemize} + \item $ \eta^{*}_A = id_{T A} $ + \item $ \eta;f^{*} = f \mbox{ for } f : A \rightarrow T B $ + \item $ f^{*} ; g^{*} = (f; g^{*})^{*} \mbox{ for } f : A \rightarrow T B \mbox{ and } g : B \rightarrow T C $ +\end{itemize} + +$ id $ is abstraction that identity mapping for any typed values ($ id x = x $). +$ id $ was exists any typed values. +notation $ id_{X} x $ is application $ id $ to a value x typed X. +Then, $ T $ is functor that pair of structure and a map that abstraction for non-structured values to abstraction for structured values. +if applied functor T to type A notated $ T A $. +For example, list of any types is functor. +List can be constructed to any typed values (list of characters, list of integers ...) and can be apply abstraction for contains elements. + +\begin{eqnarray*} + xs = \verb/[10 , 20 , 30]/ \\ + xs : \verb/List Int/ \\ + f : \verb/Int/ \rightarrow \verb/String/ \\ + \verb/[f 10 , f 20 , f 30]/ : \verb/List String/ +\end{eqnarray*} + +It's summarized informal definition of functor for explain Monad. +Values extended using property of functor T extend abstraction to normal values to structured values. + +Abstraction extended by $ \_^{*} $ on Kleisli Triple build from Monad $ (T, \eta, \mu) $. +For Example, definition of diverging computation using Monad are shown. + +\begin{itemize} + \item $ T A = A_{\bot} (= A + \{\bot\}) $ + \item $ \eta_A $ is the inclusion of A into $ A_{\bot} $ + \item if $ f : A \rightarrow T B $, then $ f^{*} (\bot) = \bot $ and $ f^{*}(a) = f (a) $ when $ a $ has type A. +\end{itemize} \section{Modification of Programs using a Monad}