B-Prolog was a high-performance implementation of the standard Prolog language with several extended features including matching clauses, action rules for event handling, finite-domain constraint solving, arrays and hash tables, declarative loops, and tabling. First released in 1994, B-Prolog is now a widely used CLP system. The constraint solver of B-Prolog was ranked top in two categories in the Second International Solvers Competition,[1] and it also took the second place in P class in the second ASP solver competition [2] and the second place overall in the third ASP solver competition.[3] B-Prolog underpins the PRISM system, a logic-based probabilistic reasoning and learning system. B-Prolog is a commercial product, but it can be used for learning and non-profit research purposes free of charge (since version 7.8 for individual users, including commercial individual users, B-Prolog is free of charge [4]). B-Prolog is not anymore actively developed, but it forms the basis for the Picat programming language.
A matching clause is a form of a clause where the determinacy and input/output unifications are denoted explicitly. The compiler translates matching clauses into matching trees and generates indexes for all input arguments. The compilation of matching clauses is much simpler than that of normal Prolog clauses because no complex program analysis or specialization is necessary; and the generated code tends to be more compact and faster. The B-Prolog compiler and most of the library predicates are written in matching clauses.
A matching clause takes the following form:
H,G=>B
where H is an atomic formula, G and B are two sequences of atomic formulas. H is called the head, G the guard, and B the body of the clause. No call in G can bind variables in H and all calls in G must be in-line tests. In other words, the guard must be flat. The following gives an example predicate in matching clauses that merges two sorted lists:
The cons [Y|Ys] occurs in both the head and the body of the third clause. To avoid reconstructing the term, we can rewrite the clause into the following:
The call Ys=[Y|_] in the guard matches Ys against the pattern [Y|_].
Action rules
The lack of a facility for programming "active" sub-goals that can be reactive to the environment has been considered one of the weaknesses of logic programming. To overcome this, B-Prolog provides a simple and yet powerful language, called Action Rules (AR), for programming agents. An agent is a subgoal that can be delayed and can later be activated by events. Each time an agent is activated, some action may be executed. Agents are a more general notion than delay constructs in early Prolog systems and processes in concurrent logic programming languages in the sense that agents can be responsive to various kinds of events including instantiation, domain, time, and user-defined events.
An action rule takes the following
H,G,{E}=>B
where H is a pattern for agents, G is a sequence of conditions on the agents, E is a set of patterns for events that can activate the agents, and B is a sequence of actions performed by the agents when they are activated. When the event pattern E together with the enclosing braces is missing, an action rule degenerates into a matching clause.
A set of built-in events is provided for programming constraint propagators and interactive graphical user interfaces. For example, ins(X) is an event that is posted when the variable X is instantiated. A user program can create and post its own events and define agents to handle them. A user-defined event takes the form of event(X,O) where X is a variable, called a suspension variable, that connects the event with its handling agents, and O is a Prolog term that contains the information to be transmitted to the agents. The built-in post(E) posts the event E.
outputs the message hello followed by world. The agent ping(T) responds to time events from the timer T. Each time it receives a time event, it prints the message ping. For example,
?-timer(T,1000),ping(T),repeat,fail.
creates a timer that posts a time event every second and creates an agent ping(T) to respond to the events. The loop after the agent is needed to make the agent perpetual.
AR has been found useful for programming simple concurrency, implementing constraint propagators, and developing interactive graphical user interfaces. It has served as an intermediate language for compiling Constraint Handling Rules (CHR) and Answer Set Programs (ASP).
CLP(FD)
Like many Prolog-based finite-domain constraint solvers, B-Prolog's finite-domain solver was heavily influenced by the CHIP system. The first fully-fledged solver was released with B-Prolog version 2.1 in March 1997. That solver was implemented in an early version of AR, called delay clauses. During the past decade, the implementation language AR has been extended to support a rich class of domain events (ins(X),bound(X),dom(X,E), and dom_any(X,E)) for programming constraint propagators and the system has been enriched with new domains (Boolean, trees, and finite sets), global constraints, and specialized fast constraint propagators. Recently, the two built-ins in/2 and notin/2 have been extended to allow positive and negative table (also called extensional) constraints.
Thanks to the employment of AR as the implementation language, the constraint solving part of B-Prolog is relatively small (3800 lines of Prolog code and 6000 lines of C code, including comments and spaces) but its performance is very competitive. The AR language is open to the user for implementing problem-specific propagators. For example, the following defines a propagator for maintaining arc consistency for the constraint X+Y #= C. Whenever an inner element Ey is excluded from the domain of Y, this propagator is triggered to exclude Ex, the counterpart of Ey, from the domain of X. For the constraint X+Y #= C, we need to generate two propagators, namely, 'X_in_C_Y_ac'(X,Y,C) and 'X_in_C_Y_ac'(Y,X,C), to maintain the arc consistency. In addition to these two propagators, we also need to generate propagators for maintaining interval consistency since no dom(Y,Ey) event is posted if the excluded value happens to be a bound. The constraint needs to be preprocessed to make it arc consistent before the propagators are generated.
In B-Prolog, the maximum arity of a structure is 65535. This entails that a structure can be used as a one-dimensional array, and a multi-dimensional array can be represented as a structure of structures. To facilitate creating arrays, B-Prolog provides a built-in, called new_array(X,Dims), where X must be an uninstantiated variable and Dims a list of positive integers that specifies the dimensions of the array. For example, the call new_array(X,[10,20]) binds X to a two dimensional array whose first dimension has 10 elements and second dimension has 20 elements. All the array elements are initialized to be free variables.
The built-in predicate arg/3 can be used to access array elements, but it requires a temporary variable to store the result, and a chain of calls to access an element of a multi-dimensional array. To facilitate accessing array elements, B-Prolog supports the array subscript notation X[I1,...,In], where X is a structure and each Ii is an integer expression. This common notation for accessing arrays is, however, not part of the standard Prolog syntax. To accommodate this notation, the parser is modified to insert a token ^ between a variable token and [. So, the notation X[I1,...,In] is just a shorthand for X^[I1,...,In]. This notation is interpreted as an array access when it occurs in an arithmetic expression, a constraint, or as an argument of a call to @=/2. In any other context, it is treated as the term itself. The array subscript notation can also be used to access elements of lists. For example, the nth/3 predicate can be defined as follows:
nth(I,L,E):-E@=L[I].
Loops with foreach and list comprehension
Prolog relies on recursion to describe loops. The lack of powerful loop constructs has arguably made Prolog less acceptable to beginners and less productive to experienced programmers because it is often tedious to define small auxiliary recursive predicates for loops. The emergence of constraint programming constructs such as CLP(FD) has further revealed this weakness of Prolog as a modeling language. B-Prolog provides a built-in, called foreach, for iterating over collections and the list comprehension notation for constructing lists.
The foreach built-in has a very simple syntax and semantics. For example,
foreach(Ain[a,b],Iin1..2,write((A,I)))
outputs four tuples (a,1), (a,2), (b,1), and (b,2). Syntactically, foreach is a variable-length call whose last argument specifies a goal to be executed for each combination of values in a sequence of collections. A foreach call may also give a list of variables that are local to each iteration and a list of accumulators that can be used to accumulate values from each iteration. With accumulators, we can use foreach to describe recurrences for computing aggregates. Recurrences have to be read procedurally and thus do not fit well with Prolog. For this reason, we adopt the list comprehension notation from functional languages. A list comprehension is a list whose first element has the functor ':'. A list of this form is interpreted as a list comprehension in calls to @=/2 and arithmetic constraints. For example, the query
X@=[(A,I):Ain[a,b],Iin1..2]
binds X to the list [(a,1),(a,2),(b,1),(b,2)]. A list comprehension is treated as a foreach call with an accumulator in the implementation.
Calls to foreach and list comprehensions are translated into tail-recursive predicates. Therefore, there is no or little penalty of using these constructs compared with using recursion.
The loop constructs considerably enhance the modeling power of CLP(FD). The following gives a program for the N-queens problem in B-Prolog:
where Qi and Qj are declared local to each iteration. The following gives a program for the N-queens problem, which uses a Boolean variable for each square on the board.
bool_queens(N):-new_array(Qs,[N,N]),Vars@=[Qs[I,J]:Iin1..N,Jin1..N],Vars::0..1,foreach(Iin1..N,% one queen in each rowsum([Qs[I,J]:Jin1..N])#=1),foreach(Jin1..N,% one queen in each columnsum([Qs[I,J]:Iin1..N])#=1),foreach(Kin1-N..N-1,% at most one queen in each left-down diagsum([Qs[I,J]:Iin1..N,Jin1..N,I-J=:=K])#=<1),foreach(Kin2..2*N,% at most one queen in each left-up diagsum([Qs[I,J]:Iin1..N,Jin1..N,I+J=:=K])#=<1),labeling(Vars),foreach(Iin1..N,[Row],(Row@=[Qs[I,J]:Jin1..N],writeln(Row))).
Tabling
Tabling has been found increasingly important for not only helping beginners write workable declarative programs but also developing real-world applications such as natural language processing, model checking, and machine learning applications. B-Prolog implements a tabling mechanism, called linear tabling, which is based on iterative computation of looping subgoals rather than suspension of them to compute the fixed points. The PRISM system, which heavily relies on tabling, has been the main driving force for the design and implementation of B-Prolog's tabling system.
The idea of tabling is to memorize the answers to tabled calls and use the answers to resolve subsequent variant calls. In B-Prolog, as in XSB, tabled predicates are declared explicitly by declarations in the following form:
:-tableP1/N1,...,Pk/Nk.
For example, the following tabled predicate defines the transitive closure of a relation as given by edge/2.
With tabling, any query to the program is guaranteed to terminate as long as the term sizes are bounded.
By default, all the arguments of a tabled call are used in variant checking and all answers are tabled for a tabled predicate. B-Prolog supports table modes, which allow the system to use only input arguments in variant checking and table answers selectively. The table mode declaration
:-tablep(M1,...,Mn):C.
instructs the system how to do tabling on p/n, where C, called a cardinality limit, is an integer which limits the number of answers to be tabled, and each Mi is a mode which can be min, max, + (input), or - (output). An argument with the mode min or max is assumed to be output. If the cardinality limit C is 1, it can be omitted with the preceding ':'.
Table modes are very useful for declarative description of dynamic programming problems. For example, the following program encodes the Dijkstra's algorithm for finding a path with the minimum weight between a pair of nodes.
The table mode states that only one path with the minimum weight is tabled for each pair of nodes.
Related Research Articles
Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:
Prolog is a logic programming language that has its origins in artificial intelligence and computational linguistics.
Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular for writing compilers, for programming language research, and for developing theorem provers.
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem-specific branching heuristic.
Oz is a multiparadigm programming language, developed in the Programming Systems Lab at Université catholique de Louvain, for programming language education. It has a canonical textbook: Concepts, Techniques, and Models of Computer Programming.
Curry is a declarative programming language, an implementation of the functional logic programming paradigm, and based on the Haskell language. It merges elements of functional and logic programming, including constraint programming integration.
In computer programming, foreach loop is a control flow statement for traversing items in a collection. foreach is usually used in place of a standard for loop statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages, an iterator, even if implicit, is often used as the means of traversal.
In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article.
Constraint Handling Rules (CHR) is a declarative, rule-based programming language, introduced in 1991 by Thom Frühwirth at the time with European Computer-Industry Research Centre (ECRC) in Munich, Germany. Originally intended for constraint programming, CHR finds applications in grammar induction, type systems, abductive reasoning, multi-agent systems, natural language processing, compilation, scheduling, spatial-temporal reasoning, testing, and verification.
Answer set programming (ASP) is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates.
An Euler diagram is a diagrammatic means of representing sets and their relationships. They are particularly useful for explaining complex hierarchies and overlapping definitions. They are similar to another set diagramming technique, Venn diagrams. Unlike Venn diagrams, which show all possible relations between different sets, the Euler diagram shows only relevant relationships.
ECLiPSe is a software system for the development and deployment of constraint logic programming applications, e.g., in the areas of optimization, planning, scheduling, resource allocation, timetabling, transport, etc. It is also suited for teaching most aspects of combinatorial problem solving, e.g., problem modeling, constraint programming, mathematical programming, and search techniques. It contains constraint solver libraries, a high-level modeling and control language, interfaces to third-party solvers, an integrated development environment and interfaces for embedding into host environments.
A definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. It is closely related to the concept of attribute grammars / affix grammars. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs. They are called definite clause grammars because they represent a grammar as a set of definite clauses in first-order logic.
In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.
Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is A(X,Y):-X+Y>0,B(X),C(Y). In this clause, X+Y>0 is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.
In computer programming, append is the operation for concatenating linked lists or arrays in some high-level programming languages.
Logtalk is an object-oriented logic programming language that extends and leverages the Prolog language with a feature set suitable for programming in the large. It provides support for encapsulation and data hiding, separation of concerns and enhanced code reuse. Logtalk uses standard Prolog syntax with the addition of a few operators and directives.
The syntax and semantics of Prolog, a programming language, are the sets of rules that define how a Prolog program is written and how it is interpreted, respectively. The rules are laid out in ISO standard ISO/IEC 13211 although there are differences in the Prolog implementations.
This article describes the features in the programming language Haskell.
OptimJ is an extension for Java with language support for writing optimization models and abstractions for bulk data processing. The extensions and the proprietary product implementing the extensions were developed by Ateji which went out of business in September 2011. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and application programming tools, and bringing software engineering techniques such as object-orientation and modern IDE support to optimization experts.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
