Problem Solved! Using Logic Programming to Find Answers

by Gavin McGimpsey

In the video "Problem Solved! Using Logic Programming to Find Answers," Gavin McGimpsey introduces viewers to the concept and advantages of logic programming, particularly in the context of Ruby. He begins with his personal background, emphasizing his journey from law school test preparation to programming and problem-solving through logic. McGimpsey defines logic programming as a methodology that allows programmers to express relations and constraints, empowering them to solve problems with incomplete information. Throughout the talk, he highlights several vital concepts and examples:

Introduction to Logic Programming: The presentation introduces logic programming as a paradigm that originated from artificial intelligence, emphasizing its declarative nature, which allows users to specify what they want without detailing how to achieve it.
Key Features of Logic Programming: McGimpsey notes three primary characteristics: declarative programming (hiding underlying processes), expressing relationships between entities, and facilitating inference.
Illustrative Examples: He discusses the Atbash cipher to demonstrate declarative programming in Ruby, showing how it simplifies complex operations by focusing on the intended outcome rather than the operational details.
Relational Thinking: He contrasts functional thinking with relational thinking, using mathematics to explain how logic programming can reframe how problems are understood and solved. He employs SQL as an example of declarative relationships but points out its limitations in making inferences.
Problem-Solving Strategies: McGimpsey explains the N-Queens problem, showcasing various problem-solving strategies, including constraint propagation, depth-first search, and backtracking, alongside the Sudoku problem as a practical example of constraint processing.
Logic Programming in Ruby: He presents his development of a Ruby library for logic programming, named 'Russell,' which intends to make logic programming more accessible and embedded within Ruby, facilitating solutions to complex constraints.
Applications of Logic Programming: Examples are given, such as Prolog's use in expert systems and IBM's Watson, as well as creative applications like music generation through logic programming.

In conclusion, McGimpsey encourages programmers to explore logic programming, experiment with writing logic-based solvers, and utilize existing libraries or create their own. He emphasizes the significance of understanding logic programming as a powerful approach to abstraction and problem-solving in programming.

00:00:15.120 Hello everyone, my name is Gavin McGimpsey, and today I’m going to introduce you to logic programming.

00:00:21.820 I just reactivated my Twitter account, so if you want to tweet at me, feel free, and I'll try to respond eventually.

00:00:27.390 You can tweet questions at me instead of sending an email if you'd prefer. How many of you have heard of logic programming?

00:00:33.340 Please raise your hand if you've used a logic programming language in-depth. Okay, so this is mostly an introduction to what logic programming offers and some discussion about Ruby options in this context.

00:00:42.340 And if you haven't heard about it, that's okay because I hadn't really either until I started preparing for this talk.

00:00:48.390 It turns out that having some pressure on you is a great way to learn something new.

00:00:55.030 Before we dive into logic programming itself, let me give you a little background on why I'm interested in this topic. For the last few years, I have been traveling around the country teaching people how to prepare for the law school admissions test.

00:01:11.590 I used to think I wanted to be a lawyer, but then I discovered there are few happy lawyers, and I decided to take a different direction. It has been refreshing to wander around and do this sort of thing.

00:01:24.010 If you've studied LSAT problems, you might have encountered logic games, which involve figuring out a little puzzle like this. You are given a set of variables and their relationships, and you have to deduce what must be true, what could be true, or what cannot be true with the information given.

00:01:45.700 Prior to this, I spent a year playing bridge full-time. For those who are familiar, bridge is a fantastic card game. I even brought some cards after this session if anyone's interested.

00:02:11.560 If you're a programmer, you will likely find bridge appealing.

00:02:16.900 There's a problem-solving aspect where you must work with incomplete information, trying to decipher what's happening at the table. A big part of that is sharing information with your partner and also figuring out what your opponents hold.

00:02:33.680 After traveling around the country for bridge tournaments, I ended up being the top-ranked rookie in North America that year. While not incredible, it was a solid achievement for a beginner.

00:02:39.980 Bridge is a game that grabs you because every five minutes, you have a new puzzle to solve. I recommend looking into it if that appeals to you. The same interests that captured me during LSAT problems and bridge are also what draw me to programming and problem-solving.

00:03:12.650 My first programming language was Logo, and my first object-oriented programming experience was in HyperCard for Mac, a long time ago. I've since moved on to larger and better things, primarily Ruby, which is excellent for expressing problems clearly.

00:03:33.070 What inspires me about programming, and particularly about logic programming, is that I view programming as a project where we communicate with the computer to get the answers we need.

00:03:51.050 When I think about programming, I envision solving a variety of problems and creating machines that can solve puzzles, model the world, or even create music. I equate programming with artificial intelligence since, ideally, we are encoding the intelligence of ourselves and our teams into something that others can use.

00:04:16.820 Today, we're diving into how logic programming puts this artificial intelligence in your hands as programmers. In essence, logic programming languages originated from artificial intelligence efforts in the 60s and 70s.

00:04:30.080 These language approaches are exceptionally suited for various problems, allowing us to delegate much of the problem-solving work to the computer.

00:04:56.010 Let’s get into logic programming. As mentioned, logic programming involves transferring much of the problem-solving responsibility to the language or software. Typically, we discuss logic programming languages as either standalone languages, like Prolog, or embedded languages within a host language, such as mini-Cameron.

00:05:19.170 Logic programming languages generally have three key features: they are declarative, they express relationships between entities, and they allow us to make inferences. The point is that they enable us to fill in the gaps and solve problems by handing the work over to the computer.

00:05:45.180 Declarative programming is about hiding the underlying processes. Let's look at a coding exercise that you might encounter on platforms like Exercism. The Atbash cipher is a straightforward text cipher.

00:06:09.960 We take a string of text, keep letters and numbers, drop punctuation, swap alphabet positions (A↔Z, B↔Y, etc.), and convert it to lowercase while breaking it into five-character words. For example, 'rubyconf 2016' becomes an encoded string.

00:06:42.360 Ruby simplifies many tasks, including this cipher. Declarative programming in Ruby takes much of the burden off our shoulders by allowing us to express our intentions without worrying about the underlying implementation.

00:07:02.000 We can encode a string by filtering characters to keep letters and numbers, passing them through our key, and converting them to lowercase before chunking them into five-character words. Ruby offers a clean interface to abstract the looping we would typically have to write manually.

00:07:37.080 This approach exemplifies being declarative, as it allows us to express 'here's what I want' without caring about how to accomplish it. Declarative programming exists on a spectrum; the more declarative we are, the less process we reveal.

00:08:07.560 Rails' 'has_many' association is a perfect illustration of this declarative nature. It's a straightforward statement: 'This thing has many of those,' and Rails manages all underlying database-level interactions.

00:08:37.560 Logic programs possess the declarative feature that allows us to take our hands off problem-solving and simply specify our needs. If you're following along, you can guess what I will discuss next: relational thinking.

00:09:05.480 This next part may be awkward for those without a math background, as relations frequently appear in mathematics. When we talk about relations, we refer to categories or types and define how they fit together, including individual data that aligns according to established rules.

00:09:43.520 Here's a simple problem: What is 42 minus 18? This sounds simple and can be computed using any programming language. However, let me pose a different question: why can't we just ask the computer 'What is 18 plus ?' We end up with a convoluted response.

00:10:12.230 This scenario illustrates function-based thinking, where we have inputs that get processed to produce an output. On the other hand, a relation operates with what we already know. If we have enough information about summation, we can determine the inputs or outputs flexibly.

00:10:41.440 Logic programming languages provide us with this relational capability, enabling the computer to trace how inputs and outputs relate and determine results based on the data it possesses.

00:11:02.380 You might be familiar with SQL, which exemplifies a declarative relational tool where we define various data types and their interrelations through tables, declaring facts when we add data, and relying on the server to handle the queries.

00:11:16.050 However, where SQL falls short is filling in the gaps, that inference we desire from logic programming—taking any input or output and deducing how they connect.

00:11:37.970 Now, let’s explore problem-solving strategies, exemplified by the N-Queens problem that emerged in the mid-1800s. This challenge involves arranging queens on an NxN chessboard so they do not threaten each other.

00:12:03.640 Various methods apply similar approaches; one could pick a square, place a queen, and observe the results while blocking off affected squares until a solution is found or you backtrack from an impasse.

00:12:31.500 There are different ways to tackle the N-Queens problem, such as breadth-first or depth-first searches, backtracking, and similar explorations discussed by Dijkstra in his 1970s paper.

00:12:54.220 This problem-solving process represents a chance for abstraction, specifically in constraint processing or propagation, repeatedly applying rules until we reach a fixed point.

00:13:15.350 Such constraints in the N-Queens case involve eliminating squares under attack by the queens and ensuring that, if one square is the only viable option in a row or column, we place the queen there.

00:13:48.500 Once an impasse is encountered, we branch out and conduct a more brute-force search by picking another square to place a queen, continue until acquiring a solution.

00:14:17.680 Visually, once our queen is placed, we eliminate all the squares it can threaten. When there are no possible placements left based solely on the established rules, we must branch out and try affecting different rows or columns.

00:14:53.710 As we branch out, we can again apply constraint propagation, exciting new squares that are now indirectly threatened by the queen's placement. We can continue this process of eliminating possibilities until we secure a solution, offering a more strategic approach than brute force, especially as the grid size increases.

00:15:46.550 A related problem that benefitted from constraint propagation techniques is Sudoku. The common 9x9 grid must be filled with numbers from 1 to 9 without any repeats in rows, columns, or boxes. Brute-force may work for small grids, but as information reduces, the complexity rapidly escalates.

00:16:07.960 Constraint propagation applies to Sudoku since we can convert the game rules into specific constraints to enforce repeatedly. As soon as we can identify a placement for a single number, such as in the upper right square where available spaces diminish, we remove other possibilities, narrowing down our approach.

00:16:45.440 This needs repeated application of rules until we arrive at a solution. This elegant code by Peter Norvig demonstrates constraint propagation for solving Sudoku, which can be compact yet effective.

00:17:03.350 However, logic programming can enhance this process, and there are various libraries in Ruby that facilitate logic programming, although many are just translations of traditional logic programming languages, such as Prolog and mini-Cameron, originally developed in Scheme.

00:17:25.740 I've been working on a logic programming library that I tentatively named Russell, aiming to promote problem-solving autonomy while maintaining a Ruby feel.

00:17:51.360 We can look at how to solve Sudoku using Russell. The core solution can be elegantly simplified without diving into the setup of the data structures, I/O, or visual outputs. The logic programming engine can manage this.

00:18:15.750 We can define constraints directly without worrying about the underlying structures used to represent Sudoku. For initializing, each square must hold a digit from one to nine.

00:18:32.460 Then, we can assert that each row, column, and square contains unique contents by claiming that all the digits from one to nine must be included.

00:18:58.770 All we have to do is tell the logic solver about our constraints and existing values, such as square A1 being five, and square B1 being one. Once declared, the solver will proceed to find a resolution.

00:19:15.990 This illustrates the promise of logic programming, aiding us in breaking down puzzles or problems with unknown inputs into known output states, inversely turning outputs into inputs for a different solve.

00:19:46.500 One key advantage of a robust logic programming library is the ability to create custom relations. In our examples, we have encountered assertions like 'equal' or 'has unique contents' based on simple logical building blocks.

00:20:05.120 This concept, known as functional completeness, indicates that with a few simple logical operators, we can construct nearly any larger relation we require.

00:20:31.520 For example, asserting unique contents in a collection requires stating that no two values can be identical, providing a clear basis for our constraints.

00:20:50.240 Similarly, constraints defining that a collection must only contain one specific item can be expressed as ensuring this member exists while the others do not.

00:21:10.340 This extensibility ensures that if no built-in functions address our specific needs, we can develop custom solutions using existing constraints as building blocks.

00:21:45.860 If you're not interested in implementing a logic programming library, this may hold less significance to you. However, if you are interested, I found scant resources on this topic that are even slightly approachable.

00:22:11.560 The core of most logic programming engines relies on something called unification, a form of pattern matching using knowledge structures stored within the solver, essentially acting as two-way pattern matching.

00:22:45.340 For instance, if we have two arrays and want them to concatenate into a third one, the unification process examines each component and matches them piece by piece.

00:23:09.560 The system keeps track of stored knowledge, allowing for queries as additional information is introduced over time.

00:23:26.280 This knowledge storage is straightforward; when we assert that a variable matches a value, it stores this relationship and can infer outcomes based on earlier assertions.

00:23:51.060 The algorithm is powerful, likened to a carpenter who has only a buzzsaw to work with—robust but a bit tricky.

00:24:08.240 When working with relations, specifically contrasting unification approaches, we want to ensure that data remains distinct, enabling us to directly query whether they match or do not.

00:24:41.680 If two elements we want to keep distinct would unify, this would invalidate the solution since it contradicts our intent to keep them apart.

00:25:08.920 Once again, if they are previously unknown, we can simply add them to our store as separated knowledge.

00:25:31.890 There are more potential applications for this algorithm, such as checking rules to determine whether one covers another, improving efficiency within logic programming.

00:25:56.940 I'm currently implementing a more straightforward version which suffices for most use cases.

00:26:24.340 Equipped with unification, we can expect this tool to facilitate many tasks in programming by seamlessly extending knowledge based on existing information.

00:26:43.830 For most logic problems you encounter, you'll find assertions create new knowledge or statements asserting relational characteristics help direct outcomes.

00:27:12.050 Now, if you're interested in real-life applications of logic programming, there are Prolog implementations and gems available, but many are outdated or require in-depth knowledge of Prolog.

00:27:48.180 Most of my work approximates an implementation based on mini-Cameron, a practical embedded approach characterized as an elegant Ruby translation of the original Scheme version.

00:28:04.800 Other areas to explore in this field include Boolean solving or other external logic languages like Prolog, Mercury, and PI cat, which emerged recently.

00:28:23.350 When might you want to use logic programming? Typically, we are looking for scenarios where our inputs or variables are constrained and can take on multiple values within limited domains.

00:29:00.780 Applications range from generating possibilities within defined systems to rule enforcement in expert systems. Prolog is famous for being behind airline ticket reservation systems, adept at enforcing fare rules.

00:29:22.700 IBM's Watson, the Jeopardy-playing AI, also employs Prolog for natural language processing, utilizing rules to navigate input queries effectively.

00:29:47.550 A recent interest lies with Oskar Vikram's development of music exercises using the core logic library in Clojure, demonstrating how logic programming can generate creative compositions by setting various musical parameters.

00:30:05.440 This results from clear constraints that can be supplied and addressed by the computer, allowing for interesting outputs in music creation.

00:30:23.350 I would love to see more integrations of logic programming in Ruby similar to how Clojure has embraced this area, aspiring to keep advancing in programming.

00:30:45.560 If you're new to logic programming, I encourage you to experiment by writing an expert system or logic-based solver within your favorite programming environment.

00:31:12.140 Clojure's core logic library is well-developed, providing an excellent foundation, whereas mini-Cameron offers a minimal yet usable option. For Boolean solving, there's also a gem wrapping around a popular Boolean solver.

00:31:31.720 As a reference for your journey into logic programming, documents on programming languages are abundant, and books such as 'The Art of Prolog' offer comprehensive insights into the topic.

00:32:02.400 For constraint processing and propagation detail, mathematical texts can be particularly enlightening, assisting in the conceptual learning of logic applications.

00:32:27.060 Before concluding, I want to highlight sentient-lang.org as an excellent example of how logic programming can be utilized through interactive browser demos.

00:32:55.480 I have no affiliations with them but think it's remarkable, and I hope to develop a blog post to delve deeper into my code and the concepts we've covered.

00:33:10.360 Ultimately, I appreciate your presence here today. Thank you for your attention and interest in logic programming.