Meta-elucidation

Presentation Transcript

Meta-translation Artificial Intelligence Programming in Prolog Lecturer: Tim Smith Lecture 17 25/11/04 AIPP Lecture 17: Meta-understanding

Contents Controlling the stream of calculation Representing intelligent connections conjunctions ( P∧Q ) disjunctions ( P∨Q) conjunctive not ¬ ( P∧Q). if.....then....else..... Meta-Interpreters condition/2 remaining to-right mediator ideal to-left translator expansiveness first best-first others AIPP Lecture 17: Meta-understanding

Controlling the stream of calculation Prolog has many inherent predicates and administrators that can be utilized to control how inquiries are demonstrated. In the first place, I will present an arrangement of capacities that can be utilized inside typical Prolog programs then I will demonstrate how these thoughts can be utilized to make Meta-Interpreters. - - - The primary predicate of this sort is call/1 . This takes one contention as an objective (i.e. a solitary term) and checks whether the objective succeeds. |?- call(write('Hello')). Hi? yes Mostly used to call objectives built utilizing =.. , functor/3 and arg/3. AIPP Lecture 17: Meta-translation

A Conjunction of Goals A conjunction of objectives (P ∧ Q) can be assembled by gathering the objectives in round sections . | ?- X = ( Y=[a,b,f,g], member(f,Y) ) , call(X). X = [a,b,f,g]=[a,b,f,g], member(f,[a,b,f,g]), Y = [a,b,f,g] ? yes The two objectives Y=[a,b,f,g] and member(f,Y) are conjoined as one term and instantiated with X. call(X) then calls them all together and will just succeed if every one of the objectives contained inside X succeed (subsequently, it is checking if the conjunction of the two objectives is valid). AIPP Lecture 17: Meta-translation

A Conjunction of Goals (2) The real employment of conjoining objectives is performed by the "," administrator. (',' = the sensible ∧) ?- (3,4) = ','(3,4). yes This is a privilege affiliated administrator: You can see this utilizing ?- current_op(1000, xfy, ','). = When utilized as a part of a progression of administrators with a similar priority the comma partners with a solitary term to one side and gatherings whatever remains of the administrators and contentions to one side. * (works correspondingly to Head a Tail list documentation). | ?- (3,4,5,6,7,8) = (3,(4,(5,(6,(7,8))))). yes | ?- (3,4,5,6,7,8) = (((((3,4),5),6),7),8). no AIPP Lecture 17: Meta-translation

A Conjunction of Goals (2) Because of this associativity, gatherings of conjoined objectives can be stripped separated by making them equivalent to (FirstGoal,OtherGoals). FirstGoal is a solitary Prolog objective OtherGoals might be a solitary objective or another combine comprising of another objective and remaining objectives (assembled around ','). | ?- (3,4,5,6,7,8) = (H,T). H = 3, T = 4,5,6,7,8 ? ; no This permits us to recursively control arrangements of objectives similarly as we beforehand controlled records. | ?- (3,4,5,6,7,8) = (A,B), B = (C,D), D = (E,F), ..... A = 3, B = 4,5,6,7,8, C = 4, D = 5,6,7,8, E = 5, F = 6,7,8, ....... Rehashed utilization of same test = recursion AIPP Lecture 17: Meta-understanding

Why utilize call? Be that as it may, why might we utilize call(X) as it appears to have an indistinguishable capacity from simply putting the variable X as an objective in your code: e.g. X = ( Y=[a,b,f,g], member(f,Y) ) , call( X) . X = ( Y=[a,b,f,g], member(f,Y) ) , X . The fundamental reason is on the grounds that it keeps the arrangement of X detached from whatever is left of the program inside which call(X) dwells. In particular, any cuts (!) inside the conjoined arrangement of objectives X just quit backtracking inside X. It doesn't quit backtracking outside of call(X). |?- goal1, goal2, call((goal3, !, goal4, goal5)). flop genuine re-try re-try re-try AIPP Lecture 17: Meta-elucidation

A Disjunction of Goals (;) As well as "," = the sensible AND ( ∧) We likewise have an administrator that speaks to the coherent OR ( ∨). Goal1 ; Goal2 = A disjunction of Goal1 and Goal2. This will succeed if either Goal1 or Goal2 are valid. | ?- 5<4;3<4. yes Semicolon is an administrator ( current_op(1100, xfy, ;) ) so it can be utilized as a part of prefix position too: | ?- ;(5<4, 3<4). yes This administrator is correct affiliated like ',': | ?- (3;4;5;6;7;8) = (A;B), B = (C;D), D = (E;F), .... A = 3, B = 4;5;6;7;8, C = 4, D = 5;6;7;8, E = 5, F = 6;7;8, ..... AIPP Lecture 17: Meta-translation

Conjoining Disjunctions However, OR has a higher priority esteem than AND, so AND dependably assembles first: current_op(1100, xfy, ;). current_op(1000, xfy, ','). An arrangement, for example, (b,c,d,e ; f). Is proportionate to (b,(c,(d,e))) ; f. not (((b,c),d), (e;f)). This is vital when you are utilizing ; in standards : a:- b,c,d,e ; f. Says that "an is valid if b, c, d, AND e are valid OR f is valid". As it were it can be composed as: a:- b,c,d,e. a:- f. AIPP Lecture 17: Meta-elucidation

Conjoining Disjunctions (2) A predicate definition with numerous provisions is favored over the utilization of ; as it makes the definition less demanding to peruse. Be that as it may, ; can be valuable when the two definitions share a substantial number of preconditions yet vary by few last objectives: e.g. a:- b,c,d,e. a:- b,c,d,f. It is wasteful to test b, c, and d again so all things being equal you could think of one decide that simply tried e OR f: e.g. a:- b,c,d,(e;f). The sections force your gathering inclination on the structure. This can be perused as: " an is genuine is b, c, d, AND e OR f are valid.". AIPP Lecture 17: Meta-understanding

Conjoining Disjunctions (3) But, recollect all OR developments can simply be supplanted by utilizing a helper predicate with different provisos. a:- b,c,d,(e;f). Can be re-characterized as: a:- b,c,d,aux. aux:- e. aux:- f. If it's not too much trouble know that at whatever point you are composing Prolog you are as of now speaking to sensible connections: A Body of a provision loaded with objectives isolated by "," is a conjunction . Characterizing a predicate with different statements speaks to a disjunction of the conditions by which that predicate can be demonstrated valid. You ought to dependably utilize these inborn sensible structures before utilizing additional administrators, (for example, ;). AIPP Lecture 17: Meta-translation

Creating a Conjoined "not" Now that we can conjoin objectives we can likewise check for their nullification i.e. ¬ ( P∧Q). Normally we are checking if a conjunction of terms in the body or a condition is genuine e.g. a(X):- b(X), c(X). Be that as it may, now and then we need a predicate to succeed just if a conjunction of terms is false e.g a1(X):- \+ (b(X),c(X)). * The space before the prefix administrator \+ and the sections is critical. In the event that there was no space the translator would search for \+/2. This is unmistakable from: a2(X):- \+b(X), \+c(X). Which is equivalent to the space outside of both b and c. a2 a B a C = a1 AIPP Lecture 17: Meta-translation

Creating a Conjoined "not" (2) But rather when might you utilize a conjoined not? " X is valid on the off chance that it is under 4 or more noteworthy than 8." For instance, we need X to be valid on the off chance that it is 3 or 9. We could speak to this utilizing a disjunction: (X<4 ; 8<X). On the other hand we could speak to it as a conjoined not: \+ (4=<X , X=<8). This is conceivable as rationale allows this change: ¬ P∨ ¬ Q = ¬ ( P∧Q) Sometimes it may be less demanding to demonstrate an objective (4=<X) instead of its inverse (X<4) so we would need to utilize a conjoined not: ¬ ( P∧Q) AIPP Lecture 17: Meta-elucidation

Using if proclamations In a ton of other programming dialects if.. at that point… else… developments are extremely normal. In Prolog there is an inherent administrator ( - >/2 ) that permits you to make comparative developments: "if X then Y" = X - > Y. "in the event that X then Y else Z" = X - > Y ; Z. n.b. the ; is a piece of the "if..then… else… " development so its degree is restricted to the if.. development. These can be utilized at the charge line or inside your predicate definitions. Be that as it may, at whatever point we are composing Prolog rules we are now speaking to an "assuming… .then… ." relationship. This manage a:- b, c, d, e - > f ; g. Is equivalent to a:- b, c, d, aux(X). aux(f):- e. aux(g). AIPP Lecture 17: Meta-translation

Meta-understanding You've seen at this point Prolog has its own particular verification procedure , which is the way it approaches attempting to unravel an objective you give it. Objectives and sub-objectives are taken in a left-to-right, and profundity first way. Notwithstanding, since we can get to the Prolog database, we can control the substance of the Prolog database as though it were whatever other kind of information (which is the thing that we mean by meta-programming - programming where the information is bits of program, as opposed to data about elements on the planet). You've perceived how we can change the database, utilizing attest/1 and withdraw/1 . Be that as it may, we can likewise make a meta-translator , which permits us to make a radical new verification technique. We don't need to depend on the essential implicit verification procedure which Prolog gives. AIPP Lecture 17: Meta-understanding

A Prolog Meta-mediator A Prolog meta-translator takes a Prolog program and an objective and endeavors to demonstrate that the objective legitimately takes after from the program. The most fundamental meta-translator takes a counseled Prolog program and tries to demonstrate a Goal by calling it: prove(Goal):- call(Goal). call/1 utilizes the first Prolog translator to demonstrate the Goal so it plays out the default confirmation system. To start controlling the verification procedure we have to diminish the 'grain size' of the translator (the span of the components it controls). We can do this by utilizing statement/2 AIPP Lecture 17: Meta-translation

proviso/2 You may recollect condition/2 from the Database Manipulation (address 14). clause(Head, Body) succeeds if there is a statement in the present Prolog database which is unifiable with: Head :- Body. E.g. :- dynamic a/2. % all predicates must be initially pronounced a(1,2). as dynamic before they can be seen a(X,_):- c(X). with provision/2. a(X,Y):- b(X)