Horn Clauses

are used in Logic programming.  Such as PROLOG.

In a logic language such as Prolog, you give the interpreter a number of logical statements and ask it to deduce the thing you want.  It uses an internal algorithm a "logic engine" to derive new Horn clauses.  The logic is limited; you don't have the power that you have in first-order logic.  (In particular,  you don't use such terms as "there exists" or "not".)  And even so, the logic engine isn't always that hot, and so you have kind of feel for how to structure your Horn clauses so that the logic engine will give you an answer in a reasonable amount of time.

An example I give is sorting.  I use the Horn clauses to define what it means to be sorted.  And then I give it an unsorted list and let Prolog have at it.  And we wait and wait and wait while it tries every combination until it finds a sorted one because I didn't think very carefully about my Horn clauses.  Then I redefine what it means to be sorted, using a definition that looks an awful lot like Merge Sort and then the logic engine sorts it using Merge Sort.

If we already have a successor function:  s(x) gives you the next integer after x.

Then we can define sum like this.

sum (0,y,y).

sum (s(x),y,s(z)) :- sum(x,y,z).

sum (27,32,x)?  Prolog would the axioms to derive statements until it was able to derive sum(27,32,59) and then it would report that x had to be 59.

We might have a set of facts.

arc (a,b).
arc (a,c).
arc (b,c).

So, what does it mean for there to be a "path" from x to y.

path(x,y) :- arc (x,y).
path(x,y) :- arc (x,z),path(z,y).


C:-A.
C:-B.

You're really saying (A v B) ==> C.



arc (a,b).
arc (b,c).

path(x,y) :- arc (x,y).
path(x,y) :- arc (x,z),path(z,y).

arc(a,b)
________
path(a,b)


arc (b,c)
_________
path (b,c)

These derived facts get added to our list of facts.

arc (a,b).
arc (b,c).
path (a,b).
path (b,c).

arc (a,b),path(b,c)
__________________
path(a,c)



The book then starts talking a made-up language called IMP.  (meaning IMPERATIVE).

Imperative languages have explicit commands called statements.  You can make advanced programs by combining statements in three primary ways:

You can concatenate statements:  stmt1; stmt2

You can combine statements in a conditional:  if (cond) stmt1 else stmt2

You can put a statement in a loop:  while (cond) stmt;

(I tend to define loops like this:
  repeat stmt1; until (cond) stmt2;

In other words, I put the test in the middle of the loop rather than at the beginning or end as this easily emulates both pre-condition and post-condition loops.

Pascal had something called repeat (stuff) until (cond).  The stuff always ran at least once.  If you wanted to consider the situation where stuff didn't run at all, and, for some reason, you were allergic to while loops, you could do it like this.  if (cond) repeat (stuff) until (cond).

Common situation for mid-condition loops.  File systems don't know that you've reached EOF until you attempt to read beyond it and fail.

while (true) {
 Read from file
 if (file.eof()) break;
 Do stuff
}

Looking for flag is a basic mid-condition loop program
while (true) {
 Read data
 if (data)=="end of data flag" break;
 Process data
}

The other major language type is FUNCTIONAL.

Rather than define programs with a series of statements (or steps), you define your program as a function, as a composition of other functions.
LISP, SCHEME.

IMPERATIVE
==> BRANCHED - you tell it explicitly where in the program to go.
    BASIC



==> STRUCTURED - It has ifs and loops.
   Pascal, C, C++, Java, Python


BASIC:

10 LET I = 1
20 IF (I > 10) THEN GOTO 60 !Conditional branch
30 PRINT I
40 LET I = I+1
50 GOTO 20 !Unconditional branch
60 END

Syntax means whether a program in the language is valid.  "Does it compile?"

Semantics is more like "What does the program do?"

MATHEMATICALLY, SIGMA is the set of all possible mappings from memory locations to integers.

For example:  x contains 5.  y contains -3.  All other memory locations contain 0.  This is a mapping from memory locations to integers.

SIGMA is a set that contains all such mappings.

sigma represents one specific mapping.  The semantics of this language are defined by what happens in memory.

sigma (5/x)    represents the mapping that sets x to 5, and otherwise agrees with sigma.