编辑:介绍
为了面向更广泛的读者群,我通过一个详尽但有些繁琐的实例重新阐述了我的原始问题。原始问题如下所示(在下文中)。
汤姆刚被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怎么处理这样的混乱,有经验的程序员反复建议他
- 将程序分解成更小的部分;并
- 他得到了确认,在某些情况下使用
goto
是可以接受的;并且 - 他被告知需要 "重构" 程序。
汤姆非常勤奋,考虑了这些建议,他的想法如下:
- 他意识到如果流图的一个连通分量恰好有一个入度和一个出度,那么这可以被视为一个“子算法”,可以独立开发,因此他可以用这种方式拆分任务。然而,他不知道如何首先找到这样的组件,以及是否有其他智能的方法来进一步拆分问题。
- Tom并不真正关心使用
goto
是好还是坏的编程实践(请参见GOTO still considered harmful?),他关心的是在他的公司有某些需要始终遵循的编程指南。 - Tom确实可以改变算法,以便用他自己的判断力替换某些指令,从而得到等效的算法。然而,Tom不知道程序的哪个部分需要重构,更重要的是,他不理解为什么需要进行重构。Tom紧张地盯着他的1000个顶点的图形,不知道该如何开始实现它。
关于这篇(编辑后)文章的问题如下:
你能帮助Tom找出如何开始实施不是“两行显然”的东西吗?特别是,是否清楚应按照流程图节点描述的任务顺序实施?是否清楚某些嵌套循环应该一个接一个地按顺序进行?
流程图中最小的“原子”是什么,不能进一步分解成更小的部分?也就是说,Tom什么时候可以自信地回答stackoverflow说“我已经将我的算法分解成较小的部分了”?一切都基本上是while循环和/或二进制分支点(第一天和第二天的任务)吗?
如何自动实现这样的“原子”,并且基本上与Tom在第一天和第二天已经做到的方式相同?
Tom能否争论使用goto
在某些情况下是必要的,即他们使用它来实现某些算法,或者根据公司的指导方针没有其他实现方法(即不使用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
跳转。
然而,我对另一个方向感兴趣。简单搜索表明,DRAKON(请参见https://en.wikipedia.org/wiki/DRAKON和http://drakon-editor.sourceforge.net/)可能恰好做到了我所问的。从这个角度来看,问题是,如果不使用
goto
语句,这样的自动流程图到代码的程序如何工作?