use of goto versus runtime code evaluation

Question

Recently for a programming class, we were given the assignment to write a program in any language that, given n, will produce all the possible derangements for an array p of size n such that p[i] != i for all i: 0 <= i < n. We had to use iterators, e.g. yield.

Example: n=3, [0, 1, 2] is not a derangement, but [2, 0, 1] is as well as [1, 2, 0].

I came up with a pseudocode solution that would work, but the problem was that it required power loops (that is, n nested loops where n is only known at runtime). To do this, I generated n nested loops in Ruby code in a string, then eval-ed the string. My solution worked, however my professor thought that using a few gotos would have been better solution (easier to read, at least) than dynamic code generation.

I was under the impression that goto was always a bad choice. Why might runtime evaluation of dynamically generated code be a worse choice than goto? The generated code is clean and simple, and seems fairly efficient for the given problem. The only user input upon which the code generation depends is n, which is checked to ensure it's an integer value beforehand. It yields only unique derangements, as it should.

I'm not asking for a solution to my programming assignment, I just want to know reasons behind the use of goto over dynamic code evaluation, or vice versa.

Edit: to clarify, the assignment included writing a program using iterators and another using recursion, so the iterative version wasn't necessarily meant to be efficient.

Answer 1

That's a really interesting question - I'm not sure that there's a definitive answer.

The problem with goto is its use in an unstructured fashion - a goto is a "massive random leap" so in the general instance, after the jump, you don't know where you came from which causes all kinds of issues both in terms of debugging and maintainability and - in a more formal sense with proving "correctness" of the code. Of course there are languages (I've been around a while) where you don't have an option at which point you impose structure on the code. The bottom line is that its not that GOTO is bad so much as the way that goto is used (and abused) that is bad and that makes its a dangerous construct to have available.

Using code generation and then evaluating the result is clever :) However "clever" is not always a good thing and I suspect that in part the issue with using that as a solution is that its not actually addressing the problem as intended. That may be "cheating" in a sense - at least so far as your professor is concerned - doesn't invalidate your solution but may render it "inelegant". The debugging and maintainance issues also arise in respect of the code.

A recursive solution - especially as I vaguely remember being taught (some 25 years ago) that one can usually unwind recursion into loops - would probably be the most elegant.

Definitely an interesting question!

Answer 2

Both GOTO and code generation are inelegant solutions to this problem IMO. There is a recursive algorithm that is probably the right answer here.

Answer 3

Without seeing your code, I would tend to side with the prof. If it's a choice between GoTo and dynamic code, I would lean towards the former. GoTo are not always a bad choice.

Answer 4

You can solve almost all problems without the use of GoTos. Specifically with loops you can use the break and continue statements to implitly use gotos while code standard are still maintained.

n nested loops sound like a bad plan, and I suggest that you instead look into a recursive functions. Every single time you need to do a n-loops you should always be thinking recursion.

Answer 5

Dynamic code is not compile time checkable, which means any errors will go undetected until run time. Potentially making them harder to find. For ruby, this would mean that syntax errors would not be found by the IDE or editor, whichever you happen to be using. That is a plus for choosing goto.

I think I would have to see both to make a decision in this case. I haven't seen the code, but I'm willing to bet there is a good solution that doesn't use dynamic code, or goto's. goto is not always bad, but if you are thinking of using it you probably have not made the best design decisions up to this point and probably want to revisit your solution.

Answer 6

In one of my assignement in college, I once had to do something that was relatively similar My solution was to use a recursive function, passing the array, the size of the array and the nesting level as argument. The function then call itself with nesting level +1, until the nesting level is equal to the size of the array. No Goto, no code evaluation, only clean code!

Example

function computeDerangement(yourArray, loopLevel, arraySize)
{
    //We check to see if the loop level is the same as the array size
    //if true, then we have executed exactly n loop
    if (loopLevel == arraySize) {
         display(yourArray); //Display being some kind of function that show the array,
                             //you get the idea
    } else {
        while(something) {
            //Here you put the logic that you execute at one level of the loop

            //Then you call yourself with one more level of nesting
            computeDerangement(yourArray, loopLevel + 1, arraySize);
        }
    }
}

Hope that help!

I have never used goto in my life, so I'm pretty sure there is always a way to avoid them

Answer 7

The main reason people avoid goto statements is that they can make your program more difficult to understand.

Without having seen your code, I'd guess it's more difficult to understand than the equivalent program using goto...

Answer 8

GOTO Solution -- a goto is convenient when simulating a function call. Here's a non-recurisve solution that simply simulates the recursive solution using a stack and a goto label to return to the point where the function call would have occurred.

See the recursive procedure (I have posted this as a separate answer) for comparison.

Option Strict On Option Explicit On

Module Module1 Dim x As Stack

Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
    For Each el In generatedList
        Console.Write(el & " ")
    Next
    Console.WriteLine()
End Sub
Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
                        ByVal generatedList As List(Of Integer))
    Dim stackI As Stack(Of Integer) = New Stack(Of Integer)
    Dim stackJ As Stack(Of Integer) = New Stack(Of Integer)


    Dim j As Integer

StartLabel:

    j = 0

    If i >= n Then
        printGeneratedList(generatedList)
        If stackI.Count = 0 Then
            Return
        Else
            GoTo ReturnLabel
        End If
    End If

     While j < n
        If Not j = i Then
            If Not generatedList.Contains(j) Then
                generatedList.Add(j)
                stackI.Push(i)
                stackJ.Push(j)
                i = i + 1
                GoTo StartLabel

ReturnLabel:

                i = stackI.Pop()
                j = stackJ.Pop()
                generatedList.Remove(j)
            End If
        End If
        j = j + 1
    End While
    If stackI.Count = 0 Then
        Return
    Else
        GoTo ReturnLabel
    End If
End Sub

Private Sub generate(ByVal n As Integer)
    Console.WriteLine("Generating for n = " & n.ToString())
    Dim l As List(Of Integer) = New List(Of Integer)
    If n < 0 Then
        Throw New Exception("n must be >= 0")
    End If
    generateAux(0, n, l)
End Sub

Sub Main()
    generate(0)
    Console.ReadLine()
    generate(1)
    Console.ReadLine()
    generate(2)
    Console.ReadLine()
    generate(3)
    Console.ReadLine()
    generate(4)
    Console.ReadLine()
End Sub

End Module

Answer 9

goto's are not clean. but if high performance is required, you need to break some of those coding rules sometimes...

if speed is really an important matter, for example if you want to write a library or code you have big exigeance on, you might consider using goto. for sure you have to pay attention that everything goes well.

Comment: At the end, the executing CPU does nothing else than simple jumps. Just only that the programming language / the compiler creates them. use with caution and don't mess with it.

Answer 10

Both the goto solution and dynamic code generation ideas are bad. This is easily solved with a recursive solution as mentioned by others. You simply recursively generate all permutations (standard recursive solution) and when generation is complete (ie at the leaf of the recursion) simply skip returning permutations that are not derangements.

Answer 11

Recursive solution -- here's a solution with early pruning. My only question is regarding enumerations: did he want you to create an enumerator that on each successful call would generate the next item in the list? This would probably be easiest implemented by creating a lambda version of this program - I used to do this in lisp all the time when writing query generators that would generate the next answer to a question when doing prolog-interpreter style queries.

Option Strict On Option Explicit On

Module Module1

Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
    For Each el In generatedList
        Console.Write(el & " ")
    Next
    Console.WriteLine()
End Sub

Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
                    ByVal generatedList As List(Of Integer))
    If i >= n Then
        printGeneratedList(generatedList)
        Return
    End If
    For j As Integer = 0 To n - 1
        If Not j = i Then
            If Not generatedList.Contains(j) Then
                generatedList.Add(j)
                generateAux(i + 1, n, generatedList)
                generatedList.Remove(j)
            End If
        End If
    Next
End Sub

Private Sub generate(ByVal n As Integer)
    Console.WriteLine("Generating for n = " & n.ToString())
    Dim l As List(Of Integer) = New List(Of Integer)
    If n < 0 Then
        Throw New Exception("n must be >= 0")
    End If
    generateAux(0, n, l)
End Sub

Sub Main()
     generate(0)

    Console.ReadLine()
    generate(1)

    Console.ReadLine()
    generate(2)

    Console.ReadLine()
    generate(3)

    Console.ReadLine()
    generate(4)

    Console.ReadLine()

End Sub

End Module