Moped (a portable debugger)

Moped is a portable debugger that uses enhanced tracing facilities and backtracing to discover unusual or undesirable program behaviors. It is based upon two modules — Program Probes and Program History. Program Probes is a forward tracing utility which allows Moped to dynamically examine the execution of a program. Program History is a backtracing utility which allows Moped to study the executed section of a program. Together, Program Probes and Program History enable Moped to have more control over the behavior of a program than either one of them, and consequently to provide an easier path toward program debugging. Moped is written in Common LISP with no dependencies on details of the machine implementation. Therefore, it is easily portable to any Common LISP environment.     

A portable lisp compiler

The programming language LISP is usually implemented via an interpreter, and a compiler is added later as a LISP program. However, all such production compilers known to the authors produce explicit instructions for the given computer being used. This paper describes the development of a portable LISP compiler in the sense that only Standard LISP functions are used in its definition and the output is a sequence of abstract machine codes, easily mapped to instruction sequences on current computers. The resulting code is quite efficient, demonstrating once again the maxim that most compiler optimization is largely machine independent.     

基于C++及其扩展语言的动态剖析

程序优化是提高程序运行效率的重要步骤,程序剖析是程序优化的第一步。对于串行语言,程序剖析代码是由编译器通过一个命令行开关自动插入。但是,大部分并行语言编译器都不具有这个功能。该文以并行C++语言的可移植的动态剖析程序(profiler)为例,从两方面对问题进行了论述:首先给出实现可移植动态剖析程序的一般方法;然后分析一个用于pC++插桩(Instrumentation)工具。     

Source-to-Source Instrumentation for the Optimization of an Automatic Reading System

Recording address traces that occur during a program execution is a significant technique for computer performance analysis. This paper describes a software method for address tracing via the instrumentation of C based languages. All program transformations are performed at the language level. This approach, which differs from the usual methods, allows portable and flexible program instrumentation. This tool has been developed to make easier the memory optimization of LIREChèques, an automatic bank check reading system. Two applications of the tool are clearly identified: (i) data cache use optimization, (ii) dynamic memory use optimization.     

LISP as a rapid prototyping environment: The Chinese tutor

LISP provides a powerful interactive environment that supports rapid prototyping of complex software. This has always been a main feature of the language, and one that has contributed to its widespread use for experimental applications. Recent years have also seen the development of LISP systems that provide performance comparable with, or better than, that of more traditional programming languages. The next logical step is to show that systems developed in LISP with a rapid-prototyping approach can also provide excellent performance. As an example of the suitability of LISP for rapid prototyping of efficient systems, this article presents a case study where a system was built in a Common Lisp environment out of a series of existing tools. Reliance on existing tools, as well as the interactive features typical of LISP, resulted in extremely rapid prototyping. The system, a computer-based tutor for beginner-level Chinese, was developed in less than three man-weeks. Very rapid development time, however, did not in any way sacrifice performance: the system's performance is quite good and comparable to that of ad hoc systems. This is true of both the interactive component of the program, i.e. the interface to the student, and the database component, which stores the system's knowledge about the Chinese language. The factors that contributed most to the short development time were the extensive reliance on existing tools, the use of an efficient knowledge representation language to implement most of the data structures, and the use of an integrated programming environment. All of these factors were in turn made possible, or at least greatly facilitated, by the choice of LISP as the programming language.     

Program Reusability through Program Transformation

How can a program written in pure applicative LISP be reused in a Fortran environment? One answer is by automatically transforming it from LISP into Fortran. In this paper we discuss a practical application of this technique-one that yields an efficient Fortran program. We view this process as an example of abstract programming, in which the LISP program constitutes an abstract specification for the Fortran version. The idea of strategy-a strategy for getting from LISP to Fortran-is basic to designing and applying the transformations. One strategic insight is that the task is easier if the LISP program is converted to ``recursive' Fortran, and then the recursive Fortran program is converted to nonrecursive standard Fortran. Another strategic insight is that much of the task can be accomplished by converting the program from one canonical form to another. Developing a strategy also involves making various implementation decisions. One advantage of program transformation methodology is that it exposes such decisions for examination and review. Another is that it enables optimizations to be detected and implemented easily. Once a strategy has been discovered, it can be implemented by means of rewrite-rule transformations using the TAMPR program transformation system. The transformational approach to program reuse based on this strategy has a measure of elegance. It is also practical-the resulting Fortran program is 25 percent faster than its compiled LISP counterpart, even without extensive optimization.     

A tutorial on LISP object-oriented programming for blackboard computation (solving the radar tracking problem)

This exposition is a tutorial on how object-oriented programming (OOP) in LISP can be used for programming a blackboard. Since we have used Common LISP and the Common LISP Object System (CLOS), the exposition demonstrates how object classes and the primary, before, and after methods associated with the classes can be used for this purpose. the reader should note that the different approaches to object-orient programming share considerable similarity and, therefore, the exposition should be helpful to even those who may not wish to use CLOS. We have used the radar tracking problem as a “medium” for explaining the concepts underlying blackboard programming the blackboard database is constructed solely of classes which act as data structures as well as method-bearing objects. Class instances form the nodes and the levels of the blackboard. the methods associated with these classes constitute a distributed monitor and support the knowledge sources in modifying the blackboard data. A rule-based planner is used to construct knowledge source activation records from the goals residing in the blackboard. These activation records are enqueued in a cyclic queueing system. A scheduler cycles through the queues and selects knowledge sources to fire. © John Wiley & Sons, Inc.     

A reduce package for determining lie symmetries of ordinary and partial differential equations

Title of program: LIE0,LIE1,LIE2,LIE3,LIE4 Catalogue number: AAZB Program obtainable form: CPC Program library, Queen's University in Belfast, N. Ireland (see application form in this issue) Computer: Siemens 7.760 Operating system: BS 2000 Programming language used: LISP High speed storage required: depends on the problem, minimum about 400 000 bytes No. of bits in a word: 32 Number of cards in combined program and test deck: 200     

A Massively Parallel Memory-Based Story System for Psychotherapy

We describe a memory-based system for psychotherapy, Dr. Bob, built to run on the data parallel processor Thinking Machines, Inc., CM-2a Connection Machine. The system retrieves, in parallel, stories of alcohol addiction and sexual abuse which can he used by psychiatrists in working with their patients as part of their work in recovering from addictive behavior and psychological trauma. The program is written in *LISP (pronounced Star LISP), a version of LISP used in programming Connection Machines.     

Automatic program debugging for intelligent tutoring systems

Program debugging is an important part of the domain expertise required for intelligent tutoring systems that teach programming languages. This article explores the process by which student programs can be automatically debugged in order to increase the instructional capabilities of these systems. The research presented provides a methodology and implementation for the diagnosis and correction of nontrivial recursive programs. In this approach, recursive programs are debugged by repairing induction proofs in the Boyer-Moore logic. The induction proofs constructed and debugged assert the computational équivalence of student programs to correct exemplar solutions. Exemplar solutions not only specify correct implementations but also provide correct code to replace buggy student code. Bugs in student code are repaired with heuristics that attempt to minimize the scope of repair. The automated debugging of student code is greatly complicated by the tremendous variability that arises in student solutions to nontrivial tasks. This variability can be coped with, and debugging performance improved, by explicit reasoning about computational semantics during the debugging process. This article supports these claims by discussing the design, implementation, and evaluation of Talus, an automatic debugger for LISP programs, and by examining related work in automated program debugging. Talus relies on its abilities to reason about computational semantics to perform algorithm recognition, infer code teleology, and to automatically detect and correct nonsyntactic errors in student programs written in a restricted, but nontrivial, subset of LISP. Solutions can vary significantly in algorithm, functional decomposition, role of variables, data flow, control flow, values returned by functions, LISP primitives used, and identifiers used. Solutions can consist of multiple functions, each containing multiple bugs. Empiricial evaluation demonstrates that Talus achieves high performance in debugging widely varying student solutions to challenging tasks.     

PLASHTRAN: An expert consultant on two-dimensional finite element modeling techniques

An expert consultant and teaching aid has been developed to aid users of the MSC/NASTRAN (MacNeal-Schwendler Corp, Los Angeles, CA, USA) finite element code in the modeling process with two-dimensional elements. Written in LISP and LOOPS, an object-oriented programming language, the system, known as PLASHTRAN, allows engineers to work in a natural environment to obtain modeling recommendations. The program performs efficiently, especially when iterations in design require changes in the finite element model. The easily expandable modeling framework allows the knowledge base to incorporate new information.     

LISP-MNet:一种支持移动的身份/位置分离方案

LISP是具有代表性的身份/位置分离方案之一,为了支持移动性,IETF IESG工作组在其原有基础上提出了LISP-MN,但这种方案需要修改主机协议栈,无法支持现有移动终端的接入,短期内难以大规模推广应用.设计一种支持主机移动性的身份/位置分离架构LISP-Mnet;在标准的LISP基础上,通过引入映射分发机制,实现了标地映射的快速分发与同步;通过在边缘接入设备实现主动注册机制,无需对终端协议栈作任何修改,即可支持移动终端在各站点之间的随遇接入和任意切换,提高了终端的移动接入能力.最后,实现了LISP-MNet的原型系统和实际组网测试,对单节点映射服务器进行了压力测试,测试结果表明其映射规模可达100M;通过VLC视频应用进行移动终端接入站点切换时延测试,结果表明,移动切换时间低于2s,移动终端在切换接入站点后,VLC视频服务器与客户端可在2s内完成视频同步.     

Parallel programming interface for distributed data

The Parallel Programming Interface for Distributed Data (PPIDD) library provides an interface, suitable for use in parallel scientific applications, that delivers communications and global data management. The library can be built either using the Global Arrays (GA) toolkit, or a standard MPI-2 library. This abstraction allows the programmer to write portable parallel codes that can utilise the best, or only, communications library that is available on a particular computing platform.Program summaryProgram title: PPIDDCatalogue identifier: AEEF_v1_0Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEEF_1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 17 698No. of bytes in distributed program, including test data, etc.: 166 173Distribution format: tar.gzProgramming language: Fortran, CComputer: Many parallel systemsOperating system: VariousHas the code been vectorised or parallelized?: Yes. 2–256 processors usedRAM: 50 MbytesClassification: 6.5External routines: Global Arrays or MPI-2Nature of problem: Many scientific applications require management and communication of data that is global, and the standard MPI-2 protocol provides only low-level methods for the required one-sided remote memory access.Solution method: The Parallel Programming Interface for Distributed Data (PPIDD) library provides an interface, suitable for use in parallel scientific applications, that delivers communications and global data management. The library can be built either using the Global Arrays (GA) toolkit, or a standard MPI-2 library. This abstraction allows the programmer to write portable parallel codes that can utilise the best, or only, communications library that is available on a particular computing platform.Running time: Problem dependent. The test provided with the distribution takes only a few seconds to run.     

A Cognitive Model and Computer Tutor for Programming Recursion

This article discusses cognitive models of learning to program recursion and their relation to lessons on recursion in an intelligent computer tutor for LISP programming (the LISP Tutor). The cognitive models are implemented as production systems in which programming skill is characterized as the decomposition of programming goals into subgoals and elementary actions via the application of programming plans. Two sets of learning mechanisms are used in the cognitive models. Analogical problem-solving mechanisms use declarative knowledge of example program solutions to overcome problem-solving impasses. Knowledge compilation mechanisms summarize problem solutions into efficient problem-solving skill. Analyses and simulations of novice and expert programming were used to develop ideal models of the programming knowledge to confer upon students and bugs that characterize common misconceptions. The LISP Tutor uses the ideal models and bugs to guide its interactions with students. Experimental evaluations of the LISP Tutor indicate that it is more efficient and effective than classroom instruction.     

Experience with software conversion

Experience with a program to convert from LISP 1.6 to INTERLISP is described. The conversion program was designed with two goals in mind. First, it had to be capable of being executed in either of the languages's environments and it had to yield identical results. Second, the speed of the converted program was to be approximately the same as the original program. This meant that the conversion process must be completed prior to execution of the converted program. The various constraints and considerations imposed by these goals are examined. In addition, aside from problems in finding INTERLISP analogs for various LISP 1.6 constructs, careful consideration must also be paid to input/output functions, escape characters, global variables, representation of numbers and different string implementations.     

函数式语言并行化的方法

Lisp作为一个表处理语言.有着悠久的历史,而COMMON LISP提供一r丰富的数据集和多程序设计模式:函数的,强制的和面向对象的〔“·幻。我们以COMMON LISP为蓝本完成T XJD一LISP/CLOS,它是为我国曙光一号机配备的.现已通过国家教委组织的鉴定。最近我们正在开发COMMON LISP的并行版本,作为863计划资助项目,这个工作很有意义。该并行系统将加速计算,并且还能对XJD一 LISP/CLOS提供支持。本文就函数式语言并行化的方法进行了探讨。     

A portable high-level database debugger and software performance monitor

The package DBDEBUG assits the users of CODASYL (network) database management systems in two ways. It can be used by applications programmers to debug their programs, and by the database administrator to monitor the performance of the database. The user may select the sections (or even individual statements) of his program to be traced and/or monitored. He may list the specific records and items he wishes to be investigated; he may also restrict tracing and monitoring to only certain DML verbs. The user's database schema and subschema are submitted to processors which generate a data dictionary. This data dictionary is then used by DBDEBUG in modifying the user's DML source code in order to obtain the specified tracing or performance statistics. The output is high-level in that it reflects the high-level language (DML COBOL) in which the user's source code was written. The package is designed to be portable. All but one of its components are written in standard Pascal or ANSI COBOL; assembler code is restricted to a ten-line subroutine which obtains L/O and CPU times from the operating system.     

Optimising code generation with haggies

This article describes haggies, a program for the generation of optimised programs for the efficient numerical evaluation of mathematical expressions. It uses a multivariate Horner-scheme and Common Subexpression Elimination to reduce the overall number of operations.The package can serve as a back-end for virtually any general purpose computer algebra program. Built-in type inference that allows to deal with non-standard data types in strongly typed languages and a very flexible, pattern-based output specification ensure that haggies can produce code for a large variety of programming languages.We currently use haggies as part of an automated package for the calculation of one-loop scattering amplitudes in quantum field theories. The examples in this articles, however, demonstrate that its use is not restricted to the field of high energy physics.

Program summary

Program title: haggiesCatalogue identifier: AEGF_v1_0Program summary: URL: http://cpc.cs.qub.ac.uk/summaries/AEGF_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU GPL v3No. of lines in distributed program, including test data, etc.: 56 220No. of bytes in distributed program, including test data, etc.: 579 010Distribution format: tar.gzProgramming language: Java, JavaCCComputer: Any system that runs the Java Virtual MachineOperating system: Any system that runs the Java Virtual MachineRAM: Determined by the size of the problemClassification: 4.14, 5, 6.2, 6.5, 11.1Nature of problem: Generation of optimised programs for the evaluation of possibly large algebraic expressionsSolution method: Java implementationRunning time: Determined by the size of the problem