Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!sdd.hp.com!ucsd!sdcc6!ir230 From: ir230@sdcc6.ucsd.edu (john wavrik) Newsgroups: comp.lang.forth Subject: Domain of Forth Keywords: Baden Permutations Algorithms Message-ID: <12218@sdcc6.ucsd.edu> Date: 9 Aug 90 05:57:01 GMT Organization: University of California, San Diego Lines: 161 Wil Baden says, > I'd like to see others' ideas of what the proper domain of Forth is. > I'm especially eager to hear from John Wavrik. This thread started with some postings related to generation of permutations. It inspired me to do some work in this area which, in my opinion, confirms the superiority of the Forth environment for developing and studying algorithms. If the algorithm is the data, Forth is a good language to use. > Every language has areas of application in which it is superior, > even Basic, Cobol, and Ada. I'm trying to discover just what is > Forth's domain of superiority. Forth has many facets. One of them is that it is a portable assembly language. As such, it can be used to create languages. In this light it is superior because it can adopt language features from other languages, as well as produce innovative features not currently found elsewhere. BASIC, for example, has admirable string handling features. I've used for years a string package for Forth, originally suggested by John James many years ago. It adds BASIC-like string commands to Forth. For other applications one could add LISP-like storage management, PROLOG-like backtracking, etc. It is the low level definition of the language and the user's access to the implementation that is responsible for this particular facet of Forth. One can add new data handling mechanisms, control structures, etc. because the language provides the tools needed to build these things. > There are algorithms envolving many variables and complicated > expressions for which Forth offers no advantage. The determination > of the date of Easter by 10 quotients and remainders is such, > although of course it can be programmed in Forth as any algorithm > can be. Local variables make Forth definitions into something like > Tiny C with postfix operators. If vector operators are important > for an application, Forth is not the best language to program them. > Forth in these instances is a dancing dog. One of the things that is called into question here is "what is an algorithm?" I have in mind a procedure whose steps I understand. If I want to generate all permutations of 1..n, I need an idea -- and then I express the idea as a procedure. Here is an idea: Start with (1,...,n) and switch the last element with the first, then permute the first n-1 elements and switch it back. Do the same swapping last with second, last with third, etc. Here is Forth code to carry out this idea. 0 \ Permutations -- generate permutations 1 2 : PERMS ( n -- ) RECURSIVE 3 DUP 1 = IF PRINT-PERM 4 ELSE DUP 1+ 1 DO 5 I OVER XCHG 6 DUP 1- PERMS 7 I OVER XCHG 8 LOOP 9 THEN DROP ; 10 11 : PERMUTATIONS ( n -- ) DUP #ELEMENTS ! 12 INIT-PERM CR PERMS ; (The words PRINT-PERM, XCHG, etc. do what you think they do!) Does the Forth code clearly express the idea? Is Forth a good language for expressing this kind of idea? Is Forth a good language for testing ideas like this? [P.S. experiments show when an idea is plausible -- and help to identify bad ideas. A proof is still needed to show that an idea works!] On the other hand, the word "algorithm" is also used for cookbook recipes. Wil Baden refers to the calculation of Easter. This is often given as a sequence of algebraic expressions to be calculated: Y = year for calculation (input ) G = ( Y mod 19 ) + 1 C = Y / 100 + 1 X = 3C / 4 - 12 etc. Wil says that removing the names and doing all these steps on the stack with unnamed variables makes things worse. I agree. However, the "algorithm" is actually the set of ideas behind this recipe. If we understood the algorithm, we might be able to express it well in Forth (but not, of course, as a sequence of infix expressions). Suppose that you really want to express a recipe like this in Forth. What should you do? Here's what I would do: I would load a package called "ALGEBRAIC" written in Forth which has the word EVALUATE" as its top level word. The recipe might be written in Forth like this: : EASTER ( year -- month day ) EVALUATE" Y = pop " EVALUATE" G = ( Y MOD 19 ) + 1 " ......... ; One might want expressions without an assignment to put their value on the stack (to allow mixing of evaluation of expressions with ordinary Forth). It would be easy, in this way, to blend words defined using algebraic expressions with other Forth words -- in the same way as we blend words defined using assembly language with other Forth words. There are several ways the variables can be handled. The simplest is to use static storage allocation with standard Forth variables -- which would allow words to be factored and share a set of variables. The kind of parser needed to implement something like this (with the expressions parsed at compile-time) would take about 10 Forth screens -- loaded when anyone needs this feature added to the language. I should pause here to say something to people who feel that I have somehow violated the purity of Forth by suggesting that words be created to handle algebraic infix expressions. My view of Forth is that its "niche" (if you want to call it that) is that it is more flexible and universal than other languages. You can use Forth to build anything that you want (and build it portably if the Standards are any good). When we want to manipulate a certain type of data, we first write words for handling this type of data and the relevant operations on it. Then we write programs using these words. [When we want to do a job, we first build tools designed for the kind of work we want to do!] Algebraic expressions are a form of data -- and the operation we want to perform is evaluation. So take the Forth approach: build tools appropriate for the task. There is yet another way that "algorithms" are presented. Hale Trotter's algorithm for permutations, which Wil Baden wrote in C and in Forth, is written in what Wil refers to as "spaghetti Algol". It is a collection of unmotivated steps written in a language which freely uses GOTO. Forth is a structured language (Moore and the early FIG group apparently understood the dangers of GOTO at the same time as the computer science community became aware of it. Notice that even Forth assembly language is structured!). Translating an algorithm from an unstructured language to a structured language is always a problem -- and Baden's C version is really not any clearer than his unfactored Forth version. The fact of the matter is that even the original spaghetti Algol version is not very illuminating. The point of the above paragraph is that translating a confusing program from another language into Forth isn't easy and it doesn't automatically make it any clearer --- but neither does translating it into anything else. If I understood the ideas behind Trotter's recipe, I might be able to write a clear (properly factored, appropriately named) Forth word set to carry it out. I wouldn't write a "spaghetti Algol" interpreter for Forth -- I'd use Forth to try to understand the algorithm and then express the ideas more clearly. [I find it objectionable to use recipes without any idea of where they come from or why they work.] In the next installment, I'll talk a bit about using Forth to make a "permutation laboratory" -- a tool for studying permutations. I think it is a perfect example of something that can be done more easily in Forth than any other language. Whatever the domain of Forth, it definitely includes "experimental computing". John J Wavrik jjwavrik@ucsd.edu Dept of Math C-012 Univ of Calif - San Diego La Jolla, CA 92093