TERMINOLOGIJA PROGRAMIRANJA V PROLOGU INFORMATICA 2/88 TERMINOLOGV OF PROLOG PROGRAMMING Igor Kononenko Fakulteta za elektrotehniko Nada Lavrač UDK 681.3.06. Prolog: 001.4 Inštitut Jožef Stefan Prolog je novejSi programski jezik, ki se vse bolj uveljavlja tudi pri nas. Zaradi velikih razlik v terminologiji tako v svetu kot pri nas j© potrebno poenotiti terminologijo, ki se uporablja v logiCnem programiranju ter programiranju v prologu. Osnova za delo sta slovarja v (Kononenko 87) in (Kononenko, Lavrae 87). V prispevku smo podali razlike med terminologijaraa matematicne logike in logiftnega programiranja ter med prologom in ostalimi programskimi Jeziki. Poskusili smo odpraviti tudi nekatere terminoloSke nesporazume. >. Podani so tudi prevodi nekaterih izrazov iz angleseine v slovenseino, za katere smo se zedinili na Fakulteti za elektrotehniko in InStitutu Jožef Stefan v Ljubljani. ABSTRACT Lately, Prolog became a very popular language in the computer programming community. As there is a lot of diversity in the terminology we point out some of the main problems and try to eliminate them by defining the most useful terms. The basis for this paper is a glossary in (Kononenko & Lavrafi 87). We present differences between mathematical logic and logic programming, betveen Prolog and other programming languages and show how these differencss affect the terminology. We also point out sorae misunderstandings regarding the usual terminology and mention some synonyms used in the field of logic programiuing. 1. RAZLIKE MED MATEMATIeNO LOGIKO IN LOGIčNIM PROGRAMIRANJEM 1. MATHEMATICAL LOGIC AND LOGIC PROGRAMMING Prolog (Clocksin, Mellish 81) je najbolj razsirjen jezik logienega programiranja. Ime Prolog (Clocksin & Mellish 81) is the most "PROLOG" je dejansko kratica za 'PROgramming in widespread language of the logic programming. LOGic'. Ker prolog temelji na matematični PROLOG is in fact an abbreviation for logiki, je iz nje privzeta tudi terminologija, PROgramming in LOGic. As it is based on kar je v doloeenih primerih pripeljalo do mathematical logic the similar terminology is dvoumnosti. adopted which in some cases leads to ambiguities. 103 Osnovna razlika med stavki v logiki in stavki v prologu je ta, da imajo stavki v prologu tudi proceduralen in ne le deklarativen pomen. Pogosto se uporablja izraz 'predikat' kot sinonim za 'proceduro'. Procedura je del programa (mnozica stavkov), ki definira predikat z dolofienim Stevilom argumentov. Definicija je kljub deklarativnemu značaju proceduralna, zato je izraz 'predikat' zavajajoe. V logiCnem programiranju zadostuje uporaba izrazov 'procedura', 'vgrajena procedura' ipd. namesto izrazov 'predikat', 'vgrajeni predikat', ipd. Pogosto se v literaturi mešata izraza 'prilagajanje' in 'unifikacija'. Prilagajanje v prologu je proceduralna implementacija unifikacije iz matematiCne logike, ki ponavadi zaradi ueinkovitosti deluje drugače kot unifikacija. Neopredeljena spremenljivka se lahko prilagodi z izrazom, v katerem sama nastopa, ne more pa se z njim unificirati. Preglavice povzroftajo tudi izrazi 'atom', 'literal' in.'cilj'. Atom je v matematifini logiki kratica za atomarno formulo, medtem ko v prologu pomeni vrsto preprostih nedeljivih podatkovnih konstruktov, ki so konstarrte razliCne od Stevil. Tako ustreza atom v prologu kostanti v matematiCni logiki. Atom v matematieni logiki ustreza strukturi v prologu, ki predstavlja klic procedure, Ce se nahaja v telesu stavka (v pogojnem delu stavka), ali pa sklep, fie se nahaja v glavi stavka (v sklepnem delu stavka). Klicu procedure v telesu prologovega stavka pravimo cilj. Nekateri avtorji (npr. Sterling, Shapiro 86) pravijo glavi stavka tudi cilj. SintaktiCno so glava stavka in cilji v telesu stavka pozitivni (nenegirani) literali. Literal je sintaktieni konstrukt sestavljen iz imena predikata in seznama argumentov v oklepaju, loeenih z vejicami. Funktor v matematifini logiki doloea funkcijo, medtem ko v prologu funkcij ni. Funktor v prologu omogoCa konstrukcijo struktur z imenom in mestnostjo (Stevilom argumentov) danega funktorja. Strukture so podatkovni objekti v prologu in nimajo veliko skupnega s funkcijami v matematiki. Nerodno je, da sta se pri programiranju v The main difference between logical statements and Prolog clauses is that Prolog clauses have also the E£O£6dyr^i meaning while logical stateraents have only the declarative meaning. The term 'predicate' is often used as a synonym for a 'procedure'. A procedure is a part of a program (a sequence of clauses) that defines a predicate with the given name and arity. Although the definition may be viewed declaratively it is in fact procedural (the order of clauses and the order of goals in clauses are important). The term 'predicate' is therefore misleading. For programming purposes it is thus more convenient to use terms 'procedure', 'built-in procedure', etc. instead of 'predicate', 'built-in predioate', etc. In the literature is often made no explicit distinction between 'unification' and 'matching'. Matching in Prolog is a procedural implementation of the unifioation from mathematical logic and usualy differs from it {for the efficiency reasons). It allows an uninstantiated variable to be matched with a term in which it itself appears while it cannot be unified with such a term (this problem is usually referred to as the 'oocurs check' problem). There are difficulties with terms 'atom', 'literal' and 'goal'. In mathematical logic an atom is an abbreviation for 'atomic formula' while in Prolog an atom is a simple data struoture, i.e. a constant that is not a number. Therefore an atom in Prolog corresponds to a constant in mathematical logic. An atom in mathematical logic corresponds to a Prolog structure representing a procedure call if it appears in a body of a clause (a condition part) or a conclusion if it appears in the head of a clause (a conclusion part). A procedure call in a body of a clause is usually called a goal. Some authors (e.g. Sterling & Shapiro 86) call the head of a clause also a goal. Syntactically the head of a clause and goals in the body of a clause are positive (nonnegated) literals. A literal is constructed from a predicate name and a list of arguments enclosed in braokets and separated by commas. A positive literal is a synonym for atomic formula. It is better to use a •term 'literal' because of the previously mentioned definition of an atom in Prolog. 104 prologu v angleSčini udomačila izraza 'bound •-' variable' in 'free variable' za spremenljivko, ki ima oziroma nima vrednosti. V matematiCni logiki se namreč ta dva izraza uporabljata za kvantificirano (vezano) in nekvantificirano (nevezano) spremenljivko. Zato je bolje, da se namesto 'bound' in 'free' uporabljata izraza 'instantiated' in 'uninstantiated'. Možni prevodi so instancirana (neinstancirana), prilagojena (neprilagojena) ali opredel.jena (neopredeljena). Zadnji prevod je najustreznejSi, saj se vrednost spremenljivke v prologu lahko med izvajanjem bolj ali manj opredeli. 2. BAZLIKE MED PROLOGOM IN OSTALIMI PROGRAMSKIMI JEZIKI In mathematical logic a functor determines a function while in Prolog are no functions. Functors in Prolog are used to construct compound data structures with the given name and arity. Structures in Prolog have not much in common with mathetnatical functions. It is awkward that the term 'bound variable' is used for a variable taht has a value and 'free variable' for a variable that doesn't have a value. In mathematical logic bound variable represents a quantified and free variable represents an unquantified variable. In Prolog all variables are universally quantified (except in questions). Therefore it is better to use terras 'instantiated' and 'uninstantiated variable'. Za razliko od ostalih razSirjenih programskih jezikov, ki imajo proceduralni značaj, je prolog je deklarativni jezik. Proceduralni pomen programa v prologu je definiran z nafiinorn izvajanja prologovega interpreterja. Vsekakor je v anglešfiini pravilneje uporabljati izraz 'execution' za izvajanje prologovega programa namesto ustaljenega izraza 'cornputation' (raftunanje), saj je izvajanje prologovega programa dejansko sklepanje (inference) na osnovi pravil in dejstev. Zato rafiunalnikom vse pogosteje pravijo tudi 'inference machine' (stroj za sklepanje) namesto 'computer'. 2. PROLOG AND OTHER PROGRAMMING LANGUAGES Prolog is a declarative language and it largely differs from other popular programming languages which are procedural. The procedural meaning of a Prolog program is defined with the way how it is executed by the Prolog interpreter. It is better to use the term 'execution' than 'computation'. Execution of a Prolog program can be viewed as inference and a computer can be also called an inference machine. Med izvajanjem prologovega programa spremenljivke dobijo svojo vrednost s procesom prilagajanja. Pravimo, da vrednost spremenljivke postane (bolj) doloCena oziroma opredeljena. Ne more pa se vrednost spremenljivke spremeniti na neko povsem drugo vrednost, razen pri avtomatskem vračanju. Pri avtomatskem vraftanju vrednost lahko postane . manj opredeljena. Za razliko od prologa pa se vrednosti spremenljivk v proceduralnih jezikih lahko spreminjajo. Zato ima izraz 'vrednost spremenljivke' v prologu nekoliko drugafien pomen. Prireditev v standardnih proceduralnih jezikih pomeni spremembo vrednosti spremenljivke na neko dolofteno vrednost. V prologu take prireditve ni. Izraz 'prireditev' se uporablja v prologu za vgrajeno proceduro 'is', ki se uporablja za izrafiun vrednosti aritmetiCnega izraza, in prilagoditev izračunane vrednosti s spremenljivko ali konstanto, Ce je to možno. During the execution of a Prolog program variables get their values by matching. We say that the value of a variable becomes (more) specified or determined. Hhile backtracking the value may become less specified. A variable is therefore more or less instantiated. The value of a variable cannot be changed as in other programming languages. Thus in Prolog the term 'the value of a variable' has a slightly different interpretation than in other programming languages. An assignment in standard procedural languages causes the change of the value of a variable to a certain new value. There is no such assigntnent in Prolog. The t.erni ' assignment' is used in Prolog for the built-in procedure 'is' which computes the value of the arithmetical expression on the right-hand side and matches the result with the argument on the left-hand side, if this is possible. 105 Pri programiranju niz (string) predstavlja ponavadi niz znakov med dvema enojnima narekovajima zgoraj. V prologu je niz seznam celih Stevil, ki ustrezajo ASCII kodam znakov, in ga lahko namesto v standardni notaciji seznama napišemo tudi kot niz ustreznih znakov med dvojnima narekovajima zgoraj. Niz znakov med enojnima narekovajima zgoraj pa v prologu predstavlja atom. In programming the term 'string' usually represents a string of characters enclosed in single quotes. In Prolog a string iš represented with a string of characters enclosed in double quotes and is equivalent to a list of integers that correspond to ASCII cod8S of characters in the string. In Prolog a string of characters enclosed in single quotes is an atom. 3. DVOUMNOSTI V TERMINOLOGIJI Prioriteta operatorjev je v prologu definirana z celimi Stevili (ponavadi od 1 do 1200). Cim manjSe je stevilo, tem močneje veze operator in obratno. Ta nekoliko neobieajna definicija dostikrat pripelje do nerazumevanja. V literaturi se pogosto navajata 'green cut' (zeleni rez) in 'red cut' (rdefii rez) (glej npr. Bratko 86). Brez zelenega reza bi procedura pravilno delovala, le nekoliko poCasnejše bi bilo izvajanje zaradi nepotrebnega vraCanja. RdeCega reza pa iz procedure ne smemo odstraniti, ker bi bilo izvajanje napaCno. Mnogi avtorji napaCno ugotavljajo, da zeleni rez ne spremeni deklarativnega pomena medtem ko rdeči rez spremeni deklarativni pomen procedure. Rez je kontrolni konstrukt, ki nima deklarativnega pomena in zato tudi ne more spremeniti deklarativnega pomena. Vpliva pa na proceduralni pomen dane procedure, saj se zaporedje izvajanja z dodajanjem reza spremeni. Torej tako zeleni kot rdeei rez spremenita proceduralni pomen procedure, le da zeleni rez lahko odstranimo, ne da bi spremenili proceduralno pravilnost procedure, medtem ko z odstranitvijo rdeftega reza postane procedura nepravilna. 3. AMBIGUITIES IN TERMINOLOGY The prscedence of an operator is defined as a strength with which an operator binds its arguments. It is labeled with an integer (usually between 1 and 1200). The greater the label is the weaker the operator binds its arguments and vice versa. This somehow unusual definition often leads to misunderstandings. In the literature we often meet 'green cut' and 'red cut' (e.g. Bratko 86). Without green cut the procedure would still perform correctly- although less efficiently due to unnecessary backtracking. The red cut must not be removed because the execution of the procedure would be incorrect. Many authors incorrectly state that the green cut does not affect the declarative meaning while the red cut does. Cut is a procedural construct with no declarative meaning and thus cannot affect the declarative meaning. It certanly affects the procedural meaning of a procedure because the execution is changed. Therefore both green and red cuts affect the procedural meaning of a procedure. The green out can be removed without affecting the procedural correctness of the procedure while when the red cut is removed the procedure becomes incorrect. 4. SINONIMI 4. SYNONYMS V seznamu sinonimov so ustreznejši izrazi na desni strani: In the following list of synonyms the terms at the right-hand side should be preferred. atomarna formula - pozitivni literal objekt - izraz podatkovna struktura - izraz atomic formula - (positive) literal bound variable - instantiated variable 106 predefinirana procedura - vgrajena procedura built-in predicate - built-in procedure sistemska procedura - vgrajena procedura struktura - sestavljeni izraz term - izraz compound term - structure computation — execution control predicate - control procedure vgrajeni predikat - vgrajena procedura data structure - term 5. USTALJENI PREVODI NEKATERIH IZRAZOV Za naslednje prevode izrazov smo se zedinili na Fakulteti za elektrotehniko in InStitutu Jozef Stefan v Ljubljani: cut - rez instance - primer instance of a term - primer izraza instantiated - opredeljen matching - prilagajanje parent goal - nadrejeni cilj term - izraz evaluable predicate - built-in procedure free variable - uninstantiated variable joint variable - shared variable object. - term predefined operator - built-in operator predefined procedure - built-in procedure priority - precedence system procedure - built-in procedure stopping condition - boundary condition unbound variable - uninstantiated variable ZAHVALA Slovarja v (Kononenko 87) in (Kononenko, LavraC 87), ki sta osnova tega dela, sta rezultat skupnega prizadevanja ob pomoCi mnogih sodelavcev. Zahvaljujeva se Tatjani Janc in Alenu VarSku za pripombe na rokopisl AKNOWLEDGEMENTS Many colleagues helped us in the preparation of a glossary in (Kononenko & Lavrač 87) which is the basis for this paper. We thank Tatjana Janc and Alen VarSek for their remarks on a manuscript. LITERATURA - REFERENCES Bratko, I. (1986) Prclog pi-ogramming for artificial intelligence, Addison-Wesley. Clocksin, W.F., Mellish, F.G. (1981) Programming in prolog, Springer- Verlag. Kononenko, I. (1987) Uvod v prolog in zbirka nalog z rešitvami, skripta, Fakulteta za elektrotehniko, Ljubljana. Kononenko, I., Lavrač, N. (1987) Prolog through examples - A practical programming guide, Sigma Press. Sterling, L., Shapiro, E. (1986) The art of prolog - Advanced programming techniques, MIT Press.