Page 80 - DLIS108_INFORMATION_AND_COMMUNICATION_TECHNOLOGY_APPLICATIONS

VED1
e\L-lovely-eng\comm8-1.pmd IInd 16-9-11 IIIrd 22-12-11 IVth 4-1-12

Unit 8: Programming Language: Types and Functions

values of these variables that make a given “conclusion with variables” true. Such a query is
called a “goal”. Notes
• The search strategy: The system looks for rules that “match” the goal, to find rules that can
give conditions under which the initial goal is true. It does this by trying to match the goal to
the head (conclusion) of each rule, and if it fits, the conditions of this rule are new goals.
When all goals have been,reduced to facts, the system has found a way (a set of variables) that
make the original “conclusion with variables” true.
• Logical variables: Can be uninstantiated (uninitialized and the system knows it) or have a
value bound to it (point to a data structure which may contain more logical variables). Also,
two uninstantiated variables can be bound together.
• Goal-head matching: A rule matches a goal when the head of the rule can be unified with the
goal (“it fits”). The result of this unification is the new goal, if it exists. If it does not, the ‘
system backtracks to the latest choice point.
• Unification: A goal and a head can be unified if their names are equal and their parameters
can be unified pair wise. When both parameters are data structures, they can be unified if
their names are equal and their components can be unified pair wise. There is no fundamen-
tal difference between unifying a goal and a head, and unifying two data structures.
• Unification of logical variables: If one is an uninstantiated variable and the other is a data
structure, the variable is bound to the data structure. If both are uninstantiated variables, they
are “bound together”, so that if one gets bound in a later stage, so will the other. If both are
bound to values (data structures) these data structures are unified. These bindings are un-
done when backtracking passes through them while retreating to an earlier choice point.
• Rules describe relations, which work two (or even more) ways. A “pure” Prolog program can
be run from input to all possible outputs but equally well from output to all possible inputs.
• There are several impure features in Prolog which disturb and sometimes destroy the pure
relational nature of logic programming.
• This model is supported by languages such as Prolog, Fril, Visual Prolog, Ciao. Mercury,
Godel, Oz, ALF (Algebraic Logic Functional Programming Languages).

8.6.5 Parallel and Distributed Programming

• Parallel: Multiple CPUs around shared memory. Often the processes all do essentially the
same, possibly even in lock step.
• Distributed: Multiple CPUs in a network. Often the processes do different things and com-
munication times are higher.
• Parallel processes have to communicate. There are two basic methods for this: shared vari-
ables and message passing.
• Shared variables: They need synchronization measures. There is control synchronization (“wait
until the data you need are there”), which waits for some other process to arrive, and mutual
exclusion synchronization (“wait until the data you need are free”) which waits for some
other process to go away. There are locks, semaphores and monitors to do this, in order of
increasing sophistication.
• Locks and semaphores: A semaphore is an integer on which the only actions allowed are
“increase by 1” (V) and “decrease by 1” (P) and which can never become negative. Normally
it is used to represent “the number of items available”. If a P operation would make the sema-
phore negative if allowed to run to completion, the attempting process is suspended, and will
be released as soon as somebody else does a V operation. In the long run there must be equally

LOVELY PROFESSIONAL UNIVERSITY 75