I have a stream, which is just going to generate a lot of output, and
I want to stuff it all into a string. (The stream could be a process
or a file). What's a good way to do this? I need to avoid any
interpretation of the input. Right now I use (f is the stream)
(let
(
(c nil) ;character read
(str ;holder for input
(make-array 2048
:element-type 'character :fill-pointer 0 :adjustable t
)))
(while (not (eq 'eof (setq c (read-char f nil 'eof))))
(when (not (vector-push c str))
(setq str (adjust-array str (+ 2048 (length str))))
(vector-push c str)
))
(concatenate 'string str)
)
but this seems ugly and painful.
--
Alan M. Carroll <-- Another casualty of applied metaphysics
Epoch Development Team
Urbana Il. "I hate shopping with the reality-impaired" - Susan
In article <····················@m.cs.uiuc.edu> ·······@cs.uiuc.edu (Alan M. Carroll) writes:
> (let
> (
> (c nil) ;character read
> (str ;holder for input
> (make-array 2048
> :element-type 'character :fill-pointer 0 :adjustable t
> )))
> (while (not (eq 'eof (setq c (read-char f nil 'eof))))
> (when (not (vector-push c str))
> (setq str (adjust-array str (+ 2048 (length str))))
> (vector-push c str)
> ))
The preceding four lines are equivalent to
(vector-push-extend c str 2048)
> (concatenate 'string str)
I don't understand this last line; is it just to get the contents of the
string copied into a simple string?
> )
>
>but this seems ugly and painful.
Unfortunately, portable Common Lisp doesn't provide any better way to do
what you want.
If efficiency is a concern, many vendors provide implementation-dependent
I/O functions that take an array and read or write it in a single,
(hopefully) efficient operation, but there has been no standardization
effort on this (I don't think anyone consciously decided to leave it out,
it was just never brought up). Some also provide documented ways to access
the I/O buffers directly, so you don't even have to copy to intermediate
arrays.
To hide all this implementation-dependency from the main body of your
program, you can write a READ-STRING function that provides the interace
you want. Then use conditional compilation to invoke the
implementation-dependent functions on those systems you're familiar with,
and fall back to the above definition as a default.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
We have recently published a textbook
(Kreutzer & McKenzie RProgramming for Artificial Intelligence - Methods, Tools and ApplicationsS - Addison Wesley 1990 - 680 pages)
which explores a variety of programming styles and metaphors which have originally evolved within the AI community. The emphasis is on Scheme, but flavor systems, Prolog and Smalltalk are also discussed in some depth.
For your interest I include a synopsis. The Software for this book is available by request from the authors.
==========================================================
W. Kreutzer: wolfgang @ cosc.canterbury.ac.nz
B.J. McKenzie: bruce @ cosc.canterbury.ac.nz
==========================================================
PREFACE:
People strive to understand a world by building mental models of structures and events, whose "recognition" is largely determined by the theories, methodologies and metaphors they subscribe to. There is no "unbiased" problem analysis without some methodological frame to guide us, and the importance of
appropriate frames of reference and structuring tools can therefore hardly be overstated. Programming languages and metaphors provide such a context, and a sufficiently "deep" understanding of a rich repertoire of tools with different orientations offers the best chance for less biased approaches to problem solving. To lay such a foundation for the development of knowledge-based systems is the purpose of this book.
This book is not about Artificial Intelligence (AI) as such, although many examples of typical AI applications will be given. Our central concern lies with Articifial Intelligence as a practical activity and the many interesting tools, metaphors and styles of program development which have evolved in this area over the last 30 years. Managing complexity is a crucial issue in problem solving programs and systems. Artificial Intelligence has made many contributions to programming technology which had a signi
ficant
impact on this endeavor, and tools and metaphors supporting these strategies have now begun to penetrate other, more traditional areas of computing. The authors subscribe to a view of computing as a laboratory subject. In addition to a solid theoretical grounding and descriptive information about prototypical systems
and applications, a student or practitioner needs to analyze, write and experiment with actual programs to gain some intuition about the strengths and limitations of a particular approach.
The book is structured into three major parts. The first of these will dicuss three major programming tools, while the second reviews a number of paradigmatic programming metaphors. The third part then centers on the important issue of the user interfaces in which programming activities may be embedded.
Two research programs, heuristic search and knowledge based systems, have dominated thirty years of AI's history, and the switch from one to the other occurred sometime in the early to mid 1970s. The introductory chapter gives a brief survey of AI's history and folklore, together with some appreciation of the differences in focus between these two paradigms.
Chapter 2 concentrates on a discussion of the languages and environments which have traditionally been used to write AI applications. Managing complexity by concept encapsulation and layers of interpretation, and an exploratory, experimental style of program development are identified as crucial ingredients of AI programming techniques. The rest of this chapter discusses and exemplifies 3 main programming metaphors within this context: procedural programming, declarative programming, and object-oriented pr
ogramming.
Scheme is used to provide a procedural perspective of the programming process. The reason that we prefer this language over other dialects of Lisp lies in the fact that it offers a well structured, highly orthogonal and powerful framework for reasoning about processes. Procedures are treated as "first class"
entities and can be manipulated in the same fashion as any other data structure. This makes it easy to write procedures building other procedures and to implement object encapsulation. The notion of continuations also offers an elegant way to define new control structures, such as coroutines. In recognition of Common Lisp's
practical importance we will survey of differences between Scheme and an appropriate subset of Common Lisp in one of the appendices.
Prolog exemplifies a contrasting, more declarative approach to program development. Although we do not emphasize the use of Prolog throughout the rest of the book, we have have tried to demonstrate both its strength and weaknesses.
To promote a wider awareness of the many benefits of object-oriented programming is one of our major objectives. In section 2.5 we therefore discuss the basic characteristics of this idea in the context of a Scheme-based flavour system. Object orientation's main benefits are demonstrated by building a simple simulator, a task which also requires the use of concurrency.
Chapter 3 surveys and analyses a number of useful and interesting programming metaphors which have grown out of the last 30 years of AI research. Our approach uses the Scheme language and is based on a number of so called "toolboxes", as collections of typical data types and procedures supporting a particular metaphor. Toolboxes for heuristic search, game playing, pattern matching, associative knowledge bases, production systems, associative networks, frame networks and ATN grammars are described,
discussed and exemplified.
Sophisticated interactive programming environments with graphics support are an important component of AI programming tools. Apart from being the most paradigmatic of all object oriented programming systems, the Smalltalk language also offers one of the most complete and sophisticated programming environments available today. This makes it an appropriate base to investigate the power of user interfaces for exploratory programming in chapter 4. The characteristics of the so called "desktop
metaphor" will be demonstrated, and we will show simple uses of graphics and the MVC metaphor for building window- and menu-based applications.
The book finishes with some "crystal ball gazing" about likely developments in AI programming, and programming technology in general. A set of exercises is associated with each of the chapters, and one of the appendixces offers some sample solution for starred (*) exercises.
The authors of this book subscribe to the notion that learning to use a programming tool requires much more than learning its syntax. It is also necessary to acquire an appreciation of typical patterns of its application and the contexts in which it is utilized. This book does not stress the description of syntactic
conventions or any other information which may easily be obtained from a reference manual. We will instead emphasize issues of style and demonstrate small but typical applications. A large number of examples presents distilled experience, and the reader is invited to browse through them as a gateway to the literature of programs provided by other textbooks and in the relevant journals. To encourage this activity, our programs are often more "verbose" than is customary, with long names for identifiers and
careful
indentation. The program examples have been designed to show both positive and negative aspects of a particular programming style and are intended to offer a basis for some intuition about what is easy or difficult. Advantages and disadvantages of each metaphor are of course also explicitely stated and many pointers for further study are given.
All the programs in this book have been run on a variety of machines. Although an Apple MacIntosh has been used as the main development system, we have also tested most of the programs on a Vax 750, a Sun 3/60, and an IBM PC. Apart from the Concurrent Flavour System discussed in chapter 2.5, we have been very careful to ensure portability. MacScheme, Chez Scheme, T, and PC Scheme are the Scheme versions for which the programs have been tested, and for which machine-readable versions of our toolboxes are av
ailable. Only standard features of Scheme, as defined by Rees & Clinger (1986), have been used, with the exception of a few convenient "extensions", whose implementation for a range of Scheme dialects are given in a "Systems" toolbox. Standard Edinburgh syntax and predicates are used in the Prolog
chapter, and all the Smalltalk code has been tested under both the Xerox VI2.5 image and Apple's VI1 subset.
The source code for the toolbox programs is given in one of the appendices, as are solutions for some of the exercises. There is also an ordering form for a machine readable version of these and a number of additional programs (for Apple MacIntosh, Unix or IBM PC systems), which are made available for a nominal fee.
This book has grown out of a number of lecture course on AI programming, given by one of the authors. It is suitable for a wide range of readerships, including students, computer professionals, and hobbyists. The book requires no prior knowledge of Artificial Intelligence or AI programming. Only some general knowledge of programming, typically in Pascal or a similar language, will be assumed.
CONTENTS:
Preface i
Table of programs ix
Chapter 1 Introduction 1
1.1 From heuristic search to knowledge based systems - a brief history of AI 1
1.2 Heuristic Search - Programs as Puzzle Solvers 5
1.3 Knowledge Representation - Programs as Expert Systems 6
1.4 AI folklore - some famous programs 8
Chapter 2 Tools & Environments for AI-Programming 1
2.1 AI-Programming - Managing Complexity. 1
2.1.1 A Layered Approach to Software Design 2
2.1.2. "Classical" versus "Exploratory" Programming. 5
2.2 From IPL to Lisp Machines - a Historical Perspective. 8
2.3 Procedural Programming - The Lisp Language 14
2.3.1 Historical Evolution and Key Concepts 14
2.3.2 Programming in Scheme 18
2.3.2.1 Overview 19
2.3.2.2 Representation and Interpretation -
Symbols & Values 20
2.3.2.3 Data Types and their Operations 22
2.3.2.4 Guiding the Flow of Control 29
2.3.2.5 Lambda Expressions and Environments 32
2.3.2.6 Procedures - definition, testing, debugging 35
2.3.2.7 Recursion 37
2.3.2.8 Objects & Continuations 41
2.3.2.9 Additional Features 50
2.3.3 Some Comments on Style 51
2.3.4 Summary and Perspective 53
2.3.5 Exercises 55
2.4 Declarative Programming - The Prolog Language 61
2.4.1 Programming in Logic - Historical Evolution
and Key Concepts 61
2.4.2 Programming in Prolog 64
2.4.2.1 Historical Development 64
2.4.2.2 Defining a World - Facts and Rules 67
2.4.2.3 Searching a World - Queries and Bindings 72
2.4.2.4 Search control and the Prolog interpreter. 74
2.4.2.5 Built-In predicates 84
2.4.2.6 List Processing 88
2.4.2.7 Deductive Databases - A Dungeon Master 91
2.4.2.8 Combinatorial Problem Solving -
The Lineland Puzzle 95
2.4.3 Some Comments on Style 102
2.4.4 Summary and Perspective 103
2.4.5 Exercises 107
2.5 Object-Oriented Programming with Flavours 111
2.5.1 Object Encapsulation, Classification and Communi-
cation - Historical Evolution and Key Concepts 111
2.5.2 Programming with Flavors 115
2.5.2.1 History 115
2.5.2.2 The Canterbury Flavour System (C-Flavours) 116
2.5.2.3 The role of concurrency in the
Canterbury Flavour System 121
2.5.2.4 Some remarks on implementation 124
2.5.2.5 A simple flavour-based simulation package 125
2.5.4 Summary and Perspective 139
Chapter 3 Programming Metaphors 1
3.1 From heuristic search to knowledge representation 1
3.2 The state space metaphor 6
3.2.1 Search, planning and problem solving 6
3.2.1.1 The 8-puzzle problem 8
3.2.1.2 State space graphs 8
3.2.1.3 Search strategies 9
3.2.1.4 Blind search 9
3.2.1.5 Heuristic search 10
3.2.1.6 Toolbox outline 12
3.2.1.7 Using the toolbox to solve the
8-puzzle problem 15
3.2.2 Game playing, minimaxing and tree pruning 21
3.2.2.1 The "Dodgem" game problem 21
3.2.2.2 AND/OR trees and the role of an adversary 22
3.2.2.3 Evaluation functions and goals 23
3.2.2.4 The "Minimax" strategy 25
3.2.2.5 Tree pruning and the alpha-beta method 27
3.2.2.6 Toolbox outline 29
3.2.2.7 Using the toolbox to play Dodgem 31
3.2.3 Exercises 38
3.3 Pattern matching & associative databases 49
3.3.1 A historical perspective 49
3.3.2 The "Patterns" toolbox 50
3.3.3 The "KnowledgeBase" toolbox 54
3.3.4 "InnKeeper" - a crude example of a counseling program 60
3.3.5 Exercises 66
3.4 Production System Interpreters 68
3.4.1 A historical perspective 68
3.4.2 The "ProductionSystems" Toolbox 71
3.4.3 Some simple examples 78
3.4.4 Exercises 86
3.5 Associative & Semantic Networks 89
3.5.1 General principles and historical perspective 89
3.5.2 The "AssociativeNetworks" Toolbox 90
3.5.3 The "Bestiary" microworld 99
3.5.4 Exercises 104
3.6 Frames & Scripts 106
3.6.1 General principles and historical perspective 106
3.6.2 The "Frames" Toolbox 107
3.6.3 The "Toyland" microworld 116
3.6.4 Exercises 123
3.7 Natural Language Processing and ATNs 125
3.7.1 General principles and historical perspective 125
3.7.2 The ATN toolbox 129
3.7.3 The "JanesGarden" microworld 134
3.7.4 Exercises 143
3.8 Rodney - a Restaurant Advisory Program 145
3.8.1 Combining the Toolboxes for a final Example 145
Chapter 4 Future Developments 1
4.1 Historical Development 1
4.2 Of Mice, Menus and Windows - The Smalltalk System and the
Desktop Metaphor 6
4.3 A Glance at Basic Syntax, Data Structures, Operations and
Control Structures 10
4.4 Defining a simple application - classes, properties, methods -
browsers, inspectors and debuggers 14
4.5 Some simple graphics - classes Pen and Form 25
4.6 FaceWorld - an example of the Model-View-Controller
methaphor 30
4.7 Control structures as message patterns and Smalltalk's view
of pseudo-concurrency 44
4.8 Files and other miscellaneous features 48
4.9 Some Comments on Style 49
4.10 Summary and Perspective 51
4.11 Exercises 54
Chapter 5 Summary and Future Perspectives 1
Appendices:
I. AI Programming - an annotated bibliography
II. A simple flavour-based simulator
III. Toolbox sources:
IV. Software Tools - some useful addresses and profiles
V. Solutions to exercises
VI. Scheme & Common Lisp: a comparison
References
Indices
- General
- Procedures, predicates and methods
- Example programs