Biductive Computing: Several Variants of a Universal Paradigm

This assignment allows students to practice with logic programming and constraint programming in Prolog using a paradigm we call “biductive computing.” Traditional imperative languages like Java and Python may be thought of as “deductive computing,” i.e., computing answers (outputs) from arguments (inputs). Abductive computing describes the reverse: computing inputs from outputs, such as diagnosing a disease from symptoms. Because Prolog does not distinguish input arguments from output answers, it naturally supports both deductive and abductive computing paradigms. A program that mixes both paradigms could be called a biductive program. Prolog supports biductive computing by allowing arguments to be fully or partially variable. Prolog’s computational model proceeds to search for values for the variables so that the logical or mathematical relationships among the arguments hold true.

For example, deductive computing could compute a student’s GPA given her course grades using a simple mathematical formula. An abductive version of this logic could compute the grades she would need to achieve a certain GPA, i.e., reasoning backwards from desired GPA to course grades. Biductive computing describes the case where some course grades are known or limited to a range (e.g., the student cannot achieve higher than a B in a certain course) and the desired GPA is limited to a range (e.g., above 3.5). Prolog can search for all solutions that meet these constraints.

This model AI assignment includes four variants of biductive computing: database querying, planning, parsing, and probabilistic reasoning.

Across the four variants of this assignment, several AI topics are covered: logic reasoning including deduction and abduction; logic programming and constraint programming; planning; parsing; and probabilistic reasoning.

This assignment may be used in an introductory AI course. Depending on the assignment variant, prior experience with formal reasoning, parsing, or probabilistic reasoning may be required. We recommend one or two weeks of introductory Prolog material before engaging with the biductive computing assignment. An exception to this recommendation is that the database querying variant may serve as a first assignment in Prolog.

Each variant of this assignment may be more or less challenging depending on how much support code is provided to students and which kinds of features they are asked to implement. Each variant lists several features of varying difficulty in order to allow educators to customize the assignment.

Prolog programs written in a biductive computing style are susceptible to time-consuming depth-first search. Special care is required to avoid infinite or deep recursive search and combinatorial explosions of answers. We note in the assignment descriptions where these issues may arise. Biductive computing serves as a good introduction to issues around combinatorial search, NP-hardness, and ordering of constraints in constraint programming.

This assignment provides opportunities for students to practice logic programming and constraint programming. Depending on the variant, it also introduces planning, parsing, and probabilistic reasoning. The assignment may also be customized for difficulty.

Biductive computing is new to most students. In our experience, students are surprised to see “reversible computing” and excited to learn how to take advantage of the paradigm. Our solution to each variant of this assignment requires 50 to 150 lines of code; in a general purpose imperative language, significantly more code would be required to accomplish the same tasks, and the code would obscure the fundamental logical relationships and constraints of the problem domain. Although Prolog can be tricky, usually the solution is compact and elegant. Students who enjoy problem solving and puzzles may be especially interested in this assignment.

We find that Prolog is not an ideal choice for certain large applications. For example, efficient planning may be best accomplished with heuristic search instead of Prolog's default depth-first search. Prolog may be coded in such a manner to realize any algorithm, but doing so is sometimes more trouble than it is worth. It is important to note, however, that classical planning finds an answer to the question, “how should these actions be sequenced to transform the initial state into a specific goal state?” while biductive planning, as detailed in one of this assignment’s variants, can answer the same question as well as, “what are all possible initial states for which there exists a plan that achieves any of several goals?”

Likewise, Prolog parsing supports context-sensitive grammars but is not specifically optimized for context-free grammars. Specifically, Prolog’s definite clause grammars (DCGs) perform recursive descent with backtracking while building a parse tree, while a deterministic LR parser can handle context-free grammars in time linear to the input size. LR parsers cannot, however, be used in a biductive paradigm, i.e., cannot produce input strings whose parse trees meet certain constraints. We note that DCGs cannot be used for (unbounded) left-recursive grammars, and when used in a biductive context, also cannot handle unbounded right-recursive grammars. Extra care is required to limit the grammar’s recursive depth, both left and right, using logical or mathematical constraints. These issues and workarounds are addressed in our background material on parsing.

The open source SWI-Prolog with its CLP library is sufficient to complete all variants of this assignment. The commerical SICStus Prolog may be used instead. Both are available for all major operating systems. We found that caching intermediate results, known as "tabling," was an effective optimization. A tabling library is available for both SWI-Prolog and SICStus in their standard distributions. ProbLog is used for the probabilistic reasoning variant of the assignment. ProbLog is open source and only requires a Python environment.

This assignment includes four variants:

Database querying: Using a Pokémon dataset transformed into Prolog facts, students are asked to write rules and queries to find Pokémon that have certain properties or certain relationships to other Pokémon. This variant may be used as an introduction to writing Prolog rules and queries.

Planning: Given a set of courses and their prerequisites, a set of courses required to graduate, and a sequence of eight blank semesters covering four years, students are asked to write a course planner that identifies which semester to take each course. The biductive use case of this variant supports arbitrary restrictions such as a study-abroad semester and course offering constraints (e.g., every other year), and is able to produce all satisfying schedules.

Parsing: Students are asked to implement a parser in the form of a definite clause grammar that represents knitting patterns. For example, the string, “k1, p1, * k2, p2; rep from * 5 times.” describes a row of knitting that has one knit, one purl, and then two knits and two purls repeating five times. Given such a string, a visual diagram may be constructed representing the knits and purls. Students are asked to support the biductive use case, i.e., both generating the diagram from a pattern string and generating a pattern string from a diagram.

Probabilistic reasoning: Using ProbLog, students are asked to represent the evidence, testimony, and relevant logical and physical constraints of a homicide case. Judicial reasoning is a good case for biductive reasoning because it often involves considering, “did the suspect commit the crime?” as well as, “who else could have committed the crime?” ProbLog allows us to include probabilities for various facts and relations and to explicitly label certain facts as evidence. ProbLog supports most Prolog syntax so non-probabilistic logical and physical constraints may be mixed in with probabilistic knowledge.