views:

260

answers:

11

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.

+6  A: 

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

Asaph
A: 

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.

Atmocreations
+2  A: 

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.

Ralph Shillington
Why is dynamic code a worse choice than `goto`?
Sarah Vessels
Try writing it in c. Most compiled languages won't net you do this easily.
Byron Whitlock
@Sarah, for starters a goto can be understood by the debugger, but it's less likely the debugger is going to be able to show you the code that exists only inside a variable. The dynamic code isn't known to be correct until runtime. In some languages the context of the dynamic code is outside the calling environment, so the caller’s variables may be out of scope. And finally, some languages / runtime environments do not support dynamic code.But after all that even dynamic code has its place. For example the serialzers in .net generate and compile code on the fly for reuse.
Ralph Shillington
+1. It's often easier to read code with gotos than reading code that generates code without gotos. :)
Marcus Lindblom
+2  A: 

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.

Qua
Part of the assignment is to solve the problem again using recursion, instead of an iterative method.
Sarah Vessels
One of the fundemental proves within the subject of algorithms is that any problem that can be solved using recursion can likewise be solved using iteration and vice versa. Basically you either just unroll the recursion with a while loop or the other way around.
Qua
Well, maybe iteration + stack or iteration with IO can simulate recursion - otherwise no, since it would equivalent to a FSA (finite state automata) whereas recursion would be equivalent to PDA (push down automata) which can recognize any language generated by a context free grammar.
Larry Watanabe
If you're doubting the statement, go check out Church-Turing's thesis or read this thread right here at stackoverflow http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration/931874
Qua
re-read my answer and your reference. Your reference explicity states that a stack is required.
Larry Watanabe
Not only that, but the Church-turing thesis states that the set of computable functions by recursion is equivalent to the set of functions computable by a turing machine. However, a TM has a tape, and is definitely more powerful than the set of functions computable by FSA or PDA. Look at my answer again - I said that iteration would require either a stack (making it equivalent to PDA) or IO (making it equivalent to a TM).
Larry Watanabe
Actually, the Church-Turing thesis can't be used to prove anything anyways, since though widely accepted it has not actually been proven. This is something I did't realize before, although of course if it had been proven it would be called the Church-Turing Theorem.
Larry Watanabe
+2  A: 

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.

Matthew Vines
Thanks for actually answering my question about _why_ `goto` is preferable to `eval`.
Sarah Vessels
+1  A: 

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

Laurent Bourgault-Roy
Good answer .. this is basic recursive programming -- handle basis case first, then inductive step .. the advantage of recursive programs like ths is that they are actually quite easy to prove correct (often in your head) using a mathematical induction proof. I've posted an implementation of the recursive solution, and also
Larry Watanabe
+1  A: 

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!

Murph
I accepted this as the answer because you didn't try to persuade me to use recursion or tell me both `goto` and `eval` were terrible. You actually answered my question, which was to explain _why_ `goto` was preferable to `eval`.
Sarah Vessels
A: 

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.

Larry Watanabe
I considered that before and asked my professor; to him, generating all permutations and only selectively displaying the derangement permutations was a "poor quality" answer.
Sarah Vessels
Ok, i see that for all i, p[i] != i. But in this case, recursive generation with early pruning should be efficient (actually optimal within a constant factor) and simple.
Larry Watanabe
Ooops .. I just remembered that one of the few times a goto is useful is when simulating a recursive procedure with an iterative one :) I get now what your prof is getting at.
Larry Watanabe
+1  A: 

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...

Nick
A: 

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

Larry Watanabe
I should add that the simplest (and probably best) way is to simply simulate the recursive solution using a stack. This was a common trick in chess programs that use recursive search algorithms, back when that made a difference. If you've taken a compiler course then you know how to model function calls by pushing and saving local variables on a stack, and popping them off on return.
Larry Watanabe
By the above, I mean the simplest and best way to implement an iterative solution. I would never bother eliminating the recursion in any program except for exceptional cases like chess programs where you are competing against others based on time.
Larry Watanabe
I've posted the non-recursive solution that simulates recursive calls with a stack and goto labels, elsewhere in this thread.
Larry Watanabe
+1  A: 

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

Larry Watanabe