面向对象程序设计体裁嵌入FFP-AST系统

FFP语言是这样的一种纯粹的泛函程序设计语言,它奠基于严格的数学理论基础之上,是归约语言L₄的一个子类^[2,3]。本文将面向对象编程(OOP)体裁相当简洁地嵌入到FFP-AST系统中。这样,一方面,揭示了面向对象编程体裁(OOPP)与泛函编程体裁(FPP)之间的近亲关系;另一方面,为OOPP奠定了 FFP-AST语义描述。本文实质上也提供了一种“加于FFP语言之上的兼备FPP和OOPP的编程语言”。贯穿文中的方法论归结为:紧密联系和使用自动机这一概念。     

Scalability of hybrid programming for a CFD code on the Earth Simulator

The Earth Simulator (ES) is an SMP cluster system. There are two types of parallel programming models available on the ES. One is a flat programming model, in which a parallel program is implemented by MPI interfaces only, both within an SMP node and among nodes. The other is a hybrid programming model, in which a parallel program is written by using thread programming within an SMP node and MPI programming among nodes simultaneously. It is generally known that it is difficult to obtain the same high level of performance using the hybrid programming model as can be achieved with the flat programming model.

In this paper, we have evaluated scalability of the code for direct numerical simulation of the Navier–Stokes equations on the ES. The hybrid programming model achieves the sustained performance of 346.9 Gflop/s, while the flat programming model achieves 296.4 Gflop/s with 16 PNs of the ES for a DNS problem size of 256³. For small scale problems, however, the hybrid programming model is not as efficient because of microtasking overhead. It is shown that there is an advantage for the hybrid programming model on the ES for the larger size problems.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

The multi-weighted Steiner tree problem: A reformulation by intersection

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges.     

A temporal programming model with atomic blocks based on projection temporal logic

Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model (αPTL) which extends the projection temporal logic (PTL) to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.     

Plans, goals and selection rules in the comprehension of computer programs

The notion of the programming plan has been proposed as a mechanism through which one can explain the nature of expertise in programming. Soloway and Ehrlich (1984) suggest that such expertise is characterized by the existence and use of programming plans. However, studies in other complex problem-solving domains, notably text editing, suggest that expertise is characterized not only by the possession of plan-related structures but also by the development of appropriate selection rules which govern the implementation of plans in appropriate situations (Card et al. 1980, Kay and Black 1984, 1986). This paper presents an experimental study which examines the role of programming plans in the context of skill development in programming. The results of this study suggest that plan-based structures cannot be used in isolation to explain novice/expert differences. Indeed, such structures appear to prevail at intermediate levels of skill. The major characteristic of expertise in programming would appear to be strongly related to the development of appropriate selection rules and to so-called program discourse rules. This in turn suggests that current views on the role of plan-based structures in expert programming performance are too limited in their conception to provide an adequate basis for a thorough analysis of the problem-solving activity in the programming domain.     

2APL: a practical agent programming language

This article presents a BDI-based agent-oriented programming language, called 2APL (A Practical Agent Programming Language). This programming language facilitates the implementation of multi-agent systems consisting of individual agents that may share and access external environments. It realizes an effective integration of declarative and imperative style programming by introducing and integrating declarative beliefs and goals with events and plans. It also provides practical programming constructs to allow the generation, repair, and (different modes of) execution of plans based on beliefs, goals, and events. The formal syntax and semantics of the programming language are given and its relation with existing BDI-based agent-oriented programming languages is discussed.     

Composition is almost (but not quite) as good as s-1-1

We establish a polynomial upper bound on the time complexity of an s-1-1 function in programming system with a linear-time composition function. This improves the doubly exponential upper bound of Machtey and Young (1978), the only previously known upper bound, and invalidates the belief expressed twice in the literature (Machtey 1978; Machtey and Young 1978) that it could not be significantly improved. We then show our upper bound to be tight, by exhibiting a family of acceptable programming systems for which it is optimal. We deduce several bounds on the time complexity of composition functions, s-1-1 functions, and various other semantic transformations of programs, in programming systems with a linear- or polynomial-time composition function. In particular, we show the existence of an acceptable programming system with a quadratic-time composition function, but no subexponential time s-1-1 function. In one interpretation from Marcoux (1991), this last result states that the complexity of a composition function for an effective programming system does not give an upper bound on the complexity of the “task of programming” in that programming system. By contrast, results by Royer (1987) indicate that this task is essentially no more complex than computing an s-1-1 function.     

Database query languages and functional logic programming

Functional logic programming is a paradigm which integrates functional and logic programming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a data definition language and, finally, a query language against the data defined according to the data model. To use functional logic programming as a database programming language, (1) we will propose a data model involving the main features adopted from functional logic programming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.     

Explicit/multi-parametric model predictive control (MPC) of linear discrete-time systems by dynamic and multi-parametric programming

This work presents a new algorithm for solving the explicit/multi-parametric model predictive control (or mp-MPC) problem for linear, time-invariant discrete-time systems, based on dynamic programming and multi-parametric programming techniques. The algorithm features two key steps: (i) a dynamic programming step, in which the mp-MPC problem is decomposed into a set of smaller subproblems in which only the current control, state variables, and constraints are considered, and (ii) a multi-parametric programming step, in which each subproblem is solved as a convex multi-parametric programming problem, to derive the control variables as an explicit function of the states. The key feature of the proposed method is that it overcomes potential limitations of previous methods for solving multi-parametric programming problems with dynamic programming, such as the need for global optimization for each subproblem of the dynamic programming step.     

On a decision procedure for quantified linear programs

Quantified linear programming is the problem of checking whether a polyhedron specified by a linear system of inequalities is non-empty, with respect to a specified quantifier string. Quantified linear programming subsumes traditional linear programming, since in traditional linear programming, all the program variables are existentially quantified (implicitly), whereas, in quantified linear programming, a program variable may be existentially quantified or universally quantified over a continuous range. In this paper, the term linear programming is used to describe the problem of checking whether a system of linear inequalities has a feasible solution. On account of the alternation of quantifiers in the specification of a quantified linear program (QLP), this problem is non-trivial. QLPs represent a class of declarative constraint logic programs (CLPs) that are extremely rich in their expressive power. The complexity of quantified linear programming for arbitrary constraint matrices is unknown. In this paper, we show that polynomial time decision procedures exist for the case in which the constraint matrix satisfies certain structural properties. We also provide a taxonomy of quantified linear programs, based on the structure of the quantifier string and discuss the computational complexities of the constituent classes. This research has been supported in part by the Air Force Office of Scientific Research under contract FA9550-06-1-0050.     

EasiSMP: A Resource-Oriented Programming Framework Supporting Runtime Propagation of RESTful Resources

In order to simplify programming for building sensor networks, macro-programming methods have been pro- posed in prior work. Most of them are designed for the dedicated networks and specific scenarios where devices are mostly homogeneous. Nevertheless the methods rarely consider those shared networks which are composed of heterogeneous de- vices, e.g., sensors, actuators, mobile devices, and share resources among themselves. In this paper, we present EasiSMP, a resource-oriented programming framework for these shared networks and generic application scenarios. In this framework, the devices and their functionalities are abstracted into RESTful virtual resources （VRs） each of which is labelled by a uni- form resource identifier （URI）. The post-deployment VR can be globally accessed and reused to propagate new resource（s） at runtime. To support the resource propagation, programming primitives are proposed and a virtual resource engine （VRE） is studied. To perform evaluation, EasiSMP is deployed into a relic monitoring network. Experimental results show that programming using Ea-siSMP is concise, and the average deployment overhead is decreased by up to 27% compared with the node-level programming.     

Layout transformation support for the disk resident arrays framework

The Global Arrays (GA) toolkit provides a shared-memory programming model in which data locality is explicitly managed by the programmer. It inter-operates with MPI and supports a variety of language bindings. The Disk Resident Arrays (DRA) model extends the GA programming model to secondary storage. GA and DRA together provide a convenient programming model that encourages locality-aware programming by the user, while presenting a high-level abstraction. High performance depends on the appropriate distribution of the data in the disk-resident arrays. In this paper, we discuss the addition of layout transformation support to DRA. The implementation of an efficient parallel layout transformation algorithm is done on top of existing GA/DRA functions; thus GA/DRA is itself used in implementing the enhanced DRA functionality. Experimental performance data is provided that demonstrates the effectiveness of the new layout transformation functionality. This work was supported in part through funding from the U.S. Department of Energy and the National Science Foundation (award 0121676).     

Dependent-chance programming with fuzzy decisions

Dependent-chance programming (DCP) is a new type of stochastic programming and has been extended to the area of fuzzy programming. This paper provides a spectrum of DCP and dependent-chance multiobjective programming (DCMOP) as well as dependent-chance goal programming (DCGP) models with fuzzy rather than crisp decisions. The terms of uncertain environment, event, chance function, and induced constraints are discussed in the case of fuzzy decisions. A technique of fuzzy simulation is also designed for computing chance functions. Finally, we present a fuzzy simulation-based genetic algorithm for solving these models and illustrate its effectiveness by some numerical examples     

Mathcad软件用于固定床反应器拟均相二维模型的数值解

为了提高化学反应工程课程的教学质量，采用了Mathcad软件编程求解固定床反应器拟均相二维模型的数值解。除了它的易使用和功能强大的工具盒的特点外，更重要的是它的编程语言的数学表达形式很接近传统的数学书写风格。使较为复杂的工业反应过程的计算问题能得以在课堂上进行生动有效的讲解，实时生成可改变操作条件的二维或三维的组成(转化率)、温度或反应速率的分布图，取得了令人满意的教学效果。     

Programming assistance tools to support the learning of IT programming in South African secondary schools

Novice programmers struggle to understand introductory programming concepts and this difficulty, associated with learning to program, contributes mainly to the lack of interest in the field of Computer Science at tertiary level. Programming assistance tools have been used to assist novice programmers extensively at education institutions. A programming assistance tool (PAT) is a software program that can be used by novice programmers to learn how to program and/or improve their understanding of programming concepts.This research proposes that novice programmers, specifically Information Technology (IT) scholars in South African secondary schools, could be supported by PATs. The main objective of this research was to determine whether the use of a PAT impacted IT scholars' understanding of programming concepts and their motivation towards programming in general. Criteria for the selection of PATs were derived from the programming difficulties identified in literature and from surveys to IT teachers and scholars. The selection criteria were grouped into programming knowledge and programming skills categories. Existing PATs were evaluated using the selection criteria and three PATs, namely, RoboMind, Scratch and B#, were selected for evaluation in this research study. A convenience sample of schools participated in the study. The three PATs provided different approaches while being able to support the Delphi programming language used in schools that participated in the study.The findings of this research indicated that, although scholars perceived the PATs to be useful in the explanation of certain of the programming concepts, there was no conclusive evidence that IT scholars who used a PAT had a significantly better understanding of programming concepts and motivation towards programming than scholars who did not use a PAT. Participant feedback was used to identify the strengths and shortcomings of the three PATs and to provide recommendations for the development of future PATs specifically designed to support IT scholars.     

Some applications of mathematical programming techniques in optimal power dispatch

Some models for the economic dispatch of electric power are introduced and treated by mathematical programming techniques. In particular, our presentation includes (i) a short-term model for the optimal dispatch of thermal units, which is solved by a specific path following method, (ii) a daily model for a generation system consisting of thermal units, pumped storage plants and an energy contract, which can be solved by standard convex quadratic programming algorithms, and (iii) two stochastic programming models for the optimal daily dispatch, which depend on the (unknown) probability distribution of the electric power demand. One of the latter models can be solved efficiently by combining nonparametric estimation procedures and convex programming methods.     

构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。     

含间隙机械系统的混杂模型预测控制器

研究含间隙机械系统的混杂模型预测控制问题.首先,将含间隙机械系统的运行模式分为"间隙模式"和"接触模式".其次,建立了含间隙机械系统的混杂分段仿射 (PWA)模型.然后,利用模型预测控制 (MPC)的方法对约束PWA系统的最优控制进行求解,通过动态规划与多参数二次规划方法,得到了MPC的离线解.最后,通过将分段二次 (PWQ)Lyapunov函数的求解转换成半正定规划,找到了确保闭环控制稳定性的PWQ Lyaplanov函数.跟踪参考速度的实验结果表明,混杂模型预测控制器对含间隙机械系统的跟踪控制具有较好的效果,能够满足小采样时间系统的实时控制要求.     

有向几何编程在数控系统中的实现

在数控加工中,G代码描述的零件加工过程不够直观.为了解决这个问题,提出采用有向几何编程语言GPL(geometric programming language)来辅助G代码进行编程,使得编程变得简单直观.设计了GPL语法规则,并依据GPL语法规则设计实现了GPL解释器,提出一种计算检测码的方法对GPL语法进行检查,创建关键字的属性值表以支持检测码的计算.该方法使GPL语法规则容易扩展,便于解释器的二次开发.采用位运算方法进行参数的冲突检测,增强语法分析器的可扩展性,提高分析速度和效率.