Denotational semantics of a goal-directed language

ABSTRACT

Goal-directed evaluation is a very expressive programming language paradigm that is supported in relatively few languages. It is characterized by evaluation of expressions in an attempt to meet some goal, with resumption of previous expressions on failure. This paradigm is found in SNOBL4 in its pattern-matching facilities, and in Icon as a general part of the language. This paper presents a denotational semantics of Icon and shows how Icon is in fact a combination of two distinct paradigms, goal-directed evaluation and functional application. The two paradigms are not supported separately in different contexts, but integrated fully into a single evaluation mechanism.

REFERENCES

• 1: D~ BRU~N, A. Operational and Denotational Semant~cs Describeng the Match*ng Process in SNOBOL4 Afdeling Informatica, Mathematlsch Centrum, Amsterdam, 1980.
• 2: FLECK, A. C., AND LIrdAYE, R. S. Formal semantics and abstract properties of string operations and extended formal language description mechanisms SIAM J Comput. 12, 1 (Feb. 1983), 166-188
• 3: FRIEDMAN, D P, HAYNES, C. T KOHLBECKER, E., AND WAND, M. Scheme 84 mterim reference manual. Tech. Rep. 153, Dept. of Computer Science, Indiana State Unir., Bloomington, Jan. 1985.
• 4: Ralph E. Griswold, The Evaluation of Expressions in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.563-584, Oct. 1982 [doi>10.1145/69622.357184]
• 5: Ralph E. Griswold , David R. Hanson, An Alternative to the Use of Patterns in String Processing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.153-172, April 1980 [doi>10.1145/357094.357096]
• 6: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 7: GUDEMAN, D.A. A contmuatlon semantics for Icon expressions. Tech. Rep. 86-15, Dept. of Computer Science, Univ. of Anzona, Tucson, Apr. 1986.
• 8: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 9: EES, J. A., ADAMS, N. I., AND MEEHAN, J R. The T manual. Tech. Rep. Computer Science Dept., Yale Univ., New Haven, Conn., Jan 1984.
• 10: Ravi Sethi, Control Flow Aspects of Semantics-Directed Compiling, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.554-595, Oct. 1983 [doi>10.1145/69575.357227]
• 11: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 12: STERLING, L., AND SHAPIRO, E The Art of Prolog. MIT Press, Cambridge, Mass, 1986.
• 13: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 14: R. D. Tennent, Mathematical semantics of SNOBOL4, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.95-107, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512936]
• 15: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 16: VAN EMnEN, M.H. An interpreting algorithm for Prolog programs. In Proceedings of the 1st International Logic Programming Conference. (Univ. of Marseilles, France, 1982), pp. 93-110.
• 17: Mitchell Wand, Deriving Target Code as a Representation of Continuation Semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.496-517, July 1982 [doi>10.1145/357172.357179]
• 18: David A. Watt, Executable semantic descriptions, Software—Practice & Experience, v.16 n.1, p.13-43, Jan. 1986 [doi>10.1002/spe.4380160104]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.2 Language Classifications
          Subjects: Nonprocedural languages**
          Nouns: ICON
      D.3.3 Language Constructs and Features
          Subjects: Control structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Languages, Theory

Keywords:
generators, goal-directed evaluation, programming language paradigms