[mod.ai] Functional programming and AI

cugini@NBS-VMS.ARPA.UUCP (05/21/86)

Here's a (dumb?) question for assorted AI wizards: how (if at all)
does functional programming support AI type applications?
By "functional programming", I mean the ability of a language
to treat functions (or some other embodiment of an algorithm) as
a data object: something that can be passed from one routine to
another, created or modified, and then applied, all at run-time.
Lisp functions are an example, as is C_Prolog's ability to
construct predicates from lists with the =.. operator, and the
OPS5 "build" action.

Do working AI programs really exploit these features a lot?
Eg, do "learning" programs construct unforeseen rules, perhaps
based on generalization from examples, and then use the rules?
Or is functional programming just a trick that happens to be
easy to implement in an interpreted language?

Thanks for any thoughts on this...

John Cugini <Cugini@NBS-VMS> 
Institute for Computer Sciences and Technology
National Bureau of Standards
------

hamscher@HT.AI.MIT.EDU (Walter Hamscher) (05/29/86)

   Date: 21 May 86 13:14:00 EST
   From: "CUGINI, JOHN" <cugini@nbs-vms.ARPA>
   Reply-to: "CUGINI, JOHN" <cugini@nbs-vms.ARPA>

   Do working AI programs really exploit these features a lot?
   Eg, do "learning" programs construct unforeseen rules, perhaps
   based on generalization from examples, and then use the rules?
   Or is functional programming just a trick that happens to be
   easy to implement in an interpreted language?

I think this is a slightly odd characterization of `functional
programming.'  Maybe I'm confused, but I always thought a `functional
language' meant (in a nutshell) that there are no side effects.  In
contrast, the one important `side effect' you're talking about here is
constructing a function at runtime and squirreling it away in a
knowledge base, to be run later.  In theory you could do the
squirreling by passing around the whole state of the world and
non-destructively modifying that datastucture as you go, but that's
orthogonal to what you seem to be talking about (besides being
painful).

Whatever it's called -- this indistinguishability between code and
data -- it's true that it's a ``trick,'' but I think it's an important
one.  In fact as I think about it now, every AI program I've ever seen
_at_some_point_ passes functions around, sticks them in places like on
property lists as demons, and/or mashes together portions of bodies of
different functions and sticks the resulting lambda-expression
somewhere to run later (Well, maybe Mycin didn't (but Teiresias did)).

As far as learning programs that construct functions, it's all in the
eyes of the interpreter.  A rule that is going to be run by a rule
interpreter counts as a kind of function (it's just not necessarily in
LISP per se).  So, since Tom Mitchell's LEX (for example) builds and
modifies the bodies of heuristic rules which later get applied to the
integration problem, it falls in this category.  Tom Diettrich's EG
does something like this too.  I'm sure there are jillions of other
examples but I'm not that deep into machine learning.

And of course there's always AM (which by now should be familiar to
all readers of AiList) which (among other things) did random structure
modifications to LISP functions, then ran them to see what they did.
For example, it might start with the following definition of EQUAL:

(defun EQUAL (a b)
    (cond ((eq a b) t)
	  ((and (consp a) (consp b))
           (and (EQUAL (car a) (car b))
		(EQUAL (cdr a) (cdr b))))
	  (t
	    nil)))

To generalize the function, it drops one of the conjunctions and
changes its name (including the recursive call):

(defun SOME-NEW-FUNCTION (a b)
    (cond ((eq a b) t)
	  ((and (consp a) (consp b))
	   (SOME-NEW-FUNCTION (cdr a) (cdr b)))
	  (t
	    nil)))

Lo and behold, SOME-NEW-FUNCTION is a new predicate meaning
something like "same length list."  So there's an existence
proof at least.

	Walter Hamscher