如何将流程图转换为实现?

7

编辑:介绍

为了面向更广泛的读者群,我通过一个详尽但有些繁琐的实例重新阐述了我的原始问题。原始问题如下所示(在下文中)。

汤姆刚被Acme公司聘为初级软件工程师(根据他前两个工作日的表现)。他的工作是使用编程语言Acme++实现高级软件开发人员设计的算法。该公司严格执行CEO的“不使用goto”政策。如果汤姆可以在试用期内表现出色,他将获得该公司的全职工作机会。

第一天,汤姆收到了要实现的以下算法。

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觉得任务非常复杂,他认为通过将程序表示为流程图来研究抽象结构会对他有所裨益。在绘制以下第一天的流程图后,他很快意识到被要求计算x的绝对值,并且可以使用简单的if-then-else语句来实现。Tom感到非常高兴,并在当天完成了任务。
第二天,Tom收到了以下要实现的算法。
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觉得更好的理解算法的方法是以抽象的方式来绘制流程图第二天的流程图

检查流程图后发现,Tom被要求实现一个while循环,等待第一个非负输入。Tom感到非常高兴,最终在当天完成了任务。

由于他出色的表现,Tom已经被公司雇佣。

然而,在第三天,Tom被扔到深水区,他接收到了一个1000行算法,其中有1996个goto跳转,这是由该公司的一名前员工设计的,没有其他人知道该算法做什么,如何做以及为什么要这样设计。然而,这并不会让Tom感到担忧,因为他的唯一任务是无论如何实现该算法。凭借前两天的经验,他绘制了具有1000个节点和1997个有向边的流程图。Tom非常绝望,询问stackoverflow怎么处理这样的混乱,有经验的程序员反复建议他

  1. 将程序分解成更小的部分;并
  2. 他得到了确认,在某些情况下使用 goto 是可以接受的;并且
  3. 他被告知需要 "重构" 程序。

汤姆非常勤奋,考虑了这些建议,他的想法如下:

  1. 他意识到如果流图的一个连通分量恰好有一个入度和一个出度,那么这可以被视为一个“子算法”,可以独立开发,因此他可以用这种方式拆分任务。然而,他不知道如何首先找到这样的组件,以及是否有其他智能的方法来进一步拆分问题。
  2. Tom并不真正关心使用goto是好还是坏的编程实践(请参见GOTO still considered harmful?),他关心的是在他的公司有某些需要始终遵循的编程指南。
  3. Tom确实可以改变算法,以便用他自己的判断力替换某些指令,从而得到等效的算法。然而,Tom不知道程序的哪个部分需要重构,更重要的是,他不理解为什么需要进行重构。Tom紧张地盯着他的1000个顶点的图形,不知道该如何开始实现它。

关于这篇(编辑后)文章的问题如下:

你能帮助Tom找出如何开始实施不是“两行显然”的东西吗?特别是,是否清楚应按照流程图节点描述的任务顺序实施?是否清楚某些嵌套循环应该一个接一个地按顺序进行?

流程图中最小的“原子”是什么,不能进一步分解成更小的部分?也就是说,Tom什么时候可以自信地回答stackoverflow说“我已经将我的算法分解成较小的部分了”?一切都基本上是while循环和/或二进制分支点(第一天和第二天的任务)吗?

如何自动实现这样的“原子”,并且基本上与Tom在第一天和第二天已经做到的方式相同?

Tom能否争论使用goto在某些情况下是必要的,即他们使用它来实现某些算法,或者根据公司的指导方针没有其他实现方法(即不使用goto)?

哪些流程图的部分存在问题需要重构,为什么?例如,一个三路分支可以被嵌套的两路 if-then-else 语句替换,也就是说,汤姆可以安全地假设他流程图上的每个节点最多只有两个出度。但是,由于 goto 语句引起的所有嵌套循环,还应该进行哪些重构?是什么图形属性使得重构成为必要?也许是高入度?
原始算法(由软件开发团队提出)的流程图以及算法的重构和拆分后的流程图(例如 Tom 实际上自动实现的流程图),背后的数学(图)理论是什么?

原始问题

假设我有一个使用二进制决策和goto语句的算法。该算法以以下高级方式描述,包含N>=2 (有限)步骤,并且应按顺序(一个接一个地)执行:

无论什么算法

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

你明白了吧。例如,Knuth在他的书中以编程语言无关的高级方式描述算法。
现在的问题是如何将带有goto语句的高级描述转换为使用while循环和if / else语句的实际实现?是否可能完全消除所有goto语句,并用while循环替换它们?如果可以,那么应该如何在一般情况下完成呢?
基于算法的描述,可以构造相应的流程图,因此也就得到了(有向)流图。因此,换句话说,问题是“如何根据其流程图实现代码而不使用goto语句(在一般情况下)?”

回答这个问题有两种方式。首选,也是最希望的,我正在寻找一种算法实现ALGORITHM WHATEVER的方法。如果ALGORITHM WHATEVER非常简单,那么应该很容易直观地知道该做什么,但是当一个步骤被频繁访问(有许多goto语句跳转到该步骤),或者换句话说,当流图的一个节点具有大的入度时,事情似乎变得非常复杂。然后我不太清楚while循环应该嵌套在什么特定的顺序中。另一方面,可能根本就无法在一般情况下做到我想要的事情,这样的答案应该由ALGORITHM IMPOSSIBLE的高级描述支持,清楚地表明无论如何,在实际实现中都不能避免使用goto跳转。

我认为将实现转换为流程图已经被要求多次了:自动流程图工具创建流程图的算法[A little guidance?]。程序code2flow似乎是可视化代码的一个很好的起点。
然而,我对另一个方向感兴趣。简单搜索表明,DRAKON(请参见https://en.wikipedia.org/wiki/DRAKONhttp://drakon-editor.sourceforge.net/)可能恰好做到了我所问的。从这个角度来看,问题是,如果不使用goto语句,这样的自动流程图到代码的程序如何工作?

您IP地址为143.198.54.68,由于运营成本限制,当前对于免费用户的使用频率限制为每个IP每72小时10次对话,如需解除限制,请点击左下角设置图标按钮(手机用户先点击左上角菜单按钮)。 - AakashM
请注意,当然执行状态机的引擎正在执行“goto”操作;只是它们被美化了。 - AakashM
@AakashM 流程图(或状态图)已经给出,因为它等同于逐步算法规范。我的问题是如何根据规范或流程图实现某些东西。 - Matsmath
在http://flowgrid.org中绘制流程图并运行它? :) http://i.imgur.com/8NueBvC.png - Stefan Haustein
3个回答

6

引用OP的话:最好并且很有希望,我正在寻找一种算法实现ALGORITHM WHATEVER的方法

显而易见的答案是为算法的每个步骤定义目标语言中的标签,在该标签处编写每个步骤的代码,并插入与ALGORITHM WHATEVER完全相同的GOTO语句。这将给你一个大多数人称之为“意大利面条代码”的工作程序。

OP有一个冗长的介绍,表明他(或者可能是Tom)更喜欢以一种令人信服地匹配ALGORITHM WHATEVER的方式编写无goto版本。

好消息是Bohm和Jocopini早就证明,你可以仅使用序列if-then-elsewhile循环这三种基本控制流操作来实现任何计算,具有单入口、单出口的良好特性。所以我们知道有一种“结构化程序”实现方法。

不太好的消息是,他们的构造性证明(从有goto/流程图版本的程序构建的过程)引入了一组布尔变量和额外的测试来控制循环。这些变量用于跳过循环迭代的其余部分,强制退出循环,并告诉循环调用者循环已退出。对我而言,这些额外代码使得生成的程序在阅读上有些难度,即使您不反对管理这些变量所需的存储和执行时间。(请参见维基百科链接以获取适用于具有goto的COBOL程序的算法)。
更好的消息是,S. Rao Kosaraju证明,如果您可以打破任意嵌套深度的循环,则可以构建此类程序而无需额外的控制变量。许多编程语言都提供了这样的功能;C语言通过其“break N;”语句提供了一个脆弱的版本,可以跳出N个嵌套循环[当有人在现有代码中插入额外的循环并没有注意到break语句时,就会像AT&T东海岸的电话系统一样崩溃]。Ada和其他语言允许给循环加标签,并且基本上可以使用“leave”来离开具有指定标签名称的循环。对我来说,这是一个不错的解决方案。[我更喜欢一种变体,其中有一个带标签的开始-结束块,可以“离开”。如果您的语言没有这样的标记离开结构,但您愿意以一种风格上批准的方式(而不是特别的方式)使用GOTO语句,那么您可以通过在每个循环后放置一个标签并写入“goto”而模拟离开语句。

因此,我们现在知道可以从任意流程图/跳转程序构建一个结构化程序,这个程序是干净的。

一种实现此目的的算法通过将原始流程图减少为结构化子元素,沿着Sue Graham的1975年论文A fast and usually linear algorithm for global flow analysis的思路进行。该算法的本质是逐步将原始流程图缩小到Bohm / Jacopini基元(序列/ if-then-else /循环)构造中,并以特殊方式减少“不可减少”的构造(想象一下流程图中的一个小结)。在每个步骤中,流程图的一部分被减少到该部分的单个摘要节点。最终,这个过程将任意复杂度的原始流程图缩小为单个节点。此时,可以运行反向减少过程,将每个摘要节点扩展回原始状态。对于OP的目的,扩展摘要节点是以结构化方式编写减少的子图的代码的机会。重复直到产生原始流程图,然后整个程序都以结构化方式编写。[今天就到这里。让我们看看我能否制作出算法。请关注此处]。

我相信你的帖子几乎涵盖了Tom所有的疑虑:结构化程序定理保证了可以消除goto跳转,而Sue Graham的论文(我稍后会从ACM获取)将流程图缩小到更小的组件,这样Tom就知道哪部分实现需要他的关注。我会继续关注SO,看看你是否会有其他的发言。感谢你提供的优秀参考资料。 - Matsmath

1
如果我们将ALGORITHM WHATEVER中的每个“Do something”语句视为返回TRUE或FALSE的函数,则可以使用以下伪代码进行操作:
让N为int curr_state为int T [1..N]是int数组 F [1..N]是int数组 Func [1..N]是返回布尔值的函数数组
1. curr_state:= 1 2. 当curr_state!= N + 1时执行/*结束状态*/ 3. 如果(Func [curr_state] == TRUE)则 4. curr_state:= T [curr_state] 5. 否则 6. curr_state:= F [curr_state] 7. 结束循环 8. 完成
有人可能会问:“但如果这些函数需要参数或需要修改一些共享状态怎么办?”原则上,函数参数和共享状态都可以存储在全局变量中(在算法范围内)。实际上,你可能会做一些略微不同的事情。

是的,这非常聪明。实际上我在想一个非常相似的解决方案,就是用函数调用代替goto语句的形式。因此,本质上,我会执行“做某事然后执行你在X时要做的事情”,而不是规范规则“做某事并转到X”。我对这两种方法不太满意的原因是,一定程度上函数Func应该理解整个算法。 - Matsmath
@Matsmath 不只有一个Func;有N个不同的Funcs,每个对应于N个不同的“做某事”的操作。 - mhum
更准确地说,Func内的函数应该一次性理解整个算法,这在实践中可能非常难以实现。(我不小心按了回车键,然后超出了5分钟允许的编辑时间...)。 - Matsmath
@Matsmath 好的。但是如果“做某事”的实现很困难,我不确定有什么比它更容易的事情可以做。 - mhum

1
嵌入式软件社区已经使用这样的工具有一段时间了,但成功的程度不同。我不再开发那种软件了,但是在十年前,有Rational Rose RT(我认为IBM收购了他们),MATLAB Simulink,MATLAB Real-time Workshop和其他工具。它们可以接受各种类型的图形输入(无论是类图、状态图还是流程图),并生成C++代码。
从你描述的例子来看,不太确定你是否描述的是有限状态机,其中状态转换原子仅取决于观察到的状态(这就是流程图的工作方式),还是描述了更多的专家系统,其中转换项不仅关心观察到的状态,而且关心在到达该状态之前发生的转换。
如果您正在描述前者,则只需注意您的goto标签本身就是状态。流程图中每个决策块都成为状态转换函数,它作用于某些信息宇宙,并在完成后设置新状态。新状态可能是“END”或其他状态。信息宇宙通常是共享的(即共享内存)在所有状态转换函数之间。软件实现通常是命令设计模式的某个变体(GoF)。
如果你正在描述后者,那么可以查看Rete算法。Rete算法是一种优化的通用算法,用于实现任何专家系统的规则集。

关于共享内存的观点很好。我忘了强调算法 WHATEVER 可能使用全局变量。虽然我不能说我深刻理解有限状态机(FSM)和专家系统之间的关系,但我觉得在这一点上,我只会根据程序规范(=流程图=FSM)进行一个脚踏实地的实现,而不是依赖更高级的工具,比如巧妙地使用人工智能和分支预测。谢谢。 - Matsmath

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接