Unchecked Exceptions Can Be Strictly More Powerful Than Call/CC

We demonstrate that in the context of statically-typed purely-functional lambda calculi without recursion, unchecked exceptions (e.g., SML exceptions) can be strictly more powerful than call/cc. More precisely, we prove that a natural extension of the simply-typed lambda calculus with unchecked exceptions is strictly more powerful than all known sound extensions of Girard's F (a superset of the simply-typed lambda calculus) with call/cc.This result is established by showing that the first language is Turing complete while the later languages permit only a subset of the recursive functions to be written. We show that our natural extension of the simply-typed lambda calculus with unchecked exceptions is Turing complete by reducing the untyped lambda calculus to it by means of a novel method for simulating recursive types using unchecked-exception–returning functions. The result concerning extensions of F with call/cc stems from previous work of the author and Robert Harper.     

Call-by-Value {lambda}-calculus and LJQ

LJQ is a focused sequent calculus for intuitionistic logic,with a simple restriction on the first premiss of the usualleft introduction rule for implication. In a previous paperwe discussed its history (going back to about 1950, or beyond)and presented its basic theory and some applications; here wediscuss in detail its relation to call-by-value reduction inlambda calculus, establishing a connection between LJQ and theCBV calculus _C of Moggi. In particular, we present an equationalcorrespondence between these two calculi forming a bijectionbetween the two sets of normal terms, and allowing reductionsin each to be simulated by reductions in the other.     

Observer-based multivariable flatness control of a cold rolling mill

The synthesis methodology developed by Kimura (1985) based on the design theory of output regulators essentially due to Wonham (1974) has been applied successfully to the flatness control system for a 6-high cold rolling mill. The system has the following remarkable features.

1. (1) The structure of the controller is simple. This makes it easy to tune the control system.

2. (2) The controller copes well with the detection time delay, and thus high performance is obtained even at a low rolling speed.

3. (3) The flatness error caused by the rolling force variation in mill acceleration and deceleration time would be kept to a minimum by the function to adjust roll bending force using the signal of rolling force.

Impact of personality and intelligence on job satisfaction of assembly line and bench work - an industrial study

A study of the impact of machine-paced (M/P) and self-paced (S/P) work on job satisfaction of 28 female industrial assembly workers was evaluated in which M/P work was confounded with simplified work and the S/P job was confounded with enriched tasks. Results indicated the following:

1. 1. Over three-quarters of workers were more satisfied in S/P jobs, while only less than one-quarter were more satisfied in M/P jobs.

2. 2. The 16PF personality test effectively predicts (0·88 multiple correlation) the satisfaction ratios of M/P to S/P jobs.

Applications of power series in computational geometry

A number of algorithms are presented for obtaining power series expansions of curves and surfaces at a point. Some results on the radius of convergence are given. Two applications of series are given:

1. • for curve tracing algorithms, where a truncated series is used to approximate the curve of intersection of two surfaces

2. • to define nth degree geometric continuity, for arbitrary

An analysis of research topics in software engineering – 2006

This paper is the first in a new annual series whose goal is to answer the following question: what are the active research focuses within the field of software engineering? We considered 7 top journals and 7 top international conferences in software engineering and examined all the 691 papers published in these journals or presented at these conferences in 2006. Consequently, we have a number of findings.

(1) Seventy-three percent of journal papers focus on 20% of subject indexes in software engineering, including Testing and Debugging (D.2.5), Management (D.2.9), and Software/Program Verification (D.2.4).

(2) Eighty-nine percent of conference papers focus on 20% of subject indexes in software engineering, including Software/Program Verification (D.2.4), Testing and Debugging (D.2.5), and Design Tools and Techniques (D.2.2).

(3) Seventy-seven percent of journal/conference papers focus on 20% of subject indexes in software engineering, including Testing and Debugging (D.2.5), Software/Program Verification (D.2.4), and Management (D.2.9).

(4) The average number of references cited by a journal paper is about 33, whereas this number becomes around 24 for a conference paper.

Simply-typed Underdeterminism

An extension of the simply-typed lambda calculus with constructs for expressing a notion called underdeterminism is studied.This allows us to interpret notions of stud and skeleton used in top-down program development.We axionatise a simple notion of program refinement,and give a semantics,for which the calculus is proved sound and complete.     

The <Emphasis Type="Italic">λ</Emphasis>-Calculus and the Unity of Structural Proof Theory

In the context of intuitionistic implicational logic, we achieve a perfect correspondence (technically an isomorphism) between sequent calculus and natural deduction, based on perfect correspondences between left-introduction and elimination, cut and substitution, and cut-elimination and normalisation. This requires an enlarged system of natural deduction that refines von Plato’s calculus. It is a calculus with modus ponens and primitive substitution; it is also a “coercion calculus”, in the sense of Cervesato and Pfenning. Both sequent calculus and natural deduction are presented as typing systems for appropriate extensions of the λ-calculus. The whole difference between the two calculi is reduced to the associativity of applicative terms (sequent calculus = right associative, natural deduction = left associative), and in fact the achieved isomorphism may be described as the mere inversion of that associativity. The novel natural deduction system is a “multiary” calculus, because “applicative terms” may exhibit a list of several arguments. But the combination of “multiarity” and left-associativity seems simply wrong, leading necessarily to non-local reduction rules (reason: normalisation, like cut-elimination, acts at the head of applicative terms, but natural deduction focuses at the tail of such terms). A solution is to extend natural deduction even further to a calculus that unifies sequent calculus and natural deduction, based on the unification of cut and substitution. In the unified calculus, a sequent term behaves like in the sequent calculus, whereas the reduction steps of a natural deduction term are interleaved with explicit steps for bringing heads to focus. A variant of the calculus has the symmetric role of improving sequent calculus in dealing with tail-active permutative conversions.     

Type checking and typability in domain-free lambda calculi

This paper shows (1) the undecidability of the type checking and the typability problems in the domain-free lambda calculus with negation, product, and existential types, (2) the undecidability of the typability problem in the domain-free polymorphic lambda calculus, and (3) the undecidability of the type checking and the typability problems in the domain-free lambda calculus with function and existential types. The first and the third results are proved by the second result and CPS translations that reduce those problems in the domain-free polymorphic lambda calculus to those in the domain-free lambda calculi with existential types. The key idea is the conservativity of the domain-free lambda calculi with existential types over the images of the translations.     

A unifying action calculus

McCarthy's Situation Calculus is arguably the oldest special-purpose knowledge representation formalism, designed to axiomatize knowledge of actions and their effects. Four decades of research in this area have led to a variety of alternative formalisms: While some approaches can be considered instances or extensions of the classical Situation Calculus, like Reiter's successor state axioms or the Fluent Calculus, there are also special planning languages like ADL and approaches based on a linear (rather than branching) time structure like the Event Calculus. The co-existence of many different calculi has two main disadvantages: The formal relations among them is a largely open issue, and a lot of today's research concerns the transfer of specific results from one approach to another. In this paper, we present a unifying action calculus, which encompasses (well-defined classes of) all of the aforementioned formalisms. Our calculus not only facilitates comparisons and translations between specific approaches, it also allows to solve interesting problems for various calculi at once. We exemplify this by providing a general, calculus-independent solution to a problem of practical relevance, which is intimately related to McCarthy's quest for elaboration tolerant formalisms: the modularity of domain axiomatizations.     

A binary modal logic for the intersection types of lambda-calculus

Intersection types discipline allows to define a wide variety of models for the type free lambda-calculus, but the Curry–Howard isomorphism breaks down for this kind of type systems. In this paper we show that the correspondence between types and suitable logical formulas can still be recovered appealing to the fact that there is a strict connection between the semantics for lambda-calculus induced by the intersection types and a Kripke-style semantics for modal and relevant logics. Indeed, we present a modal logic hinted by the analysis of the sub-typing relation for intersection types, and we show that the deduction relation for such a modal system is a conservative extension of the relation of sub-typing. Then, we define a Kripke-style semantics for the formulas of such a system, present suitable sequential calculi, prove a completeness theorem and give a syntactical proof of the cut elimination property. Finally, we define a decision procedure for theorem-hood and we show that it yields the finite model property and cut-redundancy.     

Paraconsistent intelligent systems of computer logics

The paper considers applicative computation systems (ACS) constructed as Gentzen-deductive extensions of Church's -conversion calculi with a bounded cut rule and as Sheinfinkel'-Curry pure combinatory logic.Translated from Kibernetika, No. 1, pp. 9–12, 34, January–February, 1991.     

Parallelising large irregular programs: an experience with Naira

Naira is a compiler for Haskell, written in Glasgow parallel Haskell. It exhibits modest, but irregular, parallelism that is determined by properties of the program being compiled, e.g. the complexity of the types and of the pattern matching. We report four experiments into Naira's parallel behaviour using a set of realistic inputs: namely the 18 Haskell modules of Naira itself. The issues investigated are:

• Does increasing input size improve sequential efficiency and speedup?

• To what extent do high communications latencies reduce average parallelism and speedup?

• Does migrating running threads between processors improve average parallelism and speedup at all latencies?

 

A new framework for declarative programming

We propose a new framework for the syntax and semantics of Weak Hereditarily Harrop logic programming with constraints, based on resolution over τ-categories: finite product categories with canonical structure.

Constraint information is directly built-in to the notion of signature via categorical syntax. Many-sorted equational are a special case of the formalism which combines features of uniform logic programming languages (moduels and hypothetical implication) with those of constraint logic programming. Using the cannoical structure supplied by τ-categories, we define a diagrammatic generalization of formulas, goals, programs and resolution proofs up to equality (rather than just up to isomorphism).

We extend the Kowalski-van Emden fixed point interpretation, a cornerstone of declarative semantics, to an operational, non-ground, categorical semantics based on indexing over sorts and programs.

We also introduce a topos-theoretic declarative semantics and show soundness and completeness of resolution proofs and of a sequent calculus over the categorical signature. We conclude with a discussion of semantic perspectives on uniform logic programming.     

A functional presentation of Pi calculus

From the very beginning process algebra introduced the dichotomy between channels and processes. This dichotomy prevails in all present process calculi. The situation is in contrast to that withlambda calculus which has only one class of entities-the lambda terms. We introduce in this papera process calculus called Lamp in which channels are process names. The language is more uniform than existing process calculi in two aspects-. First it has a unified treatment of channels and processes.There is only one class of syntactical entities-processes. Second it has a unified presentation ofboth first order and higher order process calculi. The language is functional in the sense that lambda calculus is functional. Two bisimulation equivalences, barbed and closed bisimilarities, are proved to coincide.A natural translation from Pi calculus to Lamp is shown to preserve both operational and algebraic semantics. The relationship between lazy lambda calculus and Lamp is discussed.     

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.     

Another approach to formalizing the point and interval calculi

In this paper a formalization of point calculus (Vilain & Kautz) and interval calculus (Allen) is presented. Semantics for this formalization is based on the point and interval temporal structures described by van Benthem. Finally, and attempt to translate these calculi into the instant tense logic and the extended tense logic accordingly is suggested.     

Resolution with Order and Selection for Hybrid Logics

We investigate labeled resolution calculi for hybrid logics with inference rules restricted via selection functions and orders. We start by providing a sound and refutationally complete calculus for the hybrid logic H(@,ˉ,A)\mathcal{H}(@,{\downarrow},\mathsf{A}), even under restrictions by selection functions and orders. Then, by imposing further restrictions in the original calculus, we develop a sound, complete and terminating calculus for the H(@)\mathcal{H}(@) sublanguage. The proof scheme we use to show refutational completeness of these calculi is an adaptation of a standard completeness proof for saturation-based calculi for first-order logic that guarantees completeness even under redundancy elimination. In fact, one of the contributions of this article is to show that the general framework of saturation-based proving for first-order logic with equality can be naturally adapted to saturation-based calculi for other languages, in particular modal and hybrid logics.     

时段演算综述

时段演算是用于嵌入式实时软件系统设计的演算系统。本文概述了该演算系统，其中包括时段演算，扩充时段演算，平均值演算和概率时段演算，它们都是区间时态逻辑的扩展，可用于处理数学分析中函数在连续时间上的一些概念，如：积分，平均值，分段连续性和可微性。该演算应用地对混合系统的实时需求进行刻划和精化，同时也能定义计算系统的实时行为和语义，以及用来计算关于系统需求的满足概率。     

The lambda-context calculus (extended version)

We present the Lambda Context Calculus. This simple lambda-calculus features variables arranged in a hierarchy of strengths such that substitution of a strong variable does not avoid capture with respect to abstraction by a weaker variable. This allows the calculus to express both capture-avoiding and capturing substitution (instantiation). The reduction rules extend the ‘vanilla’ lambda-calculus in a simple and modular way and preserve the look and feel of a standard lambda-calculus with explicit substitutions.Good properties of the lambda-calculus are preserved. The LamCC is confluent, and a natural injection into the LamCC of the untyped lambda-calculus exists and preserves strong normalisation.We discuss the calculus and its design with full proofs. In the presence of the hierarchy of variables, functional binding splits into a functional abstraction λ (lambda) and a name-binder и (new). We investigate how the components of this calculus interact with each other and with the reduction rules, with examples. In two more extended case studies we demonstrate how global state can be expressed, and how contexts and contextual equivalence can be naturally internalised using function application.