Subsequence references: first-class values for substrings

ABSTRACT

Arrays of characters are a basic data type in many programming languages, but strings and substrings are seldom accorded first-class status as parameters and return values. Such status would enable a routine that calls a search function to readily access context on both sides of a return value. To enfranchise substrings, this paper describes a new data type for substrings as a special case of one for general subsequences. The key idea is that values are not sequences or references to positions in sequences, but rather references to subsequences. Primitive operations on the data type are constants, concatenation, and four new functions—base, start, next, and extent—which map subsequence references to subsequence references. This paper informally presents the data type, demonstrates its convenience for defining search functions, and shows how it can be concisely implemented. Examples are given in Ness, a language incorporating the new data type, which is implemented as part of the Andrew User Interface System.

REFERENCES

• 1: CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. Modula-3 Report. Res. Rep. 31, Digital Systems Research Center, Palo Alto, Ca., 1988.
• 2: Center for Design of Educational Computing, CMU. The cTtre Programming Languoge. Falcon Software, Wentworth, N.H., 1989.
• 3: GLICKSTEIN, R. Lisp Primitives in ELI, the Embedded Lisp Interpreter. Information Technology Center, Carnegie Mellon Univ, 1990.
• 4: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 5: Ralph E. Griswold , Madge T. Griswold, The ICON Programming Language, Annabooks, 1996
• 6: Wilfred J. Hansen, Data structures in a bit-mapped text editor, BYTE, v.12 n.1, p.183-190, Jan. 1987
• 7: HANSEN, W. J. The computational power of an algebra for subsequences. Tech. Rep. CMU-ITC-083, Information Technology Center, Carnegie Mellon Univ., 1989.
• 8: HANSE~, W.J. Ness Language Reference Manual. Information Technology Center, Carnegie Mellon Univ., 1989.
• 9: HANSEN, W.J. Enhancing documents with embedded programs: How Ness extends insets in the Andrew ToolKit. In Proceedmgs of the 1990 International Conference on Computer Languages. IEEE Computer Society Press, Los Alamitos, Ca., 1990, pp. 23-32.
• 10: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 11: IBM Corporation PL/I language specifications. Tech. Rep. C28-6571-0, IBM Corp., Data Processing Division, White Plains, N.Y. 1965.
• 12: McKEEMAN, W. M., HORNING, J. J, AND WORTMAN, D.B. A Compiler Generator. Prentice- Hall, Englewood Cliffs, N.J., 1970.
• 13: James H. Morris , Mahadev Satyanarayanan , Michael H. Conner , John H. Howard , David S. Rosenthal , F. Donelson Smith, Andrew: a distributed personal computing environment, Communications of the ACM, v.29 n.3, p.184-201, March 1986 [doi>10.1145/5666.5671]
• 14: PALAY, A. J., HANSEN, W. J., SHERMAN, M., WADLOW, M., NEUENDORFFER, T., STERN, Z., BADER, M., AND PETERS, T. The Andrew Toolkit An overview. In Proceedings of the USENIX Winter Conferel2ce (Dallas, Tex., Feb. 1988), pp. 9 21.
• 15: Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990 [doi>10.1145/79173.79184]
• 16: Victor H. Yngve, COMIT, Communications of the ACM, v.6 n.3, p.83-84, March 1963 [doi>10.1145/366274.366291]

INDEX TERMS

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

Additional Classification:
  E. Data

General Terms:
Languages

Keywords:
ATK, AUIS, Andrew Toolkit, Ness, document processing, programming language design, sequences, string searching, strings, subsequences, substrings