Friday, September 30, 2011

C# switch statement


C# switch statement

I’ve been meaning to write something about multi-way branching (aka switch statements) for a while. I don’t have the time now to go into everything I want to say but I’ll dip my toe into the waters by discussing the C# switch statement.
C# has a switch statement just like the one found in C/C++ and Java. But the C# switch has an important difference: it does not allow fall-through between cases. Unintentional fall-through is a common programming error so this was done to “protect” programmers from this error. Good idea but it turns out that C# does actually allow explicit fall-through by using a new form of goto statement. You can write something like this:
switch (i) {
case 0:
CaseZero();
goto case 1;
case 1:
CaseZeroOrOne();
goto default;
default:
CaseAny();
break;
}
Yuck! What a language wart. It reminds me of the Pascal goto statement whereby you have todeclare the goto label in the prologue of the procedure to use it. (Apparently the label statement is intended as a badge of shame that you had sunk to using a goto statement). I don’t encourage the use of gotos in any language but that’s my point. If you want to disallow fall-through, just do it. Don’t come up with some extended goto syntax to let someone rattle around inside the switch block. The designers would have been better off adding a do-not-break statement to note the fall-though.
The C programming language is an excellent portable high-level assembly language. It was designed primarily as a system programming language. I’ve been writing C code for 20 years so I find C syntax to be comfortable. But do new languages have to swallow everything from C? Java doesn’t have C-style pointers and doesn’t allow any code to exist outside of classes. C# tries to improve the switch by disallowing fall-through and then adds this junk. I guess someone really wants to see an Obfuscated Programming Contest for C#. 

Thursday, September 29, 2011

cognitive sciences


1. History

Attempts to understand the mind and its operation go back at least to the Ancient Greeks, when philosophers such as Plato and Aristotle tried to explain the nature of human knowledge. The study of mind remained the province of philosophy until the nineteenth century, when experimental psychology developed. Wilhelm Wundt and his students initiated laboratory methods for studying mental operations more systematically. Within a few decades, however, experimental psychology became dominated by behaviorism, a view that virtually denied the existence of mind. According to behaviorists such as J. B. Watson, psychology should restrict itself to examining the relation between observable stimuli and observable behavioral responses. Talk of consciousness and mental representations was banished from respectable scientific discussion. Especially in North America, behaviorism dominated the psychological scene through the 1950s. Around 1956, the intellectual landscape began to change dramatically. George Miller summarized numerous studies which showed that the capacity of human thinking is limited, with short-term memory, for example, limited to around seven items. He proposed that memory limitations can be overcome by recoding information into chunks, mental representations that require mental procedures for encoding and decoding the information. At this time, primitive computers had been around for only a few years, but pioneers such as John McCarthy, Marvin Minsky, Allen Newell, and Herbert Simon were founding the field ofartificial intelligence. In addition, Noam Chomsky rejected behaviorist assumptions about language as a learned habit and proposed instead to explain language comprehension in terms of mental grammars consisting of rules. The six thinkers mentioned in this paragraph can be viewed as the founders of cognitive science. For a comprehensive review of the history of cognitive science, see Boden (2006).

2. Methods

Cognitive science has unifying theoretical ideas, but we have to appreciate the diversity of outlooks and methods that researchers in different fields bring to the study of mind and intelligence. Although cognitive psychologists today often engage in theorizing and computational modeling, their primary method is experimentation with human participants. People, usually undergraduates satisfying course requirements, are brought into the laboratory so that different kinds of thinking can be studied under controlled conditions. For example, psychologists have experimentally examined the kinds of mistakes people make in deductive reasoning, the ways that people form and apply concepts, the speed of people thinking with mental images, and the performance of people solving problems using analogies. Our conclusions about how the mind works must be based on more than “common sense” and introspection, since these can give a misleading picture of mental operations, many of which are not consciously accessible. Psychological experiments that carefully approach mental operations from diverse directions are therefore crucial for cognitive science to be scientific.
Although theory without experiment is empty, experiment without theory is blind. To address the crucial questions about the nature of mind, the psychological experiments need to be interpretable within a theoretical framework that postulates mental representations and procedures. One of the best ways of developing theoretical frameworks is by forming and testing computational models intended to be analogous to mental operations. To complement psychological experiments on deductive reasoning, concept formation, mental imagery, and analogical problem solving, researchers have developed computational models that simulate aspects of human performance. Designing, building, and experimenting with computational models is the central method of artificial intelligence (AI), the branch of computer science concerned with intelligent systems. Ideally in cognitive science, computational models and psychological experimentation go hand in hand, but much important work in AI has examined the power of different approaches to knowledge representation in relative isolation from experimental psychology.
While some linguists do psychological experiments or develop computational models, most currently use different methods. For linguists in the Chomskian tradition, the main theoretical task is to identify grammatical principles that provide the basic structure of human languages. Identification takes place by noticing subtle differences between grammatical and ungrammatical utterances. In English, for example, the sentences “She hit the ball” and “What do you like?” are grammatical, but “She the hit ball” and “What does you like?” are not. A grammar of English will explain why the former are acceptable but not the latter.
Like cognitive psychologists, neuroscientists often perform controlled experiments, but their observations are very different, since neuroscientists are concerned directly with the nature of the brain. With nonhuman subjects, researchers can insert electrodes and record the firing of individual neurons. With humans for whom this technique would be too invasive, it has become possible in recent years to use magnetic and positron scanning devices to observe what is happening in different parts of the brain while people are doing various mental tasks. For example, brain scans have identified the regions of the brain involved in mental imagery and word interpretation. Additional evidence about brain functioning is gathered by observing the performance of people whose brains have been damaged in identifiable ways. A stroke, for example, in a part of the brain dedicated to language can produce deficits such as the inability to utter sentences. Like cognitive psychology, neuroscience is often theoretical as well as experimental, and theory development is frequently aided by developing computational models of the behavior of groups of neurons.
Cognitive anthropology expands the examination of human thinking to consider how thought works in different cultural settings. The study of mind should obviously not be restricted to how English speakers think but should consider possible differences in modes of thinking across cultures. Cognitive science is becoming increasingly aware of the need to view the operations of mind in particular physical and social environments. For cultural anthropologists, the main method is ethnography, which requires living and interacting with members of a culture to a sufficient extent that their social and cognitive systems become apparent. Cognitive anthropologists have investigated, for example, the similarities and differences across cultures in words for colors.
With a few exceptions, philosophers generally do not perform systematic empirical observations or construct computational models. But philosophy remains important to cognitive science because it deals with fundamental issues that underlie the experimental and computational approach to mind. Abstract questions such as the nature of representation and computation need not be addressed in the everyday practice of psychology or artificial intelligence, but they inevitably arise when researchers think deeply about what they are doing. Philosophy also deals with general questions such as the relation of mind and body and with methodological questions such as the nature of explanations found in cognitive science. In addition, philosophy concerns itself with normative questions about how people should think as well as with descriptive ones about how they do. In addition to the theoretical goal of understanding human thinking, cognitive science can have the practical goal of improving it, which requires normative reflection on what we want thinking to be. Philosophy of mind does not have a distinct method, but should share with the best theoretical work in other fields a concern with empirical results.
In its weakest form, cognitive science is just the sum of the fields mentioned: psychology, artificial intelligence, linguistics, neuroscience, anthropology, and philosophy. Interdisciplinary work becomes much more interesting when there is theoretical and experimental convergence on conclusions about the nature of mind. For example, psychology and artificial intelligence can be combined through computational models of how people behave in experiments. The best way to grasp the complexity of human thinking is to use multiple methods, especially psychological and neurological experiments and computational models. Theoretically, the most fertile approach has been to understand the mind in terms of representation and computation.

3. Representation and Computation

The central hypothesis of cognitive science is that thinking can best be understood in terms of representational structures in the mind and computational procedures that operate on those structures. While there is much disagreement about the nature of the representations and computations that constitute thinking, the central hypothesis is general enough to encompass the current range of thinking in cognitive science, including connectionisttheories which model thinking using artificial neural networks.
Most work in cognitive science assumes that the mind has mental representationsanalogous to computer data structures, and computational procedures similar to computational algorithms. Cognitive theorists have proposed that the mind contains such mental representations as logical propositions, rules, concepts, images, and analogies, and that it uses mental procedures such as deduction, search, matching, rotating, and retrieval. The dominant mind-computer analogy in cognitive science has taken on a novel twist from the use of another analog, the brain.
Connectionists have proposed novel ideas about representation and computation that use neurons and their connections as inspirations for data structures, and neuron firing and spreading activation as inspirations for algorithms. Cognitive science then works with a complex 3-way analogy among the mind, the brain, and computers. Mind, brain, and computation can each be used to suggest new ideas about the others. There is no single computational model of mind, since different kinds of computers and programming approaches suggest different ways in which the mind might work. The computers that most of us work with today are serial processors, performing one instruction at a time, but the brain and some recently developed computers are parallel processors, capable of doing many operations at once.

4. Theoretical Approaches

Here is a schematic summary of current theories about the nature of the representations and computations that explain how the mind works.

4.1 Formal logic

Formal logic provides some powerful tools for looking at the nature of representation and computation. Propositional and predicate calculus serve to express many complex kinds of knowledge, and many inferences can be understood in terms of logical deduction with inferences rules such as modus ponens. The explanation schema for the logical approach is:
Explanation target:
  • Why do people make the inferences they do?
Explanatory pattern:
  • People have mental representations similar to sentences in predicate logic.
  • People have deductive and inductive procedures that operate on those sentences.
  • The deductive and inductive procedures, applied to the sentences, produce the inferences.
It is not certain, however, that logic provides the core ideas about representation and computation needed for cognitive science, since more efficient and psychologically natural methods of computation may be needed to explain human thinking.

4.2 Rules

Much of human knowledge is naturally described in terms of rules of the form IF … THEN …, and many kinds of thinking such as planning can be modeled by rule-based systems. The explanation schema used is:
Explanation target:
  • Why do people have a particular kind of intelligent behavior?
Explanatory pattern:
  • People have mental rules.
  • People have procedures for using these rules to search a space of possible solutions, and procedures for generating new rules.
  • Procedures for using and forming rules produce the behavior.
Computational models based on rules have provided detailed simulations of a wide range of psychological experiments, from cryptarithmetic problem solving to skill acquisition to language use. Rule-based systems have also been of practical importance in suggesting how to improve learning and how to develop intelligent machine systems.

4.3 Concepts

Concepts, which partly correspond to the words in spoken and written language, are an important kind of mental representation. There are computational and psychological reasons for abandoning the classical view that concepts have strict definitions. Instead, concepts can be viewed as sets of typical features. Concept application is then a matter of getting an approximate match between concepts and the world. Schemas and scripts are more complex than concepts that correspond to words, but they are similar in that they consist of bundles of features that can be matched and applied to new situations. The explanatory schema used in concept-based systems is:
Explanatory target:
  • Why do people have a particular kind of intelligent behavior?
Explanation pattern:
  • People have a set of concepts, organized via slots that establish kind and part hierarchies and other associations.
  • People have a set of procedures for concept application, including spreading activation, matching, and inheritance.
  • The procedures applied to the concepts produce the behavior.
  • Concepts can be translated into rules, but they bundle information differently than sets of rules, making possible different computational procedures.

4.4 Analogies

Analogies play an important role in human thinking, in areas as diverse as problem solving, decision making, explanation, and linguistic communication. Computational models simulate how people retrieve and map source analogs in order to apply them to target situations. The explanation schema for analogies is:
Explanation target:
  • Why do people have a particular kind of intelligent behavior?
Explanatory pattern:
  • People have verbal and visual representations of situations that can be used as cases or analogs.
  • People have processes of retrieval, mapping, and adaptation that operate on those analogs.
  • The analogical processes, applied to the representations of analogs, produce the behavior.
The constraints of similarity, structure, and purpose overcome the difficult problem of how previous experiences can be found and used to help with new problems. Not all thinking is analogical, and using inappropriate analogies can hinder thinking, but analogies can be very effective in applications such as education and design.

4.5 Images

Visual and other kinds of images play an important role in human thinking. Pictorial representations capture visual and spatial information in a much more usable form than lengthy verbal descriptions. Computational procedures well suited to visual representations include inspecting, finding, zooming, rotating, and transforming. Such operations can be very useful for generating plans and explanations in domains to which pictorial representations apply. The explanatory schema for visual representation is:
Explanation target:
  • Why do people have a particular kind of intelligent behavior?
Explanatory pattern:
  • People have visual images of situations.
  • People have processes such as scanning and rotation that operate on those images.
  • The processes for constructing and manipulating images produce the intelligent behavior.
Imagery can aid learning, and some metaphorical aspects of language may have their roots in imagery. Psychological experiments suggest that visual procedures such as scanning and rotating employ imagery, and recent neurophysiological results confirm a close physical link between reasoning with mental imagery and perception.

4.6 Connectionism

Connectionist networks consisting of simple nodes and links are very useful for understanding psychological processes that involve parallel constraint satisfaction. Such processes include aspects of vision, decision making, explanation selection, and meaning making in language comprehension. Connectionist models can simulate learning by methods that include Hebbian learning and backpropagation. The explanatory schema for the connectionist approach is:
Explanation target:
  • Why do people have a particular kind of intelligent behavior?
Explanatory pattern:
  • People have representations that involve simple processing units linked to each other by excitatory and inhibitory connections.
  • People have processes that spread activation between the units via their connections, as well as processes for modifying the connections.
  • Applying spreading activation and learning to the units produces the behavior.
Simulations of various psychological experiments have shown the psychological relevance of the connectionist models, which are, however, only very rough approximations to actual neural networks.

4.7 Theoretical neuroscience

Theoretical neuroscience is the attempt to develop mathematical and computational theories and models of the structures and processes of the brains of humans and other animals. It differs from connectionism in trying to be more biologically accurate by modeling the behavior of large numbers of realistic neurons organized into functionally significant brain areas. In recent years, computational models of the brain have become biologically richer, both with respect to employing more realistic neurons such as ones that spike and have chemical pathways, and with respect to simulating the interactions among different areas of the brain such as the hippocampus and the cortex. These models are not strictly an alternative to computational accounts in terms of logic, rules, concepts, analogies, images, and connections, but should mesh with them and show how mental functioning can be performed at the neural level. The explanatory schema for theoretical neuroscience is:
Explanation target:
  • How does the brain carry out functions such as cognitive tasks?
Explanatory pattern:
  • The brain has neurons organized by synaptic connections into populations and brain areas.
  • The neural populations have spiking patterns that are transformed via sensory inputs and the spiking patterns of other neural populations.
  • Interactions of neural populations carry out functions including cognitive tasks.
From the perspective of theoretical neuroscience, mental representations are patterns of neural activity, and inference is transformation of such patterns.

5. Philosophical Relevance

Some philosophy, in particular naturalistic philosophy of mind, is part of cognitive science. But the interdisciplinary field of cognitive science is relevant to philosophy in several ways. First, the psychological, computational, and other results of cognitive science investigations have important potential applications to traditional philosophical problems in epistemology, metaphysics, and ethics. Second, cognitive science can serve as an object of philosophical critique, particularly concerning the central assumption that thinking is representational and computational. Third and more constructively, cognitive science can be taken as an object of investigation in the philosophy of science, generating reflections on the methodology and presuppositions of the enterprise.

5.1 Philosophical Applications

Much philosophical research today is naturalistic, treating philosophical investigations as continuous with empirical work in fields such as psychology. From a naturalistic perspective, philosophy of mind is closely allied with theoretical and experimental work in cognitive science. Metaphysical conclusions about the nature of mind are to be reached, not by a priori speculation, but by informed reflection on scientific developments in fields such as computer science and neuroscience (Thagard, 2009). Similarly, epistemology is not a stand-alone conceptual exercise, but depends on and benefits from scientific findings concerning mental structures and learning procedures. Even ethics can benefit by using greater understanding of the psychology of moral thinking to bear on ethical questions such as the nature of deliberations concerning right and wrong. Goldman (1993) provides a concise review of applications of cognitive science to epistemology, philosophy of science, philosophy of mind, metaphysics, and ethics. Here are some philosophical problems to which ongoing developments in cognitive science are highly relevant. Links are provided to other relevant articles in this Encyclopedia.
  • Innateness. To what extent is knowledge innate or acquired by experience? Is human behavior shaped primarily by nature or nurture?
  • Language of thought. Does the human brain operate with a language-like code or with a more general connectionist architecture? What is the relation between symbolic cognitive models using rules and concepts and sub-symbolic models using neural networks?
  • Mental imagery. Do human minds think with visual and other kinds of imagery, or only with language-like representations?
  • Folk psychology. Does a person's everyday understanding of other people consist of having a theory of mind, or of merely being able to simulate them?
  • Meaning. How do mental representations acquire meaning or mental content? To what extent does the meaning of a representation depend on its relation to other representations, its relation to the world, and its relation to a community of thinkers?
  • Mind-brain identity. Are mental states brain states? Or can they be multiply realized by other material states? What is the relation between psychology and neuroscience? Is materialism true?
  • Free will. Is human action free or merely caused by brain events?
  • Moral psychology. How do minds/brains make ethical judgments?
  • The meaning of life. How can minds construed naturalistically as brains find value and meaning?
  • Emotions. What are emotions, and what role do they play in thinking?
  • Mental illness. What are mental illnesses, and how are psychological and neural processes relevant to their explanation and treatment?
  • Appearance and reality. How do minds/brains form and evaluate representations of the external world?
  • Social science. How do explanations of the operations of minds interact with explanations of the operations of groups and societies?
Additional philosophical problems arise from examining the presuppositions of current approaches to cognitive science.

5.2 Critique of Cognitive Science

The claim that human minds work by representation and computation is an empirical conjecture and might be wrong. Although the computational-representational approach to cognitive science has been successful in explaining many aspects of human problem solving, learning, and language use, some philosophical critics such as Hubert Dreyfus (1992) and John Searle (1992) have claimed that this approach is fundamentally mistaken. Critics of cognitive science have offered such challenges as:
  1. The emotion challenge: Cognitive science neglects the important role of emotions in human thinking.
  2. The consciousness challenge: Cognitive science ignores the importance of consciousness in human thinking.
  3. The world challenge: Cognitive science disregards the significant role of physical environments in human thinking.
  4. The body challenge: Cognitive science neglects the contribution of embodiment to human thought and action.
  5. The social challenge: Human thought is inherently social in ways that cognitive science ignores.
  6. The dynamical systems challenge: The mind is a dynamical system, not a computational system.
  7. The mathematics challenge: Mathematical results show that human thinking cannot be computational in the standard sense, so the brain must operate differently, perhaps as a quantum computer.
Thagard (2005) argues that all these challenges can best be met by expanding and supplementing the computational-representational approach, not by abandoning it.

5.3 Philosophy of Cognitive Science

Cognitive science raises many interesting methodological questions that are worthy of investigation by philosophers of science. What is the nature of representation? What role do computational models play in the development of cognitive theories? What is the relation among apparently competing accounts of mind involving symbolic processing, neural networks, and dynamical systems? What is the relation among the various fields of cognitive science such as psychology, linguistics, and neuroscience? Are psychological phenomena subject to reductionist explanations via neuroscience? Von Eckardt (1993) and Clark (2001) provide discussions of some of the philosophical issues that arise in cognitive science. Bechtel et al. (2001) collect useful articles on the philosophy of neuroscience.
The increasing prominence of neural explanations in cognitive, social, developmental, and clinical psychology raises important philosophical questions about explanation and reduction. Anti-reductionism, according to which psychological explanations are completely independent of neurological ones, is becoming increasingly implausible, but it remains controversial to what extent psychology can be reduced to neuroscience and molecular biology (see McCauley, 2007, for a comprehensive survey). Essential to answering questions about the nature of reduction are answers to questions about the nature of explanation. Explanations in psychology, neuroscience, and biology in general are plausibly viewed as descriptions of mechanisms, which are systems of parts that interact to produce regular changes (Bechtel and Abrahamsen, 2005; Bechtel, 2008). In psychological explanations, the parts are mental representations that interact by computational procedures to produce new representations. In neuroscientific explanations, the parts are neural populations that interact by electrochemical processes to produce new activity in neural populations. If progress in theoretical neuroscience continues, it should become possible to tie psychological to neurological explanations by showing how mental representations such as concepts are constituted by activities in neural populations, and how computational procedures such as spreading activation among concepts are carried out by neural processes.
Cognitive psychology is increasingly becoming integrated with neuroscience (e.g. Smith and Kosslyn, 2007; Anderson, 2010). Thagard (2010) sees this development as evidence for the mind-brain identity theory according to which mental processes are neural, representational, and computational. Other philosophers dispute such identification on the grounds that minds are embodied in biological systems and extended into the world (e.g. Thompson, 2007; Clark, 2008). However, moderate claims about embodiment are consistent with the identity theory because brain representations operate in several modalities (e.g. visual and motor) that enable minds to deal with the world

Tuesday, September 27, 2011

List Manipulation, artificial intelligence


Chapter 2
List Manipulation


This chapter introduces a special notation for lists, one of the most important data structures in Prolog, and provides some examples for how to work with them.

2.1     Notation
Lists are contained in square brackets with the elements being separated by commas. Heres an example:
[elephant, horse, donkey, dog]
This is the list of the four atoms elephant, horse, donkey, and dog. Elements of lists could be any valid Prolog terms, i.e. atoms, numbers, variables, or compound terms. This includes also other lists. The empty list is written as []. The following is another example for a (slightly more complex) list:
[elephant, [], X, parent(X, tom), [a, b, c], f(22)]

Internal representation.  Internally, lists are represented as compound terms using the functor . (dot). The empty list [] is an atom and elements are added one by one. The list [a,b,c], for example, corresponds to the following term:
.(a, .(b, .(c, [])))

2.2     Head and Tail
The first element of a list is called its head and the remaining list is called the tail. An empty list doesnt have a head. A list just containing a single element has a head (namely that particular single element) and its tail is the empty list.
A variant of the list notation allows for convenient addressing of both head and tail
of a list.  This is done by using the separator | (bar).   If it is put just before the last
term inside a list, it means that that last term denotes another list.  The entire list is

15








16                             Chapter 2.  List Manipulation

then constructed by appending this sub-list to the list represented by the sequence of elements before the bar. If there is exactly one element before the bar, it is the head and the term after the bar is the lists tail. In the next example 1 is the head of the list and [2,3,4,5] is the tail, which has been computed by Prolog simply by matching the list of numbers with the head/tail-pattern.
?- [1, 2, 3, 4, 5] = [Head | Tail]. Head = 1
Tail = [2, 3, 4, 5]
Yes
Note that Head and Tail are just names for variables. We could have used X and Y or whatever instead with the same result. Note also that the tail of a list (more generally speaking: the thing after |) is always a list itself. Possibly the empty list, but definitely a list.  The head, however, is an element of a list.  It could be a list as well, but not necessarily (as you can see from the previous example — 1 is not a list).  The same applies to all other elements listed before the bar in a list.
This notation also allows us to retrieve the, say, second element of a given list.  In the following example we use the anonymous variable for the head and also for the list after the bar, because we are only interested in the second element.
?- [quod, licet, jovi, non, licet, bovi] = [_, X | _]. X = licet
Yes
The head/tail-pattern can be used to implement predicates over lists in a very compact
and elegant way. We exemplify this by presenting an implementation of a predicate that
can be used to concatenate two lists.1  We call it concat_lists/3. When called with the
first two elements being instantiated to lists, the third argument should be matched with
the concatenation of those two lists, in other words we would like to get the following
behaviour:
?- concat_lists([1, 2, 3], [d, e, f, g], X). X = [1, 2, 3, d, e, f, g]
Yes
The general approach to such a problem is a recursive one.  We start with a base case
and then write a clause to reduce a complex problem to a simpler one until the base case
is reached.  For our particular problem, a suitable base case would be when one of the
two input-lists (for example the first one) is the empty list. In that case the result (the
third argument) is simply identical with the second list. This can be expressed through
the following fact:
1Note that most Prolog systems already provide such a predicate, usually called append/3 (see Section 2.3). So you do not actually have to implement this yourself.








Ulle Endriss.  And Introduction to Prolog Programming                                                  17


concat_lists([], List, List).
In all other cases (i.e. in all cases where a query with concat_lists as the main functor
doesn
t match with this fact) the first list has at least one element.  Hence, it can be
written as a head/tail-pattern:
[Elem | List1].  If the second list is associated with
the variable List2, then we know that the head of the result should be Elem and the tail
should be the concatenation of List1 and List2.  Note how this simplifies our initial
problem:  We take away the head of the first list and try to concatenate it with the
(unchanged) second list.  If we repeat this process recursively, we will eventually end
up with an empty first list, which is exactly the base case that can be handled by the
previously implemented fact. Turning this simplification algorithm into a Prolog rule is
straightforward:
concat_lists([Elem | List1], List2, [Elem | List3]) :-
   
concat_lists(List1, List2, List3).
And thats it! The concat_lists/3 can now be used for concatenating two given lists as specified. But it is actually much more flexible than that. If we call it with variables in the first two arguments and instantiate the third one with a list, concat_lists/3 can be used to decompose that list.  If you use the semicolon key to get all alternative solutions to your query, Prolog will print out all possibilities how the given list could be obtained from concatenating two lists.

?- concat_lists(X, Y, [a, b, c, d]).

X = []
Y = [a, b, c, d] ;

X = [a]
Y = [b, c, d] ;

X = [a, b]
Y = [c, d] ;

X = [a, b, c]
Y = [d] ;
X = [a, b, c, d] Y = [] ;

No

Recall that the No at the end means that there are no further alternative solutions.








18                                        Chapter 2.  List Manipulation

2.3    Some Built-in Predicates for List Manipulation
Prolog comes with a range of predefined predicates for manipulating lists. Some of the most important ones are presented here. Note that they could all easily be implemented by exploiting the head/tail-pattern.
length/2: The second argument is matched with the length of the list in the first argu-
         ment. Example:
?- length([elephant, [], [1, 2, 3, 4]], Length). Length = 3
Yes
It is also possible to use length/2 with an uninstantiated first argument. This will generate a list of free variables of the specified length:
?- length(List, 3).
List = [_G248, _G251, _G254]
Yes
The names of those variables may well be different every time you call this query, because they are generated by Prolog during execution time.
member/2: The goal member(Elem, List) will succeed, if the term Elem can be matched
        
with one of the members of the list List. Example:
?- member(dog, [elephant, horse, donkey, dog, monkey]).
Yes
append/3: Concatenate  two  lists.   This  built-in  works  exactly  like  the  predicate
         concat_lists/3 presented in Section
2.2.
last/2: This predicate succeeds, if its second argument matches the last element of the
         list given as the first argument of last/2.
reverse/2: This predicate can be used to reverse the order of elements in a list. The first
        
argument has to be a (fully instantiated) list and the second one will be matched
         with the reversed list. Example:
?- reverse([1, 2, 3, 4, 5], X). X = [5, 4, 3, 2, 1]
Yes
select/3: Given a list in the second argument and an element of that list in the first, this
         predicate will match the third argument with the remainder of that list. Example:
?- select(bird, [mouse, bird, jellyfish, zebra], X). X = [mouse, jellyfish, zebra]
Yes








Ulle Endriss.  And Introduction to Prolog Programming                                                  19

2.4    Exercises
Exercise 2.1.  Write a Prolog predicate analyse_list/1 that takes a list as its argument and prints out the lists head and tail on the screen. If the given list is empty, the predicate should put out an accordant message. If the argument term isnt a list at all, the predicate should just fail. Examples:
?- analyse_list([dog, cat, horse, cow]). This is the head of your list: dog
This is the tail of your list: [cat, horse, cow]
Yes

?- analyse_list([]).
This is an empty list.
Yes
?- analyse_list(sigmund_freud).
No
Exercise 2.2.  Write a Prolog predicate membership/2 that works like the built-in predicate member/2 (without using member/2).
Hint: This exercise, like many others, can and should be solved using a recursive approach and the head/tail-pattern for lists.

Exercise 2.3.  Implement a Prolog predicate remove_duplicates/2 that removes all duplicate elements from a list given in the first argument and returns the result in the second argument position. Example:
?- remove_duplicates([a, b, a, c, d, d], List). List = [b, a, c, d]
Yes

Exercise 2.4.  Write a Prolog predicate reverse_list/2 that works like the built-in predicate reverse/2 (without using reverse/2). Example:
?- reverse_list([tiger, lion, elephant, monkey], List). List = [monkey, elephant, lion, tiger]
Yes
Exercise 2.5.  Consider the following Prolog program:
        
whoami([]).








20                             Chapter 2.  List Manipulation

whoami([_, _ | Rest]) :-
   
whoami(Rest).
Under what circumstances will a goal of the form whoami(X) succeed?

Exercise 2.6.  The objective of this exercise is to implement a predicate for returning the last element of a list in two different ways.
(a) Write a predicate last1/2 that works like the built-in predicate last/2 using a
      
recursion and the head/tail-pattern of lists.
(b) Define a similar predicate last2/2 solely in terms of append/3, without using a
      
recursion.
Exercise 2.7.  Write a predicate replace/4 to replace all occurrences of a given element (second argument) by another given element (third argument) in a given list (first argument). Example:
?- replace([1, 2, 3, 4, 3, 5, 6, 3], 3, x, List). List = [1, 2, x, 4, x, 5, 6, x]
Yes

Exercise  2.8.  Prolog lists without duplicates can be interpreted as sets.  Write a
program that given such a list computes the corresponding power set.  Recall that the
power set of a set S is the set of all subsets of S. This includes the empty set as well as
the set S itself.
Define a predicate power/2 such that, if the first argument is instantiated with a
list, the corresponding power set (i.e. a list of lists) is returned in the second position.
Example:
?-   power([a, b, c], P).
P = [[a, b, c], [a, b], [a, c], [a], [b, c], [b], [c], []]
Yes
Note: The order of the sub-lists in your result doesnt matter.