Converting flowchart to pseudocode

[sandy.bridge]

Homework Statement

The problem I am having trouble with has to do with pseudocode and flowcharts. We were told that indeed any pseudocode can be represented by flowcharts; however, our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode. I am having trouble seeing this, so perhaps you guys can help.

Here are the rules pertaining to the flowcharts:
atomic actions are represented by rectangular boxes. There is one arrow in and one arrow out.
Start and Stop has one arrow out and one arrow in, respectively. They are represented by oval boxes.
Diamond boxes denote choices/conditions. It says there can be one arrow in and two out (true/false).
Bullets can have one or more arrow in and one arrow out; purely presentational.

The Attempt at a Solution

I have tried numerous combinations but it seems that I am able to convert them all into pseudocode given these rules. Any ideas?

 

[jedishrfu]

The only thing I can think of is that its related to the halting problem or if an atomic operation has some sort of side-effect.

 

[sandy.bridge]

Yeah, this is the last question and it certainly has me stumped. He has yet to talk about said "halting problem" or any possible adverse side-effects exhibited by atomic actions.

I can do the opposite; that is, I could develop pseudocode that cannot be represented by the flowcharts (with his set of rules) easily. For example, if I did a pseudocode that had a choice branch that had more than two options it would require more than two arrows to leave the diamond. However, working from flowcharts to the pseudocode appears to be more difficult.

 

[rcgldr]

our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode.

It seems that this would require an arbitrary restriction on pseudcode that wasn't applied to flowcharts in your class.

Note that there are programs like AllClear that generate flowcharts based on a psuedocode like language that the user inputs into a text file, so I'm not sure of the point your professor is trying to make.

 

[gneill]

If the pseudocode language forbids GOTO with labeled destinations, then I imagine you could lay out a flow chart with jumps into and out of overlapping loop structures that would be pretty hairy to render into pseudocode.

 

[sandy.bridge]

I'm not sure what point he is trying to make either. He explicitly points out that all flowcharts can be represented by pseudocode (opposite true as well), but he says that given the rules presented in topic 2 (which I have shared with you guys already) it is possible to build a flowchart that cannot be represented by pseudocode. I might just have to take an L on this one.

 

[jedishrfu]

I'm not sure what point he is trying to make either. He explicitly points out that all flowcharts can be represented by pseudocode (opposite true as well), but he says that given the rules presented in topic 2 (which I have shared with you guys already) it is possible to build a flowchart that cannot be represented by pseudocode. I might just have to take an L on this one.

Be creative and come up with something perhaps mix quantum entanglement into the picture or fuzzy logic. You might still get a laugh and a better grade and you just might disover what he's alluding to.

One thing I noticed is that interrupts don't seem to be included so that basically the atomic action occurs and can't be interrupted. Also what about exceptions when the atomic operation fails. These two states would require a receive interrupt arrow and transmit interrupt arrow.

 

[jedishrfu]

what if you tied the output of the if to the input of the if? How would you represent that as programmable psuedo code?

 

[sandy.bridge]

Right, that makes sense. No where in the rules does he specify rules pertaining to the different types of choice blocks that there is; hence, if you had an if block that had the true connected to very same if block, it wouldn't able to be converted to pseudocode.

What about an atomic action looped to itself? Essentially there would be no end. With pseudocode, this would have to be repetition and therefore a choice block. Does that make sense?

 

[rcgldr]

what if you tied the output of the if to the input of the if? How would you represent that as programmable psuedo code?

As a while loop

    while(interrupt_occurred == false)
    endwhile

or with a label and goto

wait_for_interrupt:
    if(interrupt_occurred == false)
        goto wait_for_interrupt

 

[gneill]

Much depends upon what control structures are available in the given pseudocode language. Are GOTOs permitted? Recursion?

 

[sandy.bridge]

There is nothing mentioned of GOTOs or recursion. This is a course in C++ and it is intended for students who have never programmed before. This is the second week of classes, and therefore, the programming language itself has barely crept its way into lectures.

 

[gneill]

There is nothing mentioned of GOTOs or recursion. This is a course in C++ and it is intended for students who have never programmed before. This is the second week of classes, and therefore, the programming language itself has barely crept its way into lectures.

The elements of the pseudo code language were not presented? How can one claim that something cannot be implemented in a language that is not specified?

 

[sandy.bridge]

Very minimal was stated about pseudocode. Here is the only information presented:
"It is quite common, in textbooks and research reports, to see algorithms written in a hybrid
of plain language and a programming language throughout Computer Science; we call these
hybrid descriptions “pseudocode” (pseudo- is a prefix that means “fake”). The idea behind
pseudo-code is to use the best of both languages. We will use plain English to describe actions
that do not need to be expressed with pin-point precision, and use programming language constructs
when the actions require precision. Do not be too concerned at this point if you don’t feel
you can tell the difference yet; it is something that comes with experience and practice.
In this course, we will focus on using language to communicate algorithms, but we’ll also
use diagrams called flow charts from time to time to help clarify our explanations."

From this description he immediately goes into applying pseudocodes to flowcharts. The question specifically states that we can answer that question based on the rules that we have for the flowcharts. It even directs me to the slide that the rules are on (which I have given).

Furthermore, for the example one can use abstract components; they need not to have meaning.

 

[gneill]

So, the flowchart rules, as given, do not place any limit on the number of STARTs?

 

[sandy.bridge]

Yeah, it does say only one of each. Thought I had that in there but I missed that. I just double checked the rest is essentially word for word:

atomic actions are represented by rectangular boxes. There is one arrow in and one arrow out.
Start and Stop has one arrow out and one arrow in, respectively. They are represented by oval boxes, and there is only one of each
Diamond boxes denote choices/conditions. It says there can be one arrow in and two out (true/false branches).
Bullets can have one or more arrow in and one arrow out; purely presentational; they have no function.

 

[rcgldr]

Bullets can have one or more arrow in and one arrow out; purely presentational; they have no function.

Bullets would be the equivalent of labels in pseudocode. Again, since some flowchart tools like AllClear use pseudocode to create flowcharts, I don't see why your professor is claiming that some flow charts don't have a pseudocode equivalent.

 

[Joffan]

Are arrows obliged to connect two elements, or can you just leave them dangling?

 

[sandy.bridge]

It doesn't say anything about that, but if there are no atomic actions/conditions left to be executed it is assumed one goes to "stop"

 

[tip_top]

Page 19 in the textbook sets out the constraints of an algorithm. It must be unambiguous, executable and terminating. Infinite loop violates this.

 

[rcgldr]

Page 19 in the textbook sets out the constraints of an algorithm. It must be unambiguous, executable and terminating. Infinite loop violates this.

True, but neither pseudocode or a flowchart has to meet these requirements, and an infinite loop could be used as an alternative to termination. With a multi-tasking OS, sometimes the "idle state" or "idle task" is an infinite loop (as opposed to a halt instruction, which may intefere with normal operation or perhaps intefere with a debugger in some environments (depending on the processor and the debugger)).

 

[sandy.bridge]

I'm going to assume tip_top is in my class. The only thing that I see on page 19 regarding flow charts is the very last sentence: a flow chart has no ambiguities, since it always uses explicit arrows to direct the flow to the next action.

 

[D H]

The problem I am having trouble with has to do with pseudocode and flowcharts. We were told that indeed any pseudocode can be represented by flowcharts; however, our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode.

The Böhm-Jacopini theorem says that any algorithm can be implemented using only three constructs: sequence (a; b; c; ...), selection (if else), and iteration (while).

However, if you restrict how selection and iteration work there are algorithms that can be expressed via flowcharts but cannot be represented using those limited forms of selection and iteration. For example, disallow the use of auxiliary variables and you cannot express a flowchart that has an escape from multiple levels of loops^1[/color].

Aside: Some languages provide a multi-level escape mechanism (e.g., Java), others don't (e.g., C and C++). This lack of a multi-level break in C/C++ is oftentimes one of the few allowed uses of goto.


^1[/color] Kozen and Tseng, The Böhm–Jacopini Theorem is False, Propositionally, in Proceedings of the 9th International Conference, Mathematics of Program Construction 2008
pdf: http://ecommons.library.cornell.edu/bitstream/1813/9478/4/BohmJacopini.pdf

 

[sandy.bridge]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

 

[Joffan]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

If you are strict about the arrow counts, then bullets are not merely decorative; they are essential to gather inputs in such cases.

 

[sandy.bridge]

I'm not strict about arrow counts, but we are to follow the rules we were given in regards to flow chart construction. Having more than one input to actions or conditions violates the rules we were given and therefor does not address what the problem is asking.

 

[Joffan]

What I'm saying is that you can bring such a flowchart back into conformance by adding a bullet above a multiple-input box, putting all inputs to that bullet and sending the bullet output to the box of concern.

 

[sandy.bridge]

I like the way you think!

 

[D H]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

Those are finite state machine transition diagrams, not flow charts. That said, it's fairly easy to convert either a Moore machine diagram or a Mealy machine diagram into a flow chart. You might get lines that cross and cannot be uncrossed -- and that's a sign of trouble for translation to a hobbled pseudocode.

 

[sandy.bridge]

Alright, let's see if I was able to capture that idea with the attached flow chart.

 

[rcgldr]

Alright, let's see if I was able to capture that idea with the attached flow chart.

As mentioned before, those "bullets" or "connectors" are the equivalent of branch target labels in pseudocode.

 

[sandy.bridge]

I don't know, then. I've tried looking online, but have not found anything. I have 2 friends in CompSci that think all flow charts can be represented by pseudo-code. I am just not seeing it.

 

[gneill]

If the rules, strictly interpreted, allow decision block outputs to feed back to their inputs, then you can create a situation where 1) there are "hidden" START points implying multithreading, and 2) create race conditions that can affect subsequent program logic.

 

[sandy.bridge]

Okay, and what happens when the conditional gets X=0 and X=1 at the same time? And in the last atomic action where you wrote "Do something clever", are you referring to me? Is this my time to shine?

 

[gneill]

Okay, and what happens when the conditional gets X=0 and X=1 at the same time?

That's the "race condition"; No telling which path will be the last one to set the variable's value.

Of course the argument against this "solution" is that there's no path to either branch from the start box, so that neither branch would be able to execute, and the branches (more correctly "tributaries"?) represent "dead code".

And in the last atomic action where you wrote "Do something clever", are you referring to me? Is this my time to shine?

Ha! Never thought about it that way... I just needed something to put in the box.

 

[sandy.bridge]

Interesting. So not only is there a race condition, both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct? From what I know, you start at "START", and end and "STOP", and therefore those conditions would not be able to be represented between START and STOP.

 

[gneill]

Interesting. So not only is there a race condition, both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct? From what I know, you start at "START", and end and "STOP", and therefore those conditions would not be able to be represented between START and STOP.

That's more or less it. While it's possible to write "dead code" in pseudo code (just put a branch around it), I don't think there's a way to exactly reproduce the structure of such a race condition.

 

[rcgldr]

both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct?

One method for multi-threading psuedocode is to use sequences. All sequences in this example would start and run at the same time in parallel. To duplicate the race condition in your flowchart with pseudocode, but without the uneeded conditionals:

sequence
    x = 1
endsequence

sequence
    x = 0
endsequence

sequence
    if(x == 1)
        then docleverthing
endsequence

CH USB gaming controllers includes a scripting language that uses this same syntax (sequence , endsequence), for multi-threading, except it's sequences continously loop. Generally the sequences wait for controller button presses / releases, or continously convert physical controller inputs to virtual controller outputs (this is done at some fixed sampling rate that is adjustable).

The structure of the race condition flow chart is faulty. You can't have 3 parallel threads of code merge into a single thread. What the flowchart should look like is 3 flow charts with starts and stops, but sharing a common variable, x. Treat each thread as if it's running on it's own processor, and that only memory (in this case "x") is shared. There shouldn't be any arrows connecting the "x = 0" thread and the "x = 1" thread into the "x == 1?" thread, since these are independent threads. For example, you could consider the "x=0" and "x=1" threads as input devices with dma access to the variable x, and these input devices could not switch into the context of executing code from the "x == 1?" thread.

 

[sandy.bridge]

So are the threads going to come together at any joints at all? Or are we merely running the three threads at the same time?

 

[gneill]

The structure of the race condition flow chart is faulty. You can't have 3 parallel threads of code merge into a single thread.

Well, the point is that by the given rules the flowchart is valid. Whether or not it is meaningful or "correct" is another matter Not my fault if the rules are faulty or incomplete!

Cray had a form of parallelism called autotasking, implemented at the compiler/library level. With it logical threads could be spawned, merged, and dismissed automagically. For example, a DO LOOP might automatically be split into several portions to be worked on by separate tasks (threads), then the results merged upon completion. The language (a version of FORTRAN) didn't have to explicitly specify the action at each instance. Threads simply joined the fray, results merged, and then disappeared leaving a single serial thread to carry on. While all the logically correct details were managed below the surface, the code that the user wrote and saw simply looked like a typical single-thread serial code.

 

[rcgldr]

So are the threads going to come together at any joints at all? Or are we merely running the three threads at the same time?

You're running three threads at the same time, at least initially. The flow chart implies that the three threads become one thread where the arrows connect in at the middle.

The flowchart would be valid if those arrows from the outer threads connecting to the inner thread represented termination of those outer threads, and that the inner thread was pending on completion of both outer threads (order not important, so you still have the race condition) before continuing. This would be the windows equivalent of the inner thread doing a WaitForMultipleObjects() on an array of 2 thread handles for the outer threads (order of thread termination would not be important).

Cray had a form of parallelism called autotasking, implemented at the compiler/library level. With it logical threads could be spawned, merged, and dismissed automagically.

The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads. On the CDC and Cray machines (and I assume many current processors), some out of order and parallel operations on registers were handled via register "scoreboarding", a hardware scheme which was used to indicate that a register was "waiting" for the output from some operation, suspending any operations wanting to use that register as input. I don't think there was any form of hardware "scoreboarding" for memory, so that required a software handshake (mutex, semaphore, ...).

Scoreboarding dates back to the CDC 6600 (1964) (about a year before the first IBM 360 was delivered):

http://en.wikipedia.org/wiki/Scoreboarding

 

[sandy.bridge]

Why exactly can't it be converted into pseudo-code then? I'm seeing the race condition and how the program can fail but I am not seeing how it cannot be converted into pseudo-code.
For example:

Do A1=0

Do A1=1

If A1==1
{

somethingClever​

}

 

[rcgldr]

Why exactly can't it be converted into pseudo-code then?

It can be converted into psuedo code, but you need a convention on how to describe parallel threads with pseudo code, and operators that can pend on actions (including spawning and termination) between threads.

 

[gneill]

You're running three threads at the same time.

Depends on how "flowchart" was defined. Normally you can't have multiple states at the same instance in a flowchart, so the control flow can only be at one point in the flow chart at any time. In this case the flow chart starts with 3 control flows, then ends up with one.

The flowchart would be valid if those arrows from the outer threads connecting to the inner thread represented termination of those outer threads, and that the inner thread was pending on completion of both outer threads (order not important, so you still have the race condition) before continuing.

In this case we can only assume the rules are as given, no more, no less. Whether they are complete, correct, sufficient, or permit the construction of illogical or flawed structures is not at issue. In fact, here we are trying to find just such a situation for the given rules. Also the underlying implementation of what the flowchart describes is not particularly relevant, even if we know how it's "really done" in real world implementations. By assuming the worst we can might be able to answer the question

The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads.

Yes, the results were merged, and to the user it appeared that nothing had happened except that the code ran faster. In actuality the threads ("microtasks") had come into existence previously and hung around in a sleep state waiting to be called into a fray. At the end of a given fray the results were merged via semaphore mechanisms and the tasks would depart, returning to a wait state ("spinwait"), and eventually to sleep if not promptly summoned for more work (yielding up the physical CPU for rescheduling by the OS), and await another summons to a fray. For microtasking and autotasking the underlying tasks weren't continually destroyed and recreated because the instantiation cost was too high (OS call, resource allocation, rescheduling). Much more efficient to do it once at the beginning of a program, or for a chunk where parallelism is going to be used, and have them ready to go either spin-waiting or at worst, waiting for the attaching of an available CPU.

But the implementation details are not what the user saw (or rather, what they weren't supposed to have to see...).

In the case of register access, register "scoreboarding" was used to indicate that a register was "waiting" for the output from some operation, suspending any operations wanting to use that register as input. I don't think there was any form of hardware "scoreboarding" for memory, so that required a software handshake (mutex, semaphore, ...).

No, no scoreboarding for memory, but there were shared registers and semaphore registers that could be used for managing memory based structures.

 

[sandy.bridge]

So essentially you have two threads running in synchronization, and then the third thread is evaluated after the first two are declared? Or are all three threads to be running in parallel and synchronized?

 

[rcgldr]

In this case we can only assume the rules are as given, no more, no less. Whether they are complete, correct, sufficient, or permit the construction of illogical or flawed structures is not at issue. In fact, here we are trying to find just such a situation for the given rules.

In that case, you could simply allow multiple threads to be running the same code with the same variables but out of sync and running at different speeds to create all sorts of problems. For example, take the pseudocode case

A: x = 0
B: x = 1
C: if(x == 1) then doclever

but with 3 separate threads running at the same time, thread 0 at A:, thread 1 at B:, and thread 2 at C:.

Normally a flow chart doesn't allow for the control point to be at multiple locations on the flow chart at the same time (due to the multiple threads). A flow chart normally represents the control flow for a single state machine, although it could be expanded to handle multiple threads, but there needs to be a reasonable convention for doing so.

However, the point is that you can bend the rules for pseudocode in the same way rules are bent for flowcharts to end up with the same issues.

Rcgldr: The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads.

For microtasking and autotasking the underlying tasks weren't continually destroyed and recreated because the instantiation cost was too high (OS call, resource allocation, rescheduling).

I only meant logically. The unused tasks would be in an idle / pending state when there was nothing for them to do. Also some of this out of order processing uses the equivalent of hardware multi-tasking that doesn't involve the OS, such as multiple arithemetic units on a single processor running at the same time, which the OS would be unaware of (the hardware would usually handle this with some form of scoreboarding).

 

[rcgldr]

So essentially you have two threads running in synchronization, and then the third thread is evaluated after the first two are declared? Or are all three threads to be running in parallel and synchronized?

You start with three threads running unsynchronized. The merging arrows would (or at least should) imply synchonization, with the middle thread waiting for both outer threads to terminate (or go idle as gneill pointed out), but in no specifc order (wouldn't matter which one terminated first). You could also invent other conventions for syncrhonization between threads.

Actually in a multi-threading environment, the ability to wait for multiple events with a single atomic call eliminates a lot of issues related to priority issues between the signaling and pending threads when the pending thread needs to wait for multiple events before continuing.

 

[sandy.bridge]

Is there a way to represent the "pending" of the middle thread to show that it is waiting for the side threads via flow chart? Or would I just have to have a brief explanation?

 

[rcgldr]

Is there a way to represent the "pending" of the middle thread to show that it is waiting for the side threads via flow chart? Or would I just have to have a brief explanation?

You could assume that it's implied by the merging arrows, but that would require a brief explanation. Otherwise, you need to create some convention for threads to signal or pend on events, in either your flowcharts or your pseudocode.

This still doesn't get back to the original problem, since there's no reason you can't "bend" the rules for pseudocode in the same manner as you do for flowcharts. I'm wondering what your professor's point is. Let us know when you find out.

 

[sandy.bridge]

Will do! Thanks for the help, guys.