This is the short version of the paper: Prokhorov, V.V. Pi-charts: The Language for Graphic Representation of Algorithms and Syntactic Descriptions. Cybernetics and Systems Analysis, 1992, N2, p.93-117.

On Graph Descriptions of Algorithms

Vladimir V. Prokhorov

Institute of Math and Mechanics, Russian Academy of Sciences/Ural Branch

GSP-384 Yekaterinburg, 620219 RUSSIA

Fax: (7 343) 244-2581. Email: vpro@convex.ru

Abstract

Structured visual algorithmic language is discussed. This one is based on representation of algorithm’s structure in a tree-like graph form. The language may be used for algorithmic knowledge representation as in publications and education, as in computer environment for human-computer interface supply. The language is used in visual programming environment PYTHAGORAS; this media is used particularly for interaction with multi-computer complex on the Internet base. A version of the media is used in education.

Keywords: Algorithmic Languages, Knowledge Representation, Visual Programming

Contents:

    Introduction

1. Description of the Language

2. Examples

3. Applications

    References

Introduction

Nowadays, there are used some visual languages algorithmic knowledge representation [5]. The most popular is the flow chart (ISO DIS 5807.2). Idea of flow chart is based on the algorithm’s idea as a flow of commands, while in textual algorithmic languages the technology of structural representation is much popular. The simplest text-graphic form of algorithm’s representation is writing in such a manner, that a structural hierarchy is shown by indents of text lines. Among graphic structural languages, the most common is the structure grams by Nessie and Shneiderman (DIN 65261 HCN 1422). HIPO-charts are also in use, but the degree of their “graphicity” may be doubted.

Our visual language (see also [5]) in its idea is similar to Nessie-Shneiderman’s structure grams, but, apparently, seems to be more convenient for of algorithms’ writing. The p-charts algorithmic language is oriented exclusively to the structural approach to algorithmization (the nonstructural one becoming impossible), and to the “top-down” technology of algorithm's development. We look at the language from micro-language [4] viewpoint, as element of layered language. Therefore, we consider neither language’s sublanguages-“clients”, nor language’s “host” (for example, constructions of object-oriented programming). A first description of the language was given in [2]. The language is similar to the syntactical p-charts language [3] in its idea.

1. Description of the Language

    We give main elements’ description using a certain version of Backus-Naur syntactic formulas.

    <Statement>::= <Terminal> | <Series> | <Parallel> | <Case statement> |
    <Loop statement> | <Multiplier statement> | <Block> | <Control element>

    <Terminal>::= <Atom> | <Embedded object>

    Here <Atom> is an elementary command that may be considered as not requiring further fragmentation into the smaller elements in terms of the language. <Atom> is an element of set of primitive actions. <Embedded object> is a complex object, constructed in another language.

    <Case statement>::= <Logical case statement> | <Switch case statement>

    <Selector>::= <Value> | <Set of values>

    <Multiplier statement> is intended to use in parallel algorithms (as reduced form of <Parallel>).

    Block is a statement having a name and/or local data and/or comment.

    <Control element>::=
    <Loop statement termination> | <Procedure body statement termination>

    <Substitution> denotes equivalence if circle-marked field to the <Statement>.

    From the given definitions, the p-chart is a tree-like graph. Each of its sub-trees is called a statement. The non-terminal nods of the graph correspond to the various algorithmic language constructions, and the terminal ones — to executed actions. In addition, two algorithmic elements — termination of loop statement, and termination of procedure body — may be used as terminal nodes. So, the language is based on graph of algorithm’s structure. They are two-dimensional: the top-bottom direction reveals the degree of structure elaboration, and the left-to-right direction represents a proceeding sequence in the <Series> construction, and conditions priority in the <Case statement>. Note, that the flowchart is based upon an algorithm proceeding graph where “the time axis” is represented by the arcs (hence, flow chart is one-dimensional diagram).

2. Examples

    As example, we give representations of the same algorithm in the p-chart (Figure 1) and the flowchart (Figure 2) languages. The p-chart is result of formal transformation of the flowchart. The algorithmic description in the language is used with some textual language as “client” one. The language may be used as sub layer of multiparadigm language ([4], [5]). Figure 3 shows an example of several sub-languages’ cooperative use in accordance with microcontext multiparadigm layered technology.

    Figure 1

    Figure 2

3. Applications

The language is convenient for algorithms representation on the discussions and preliminary design stage. It is agree with both structural and top-down approaches to design. The same advantages do fruitful use the language in education.

A team of developers in the author-heading laboratory has created some generations of software media PYTHAGORAS to support the language as programming one (Figure 4). One of the versions is aided on educational tasks; in the version modes of program’s execution with animation of “developer”, “supervisor” and “executor” (for example, turtle). Therefore, the software allows to use visual approach with animation of three stages of program’s life (see [1]), and top-down approach [7] in education. Version for professional use is oriented to work in multi-computer environment, including PCs and powerful multiprocessor computing machine, on Internet basis. The language support allows integrating software and hardware tools available. We are developing versions of the language as visual versions of JAVA and OCCAM.

Figure 3

 

Figure 4

References

[1] Papert, S. Mindstorms. Basic Books, Inc. New York, 1980.

[2] Prokhorov, V.V. On a Project of Standards for Structure-Procedural Charts of Algorithms and Syntax Diagrams. Proceedings of the IV All-Union Workshop on Development and Application of Computer Software for Education, Moscow, USSR, 1988, p.23-27.

[3] Prokhorov, V.V. On Graph Representation of Syntax Definitions. In: J.G.Chen, ed. Expert Systems Applications & Artificial Intelligence. Technology Transfer Series. IITT International, Gournay-Sur-Marne, France: 1995, p.53-58.

[4] Prokhorov, V.V. PYTHAGORAS: Multienvironment Software. In: B.Blumenthal, J.Gornostaev, and C.Unger, Eds. Human-Computer Interaction. Lecture Notes in Computer Science, v.1015. Springer Verlag, Berlin, Germany, 1995, p.135-148.

[5] Prokhorov, V.V. The Language for Graphic Representation of Algorithms and Syntactic Descriptions. Cybernetics and System Analysis, 1992, N2, p.93-117.

[6] Raeder, G. A Survey of Current Graphical Programming Techniques. Computer, 1985, 14(11), p.11-23.

[7] Reek, M.M. A Top-Down Approach to Teaching Programming. SIGCSE Bulletin, 1995, 27(1), p.6-9.