Mercurial > hg > Papers > 2015 > kono-lola
changeset 4:8d0f97fd8af3
fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 12 May 2015 10:44:14 +0900 |
parents | 259facc91c65 |
children | 32ec7f73f166 |
files | gears.ind lola2015.tex |
diffstat | 2 files changed, 150 insertions(+), 74 deletions(-) [+] |
line wrap: on
line diff
--- a/gears.ind Tue May 12 04:07:34 2015 +0900 +++ b/gears.ind Tue May 12 10:44:14 2015 +0900 @@ -2,17 +2,24 @@ --abstract: ---Reliable computation and predictablity +We introduce system of code and data. Instead of function call, code accepts input data and simply generates output data. +Chains of code and data performs computation. After calling next code, it does not return to the caller, so it has no +environment nor calling stack. This system is designed for reliable system description and parallel execution on various +architecture. We use segments or gears sometime. This is directly connected to the category theory like lambda calculus. +We also find a categorical representation from the view point of data. This shows duality of code and data. This duality will be +a guideline of our system design. -Various softwares are used in real world. Each of them have to work in a reliable way. A peice of devie contains -millons of lines of code. These programs are written in C, Haskell and so on. +--Reliable computation and predictability + +Various software are used in real world. Each of them have to work in a reliable way. A piece of device contains +millions of lines of code. These programs are written in C, Haskell and so on. To assure its reliability, the computation of a function should be predictable. -The correctness of the predecion should be assured by measurements, model checkings or proofs. +The correctness of the prediction should be assured by measurements, model checking or proofs. % The unit of computation of conventional programming language is of course a function call. % a function may call another functions and it comes back to the original function. % Proof theory such as Hoare Logic or model checking method is used to make the prediction, such as -% zero divide is never occured in a function. +% zero divide is never occurred in a function. We propose new unit of computation, data segments and code segments. Computations in these segments are finite and predictable. We sometimes call these gears. @@ -26,7 +33,7 @@ --Definition of data segment and code segment -Actually we implment our Gears language in LLVM\cite{LLVM}, but we can think both code and data are System F\cite{} term. As usuall, Types are +Actually we implement our Gears language in LLVM\cite{LLVM}, but we can think both code and data are System F\cite{Girard:1989:PT:64805} term. As usual, Types are defined starting from type variables X,Y,Z and is generated by two operations: 1. if U and V are types, then U → V is a type. @@ -35,44 +42,48 @@ Terms are constructed by six schemes 1. variable: $x^T, y^T, z^T,...$ of type $T$, - 2. application: $tu$ ov type $V$, where $t$ is of type $U→V$ and $u$ is of type $U$, + 2. application: $tu$ of type $V$, where $t$ is of type $U→V$ and $u$ is of type $U$, 3. λ-abstraction: $λx^U.v$ of type $U→V$, where $x^U$ is a variable of type $U$ and $v$ is of type $V$, 4. universal abstraction: if $v$ is a term type V, then we can form $ΛX.v$ of type $ΠX.V$, so long as the variable $X$ is not free in the type of a free variable of $v$. - 5. universal application: if $t$ is a term of type $ΠX.V$ and $U$ is a type, then %tU$ is a tem of type $V[U/X]$. + 5. universal application: if $t$ is a term of type $ΠX.V$ and $U$ is a type, then %tU$ is a term of type $V[U/X]$. -and usuall conversions, +and usual conversions, 1. (λx.v)u 〜> v[u/x] 2. (ΛX.v)U 〜> v[U/X] -Code segments of type $C$ accepts data segments of type $I$ and generates data segments of type $O$. +What we need here is that a term has a type, a function has type $U → V$. +Code segments f of type $I → O$, accepts data segments of type $I$ and generates data segments of type $O$. - C : I → O + f : I → O -Domain of C is I and codemain of C is O. +Domain of C is I and codomain of C is O. -<center><img src="fig/codeGear.jpg"></center> +Gears system only allows calling another code at the bottom of the code, that is all codes have tail call form. Normal function call +is not prohibited, but it should be closed in a code. + +<center><img src="fig/codeGear.svg"></center> --Meta computation of Gears -Computation of a code is limited in the inputs and the outputs and it makes the compuation of the code predictable, but its data are -ususally connected to other data. The code has its continuation also. These connections are out of the scope of the code. -We think these connections are made by a meta computation, such as monads\cite{}. A monad is a data structure with monad laws and -after an execution of a code, monad's join code is called to handle meta data structure. With monad $T$, +Computation of a code is limited in the inputs and the outputs and it makes the computation of the code predictable, but its data are +usually connected to other data. The code has its continuation also. These connections are out of the scope of the code. +We think these connections are made by a meta computation, such as monads\cite{Moggi:1989:CLM:77350.77353}. A monad is a data structure with monad laws and +after an execution of a code, monads join code is called to handle meta data structure. With monad $T$, C' : I → T O -is a meta compuation. $C$ has one to one correcpondence with $C'$. +is a meta computation. $C$ has one to one correspondence with $C'$. μ : T (T O) → T O -Parallel execution or IO handling are represented as a monad in our scheme. +Parallel execution or IO handling are represented as a monad in our scheme. Monads are only allows to use at the bottom of a code in our system. -<center><img src="fig/meta.jpg"></center> +<center><img src="fig/meta.svg"></center> ---A cateogy of codes +--A category of codes -Types of code segments and data segments narually compose a category of function and types. Codes and data are interconnected one by one. +Types of code segments and data segments naturally compose a category of function and types. Codes and data are interconnected one by one. Object : a, b, c ... Arrows : f, g, h ... @@ -84,11 +95,11 @@ g : b → c f : c → d -There is compositon of arrows, +There is composition of arrows, f o g : b → d -and it satisfies the compisition law. +and it satisfies the composition law. (f o g) o h = f o (g o h ) @@ -96,42 +107,42 @@ a o id (domain a) = a = id (domain a) o a ---A cateogy of data +--A category of data A code generate an output type and it becomes an input type of next code. It is similar to a code is in between an input type and an output type. Is is possible to think data is an arrow between codes? -<center><img src="fig/dataGear.jpg"></center> +<center><img src="fig/dataGear.svg"></center> -In other words, is there any duality in codes and data? Ususall answer is no, since we cannot simply combine data segments, +In other words, is there any duality in codes and data? Usual answer is no, since we cannot simply combine data segments, but introducing continuation, it is possible to create a category which objects are functions and which arrows are data. Actually these two categories are dual in the sense of adjunction, that is -there is a one to one corespondense between their arrows with isomorphism. +there is a one to one correspondence between their arrows with isomorphism. Here we show the duality as an exercise of a category theory. -The problem of data segments compisition is that it forgets about later computation. We can simply store it as a continuation in the +The problem of data segments composition is that it forgets about later computation. We can simply store it as a continuation in the data segment. Data segments now have a continuation, which is a code segment. It is a part of meta computation. We have a data $f$, which is a codomain of a code $a$ and is a domain of code $b$. A continuation of $f$ will called before the execution of code $b$. -Now an data arrow $f$ is a triplet ${a,b,n}$, $a$ is a code which codomain is data $f$ and $b$ is a code wich domain is data $f$. +Now an data arrow $f$ is a triplet ${a,b,n}$, $a$ is a code which codomain is data $f$ and $b$ is a code which domain is data $f$. $n : codomain a → domain b $ is a continuation of $f$. -We introdue access function as follows: +We introduce access function as follows: data-domain f = a data-codomain f = b continuation f = n -We use data-codomain and data-comain for new Data Category C, which is constructed from a category C. +We use data-codomain and data-codomain for new Data Category C, which is constructed from a category C. Objects of Data category C are arrows of category C. An arrow of Data category C from $a$ to $c$ is -a data segment $f$ with continuation $n$, $b'$ is a intermidiate data segment. +a data segment $f$ with continuation $n$, $b'$ is a intermediate data segment. n : codomain a → domain b f = {a,b,n} $f$ is an arrow from $a$ to $b$. -<center><img src="fig/dataGearComposition.jpg"></center> +<center><img src="fig/dataGearComposition.svg"></center> If $f$ and $g$ has same data-domain and data-codomain, an equality of $f$ and $g$ is defined as follows, @@ -139,7 +150,7 @@ where $b$ is data-codomain of $f$ and $g$. -Compisition of arrows of Data category is defined as follows. +Composition of arrows of Data category is defined as follows. {b,c,m} ∙ {a,b,n} = {a,c,m o (b o n))} @@ -155,13 +166,13 @@ To make an identity arrow in the Data category, if $a$ is a codomain of $f$, we need a reverse arrow of $a$, $a'$. So every arrows $a$ in C have to have a reverse arrow $a'$, where - a o a' = id (codmain a) + a o a' = id (codomain a) -Then an identity data segment of $a$ in Data Categoy C is +Then an identity data segment of $a$ in Data Category C is {a,a,a'} -<center><img src="fig/IdDataGear.jpg"></center> +<center><img src="fig/IdDataGear.svg"></center> To check $data(f,a')$ is an identity, @@ -172,14 +183,14 @@ --A trivial duality of code and data -<center><img src="fig/Duality.jpg"></center> +<center><img src="fig/Duality.svg"></center> -Data category is a data segment with continuation, which is one step behind, so there is a trivial one to one corespondence. -It is also easy to show C and Data category C is an adjuntion pair. We show it using a universal mapping problem. +Data category is a data segment with continuation, which is one step behind, so there is a trivial one to one correspondence. +It is also easy to show C and Data category C is an adjunction pair. We show it using a universal mapping problem. Data segments in a Data category C is an object of original category C, so it has an identity arrow, -which is an object of Data Category C . Acturally, we have a map F, +which is an object of Data Category C . Actually, we have a map F, F : Obj C → Obj (Data Category C) F a = id a @@ -189,10 +200,10 @@ U d = codomain d U {a,b,n} = b o n -wehre $d$ is an object of Data Category C, and ${a,b,n}$ is an arrow from $a$ to $b$, with continuation $n$. -Identity law and distribution law of $U$ is easily checked as +where $d$ is an object of Data Category C, and ${a,b,n}$ is an arrow from $a$ to $b$, with continuation $n$. +Identity law and distribution law of $U$ is easyly checked as - U {a,a,a'} = a o a' = id (codmain a) + U {a,a,a'} = a o a' = id (codomain a) We need a mapping $η$, which will be a natural transformation. @@ -211,7 +222,7 @@ U ( *f ) o (η a) = (b o (b' o f) ) o id a = f -is directry checke and $*f$ is unique, that is +is directly checked and $*f$ is unique, that is if there is an arrow g $U g o (η a) = f$ then $g = *f$. @@ -227,28 +238,29 @@ --Comparison -Meta compuation in Haskell\cite{} is defined as set of explict monads. In Gears, meta computation is unique among the system, +Meta computation in Haskell is defined as set of explicit monads. In Gears, meta computation is unique among the system, which is something like operating system kernel or libraries. -In Open CL\cite{} or Cuda\cite{}, there is a code segment which is called kernel. The kernel runs parallelly in a GPU. The kernel +In OpenCL\cite{opencl} or Cuda\cite{cuda}, there is a code segment which is called kernel. The kernel runs parallelly in a GPU. The kernel is very similar to our code segment. -Object oriented languages, such as Smalltalk-80 or Java , has meta compuation as a virtual machines. It is very different from -monad or meta computation of our Gears system. Data segment has no idenity such as Smalltalk's self, it can be copied easily, -which is a very good property in a parallel compuation environment. +Object oriented languages, such as Smalltalk-80 or Java , has meta computation as a virtual machines. It is very different from +monad or meta computation of our Gears system. Data segment has no identity such as Smalltalk's self, it can be copied easyly, +which is a very good property in a parallel computation environment. -Code segment can be seen as a kind of Typed assembly language, which has typed input and predictable behaviour. +Code segment can be seen as a kind of Typed assembly language, which has typed input and predictable behavior. In old age, there is a software design method called data flow diagram. Category of code and data is very much like -data flow diagram approach. It can be seen as a rivival of main frame technologies. +data flow diagram approach. It can be seen as a revival of main frame technologies. --Conclusion -As usual categorrical result, trivial duality of category and Data category means nothing itself. +As usual categorical result, trivial duality of category and Data category means nothing itself. During the design of gears system, we see similarities of code segment and data segment. It has -meta segments and contnuations. We think the duality gives us some guidance to design software +meta segments and continuations. We think the duality gives us some guidance to design software system such as an operating system or libraries. -We have implemented Gears system on top of LLVM\cite{} and hope it can be used as real sysetm description language. +We have implemented Gears system on top of LLVM\cite{LLVM} and hope it can be used as real system description language. +
--- a/lola2015.tex Tue May 12 04:07:34 2015 +0900 +++ b/lola2015.tex Tue May 12 10:44:14 2015 +0900 @@ -1,34 +1,98 @@ -\documentclass[envcountsame]{llncs} +\documentclass[conference]{IEEEtran} \usepackage[dvipdfmx]{graphicx} -\usepackage{llncsdoc} +\usepackage[cmex10]{amsmath} \usepackage{url} \usepackage{listings} +\lstset{ + frame=single, + keepspaces=true, + stringstyle={\ttfamily}, + commentstyle={\ttfamily}, + identifierstyle={\ttfamily}, + keywordstyle={\ttfamily}, + basicstyle={\ttfamily}, + breaklines=true, + xleftmargin=0zw, + xrightmargin=0zw, + framerule=.2pt, + columns=[l]{fullflexible}, + numbers=left, + stepnumber=1, + numberstyle={\scriptsize}, + numbersep=1em, + language={}, + tabsize=4, + lineskip=-0.5zw, + escapechar={@}, +} -\bibliographystyle{plain} % for bibliography -%\title{The implementation of recursive type syntax on GCC-4.6 for CbC} -\title{Recursive type syntax in Continuation based C} -\titlerunning{title running} -\toctitle{toc title} -%\subtitle{sub title} -\author{Shinji Kono\inst{1} Nobuyasu Oshiro\inst{2}} -\authorrunning{authorrunning} -\institute{University of the Ryukyus} -\email{} +\ifCLASSINFOpdf + % \usepackage[pdftex]{graphicx} + % declare the path(s) where your graphic files are + % \graphicspath{{../pdf/}{../jpeg/}} + % and their extensions so you won't have to specify these with + % every instance of \includegraphics + % \DeclareGraphicsExtensions{.pdf,.jpeg,.png} +\else + % or other class option (dvipsone, dvipdf, if not using dvips). graphicx + % will default to the driver specified in the system graphics.cfg if no + % driver is specified. + % \usepackage[dvips]{graphicx} + % declare the path(s) where your graphic files are + % \graphicspath{{../eps/}} + % and their extensions so you won't have to specify these with + % every instance of \includegraphics + % \DeclareGraphicsExtensions{.eps} +\fi + + +% correct bad hyphenation here +% \hyphenation{op-tical net-works semi-conduc-tor} + \begin{document} -\maketitle -\input common +% +% paper title +% Titles are generally capitalized except for words such as a, an, and, as, +% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually +% not capitalized unless they are the first or last word of the title. +% Linebreaks \\ can be used within to get better formatting as desired. +% Do not put math or special symbols in the title. +\title{ Programming in code and data and its duality} + +% author names and affiliations +% use a multiple column layout for up to three different +% affiliations +\author{ +\IEEEauthorblockN{Shinji KONO} +\IEEEauthorblockA{University of the Ryukyus \\ Email: kono@ie.u-ryukyu.ac.jp} +} + +% make the title area +\maketitle + + +% As a general rule, do not put math, special symbols or citations +% in the abstract +% As a general rule, do not put math, special symbols or citations +% in the abstract \begin{abstract} -\input{abstract} +\input{abstract} \end{abstract} -%\pagenumbering{arabic} +% For peer review papers, you can put extra information on the cover +% page as needed: +% \ifCLASSOPTIONpeerreview +% \begin{center} \bfseries EDICS Category: 3-BBND \end{center} +% \fi +% +% For peerreview papers, this IEEEtran command inserts a page break and +% creates the second title. It will be ignored for other modes. +\IEEEpeerreviewmaketitle \input{0} % sections \bibliography{ref} -\nocite{r4rs,CompilingWithContinuation,kono08f} - \end{document}