An Alternative to the Use of Patterns in String Processing

ABSTRACT

SNOBOL4 is best known for its string processing facilities, which are based on patterns as data objects. Despite the demonstrated success of patterns, there are many shortcomings associated with their use. The concept of patterns in SNOBOL4 is examined and problem areas are discussed. An alternative method for high-level string processing is described. This method, implemented in the programming language Icon, employs generators, which are capable of producing alternative values. Generators, coupled with a goal-driven method of expression evaluation, provide the string processing facilities of SNOBOL4 without the disadvantages associated with patterns. Comparisons between SNOBOL4 and Icon are included and the broader implications of the new approach are discussed.

REFERENCES

• 1: ATKINSON, R. Toward more general iteration methods in CLU. CLU Design Note 54, M.I.T., Cambridge, Mass., Sept. 1975.
• 2: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 3: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 4: DEWAR, R.B.K. SPITBOL version 2.0. SNOBOL4 Proj. Doc. S4D23, Illinois Inst. Technology, Chicago, 1971.
• 5: DEWAR, R.B.K., AND MCCANN, A.P. MACRO SPiTBOL--A SNOBOL4 compiler. Softw., Pract. Exper. 7, I (Jan.-Feb. 1977), 95-114.
• 6: DOYLE, J.N. A generalized facility for the analysis and synthesis of strings and a procedurebased model of an implementation. M.S. thesis, Univ. Arizona, Tucson, 1975.
• 7: FLECK, A.C. Formal models for string patterns. In Current Trends in Programming Methodology, vol. IV, Data Structuring, R. T. Yeh, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1978, pp. 216-240.
• 8: Christopher W. Fraser, A compact, machine-independent peephole optimizer, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-6, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567753]
• 9: James F Gimpel, Algorithms in SNOBOL4, Catspaw, Salida, CO, 1986
• 10: J. F. Gimpel, A theory of discrete patterns and their implementation in SNOBOL4, Communications of the ACM, v.16 n.2, p.91-100, Feb. 1973 [doi>10.1145/361952.361960]
• 11: GiMPEL, J.F. Nonlinear pattern theory. Acta Inf. 4, (1975), 91-100.
• 12: Ralph E. Griswold, Extensible pattern matching in SNOBOL4, Proceedings of the 1975 annual conference, p.248-252, January 1975 [doi>10.1145/800181.810331]
• 13: Ralph E. Griswold, String analysis and synthesis in SL5, Proceedings of the annual conference, p.410-414, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805628]
• 14: GRISWOLD, R.E. String and List Processing in SNOBOL4, Techniques and Applications. Prentice-Hall, Englewood Cliffs, N.J., 1975, pp. 12, 233-234.
• 15: Ralph E Griswold, The macro implementation of SNOBOL4;: A case study of machine-independent software development, W. H. Freeman & Co., New York, NY, 1972
• 16: GRmWOLD, R.E. The use of character sets and character mappings in Icon. Comput. J., to appear.
• 17: Ralph E. Griswold , David R. Hanson, An overview of SL5, ACM SIGPLAN Notices, v.12 n.4, p.40-50, April 1977 [doi>10.1145/954654.954658]
• 18: GRISWOLD, R.E., AND HANSON, D.R. Reference manual for the Icon programming language. Tech. Rep. TR 79-1, Dep. Comput. Sci., Univ. Arizona, Tucson, Jan. 1979.
• 19: Ralph E. Griswold , David R. Hanson , John T. Korb, Generators in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.144-161, April 1981 [doi>10.1145/357133.357136]
• 20: Ralph E. Griswold , David R. Hanson , John T. Korb, The icon programming language: an overview, ACM SIGPLAN Notices, v.14 n.4, April 1979 [doi>10.1145/988078.988082]
• 21: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 22: David R. Hanson , Ralph E. Griswold, The SL5 procedure mechanism, Communications of the ACM, v.21 n.5, p.392-400, May 1978 [doi>10.1145/359488.359502]
• 23: KNUTH, D.E., MORRIS, J.H., AND PRATT, V.R. Fast pattern matching in strings. SIAM J. Comput. 6, 2 (June 1977), 323-350.
• 24: John Timothy Korb, The design and implementation of a goal-directed programming language., 1979
• 25: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 26: NEWELL, A., ED. Information Processing Language-V Manual (Rand Corp.), Prentice-Hall, Englewood Cliffs, N.J., 1961.
• 27: PFEFrER, A.S., AND FURTADO, A.L. Pattern matching for structured programming. In Proc. 7th Asilomar Conf. Circuits, Systems, and Computers, Pacific Grove, Calif., 1973, pp. 466-469.
• 28: Proceedings of the workshop on pattern-directed inference systems. SIGART Newsletter 63 (June 1977), 1-84.
• 29: Mary Shaw , William A. Wulf , Ralph L. London, Abstraction and verification in Alphard: defining and specifying iteration and generators, Communications of the ACM, v.20 n.8, p.553-564, Aug. 1977 [doi>10.1145/359763.359782]
• 30: Glenn F. Stewart, An algebraic model for string patterns, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.167-184, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512994]
• 31: SUSSMAN, G.J., ANO McDERMOtt, D.V. From PLANNER to CONNIVER--A genetic approach. Proc. 1972 AFIPS, Fall Jt. Computer Conf., vol. 41, AFIPS Press, Arlington, Va., pp. 1171-1179.
• 32: TESLER, L.G., ENEA, H.J., AND SMXTH, D.C. The LISP70 pattern matching system. In Proc. 3rd Int. Jt. Conf. Artificial Intelligence, Stanford, Calif., 1973, pp. 671-676.
• 33: VA~ WIJ~GAAROE~, A., ET AL. Revised report on the algorithmic language Algol 68. Acta Inf. 5 (Jan. 1976), 1-236.
• 34: W. Wulf , Mary Shaw, Global variable considered harmful, ACM SIGPLAN Notices, v.8 n.2, p.28-34, February 1973 [doi>10.1145/953353.953355]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Patterns (e.g., client/server, pipeline, blackboard)

General Terms:
Design, Languages, Performance, Theory