What is structured programming (was for/while else doesn't make sense)

Rustom Mody rustompmody at gmail.com
Fri Jun 17 12:32:10 EDT 2016


On Friday, June 17, 2016 at 7:23:27 AM UTC+5:30, Lawrence D’Oliveiro wrote:
> On Thursday, June 16, 2016 at 11:13:14 PM UTC+12, Rustom Mody wrote:
> 
> > Please see https://en.wikipedia.org/wiki/Nassi%E2%80%93Shneiderman_diagram
> > 
> > | Nassi–Shneiderman diagrams are (almost) isomorphic with
> > | flowcharts. Everything you can represent with a Nassi–Shneiderman
> > | diagram you can also represent with a flowchart.
> > 
> > which is in line with what I am saying, viz that break/continue/goto are same
> > in the sense of being 'unstructured' and therefore do not fit into a
> > structured framework like NSDs
> 
> This is just a restatement of the “structure theorem”, which proves that structured control statements are mathematically equivalent to gotos, and anything that can be expressed one way can be expressed the other way.
> 
> True, but a complete red herring.

I wonder whether "red herring" is your red herring <wink>


You talk of THE structure theorem.  Is there one?
Wikipedia's https://en.wikipedia.org/wiki/Structured_program_theorem has a 
references section with some two dozen links.

Many of these pull in significantly opposite direction with small changes in
conditions/clauses/definitions etc.

Here is a selection. Which is for you "THE theorem"?

[WHILE means language of structured programs -- think prototypical Pascal

FLOW is language of flowcharts]
===================================

Böhm and Jacopini show that that WHILE is equivalent to FLOW by showing
how to translate every program in FLOW into WHILE.  [Reverse translation is trivial] However...
Ashcroft and Manna [Translation of Goto to while]
Can every flowchart program be translated into an equivalent while
program without adding extra variables? (i.e., using only the original
state vector). NO!

[They go on]
Bohm and Jacopini have shown that every FLOW program can
be effectively translated into an equivalent WHILE program (WITH ONE WHILE
statement) hence the topology of the program is changed...
We (Ashcroft and Manna) show how to transform flowchart into while *preserving* topology.


Knuth and Floyd: [Notes on avoiding goto statements]
prove the existence of programs whose go to
statements cannot be eliminated without introducing procedure calls.

Kosaraju proved that it's possible to avoid adding additional variables in structured programming, as long as arbitrary-depth, multi-level breaks from loops are allowed.[1][14] Furthermore, Kosaraju proved that a strict hierarchy of programs exists, nowadays called the Kosaraju hierarchy, in that for every integer n, there exists a program containing a multi-level break of depth n that cannot be rewritten as program with multi-level breaks of depth less than n (without introducing additional variables)


=================================
IOW when you say "mathematically equivalent" you can mean whatever you like!!
Unless you clarify in what sense 'equivalent'


More information about the Python-list mailing list