A call-by-name lambda-calculus machine

We present a particularly simple lazy lambda-calculus machine, which was introduced twenty-five years ago. It has been, since, used and implemented by several authors, but remained unpublished. We also build an extension, with a control instruction and continuations. This machine was conceived in order to execute programs obtained from mathematical proofs, by means of the Curry-Howard (also known as “proof-program”) correspondence. The control instruction corresponds to the axiom of excluded middle.     

On the call-by-value CPS transform and its semantics

We investigate continuations in the context of idealized call-by-value programming languages. On the semantic side, we analyze the categorical structures that arise from continuation models of call-by-value languages. On the syntactic side, we study the call-by-value continuation-passing transformation as a translation between equational theories. Among the novelties are an unusually simple axiomatization of control operators and a strengthened completeness result with a proof based on a delaying transform.     

Monad的一种自动生成技术

Monad程序的核心是一组Monad定义.Monad定义分为MAP型和BIND型.如果在Monad库中已有所需要的Monad定义型,则可以直接使用,而不需要重新构造;否则,需要重新构造.但如果在Monad程序设计环境中增加从一类Monad构造另一类Monad的自动生成器,那么既方便了用户也扩充了1倍原有的Monad库.鉴于这种思想,用支持Monad程序设计的高阶函数语言Haskell实现了一个Monad的自动生成系统.另外,用户构造Monad不仅要花费较多的时间,而且写出的Monad多态函数往往不满足Monad所需满足的几条公理,因此,从这方面也可以看出,从一种类型的Monad自动产生另一种类型的Monad的重要意义.     

Two Algorithms for Decomposing a Polyhedron into Convex Parts

Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring-shaped faces and cavities. The time requirement in both cases is O ( DN log N ), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D + 1 convex pieces which is the minimal number of the convex components.     

Strong normalization from an unusual point of view

A new complete characterization of β-strong normalization is given, both in the classical and in the lazy λ-calculus, through the notion of potential valuability inside two suitable parametric calculi.     

A prismoid framework for languages with resources

Inspired by the Multiplicative Exponential fragment of Linear Logic, we define a framework called the prismoid of resources where each vertex is a language which refines the λ-calculus by using a different choice to make explicit or implicit (meta-level) the definition of the contraction, weakening, and substitution operations. For all the calculi in the prismoid we show simulation of β-reduction, confluence, preservation of β-strong normalisation and strong normalisation for typed terms. Full composition also holds for all the calculi of the prismoid handling explicit substitutions. The whole development of the prismoid is done by making the set of resources a parameter of the formalism, so that all the properties for each vertex are obtained as a particular case of the general abstract proofs.     

一种基于组合Monad的纯函数式通道系统操作

Monad作为构造纯函数式语言的工具,能构造出诸如错误处理、状态、IO等非纯函数式语言的特征。该文通过组合状态转换Monad和异常处理Monad来定义纯函数式语言通道系统操作,给出了通道系统操作的操作语义。     

基于Monad的纯函数式语言通道系统设计

本文通过状态转换器来定义I／O的文件系统,并用非确定性Monad描述了操作系统的进程同,从而给出了通道系统的语义。     

The impact of replenishment parameters and information sharing on the bullwhip effect: A computational study

Demand variability amplification across the supply chain, known as the bullwhip effect, results in serious inefficiencies across the chain. Managers are expected to minimize this phenomenon in their chain in order to reduce costs and increase customer satisfaction by making critical decisions on replenishment policy. We study how specific replenishment parameters affect order variability amplification, product fill rates and inventory levels across the chain. Furthermore, we study how demand information sharing can help towards reducing order oscillations and inventory levels in upper nodes of a supply chain. A two-stage supply chain consisting of a warehouse and stores that face customer demand is modeled. Real demand data are used as the underlying customer demand during the experiments.     

Infinite trees and completely iterative theories: a coalgebraic view

Infinite trees form a free completely iterative theory over any given signature—this fact, proved by Elgot, Bloom and Tindell, turns out to be a special case of a much more general categorical result exhibited in the present paper. We prove that whenever an endofunctor H of a category has final coalgebras for all functors H( _ )+X, then those coalgebras, TX, form a monad. This monad is completely iterative, i.e., every guarded system of recursive equations has a unique solution. And it is a free completely iterative monad on H. The special case of polynomial endofunctors of the category is the above mentioned theory, or monad, of infinite trees.

This procedure can be generalized to monoidal categories satisfying a mild side condition: if, for an object H, the endofunctor H_+I has a final coalgebra, T, then T is a monoid. This specializes to the above case for the monoidal category of all endofunctors.     

Nominal Techniques in Isabelle/HOL

This paper describes a formalisation of the lambda-calculus in a HOL-based theorem prover using nominal techniques. Central to the formalisation is an inductive set that is bijective with the alpha-equated lambda-terms. Unlike de-Bruijn indices, however, this inductive set includes names and reasoning about it is very similar to informal reasoning with “pencil and paper”. To show this we provide a structural induction principle that requires to prove the lambda-case for fresh binders only. Furthermore, we adapt work by Pitts providing a recursion combinator for the inductive set. The main technical novelty of this work is that it is compatible with the axiom of choice (unlike earlier nominal logic work by Pitts et al); thus we were able to implement all results in Isabelle/HOL and use them to formalise the standard proofs for Church-Rosser, strong-normalisation of beta-reduction, the correctness of the type-inference algorithm W, typical proofs from SOS and much more. This paper is a revised and much extended version of Urban and Berghofer [32], and Urban and Tasson [36].     

一种基于组合Monad的纯函数式Lazy I/O操作

Monad作为构造纯函数式语言的工具,能构造出诸如错误处理、状态、I/O等非纯函数式语言的特征.本文通过组合状态转换Monad和异常处理Monad来定义纯函数式LazyI/O操作,既保持了纯函数式语言的特征,又融入了非纯函数式语言的特征.     

A calculus of coroutines

We describe a simple but expressive calculus of sequential processes, represented as coroutines. We show that this calculus can be used to express a variety of programming language features including procedure calls, labelled jumps, integer references and stacks. We describe the operational properties of the calculus using reduction rules and equational axioms.

We describe a notion of categorical model for our calculus, and give a simple example of such a model based on a category of games and strategies. We prove full abstraction results showing that equivalence in the categorical model corresponds to observational equivalence in the calculus, and also to equivalence of evaluation trees, which are infinitary normal forms for the calculus.

We show that our categorical model can be used to interpret the untyped λ-calculus and use this fact to extract a sound translation of the latter into our calculus of coroutines.     

Makespan minimization flowshop with position dependent job processing times—computational complexity and solution algorithms

This paper considers flowshop scheduling problems where job processing times are described by position dependent functions, i.e., dependent on the number of processed jobs, that model learning or aging effects. We prove that the two-machine flowshop problem to minimize the maximum completion time (makespan) is NP-hard if job processing times are described by non-decreasing position dependent functions (aging effect) on at least one machine and strongly NP-hard if job processing times are varying on both machines. Furthermore, we construct fast NEH, tabu search with a fast neighborhood search and simulated annealing algorithms that solve the problem with processing times described by arbitrary position dependent functions that model both learning and aging effects. The efficiency of the proposed methods is numerically analyzed.     

一种基于Z规范的纯函数式程序设计方法

状态、输入和输出是Z规范的基础,引入Monad的纯函数式语言特别适合用来实现用Z规范说明的系统.通过将状态、输入和输出封装在一个Monad内,提出一种基于Z规范的纯函数式程序设计方法.     

Categorical models for local names

This paper describes the construction of categorical models for thenu-calculus, a language that combines higher-order functions with dynamically creatednames. Names are created with local scope, they can be compared with each other and passed around through function application, but that is all.The intent behind this language is to examine one aspect of the imperative character of Standard ML: the use of local state by dynamic creation of references. The nu-calculus is equivalent to a certain fragment of ML, omitting side effects, exceptions, datatypes and recursion. Even without all these features, the interaction of name creation with higher-order functions can be complex and subtle; it is particularly difficult to characterise theobservable behaviour of expressions.Categorical monads, in the style of Moggi, are used to build denotational models for the nu-calculus. An intermediate stage is the use of a computational metalanguage, which distinguishes in the type system between values and computations.The general requirements for a categorical model are presented, and two specific examples described in detail. These provide a sound denotational semantics for the nu-calculus, and can be used to reason about observable equivalence in the language. In particular a model using logical relations is fully abstract for first-order expressions.Supported by UK SERC studentship 91307943 and CEC SCIENCE project PL910296     

Probabilistic coherence spaces as a model of higher-order probabilistic computation

We study a probabilistic version of coherence spaces and show that these objects provide a model of linear logic. We build a model of the pure lambda-calculus in this setting and show how to interpret a probabilistic version of the functional language PCF. We give a probabilistic interpretation of the semantics of probabilistic PCF closed terms of ground type. Last we suggest a generalization of this approach, using Banach spaces.     

Decomposing and Solving Timetabling Constraint Networks

The binary version of the school timetabling (STT) problem is a real‐world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real‐world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real‐world high school.
To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.     

State-transition machines, revisited

History and context are given regarding the development of the WNF-machine, the first example of a Krivine machine. Supported by NSF ITR-0085949 and ITR-0086154.