contrib/awk/doc/awkforai.txt

   1 Draft for ACM SIGPLAN Patterns (Language Trends)
   2
   3 1996
   4
   5 Why GAWK for AI?
   6
   7 Ronald P. Loui
   8
   9 Most people are surprised when I tell them what language we use in our
  10 undergraduate AI programming class.  That's understandable.  We use
  11 GAWK.  GAWK, Gnu's version of Aho, Weinberger, and Kernighan's old
  12 pattern scanning language isn't even viewed as a programming language by
  13 most people.  Like PERL and TCL, most prefer to view it as a "scripting
  14 language."  It has no objects; it is not functional; it does no built-in
  15 logic programming.  Their surprise turns to puzzlement when I confide
  16 that (a) while the students are allowed to use any language they want;
  17 (b) with a single exception, the best work consistently results from
  18 those working in GAWK.  (footnote:  The exception was a PASCAL
  19 programmer who is now an NSF graduate fellow getting a Ph.D. in
  20 mathematics at Harvard.) Programmers in C, C++, and LISP haven't even
  21 been close (we have not seen work in PROLOG or JAVA).
  22
  23 Why GAWK?
  24
  25 There are some quick answers that have to do with the pragmatics of
  26 undergraduate programming.  Then there are more instructive answers that
  27 might be valuable to those who debate programming paradigms or to those
  28 who study the history of AI languages.  And there are some deep
  29 philosophical answers that expose the nature of reasoning and symbolic
  30 AI.  I think the answers, especially the last ones, can be even more
  31 surprising than the observed effectiveness of GAWK for AI.
  32
  33 First it must be confessed that PERL programmers can cobble together AI
  34 projects well, too.  Most of GAWK's attractiveness is reproduced in
  35 PERL, and the success of PERL forebodes some of the success of GAWK.
  36 Both are powerful string-processing languages that allow the programmer
  37 to exploit many of the features of a UNIX environment.  Both provide
  38 powerful constructions for manipulating a wide variety of data in
  39 reasonably efficient ways.  Both are interpreted, which can reduce
  40 development time.  Both have short learning curves.  The GAWK manual can
  41 be consumed in a single lab session and the language can be mastered by
  42 the next morning by the average student.  GAWK's automatic
  43 initialization, implicit coercion, I/O support and lack of pointers
  44 forgive many of the mistakes that young programmers are likely to make.
  45 Those who have seen C but not mastered it are happy to see that GAWK
  46 retains some of the same sensibilities while adding what must be
  47 regarded as spoonsful of syntactic sugar.  Some will argue that
  48 PERL has superior functionality, but for quick AI applications, the
  49 additional functionality is rarely missed.  In fact, PERL's terse syntax
  50 is not friendly when regular expressions begin to proliferate and
  51 strings contain fragments of HTML, WWW addresses, or shell commands.
  52 PERL provides new ways of doing things, but not necessarily ways of
  53 doing new things.
  54
  55 In the end, despite minor difference, both PERL and GAWK minimize
  56 programmer time.  Neither really provides the programmer the setting in
  57 which to worry about minimizing run-time.
  58
  59 There are further simple answers.  Probably the best is the fact that
  60 increasingly, undergraduate AI programming is involving the Web.  Oren
  61 Etzioni (University of Washington, Seattle) has for a while been arguing
  62 that the "softbot" is replacing the mechanical engineers' robot as the
  63 most glamorous AI testbed.  If the artifact whose behavior needs to be
  64 controlled in an intelligent way is the software agent, then a language
  65 that is well-suited to controlling the software environment is the
  66 appropriate language.  That would imply a scripting language.  If the
  67 robot is KAREL, then the right language is "turn left; turn right." If
  68 the robot is Netscape, then the right language is something that can
  69 generate "netscape -remote 'openURL(http://cs.wustl.edu/~loui)'" with
  70 elan.
  71
  72 Of course, there are deeper answers.  Jon Bentley found two pearls in
  73 GAWK:  its regular expressions and its associative arrays.  GAWK asks
  74 the programmer to use the file system for data organization and the
  75 operating system for debugging tools and subroutine libraries.  There is
  76 no issue of user-interface.  This forces the programmer to return to the
  77 question of what the program does, not how it looks.  There is no time
  78 spent programming a binsort when the data can be shipped to /bin/sort
  79 in no time.  (footnote:  I am reminded of my IBM colleague Ben Grosof's
  80 advice for Palo Alto:  Don't worry about whether it's highway 101 or 280.
  81 Don't worry if you have to head south for an entrance to go north.  Just
  82 get on the highway as quickly as possible.)
  83
  84 There are some similarities between GAWK and LISP that are illuminating.
  85 Both provided a powerful uniform data structure (the associative array
  86 implemented as a hash table for GAWK and the S-expression, or list of
  87 lists, for LISP).  Both were well-supported in their environments (GAWK
  88 being a child of UNIX, and LISP being the heart of lisp machines).  Both
  89 have trivial syntax and find their power in the programmer's willingness
  90 to use the simple blocks to build a complex approach.
  91
  92 Deeper still, is the nature of AI programming.  AI is about
  93 functionality and exploratory programming.  It is about bottom-up design
  94 and the building of ambitions as greater behaviors can be demonstrated.
  95 Woe be to the top-down AI programmer who finds that the bottom-level
  96 refinements, "this subroutine parses the sentence," cannot actually be
  97 implemented.  Woe be to the programmer who perfects the data structures
  98 for that heapsort when the whole approach to the high-level problem
  99 needs to be rethought, and the code is sent to the junkheap the next day.
 100
 101 AI programming requires high-level thinking.  There have always been a few
 102 gifted programmers who can write high-level programs in assembly language.
 103 Most however need the ambient abstraction to have a higher floor.
 104
 105 Now for the surprising philosophical answers.  First, AI has discovered
 106 that brute-force combinatorics, as an approach to generating intelligent
 107 behavior, does not often provide the solution.  Chess, neural nets, and
 108 genetic programming show the limits of brute computation.  The
 109 alternative is clever program organization.  (footnote: One might add
 110 that the former are the AI approaches that work, but that is easily
 111 dismissed:  those are the AI approaches that work in general, precisely
 112 because cleverness is problem-specific.)  So AI programmers always want
 113 to maximize the content of their program, not optimize the efficiency
 114 of an approach.  They want minds, not insects.  Instead of enumerating
 115 large search spaces, they define ways of reducing search, ways of
 116 bringing different knowledge to the task.  A language that maximizes
 117 what the programmer can attempt rather than one that provides tremendous
 118 control over how to attempt it, will be the AI choice in the end.
 119
 120 Second, inference is merely the expansion of notation.  No matter whether
 121 the logic that underlies an AI program is fuzzy, probabilistic, deontic,
 122 defeasible, or deductive, the logic merely defines how strings can be
 123 transformed into other strings.  A language that provides the best
 124 support for string processing in the end provides the best support for
 125 logic, for the exploration of various logics, and for most forms of
 126 symbolic processing that AI might choose to call "reasoning" instead of
 127 "logic."  The implication is that PROLOG, which saves the AI programmer
 128 from having to write a unifier, saves perhaps two dozen lines of GAWK
 129 code at the expense of strongly biasing the logic and representational
 130 expressiveness of any approach.
 131
 132 I view these last two points as news not only to the programming language
 133 community, but also to much of the AI community that has not reflected on
 134 the past decade's lessons.
 135
 136 In the puny language, GAWK, which Aho, Weinberger, and Kernighan thought
 137 not much more important than grep or sed, I find lessons in AI's trends,
 138 AI's history, and the foundations of AI.  What I have found not only
 139 surprising but also hopeful, is that when I have approached the AI
 140 people who still enjoy programming, some of them are not the least bit
 141 surprised.
 142
 143
 144 R. Loui (loui@ai.wustl.edu) is Associate Professor of Computer Science,
 145 at Washington University in St. Louis.  He has published in AI Journal,
 146 Computational Intelligence, ACM SIGART, AI Magazine, AI and Law, the ACM
 147 Computing Surveys Symposium on AI, Cognitive Science, Minds and
 148 Machines, Journal of Philosophy, and is on this year's program
 149 committees for AAAI (National AI conference) and KR (Knowledge
 150 Representation and Reasoning).