Mercurial > hg > Papers > 2012 > aplas
changeset 37:bda0b56c9231
fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 16 Jun 2012 01:02:37 +0900 |
parents | 2dd2b481b291 |
children | 34a726a5c0d4 |
files | paper/rectype.ind |
diffstat | 1 files changed, 48 insertions(+), 62 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/rectype.ind Sat Jun 16 00:22:34 2012 +0900 +++ b/paper/rectype.ind Sat Jun 16 01:02:37 2012 +0900 @@ -19,7 +19,24 @@ --Motivation +The C programming language is used in many practical programs, operating system +kernels, byte code machines, network servers or embeded systems. Low level feature +of C is useful, but sometimes it requres programming hacks. For example, in case of +byte code machine often entire program is a huge switch statement which has many +labels which corespond the byte codes. Operating system or network server has +many layers such as system call dispatch, transport or presentation layer. It +requires deep call levels, 2 or 3 for each layer, resulting 10-30 call levels. +Continuation based C (CbC) provids a structured way to represent these situations. It +is a small modication of C. It consists of a syntax to force tail-call-elimation +and parametarized goto statement. + +C has capable of recursive functions, but we find it's type system is not enough +to represent CbC programming. In this paper, we introduce \rectype +keyward as a recursive type. To handle recursive type, conventionally tagged struct +is used. It is also fit for CbC program. + +We will describe the CbC and \rectype implementation of CbC on GCC 4.6.0. --Continuation based C @@ -78,89 +95,58 @@ -CbC is a kind of high level assembler language. It can do several -original C language cannot do. For examples, - - Thread Scheduler - Context Switch - Synchronization Primitives - I/O wait semantics - - -are impossible to write in C. Usually it requires some help of -assembler language such as \verb+__asm+ statement extension which is -of course not portable. - ---Scheduler example - -We can easily write these things in CbC, because -CbC has no hidden information behind the stack frame of C. -A thread simply go to the scheduler, - - goto scheduler(self, task_list); - - -and the scheduler simply pass the control to the next -thread in the task queue. - - code scheduler(Thread self,TaskPtr list) - { - TaskPtr t = list; - TaskPtr e; - list = list->next; - goto list->thread->next(list->thread,list); - } - -Of course it is a simulator, but it is an implementation -also. If we have a CPU resource API, we can write real multi -CPU scheduler in CbC. - -This is impossible in C, because we cannot access the hidden -stack which is necessary to switch in the scheduler. In CbC, -everything is visible, so we can switch threads very easily. - -This means we can use CbC as an executable specification -language of OS API. - - --Recursive type syntax -CbC's program pass next pointer of Code Segment on argument. -It is passed as follows. +A continuation is a pointer to a Code Segment to be executed after. +For example, it is passed as follows; __code csA( __code (*p)() ) { goto p(csB); } -p is next pointer of Code Segment. -But, This declaration is not right. -Because p have arguments. -We wanted to the same type of p's arguments as type of csA's arguments. -Right declaration is as follows. +where {\tt p} is the continuation and {\tt csB} is a Code Segment which +has the same type of {\tt csA}. This declaration is not enough because +it lacks the type of the argument. If add the type declaration, we +get following program; - __code csA( __code (*p)( __code (*)( __code (*)( __code *)))) { + __code csA( __code (*p)( __code (*)( __code (*)( __code (*)())))) { goto p(csB); } -The syntax of C Must be declared recursively. -The following declaration if it may be that the type checking of p. - +or __code csA( __code (*p)( __code(*)())) { goto p(csB); } -However this declaration is to require long typing. -Therefore we implemented \rectype syntax in CbC on GCC. +It is enough to type {\csB}, but of course it is not completly wll typed. +Omitting types of the arguments of a function is allowed, but it requires +complex declaration and it is imcomplete. -\rectype syntax is declare a recursive type. -This example is using \rectype syntax. +We introduce \rectype syntax for this situation. In an argument declation, +\rectype represents it's fuction type. Using \rectype, previous example can +be written like this; __code csA( __rectype *p) { goto p(csB); } -*p represent pointer of csA at \ref{code:rectype} . -p's argument type is same csA that function pointer. +{\tt *p} has a type of {\tt csA} itself. + +The same situation is happen in convetional C, since Code Segment is a +mere C function with tail-call-elimination. \rectype provides exact and +concise way to describe recursive type. If we have extra arguments, + + __code csBs(int a, __rectype *p) ; + + __code csAs(int a, __rectype *p) { + goto p(a, csBs); + } + +In this case, we have two \rectype keywords. It may points the same type or +different types. There is no ambiguity here, because it point the exact +position. If it points the same position in the same type declaration, +it is the same type. +