SCHATCHEN(ID:7203/sch015)Pattern matching sublanguage for SINfor the Yiddish for "matchmaker" Pattern matching sublanguage for SIN Related languages
References: There were at least three different pattern matchers in Macsyma ?82. The first and oldest one was Schatchen (Yiddish for match-maker) written by Joel Moses, for use with his symbolic indefinite integration program, SIN, and then modified, along with SIN, by R. Grabel, to use Macsyma?s internal ?tagged? expression-tree forms. This system was later used for other problems, for example by Richard Zippel in programs for the recognition of certain classes of closed-form summations. This pattern matcher was quite flexible, but appeared to be useful only for relatively small patterns designed for matching (in some cases) fairly devious instances of generally small expressions. It was potentially very expensive, since it could require backtracking in the course of matching. Commutativity and collection of terms based on mostly syntactic criteria provided important simplifications of integrand-patterns, and the cost to collect such terms and permute objects was not significant in practice, even though inherently exponential-cost algorithms were used. I believe that because one could rely on seeing small expressions, and the number of patterns used was small, it was practical to use Schatchen uniformly and effectively. The problem of scaling up to large expressions was not significant because large integrands were unlikely to occur (but when they did, results might be rather slow in arriving). The best known, purely symbolic systems are, of course, Formac and its current version PL/IFORMAC (Petrick, 1971; pp. 105-114). Formac was the first widely available general-purpose algebraic manipulation system and served for a period to define the field. Certainly, there was a time when one could have safely made the statement that the majority of all mechanical symbolic mathematical computations had been done within Formac. The practical success of these systems, in spite of their rigidity with respect to user modifications and their lack of any seminumerical facilities for rational function computations, is probably due to the overall intelligence of the facilities that were provided. Above all, they were certainly sufficient to support the dominant application area of truncated power series expansion. Current support is minimal. Extract: SCHATCHEN It is impossible to summarize here its facilities, ranging as they do from extremely flexible user control over the form in which rational functions are presented to a semantic pattern-matching facility that, at least, if taken together with SCHATCHEN, serves to define the state of the art. Features such as programs for the manipulation at polynomials over the Gaussian integers or the best extant program for the computation of symbolic limits are almost lost in the enormity of this first system to approach the goal al an algebraic manipulation facility. Extract: Symbolic systems SYMBOLIC SYSTEMS. We should mention first a sequence of three early programs for the simplification of general symbolic mathematical expressions represented as prefix-notation tree structures. The first, at M.I.T., was due to Hart, and the other two were due to Wooldridge and Korsvold at Stanford. The latter has survived in current usage as a result of its incorporation, subject to modification, into the MATHLAB, MACSYMA, and SCRATCHPAD systems. In the mid-1960s there appeared two systems, Formula Algol and FAMOUS, which, while dedicated to the symbolic manipulation of mathematical expressions, presented the user with almost no built-in automatic simplification facilities. This was due, at least in the case of FAMOUS, to a conscious decision that, since the "simplicity" of an expression is surely context- dependent, it should be reasonable to present the user with complete control over the simplification process. That is, the user'should be compelled to define all transformations, rather than, as with most systems, be permitted simply to switch on and off the transformations supplied by the system architects. No system of this species has ever solved the inherent efficiency problems to the extent that it could serve more than didactic purposes. Probably neither Formula Algol nor FAMOUS could be revived today. Another lost symbolic system of importance is the Symbolic Mathematical Laboratory of W. A. Martin. This system provided high-quality 2-D graphics on a DEC-340 display and was also the first to employ a light pen for subexpression selection. In some ways, it represented a degree of interaction that has not been duplicated by any subsequent system. Nor were its innovative internal programming techniques restricted to its graphics facilities. Of particular interest is the use of hash coding for subexpression matching (Petrick, 1971; pp. 305-310). in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details |