Ai Algorithms, Data Structures, And Idioms In Prolog, Lisp, And Java

Luger_all_wcopyright_COsfixed.pd2 2 5/15/2008 6:34:39 PM AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java Luger_all_wcopyright_COsfixed.pd1 1 5/15/2008 6:34:39 PM Luger_all_wcopyright_COsfixed.pd2 2 5/15/2008 6:34:39 PM AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java George F. Luger William A. Stubblefield Luger_all_wcopyright_COsfixed.pd3 3 5/15/2008 6:34:39 PM Executive Editor Acquisitions Editor Editorial Assistant Managing Editor Digital Assets Manager Senior Media Producer Marketing Manager Senior Author Support/ Technology Specialist Senior Manufacturing Buyer Text Design, Composition, and Illustrations Cover Design Cover Image Michael Hirsch Matt Goldstein Sarah Milmore Jeff Holcomb Marianne Groth Bethany Tidd Erin Davis Joe Vetere Carol Melville George F Luger Barbara Atkinson © Tom Barrow Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. Copyright © 2009 Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc., Rights and Contracts Department, 501 Boylston Street, Suite 900, Boston, MA 02116, fax (617) 671-3447, or online at http://www.pearsoned.com/legal/permissions.htm. ISBN-13: 978-0-13-607047-4 ISBN-10: 0-13-607047-7 1 2 3 4 5 6 7 8 9 10—OPM—12 11 10 09 08 Luger_copyright.pdf 1 5/15/2008 6:02:23 PM Contents Preface Part I Chapter 1 ix Language Idioms and the Master Programmer Idioms, Patterns, and Programming 3 1.1 Introduction: Idioms and Patterns 3 1.2 Selected Examples of Language Idioms 6 1.3 A Brief History of Three Programming Paradigms 1.4 A Summary of Our Task Part II Chapter 2 17 19 2.1 Introduction: Logic-Based Representation 2.2 Prolog Syntax 11 15 Programming in Prolog Prolog: Representation 1 19 20 2.3 Creating, Changing, and Tracing a Prolog Computation 2.4 Lists and Recursion in Prolog 25 2.5 Structured Representation and Inheritance Search Exercises Chapter 3 3.1 Introduction Chapter 4 28 32 Abstract Data Types and Search 33 33 3.2 Using cut to Control Search in Prolog 36 3.3 Abstract Data Types (ADTs) in Prolog 38 Exercises 42 Depth- Breadth-, and Best-First Search 4.1 Production System Search in Prolog 43 43 4.2 A Production System Solution of the FWGC Problem 4.3 Designing Alternative Search Strategies Exercises Chapter 5 24 46 52 58 Meta-Linguistic Abstraction, Types, and Meta-Interpreters 5.1 Meta-Interpreters, Types, and Unification 5.2 Types in Prolog 59 61 5.3 Unification, Variable Binding, and Evaluation Exercises 59 64 68 v Luger_all_wcopyright_COsfixed.pd5 5 5/15/2008 6:34:39 PM vi Contents Chapter 6 Three Meta-Interpreters: Prolog in Prolog, EXSHELL, and a Planner 59 6.1 An Introduction to Meta-Interpret