From: Lieven Marchand <mal@bewoner.dma.be>
Subject: Re: Status of Bohm-Jacopini Theorem
Date: 11 May 2000 19:08:31 +0200
Newsgroups: comp.theory,sci.math
Summary: [missing]

Boudewijn Moonen <Boudewijn.Moonen@ipb.uni-bonn.de> writes:

> In their seminal - yet, strangely, apparently not widely known -
> 1966 paper [1], Bohm and Jacopini established the fundamental
> result that any computer program can be rewritten as a *structured*
> program, i.e. a program using recursively only the following three 
> basic flow control constructs
> 
>     - sequence
>     - iteration
>     - alternative
> 

How obscure is it? I've seen it cited and I think most people with a
CS degree know it as a folk theorem.

>     1) What is the actual status of the Bohm-Jacopini result nowadays?
>        Is it considered as having been proved rigorously, or only
>        sketched, or is its proof regarded as being incomplete?
> 

I'd say it's proven.

>     2) Is there an elaborated version of their result somewhere in
>        the accessible literature?
> 

A reference to a more elaborate explanation of the construction is:

H.D. Mills, Mathematical foundations for structured programming. Report
FSC 72-6012. IBM Federal Systems Division, 1972.

Another interesting result is a theorem by Lipton, Eisenstadt and DeMillo:

for any large integer n, there exists an n statement program using goto,
that cannot be converted to a structured goto less form of less than
(1.3)^sqrt(n) statements, unless that programs runs at least a factor
1/2 log_2(n) slower.

The last version of that theorem is in Journal of the ACM 27(1980),123-127.

A better elimination technique than Bohm and Jacopini is in:

Ashcroft & Manna, The translation of go to programs to while programs,
Information Processing 71, Proceedings of IFIP congres 71 (Amsterdam,
North Holland, 1972) pp 250-255.


>     3) Can someone give an intuitive/heuristic argument why their result
>        holds?
> 

Cut up the program in basic blocks. Put them all in one giant while
loop conditionally executed on boolean variables and change the goto's
to the appropriate settings of the boolean variables.

-- 
Lieven Marchand <mal@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
==============================================================================

From: eclrh@sun.leeds.ac.uk (Robert Hill)
Subject: Re: Status of Bohm-Jacopini Theorem
Date: Thu, 11 May 2000 18:34:22 +0100 (BST)
Newsgroups: comp.theory,sci.math

In article <391AC666.22F32466@ipb.uni-bonn.de>, 
Boudewijn Moonen <Boudewijn.Moonen@ipb.uni-bonn.de> writes:

> In their seminal - yet, strangely, apparently not widely known -
> 1966 paper [1], Bohm and Jacopini established the fundamental
> result that any computer program can be rewritten as a *structured*
> program, i.e. a program using recursively only the following three 
> basic flow control constructs
> 
>     - sequence
>     - iteration
>     - alternative
> 
> (as a side remark, they even show the first two suffice). Together
> with Dijkstra's notorious letter to the editor [2], where this result
> is cited, this got structured ("GOTOless") programming off the ground.
> 
> However, there seem to be some reservations around about how rigorously
> this has been proved.
> 
> [...]
> 
> Thus I decided to look up the old paper [1] and found it cryptic and
> obscure,
>
> [...]
> 
> I therefore have the following questions:
> 
>     1) What is the actual status of the Bohm-Jacopini result nowadays?
>        Is it considered as having been proved rigorously, or only
>        sketched, or is its proof regarded as being incomplete?
> 
>     2) Is there an elaborated version of their result somewhere in
>        the accessible literature?
> 
>     3) Can someone give an intuitive/heuristic argument why their result
>        holds?
> 
> Any comment welcome.

D.E. Knuth's famous paper "Structured Programming with GOTO statements" 
(which was probably in Comm. ACM in 1974) cites a paper (or letter or note) 
by D.C. Cooper, which points out that Boehm and Jacopini's paper says less 
than it seems to say.  I think (that Knuth says that Cooper says)
that B&J's paper effectively says not much more than this:  
given a program P in a language L, we can write a GOTO-less interpreter I 
for language L.  We can then execute I with P as input.

Disclaimers: I have never read the B&J paper, or Cooper's paper
(despite the fact that Cooper was later my boss from 1975 to 1977).
Though I have read the Knuth paper more than once, I have not read it
for at least 15 years.  So my memories may be all wrong.  

-- 
Robert Hill
Information Systems Services
University of Leeds