A visual debugger for pure Prolog

This work involves the design and coding of an interpreter for pure Prolog and building a visual debugger for it. Most of the available Prolog interpreters contain some tracing facilities. They do not incorporate, however, a comprehensive visual debugger. The interpreter performs the operations of parsing, unification, resolution, and search in a state-space representation of the Prolog program. The visual debugger incorporates the graphical visualization and the manipulation of the SLD resolution tree. The user visualizes the execution of a pure Prolog program and interacts with the program inside a windowing environment. The program execution may be viewed without interruption or the execution can be stopped at any moment in time. At this point the “snapshot” can be scrutinized with the help of break-points and data displays. This software aims itself to those who wish to observe the actual process of predicate unification, substitution, resolution and goal matching in a Prolog program and to visually interact with the interpreter using a highly friendly and pleasing user interface. An advanced feature, referred to as debugging on the tree, provides the user with the ability to insert break-points directly on the SLD tree, to choose the path of execution, and change the search mode. The resultant search algorithm can be a mixture of depth-first and breadth-first search, avoiding infinite search paths.     

The occur-check problem revisited

A method is presented for executing PROLOG programs which avoids almost all unnecessary occur-checks. The method is based on a dynamic classification of the context in which logical variables occur. No static global analysis of the PROLOG program is required to detect the places where an occur-check has to be made. The presented method has also an important side benefit. It considerably cuts down on the number of memory references during the execution of PROLOG programs. Furthermore, in most cases it avoids “trailing” and “untrailing” of unbound variables altogether. Due to this fact the employed method actually speeds up PROLOG execution. The method is discussed in terms of an actual implementation based on the Warren abstract PROLOG instruction set. However, the method should be applicable to other implementation models as well. No assumptions are made with respect to particular hardware.     

PROVIDE: a process visualization and debugging environment

The author introduces PROVIDE, a source-level process visualization and debugging environment currently under development at the University of Illinois at Chicago. PROVIDE is a modern coding and debugging environment that is designed to allow the user to configure interaction at a desired level of abstraction. It emphasizes the use of interactive computer graphics for the illustration of program execution, with special attention to the requirements of program debugging. The major features of PROVIDE are presented, especially the concepts of deferred-binding program animation, which allows users to interactively change the depiction of program execution during the debugging task, and process history consistency maintenance, which guarantees a consistent (automatically updated) record of program execution in the face of changes to program instructions and run-time data values. The current PROVIDE prototype is implemented on Macintosh workstations networked to a VAX 11/780 running 4.2 BSD Unix     

Fuzzy prolog

Various methods of representing uncertainty are discussed including some fuzzy methods. Representation and calculation of fuzzy expressions are discussed and a symbolic representation of fuzzy quantities coupled with axiomatic evaluation is proposed. This is incorporated into the PROLOG language to produce a fuzzy version. Apart from enabling imprecise facts and rules to be expressed, a natural method of controlling the search is introduced, making the search tree admissible.Formal expression of heuristic information in the same language, FUZZY PROLOG, as the main problem language follows naturally and therefore allows the same executor to evaluate in both “problem” space and “heuristic” space.In addition, the use of variable functors in the specification of bidirectional logic is discussed. The paper shows two areas of application of higher order fuzzy predicates. As an introduction Warren's examples are outlined and used with variable functors to illustrate their use in describing some relatively conventional applications.Translation of English into horn clause format is described and is used to illustrate the simplicity of representation using variable functors. Alternative formulations are also explored, typically the use of the “meta-variable” in MICRO-PROLOG and using the “univ” operator.Representation of rule generation and inference is addressed. Examples are given where the expression of meta-rules in standard PROLOG are compared with the expression of the same rules using “variable” predicate symbols. Some meta-rules illustrated are clearly not universally valid and this leads to the addition of fuzzy tokens.     

Incremental parsing without a parser

This article describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. Consider, for example, changing a “ + ” operator to a “1” operator or adding a short subexpression at a syntactically but not structurally correct position, such as inserting “) 1 (d“ at the # mark in” (a + b # + c)”. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This article describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. This algorithm is significantly different from other incremental parsing algorithms in that it does not involve modifications to a traditional parsing algorithm or the overhead of maintaining a parser stack or any data structure other than the syntax tree. Instead, the algorithm applies tree transformations, in real-time as each token is inserted or deleted, to maintain a correct syntax tree.     

Denotational and operational semantics for prolog

The semantics of PROLOG programs is usually given in terms of the model theory of first-order logic. However, this does not adequately characterizethe computational behavior of PROLOG programs. PROLOG implementations typically use a sequential evaluation strategy based on the textual order of clauses and literals in a program, as well as nonlogical features like cut. In this work we develop a denotational semantics that captures thecomputational behavior of PROLOG. We present a semantics for “cut-free” PROLOG, which is then extended to PROLOG with cut. For each case we develop a congruence proof that relates the semantics to a standard operational interpreter. As an application of our denotational semantics, we show the correctness of some standard “folk” theorems regarding transformations on PROLOG programs.     

The use of coherent ray tracing for physically accurate rendering

As the power of modern microprocessors increases, the coherent ray tracing becomes increasingly popular in computer graphics because the use of SIMD instructions considerably speeds up this operation. However, after speeding up ray tracing, it turns out that other algorithms for physically accurate rendering, such as the calculation of illumination or application of texture, etc., become a bottleneck in improving the performance. In this paper, a coherent physically accurate rendering algorithm is proposed that makes use of SIMD instructions of modern processors at each stage of the image generation. Coherent algorithms for the calculation of illumination and materials, for antialiasing, and for tone mapping are presented. The comparison of the execution time of coherent and incoherent algorithms using benchmark scenes showed that the former are considerably faster.     

Local matching of surfaces using a boundary-centered radial decomposition

A new surface representation, the “distance profile” is introduced. A distance profile is a decomposition of a surface into “distance contours,” each of which is the locus of all points a certain distance r from a point called the “center point.” The distance contour is in turn represented as a plot of the contour's distance from its centroid as a function of arc length along the contour. The distance profile representation is invariant with respect to rotation about the center point and thus is ideal for “rigid matching” (where the correspondence function between two objects is a rotation and/or translation). For global matching, the center point can be the centroid of the surface. For local matching, we compute multiple distance profiles, each centered around a “critical point” on the surface (a minimum or maximum of curvature or a sharp peak in the surface). This comprises the “boundary-centered radial decomposition.” An implementation of a local surface matcher based on theboundary-centered radial decomposition is described.     

Graphical simulation of Petri Nets

An interactive graphics package for modeling with Petri Nets has been implemented. It uses the VT-11 graphics terminal supported on the PDP-11/35 computer to draw, execute, analyze, edit and redraw a Petri Net. Each of the above mentioned tasks can be performed by selecting appropriate items from a menu displayed on the screen. Petri Nets with a reasonably large number of nodes can be created and analyzed using this package. The number of nodes supported may be increased by making simple changes in the program. Being interactive, the program seeks information from the user after displaying appropriate messages on the terminal. After completing the Petri Net, it may be executed step by step and the changes in the number of tokens may be observed on the screen, at each place. Some properties of Petri Nets like safety, boundedness, conservation and redundancy can be checked using this package. This package can be used very effectively for modeling asynchronous (concurrent) systems with Petri Nets and simulating the model by “graphical execution.”     

多核处理器YHFT-QDSP的调试系统

YHFT-QDSP是一款多核处理器。为满足其并发调试和实时调试的需要,在原有单核调试系统的基础上设计实现了多核同步调试系统和片上实时追踪系统（片上Trace）。多核同步调试提供了命令广播和断点同步触发等并发程序协同调试的功能;片上Trace通过专用硬件记录程序执行路径和数据读写等信息实现非入侵实时调试。本文从原理、结构和
软硬件实现等方面介绍了该调试系统。     

并发约束程序设计语言COPS及其执行模型

约束程序设计尤其是约束逻辑程序设计与并发约束程序设计在AI程序设计领域占据着越来越重要的位置。传统逻辑程序设计的基“计算即为定理证明”的计算风格虽获得了简洁优美的操作语义特性,但也付出了执行效率低的代价,当应用系统规模增大时,其性能严重下降以致崩溃。针对传统逻辑程序设计的这种可伸缩性问题,设计了一个基于并发约束程序设计概念的说明性语言COPS,旨在从语言设计与执行模型两方面降低说明性程序的不确定性,提高搜索与运行效率。在语言设计方面,通过引入确定性语言成分,避免不确定计算用于确定性目标所浪费的系统开销;在执行模型方面,在目标的并发穿叉执行与数据驱动的并发同步机制的基础上,实现“优先执行确定目标”策略与“最少假定”策略,作为约束传播的延伸,最大幅度地剪枝搜索空间,降低搜索复杂性。COPS提供的知识表示、推理与并发机制使其成为构造agent程序的理想语言。论文给出COPS语言的语法规范与执行模型的操作语义描述。     

A PCA approach for fast retrieval of structural patterns inattributed graphs

An attributed graph (AG) is a useful data structure for representing complex patterns in a wide range of applications such as computer vision, image database retrieval, and other knowledge representation tasks where similar or exact corresponding structural patterns must be found. Existing methods for attributed graph matching (AGM) often suffer from the combinatorial problem whereby the execution cost for finding an exact or similar match is exponentially related to the number of nodes the AG contains. The square matching error of two AGs subject to permutations is approximately relaxed to a square matching error of two AGs subject to orthogonal transformations. Hence, the principal component analysis (PCA) algorithm can be used for the fast computation of the approximate matching error, with a considerably reduced execution complexity. Experiments demonstrate that this method works well and is robust against noise and other simple types of transformations.     

Propositional representation for graphical knowledge

Multi-media interfaces with a graphics and a natural language component can be viewed as a Natural Language Graphics systems without a host program. We will investigate a theory of Natural Language Graphics that is based on the notion of “Graphical Deep Knowledge” defined in this research. Graphical Deep Knowledge is knowledge that can be used for display purposes as well as reasoning purposes and we describe the syntax and semantics of its constructs. This analysis covers forms, positions, attributes, parts, classes, reference frames, inheritability, etc. Part hierarchies are differentiated into three sub-types. The usefulness of inheritance along part hierarchies is demonstrated, and criticism of inheritance-based knowledge representation formalisms with a bias towards class hierarchies is derived from this finding. The presented theory has been implemented as a generator program that creates pictures from knowledge structures, and as an augmented transition network grammar that creates knowledge structures from limited natural language input. The function of the picture generation program Tina as a user interface for a circuit board maintenance system and as part of a CAD-like layout system is demonstrated.     

Evaluation of a graphical interaction technique using GKS

This paper shortly presents an interactive application with graphics in the field of computer-aided education that has been designed and implemented by using a window-oriented style of interaction. The main idea was to separate the dialogue from the application functions. Thus the basic building blocks of the dialogue have been based on a conceptual model called the interaction event model that also provides both “help” and “abort” facilities. GKS (level 1b) has been used for the production and manipulation of graphical entities, as well as for providing high portability.     

Low overhead path regeneration

Monte Carlo Path Tracing is a core light transport technique which is used for modern methods (like BDPT, MLT, VCM and others). One of the main challenge of efficient GPU Path Tracing implementation is inefficient workload caused by paths of different lengths; few threads process the long paths, while other threads are idle. A work distribution technique called “Path Regeneration” is commonly used to solve this problem. We introduce a novel GPU implementation of path regeneration technique called “in place block based path regeneration.” In comparison to previous approaches our algorithm possesses two main advantages: it has lower self-cost and it does not move any per-ray data along threads in memory, thus, our algorithm can be easily integrated to any advanced path tracing technique (like BDPT, MLT and other) or photon mapping. We tested our solution with path tracing using both CUDA and OpenCL.     

并发环境中渐增式追踪重演机制

在基于消息传递的并发程序中,由于进程的调度顺序以及消息延时等特性,使得同样输入的不同执行呈现不同的结果,这种并发程序行为的不确定性直接导致了程序错误的不可再现性,即后续的执行无法再现前次执行的错误。以反复执行程序、重复再现故障为核心的循环调试方法变得不再可用。因此,对于并发程序的调试问题,我们将传统的循环调试方法加以扩充,引入追踪和重演的机制,重放程序的某次执行,以消除并发程序的错误不可再现性。