5180180
Logic programming in a fragment of intuitionistic linear logic
The intuitionistic notion of context is refined by using a fragment of J.-Y. Girard's (Theor. Comput. Sci., vol.50, p.1-102, 1987) linear logic that includes additive and multiplicative conjunction, linear implication, universal quantification, the of course exponential, and the constants for the empty context and for the erasing contexts. It is shown that the logic has a goal-directed interpretation. It is also shown that the nondeterminism that results from the need to split contexts in order to prove a multiplicative conjunction can be handled by viewing proof search as a process that takes a context, consumes part of it, and returns the rest (to be consumed elsewhere). Examples taken from theorem proving, natural language parsing, and database programming are presented: each example requires a linear, rather than intuitionistic, notion of context to be modeled adequately.<<ETX>>
8816413
Uses of Higher-Order Unification for Implementing Program Transformers
Source-to-source program transformers belong to the class of meta-programs that manipulate programs as objects. It has previously been argued that a higher-order extension of Prolog, such as λProlog, makes a suitable implementation language for such meta-programs. In this paper, we consider this claim in more detail. In λProlog, object-level programs and program schemata can be represented using simply typed λ-terms and higher-order (functional) variables. Unification of these λ-terms, called higher-order unification, can elegantly describe several important meta-level operations on programs. We detail some properties of higher-order unification that make it suitable for analyzing program structures. We then present (in λProlog) the specification of several simple program transformers together with a more involved partial evaluator. With the depth-first control strategy of λProlog for both clause selection and unifier selection all the above mentioned specifications can be and have been executed and tested. Comments University of Pennsylvania Department of Computer and Information Science Technical Report No. MSCIS-88-46. This technical report is available at ScholarlyCommons: http://repository.upenn.edu/cis_reports/698 USES OF HIGHER-ORDER UNIFICATION FOR IMPLEMENTING PROGRAM TRANSFORMERS JohnHannan Dale Miller MS-CIS-88-46 LlNC LAB 118 Department of Computer and Information Science School of Engineering and Applied Science University of Pennsylvania Philadelphia, PA 19104
14544430
Specifying Theorem Provers in a Higher-Order Logic Programming Language
Since logic programming systems directly implement search and unification and since these operations are essential for the implementation of most theorem provers, logic programming languages should make ideal implementation languages for theorem provers. We shall argue that this is indeed the case if the logic programming language is extended in several ways. We present an extended logic programming language where first-order terms are replaced with simply-typed λ-terms, higher-order unification replaces first-order unification, and implication and universal quantification are allowed in queries and the bodies of clauses. This language naturally specifies inference rules for various proof systems. The primitive search operations required to search for proofs generally have very simple implementations using the logical connectives of this extended logic programming language. Higher-order unification, which provides sophisticated pattern matching on formulas and proofs, can be used to determine when and at what instance an inference rule can be employed in the search for a proof. Tactics and tacticals, which provide a framework for high-level control over search, can also be directly implemented in this extended language. The theorem provers presented in this paper have been implemented in the higher-order logic programming language λProlog.
5278164
A Logic Programming Approach to Manipulating Formulas and Programs
By permitting function and predicate symbols to be variables and by replacing first-order terms by simply typed $lambda$-terms, a higher-order extension to first-order Horn clauses can be described. To be complete in principle, a logic programming language based on this extension must incorporate higher-order unification. Although this is a more complex operation than first-order unification, its availability as a primitive makes certain kinds of programming tasks easier. We illustrate this aspect in the paper by presenting some programs in a higher-order version of Prolog called $\lambda$Prolog that manipulate objects, such as formulas and programs, whose representation requires structures containing abstractions or bound variables. Specifically, we show (a) how a simple natural deduction theorem prover may be implemented in $\lambda$Prolog, and (b) how some simple program transformers for a functional programming language may be written in this language. These programs exploit the availability of $\lambda$-conversion and higher-order unification in $\lambda$Prolog to provide elegant solutions to several awkward problems inherent in these tasks. We contend that programs which perform similar tasks but which are written in languages without these features would, at least, be much less perspicuous.
10134130
A Congruence Format for Name-passing Calculi
We define and use a SOS-based framework to specify the transition systems of calculi with name-passing properties. This setting uses proof-theoretic tools to take care of some of the difficulties specific to name-binding and make them easier to handle in proofs. The contribution of this paper is the presentation of a format that ensures that open bisimilarity is a congruence for calculi specified within this framework, extending the well-known tyft/tyxt format to the case of name-binding and name-passing. We apply this result to the @p-calculus in both its late and early semantics.
32145280
Logical foundations for open system design
18083854
Attitude and Position Control Using Real-Time Color Tracking
A variety of sensors and positioning methods have been developed over the years. Most methods rely on active sensors (such as sonars or lasers) which have range and power restrictions, or rely on computationally complex (and often slow) methods such as recovering position from stereo or optical flow. This paper describes a system that can determine a robot's position and orientation, in all six degrees of freedom, relative to a simple passive target. The system can determine its position relative to the target from a single image frame, and process the image and calculate the position faster than a camera's frame rate (60Hz). It uses a standard, uncalibrated color video camera as its sensor. The system runs on an inexpensive microprocessor (a Motorola 68332) leaving many cycles left over. By careful design of the target and the vision processing hardware and software, we are able to selectively perceive only the relevant parts of the target, greatly simplifying and speeding all the necessary computations. The system is being developed for autonomous spacecraft station keeping and docking.
13298925
Collection analysis for Horn clause programs
We consider approximating data structures with collections of the items that they contain. For examples, lists, binary trees, tuples, etc, can be approximated by sets or multisets of the items within them. Such approximations can be used to provide partial correctness properties of logic programs. For example, one might wish to specify than whenever the atom sort(t,s) is proved then the two lists t and s contain the same multiset of items (that is, s is a permutation of t). If sorting removes duplicates, then one would like to infer that the sets of items underlying t and s are the same. Such results could be useful to have if they can be determined statically and automatically. We present a scheme by which such collection analysis can be structured and automated. Central to this scheme is the use of linear logic as a computational logic underlying the logic of Horn clauses
27771874
Combined Learning and Use for a Mixture Model Equivalent to the RBF Classifier
We show that the decision function of a radial basis function (RBF) classifier is equivalent in form to the Bayes-optimal discriminant associated with a special kind of mixture-based statistical model. The relevant mixture model is a type of mixture-of-experts model for which class labels, like continuous-valued features, are assumed to have been generated randomly, conditional on the mixture component of origin. The new interpretation shows that RBF classifiers effectively assume a probability model, which, moreover, is easily determined given the designed RBF. This interpretation also suggests a statistical learning objective as an alternative to standard methods for designing the RBF-equivalent models. The statistical objective is especially useful for incorporating unlabeled data to enhance learning. Finally, it is observed that any new data to classify are simply additional unlabeled data. Thus, we suggest a combined learning and use paradigm, to be invoked whenever there are new data to classify.
6001799
Limit to the Bit-Rate Capacity of Electrical Interconnects from the Aspect Ratio of the System Architecture
We show that there is a limit to the total number of bits per second,B, of information that can flow in a simple digital electrical interconnection that is set only by the ratio of the lengthlof the interconnection to the total cross-sectional dimensionAof the interconnect wiring?the “aspect ratio” of the interconnection. This limit is largely independent of the details of the design of the electrical lines. The limit is approximatelyB~BoA/l2bits/s, withBo~ 1015(bit/s) for high-performance strip lines and cables, ~1016for small on-chip lines, and ~1017?1018for equalized lines. Because the limit is scale-invariant, neither growing nor shrinking the system substantially changes the limit. Exceeding this limit requires techniques such as repeatering, coding, and multilevel modulation. Such a limit will become a problem as machines approach Tb/s information bandwidths. The limit will particularly affect architectures in which one processor must talk reasonably directly with many others. We argue that optical interconnects can solve this problem since they avoid the resistive loss physics that gives this limit.
16186126
Representing and Reasoning with Operational Semantics
The operational semantics of programming and specification languages is often presented via inference rules and these can generally be mapped into logic programming-like clauses. Such logical encodings of operational semantics can be surprisingly declarative if one uses logics that directly account for term-level bindings and for resources, such as are found in linear logic. Traditional theorem proving techniques, such as unification and backtracking search, can then be applied to animate operational semantic specifications. Of course, one wishes to go a step further than animation: using logic to encode computation should facilitate formal reasoning directly with semantic specifications. We outline an approach to reasoning about logic specifications that involves viewing logic specifications as theories in an object-logic and then using a meta-logic to reason about properties of those object-logic theories. We motivate the principal design goals of a particular meta-logic that has been built for that purpose.