3rdParty/boost/1.78.0/libs/context/doc/html/context/cc.html
| | Home | Libraries | People | FAQ | More |
| | Note | |
call/cc is the reference implementation of C++ proposal P0534R3: call/cc (call-with-current-continuation): A low-level API for stackful context switching.
|
call/cc (call with current continuation) is a universal control operator (well-known from the programming language Scheme) that captures the current continuation as a first-class object and pass it as an argument to another continuation.
A continuation (abstract concept of functional programming languages) represents the state of the control flow of a program at a given point in time. Continuations can be suspended and resumed later in order to change the control flow of a program.
Modern micro-processors are registers machines; the content of processor registers represent a continuation of the executed program at a given point in time. Operating systems simulate parallel execution of programs on a single processor by switching between programs (context switch) by preserving and restoring the continuation, e.g. the content of all registers.
callcc() is the C++ equivalent to Scheme's call/cc operator. It captures the current continuation (the rest of the computation; code after callcc()) and triggers a context switch. The context switch is achieved by preserving certain registers (including instruction and stack pointer), defined by the calling convention of the ABI, of the current continuation and restoring those registers of the resumed continuation. The control flow of the resumed continuation continues. The current continuation is suspended and passed as argument to the resumed continuation.
callcc() expects a context-function with signature 'continuation(continuation && c)'. The parameter c represents the current continuation from which this continuation was resumed (e.g. that has called callcc()).
On return the context-function of the current continuation has to specify an continuation to which the execution control is transferred after termination of the current continuation.
If an instance with valid state goes out of scope and the context-function has not yet returned, the stack is traversed in order to access the control structure (address stored at the first stack frame) and continuation's stack is deallocated via the StackAllocator.
| | Note | |
Segmented stacks are supported by callcc() using [ucontext_t](ff/implementations fcontext_t ucontext_t_and_winfiber.html#implementation).
|
continuation represents a continuation; it contains the content of preserved registers and manages the associated stack (allocation/deallocation). continuation is a one-shot continuation - it can be used only once, after calling continuation::resume() or continuation::resume_with() it is invalidated.
continuation is only move-constructible and move-assignable.
As a first-class object continuation can be applied to and returned from a function, assigned to a variable or stored in a container.
A continuation is continued by calling resume()/resume_with().
namespacectx=boost::context;inta;ctx::continuationsource=ctx::callcc([&a](ctx::continuation&&sink){a=0;intb=1;for(;;){sink=sink.resume();intnext=a+b;a=b;b=next;}returnstd::move(sink);});for(intj=0;j\<10;++j){std::cout\<\<a\<\<" ";source=source.resume();}output:0112358132134
This simple example demonstrates the basic usage of call/cc as a generator. The continuation sink represents the main-continuation (function main()). sink is captured (current-continuation) by invoking callcc() and passed as parameter to the lambda.
Because the state is invalidated (one-shot continuation) by each call of continuation::resume(), the new state of the continuation, returned by continuation::resume(), needs to be assigned to sink after each call.
The lambda that calculates the Fibonacci numbers is executed inside the continuation represented by source. Calculated Fibonacci numbers are transferred between the two continuations via variable a (lambda capture reference).
The locale variables b and next remain their values during each context switch. This is possible due source has its own stack and the stack is exchanged by each context switch.
Data can be transferred between two continuations via global pointers, calling wrappers (like std::bind) or lambda captures.
namespacectx=boost::context;inti=1;ctx::continuationc1=callcc([&i](ctx::continuation&&c2){std::printf("inside c1,i==%d\n",i);i+=1;returnc2.resume();});std::printf("i==%d\n",i);output:insidec1,i==1i==2
callcc(<lambda>) enters the lambda in continuation represented by c1 with lambda capture reference i=1. The expression c2.resume() resumes the continuation c2. On return of callcc(<lambda>), the variable i has the value of i+1.
If the function executed inside a context-function emits an exception, the application is terminated by calling std::terminate(). std::exception_ptr can be used to transfer exceptions between different continuations.
| | Important | |
Do not jump from inside a catch block.
|
Sometimes it is useful to execute a new function on top of a resumed continuation. For this purpose continuation::resume_with() has to be used. The function passed as argument must accept a rvalue reference to continuation and return continuation.
namespacectx=boost::context;intdata=0;ctx::continuationc=ctx::callcc([&data](ctx::continuation&&c){std::cout\<\<"f1: entered first time: "\<\<data\<\<std::endl;data+=1;c=c.resume();std::cout\<\<"f1: entered second time: "\<\<data\<\<std::endl;data+=1;c=c.resume();std::cout\<\<"f1: entered third time: "\<\<data\<\<std::endl;returnstd::move(c);});std::cout\<\<"f1: returned first time: "\<\<data\<\<std::endl;data+=1;c=c.resume();std::cout\<\<"f1: returned second time: "\<\<data\<\<std::endl;data+=1;c=c.resume\_with([&data](ctx::continuation&&c){std::cout\<\<"f2: entered: "\<\<data\<\<std::endl;data=-1;returnstd::move(c);});std::cout\<\<"f1: returned third time"\<\<std::endl;output:f1:enteredfirsttime:0f1:returnedfirsttime:1f1:enteredsecondtime:2f1:returnedsecondtime:3f2:entered:4f1:enteredthirdtime:-1f1:returnedthirdtime
The expression c.resume_with(...) executes a lambda on top of continuation c, e.g. an additional stack frame is allocated on top of the stack. This lambda assigns -1 to data and returns to the second invocation of c.resume().
Another option is to execute a function on top of the continuation that throws an exception.
namespacectx=boost::context;structmy\_exception:publicstd::runtime\_error{ctx::continuationc;my\_exception(ctx::continuation&&c\_,std::stringconst&what):std::runtime\_error{what},c{std::move(c\_)}{}};ctx::continuationc=ctx::callcc([](ctx::continuation&&c){for(;;){try{std::cout\<\<"entered"\<\<std::endl;c=c.resume();}catch(my\_exception&ex){std::cerr\<\<"my\_exception: "\<\<ex.what()\<\<std::endl;returnstd::move(ex.c);}}returnstd::move(c);});c=c.resume\_with([](ctx::continuation&&c){throwmy\_exception(std::move(c),"abc");returnstd::move(c);});output:enteredmy\_exception:abc
In this exception my_exception is throw from a function invoked on-top of continuation c and catched inside the for-loop.
On construction of continuation a stack is allocated. If the context-function returns the stack will be destructed. If the context-function has not yet returned and the destructor of an valid continuation instance (e.g. continuation::operator bool() returns true) is called, the stack will be destructed too.
| | Important | |
Code executed by context-function must not prevent the propagation ofs the detail::forced_unwind exception. Absorbing that exception will cause stack unwinding to fail. Thus, any code that catches all exceptions must re-throw any pending detail::forced_unwind exception.
|
Allocating control structures on top of the stack requires to allocated the stack_context and create the control structure with placement new before continuation is created.
| | Note | |
The user is responsible for destructing the control structure at the top of the stack.
|
namespacectx=boost::context;// stack-allocator used for (de-)allocating stackfixedsize\_stacksalloc(4048);// allocate stack spacestack\_contextsctx(salloc.allocate());// reserve space for control structure on top of the stackvoid\*sp=static\_cast\<char\*\>(sctx.sp)-sizeof(my\_control\_structure);std::size\_tsize=sctx.size-sizeof(my\_control\_structure);// placement new creates control structure on reserved spacemy\_control\_structure\*cs=new(sp)my\_control\_structure(sp,size,sctx,salloc);...// destructing the control structurecs-\>~my\_control\_structure();...structmy\_control\_structure{// captured continuationctx::continuationc;template\<typenameStackAllocator\>my\_control\_structure(void\*sp,std::size\_tsize,stack\_contextsctx,StackAllocatorsalloc):// create captured continuationc{}{c=ctx::callcc(std::allocator\_arg,preallocated(sp,size,sctx),salloc,entry\_func);}...};
namespacectx=boost::context;/\* \* grammar: \* P ---\> E '\0' \* E ---\> T {('+'|'-') T} \* T ---\> S {('\*'|'/') S} \* S ---\> digit | '(' E ')' \*/classParser{charnext;std::istream&is;std::function\<void(char)\>cb;charpull(){returnstd::char\_traits\<char\>::to\_char\_type(is.get());}voidscan(){do{next=pull();}while(isspace(next));}public:Parser(std::istream&is\_,std::function\<void(char)\>cb\_):next(),is(is\_),cb(cb\_){}voidrun(){scan();E();}private:voidE(){T();while(next=='+'||next=='-'){cb(next);scan();T();}}voidT(){S();while(next=='\*'||next=='/'){cb(next);scan();S();}}voidS(){if(isdigit(next)){cb(next);scan();}elseif(next=='('){cb(next);scan();E();if(next==')'){cb(next);scan();}else{throwstd::runtime\_error("parsing failed");}}else{throwstd::runtime\_error("parsing failed");}}};std::istringstreamis("1+1");// execute parser in new continuationctx::continuationsource;// user-code pulls parsed data from parser// invert control flowcharc;booldone=false;source=ctx::callcc([&is,&c,&done](ctx::continuation&&sink){// create parser with callback functionParserp(is,[&sink,&c](charc\_){// resume main continuationc=c\_;sink=sink.resume();});// start recursive parsingp.run();// signal terminationdone=true;// resume main continuationreturnstd::move(sink);});while(!done){printf("Parsed: %c\n",c);source=source.resume();}output:Parsed:1Parsed:+Parsed:1
In this example a recursive descent parser uses a callback to emit a newly passed symbol. Using call/cc the control flow can be inverted, e.g. the user-code pulls parsed symbols from the parser - instead to get pushed from the parser (via callback).
The data (character) is transferred between the two continuations.
| | Copyright © 2014 Oliver Kowalke
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|