A principled approach to programming with nested types in Haskell

Initial algebra semantics is one of the cornerstones of the theory of modern functional programming languages. For each inductive data type, it provides a Church encoding for that type, a build combinator which constructs data of that type, a fold combinator which encapsulates structured recursion over data of that type, and a fold/build rule which optimises modular programs by eliminating from them data constructed using the buildcombinator, and immediately consumed using the foldcombinator, for that type. It has long been thought that initial algebra semantics is not expressive enough to provide a similar foundation for programming with nested types in Haskell. Specifically, the standard folds derived from initial algebra semantics have been considered too weak to capture commonly occurring patterns of recursion over data of nested types in Haskell, and no build combinators or fold/build rules have until now been defined for nested types. This paper shows that standard folds are, in fact, sufficiently expressive for programming with nested types in Haskell. It also defines buildcombinators and fold/build fusion rules for nested types. It thus shows how initial algebra semantics provides a principled, expressive, and elegant foundation for programming with nested types in Haskell.     

The BC-chain method for representing combinators in linear space

Turner’s combinator implementation (1979) of functional programs requires the memory space of size Ω(n ²) in the worst case for translating given lambda expressions of lengthn to combinator graphs. In this paper a new idea named the BC-chain method for transferring actual arguments to variables is presented. We show that the BC-chain method requires onlyO(n) space for the translation. The basic idea is to group together into a single entity a sequence of combinatorsB, B′, C andC′, for a variable, which appear consecutively along a path in the combinator graph. We formulate two reduction algorithms in the new representation. The first algorithm naively simulates the original normal order reduction, while the second algorithm simulates it in constant time per unit operation of the original reduction. Another reduction method is also suggested, and a technique for practical implementation is briefly mentioned.     

Combinator evaluation of functional programs with logical variables

A technique is presented that brings logical variables into the scope of the well-known Turner method for normal order evaluation of functional programs by S, K, I combinator graph reduction. This extension is illustrated bySASL+LV, an extension of Turner's languageSASL in which arbitrary expressions serve as formal parameters, and parameter passage is done by unification. The conceptual and practical advantages of such an extension are discussed, as well as semantic pitfalls that arise from the attendant weakening of referential transparency. Only five new combinators (LV, BV, FN, FB and UNIFY) are introduced. The resulting object code is fully upward compatible in the sense that previously compiledSASL programs remain executable with unchanged semantics. However,read-only variable usage inSASL+LV programs requires amultitasking extension of the customary stack-based evaluation method. Mechanisms are presented for managing this multitasking on both single and multiprocessor systems. Finally, directions are mentioned for applying this technique to implementations involving larger granularity combinators, and fuller semantic treatment of logical variables (e.g. accommodation of failing unifications).Research was supported in part by the Marcus Wallenberg Foundation.Research supported in part by grant CCR-8704778 from the National Science Foundation, and by an unrestricted gift from Telefonaktiebolaget LM Ericsson, Stockholm.     

Statistics on graph reduction of SASL programs

The execution has been studied of four small and four medium-sized SASL programs, when interpreted by a variant of Turner's combinator reducer. Size, structure and composition of the combinator graph have been analysed at frequent intervals during the reduction process. The most interesting results are summarized and discussed. Nodes of the graph live rather short lives and are usually not shared. Cycles are rare, and linear lists are often short. In most aspects the behaviour of the graph is quite ordinary in the sense that a simple model is sufficient to obtain a good approximation.     

Universal Boolean Systems

Boolean interaction systems and hard interaction systems define nets of interacting cells. They are based on the same local interaction principle between two cells as interaction nets but do not allow that the structure of nets may evolve. With boolean nets, it is not possible to create or destroy cells or links between existing cells. They are very similar to hardware circuits but based on an implicit rendez-vous information exchange mechanism.If we want to implement such systems using hardware circuits, it is important to define a set of universal combinators that reduces this task to the implementation of a fixed number of known agents. Here, we show how we can simulate every hard interaction system by a universal boolean interaction system composed of three combinators: a duplicator, a NAND gate and a three-state input/output channel.     

Adapting combinator and SECD machines to display snapshots of functional computations

A functional computation involves substituting for function applications in an expression until that expression is reduced to normal form. The views of computations presented by the sequence- and state-oriented debugging tools of imperative systems are inappropriate for use with functional computations. New debugging tools are needed to aid the development of functional programs, especially in the context of lazy evaluation. After surveying previously reported debugging tools, we discuss a new debugging tool. Its implementation involves changing the reduction rules of the machine. The new reduction rules are applied to an interrupted computation to give a snapshot of that computation in source-level terms. We have implemented tools to produce snapshots for eager SECD and lazy combinator reduction machines. Example snapshots are shown from each. The implementation for an eager SECD machine is relatively straightforward, so we confine discussion of this to a brief sketch. A more detailed account is given of the implementation for a lazy combinator reduction machine, as this offers one solution to well-known problems with debugging functional programs in the context of lazy evaluation and combinator code.     

Lazy debugging of lazy functional programs

The debugging of fully lazy functional programs can require searching a very large reduction-history space containing many delayed computations. A debugger should provide a means to obtain a source level representation of the computation, which can be large, and a means to select the appropriate part of the computation to investigate, which can be difficult. A method is presented to compile functional programs to combinator code such that a source-like representation of any part of a computation graph can be efficiently reconstructed at run-time. Other less efficient methods require excessive compile-time guidance as to the specific part of the computation to be investigated. Reconstruction, forward reduction, and a history-rollback mechanism combine to make the entire source-like reduction-history space dynamically available at run-time. The deferring of debugging decisions until run-time is called lazy dubugging. Once the computation-sequence is meaningfully and efficiently available, the problem of debugging becomes that of localizing the search for the error. Some searching issues are discussed with respect to graph browsing and user-interface design. The method shows promise as a programmer tool to debug programs and to informally reason about the time and space behavior of fully lazy functional programs, a nonintuitive process due to the subtleness of sharing and delayed computations.     

节点层次化的二进制文件比对技术

当前二进制文件比对技术主流是以BinDiff为代表的结构化比对方法,存在结构相似导致的误匹配、分析耗时较高的问题。针对该问题提出一种基于节点层次化、价值化的匹配方法。通过提取函数节点在函数调用图中的层次与函数在调用网络中的价值,对层次模糊的节点提供了节点层次估算算法,最后递归匹配节点。实验表明,该方法避免了结构相似导致的误匹配,其时耗低于结构化比对工具Bindiff的1/2,节点匹配数量减少在15%以内。该方法可有效提高嵌入式设备固件的跨版本相似性分析效率。     

稀疏判别分析

针对流形嵌入降维方法中在高维空间构建近邻图无益于后续工作,以及不容易给近邻大小和热核参数赋合适值的问题,提出一种稀疏判别分析算法（SEDA）。首先使用稀疏表示构建稀疏图保持数据的全局信息和几何结构,以克服流形嵌入方法的不足;其次,将稀疏保持作为正则化项使用Fisher判别准则,能够得到最优的投影。在一组高维数据集上的实验结果表明,SEDA是非常有效的半监督降维方法。     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

半监督图核降维方法

基于图结构的数据表示和分析,在机器学习领域正得到越来越广泛的关注。以往研究主要集中在为图数据定义一个度量其相似性关系的核函数即图核,一旦定义出图核,就可以用标准的支持向量机(SVM)来对图数据进行分类。将图核方法进行扩充,先利用核主成分分析(kPCA)对图核诱导的高维特征空间中的数据进行降维,得到与原始图数据相对应的低维向量表示的数据,然后对这些新得到的数据用传统机器学习方法进行分析;通过在kPCA中利用图数据中的成对约束形式的监督信息,得到基于图核的半监督降维方法。在MUTAG和PTC等标准图数据集上的实验结果验证了所提方法的有效性。     

基于时序结构图的视频流描述方法

通过对视频流的分解可以获得基于关键帧集的视频流表示,但这种表示方法不能反映出视频流中隐藏的故事发展关系,为揭示这种关系,提出了一种视频流的快速聚类算法,用于对视频流分解单元进行相关性分析,该算法通过检测视频镜头间的相似性和连续性,实现把来自同一摄像机的视频镜头归并入同一视频类,并帱此得到而且为矿山频流的快速浏览和检索提供了新的思路。     

一种核化图嵌入算法的快速求解模型

针对核化图嵌入算法对于人脸识别等高维小样本问题存在着计算量大且所需存储空间多的缺点,提出了一种核化图嵌入算法的快速求解模型。该模型的思想是首先对原始样本进行降维处理,对此给出了定理1和2。两个定理证明了样本先进行降维处理的可行性,同时也表明这一过程是不损失任何有效鉴别信息的。然后再对新的低维样本按核化图嵌入算法进行计算。人脸库上的实验结果表明,所提模型不但减少了算法的计算时间,同时也保证了算法的分类识别率。     

A timed semantics of Orc

Orc is a kernel language for structured concurrent programming. Orc provides three powerful combinators that define the structure of a concurrent computation. These combinators support sequential and concurrent execution, and concurrent execution with blocking and termination.Orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. Orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication.Our previous work on the semantics of Orc focused on its asynchronous behavior. The inclusion of time or the effect of delay on a computation had not been modeled. In this paper, we define an operational semantics of Orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. We develop a number of identities among Orc expressions and define an equality relation that is a congruence. We also present a denotational semantics in which the meaning of an Orc program is a set of traces, and show that the two semantics are equivalent.     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

Coverage probability driven dynamic spectrum allocation in heterogeneous wireless networks

In this paper,we design a dynamic spectrum allocation(DSA) scheme for heterogeneous cellular wireless networks with special interest on guaranteeing the cell coverage probability.To this end,considering users spatial distribution,we propose a new interference control(IC) model,which guarantees SINR(signal to interference plus noise ratio) requirements of different services and ensures the coverage performance of base stations(BSs).Under such an IC model,we formulate the DSA scheme as a combinatorial optimization problem.Since the problem is computationally intractable,we design an algorithm for its solution based on graph coloring.Simulation results indicate that the proposed DSA scheme can increase the total spectrum utility while effectively controlling the interference among BSs and meeting SINR requirements of users.     

加权分治与皇冠技术求解最大加权独立集

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度。针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法。     

Source model analysis using the JJTraveler visitor combinator framework

Program understanding tools manipulate program representations, such as abstract syntax trees, control‐flow graphs, or data‐flow graphs. This paper deals with the use of visitor combinators to conduct such manipulations. Visitor combinators are an extension of the well‐known visitor design pattern. They are small, reusable classes that carry out specific visiting steps. They can be composed in different constellations to build more complex visitors. We evaluate the expressiveness, reusability, ease of development, and applicability of visitor combinators to the construction of program understanding tools. To that end, we conduct a case study in the use of visitor combinators for control‐flow analysis and visualization as used in a commercial Cobol program understanding tool. Copyright © 2004 John Wiley & Sons, Ltd.     

低碳导向的网约车合乘动态匹配算法研究

针对网约车合乘减排效益未能充分发挥的问题,提出一种低碳导向的网约车合乘动态匹配算法,可在保证网约车合乘经济效益的同时优化合乘的减排效益。首先根据合乘规则构建可合乘网络,然后基于图优化理论将可合乘网络转换为带权无向图,同时基于COPERT模型计算潜在合乘订单的碳减排量作为无向图的权重,最后利用改进的最大权重匹配方法对其进行求解,进而得到碳减排效益最大化的合乘匹配方案。以成都市网约车订单数据为分析实例,对该算法与传统匹配算法进行对比评估。结果表明,当乘客最大允许延误为10 min时,该算法下的可合乘出行比例达86%,碳减排总量相比传统匹配算法可提高122%,单次合乘行程的减排效率平均提高128%。因此,本文提出的算法能够在不影响平台经济效益的情况下,显著提升合乘减排效益。     

基于动态进化图的行人轨迹预测

行人轨迹预测在自动驾驶和社交机器人等领域有着广泛的应用.对行人间复杂的交互关系进行有效建模是提高轨迹预测准确性的关键问题.然而,基于图神经网络的方法建模行人间的复杂交互时,存在行人间交互关系不会随着时间推移而改变,并且图模型无法自适应地调整网络参数,导致预测轨迹与真实轨迹偏差较大.为此,提出基于动态进化图的行人轨迹预测方法,设计动态特征更新(DFU)以定义行人间的动态特性,对行人间动态交互进行建模以构建时间域的网络动态性,提升对行人间复杂交互关系建模的能力.采用进化图卷积单元优化编码器,灵活进化图模型网络参数,增强图模型的自适应能力.研究结果表明,在预测8个时间步长下,与STGAT模型相比,所提出模型在两个公开数据集(ETH和UCY)上取得了更好的性能,平均位移误差降低12.26%,最终位移误差降低14.10%.