Data-flow based execution mechanisms of Parallel and Concurrent Prolog

Study attempts to show that our machine architecture based on the data flow model is suitable for two types of logic programming languages with different aims: one is Parallel Prolog and the other is Concurrent Prolog. The data flow model can naturally implement parallel computation, and it has close similarity to these languages. Unification and nondeterministic control, two basic functions of these languages, are represented by data flow graphs and interpreted by the machine. Several representations of variables, that facilitate the development of parallel unification and nondeterministic control mechanisms for these languages, the unification and control primitives needed to execute these languages on this architecture are presented.     

Sparse coding of i-vector/JFA latent vector over ensemble dictionaries for language identification systems

Computing sparse representation (SR) over an exemplar dictionary is time consuming and computationally expensive for large dictionary size. This also requires huge memory requirement for saving the dictionary. In order to reduce the latency and to achieve some diversity, ensemble of exemplar dictionary based language identification (LID) system is explored. The full diversity can be obtained if each of the exemplar dictionary contains only one feature vector from each of the language class. To achieve full diversity, a large number of multiple dictionaries are required; thus needs to compute SR for a particular test utterance as many times. The other solution to reduce the latency is to use a learned dictionary. The dictionary may contain unequal number of dictionary atoms and it is not guaranteed that each language class information is present. It totally depends upon the number of data and its variations. Motivated by this, language specific dictionary is learned, and then concatenated to form a single learned dictionary. Furthermore, to overcome the problem of ensemble exemplar dictionary based LID system, we investigated the ensemble of learned-exemplar dictionary based LID system. The proposed approach achieves the same diversity and latency as that of ensemble exemplar dictionary with reduced number of learned dictionaries. The proposed techniques are applied on two spoken utterance representations: the i-vector and the JFA latent vector. The experiments are performed on 2007 NIST LRE, 2009 NIST LRE and AP17-OLR datasets in closed set condition.     

Replacing unification by constraint satisfaction to improve logic program expressiveness

Unification, the heart of resolution, was formulated to work in the Herbrand universe and hence does not incorporate any function evaluation. Matching is completely syntactic. In this paper, we study the replacement of unification by a constraints solver in automatic theorem proving systems using Prolog as our example. The generalization of unification into a constraint satisfaction algorithm allows the (limited) incorporation of function evaluation into unification. Constraints are also allowed as literals in the clause. We discuss the enhanced expressive power that results from incorporating an efficient constrained unifier into an automatic theorem proving system. An interpreter for the extended Prolog system (written in Prolog) incorporating a constraint solver is presented along with examples illustrating its capabilities.     

An Experiment in Abstract Machine Design

In this article we present Typed Feature Structures as an extension of Prolog, and show how to come up with a compilation scheme and an abstract machine using a design methodology based on partial evaluation. First we define the transformations used by our partial evaluator. Then we present the design methodology which we will use later. Next, we clarify the notion of Typed Feature Structures that underlies our work, and formally define the unification of such structures. Based on this definition, we develop a unification procedure with explicit heap representation. By partially evaluating this procedure with respect to some example programs, we show how to come up with the machine instructions and translation schemes. Finally, we briefly address coreferences, cyclic structures and the unification of types. © 1997 by John Wiley & Sons, Ltd.     

How to invent a Prolog machine

In this paper we study the compilation of Prolog by making visible hidden operations (especially unification), and then optimizing them using well-known partial evaluation techniques. Inspection of straightforward partially evaluated unification algorithms gives an idea how to design special abstract machine instructions which later form the target language of our compilation. We handle typical compiler problems like representation of terms explicitly. This work gives a logical reconstruction of abstract Prolog machine code, and represents an approach of constructing a correct compiler from Prolog to such a code. As an example, we are explaining the unification principles of Warren’s New Prolog Engine within our framework.     

P#: a concurrent Prolog for the .NET framework

We discuss P#, our implementation of a tool that allows interoperation between a concurrent superset of the Prolog programming language and C#. This enables Prolog to be used as a native implementation language for Microsoft's .NET platform. P# compiles a linear logic extension of Prolog to C# source code. We can thus create C# objects from Prolog and use C#'s graphical, networking and other libraries. We add language constructs on the Prolog side that allow concurrent Prolog code to be written. A primitive predicate is provided that evaluates a Prolog structure on a newly forked thread. Communication between threads is based on the unification of variables contained in such a structure. It is also possible for threads to communicate through a globally accessible table. All of the new features are available to the programmer through new built-in Prolog predicates. We discuss two software engineering tools implemented using P#. Copyright © 2004 John Wiley & Sons, Ltd.     

面向数据的句法分析技术

面向数据的分析技术(Data-Oriented Parsing ,DOP) 首先由Scha (1990) 年提出。该处理技术具体表达了这样的假设:人类对语言的领悟和创造依赖于以往具体的语言经验,而不是依赖于抽象的语法规则。DOP 技术框架可以分为: (1) 建立包括以往成功分析的语言经验的标注语料库; (2) 从语料库中抽取片段单元来构造新语言的分析过程;(3) 计算分析过程的概率。DOP 模型建立在包含大量语言现象的语料库基础上,把经过标注的语料库看作一个语法( Grammar) 。当输入一个新的语言现象时,系统通过对语料库中片段单元的组合运算来组合分析过程。根据所有片段单元的共现频率来评估最有可能性的分析结果。本文详细论述了语料库的标注,片段单元的定义,组合分析和概率计算。     

On parallel unification for Prolog

Parallel unification algorithms are not nearly so numerous or well-developed as sequential ones. In order to estimate the improvement in efficiency which may be expected, we define and discuss an objective measure of the effect of parallelism on a sequential algorithm. This measure, known as thepotential parallel factor (PPF), is applied to parallel versions of the unification algorithms of Yasuura and Jaffar. The PPFs for these algorithms are measured on a variety of running Prolog programs to estimate what increase in speed may be expected in a Prolog environment from the use of parallelism. Other potential uses of parallelism may be evaluated by different applications of our general methods and techniques.     

A full theorem-prover under uncertainty

Prolog embodies an ordered input resolution inference mechanism, with a powerful unification procedure. However, Prolog is not a full theorem-prover, and does not contain an inexact reasoning mechanism. In this paper, it is shown how these capabilities can be combined in a Prolog environment. A Prolog meta-interpreter is used in an elegant and simple way for this purpose. The inexact reasoning mechanism is presented through the certainty factor model, but it is also discussed how other inexact reasoning models may be also implemented.     

A prolog technology theorem prover: Implementation by an extended prolog compiler

A Prolog technology theorem prover (PTTP) is an extension of Prolog that is complete for the full first-order predicate calculus. It differs from Prolog in its use of unification with the occurs check for soundness, the model-elimination reduction rule that is added to Prolog inferences to make the inference system complete, and depth-first iterative-deepening search instead of unbounded depthfirst search to make the search strategy complete. A Prolog technology theorem prover has been implemented by an extended Prolog-to-LISP compiler that supports these additional features. It is capable of proving theorems in the full first-order predicate calculus at a rate of thousands of inferences per second.This is a revised and expanded version of a paper presented at the 8th International Conference on Automated Deduction, Oxford, England, July 1986.This research was supported by the Defense Advanced Research Projects Agency under Contract N00039-84-K-0078 with the Naval Electronic Systems Command and by the National Science Foundation under Grant CCR-8611116. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, the National Science Foundation, or the United States government. Approved for public release. Distribution unlimited.     

一种基于情感特征表示的跨语言文本情感分析模型

基于深度学习的跨语言情感分析模型需要借助预训练的双语词嵌入(Bilingual Word Embedding,BWE)词典获得源语言和目标语言的文本向量表示.为了解决BWE词典较难获得的问题,该文提出一种基于词向量情感特征表示的跨语言文本情感分析方法,引入源语言的情感监督信息以获得源语言情感感知的词向量表示,使得词向量...     

POPE — a parallel-operating prolog engine

An architecture is presented for the parallel execution of sequential Prolog. The architecture is based on a pipeline of unification processors and designed to work as a co-processor to a more conventional, UNIX based workstation. The unification processors execute highly optimized compiled Prolog code; however, the basic concept of the architecture could also increase the performance of interpreter based systems. It will be shown that even programs that do not exhibit any of the ‘classical’ forms of parallelism (i.e. AND-, OR-parallelism, etc.) can be effectively mapped onto the proposed architecture. The presented architecture should also prove very effective as a multi-user Prolog machine executing several independent Prolog programs in parallel. In contrast to other attempts to execute sequential Prolog in parallel we do not restrict the use of any of the standard Prolog language features such as dynamic assert/retract, CUT, etc. Simulation results show that peak execution rates of over 1000 KLIPS can be obtained.     

Specification and correctness proof of a WAM extension with abstract type constraints

We provide a mathematical specification of an extension of Warren's Abstract Machine (WAM) for executing Prolog to type-constraint logic programming and prove its correctness. Our aim is to provide a full specification and correctness proof of a concrete system, the PROTOS Abstract Machine (PAM), an extension of the WAM by polymorphic order-sorted unification as required by the logic programming language PROTOS-L.In this paper, while leaving the details of the PAM's type constraint representation and solving facilities to a sequel to this work, we keep the notion of types and dynamic type constraints abstract to allow applications to different constraint formalisms like Prolog III or CLP(R). This generality permits us to introduce modular extensions of Börger's and Rosenzweig's formal derivation of the WAM. Since the type constraint handling is orthogonal to the compilation of predicates and clauses, we start from type-constraint Prolog algebras with compiled AND/OR structure that are derived from Börger's and Rosenzweig's corresponding compiled standard Prolog algebras. The specification of the type-constraint WAM extension is then given by a sequence of evolving algebras, each representing a refinement level, and for each refinement step a correctness proof is given. Thus, we obtain the theorem that for every such abstract type-constraint logic programming system L, every compiler to the WAM extension with an abstract notion of types which satisfies the specified conditions, is correct.The first author was partially funded by the German Ministry for Research and Technology (BMFT) in the framework of the WISPRO Project (Grant 01 IW 206). He would also like to thank the Scientific Center of IBM Germany where the work reported here was started.     

Parallel model representations

Most mathematical programming models and knowledge-based systems in optimization from exist in various representations; however, the user is frequently not aware of this. For example, a model which is developed with a knowledge-based system such as the PM system of Krishnan (1988) will have several representations in Prolog and then will be translated into another representation in Structured Modeling before it is solved. Also, a model which is developed in the GAMS language will be translated into an MPS input form internally before the problem is passed to a solver such as MINOS. The results from MINOS are then passed back to GAMS and the user sees the results in the style of the GAMS representation of the model. This could be called a vertical set of model representations since the user can modify only one representation and the models are passed down directly to the solver.

This paper argues that in considering knowledge-based systems with optimization we should begin to employ a set of parallel model representations, any one of which the user can see and modify. These can be called horizontal model representations. For example, a given model might be represented in graphical, knowledge base, modeling language, and mathematical forms. The user would be able to modify any of these versions and have the other representations altered automatically to reflect the changes.     

维汉机器翻译用电子词典的设计

电子词典是在机器翻译系统中包含的信息量最大的一个部件,电子词典包的质量和容量直接限定机器翻译的质量和应用范围。与一般的电子词典不同,机器翻译词典每个词条都要比一般的电子词典增加词类信息、语义类别信息和成语等。文章以频率统计和频率分布统计作为维汉机器翻译词典的词条收录原则,统计维吾尔文中常用的单词数目,论述维汉机器翻译词典的设计思想,用BNF形式语言和Jackson图描述维汉机器翻译词典应包含的词条信息,最后介绍词典的具体构造方法、词条排序原则、索引表和属性库的数据结构和词典信息的查找方法。试验表明该词典在解决维吾尔语词汇歧义、结构歧义、提高汉语译文准确率等方面较为有效。     

基于类邻域字典的线性回归文本分类

文本表示的高维性会增加文本分类时的计算复杂度。针对该问题,构建基于类邻域字典的线性回归分类模型。采用K近邻方法构造各类别的类邻域字典,根据对测试样本的不同表示,分别提出基于级联类邻域字典和基于类邻域字典的线性回归分类算法。此外,为缓解噪声数据对分类性能的影响,通过度量测试样本与各个类别之间的相关度裁剪噪声类数据。实验结果表明,该模型对长文本和短文本均能够得到较高的分类精度和计算效率,同时,噪声类裁剪策略使其对包含较多类别数的文本语料也具有较好的分类性能。     

Sequential Prolog machine PEK

The sequential Prolog machine PEK currently under development is described. PEK is an experimental machine designed for high speed execution of Prolog programs. The PEK machine is controlled by horizontal-type microinstructions. The machine includes bit slice microprocessor elements comprising a microprogram sequencer and ALU, and possesses hardware circuits for unification and backtracking. The PEK machine consists of a host processor (MC68000) and a backend processor (PEK engine). A Prolog interpreter has been developed on the machine and the machine performance evaluated. A single inference can be executed in 89 microinstructions, and execution speed is approximately 60–70 KLIPS.     

Prosum-Prolog system for uncertainty management

In this paper we present a system which uses knowledge represented in the form of production rules accompanied by uncertainty degrees. The uncertainty of a rule is given by using the method from SLOP and FRIL: a support pair, which comprises a necessary and possible support and can be interpreted as an interval in which the unknown probability lies. Giving the knowledge in this form, our system generates a Turbo Prolog program which has included the operations for uncertainty management. In this version, two kinds of rules for support logic programming are implemented but the user can propose the other ones, by using the dialogue with the system. Semantic unification differs from that used in FRIL; we use generalized belief functions. © 1997 John Wiley & Sons, Inc.     

Focal structures and information types in Prolog

Several studies have suggested that the mental structures of programmers of procedural languages have a close relationship with a model of structural knowledge related to functional information known as programming Plans. It also has been claimed that experienced programmers organize this representation in a hierarchical structure where some elements of Plans are focal or central to them. However, it is not clear that this is the case for other types of programming languages, especially for those which are significantly different from the procedural paradigm.The study reported in this paper investigates whether these claims are true for Prolog, a language which has important differences to procedural languages. Prolog does not have obvious syntactic cues to mark blocks of code (begin/end, repeat/until, etc). Also, its powerful primitives (unification and backtracking) and the extensive use of recursion might influence how programmers comprehend Prolog code in a significant way.The findings of the study suggest that Plans and functional information are important for Prolog programmers, but that there is also at least another model of structural knowledge valid for this language. This model of structural knowledge, Prolog schemas, is related to data structure information and it seems that a hierarchical organisation that highlights the relevance of some of its elements as focal is valid for Prolog. These results support the view that comprehension involves the detection of varying aspects of the code and that each of the structures related to these aspects might have their own organization and hierarchical relations.