Two-level grammars as a technique for formalizing programming schemes

ABSTRACT

This paper addresses the issue of formalizing programming schemes (or programming plans). Research in problem solving and in programming has shown a hierarchical organization of program solutions. This organization suggests that a hierarchical formal definition can be used to eliminate the ambiguity inherent in previous natural language definitions. This paper uses the hierarchy implicit in two-level grammars to define programming schemes. It gives examples to illustrate how the definition can be used for a particular scheme.

REFERENCES

• ADE81: B. Adelson, Problem Solving and the Development of Abstract Categories in Programming Languages, Memory and Cognition, 9(1981), 422-433.
• CHA73: W. C. Chase and H. Simon, Perception in Chess, Cognitive Psychology, 4(1973) 55-81.
• DEG65: A. D. deGroot, Thought and Choice in Chess, Paris, France, Mouton, 1965.
• DEG84: J. De Graaf and A. Ollongran, On Two-Level Grammars, International Journal of Computer Mathematics, 15(1984), 269-288.
• GEN83: D. Gentner and D. Gentner, Flowing Waters or Teeming Crowds: Mental Models of Electricity, In Mental Models, D Genmer (ed), 1983.
• GIC86: M. Gick, Problem-Solving Strategies, Educational Psychology, 21(1986), 99-120.
• GIC83: M. Gick and K. Holyoak, Schema Induction and Analogical Transfer, Cognitive Psychology, 15(1983)1-38.
• HAR78: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• HOR84: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• HOR84: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• KEA85: M. Keane, On Drawing Analogies A Theory and Test of Solution Problem-Solving Task, British 76(1985)449-458.
• KNU73: D. Knuth, The Art of Computer Sorting and Searching, Company, 1973.
• LEV83: J. Levy, The Einstellung Effect Honors Thesis, Tulane University, 1983,
• MAL84: J. Maluszynski, Towards a Programming the Notion of Two-Level Grammar, Science, 28(1984), 13-43.
• MAR77: M. Marcotty, H. Ledgard, Formal Definitions, Computing 191-276.
• MAY81: R. Mayer, The Psychology of Programming, Computing Surveys,
• NUT85: J.T. Nutter and J. Hassell, Program Understanding and Association for Educational 18(1985), 195-206.
• POH86: H.L. Pohl and J.T. Nutter, Language Acquisition, Association Systems Journal, 18(1985),
• RIS86: R.S. Rist, Plans in Programming: and Development, In Empirical E. Soloway and S. Iyengar (eds) 1986.
• SCH77: R.C. Schank and R. Abelson, Understanding, Lawrence Erlbaum
• SIM78: D.P. Simon and H.A. Simon, Solving Physics Problems, In develops?, R.S. Siegler (ed)
• SOL81: E. Soloway and B. Woolf, Problems, ACM SlGCSE Bulletin, 12
• SOL82: E. Soloway, K. Ehrlich, J. Bonar, Novices Know About Programming, Computer-Human Interaction, Badre (eds) Ablex Publishing
• SOL83: E. Soloway, K. Ehrlich, and Like Reading a Story (well, almost) Fifth Annual Conference Society, 1983.
• SOL84: E. Soloway and K. Ehrlich, Programming Knowledge, IEEE Engineering, 10(1984) 595-609.
• TRE76: J.P. Tremblay and P.G. Sorenson, Structures with Applications,
• VAN75: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

General Terms:
Design, Languages