如何将流程图转换为实现？ [英] How to transform a flow chart into an implementation?

问题描述

编辑：简介

为了接触更广泛的读者，我通过一个复杂的（有些乏味的）现实生活中的例子重新制定了我的原始问题。

Tom刚刚被雇用（取决于他在前两个工作日期间的表现）到Acme Inc.作为一个初级软件工程师。他的工作是实现由高级软件开发人员在编程语言Acme ++中设计的算法。该公司遵循严格的不 goto 的政策，由CEO的排他性命令。

在第一天，汤姆收到以下算法来实施。

 步骤1. START 
步骤2.输入x 
步骤3.如果x <0 goto步骤4否则转到步骤5 
步骤4.设置x = -x 
步骤5.输出x 
步骤6. END 
  

Tom认为任务非常复杂，他认为通过将其表示为流程图，他可以从研究程序的抽象结构中受益。绘制下图第一天的流程图后，他很快意识到，他被要求计算x的绝对值，他可以用一个简单的if-then-else语句实现它。

在第二天，汤姆收到以下算法来实现。

 步骤1. START 
步骤2.输入x 
步骤3.如果x <0，转到步骤2，否则转到步骤4 
步骤4.输出x 
步骤5. END 
  

一个新手，感觉再次更好地理解这个算法以抽象的方式，所以他绘制以下流程图第二天的流程图。

检查流程图显示，Tom被要求实现一个while循环，等待第一个非负输入。汤姆非常高兴，并在一天结束时完成他的任务。

根据他出色的表现，汤姆被雇用到公司。

然而，在第3天，汤姆在深处被扔进去，因为他收到了一个有1000行算法的1996 goto 跳跃，由公司的前雇员设计，没有人留在那里谁会知道什么算法，它是如何做到的，为什么它的设计在这样的方式首先。然而，这不涉及汤姆，因为他的唯一任务是实现算法，而不管它是什么。拥有前两天的专业知识，他绘制流程图上1000个节点与1997有向边。汤姆，非常绝望，请求stackoverflow什么是这样的混乱，经验丰富的程序员反复建议他

1. 分解程序变成小块;和


2. 他得到了保证，在某些情况下，确实可以使用 goto ;

，考虑这些建议，他的想法如下：


1. 他意识到如果流图的连接组件具有一个程度和正好一个出度，那么可以被认为是可以独立开发的子算法，因此他可以以这种方式分解他的任务。然而，他不知道如何找到这样的组件，以及是否还有其他智能方法来进一步分解这个问题。


2. Tom真的不在乎是否使用 goto 是一种好的或坏的编程习惯（请参阅 GOTO仍然认为有害吗？），他所关心的是，他的公司有一定的编程准则，他需要随时跟随。


3. Tom可以触摸算法，因为他可能会自行决定替换导致等效算法的某些指令。然而，汤姆不知道程序的哪一部分需要重组，更重要的是，他不明白为什么重组是必要的。汤姆紧张地盯着他的1000顶点图，并不真正知道如何开始实现它在第一位。







关于这个（编辑）帖子的问题如下：





你能帮助Tom找出如何开始实现不是两线死亡显而易见 ？特别是，很清楚，以什么顺序应该实现由流程图的节点描述的任务？很清楚，以什么顺序应该一个接一个的出现某些嵌套循环？





流程图中最小的原子是什么，不能进一步分解成更小的件？也就是说，Tom何时可以自信地回应我已经将我的算法分解为更小的部分的stackoverflow？是真的，一切都基本上是一个while循环和/或二进制分支点（第一天和第二天的任务）？





如何实现这样的原子自动，或多或少，就像汤姆在第一天和第二天已经做过的那样。





汤姆和CEO说，使用 goto 在某些情况下是必不可少的，也就是说，他们使用它来实现某种算法，或者根本没有其他方法来实现它的公司的指导方针（即没有使用 goto ）？





流图的哪些部分有问题，需要重组，为什么？例如，三向分支可以被嵌套的双向if-then-else语句替代，也就是说，Tom可以安全地假设他的流程图上的每个节点具有最多两个度。但是，什么其他重组应该处理由 goto 语句引起的所有嵌套循环？什么图形属性使重组是必要的？也许是高度的？





最初提出的算法（由软件开发团队）的流程图背后的数学（图形）理论是什么，以及实际上或多或少自动实现的算法的重构和分解流程图。





---





ORIGINAL QUESTION





假设我有一些使用二进制决定的算法， $ c> goto 语句。该算法在以下高级方式中在N> = 2（有限）步骤中描述，并且应当顺序地（逐个步骤地）执行：





算法WHATEVER

 步骤1. START 
第2步。如果步骤2中的条件持有转到步骤X，否则转到步骤Y. 
步骤3.做某事。如果步骤3中的条件持有转到步骤U，否则转到步骤V. 
步骤4.做某事。 
第5步。做某事。如果第5步中的条件持有goto ... 
步骤6. ... 
 ... 
步骤N. END 
  

你得到了想法。例如，Knuth在这样的编程语言独立的高级方式中描述了他的书中的算法。





现在的问题是如何转换这样的高级描述将 goto 语句转换为具有while循环和if / else语句的实际实现？是否可以完全消除所有 goto 语句，并用while循环替换它们？





根据算法的描述，可以构造相应的流程图，和因此（定向）流程图。因此，换句话说，问题是如何实现一个基于其流程图的代码，而不需要 goto 语句一般？。





有两种方法来回答这个问题。优选地，并且相当希望地，我正在寻找一种算法方法来实现ALGORITHM WHATEVER。如果ALGORITHM WHATEVER是非常简单的，那么直观地清楚应该怎么做，但是在我看来，一旦一个步骤被频繁访问，事情变得相当复杂（有许多goto语句跳跃到那里）或者换句话说，当流程图的节点之一具有大的in-degree时。然后我不明白什么特定的顺序while循环应该嵌套。另一方面，可能很有可能，一个人根本不能做我想要的一般，这样的答案应该支持一个高层次的ALGORITHM IMPOSSIBLE的描述，清楚地表明，无论什么，根本不能避免在实际实现中使用 goto 跳转。





在我看来， ：自动流程图工具和此处创建流程图的算法[一点指导]。程序 code2flow 似乎是可视化代码的良好起点。





但是，这里我对另一个方向感兴趣。简单的搜索结果显示， DRAKON （另请参阅 https://en.wikipedia.org/wiki/DRAKON 和 http://drakon-editor.sourceforge.net/ ）可能正在做我正在问的问题。从这个角度来看，问题是，这样的自动流程图代码程序如何在不使用 goto 语句的额外假设下工作？

解决方案

引用OP：最好是，我希望找到一个算法的方法来实现ALGORITHM WHATEVER 好吧，明显的答案是为目标语言为算法的每个步骤定义一个标签，为每个步骤在该标签上写入代码，并将GOTO语句完全插入ALGORITHM WHATEVER描述。这将给你一个工作程序，大多数将称为意大利面条代码。





OP有一个长期的介绍，表明他（或也许汤姆）





好的，好消息是序列， if -then-else 和 while循环，其中nice属性为单入，单退出。所以我们知道有一个结构化程序实现。不太好的消息是，他们的建设性证明（从gotoful /流程图版本构建这样的程序的过程）引入了一组布尔变量和附加测试来控制循环。这些变量用于跳过循环迭代的剩余部分，强制退出循环，并告诉循环调用者循环退出。这个额外的
代码，对我来说，即使你不反对管理这些变量所需的存储和执行时间，结果程序有点更糟。





更好的消息是，S. Rao Kosaraju演示了你构建这样的程序与NO附加控制变量，如果你可以突破任意嵌套深度的循环。许多编程语言提供这样的特征; C提供了一个脆弱的版本其break N;声明打破了N个嵌套循环[使用这个着名的AT& T的电话系统为东海岸，当有人在现有代码中插入一个额外的循环，没有注意到break语句]。 Ada和其他语言允许标记循环，并且基本上离开离开具有指定标签名称的循环。对我来说，这是一个漂亮的解决方案。 [我喜欢一种变体，其中有一个标记的开始 - 结束块，可以离开d。
如果你的语言没有这样的标签离开结构，但你愿意以风格批准的（而不是特别的方式）使用GOTO语句，你可以模仿leave语句，放置一个标签 after





因此，我们知道可以从任意的流程图/ gotoful中构建一个结构化的程序程序是干净的。





一个算法，通过将原来的流程图减少到结构化子元素，按照格雷厄姆1975年的论文，
< a href =http://dl.acm.org/citation.cfm?id=512979 =nofollow>用于全局流分析的快速且通常为线性的算法。





此算法的本质是在可能的情况下逐步将原始流程图减少到Bohm / Jacopini原语（sequence / if-then-else / loop）结构中，并减少不可缩减结构认为在流程图中的一个小结），看起来不像这些在一个特殊的方式。在每个步骤，流程图的一部分被缩减为该部分的单个汇总节点。最终，该过程将任意复杂度的原始流程图减少为单个节点。在这一点上，缩减过程可以反向运行，每个汇总节点扩展回原来的。





为了OP的目的，扩展汇总节点是以结构化方式编写缩减子图的代码的机会。重复直到生成原始流程图，然后导致整个程序以结构化的方式写入。





[这一切都是今天。让我们看看是否可以产生一个算法。看这个空间]。




EDIT: INTRODUCTION

To reach out towards a broader readership, I have reformulated my original question through an elaborate (and somewhat tedious) real-life example. The original question is shown (far) below.

Tom has just been hired (depending on his performance during his first two working days) to Acme Inc. as a junior software engineer. His job is to implement algorithms designed by the senior software developers, in the programming language Acme++. The company follows a strict "no goto" policy by the exclusive order of the CEO. In case Tom can perform exceptionally on his probation time, he will be offered a full time job at the company.

On day 1, Tom receives the following algorithm to be implemented.

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 4 otherwise goto Step 5
Step 4. Set x=-x
Step 5. Output x
Step 6. END

Tom feels like that the task is very complicated, and he thinks that he would benefit from studying the abstract structure of the program, by representing it as a flow chart. After drawing the following diagram Flow chart of day one he quickly realizes, that he was asked to compute the absolute value of x, and he can implement it with a simple if-then-else statement. Tom is very happy, and he finishes his task by the end of the day.

On day 2, Tom receives the following algorithm to be implemented.

Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 2 otherwise goto Step 4
Step 4. Output x
Step 5. END

Tom, being a newbie, feels like again it would be better to understand the algorithm in an abstract way, so he draws the following flow chart Flow chart of day two.

Inspection of the flow chart reveals that Tom was asked to implement a while loop which waits for the first nonnegative input. Tom is very happy, and finishes his task by the end of the day.

Based on his outstanding performance, Tom has been hired to the company.

On day 3, however, Tom is being thrown in at the deep end as he receives a 1000 line algorithm with 1996 goto jumps, designed by a former employee of the company, and there is noone else left there who would know what the algorithm does, how it does it, and why was it designed in such a way in the first place. However, this does not concerns Tom at all, as his sole task is to implement the algorithm irrespectively of what it is. Armed with the previous two day's of expertise, he draws the flow graph on 1000 nodes with 1997 directed edges. Tom, being very desperate, asks on stackoverflow what the heck to do with such a mess, where experienced programmers repeatedly advise him to

1. break up the program into smaller pieces; and
2. he got reassured that in certain cases it is actually ok to use goto; and
3. he is told to "restructure" the program.

Tom, being very diligent, considers these advices, and his idea is as follows:

1. he realizes that if a connected component of the flow graph has exactly one in-degree, and exactly one out-degree, then that can be considered as a "sub-algorithm" which can be developed independently, so he could break up his task in this manner. He, however, has no idea how to find such components in the first place, and whether there are other intelligent ways to break up the problem further.
2. Tom doesn't really care whether using goto is a good or a bad programming practice (see GOTO still considered harmful?), what he is concerned about is that there are certain programming guidelines at his company what he needs to follow at all times.
3. Tom can indeed touch the algorithm in the sense that he might replace certain instructions which lead to an equivalent algorithm at his own discretion. Tom, however, has no idea which part of the program requires restructuring, and more importantly, he doesn't understand why the restructuring is necessary. Tom nervously stares at his 1000-vertex graph, and doesn't really know how to begin implementing it in the first place.

The questions regarding this (edited) post are as follows:

Can you help Tom to figure out how to begin implementing something which is not "two-line-dead-obvious"? In particular, is it clear that in what order should one implement the tasks described by the nodes of the flow chart? Is it clear that in what order should come certain nested loops one after another?

What are the smallest "atoms" of the flow chart which cannot be further broken up into smaller pieces? That is, when can Tom confidently respond to stackoverflow that "I have broken up my algorithm into smaller parts already"? Is it true that everything is essentially a while loop and/or a binary branch point (the tasks of days one and two)?

How to implement such an "atom" automatically, more-or-less in the same way as Tom did it on days one and day two already?

Can Tom argue with the CEO that using goto in certain cases is essential, that is, either they use it to implement certain algorithm, or there is absolutely no other way to implement it according to the company's guidelines (that is, without the use of goto)?

What parts of the flow-graph are problematic and requires restructuring, and why? For example, a three-way branch could be replaced by a nested two-way if-then-else statement, that is, Tom could safely assume that each node on his flow chart has out degree at most two. But what other restructurings should be done to deal with all the nested loops caused by the goto statements? What graph-property makes the restructuring necessary? Perhaps, high in-degree?

What is the mathematical (graph) theory behind the flow chart of an originally proposed algorithm (by the software development team), and the restructured and broken up flow chart(s) of the algorithm(s) which one (say Tom) actually more-or-less automatically implements?

---

ORIGINAL QUESTION

Suppose that I have some algorithm which uses binary decisions and goto statements. The algorithm is described in N>=2 (finite) steps in the following high-level way, and it should be executed sequentially (one step after another):

ALGORITHM WHATEVER

Step 1. START
Step 2. Do something. If condition in Step 2 holds goto Step X else goto Step Y.
Step 3. Do something. If condition in Step 3 holds goto Step U else goto Step V.
Step 4. Do something.
Step 5. Do something. If condition in Step 5 holds goto...
Step 6. ...
...
Step N. END

You get the idea. For example, Knuth describes the algorithms in his books in such a programming-language independent, high level way.

The question is now how to transform such a high-level description with goto statements into an actual implementation with while loops and if/else statements? Is it possible to completely eliminate all the goto statements, and replacing them by a while loop? If so, how should one do this in general?

Based on the description of the algorithm it is possible to construct the corresponding flow chart, and hence the (directed) flow graph. So the question in other words is "How to implement a code based on its flow chart without goto statements in general?".

There are two ways to answer this question. Preferably, and quite hopefully, I am looking for an algorithmic way to implement ALGORITHM WHATEVER. If ALGORITHM WHATEVER is very simple, then it is intuitively clear what one should do, but it seems to me that things get quite complicated once a step is visited frequently (there are many goto statements jumping there), or, in other words, when one of the nodes of the flow graph has a large in-degree. Then I don't quite see in what particular order the while loops should be nested. On the other hand, it might very well be possible that one simply cannot do what I want in general, and such an answer should be backed up by a high-level description of ALGORITHM IMPOSSIBLE which clearly demonstrates that no matter what, one simply cannot avoid using goto jumps in an actual implementation.

It seems to me that transforming implementation into flowcharts were asked several times: Automatic flowchart tool and here Algorithm to create flow chart [A little guidance??]. The program code2flow seems to be a good starting point for visualising a code.

However, here I am interested in the other direction. A simple search revealed that DRAKON (see also https://en.wikipedia.org/wiki/DRAKON and http://drakon-editor.sourceforge.net/) might be doing exactly what I am asking about. From this perspective, the question is, how might such an automatic flowchart-to-code program work under the extra assumption that it does not use the goto statement?

解决方案

Quoting OP: Preferably, and quite hopefully, I am looking for an algorithmic way to implement ALGORITHM WHATEVER

Well, the obvious answer is to define a label in the target language for each step of the algorithm, write the code for each step at that label, and insert GOTO statements exactly as ALGORITHM WHATEVER describes. That will give you a working program that most would call "spaghetti code".

OP has a long-winded introduction that suggests he (or maybe Tom) would prefer to write a goto-free version in a way that convincingly matches ALGORITHM WHATEVER.

OK, so the good news is that Bohm and Jocopini long ago showed that you can implement any computation with just the three basic control flow operations of sequence, if-then-else, and while loops, with the nice property of being single-entry, single-exit. So we know there is a "structured program" implementation.

The not so good news is that their constructive proof (procedure for building such a program from a gotoful/flowchart version) introduces a set of boolean variables and additional tests to control the loops. These variables are used to skip the remainder of a loop iteration, to force exit from the loop, and tell the loop-invoker that the loop exited. This extra code, for me, makes the resulting program somewhat worse to read even if you don't object to the storage and execution time needed to manage those variables. (See the wikipedia link for an algorithm that does this for goto-ful COBOL programs).

Better news is that S. Rao Kosaraju demonstrated that you build such programs with NO additional control variables if you can break out of loops of arbitrary nesting depth. Many programming languages offer such a feature; C offers a fragile version with its "break N;" statement that breaks out of N nested loops [using this famously crashed AT&T's telephone system for the East Coast when somebody inserted an extra loop in existing code and didn't notice the break statements]. Ada and other languages allow one to label the loops, and essentially "leave " to leave the loop with specified label name. For me, this is a pretty solution. [I prefer a variant in which one has a labelled begin-end block that can be "leave"d. If your language does not have such a labelled-leave construct, but you are willing to use GOTO statements in a stylistically approved (rather than ad hoc manner), you can simulate leave statements by placing a label after each loop and writing "goto " instead of leave.

So, we know understand it is possible to build a structured program out of an arbitrary flowchart/gotoful program that is clean.

An algorithm to do this works by reducing the original flowchart into structured sub elements, along the lines of Sue Graham's 1975 paper, A fast and usually linear algorithm for global flow analysis.

The essence of this algorithm is to stepwise reduce the original flowchart into the Bohm/Jacopini primitives (sequence/if-then-else/loop) constructs where possible, and reducing "non-reducible" constructs (think of a small knot in the flowchart) that don't look like these in a special way. At each step, a part of the flowchart is reduced to a single summary node for that part. Eventually, this process reduces the original flowchart of arbitrary complexity into a single node. At this point, the reduction process can be run in reverse, with each summary node expanded back to the original.

For OP's purpose, expansion of the summary node is the opportunity to write code for the reduced subchart in a structured way. Repeating until the original flowchart is produced then causes the entire program to be written in a structured way.

[That's all for today. Let's see if I can produce an algorithm. Watch this space].

这篇关于如何将流程图转换为实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！