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.
+