solomon@aero.ARPA (Steve Solomon) (01/06/86)
In the discussion on the virtues/flaws of Forth vs. other languages, the friendly user who posted a reprint article (I lost his name in my kill ring-- so much for EMACS) states: > 3) Forward referencing (including recursion) is not normal and must be > done by manipulating compiled code. Bye-bye portability. Indeed, I have > never seen anyone write a recursive Forth routine (although it can be > done). Bye-bye AI. As an an AI researcher looking into implementing semi-intelligent programs on micros, but disappointed by how slowly LISP crawls along on a PC, I've recently become interested in Forth as an alternative to LISP. My credentials in Forth are not what one would call the highest, since I've only started, but the statement about recursive routines surprised me even before I found the following excerpt, from FORTH, W.P. Salman, O. Tisserand, and B. Toulout, Springer-Verlag, 1984*, pg. 107, defining the quintessential factorial routine: The correct definition of FACT is then : FACT SMUDGE IF DUP 1 - FACT * ELSE 1 THEN SMUDGE ; <Return> OK Admittedly, this is hard to read (at first glance). But it IS recursion. Also, I was able to figure out what was going on with considerably less trouble than what has been intimated in recent postings, just from my reading the text. An explanation: 1) The SMUDGE works apparently like a forward declaration in Pascal. You need to imbed your code in a recursive definition between two SMUDGE's because the final ";" toggles the same bit in the word definition as SMUDGE, and with only the top SMUDGE it and the semi-colon would cancel each other out. 2) The "IF" syntax in Forth works as follows (pg. 28): condition IF process 1 ELSE process 2 THEN The condition is the boolean value at the top of the data stack, 0 = false, true otherwise. So "DUP 1 - FACT *" is really the THEN part of the conditional (inductive) part. In this case, if the top of the stack (the value implicitly passed to FACT) is not zero, then duplicate that value on the stack, subtract 1, then find the FACT of it, and multiply. ELSE when the value is 0, return 1. The advantage of Forth over assembly language in this case is that the data and return stacks are given; if I wanted to program recursively in assembly language, I would have to construct a run-time program stack with the addresses of the last invoked routines on it. At least Forth takes care of this drudgery for me. What makes Forth attractive for me is its compactness, its run-time extensibility, and its multitasking capabilities, among other features. From what little I've read, Forth also reminds of LISP. Vocabularies seem a little like LISP packages, and there are other similarities. The comment about Forth being like LISP without parentheses is apt, I have the feeling. I am especially interested in using Forth to write a compiler for an unnamed pattern matching AI language to be run on micros, and as everyone knows, parsing by means of recursion is an acceptable method in compiler design. Hence my interest that Forth have recursion. *An extremely informative text on Forth, which I've been reading for the past week. ________________________ Steve Solomon solomon@aero.ARPA "Wenn Forscher neben Forschern forschern, forschern Forscher Forscher." ________________________
rmc@teddy.UUCP (01/07/86)
I have also been interested in FORTH as an AI-ish language for small computers. In fact, the English have used a stack oriented language called POP for some time now (see for example POPLOG, a system containing an editor, several utilities, POP-11, Common Lisp and Prolog. POP-11 is used as the implementation language for the other parts of the environment, and the stack architecture makes the whole system mildly portable. University of Sussex is the originator, System Designers Software is the US distributor, and more information is also available in Pop-11, a book by Barrett, Ramsay and Sloman. I don't know the publisher of the book but SDS can probably give you order information). There are two moderately large problems with FORTH per se as an AI language. The first is scoping, the second is garbage collection. Together they make it rather hard to manage the large programs associated with AI techniques. The two scoping techniques used in Lisp are dynamic and lexical scoping. Dynamic scoping means that the most recent value of a procedure or variable gets used, regardless of who set the variable. Lexical scoping (Algol or C or Pascal technique) says that you can only set variables within your own routine, or those containing you if you look at a printed representation of the program. It turns out that dynamic scoping is simplest for implementing a naive interpreter, but that dynamic scoping has a number of advantages for avoiding name space conflicts and object oriented programming. FORTH scoping is sort of funny. I guess the best way to characterize it would be as dynamic scoping at compile / word definition time rather than at execution time. This means that you can't easily change the definition of a word and have the new definition take effect in existing words. This makes many of the ideas of using programs to build themselves (ie, putting knowledge in procedures) somewhat difficult to handle. A more important limitation is the absence of garbage collection. One of the important techniques in AI is to try to solve a problem and, if that solution fails, try again (ie, use backtracking). The structures describing the problem (schedule of actions in a robot plan, parse tree for a sentence, what have you) are large, and some of the structure is re-used in subsequent attemtpts to solve the problem. In FORTH, all your data ends up on the stack and in the dictionary, making recovering the space for unneeded data extremely complicated. So while there are interesting parallels between FORTH and Lisp, and attempts to use the stack architecture as a "portable engine" for implementing AI languages, it seems that FORTH has some limitations that make it awkward for supporting large, dynamic programs. R Mark Chilenskas decvax!genrad!panda!rmc