CS508 Modern Programming Languages Midterm PDF

Modern Programming Languages (CS508) VU Modern Programming Languages CS508 Virtual University of Pakistan Leaders in Education Technology...

Modern Programming Languages (CS508) VU Modern Programming Languages CS508 Virtual University of Pakistan Leaders in Education Technology 1 © Copyright Virtual University of Pakistan Modern Programming Languages (CS508) VU TABLE of CONTENTS Course Objectives........................................................................................................................... 4 Introduction and Historical Background (Lecture 1-8).............................................................. 5 Language Evaluation Criterion..................................................................................................... 6 Language Evaluation Criterion................................................................................................... 15 An Introduction to SNOBOL (Lecture 9-12)............................................................................. 32 Ada Programming Language: An Introduction (Lecture 13-17)............................................. 45 LISP Programming Language: An Introduction (Lecture 18-21)........................................... 63 PROLOG - Programming in Logic (Lecture 22-26)................................................................. 77 Java Programming Language (Lecture 27-30).......................................................................... 92 C# Programming Language (Lecture 31-34)........................................................................... 111 PHP – Personal Home Page PHP: Hypertext Preprocessor (Lecture 35-37)........................ 129 Modern Programming Languages-JavaScript........................................................................ 141 Lecture 38.................................................................................................................................... 141 Location of Code......................................................................................................................... 141 Arrays.......................................................................................................................................... 143 Operators.................................................................................................................................... 144 Type Conversion......................................................................................................................... 144 Control Statements..................................................................................................................... 144 Labels and Flow Control........................................................................................................... 145 Modern Programming Languages-JavaScript........................................................................ 147 Lecture 39.................................................................................................................................... 147 Objects......................................................................................................................................... 147 Two Object Models.................................................................................................................... 147 Modern Programming Languages............................................................................................ 160 Lecture # 40................................................................................................................................. 160 Names.......................................................................................................................................... 160 Special Words............................................................................................................................. 160 Possible binding times................................................................................................................ 160 Static and Dynamic Binding...................................................................................................... 161 Type Bindings............................................................................................................................. 161 Dynamic Type Binding.............................................................................................................. 161 Storage Bindings......................................................................................................................... 161 Categories of variables by lifetimes.......................................................................................... 161 Explicit Heap Dynamic Variables............................................................................................. 162 Implicit Heap Dynamic Variables............................................................................................. 162 Modern Programming Languages Lecture 41......................................................................... 163 Type Checking............................................................................................................................ 163 Strongly Typed Languages?...................................................................................................... 163 Type Compatibility..................................................................................................................... 163 Data Types................................................................................................................................... 164 Primitive Data Types.................................................................................................................. 164 Character String Types.............................................................................................................. 164 Ordinal Types (user defined)..................................................................................................... 165 Four Categories of Arrays (based on subscript binding and binding to storage)................ 167 Modern Programming Languages Lecture 42......................................................................... 168 Records-(like structs in C/C++)................................................................................................. 168 Pointers........................................................................................................................................ 169 Unions.......................................................................................................................................... 170 Arithmetic Expressions.............................................................................................................. 172 Modern Programming Languages Lecture 43......................................................................... 173 2 © Copyright Virtual University of Pakistan Modern Programming Languages (CS508) VU Modern Programming Languages Lecture 44......................................................................... 177 1. FORTRAN 77 and 90............................................................................................................. 181 2. ALGOL 60............................................................................................................................... 182 3. Pascal....................................................................................................................................... 182 4. Ada........................................................................................................................................... 183 5. C............................................................................................................................................... 183 6. C++.......................................................................................................................................... 183 7. Java.......................................................................................................................................... 183 Logically-Controlled Loops....................................................................................................... 184 Examples..................................................................................................................................... 184 Unconditional Branching........................................................................................................... 185 Conclusion................................................................................................................................... 185 Modern Programming Languages Lecture 45......................................................................... 187 Parameters and Parameter Passing.......................................................................................... 187 1. Pass-by-value (in mode)........................................................................................................ 187 2. Pass-by-result (out mode)...................................................................................................... 187 Implementing Parameter Passing............................................................................................. 188 Design Considerations for Parameter Passing......................................................................... 188 Concluding Remarks.................................................................................................................. 188 3 © Copyright Virtual University of Pakistan Modern Programming Languages (CS508) VU Course Objectives Thousands of different programming languages have been designed by different people over the last 60 years. The questions that come to mind are: Why are there so many different programming languages? How and why they are developed? What is the intended purpose of a language? In what ways are they similar? What are the differences among them? Why wouldn’t we simply continue to use what we have today? What kinds of programming languages may be developed in future? We will try to answer some of these questions in this course. In addition, we will discuss the design issues of various languages, design choices and alternatives available, historical context and specific needs, and specific implementation issues. Text Book The main text book for this course is: Concepts of Programming Languages, 6th Ed. by Robert Sebesta. 4 © Copyright Virtual University of Pakistan Introduction and Historical Background (Lecture 1-8) VU Introduction and Historical Background (Lecture 1-8) Reasons to study concepts of Programming Languages The first question is: why should we study programming languages. There are many reasons for that and some of them are enumerated in the following paragraphs. - Increased capacity to express programming concepts Study of programming languages helps in increasing the capacity to express programming concepts. Dijkstra has put it as follows: The tools we use have a profound (and devious!) influence on our thinking habits, and, therefore, on our thinking abilities. That is, one is limited in his/her thinking by the tools used to express his/her ideas. Depth at which we can think is influenced by the expressive power of the language. It includes the kind of algorithms you can develop. The range of software development thought process can be increased by learning new languages as those constructs can be simulated. - Improved background for choosing appropriate languages Study of programming languages also helps one in choosing the right language for the given task. Abraham Maslow says, "To the man who only has a hammer in the toolkit, every problem looks like a nail." That is, if the only tool you have is a hammer, then you will treat every problem like a nail. Sometimes, some programming languages are more suitable for a specific task. There are many special purpose languages. In this course we will study one such language by the name of Snobol. - Increased ability to learn new languages Study of different programming languages also helps one in learning new languages by learning the syntax and semantics of different languages and understanding different design methodologies. - Understanding the significance of implementation In some cases, an understanding of implementation issues leads to an understanding of why languages are designed the way they are. This ultimately leads to efficient use of the language. One such example is Row vs. column major. If a programmer knows that two- dimensional arrays are stored column-wise (column major) in FORTRAN (where in most other languages it is row major) then he will be careful to process it column-wise, hence making it more efficient. 5 © Copyright Virtual University of Pakistan Introduction and Historical Background (Lecture 1-8) VU Same is the case with recursion. If the programmer knows how recursion is implemented and the associated cost of recursive programs, he can use this knowledge to come-up with more efficient programs if needed. Also, certain bugs can only be found and fixed if the programmer knows some related implementation details. - Increased ability to design new languages By learning a number of programming languages, one gets to know the pros and cons of different language features and issues related to these features. This knowledge will therefore help if one has to design a new language for any purpose. Language Evaluation Criterion In order to evaluate and compare different languages, we need some mechanism for their evaluation. The first criterion that comes to mind is: how long it takes to develop a program in a given programming language. Capers Jones has developed the following Programming Languages Table which relates languages with the productivity. Language Level Relationship to Productivity LANGUAGE LEVEL PRODUCTIVITY AVERAGE PER STAFF MONTH -------------------------- ------------------------------------------------------------------ 1-3 5 to 10 Function Points 4-8 10 to 20 Function Points 9 - 15 16 to 23 Function Points 16 - 23 15 to 30 Function Points 24 - 55 30 to 50 Function Points Above 55 40 to 100 Function Points As can be seen, a higher-level language will yield more productivity as compared to a lower level language. Some of the common languages with their levels are listed below. Assembly(1), C(2.5), Pascal(3.5), LISP(5), BASIC(5), C++(6) As can be seen, C++ has the highest level in this list. Let us now try to use this criterion to evaluate different languages. When a programmer starts to learn a new language, a typical first exercise is to program the computer to display the message "Hello World". A compilation of “Hello World programs” designed by various categories of “developer” follows. 6 © Copyright Virtual University of Pakistan Introduction and Historical Background (Lecture 1-8) VU Hello World Programs – adapted from: Infiltec Humor Page www.infiltec.com A compilation of *Hello World programs* designed by various categories of *developer* follows. High School/Jr.High - BASIC Language ==================================== 10 PRINT "HELLO WORLD" 20 END First year in College - Pascal ============================== program Hello(input, output) begin writeln('Hello World') end. Senior year in College - LISP ============================= (defun hello (print (cons 'Hello (list 'World)))) New professional - C ==================== #include void main(void) { char *message[] = {"Hello ", "World"}; int i; for(i = 0; i < 2; ++i) printf("%s", message[i]); printf("\n"); } Seasoned professional – C++ =========================== #include #include class string { private: int size; char *ptr; 7 © Copyright Virtual University of Pakistan Introduction and Historical Background (Lecture 1-8) VU public: string() : size(0), ptr(new char('\0')) {} string(const string &s) : size(s.size) { ptr = new char[size + 1]; strcpy(ptr, s.ptr); } ~string() { delete [] ptr; } friend ostream &operator Less Than < < Greater Than Or Equal >= >= Less Than Or Equal Float_Val : Float; end case; end record; Now the value of the discriminant V shows what type is currently present. Variables of a discriminated type are referenced as shown in the following example: Puzzle : Int_Float; … Puzzle := (Float, 1.0); F := Puzzle.Float_Val; -- OK I := Puzzle.Int_Val; -- type mismatch - raise exception … Puzzle.V := SomeIntValue; -- not allowed! Discriminated records can be used for making subtypes subtype PuzzleI is puzzle (Int); -- this type only holds int values These can also be used to specify array dimensions: Subtype Vlen is Integer range 1.. 10; type Vstr (Vlen : Integer := 0) is record Data : String (1.. Vlen); end record; VV : Vstr := (5, “hello”); 52 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU Access Types An access type roughly corresponds to a C++ pointer. type Address_Ref is access Address; A_Ref := new Address; A_Ref.Postal_Code := "94960-1234"; Note that, unlike C, there is no notational difference for accessing a record field directly or through an access value. To refer to the entire record accessed by an access value use the following notation: Print(A_Ref.all); Statement Forms Assignment statement Like all imperative languages, Ada also supports the assignment statement. However, in Ada the assignment is not an expression like C. The syntax of the assignment statement is as follows: Variable := expression; Note that, in Ada, ‘:=’ is used as the assignment operator whereas ‘=’ is used as assignment operator in C. If Statement The Ada if statement is fully blocked. In fact, all Ada control structures are fully blocked. That means, we do not have two separate forms if we need only one statement to be executed if the condition for the if statement is true and if we want more than one statements. The body of the if statements is always in side a a complete block that starts with the then keyword and end with end if as shown below: if condition then -- statement(s) end if; If an if statement has multiple else parts with separate conditions, then Ada uses the keyword elsif to indicate that. The else part is optional and comes at the end. Each if statement must have a corresponding end if in it. The following examples demonstrate this concept. if condition1 then -- statement(s) elsif condition2 then if condition3 then 53 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU -- statements end if; -- statement(s) … else -- statement(s) end if; if condition1 then -- statements elsif condition2 then if condition3 then -- statements end if; -- statements … else if condition4 then -- this is a new if statement and hence must have its own end if -- statements end if; -- statements end if; Case Statements Case statement is like the switch statement in C, but as compared to C, it is safer and more structured. Its syntax is as shown below: case expression is when choice list => sequence-of-statements when choice list => sequence-of-statements when others => sequence-of-statements end case; As opposed to C, the case statement is fully structured; there is no equivalent of the break statement and the control does not fall through to the next choice after executing the set of statements for the selected choice. The choice _list can have more than one values specified in the form of a range specified with the.. operator like 1..10, discrete values separated by | such as a | e | i | o | u, or a combination of both. The following example elaborates this concept. case TODAY is when MON.. THU => WORK; when FRI => WORK; PARTY; when SAT | SUN => 54 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU REST; end case; All values in when branches must be static and all possible values of expression must be included exactly once. In Ada, the case expression must match one of the choices given in the when clause as an exception will be raised as run time if there is no match. when others => is like default in C and is used to cover all the rest of the choices not mentioned in the above when clauses. Looping There are three types of loops in Ada: 1. Simple Loop – unconditional infinite loop 2. While loop 3. For Loop Simple Loop A simple loop is used to signify a potentially infinite loop. These loops are typically used in operating systems and embedded systems. Its syntax is as follows: loop -- Loop body goes here end loop; The exit statement can be used to come out of the loop as shown below. loop -- Loop body goes here exit when condition; end loop; It is equivalent to the following code segment. loop -- Loop body goes here if condition then exit; end if; end loop; The exit statement is like the break statement in C but there are certain differences and will be discussed later. While and For Loops Ada has only the pre-test while loop and does not support the post-test loop like the do- while statement in C. The while statement in Ada has the following structure. 55 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU while condition loop -- Loop body goes here end loop; The semantics of the while statement are exactly the same as its counterpart in C. The for statement in Ada is however quite different here. In C, the for statement is virtually the same as the while statement as the condition in the C for statement is checked in each iteration and the number of iterations therefore cannot be determined upfront. In Ada for statement, the number of iterations are fixed the first time the control hits the for statement and is specified by a range just like the choice_list in the case statement as shown below: for variable in low_value.. high_value loop -- Loop body goes here end loop; The value of the loop variable can be used but cannot be changed inside the loop body. The loop counting can be done in the reverse order as well. This is shown below. for variable in reverse high_value.. low_value loop -- Loop body goes here end loop; Exit statement The exit statement can be used with our without a when condition as mentioned in the case of the loop statement. exit; exit when condition; It can only be used in a loop. It can use labels and can be used to specify the specific loop to exit as shown below. Outer : loop Inner : loop … exit Inner when Done; end loop Inner; end loop Outer; Block Statement Block statement in Ada is very similar to a block in C. It can be used anywhere and has the following structure: declare -- declare section optional declarations 56 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU begin statements exception -- exception section optional handlers end; Return statement The return statement can only be used in subprograms and has the following form: return; -- procedure return expression; -- function Function must have at least one return. Raise statement Raise statement is like throw statement in C++ and is used to raise exception as shown below: raise exception-name; Declaring and Handling Exceptions Ada was the first language to provide a structured exception handling mechanism. C++ exception handling is very similar to Ada. In Ada, the programmer can declare, raise, and handle exception. Declaring an exception Exceptions are declared just like any other variable before they can be raised. This is shown in the following example: Error, Disaster : exception; Raising an exception Like throw in C++, an Ada programmer can explicitly raise an exception and it strips stack frames till a handler is found. raise Disaster; Handling an exception Like C++, an exception handling code may be written at the end of a block. Anywhere we have begin-end, we can also have an exception handling code. The structure of exception handling part is shown in the following example. begin statements 57 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU exception when exception1 => statements; when exception2 => statements; end; Subprograms In Ada, there are two types of subprograms: procedures and functions. Unlike C, we can also have nesting of subprograms. A subprogram defined inside another subprogram an be used by its parent, children, or sibling subprograms only. This is demonstrated in the following example: Procedure My_procedure(x, y : IN OUT integer) is … function aux_func(a : Integer) return integer is Temp : float; begin … return integer(temp) * a; -- retrun temp * a is not allowed end aux_func; … begin -- begin of My_procedure … aux_func(x); … end My_procedure; Packages The primary structure used for encapsulation in Ada is called a package. Packages are used to group data and subprograms. Packages can be hierarchical, allowing a structured and extensible relationship for data and code. All the standard Ada libraries are defined within packages. Package definitions usually consist of two parts: package specification and package body. Package bodies can also declare and define data types, variables, constants, functions, and procedures not declared in the package specification. In the following example, a STACK package is defined. We first the have the package specification as follows: package STACK is procedure PUSH (x : INTEGER); function POP return INTEGER; end STACK; The body of the package is shown below. package body STACK is MAX: constant := 100; S : array (1..MAX) of INTEGER; TOP : INTEGER range 0..MAX; 58 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU procedure PUSH (x : INTEGER) is begin TOP := TOP + 1; S(TOP) := x; end PUSH; function POP return integer is TOP := TOP - 1; return S(TOP + 1); end POP; begin TOP := 0; end STACK; Once defined, a package can be used in the client program as follows: with STACK; use STACK; procedure myStackExample is I, O : integer; begin … push(i); … O := pop; … end myStackExample; Object-Orientation – The Ada Way Ada provides tools and constructs for extending types through inheritance. In many object oriented languages the concept of a class is overloaded. It is both the unit of encapsulation and a type definition. Ada separates these two concepts. Packages are used for encapsulation and Tagged types are used to define extensible types. Tagged Type A tagged type is like a record which can be used to declare objects. Following is an example of a tagged type: type Person is tagged record Name : String(1..20); Age : Natural; end record; Such a type definition is performed in a package. Immediately following the type definition must be the procedures and functions comprising the primitive operations defined for this type. Primitive operations must have one of its parameters be of the tagged type, or for functions the return value can be an instance of the tagged type. It 59 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU allows you to overload functions based upon their return type. It may be noted that C++ and Java do not allow you to overload based upon the return type of a function. Extending Tagged Types Just like classes in C++, the tagged type can be extended by making a new tagged record based upon the original type as shown below: type Employee is new Person with record Employee_Id : Positive; Salary : Float; end record; In this example, type Employee inherits all the fields and primitive operations of type Person. Generics Generics are like templates in C++ and allow parameterization of subprograms and packages with parameters which can be types and subprograms as well as values and objects. The following example elaborates the concept of generics. generic MAX : positive; type item is private; package STACK is procedure PUSH (x : item); function POP return item; end STACK; Note that the type of the item is left unspecified. The corresponding body of STACK package is as follows: package body STACK is S : array (1..MAX) of item; TOP : INTEGER range 0..MAX; procedure PUSH (x : item) is begin … end PUSH; function POP return item is … end POP; begin TOP := 0; end STACK; Once we have the generic definition, we can instantiate our own STACK for the given type which is integer in the following example. 60 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU declare package myStack is new STACK(100, integer); use myStack; begin … push (i); … O := pop; … end; Concurrency Ada Tasking allows the initiation of concurrent tasks which initiates several parallel activities which cooperate as needed. Its syntax is similar to packages as shown below: task thisTask is …-- interfaces end thisTask; task body thisTask is … end thisTask; task simpleTask; -- this task does not provide an interface to other tasks Here is a very simple example that demonstrates the concept of parallel processing. In this example we specify COOKING a procedure composed of three steps. procedure COOKING is begin cookMeat; cookRice; cookPudding; end COOKING; As these steps can be carried out in parallel, we define tasks for these tasks as shown below: procedure COOKING is task cookMeat; task body cookMeat is begin -- follow instructions for cooking meat end cookMeat; task cookRice; task body cookRice is begin -- follow instructions for cooking rice 61 © Copyright Virtual University of Pakistan Ada Programming Language: An Introduction (Lecture 13-17) VU end cookRice; begin cookPudding; end COOKING; Other Features Ada is a HUGE language and we have looked at may be only 25-30% of this language. It is to be remembered that the main objective of the Ada design was to incorporate the contemporary software engineering knowledge in it. In general, software development time is: 10% design, 10% coding, 60% debug and 20% test. Last 80% of the project is spent trying to find and eliminate mistakes made in the first 20% of the project. Therefore Ada promised to spend 20% time in design, 60% in coding, 10% in debug, and 10% in testing. Therefore cutting the entire cycle time in half! I would like to finish with a quote from Robert Dewar: “ When Roman engineers built a bridge, they had to stand under it while the first legion marched across. If programmers today worked under similar ground rules, they might well find themselves getting much more interested in Ada. “ 62 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU LISP Programming Language: An Introduction (Lecture 18-21) Functional Programming Paradigm and LISP Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style. LISP is a representative language of this style of programming. Lisp stands for “LISt Process”. It was invented by John McCarthy in 1958 at MIT. It has simple data structure (atoms and lists) and makes heavy use of recursion. It is an interpretive language and has many variations. The two most popular versions are Scheme and Common Lisp (de facto industrial standard). It is the most widely used AI programming language. Valid Objects A LISP program has two types of elements: atoms and lists. Atoms: Atoms include numbers, symbols, and strings. It supports both real numbers and integers. symbols: a symbol in LISP is a consecutive sequence of characters (no space). For example a, x, and price-of-beef are symbols. There are two special symbols: T and NIL for logical true and false. strings: a string is a sequence of characters bounded by double quotes. For example "this is red" is a string. S-expression An S-expression (S stands for symbolic) is a convention for representing data or an expression in a LISP program in a text form. It is characterized by the extensive use of prefix notation with explicit use of brackets (affectionately known as Cambridge Polish notation). S-expressions are used for both code and data in Lisp. S-expressions were originally intended only as machine representations of human-readable representation of symbols, but Lisp programmers soon started using S-expressions as the default notation. S-expressions can either be single objects or atoms such as numbers, or lists. Lists List is the most important concept in LISP. A list is a group of atoms and/or lists, bounded by ( and ). For example (a b c) and (a (b c)) are two lists. In these examples the list (a b c) is a list of atoms a, b, and c, whereas (a (b c)) is a list of two elements, the first one an atom a, and the second one a list (b c). 63 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU Top elements of a list The first-level elements in LISP are called top-level elements. For example top elements of list (a b c) are a, b, and c. Similarly, top elements of list (a (b c)) are a and (b c). An empty list is represented by nil. It is the same as (). Function calls In LISP, a function and a function call is also a list. It uses prefix notation as shown below: (function-name arg1... argn) A function call returns function value for the given list of arguments. Functions are either provided by LISP function library or defined by the user. Following are some examples of function calls. Note that the first symbol is the name of the function and the rest are its arguments. >(+ 1 3 5) 9 Note that the arithmetic functions may take more than two arguments. >(/ 3 5) 3/5 When we use two integers in division, the answer is converted into fraction. >(/ 3.0 5) 0.59999999999999998 Note the difference between integer and real division. >(sqrt 4) 2 Evaluation of S-expression S-expressions are evaluated as follows: 1) Evaluate an atom. numerical and string atoms evaluate to themselves; symbols evaluate to their values if they are assigned values, return Error, otherwise; the values of T and NIL are themselves. 2) Evaluate a list evaluate every top element of the list as follows, unless explicitly forbidden: 64 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU the first element is always a function name; evaluating it means to call the function body; each of the rest elements will then be evaluated, and their values returned as the arguments for the function. Examples: 1. >(+ (/ 3 5) 4) 23/5 The first element is + so we make a call to + function with (/ 3 5) and 4 as arguments. Now (/ 3 5) is evaluated and the answer is 3/5. After that 4 is evaluated to itself and thus returns 4. So, 3/5 and 4 are added to return 23/5. 2. >(+ (sqrt 4) 4.0) 6.0 This example is similar to the first example. 3. >(sqrt x) Error: The variable X is unbound. This code generates an error as the symbol x is not associated with any value and thus cannot be evaluated. setq, set, and setf are used to assign a value to a symbol. For example, the following code assigns a value 3 to symbol x. >(setq x 3.0) 3.0 setq is a special form of function (with two arguments). The first argument is a symbol which will not be evaluated and the second argument is a S-expression, which will be evaluated. The value of the second argument is assigned to be the value of the first argument. To forbid evaluation of a symbol a quote or ’ is used. For example >(quote x) x Similarly if we have >(setq x 3.0) 3.0 65 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU and then we do >(setq y x) 3.0 then y will also have a value 3.0 But if we use a quote as shown below (cons 'x L) ; insert symbol x at the front of list L, which is (X A B C) ; (A B C) list takes arbitrary number of arguments and makes a list of these arguments as shown below: >(list 'a 'b 'c) ; making a list with the arguments as its elements (A B C) ; if a, b, c have values A, B, C, then (list a b c) returns list (A B C) append takes two lists as arguments and appends one list in front of the other as shown below: >(append '(a b) '(c d)) (A B C D) ; appends one list in front of another List Selectors In order to select elements from a list, selectors functions are used. There are two basic selector functions known as first (or car) and rest (or cdr). The rest can be build with the help of these functions. 66 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU first (or car) takes a list as an argument and returns the first element of that list as shown in the following examples: >(first '(a s d f)) a >(first '((a s) d f)) (a s) >(setq L '(A B C)) (A B C) >(car L) A rest (or cdr) takes a list as its argument and returns a new list after removing the first element from the list. This is demonstrated in the following examples: >(rest '(a s d f)) (s d f). >(rest '((a s) d f)) (d f) >(rest '((a s) (d f)) ((d f)) >(setq L '(A B C)) (A B C) >(cdr L) (B C) Some of the other useful list manipulation functions are: >(reverse L) ; reverses a list (C B A) and >(length L) ; returns the length of list L 3 Predicates A predicate is a special function which returns NIL if the predicate is false, T or anything other than NIL, otherwise. Predicates are used to build Boolean expressions in the logical statements. The following comparative operators are used as functions for numerical values and return a T or NIL. =, >, =, (- 5 2) (+ 3 1)) ¾ NIL For non numeric values you can only check for equality using equal or eq. Some other useful predicates are listed below: atom: test if x is an atom listp: test if x is a list Also number, symbolp, null can be used to test whether the operand is a number, symbol, or a null value. Set Operations A list can be viewed as a set whose members are the top elements of the list. The list membership function is a basic function used to check whether an element is a member of a list or not. It is demonstrated with the help of the following code: >(setq L '(A B C)) >(member 'b L) ; test if symbol b is a member (a top element) of L (B C) ; if yes, returns the sublist of L starting at the ; first occurrence of symbol b >(member ‘b (cons 'b L)) (B A B C) Note here that the mathematical definition of a set is different from the LISP definition. In Mathematics, a symbol cannot be repeated in a set whereas in LIST there is no such restriction. If an element is not present in the list, it returns NIL as shown below. >(member x L) NIL ; if no, returns NIL Some of the other set operations are defined as below: >(union L1 L2) ; returns the union of the two lists >(intersection L1 L2) ; returns the intersection of the two lists >(set-difference L1 L2) ; returns the difference of the two lists 68 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU Defining LISP functions In LISP, defun is used to write a user-defined function. Note that different dialects of LISP may use different keywords for defining a function. The syntax of defun is as below: (defun func-name (arg-1... Arg-n) func-body) That is, a function has a name, list of arguments, and a body. A function returns the value of last expression in its body. This concept is demonstrated with the help of the following example: >(defun y-plus (x) (+ x y)) ;definition of y-plus This function adds x to y where x is the parameter passed to the function and y is a global variable since it is not defined inside the function. It work in the following manner: >(setq y 2) >(y-plus 23) 25 With this we introduce the concept of local and global variables. Local variables are defined in function body. Everything else is global. Conditional control: if, when and cond LISP has multiple conditional control statements. The set includes if, when, and cond. In the following pages we study these statements one by one. if statement The if statement has the following syntax: (if ) That is, an if statement has three parts: the test, the then part, and the else part. It works almost exactly like the if statement in C++. If the test is TRUE then the then part will be executed otherwise the else part will be executed. If there is no else part then if the test is not true then the if statement will simply return NIL. Here is an example that shows the if statement: > (setq SCORE 78) > 78 > (if (> score 85) ‘HIGH (if (and (< score 84) (> score 65)) ‘MEDIUM ‘LOW)) > MEDIUM In the above if statement, the then part contains ‘HIGH and the else part is another if statement. So, with the help of nested if statements we can develop code with multiple branches. 69 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU cond statement The cond statement in LISP is like the switch statement in C++. There is however a slight different as in this case each clause in the cond requires a complete Boolean test. That is, just like multiple else parts in the if statement where each needs a separate condition. Syntax of cond is as shown below: >(cond ( ) ( )... ( )) Each ( ) is called a clause. If test-i (start with i=1) returns T (or anything other than NIL), this function returns the value of action-i, else, it goes to the next clause. Usually, the last test is T, which always holds, meaning otherwise. Just like the if statement, cond can be nested (action-i may contain (cond...)) This statement is explained with the help of the following example: > (setf operation ‘area L 100 W 50) > 50 > (cond ((eq operation ‘perimeter) (* 2 (+ L W))) (eq operation ‘area) (* L W)) (t ‘i-do-not-understand-this) ) ) > 5000 This program has three clauses. The first one checks whether the operation is the calculation of the perimeter or not. In this case it uses the length and width to calculate the perimeter. The control will come to the second clause if the first test is evaluated to be false or NIL. The second clause checks if the operation is about area and if it is true then it will calculate area. The third clause is the default case which will always be true. So if the first two tests fail, it will print ‘i-do-not-understand-this 70 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU Recursion Recursion is the main tool used for iteration. In fact, if you don’t know recursion, you won’t be able to go too far with LISP. There is a limit to the depth of the recursion, and it depends on the version of LISP. Following is an example of a recursive program in LISP. We shall be looking at a number of recursive functions in the examples. (defun power (x y) (if (= y 0) 1 (* x (power x (1- y))))) This function computes the power of x to y. That is, it computes xy by recursively multiplying x with itself y number of times. So >(power 3 4) 81 Let us look at another example. In this example, we compute the length of a list, that is, we compute the number of elements in a list. The function is given as follows: (defun length (x) (if (null x) 0 (+ length (rest x) 1) ) ) > (Length ‘(a b c d)) >4 Here are some more examples: The first function determines whether a symbol is present in a list or not and the second function computes the intersection of two lists. These functions are given below: (defun member (x L) ; determine whether x is in L or not (cond ((null L) nil) ; base case 1: L is empty ((equal x (car L)) L) ; base case 2: x=first(L) (t (member x (cdr L))) ; recursion: test if x is in rest(L) )) (defun intersection (L1 L2) ; compute intersection of two lists (cond ((null L1) nil) ((null L2) nil) ((member (car L1) L2) (cons (car L1) (intersection (cdr L1) L2))) (t (intersection (cdr L1) L2)) )) It may be noted that the intersection function is different from the mathematical definition of set intersection. In this case the function looks at all the elements of the first list, one at 71 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU a time, and checks whether that element is present in the second list. You may recall from our earlier discussion that our definition of set if different from the mathematical definition of a set where duplications are not allowed. This concept is elaborated with the help of the following examples where you pass same lists in different order and get different results. > (intersection '(a b c) '(b a b c)) > (a b c) > (intersection '(b a b c) '(a b c)) > (b a b c) Following is yet another example to compute the set difference of two sets. (defun set-difference (L1 L2) (cond ((null L1) nil) ((null L2) L1) ((not (member (car L1) L2)) (cons (car L1) (set-difference (cdr L1) L2))) (t (set-difference (cdr L1) L2)) )) Iteration: dotimes and dolist Apart from recursion, in LISP we can write code involving loops using iterative non- recursive mechanism. There are two basic statements for that purpose: dotimes and dolist. These are discussed in the following paragraphs. dotimes dotimes is like a counter-control for loop. Its syntax is given as below: (dotimes (count n result) body) It executes the body of the loop n times where count starts with 0, ends with n-1. The result is optional and is to be used to hold the computing result. If result is given, the function will return the value of result. Otherwise it returns NIL. The value of the count can be used in the loop body. dolist The second looping structure is dolist. It is used to iterate over the list elements, one at a time. Its syntax is given below: (dolist (x L result) body) 72 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU It executes the body for each top level element x in L. x is not equal to an element of L in each iteration, but rather x takes an element of L as its value. The value of x can be used in the loop body. As we have seen in the case of dotimes, the result is optional and is to be used to hold the computing result. If result is given, the function will return the value of result. Otherwise it returns NIL. To understand these concepts, let us look at the following examples: > (setf cold 15 hot 35) > 35 The following function use dolist to computes the number of pleasant days, that is, between cold and hot. > (defun count-pleasant (list-of-temperatures) (let ((count-is 0)) ; initialize (dolist (element my-list count-is) (when (and (< element hot) (> element cold)) (setf count-is (+ count-is 1)))))) > (count-pleasant ‘(30 45 12 25 10 37 32)) >3 Here is a very simple example which uses dotimes: > (defun product-as-sum (n m) (let ((result 0)) (dotimes (count n result) (setf result (+ result m))))) > (product-as-sum 3 4) > 12 Property Lists Property lists are used to assign/access properties (attribute-value pairs) of a symbol. The following functions are used to manipulate a property list. To assign a property: (setf (get object attribute) value) To obtain a property: (get object attribute) To see all the properties; (symbol-plist object) Here is an example that elaborates this concept: >(setf (get 'a 'height) 8) ; cannot use "setq" here ; setting the height property of symbol a. 8 73 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU >(get 'a 'height) ; setting the height property of symbol a. 8 >(setf (get ‘a ‘weight) 20) ; setting the weight property of symbol a. 20 Now we list all properties of a: >(symbol-plist ‘a) (WEIGHT 20 HEIGHT 8) We can remove a property by using the remprop function as shown below: > (remprop ‘a ‘WEIGHT) T >(symbol-plist ‘a) (HEIGHT 8) > (remprop ‘a ‘HEIGHT) T >(symbol-plist ‘a) NIL We can use the property list to build more meaningful functions. Here is one example: Assume that if the name of a person’s father is known, the father’s name is given as the value of the father property. We define a function GRANDFATHER that returns the name of a person’s paternal grandfather, if known, or NIL otherwise. This function is given below: (defun grandfather (x) (if (get x ‘father) (get (get x ‘father) ‘father) nil)) We now make a list of the paternal line: (defun lineage (x) (if x (cons (x (lineage (get x ‘father)))))) The following would trace the family line from both father and mother’s side: 74 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU (defun ancestors (x) (if x (cons x (append (ancestors (get x ‘father)) (ancestors (get x ‘mother)))))) Arrays Although the primary data structure in LISP is a list, it also has arrays. These are data type to store expressions in places identified by integer indexes. We create arrays by using the linear-array function as shown below: (setf linear-array (make-array ‘(4))) This statement creates a single dimension array of size 4 by the name of linear-array with indices from 0 to 3. Here is an example of a two-dimensional array: (setf chess-board (make-array ‘(8 8))) Once created, we can store data at the desired index as follows: (setf (aref chess-board 0 1) ‘WHITE-KNIGHT) (setf (aref chess-board 7 4) ‘BLACK-KING) Here, aref is the array reference. The above statements say that store symbol WHITE- KNIGHT at chess-board position 0 1 and store BLACK-KING at position 7 4. aref can be used to access any element in the array as shown below: (aref chess-board 0 2) WHITE-BISHOP (aref chess-board 7 2) BLACK-BISHOP What made Lisp Different? LISP was one of the earliest programming language. It was designed at MIT for artificial intelligence and it has since been the defacto standard language for the AI community, especially in the US. LISP program composed of expression. They are in fact trees of expression, each of which returns a value. It has Symbol types: symbols are effectively pointer to strings stored in a hash table. One very important aspect of LISP is that the whole language is there. That is, there is no real distinction between read-time, compile-time and runtime. You can compile or run code while reading, read or run code while compiling, and read or compile code at runtime. That is, programs are expressed directly in the parse trees that get build behind the scenes when other languages are parsed, and these trees are make of 75 © Copyright Virtual University of Pakistan LISP Programming Language: An Introduction (Lecture 18-21) VU lists, which are Lisp date structures. This provides a very powerful feature allowing the programmer to write programs that write programs. From a programming language design point of view, LISP was the first to introduce the following concepts: Conditionals: such as if-then-else construct. Function types: where functions are just like integers and strings Recursion: first language to support it. Dynamic typing: all variable are pointers. Garbage-Collection. Programs composed of expressions. A symbol type. The whole program is a mathematical function 76 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Modern Programming Languages Lecture 22-26 PROLOG - Programming in Logic An Introduction PROLOG stands for PROgramming in LOGic and was design in 1975 by Phillippe Roussell. It is a declarative programming language and is based upon Predicate Calculus. A program in PROLOG is written by defining predicates and rules and it has a built-in inference mechanism. Unfortunately, there is no effective standardization available. PROLOG Paradigm As mentioned earlier, PROLOG draws inferences from facts and rules. It is a declarative language in which a programmer only specifies facts and logical relationships. It is non- procedural. That is we only state "what" is to be done and do not specify "how" to do it. That is, we do not specify the algorithm. The language just executes the specification. In other words, program execution is carried out as a theorem proving exercise. It is similar to SQL used in databases with automated search and the ability to follow general rules. One of the main features of this language is its ability to handle and process symbols. Hence it is used heavily in AI related applications. It is an interactive (hybrid compiled/interpreted) language and its applications include expert systems, artificial intelligence, natural language understanding, logical puzzles and games. PROLOG Programming PROLOG programming follows the following steps: Declaring some facts about objects and their relationships Defining some rules about objects and their relationships Asking questions about objects and their relationships The PROLOG Programmer loads facts and rules into the database and makes queries to the database to see if a fact is in the database or can be implied from the facts and rules therein. This is depicted in the following diagram. 77 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Facts Facts are used to represent unchanging information about objects and their relationships. Only facts in the PROLOG database can be used for problem solving. A programmer inserts facts into the database by typing the facts into a file and loading (consulting) the file into a running PROLOG system. Queries Queries are used to retrieve information from the database. A query is a pattern that PROLOG is asked to match against the database and has the syntax of a compound query. It may contain variables. A query will cause PROLOG to look at the database, try to find a match for the query pattern, execute the body of the matching head, and return an answer. Logic Programming Logic programming is a form of declarative programming. In this form, a program is a collection of axioms where each axiom is a Horn clause of the form: H :- B1, B2,..., Bn. where H is the head term and Bi are the body terms, meaning H is true if all Bi are true. A user of the program states a goal (a theorem) to be proven. The logic programming system attempts to find axioms using inference steps that imply the goal (theorem) is true. The basic proof technique is Modus Ponens i.e. A -> B (If A is true then B is also true but it does not mean that if B is true then A is also true) If Fact is given that A is true Then B is also true Resolution To deduce a goal (theorem), the logic programming system searches axioms and combines sub-goals. For this purpose we may apply forward (from fact to goal) or backward (from goal to fact) chaining. For example, given the axioms: C :- A, B. D :- C. Given that A and B are true, forward chaining (from fact to goal) deduces that C is true because C :- A, B and then D is true because D :- C. 78 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Backward chaining (from goal to fact) finds that D can be proven if sub-goal C is true because D :- C. The system then deduces that the sub-goal is C is true because C :- A, B. Since the system could prove C it has proven D. Prolog Uses backward chaining because it is more efficient than forward chaining for larger collections of axioms. Examples Let us look at some examples of facts, rules, and queries in Prolog. Facts Following table shows some example of facts. English PROLOG “A dog is a mammal” isa(dog, mammal). “A sparrow is a bird” isa(sparrow, bird). Rules Here are some examples of rules. English PROLOG “Something is an animal animal(X) :- isa(X, bird). if it is a mammal or a bird” animal(X) :- isa(X,mammal). Queries An now some queries: English PROLOG “is a sparrow an animal?” ?- animal(sparrow). answer: “yes” yes “is a table an animal?” ?- animal(table). answer: “no” no “what is a dog?” ?- isa(dog, X). answer: “a mammal” X = mammal ------------------------------------END OF LECTURE 22------------------------------------------- 79 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU PROLOG syntax Constants There are two types of constants in Prolog: atoms and numbers. Atoms: Alphanumeric atoms - alphabetic character sequence starting with a lower case letter. Examples: apple a1 apple_cart Quoted atoms - sequence of characters surrounded by single quotes. Examples: ‘Apple’ ‘hello world’ Symbolic atoms - sequence of symbolic characters. Examples: & < > * - + >> Special atoms. Examples: ! ; [ ] {} Numbers: Numbers include integers and floating point numbers. Examples: 0 1 9821 -10 1.3 -1.3E102. Variable Names In Prolog, a variable is a sequence of alphanumeric characters beginning with an upper case letter or an underscore. Examples: Anything _var X _ Compound Terms (structures) A compound term is an atom followed by an argument list containing terms. The arguments are enclosed within brackets and separated by commas. Example: isa(dog, mammal) Comments In Prolog % is used to write a comment just like // in C++. That is after % everything till the end of the line is a comment. Important points to note The names of all relationships and objects must begin with a lower case letter. o For example studies, ali, programming The relationship is written first and the objects are enclosed within parentheses and are written separated by commas. o For example studies(ali, programming) The full stop character ‘.’ must come at the end of a fact. Order is arbitrary but it should be consistent. 80 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU An Example Prolog Program This program has three facts and one rule. The facts are stated as follows: rainy(columbo). rainy(ayubia). cold(ayubia). The rule is: snowy(X) :- rainy(X), cold(X). Some queries and responses: ?- snowy(ayubia). yes ?- snowy(columbo). no ?- snowy(lahore). No ?- snowy(C). C = ayubia Because rainy (ayubia) and cold (ayubia) are sub-goals that are both true facts in the database, snowy(X) with X=columbo is a goal that fails, because cold(X) fails, triggering backtracking. This inference mechanism based upon back tracking is depicted in the following diagram: 81 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Logic Representation: Propositional Calculus Propositional Logic is a set of Boolean statements. It involves logic connectives such as ¬ ∧ ∨ ⇔ ⇒. Example – a family If we had the following atomic statements: p: Ahmed is father of Belal q: Ahmed is brother of Aslam r : Aslam is uncle of Belal Then the following table shows the meanings in English for some logical statements in propositional calculus: Statement Logical meaning ¬p Ahmed is not father of Belal p∨q Ahmed is father of Belal or Ahmed is brother of Aslam p ∧ q ⇒ r If Ahmed is father of Belal and brother of Aslam then Aslam is uncle of Belal Statements in predicate calculus can be mapped almost directly into prolog as shown below: Sections of Prolog Program Predicates Predicates are declarations of relations or rules. They are just like function prototypes (declaration). A predicate may have zero or more arguments. Example of predicates is: 82 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU man(symbol) family() a_new_predicate (integer, char) Clauses Clauses are definition(s) of Predicate sentence or phrase. It has two types: rules and facts. A rule is a function definition. It may have 0 or more conditions. A fact has all parameters as constants and it cannot contain any condition. Example – Fact: brother(ahmed, chand). Saying that ahmed and chand are brothers. Example – Rule: brother(X,Y):- man(X), man(Y), father(Z,Y), father(Z,X). It says that two symbols, X and Y, are brothers if X is a man and Y is a man and their father is same. Goal Goal is the objective of the program. There can be only and exactly one instance of the goal in a program. It is the only tentative section of the program. It may be thought as the main() function of prolog. The truth value of the goal is the output of the program. Syntactically and semantically, it is just another clause. It may be empty, simple (one goal), or compound (sub-goals). Examples 1. brother(X,chand). % In this case the output will be the name of Chand’s brother. 2. brother(ahmed,chand).% The output will be true or false. 3. brother(X,chand), father(X, Y). % The output will be Chand’s and his children. ------------------------------------END OF LECTURE 23------------------------------------------- Prolog Variables Prolog variable are actually constant placeholders and NOT really variables. That is, a value to a variable can be bound only once and then it cannot be changed. These variables are loosely typed. That is, type of the variable is not defined at compile time. As mentioned earlier, a variable name starts with capital letter or underscore. Here are some examples of variable names: 83 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU ‰ brother(ahmed, Ahmed) % ahmed is a constant whereas Ahmed is a variable ‰ brother(ahmed, _x) % _x is a variable ‰ Brother(ahmed, X) % X is a variable Anonymous variable: The _ is a special variable. It is called the anonymous variable. It is used as a place holder for a value that is not required. For example _ is used as a variable in the following clause: brother(ahmed, _) Other Syntactic Elements Prolog has a number of other syntactic elements. Some of these are listed below: ‰ Special predicates cut ! not(predicate) ‰ Predefined predicates write(arg1[,arg2[,arg3[,arg4[…..]]]]) % for output nl % new line readint(var) % read integer readchar(var) % read char readln(var) % read line into var … many more related to i/o, arithmetic, OS etc ‰ Operators Arithmetic ¾ + - * div / mod Relational ¾ < > = >< PROLOG Lists In Prolog, a list is a sequence of terms of the form [t1, t2, t3, t4,..., tn] where term ti is the ith element of the list Examples: 1. [a,b,c] is a list of three elements a, b and c. 2. [[a,list,of,lists], and, numbers,[1,2,3]] is a four element list, the first and last are themselves lists. 3. [ ] is the ‘empty list’. It is an atom not a list data type. This is a fixed symbol. And it will always have the same meaning that’s why it is treated as atom not list. 84 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Working with Lists 1. Lists are used to build compound data types. 2. A list can have elements of arbitrary type and size. 3. There is no size limits. 4. Representation in prolog is very concise (short). 5. head – tail separator a. The vertical bar ‘|’ is used to separate the head and tail of a list as shown below: [|] b. In this case, head is an element whereas tail is list of the same sort. c. The | has dual purpose in Prolog; it is used for list construction as well as list dismantling. Here as some examples of lists: [a, bc, def, gh, i] % a simple list of five elements [] % an empty list [1,2,3] % a simple list of three elements [1, 2 | ] % same as above; a list of three elements with 1 and 2 as head and % as tail. When you join head and tail you get [1 2 3]. [1 | [2, 3] ] % another way of writing the same thing again. This time the head % is only 1 and the tail is [2 3]. Concatenation of these two gives % [1 2 3]. [1, 2, 3 | [ ] ] % same thing again but with a different head and tail formation Recursion is the basic tool for writing programs in Prolog. Let us now look at some example programs in Prolog using lists. Example 1: Calculating the length of a list by counting the first level elements Domains list = Integer * Predicates length (list, integer) Clauses length([],0). %length of an empty list is zero length ([_|Tail], Len):- Length (Tail, TailLen), %getting the tail length Len = TailLen + 1. %the length of list is 1 plus the % length of tail Goal X = [1,2,3], length(X,Len). 85 © Copyright Virtual University of Pakistan PROLOG - Programming in Logic (Lecture 22-26) VU Example 2: Finding the last and second last element in a list lastElement(X,[X]). % if the list has only one element % then it is the last element lastElement(X,[_|L]) :- lastElement(X,L). % recursive step last_but_one(X,[X,_]). % similar to the above example last_but_one(X,[_,Y|Ys]) :- last_but_one(X,[Y|Ys]). ------------------------------------END OF LECTURE 24------------------------------------------- Example 3: Eliminate consecutive duplicates of list elements. If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. Example: ?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X). X = [a,b,c,a,d,e] Here is the code for this function: compress([],[]). % there is nothing to be compressed in compress([X],[X]). % an empty list or a list with only one % element compress([X,X|Xs],Zs) :- % if the first element is repeated, copy compress([X|Xs],Zs). % it once in the new list compress([X,Y|Ys],[X|Zs]) :- % inspect the rest of the list and X \= Y,compress([Y|Ys],Zs). % repeat the process recursively Sorting Remember, in Prolog, we only specify what we want and not how to do it. Here is a classical example of this specification. In the following program segment, in order to sort a list, we only specify what is meant by sorting and not how to do it. sorted ([ ]). % an empty list or list with only one element sorted ([X]). % is already sorted sorted ([X, Y | list]) :- % recursive step X