Completeness of Continuation Models for λμ-Calculus

We show that a certain simple call-by-name continuation semantics of Parigot's λ_μ-calculus is complete. More precisely, for every λ_μ-theory we construct a cartesian closed category such that the ensuing continuation-style interpretation of λ_μ, which maps terms to functions sending abstract continuations to responses, is full and faithful. Thus, any λ_μ-category in the sense of L. Ong (1996, in “Proceedings of LICS '96,” IEEE Press, New York) is isomorphic to a continuation model (Y. Lafont, B. Reus, and T. Streicher, “Continuous Semantics or Expressing Implication by Negation,” Technical Report 93-21, University of Munich) derived from a cartesian-closed category of continuations. We also extend this result to a later call-by-value version of λ_μ developed by C.-H. L. Ong and C. A. Stewart (1997, in “Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, January 1997,” Assoc. Comput. Mach. Press, New York).     

The logic of aliasing

Summary We present a new version of Hoare's logic that correctly handles programs with aliased variables. The central proof rules of the logic (procedure call and assignment) are proved sound and complete.An earlier version of this paper appeared in the Proceedings of the Fifth ACM Symposium on Principles of Programming Languages, 1978. This research has been partially supported by National Science Foundation grants MCS 76-14293 and MCS 76-000327     

On the computational cost of disjunctive logic programming: Propositional case

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is ₂ ^p -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is ₂ ^p -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.Parts of the results in this paper appeared in form of an abstract in the Proceedings of the Twelfth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pp. 158–167. Other parts appeared in shortened form in the Proceedings of the International Logic Programming Symposium, Vancouver, October 1993 (ILPS-93), pp. 266–278. MIT Press.     

Supporting Function Calls within PELCR

In [M. Pedicini and F. Quaglia. A parallel implementation for optimal lambda-calculus reduction PPDP '00: Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 3–14, ACM, 2000, M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005], PELCR has been introduced as an implementation derived from the Geometry of Interaction in order to perform virtual reduction on parallel/distributed computing systems.In this paper we provide an extension of PELCR with computational effects based on directed virtual reduction [V. Danos, M. Pedicini, and L. Regnier. Directed virtual reductions. In M. Bezem D. van Dalen, editor, LNCS 1258, pages 76–88. EACSL, Springer Verlag, 1997], namely a restriction of virtual reduction [V. Danos and L. Regnier. Local and asynchronous beta-reduction (an analysis of Girard's EX-formula). LICS, pages 296–306. IEEE Computer Society Press, 1993], which is a particular way to compute the Geometry of Interaction [J.-Y. Girard. Geometry of interaction 1: Interpretation of system F. In R. Ferro, et al. editors Logic Colloquium '88, pages 221–260. North-Holland, 1989] in analogy with Lamping's optimal reduction [J. Lamping. An algorithm for optimal lambda calculus reduction. In Proc. of 17th Annual ACM Symposium on Principles of Programming Languages. ACM, San Francisco, California, pages 16–30, 1990]. Moreover, the proposed solution preserves scalability of the parallelism arising from local and asynchronous reduction as studied in [M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005].     

An Applicative Control-Flow Graph Based on Huet's Zipper

We are using ML to build a compiler that does low-level optimization. To support optimizations in classic imperative style, we built a control-flow graph using mutable pointers and other mutable state in the nodes. This decision proved unfortunate: the mutable flow graph was big and complex, and it led to many bugs. We have replaced it by a smaller, simpler, applicative flow graph based on Huet's [Huet, Gérard, 1997. The Zipper. Journal of Functional Programming, 7(5):549–554. Functional Pearl] zipper. The new flow graph is a success; this paper presents its design and shows how it leads to a gratifyingly simple implementation of the dataflow framework developed by [Lerner, Sorin, David Grove, and Craig Chambers. 2002. Composing dataflow analyses and transformations. Conference Record of the 29th Annual ACM Symposium on Principles of Programming Languages, in SIGPLAN Notices, 31(1):270–282].     

Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.A preliminary version of this paper appears as: Reducing Nondeterminism while Specializing Logic Programs. Proceedings of the 24th Annual ACM Symposium on Principles of Programming Languages, Paris, France, January 15–17, 1997, ACM Press, 1997, pp. 414–427.     

Improved multi-processor scheduling for?flow time and?energy

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409–420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647–659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.     

Dynamic Partitioning in Linear Relation Analysis: Application to the Verification of Reactive Systems

We apply linear relation analysis (P. Cousot and N. Halbwachs, in 5th ACM Symposium on Principles of Programming Languages, POPL'78, Tucson (Arizona), January 1978; N. Halbwachs, Y.E. Proy, and P. Roumanoff, Formal Methods in System Design, Vol. 11, No. 2, pp. 157–185, 1997) to the verification of declarative synchronous programs (N. Halbwachs, Science of Computer Programming, Special Issue on SAS'94, Vol. 31, No. 1, 1998). In this approach, state partitioning plays an important role: on one hand the precision of the results highly depends on the fineness of the partitioning; on the other hand, a too much detailed partitioning may result in an exponential explosion of the analysis. In this paper, we propose to dynamically select a suitable partitioning according to the property to be proved. The presented approach is quite general and can be applied to other abstract interpretations.     

VyrdMC: Driving Runtime Refinement Checking with Model Checkers

This paper presents VyrdMC, a runtime verification tool we are building for concurrent software components. The correctness criterion checked by VyrdMC is refinement: Each execution of the implementation must be consistent with an atomic execution of the specification. VyrdMC combines testing, model checking, and Vyrd, the runtime refinement checker we developed earlier. A test harness first drives the component to a non-trivial state which serves as the starting state for a number of simple, very small multi-threaded test cases. An execution-based model checker explores for each test case all distinct thread interleavings while Vyrd monitors executions for refinement violations. This combined approach has the advantage of improving the coverage of runtime refinement checking at modest additional computational cost, since model checkers are only used to explore thread interleavings of a small, fixed test program. The visibility and detailed checking offered by using refinement as the correctness criterion differentiate our approach from simply being a restricted application of model checking. An important side benefit is the reduction in program instrumentation made possible if VyrdMC is built using a model checker with its own virtual machine, such as Java PathFinder [Guillaume Brat, Klaus Havelund, Seung-Joon Park, and Willem Visser. Model Checking Programs. In IEEE International Conference on Automated Software Engineering (ASE), September 2000]. We are investigating the use of two different model checkers for building VyrdMC: Java PathFinder, an explicit-state model checker and Verisoft, a “stateless” model checker [P. Godefroid. Model Checking for Programming Languages using VeriSoft. In Proceedings of the 24th ACM Symposium on Principles of Programming Languages, pages 174–186, Paris, January 1997].     

Functional un|unparsing

Danvy??s functional unparsing problem (Danvy in J. Funct. Program. 8(6), 621?C625, 1998) is to implement a type-safe ??printf?? function, which converts a sequence of heterogeneous arguments to a string according to a given format. The dual problem is to implement a type-safe ??scanf?? function, which extracts a sequence of heterogeneous arguments from a string by interpreting (Friedman and Wand in LFP, pp. 348?C355, 1984 and in Essentials of Programming Languages, MIT Press, 2008) the same format as an equally heterogeneous sequence of patterns that binds zero or more variables. We derive multiple solutions to both problems (Wand in J. ACM 27(1), 164?C180, 1980) from their formal specifications (Wand in Theor. Comput. Sci. 20(1), 3?C32, 1982). On one hand, our solutions show how the Hindley-Milner type system, unextended, permits accessing heterogeneous sequences with the static assurance of type safety. On the other hand, our solutions demonstrate the use of control operators (Felleisen et al. in Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pp. 52?C62, ACM Press, New York, 1988; Wand in POPL 85: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, vol. 16, ACM Press, New York, 1985; Meyer and Wand in Logics of Programs, Lecture Notes in Computer Science, vol. 193, pp. 219?C224, Springer, Berlin, 1985) to communicate with formats as coroutines (Wand in Proceedings of the 1980 ACM Conference on Lisp and Functional Programming, vol. 12, pp. 285?C299, ACM Press, New York, 1980 and Haynes et al. in LFP, pp. 293?C298, 1984).     

A linear time algorithm for monadic querying of indefinite data over linearly ordered domains

This paper demonstrates the generation of a linear-time query-answering algorithm based on the constructive proof of Higman’s lemma by Murthy and Russell [Proceedings of the 5th IEEE Symposium on Logic in Computer Science, 1990, p. 257–267]. The target problem is linear-time evaluation of a fixed disjunctive monadic query on an indefinite database over linearly ordered domains, first posed by van der Meyden [Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1992, p. 331–345]. Van der Meyden showed the existence of a linear-time algorithm, but an explicit construction has, until now, not been reported.     

The complexity of reachability in distributed communicating processes

Summary A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models of communicating processes. We obtain these models by making simplifying assumptions about the behavior of message queues and program control, with the hope that reachability may become easier to decide. Depending on the assumptions made, we show that reachability is undecidable, requires nearly exponential space infinitely often, or is NP-complete. In obtaining these results, we demonstrate a very close relationship between the decidable models and Petri nets and Habermann's path expressions, respectively.A preliminary version of this paper appeared in the proceedings of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp. 257–268, June 1979Supported by National Science Foundation Grant NSF MCS 82-00269 and the Office of Naval Research Contract N00014-80-C-0647Supported by National Science Foundation Grants NSF DCR-8505873 and CCR-8704309ACM = The Association for Computing Machinery, Inc. IEEE = The Institute of Electrical and Electronics Engineers, Inc.     

Data flow analysis of distributed communicating processes

Data flow analysis is a technique essential to the compile-time optimization of computer programs, wherein facts relevant to program optimizations are discovered by the global propagation of facts obvious locally. This paper extends several known techniques for data flow analysis of sequential programs to the static analysis of distributed communicating processes. In particular, we present iterative algorithms for detecting unreachable program statements, and for determining the values of program expressions. The latter information can be used to place bounds on the size of variables and messages. Our main innovation is theevent spanning graph, which serves as a heuristic for ordering the nodes through which data flow information is propagated. We consider bothstatic communication, where all channel arguments are constants, and the more difficultdynamic communication, where channel arguments may be variables and channels may be passed as messages.A preliminary version of this paper appeared in the proceedings of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp. 257–268, June 1979.Supported by National Science Foundation Grant NSF MCS82-00269 and the Office of Naval Research Contract N00014-80-C-0647.Supported by National Science Foundation Grants NSF DCR-8505873 and NSF CCR-8704309.     

Syntactic Type Soundness Results for the Region Calculus

The region calculus of Tofte and Talpin is a polymorphically typed lambda calculus with annotations that make memory allocation and deallocation explicit. It is intended as an intermediate language for implementing Hindley-Milner typed functional languages such as ML without traditional trace-based garbage collection. Static region and effect inference can be used to annotate a statically typed ML program with memory management primitives. Soundness of the calculus with respect to the region and effect system is crucial to guarantee safe deallocation of regions, i.e., deallocation should only take place for objects which are provably dead. The original soundness proof by Tofte and Talpin requires a complex co-inductive safety relation. In this paper, we present two small-step operational semantics for the region calculus and prove their type soundness with respect to the region and effect system. Following the standard syntactic approach of Wright, Felleisen, and Harper, we obtain simple inductive proofs. The first semantics is store-less. It is simple and elegant and gives rise to perspicuous proofs. The second semantics provides a store-based model for the region calculus. Albeit slightly more complicated, its additional expressiveness allows us to model operations on references with destructive update. A pure fragment of both small-step semantics is then proven equivalent to the original big-step operational approach of Tofte and Talpin. This leads to an alternative soundness proof for their evaluation-style formulation.     

A fully abstract trace model for dataflow and asynchronous networks

Summary A dataflow network consists of nodes that communicate over perfect unbounded FIFO channels. For dataflow networks containing only deterministic nodes, a simple and elegant semantic model has been presented by Kahn. However, for nondeterministic networks, the straight-forward generalization of Kahn's model is not compositional. We present a compositional model for nondeterministic networks that is fully abstract i.e., it has added the least amount of extra information to Kahn's model that is necessary for attaining compositionality. The model is based on traces. We also generalize our result, showing that the model is fully abstract also for classes of networks where nodes communicate over other types of asynchronous channels. Examples of such classes are networks with unordered channels, and networks with lossy channels. Bengt Jonsson (B.A. Stockholm University 1979, M.Sc. Stanford University 1985, Ph.D. Uppsala University, Sweden 1987) is a professor at the Department of Computer Systems at Uppsala University. From 1988 till 1992 he was employed as a researcher at the Swedish Institute of Computer Science in Kista, Stockholm. His research interests concern semantics, specification, analysis, and formal development, of distributed systems, communication protocols, and real-time systems.This research report is a revised and extended version of a paper that has appeared under the title A fully abstract trace model for dataflow networks in the Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages, Austin, Texas, January 1989. This work was supported in part by the Swedish Board for Technical Development (STU) under contract no. 86-4250, and also under contract No. 89-01220P as part of Esprit BRA project SPEC     

Handling distributed authorization with delegation through answer set programming

Distributed authorization is an essential issue in computer security. Recent research shows that trust management is a promising approach for the authorization in distributed environments. There are two key issues for a trust management system: how to design an expressive high-level policy language and how to solve the compliance-checking problem (Blaze et al. in Proceedings of the Symposium on Security and Privacy, pp. 164–173, 1996; Proceedings of 2nd International Conference on Financial Cryptography (FC’98). LNCS, vol.1465, pp. 254–274, 1998), where ordinary logic programming has been used to formalize various distributed authorization policies (Li et al. in Proceedings of the 2002 IEEE Symposium on Security and Privacy, pp. 114–130, 2002; ACM Trans. Inf. Syst. Secur. (TISSEC) 6(1):128–171, 2003). In this paper, we employ Answer Set Programming to deal with many complex issues associated with the distributed authorization along the trust management approach. In particular, we propose a formal authorization language providing its semantics through Answer Set Programming. Using language , we cannot only express nonmonotonic delegation policies which have not been considered in previous approaches, but also represent the delegation with depth, separation of duty, and positive and negative authorizations. We also investigate basic computational properties related to our approach. Through two case studies. we further illustrate the application of our approach in distributed environments.     

Tags for Multi-Protocol Authentication

Formal methods have been proved successful in analyzing different kinds of security protocols. They typically formalize and study the security guarantees provided by cryptographic protocols, when executed by a (possibly unbounded) number of different participants. A key problem in applying formal methods to cryptographic protocols, is the study of multi-protocol systems, where different protocols are concurrently executed. This scenario is particularly interesting in a global computing setting, where several different security services coexist and are possibly combined together. In this paper, we discuss how the tagging mechanism presented in [M. Bugliesi, R. Focardi, and M. Maffei. Compositional analysis of authentication protocols. In Proceedings of European Symposium on Programming (ESOP 2004), volume 2986 of Lecture Notes in Computer Science, pages 140–154. Springer-Verlag, 2004, M. Bugliesi, R.Focardi, and M.Maffei. A theory of types and effects for authentication. In ACM Proceedings of Formal Methods for Security Engineering: from Theory to Practice (FMSE 2004), pages 1–12. ACM Press, October 2004] addresses this issue.     

Overcoming Heterogeneity and Autonomy in Multidatabase Systems

A multidatabase system (MDBS) is a software system for integration of preexisting and independent local database management systems (DBMSs). The transaction management problem in MDBSs consists of designing appropriate software, on top of local DBMSs, such that users can execute transactions that span multiple local DBMSs without jeopardizing database consistency. The difficulty in transaction management in MDBSs arises due to the heterogeneity of the transaction management algorithms used by the local DBMSs, and the desire to preserve their local autonomy. In this paper, we develop a framework for designing fault-tolerant transaction management algorithms for MDBS environments that effectively overcomes the heterogeneity- and autonomy-induced problems. The developed framework builds on our previous work. It uses the approach described in S. Mehrotra et al. (1992, in “Proceedings of ACM–SIGMOD 1992 International Conference on Management of Data, San Diego, CA”) to overcome the problems in ensuring serializability that arise due to heterogeneity of the local concurrency control protocols. Furthermore, it uses a redo approach to recovery for ensuring transaction atomicity (Y. Breitbart et al., 1990, in “Proceedings of ACM–SIGMOD 1990 International Conference on Management of Data, Atlantic City, NJ;” Mehrotra et al., 1992, in “Proceedings of the Eleventh ACM SIGACT–SIGMOD–SIGART Symposium on Principles of Database Systems, San Diego, CA;” and A. Wolski and J. Veijalainen, 1990, in “Proceedings of the International Conference on Databases, Parallel Architectures and Their Applications”, pp. 321–330), that strives to ensure atomicity of transactions without the usage of the 2PC protocol. We reduce the task of ensuring serializability in MDBSs in the presence of failures to solving three independent subproblems, solutions to which together constitute a complete strategy for failure-resilient transaction management in MDBS environments. We develop mechanisms with which each of the three subproblems can be solved without requiring any changes be made to the preexisting software of the local DBMSs and without compromising their autonomy.     

Modeling of storage properties of higher-level languages

The role of storage in the characterization of higher-level programming languages is discussed. Assignment, in particular, has significantly different meaning in different languages, which can hardly be understood without reference to an underlying model of storage. A general storage model is sketched which can be specialized to a model of ALGOL 68 or of PL/I storage. The same model is used to discuss language features allowing highly flexible data structures.Revised version of a paper presented at the ACM Symposium on Data Structures in Programming Languages, University of Florida, Gainesville, February 25–27, 1971.     

The complexity of reachability in distributed communicating processes

Summary A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models of communicating processes. We obtain these models by making simplifying assumptions about the behavior of message queues and program control, with the hope that reachability may become easier to decide. Depending on the assumptions made, we show that reachability is undecidable, requires nearly exponential space infinitely often, or is NP-complete. In obtaining these results, we demonstrate a very close relationship between the decidable models and Petri nets and Habermann’s path expressions, respectively. A preliminary version of this paper appeared in the proceedings of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp. 257–268, June 1979. Supported by National Science Foundation Grant NSF MCS 82-00269 and the Office of Naval Research Contract N00014-80-C-0647. Supported by National Science Foundation Grants NSF DCR-8505873 and CCR-8704309.