联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Subject Introduction The University of Melbourne School of Computing and Information Systems COMP30020 Declarative Programming Lecture 0 Subject Introduction Copyright 2022 The University of Melbourne COMP30020 Declarative Programming Subject Introduction Welcome to Declarative Programming Lecturer: Peter Schachte Contact information is available from the LMS. There will be two pre-recorded one-hour lectures per week, plus one live one-hour practical meeting for questions, discussion, and demonstrations. There will be eleven one-hour workshops (labs), starting in week 2. You should have already been allocated a workshop. Please check your personal timetable after the lecture. COMP30020 Declarative Programming Lecture 0 – 1 / 16 Subject Introduction Grok We use Grok to provide added self-paced instructional material, exercises, and self-assessment for both Haskell and Prolog. You can access Grok by following the link from the subject LMS page. If you are unable to access Grok or find that it is not working correctly, please email Grok University Support from your university email account and explain the problem. If you have questions regarding the Grok lessons or exercises, please post a message to the subject LMS discussion forum. COMP30020 Declarative Programming Lecture 0 – 2 / 16 Subject Introduction Workshops The workshops will reinforce the material from lectures, partly by asking you to apply it to small scale programming tasks. To get the most out of each workshop, you should read and attempt the exercises before your workshop. You are encouraged to ask questions, discuss, and actively engage in workshops. The more you put into workshops, the more you will get out of them. Workshop exercises will be available through Grok, so they can be undertaken even if you are not present in Australia. Sample solutions for each set of workshop exercises will also be available through Grok. Most programming questions have more than one correct answer; your answer may be correct even if it differs from the sample solution. NOTE If your laptop can access the building’s wireless network, you will be able to use Grok, giving you access to Prolog and Haskell. If your laptop cannot access the building’s wireless network, then you will be able to test your Haskell or Prolog code if you install the implementations of those languages on your machine yourself. For both languages this is typically fast and simple. COMP30020 Declarative Programming Lecture 0 – 3 / 16 Subject Introduction Resources The lecture notes contain copies of the slides presented in lectures, plus some additional material. All subject materials (lecture notes, workshop exercises, project specifications etc) will be available online through the LMS. The recommended text (which is available online)is Bryan O’Sullivan, John Goerzen and Don Stewart: Real world Haskell. Other recommended resources are listed on the LMS. COMP30020 Declarative Programming Lecture 0 – 4 / 16 Subject Introduction Academic Integrity All assessment for this subject is individual; what you submit for assessment must be your work and your work alone. It is important to distinguish project work (which is assessed) from tutorials and other unassessed exercises. We are well aware that there are many online sources of material for subjects like this one; you are encouraged to learn from any online sources, and from other students, but do not submit for assessment anything that is not your work alone. Do not provide or show your project work to any other student. Do not store your project work in a public Github or other repository. We use sophisticated software to find code that is similar to other submissions this year or in past years. Students who submit another person’s work as their own or provide their work for another student to submit in whole or in part will be subject to disciplinary action. COMP30020 Declarative Programming Lecture 0 – 5 / 16 Subject Introduction How to succeed Declarative programming is substantially different from imperative programming. Even after you can understand declarative code, it can take a while before you can master writing your own. If you have been writing imperative code all your programming life, you will probably try to write imperative code even in a declarative language. This often does not work, and when it does work, it usually does not work well. Writing declarative code requires a different mindset, which takes a while to acquire. This is why attending the workshops, and practicing, practicing and practicing some more are essential for passing the subject. COMP30020 Declarative Programming Lecture 0 – 6 / 16 Subject Introduction Sources of help During contact hours: Ask me during or after a lecture (not before). Ask the demonstrator in your workshop. Outside contact hours: The LMS discussion board (preferred: everyone can see it) Email (if not of interest to everyone) Attend my consultation hours (see LMS for schedule) Email to schedule an appointment Subject announcements will be made on the LMS. Please monitor the LMS for announcements, and the discussion forum for detailed information. Read the discussion forum before asking questions; questions that have already been answered will not be answered again. COMP30020 Declarative Programming Lecture 0 – 7 / 16 Subject Introduction Objectives On completion of this subject, students should be able to: apply declarative programming techniques; write medium size programs in a declarative language; write programs in which different components use different languages; select appropriate languages for each component task in a project. These objectives are not all of equal weight; we will spend almost all of our time on the first two objectives. COMP30020 Declarative Programming Lecture 0 – 8 / 16 Subject Introduction Content Introduction to logic programming and Prolog Introduction to constraint programming Introduction to functional programming and Haskell Declarative programming techniques Tools for declarative programming, such as debuggers Interfacing to imperative language code This subject will teach you Haskell and Prolog, with an emphasis on Haskell. For logistical reasons, we will begin with Prolog. COMP30020 Declarative Programming Lecture 0 – 9 / 16 Subject Introduction Why Declarative Programming Declarative programming languages are quite different from imperative and object oriented languages. They give you a different perspective: a focus on what is to be done, rather than how. They work at a higher level of abstraction. They make it easier to use some powerful programming techniques. Their clean semantics means you can do things with declarative programs that you can’t do with conventional programs. The ultimate objective of this subject is to widen your horizons and thus to make you better programmers, and not just when using declarative programming languages. COMP30020 Declarative Programming Lecture 0 – 10 / 16 Subject Introduction Imperative vs logic vs functional programming Imperative languages are based on commands, in the form of instructions and statements. Commands are executed. Commands have an effect, such as to update the computation state, and later code may depend on this update. Logic programming languages are based on finding values that satisfy a set of constraints. Constraints may have multiple solutions or none at all. Constraints do not have an effect. Functional languages are based on evaluating expressions. Expressions are evaluated. Expressions do not have an effect. COMP30020 Declarative Programming Lecture 0 – 11 / 16 Subject Introduction Side effects Code is said to have a side effect if, in addition to producing a value, it also modifies some state or has an observable interaction with calling functions or the outside world. For example, a function might modify a global or a static variable, modify one of its arguments, raise an exception (e.g. divide by zero), write data to a display, file or network, read data from a keyboard, mouse, file or network, or call other side-effecting functions. NOTE Reading from a file is a side effect because it moves the current position in the file being read, so that the next read from that file will get something else. COMP30020 Declarative Programming Lecture 0 – 12 / 16 Subject Introduction An example: destructive update In imperative languages, the natural way to insert a new entry into a table is to modify the table in place: a side-effect. This effectively destroys the old table. In declarative languages, you would instead create a new version of the table, but the old version (without the new entry) would still be there. The price is that the language implementation has to work harder to recover memory and to ensure efficiency. The benefit is that you don’t need to worry what other code will be affected by the change. It also allows you to keep previous versions, for purposes of comparison, or for implementing undo. The immutability of data structures also makes parallel programming much easier. Some people think that programming the dozens of cores that CPUs will have in future is the killer application of declarative programming languages. COMP30020 Declarative Programming Lecture 0 – 13 / 16 Subject Introduction Guarantees If you pass a pointer to a data structure to a function, can you guarantee that the function does not update the data structure If not, you will need to make a copy of the data structure, and pass a pointer to that. You add a new field to a structure. Can you guarantee that every piece of code that handles the structure has been updated to handle the new field If not, you will need many more test cases, and will need to find and fix more bugs. Can you guarantee that this function does not read or write global variables Can you guarantee that this function does no I/O If the answer to either question is “no”, you will have much more work to do during testing and debugging, and parallelising the program will be a lot harder. COMP30020 Declarative Programming Lecture 0 – 14 / 16 Subject Introduction Some uses of declarative languages In a US Navy study in which several teams wrote code for the same task in several languages, declarative languages like Haskell were much more productive than imperative languages. Mission Critical used Mercury to build an insurance application in one third the time and cost of the next best quote (which used Java). Ericsson, one of the largest manufacturers of phone network switches, uses Erlang in some of their switches. The statistical machine learning algorithms behind Bing’s advertising system are written in F#. Facebook used Haskell to build the system they use to fight spam. Haskell allowed them to increase power and performance over their previous system. NOTE Erlang, F# and Lisp are of course declarative languages. For a whole bunch of essays about programming, including some about the use of Lisp in Yahoo! Store, see paulgraham.com. COMP30020 Declarative Programming Lecture 0 – 15 / 16 Subject Introduction The Blub paradox Consider Blub, a hypothetical average programming language right in the middle of the power continuum. When a Blub programmer looks down the power continuum, he knows he is looking down. Languages below Blub are obviously less powerful, because they are missing some features he is used to. But when a Blub programmer looks up the power continuum, he does not realize he is looking up. What he sees are merely weird languages. He thinks they are about equivalent in power to Blub, but with some extra hairy stuff. Blub is good enough for him, since he thinks in Blub. When we switch to the point of view of a programmer using a language higher up the power continuum, however, we find that she in turn looks down upon Blub, because it is missing some things she is used to. Therefore understanding the differences in power between languages requires understanding the most powerful ones. NOTE This slide is itself paraphrased from one of Paul Graham’s essays. (The full quotation is too big to fit on one slide.) The least abstract and therefore least powerful language is machine code. One step above that is assembler, and one step above that are the lowest level imperative languages, like C and Fortran. Everyone agrees on that. Most people (but not all) would also agree that modern object-oriented languages like Java and C#, scripting languages like awk and Perl and multi-paradigm languages like Python and Ruby are more abstract and more powerful than C and Fortran, but there is no general agreement on their relative position on the continuum. However, almost everyone who knows declarative programming languages agrees that they are more abstract and more powerful than Java, C#, awk, Perl, Python and Ruby. A large part of that extra power is the ability to offer many more guarantees. COMP30020 Declarative Programming Lecture 0 – 16 / 16 Introduction to Logic Programming The University of Melbourne School of Computing and Information Systems COMP30020 Declarative Programming Lecture 1 Introduction to Logic Programming Copyright 2022 The University of Melbourne COMP30020 Declarative Programming Introduction to Logic Programming Logic programming Imperative programming languages are based on the machine architecture of John von Neumann, which executes a set of instructions step by step. Functional programming languages are based on the lambda calculus of Alonzo Church, in which functions map inputs to outputs. Logic programming languages are based on the predicate calculus of Gottlob Frege and the concept of a relation, which captures a relationship among a number of individuals, and the predicate that relates them. A function is a special kind of relation that can only be used in one direction (inputs to outputs), and can only have one result. Relations do not have these limitations. While the first functional programming language was Lisp, implemented by John McCarthy’s group at MIT in 1958, the first logic programming language was Prolog, implemented by Alain Colmerauer’s group at Marseille in 1971. NOTE Since the early 1980s, the University of Melbourne has been one of the world’s top centers for research in logic programming. Lee Naish designed and implemented MU-Prolog, and led the development of its successor, NU-Prolog. Zoltan Somogyi led the development of Mercury, and was one of its main implementors. NOTE The name “Prolog” was chosen by Philippe Roussel as an abbreviation for “programmation en logique”, which is French for “programming in logic”. MU-Prolog and NU-Prolog are two closely-related dialects of Prolog. There are many others, since most centers of logic programming research in the 1980s implemented their own versions of the language. The other main centers of logic programming research are in Leuven, Belgium; Uppsala, Sweden; Madrid, Spain; and Las Cruces, New Mexico, USA. COMP30020 Declarative Programming Lecture 1 – 1 / 20 Introduction to Logic Programming Relations A relation specifies a relationship; for example, a family relationship. In Prolog syntax, parent(queen_elizabeth, prince_charles). specifies (a small part of the) parenthood relation, which relates parents to their children. This says that Queen Elizabeth is a parent of Prince Charles. The name of a relation is called a predicate. Predicates have no directionality: it makes just as much sense to ask of whom is Queen Elizabeth a parent as to ask who is Prince Charles’s parent. There is also no promise that there is a unique answer to either of these questions. COMP30020 Declarative Programming Lecture 1 – 2 / 20 Introduction to Logic Programming Facts A statement such as: parent(queen_elizabeth, prince_charles). is called a fact. It may take many facts to define a relation: % (A small part of) the British Royal family parent(queen_elizabeth, prince_charles). parent(prince_philip, prince_charles). parent(prince_charles, prince_william). parent(prince_charles, prince_harry). parent(princess_diana, prince_william). parent(princess_diana, prince_harry). … Text between a percent sign (%) and end-of-line is treated as a comment. COMP30020 Declarative Programming Lecture 1 – 3 / 20 Introduction to Logic Programming Using Prolog Most Prolog systems have an environment similar to GHCi. A file containing facts like this should be written in a file whose name begins with a lower-case letter and contains only letters, digits, and underscores, and ends with “.pl”. A source file can be loaded into Prolog by typing its filename (without the .pl extension) between square brackets at the Prolog prompt ( -). Prolog prints a message to say the file was compiled, and true to indicate it was successful (user input looks like this): – [royals]. % royals compiled 0.00 sec, 8 clauses true. – NOTE Some Prolog GUI environments provide other, more convenient, ways to load code, such as menu items or drag-and-drop. COMP30020 Declarative Programming Lecture 1 – 4 / 20 Introduction to Logic Programming Queries Once your code is loaded, you can use or test it by issuing queries at the Prolog prompt. A Prolog query looks just like a fact. When written in a source file and loaded into Prolog, it is treated as a true statement. At the Prolog prompt, it is treated as a query, asking if the statement is true. – parent(prince_charles, prince_william). true . – parent(prince_william, prince_charles). false. COMP30020 Declarative Programming Lecture 1 – 5 / 20 Introduction to Logic Programming Variables Each predicate argument may be a variable, which in Prolog begins with a capital letter or underscore and follows with letters, digits, and underscores. A query containing a variable asks if there exists a value for that variable that makes that query true, and prints the value that makes it true. If there is more than one answer to the query, Prolog prints them one at a time, pausing to see if more solutions are wanted. Typing semicolon asks for more solutions; just hitting enter (return) finishes without more solutions. This query asks: of whom Prince Charles is a parent – parent(prince_charles, X). X = prince_william ; X = prince_harry. COMP30020 Declarative Programming Lecture 1 – 6 / 20 Introduction to Logic Programming Multiple modes The same parenthood relation can be used just as easily to ask who is a parent of Prince Charles or even who is a parent of whom. Each of these is a different mode, based on which arguments are bound (inputs; non-variables) and which are unbound (outputs; variables). – parent(X, prince_charles). X = queen_elizabeth ; X = prince_philip. – parent(X, Y). X = queen_elizabeth, Y = prince_charles ; X = prince_philip, Y = prince_charles ; … COMP30020 Declarative Programming Lecture 1 – 7 / 20 Introduction to Logic Programming Compound queries Queries may use multiple predicate applications (called goals in Prolog and atoms in predicate logic). The simplest way to combine multiple goals is to separate them with a comma. This asks Prolog for all bindings for the variables that satisfy both (or all) of the goals. The comma can be read as “and”. In relational algebra, this is called an inner join (but do not worry if you do not know what that is). – parent(queen_elizabeth, X), parent(X, Y). X = prince_charles, Y = prince_william ; X = prince_charles, Y = prince_harry. COMP30020 Declarative Programming Lecture 1 – 8 / 20 Introduction to Logic Programming Rules Predicates can be defined using rules as well as facts. A rule has the form Head :- Body, where Head has the form of a fact and Body has the form of a (possibly compound) query. The :- is read “if”, and the clause means that the Head is true if the Body is. For example grandparent(X,Z) :- parent(X, Y), parent(Y, Z). means “X is grandparent of Z if X is parent of Y and Y is parent of Z .” Rules and facts are the two different kinds of clauses. A predicate can be defined with any number of clauses of either or both kinds, intermixed in any order. COMP30020 Declarative Programming Lecture 1 – 10 / 20 Introduction to Logic Programming Recursion Rules can be recursive. Prolog has no looping constructs, so recursion is widely used. Prolog does not have a well-developed a library of higher-order operations, so recursion is used more in Prolog than in Haskell, as you will see. A person’s ancestors are their parents and the ancestors of their parents. ancestor(Anc, Desc) :- parent(Anc, Desc). ancestor(Anc, Desc) :- parent(Parent, Desc), ancestor(Anc, Parent). COMP30020 Declarative Programming Lecture 1 – 11 / 20 Introduction to Logic Programming Equality Equality in Prolog, written “=” and used as an infix operator, can be used both to bind variables and to check for equality. Prolog is a single-assignment language: once bound, a variable cannot be reassigned. – X = 7. X = 7. – a = b. false. – X = 7, X = a. false. – X = 7, Y = 8, X = Y. false. COMP30020 Declarative Programming Lecture 1 – 12 / 20 Introduction to Logic Programming Disjunction Goals can be combined with disjunction (or) as well as conjunction (and). Disjunction is written “;” and used as an infix operator. Conjunction (“,”) has higher precedence (binds tighter) than disjunction, but parentheses can be used to achieve the desired precedence. Who are the children of Queen Elizabeth or Princess Diana – parent(queen_elizabeth, X) ; parent(princess_diana, X). X = prince_charles ; X = prince_william ; X = prince_harry. COMP30020 Declarative Programming Lecture 1 – 13 / 20 Introduction to Logic Programming Negation Negation in Prolog is written “+” and used as a prefix operator. Negation has higher (tighter) precedence than both conjunction and disjunction. Be sure to leave a space between the + and an open parenthesis. Who are the parents of Prince William other than Prince Charles – parent(X, prince_william), + X = prince_charles. X = princess_diana. Disequality in Prolog is written as an infix “=”. So X = Y is the same as + X = Y. – parent(X, prince_william), X = prince_charles. X = princess_diana. COMP30020 Declarative Programming Lecture 1 – 14 / 20 Introduction to Logic Programming The Closed World Assumption Prolog assumes that all true things can be derived from the program. This is called the closed world assumption. Of course, this is not true for our parent relation (that would require tens of billions of clauses!). – + parent(queen_elizabeth, princess_anne). true. but Princess Anne is a daughter of Queen Elizabeth. Our program simply does not know about her. So use negation with great care on predicates that are not complete, such as parent. COMP30020 Declarative Programming Lecture 1 – 16 / 20 Introduction to Logic Programming Negation as failure Prolog executes + G by first trying to prove G. If this fails, then + G succeeds; if it succeeds, then + G fails. This is called negation as failure. In Prolog, failing goals can never bind variables, so any variable bindings made in solving G are thrown away when + G fails. Therefore, + G cannot solve for any variables, and goals such as these cannot work properly. Is there anyone of whom Queen Elizabeth is not a parent Is there anyone who is not Queen Elizabeth – + parent(queen_elizabeth, X). false. – X = queen_elizabeth. false. COMP30020 Declarative Programming Lecture 1 – 17 / 20 Introduction to Logic Programming Execution Order The solution to this problem is simple: ensure all variables in a negated goal are bound before the goal is executed. Prolog executes goals in a query (and the body of a clause) from first to last, so put the goals that will bind the variables in a negation before the negation (or =). In this case, we can generate all people who are either parents or children, and ask whether any of them is different from Queen Elizabeth. – (parent(X,_) ; parent(_,X)), X = queen_elizabeth. X = prince_philip ; … COMP30020 Declarative Programming Lecture 1 – 18 / 20 Introduction to Logic Programming Datalog The fragment of Prolog discussed so far, which omits data structures, is called Datalog. It is a generalisation of what is provided by relational databases. Many modern databases now provide Datalog features or use Datalog implementation techniques. capital(australia, canberra). capital(france, paris). … continent(australia, australia). continent(france, europe). … population(australia, 22_680_000). population(france, 65_700_000). … COMP30020 Declarative Programming Lecture 1 – 19 / 20 Introduction to Logic Programming Datalog Queries What is the capital of France – capital(france, Capital). Capital = paris. What are capitals of European countries – continent(Country, europe), capital(Country, Capital). Country = france, Capital = paris. What European countries have populations > 50,000,000 – continent(Country, europe), population(Country, Pop), | Pop > 50_000_000. Country = france, Pop = 65700000. COMP30020 Declarative Programming Lecture 1 – 20 / 20 Beyond Datalog The University of Melbourne School of Computing and Information Systems COMP30020 Declarative Programming Lecture 2 Beyond Datalog Copyright 2022 The University of Melbourne COMP30020 Declarative Programming Beyond Datalog Terms In Prolog, all data structures are called terms. A term can be atomic or compound, or it can be a variable. Datalog has only atomic terms and variables. Atomic terms include integers and floating point numbers, written as you would expect, and atoms. An atom begins with a lower case letter and follows with letters, digits and underscores, for example a, queen_elizabeth, or banana. An atom can also be written beginning and ending with a single quote, and have any intervening characters. The usual character escapes can be used, for example n for newline, t for tab, and ’ for a single quote. For example: ’Queen Elizabeth’ or ’Hello, World!n’. COMP30020 Declarative Programming Lecture 2 – 1 / 21 Beyond Datalog Compound Terms In the syntax of Prolog, each compound term is a functor (sometimes called function symbol) followed by zero or more arguments; if there are any arguments, they are shown in parentheses, separated by commas. Functors are Prolog’s equivalent of what Haskell calls data constructors, and have the same syntax as atoms. For example, a small tree with 1 at the root, an empty left branch, and 2 in the right branch, could be written as: node(leaf, 1, node(leaf, 2, leaf)) Because Prolog is dynamically typed, each argument of a term can be any term, and there is no need to declare types. Prolog has special syntax for some functors, such as infix notation. COMP30020 Declarative Programming Lecture 2 – 2 / 21 Beyond Datalog Variables A variable is also a term. It denotes a single unknown term. A variable name begins with an upper case letter or underscore, followed by any number of letters, digits, and underscores. A single underscore _ is special: it specifies a different variable each time it appears. Prolog is a single-assignment language: a variable can only be bound (assigned) once. Because the arguments of a compound term can be any terms, and variables are terms, variables can appear in terms. For example f(A,A) denotes a term whose functor is f and whose two arguments can be anything, as long as they are the same; f(_,_) denotes a term whose functor is f and has any two arguments. COMP30020 Declarative Programming Lecture 2 – 3 / 21 Beyond Datalog List syntax Prolog has a special syntax for lists. The empty list is denoted by []. A non-empty list is denoted by [H | T], where H is the head element of the list and T is the tail. For example, the list containing 1, 2 and 3 can be denoted by [1 | [2 | [3 | []]]]. If multiple head elements are known, this can be shortened to [1, 2 | [3 | []]]. If all elements are known, then this can be shortened to [1, 2, 3] COMP30020 Declarative Programming Lecture 2 – 4 / 21 Beyond Datalog Ground vs nonground terms A term is a ground term if it contains no variables, and it is a nonground term if it contains at least one variable. 3 and f(a, b) are ground terms. Since Name and f(a, X) each contain at least one variable, they are nonground terms. If a variable occurs more than once in a term, then, just as in Algebra, each occurrance must be bound to an identical term. COMP30020 Declarative Programming Lecture 2 – 5 / 21 Beyond Datalog Substitutions A substitution is a mapping from variables to terms. Applying a substitution to a term means consistently replacing all occurrences of each variable in the map with the term it is mapped to. Note that a substitution only replaces variables, never atomic or compound terms. For example, applying the substitution {X1 7→ leaf, X2 7→ 1, X3 7→ leaf} to the term node(X1,X2,X3) yields the term node(leaf,1,leaf). Since you can get node(leaf,1,leaf) from node(X1,X2,X3) by applying a substitution to it, node(leaf,1,leaf) is an instance of node(X1,X2,X3). Any ground Prolog term has only one instance, while a nonground Prolog terms has an infinite number of instances. COMP30020 Declarative Programming Lecture 2 – 6 / 21 Beyond Datalog Unification The term that results from applying a substitution θ to a term t is denoted tθ. A term u is therefore an instance of term t if there is some substitution θ such that u = tθ. A substitution θ unifies two terms t and u if tθ = uθ. Consider the terms f(X, b) and f(a, Y). Applying a substitution {X 7→ a} to those two terms yields f(a, b) and f(a, Y), which are not syntactically identical, so this substitution is not a unifier. On the other hand, applying the substitution {X 7→ a, Y 7→ b} to those terms yields f(a, b) in both cases, so this substitution is a unifier. COMP30020 Declarative Programming Lecture 2 – 7 / 21 Beyond Datalog Recognising proper lists A proper list is either empty ([]) or not ([X|Y]), in which case, the tail of the list must be a proper list. We can define a predicate to recognise these. proper_list([]). proper_list([Head|Tail]) :- proper_list(Tail). – [list]. Warning: list.pl:3: Singleton variables: [Head] % list compiled 0.00 sec, 2 clauses true. COMP30020 Declarative Programming Lecture 2 – 9 / 21 Beyond Datalog Detour: singleton variables Warning: list.pl:3: Singleton variables: [Head] The variable Head appears only once in this clause: proper_list([Head|Tail]) :- proper_list(Tail). This often indicates a typo in the source code. For example, if Tail were spelled Tial in one place, this would be easy to miss. But Prolog’s singleton warning would alert us to the problem. COMP30020 Declarative Programming Lecture 2 – 10 / 21 Beyond Datalog Detour: singleton variables In this case, there is no problem; to avoid the warning, we should begin the variable name Head with an underscore, or just name the variable _. proper_list([]). proper_list([_Head|Tail]) :- proper_list(Tail). – [list]. % list compiled 0.00 sec, 2 clauses true. General programming advice: always fix compiler warnings (if possible). Some warnings may indicate a real problem, and you will not see them if they’re lost in a sea of unimportant warnings. It is easier to fix a problem when the compiler points it out than when you have to find it yourself. COMP30020 Declarative Programming Lecture 2 – 11 / 21 Beyond Datalog Append Appending two lists is a common operation in Prolog. This is a built in predicate in most Prolog systems, but could easily be implemented as: append([], C, C). append([A|B], C, [A|BC]) :- append(B, C, BC). – append([a,b,c],[d,e],List). List = [a, b, c, d, e]. COMP30020 Declarative Programming Lecture 2 – 12 / 21 Beyond Datalog append is like proper_list Compare the code for proper_list to the code for append: proper_list([]). proper_list([Head|Tail]) :- proper_list(Tail). append([], C, C). append([A|B], C, [A|BC]) :- append(B, C, BC). This is common: code for a predicate that handles a term often follows the structure of that term (as we will see in Haskell). While the proper_list predicate is not very useful itself, it was worth designing, as it gives a hint at the structure of other code that traverses lists. Since types are not declared in Prolog, predicates like proper_list can serve to indicate the notional type. COMP30020 Declarative Programming Lecture 2 – 13 / 21 Beyond Datalog Appending backwards Unlike ++ in Haskell, append in Prolog can work in other modes: – append([1,2,3], Rest, [1,2,3,4,5]). Rest = [4, 5]. – append(Front, [3,4], [1,2,3,4]). Front = [1, 2] ; false. – append(Front,Back,[a,b,c]). Front = [], Back = [a, b, c] ; Front = [a], Back = [b, c] ; Front = [a, b], Back = [c] ; Front = [a, b, c], Back = [] ; false. COMP30020 Declarative Programming Lecture 2 – 14 / 21 Be