Logical Programming

11:35 Horn Clause

A Horn clause is a way of formulating logical statements. It was named after Alfred Horn. He was the first to recognize their significance.

“If you pass in the same values you always get the same results, it doesn’t have side effects.”

It is a clause or disjunction of literals, or a set of alternatives, with at most one positive literal. A dual-Horn clause contains at most one negated literal. A literal is an atomic formula that is referentially transparent (replaceable with corresponding value). Definite clauses are Horn clauses with no negative literals.

Clauses are written in an if/then format. It can be If A And B Then C. Or it can be If Not A Or Not B Then Not C. This will come up in the control side of logical algorithms.

13:55 Declarative Programming

“This is what states what is going to happen.”

Declarative programming is a paradigm that states the logical computation. It doesn’t describe the actual flow through the computations. Declarative programming focuses on the end result. Emphasis is on what you are getting from it. The how is irrelevant. It also lacks side effects and is referentially transparent.

Imperative programming on the other hand goes through the flow. It describes the actual flow through the computations. It uses statements that change a programs state. Imperative programming focuses on how the result is obtained.

“You don’t want to call a function and have it mess something up so that the next time you call it it changes the result.”

Declarative programming is an overarching term that describes several paradigms. Modelling is a paradigm that represents physical systems in declarative code. Equations declare behavior and relationships. Mathematical calculations are used to algebraically manipulate and find solutions. Languages include Analytica, Modelica, and Simile.

Constraint programming sets the relationship between variables by use of constraints on the variables. Constraints don’t specify how solutions are obtained. Instead they set the properties of the solution stating what is being looked for by the code. In the refinement model variables are not initially assigned but assumed to be anything within the range of the variable. In the perturbation model variables are assigned a single value that can be changed.

Markup languages such as HTML, XAML, etc are usually declarative. HTML only describes what should be on the webpage not it’s control flow.

21:10 Control Flow

Control flow is the order that statements or function calls are evaluated in a program. A control flow statement is one that results in a choice between multiple paths the code could take. These are the decision making statements in code. A block groups and defines the scope of a set of control flow statements.

“You can write crappy BASIC in any language you like.”

Control flow statements are categorized by the effect that have on the flow through the code. A branch is an instruction that causes the app to execute different code than the default. An unconditional branch or a jump is the continuation of flow at a different statement or place in the code. A conditional branch executes a block of code only if a condition is met. This includes things like `if` statements that only look at the code if the conditional is true. It can also be loops that execute until a condition is met. Subroutines, coroutines, and continuations execute a block of code then return the control to the caller. An unconditional halt stops the app.

In some languages like JavaScript you have truthy and falsy statements. These either evaluate to true or false when put into a conditional. You have to be careful not to confuse the primitive boolean value with the value in a Boolean object. So if you set b = false then evaluate b it will return true because the condition is evaluating the object not the value in it.

25:15 Problem solving

At the most atomic level (no variables) logic programming uses backward reasoning to create an and-or tree. This creates a space for the program or app to come up with a solution. And-Or trees reduce problems to conjuctions (And) and disjunctions (Or) of subproblems.

“So it’s essentially making an expression tree with a limited operating set.”

Given any node in the tree and any clause whose head matches the node, there exists a set of child nodes corresponding to the sub-goals in the body of the clause. Child nodes are grouped by the And. Alternative solutions and children are grouped by an Or.

Backtracking is used to calculate results. It checks each like for true/false values. Passes on to the next line, even if the previous line errors.

Different backtracking strategies may be used to find a solution to a given problem. Prolog uses a last-in-first-out strategy. Intelligent backtracking and best-first are other strategies used. Concurrent logic programming chooses the most highly or sufficiently instantiated sub-goal.

28:55 Negation As Failure (NAF)

Negation as failure is a non-monotonic inference rule. Non-monotonic logic allows for the creating of tentative conclusions. These conclusions may be removed or changed based on further evidence. It allows state changes.

“It’s almost a way of short cutting that expression tree.”

In formal logic adding a formula to a theory will not reduce the set of consequences of that theory. Abductive reasoning derives the most likely explanation from the known facts. This is a starting point for monotonic logic. More facts may change the conclusion of the abductive reasoning.

“It’s basically stereotyping.”

Negation as failure is used to figure out what something (variable, parameter, function, etc) cannot have as a value by the failure to get that thing. Not x from the failure to derive x. This does not mean the logical negative of x (-x).

In logic it applies by looking at the result of a function and applying control logic if it is negative. It is used in a conditional to say branch if this is not the case. It can also be used to state that a formula or variable is unknown.

33:20 Functional vs Logical

Both are declarative paradigms with a relation to lambda calculus. Lambda calculus uses mathematical logic to express it’s computations. Functional programming is based around lambda calculus.

Logical programming has a few things better than functional. Much easier to maintain. Has fewer errors than other traditional languages. Very good at expressing complex ideas.

“It’s like a mathematical function, it has to return something.”

Functional in turn has a some advantages over logical. Lack of side effects makes understanding functionality easier. The environment is protected from changes in state. It encourages rapid prototyping.

Not everything in logical programming is perfect and is has some disadvantages. It’s not widely used or popular so finding help is difficult. Also the predicates are difficult to read and understand.

Functional programming has it’s own disadvantages not found in logical programming. It can have a negative impact on debugging. Functional programming may not match the way the hardware works. It can be more difficult to learn by those starting out than other paradigms.