Subcontinuations

Continuations have proven to be useful for implementing a variety of control structures, including exception handling facilities and breadth-first searching algorithms. However, traditional continuations are not useful in the presence of concurrency, because the notion of the rest of the computation represented by a continuation does not in general make sense. Traditional continuations can also be difficult to use in nonconcurrent settings, since their global nature is sometimes problematic. This article presents a new type of continuation, called asubcontinuation. Just as a traditional continuation represents the rest of a computation ¿from a given point in the computation, a subcontinuation represents the rest of asubcomputation ¿from a given point in the subcomputation. Subcontinuations may be used to control tree-structured concurrency by allowing nonlocal exits to arbitrary points in a process tree and allowing the capture of a subtree of a computation as a composable continuation for later use. In the absence of concurrency the localized control achievable with subcontinuations makes them more useful than traditional continuations.This material is based on work supported by the National Science Foundation under grant number CCR-88-03432 and by Sandia National Laboratories under contract number 06-06211. This article is a revised and extended version of a paper presented at the 1990 ACM Conference on Principles and Practice of Parallel Programming.Robert Hieb died in an automobile accident in April 1992.     

Threads Yield Continuations

Just as a traditional continuation represents the rest of acomputation from a given point in the computation, a subcontinuationrepresents the rest of a subcomputation from agiven point in the subcomputation. Subcontinuationsare more expressive than traditional continuations and have been shown to beuseful for controlling tree-structured concurrency, yet they havepreviously been implemented only on uniprocessors. This article describes aconcurrent implementation of one-shot subcontinuations. Like one-shotcontinuations, one-shot subcontinuations are first-class but may be invokedat most once, a restriction obeyed by nearly all programs that usecontinuations. The techniques used to implement one-shot subcontinuationsmay be applied directly to other one-shot continuation mechanisms and may begeneralized to support multi-shot continuations as well. A novel feature ofthe implementation is that continuations are implemented in terms ofthreads. Because the implementation model does not rely upon any speciallanguage features or compilation techniques, the model is applicable toany language or language implementation that supports a small set of threadprimitives.     

Threads Yield Continuations

Just as a traditional continuation represents the rest of acomputation from a given point in the computation, a subcontinuationrepresents the rest of a subcomputation from agiven point in the subcomputation. Subcontinuationsare more expressive than traditional continuations and have been shown to beuseful for controlling tree-structured concurrency, yet they havepreviously been implemented only on uniprocessors. This article describes aconcurrent implementation of one-shot subcontinuations. Like one-shotcontinuations, one-shot subcontinuations are first-class but may be invokedat most once, a restriction obeyed by nearly all programs that usecontinuations. The techniques used to implement one-shot subcontinuationsmay be applied directly to other one-shot continuation mechanisms and may begeneralized to support multi-shot continuations as well. A novel feature ofthe implementation is that continuations are implemented in terms ofthreads. Because the implementation model does not rely upon any speciallanguage features or compilation techniques, the model is applicable toany language or language implementation that supports a small set of threadprimitives.     

On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

Logic continuations

We develop a “complete” embedding of logic programming into scheme—a lexically scoped lisp dialect with first-class continuations. Logic variables are bound in the scheme environment, and the success and failure continuations are represented as scheme continuations. To account for the semantics of logic variables and failure continuations, the state-space model of control is modified in a novel way that generalizes the trail mechanism. This ensures that logic variable bindings are properly restored when continuations are invoked to perform “lateral” control transfers that are not possible in a traditional logic programming context. It is thereby possible to obtain greater control flexibility while allowing much of a program to be expressed with logic programming.     

Unsafe operations in B-trees

Summary A simple mathematical model for analyzing the dynamics of a B-tree node is presented. From the solution of the model, it is shown that the simple technique of allowing a B-tree node to be slightly less than half full can significantly reduce the rate of split, merge and borrow operations. We call split, merge, borrow and balance operations unsafe operations in this paper. In a multi-user environment, a lower unsafe operation rate implies less blocking and higher throughput, even when tailored concurrency control algorithms (e.g., that proposed by Lehman and Yao [10]) are used. A lower unsafe operation rate also means a longer life time of an optimally initialized B-tree (e.g., compact B-tree). It is in general useful to have an analytical model which can predict the rate of unsafe operations in a dynamic data structure, not only for comparing the behavior of variations of B-trees, but also for characterizing workload for performance evaluation of different concurrency control algorithms for such data structures. The model presented in this paper represents a starting point in this direction.     

Using a Continuation Twice and Its Implications for the Expressive Power of call/cc

We study the implications for the expressive power of call/cc of upward continuations, specifically the idiom of using a continuation twice. Although such control effects were known to Landin and Reynolds when they invented J and escape, the forebears of call/cc, they still act as a conceptual pitfall for some attempts to reason about continuations. We use this idiom to refute some recent conjectures about equivalences in a language with continuations, but no other effects. This shows that first-class continuations as given by call/cc have greater expressive power than one would expect from goto or exits.     

Comparing Control Constructs by Double-Barrelled CPS

We investigate call-by-value continuation-passing style transforms that pass two continuations. Altering a single variable in the translation of -abstraction gives rise to different control operators: first-class continuations; dynamic control; and (depending on a further choice of a variable) either the return statement of C; or Landin's J-operator. In each case there is an associated simple typing. For those constructs that allow upward continuations, the typing is classical, for the others it remains intuitionistic, giving a clean distinction independent of syntactic details. Moreover, those constructs that make the typing classical in the source of the CPS transform break the linearity of continuation use in the target.     

Parallel object monitors

Coordination of parallel activities on a shared memory machine is a crucial issue for modern software, even more with the advent of multi‐core processors. Unfortunately, traditional concurrency abstractions force programmers to tangle the application logic with the synchronization concern, thereby compromising understandability and reuse, and fall short when fine‐grained and expressive strategies are needed. This paper presents a new concurrency abstraction called POM, parallel object monitor, supporting expressive means for coordination of parallel activities over one or more objects, while allowing a clean separation of the coordination concern from application code. Expressive and reusable strategies for concurrency control can be designed, thanks to a full access to the queue of pending requests, parallel execution of dispatched requests together with after‐actions, and complete control over reentrancy. A small domain‐specific aspect language is provided to adequately configure pre‐packaged, off‐the‐shelf synchronizations. Copyright © 2007 John Wiley & Sons, Ltd.     

A type-theoretic foundation of delimited continuations

There is a correspondence between classical logic and programming language calculi with first-class continuations. With the addition of control delimiters, the continuations become composable and the calculi become more expressive. We present a fine-grained analysis of control delimiters and formalise that their addition corresponds to the addition of a single dynamically-scoped variable modelling the special top-level continuation. From a type perspective, the dynamically-scoped variable requires effect annotations. In the presence of control, the dynamically-scoped variable can be interpreted in a purely functional way by applying a store-passing style. At the type level, the effect annotations are mapped within standard classical logic extended with the dual of implication, namely subtraction. A continuation-passing-style transformation of lambda-calculus with control and subtraction is defined. Combining the translations provides a decomposition of standard CPS transformations for delimited continuations. Incidentally, we also give a direct normalisation proof of the simply-typed lambda-calculus with control and subtraction.     

Dynamic slicing of concurrent specification languages

Dynamic slicing is a technique to extract the part of the program (called slice) that influences or is influenced, in a particular execution, by a given point of interest in the source code (called slicing criterion). Since a single execution is considered, the technique often uses a trace of this execution to analyze data and control dependencies. In this work we present the first formulation and implementation of dynamic slicing in the context of CSP. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. We base our technique on a new data structure to represent CSP computations called track. A track is a data structure which represents the sequence of expressions that have been evaluated during the computation, and moreover, it is labeled with the location of these expressions in the specification. The implementation of a dynamic slicer for CSP is useful for debugging, program comprehension, and program specialization, and it is also interesting from a theoretical perspective because CSP introduces difficulties such as heavy concurrency and non-determinism, synchronizations, frequent absence of data dependence, etc.     

Integrated concurrency control in shared B-trees

The traditional approach to concurrency control in sharedB-trees is based on locking. Recently new methods have been proposed called optimistic methods. In contrast to locking these methods achieve correct operations on theB-tree by a restart mechanism. In this paper we present a new approach to concurrency control, which integrates locking and the optimistic method. Practical applications are pointed out in which this approach can be expected to be superior to either locking or the optimistic method.     

Obtaining coroutines with continuations

Continuations, when made available to the programmer as first class objects, provide a general control abstraction for sequential computation. The power of first class continuations is demonstrated by implementing a variety of coroutine mechanisms using only continuations and functional abstraction. The importance of general abstraction mechanisms such as continuations is discussed.     

Deriving Proof Rules from Continuation Semantics

We claim that a continuation style semantics of a programming language can provide a starting point for constructing its proof system. The basic idea is to see weakest preconditions as a particular instance of continuation style semantics, hence to interpret correctness assertions (e.g. Hoare triples {p} C {r}) as inequalities over continuations. This approach also shows a correspondence between labels in a program and annotations. Received July 1997 / Accepted in revised form August 1999     

Relational structures model of concurrency

The paper deals with the foundations of concurrency theory. We show how structurally complex concurrent behaviours can be modelled by relational structures (X, ¨, \sqsubset){(X, \diamondsuit, \sqsubset)} , where X is a set (of event occurrences), and ¨{\diamondsuit} (interpreted as commutativity) and \sqsubset{\sqsubset} (interpreted as weak causality) are binary relations on X. The paper is a continuation of the approach initiated in Gaifman and Pratt (Proceedings of LICS’87, pp 72–85, 1987), Lamport (J ACM 33:313–326, 1986), Abraham et al. (Semantics for concurrency, workshops in computing. Springer, Heidelberg, pp 311–323, 1990) and Janicki and Koutny (Lect Notes Comput Sci 506:59–74, 1991), substantially developed in Janicki and Koutny (Theoretical Computer Science 112:5–52, 1993) and Janicki and Koutny (Acta Informatica 34:367–388, 1997), and recently generalized in Guo and Janicki (Lect Notes Comput Sci 2422:178–191, 2002) and Janicki (Lect Notes Comput Sci 3407:84–98, 2005). For the first time the full model for the most general case is given.     

Discussion about parameterization in the asymptotic numerical method: Application to nonlinear elastic shells

The Asymptotic Numerical Method (ANM) is a family of algorithms for path following problems based on the computation of truncated vectorial series with respect to a path parameter “a” [B. Cochelin, N. Damil, M. Potier-Ferry, Méthode Asymptotique Numérique, Hermès-Lavoisier, Paris, 2007]. In this paper, we discuss and compare three concepts of parameterizations of the ANM curves i.e. the definition of the path parameter “a”. The first concept is based on the classical arc-length parameterization [E. Riks, Some computational aspects of the stability analysis of nonlinear structures, Computer Methods in Applied Mechanics and Engineering, 47 (1984) 219–259], the second is based on the so-called local parameterization [W. C. Rheinboldt, J. V. Burkadt, A Locally parameterized continuation, Acm Transaction on mathematical Software, 9 (1983) 215–235; R. Seydel, A Tracing Branches, World of Bifurcation, Online Collection and Tutorials of Nonlinear Phenomena (http://www.bifurcation.de), 1999; J. J. Gervais, H. Sadiky, A new steplength control for continuation with the asymptotic numerical method, IAM, J. Numer. Anal. 22, No. 2, (2000) 207–229] and the third is based on a minimization condition of a rest [S. Lopez, An effective parametrization for asymptotic extrapolation, Computer Methods in Applied Mechanics and Engineering, 189 (2000) 297–311]. We demonstrate that the third concept is equivalent to a maximization condition of the ANM step lengths. To illustrate the performance of these proposed parameterizations, we give some numerical comparisons on nonlinear elastic shell problems.     

Prescheduling policy for real-time concurrency control: A performance evaluation

A new priority management policy, aprescheduling policy, is proposed. This policy can be applied on any conventional concurrency control protocol to schedule a real-time transaction. Costly preemption is avoided by the prescheduling policy, and parsing dataset of a transaction is not needed. Three widely used conventional concurrency control protocols (dynamic two-phase locking, basic timestamp ordering, and optimistic) are incorporated with the prescheduling policy to form three real-time concurrency control protocols. Performance of the three protocols is evaluated from three different viewpoints: database management systems, protocols, and transaction. From a database management system viewpoint, we show the prescheduling policy can improve the performance of protocols by raising thevalid ratio and reducingrestart counts. In general, two-phase locking with the prescheduling policy performs the best in most cases and yields the best choice for concurrency control in a real-time application. Deciding factors that affect performance of each protocol are identified from protocol viewpoint. Some suggestions are given for writing a timely transaction from the aspect of transaction viewpoint.     

Abstracting timed preemption with engines

The need for a programming language abstraction for timed preemption is argued, and several possibilities for such an abstraction are presented. One, called engines, is adopted. Engines are an abstraction of bounded computation, not a process abstraction in the usual sense. However, in conjuction with first class continuations, engines allow a language to be extended with time-sharing implementations for a variety of process abstraction facilities. We present a direct implementation of hiaton streams. Engine nesting refers to the initiation of an engine computation by an already running engine. We consider the need for engine nesting and show how it may be accomplished in a manner that charges a parent engine for the computation of its offspring. We conclude by discussing the importance of simple and general abstractions such as engines.     

一种基于时间戳的面向对象数据库的并发控制算法

本文提出了一种基于时间戳的面向对象数据库（ＯＯＤＢ，ｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄｄａｔａｂａｓｅ）的并发控制算法．设计这一算法时，我们首先按照ＯＯＤＢ的数据模型对传统的时间戳算法进行扩展，然后利用抽象数据类型的语义定义了相容性矩阵，对不同级别的并发性冲突操作进行不同的处理，从而达到在系统开销尽可能小的情况下，尽可能大地增加数据库存取操作的并发度的效果．这一算法的优点是：①利用对象版本的时间信息减少了数据项的读写时间戳所需的额外存储空间；②消除了封锁算法带来的封锁及死销预防或死锁检测所需要的系统开销。本文还用模拟的方法给出了新算法和ＯＲＩＯＮ中使用的封锁算法之间的性能比较     

基于四叉树索引的区域版本实时协同绘图系统

随着传统GIS向网络GIS的发展,地图的更新通常需要网络中多个站点相互协作完成,传统的并发控制策略不能很好满足协同GIS中多用户协作感知的要求。为此提出了基于四叉树索引的区域版本并发控制机制,并给出了基于四叉树索引的区域版本实时协同绘图系统的框架和相关问题的解决方案。