Welcome, guest | Sign In | My Account | Store | Cart

A function-decorator that provides the goto command.

Python, 103 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
import dis
import new

class MissingLabelError(Exception):
    """'goto' without matching 'label'."""
    pass


def goto(fn):
    """
    A function decorator to add the goto command for a function.

    Specify labels like so:

    label .foo
    
    Goto labels like so:

    goto .foo
    """
    labels = {}
    gotos = {}
    globalName = None
    index = 0
    end = len(fn.func_code.co_code)
    i = 0

    # scan through the byte codes to find the labels and gotos
    while i < end:
        op = ord(fn.func_code.co_code[i])
        i += 1
        name = dis.opname[op]

        if op > dis.HAVE_ARGUMENT:
            b1 = ord(fn.func_code.co_code[i])
            b2 = ord(fn.func_code.co_code[i+1])
            num = b2 * 256 + b1
            
            if name == 'LOAD_GLOBAL':
                globalName = fn.func_code.co_names[num]
                index = i - 1
                i += 2
                continue
                
            if name == 'LOAD_ATTR':
                if globalName == 'label':
                    labels[fn.func_code.co_names[num]] = index
                elif globalName == 'goto':
                    gotos[fn.func_code.co_names[num]] = index
                    
            name = None
            i += 2

    # no-op the labels
    ilist = list(fn.func_code.co_code)
    for label,index in labels.items():
        ilist[index:index+7] = [chr(dis.opmap['NOP'])]*7

    # change gotos to jumps
    for label,index in gotos.items():
        if label not in labels:
            raise MissingLabelError("Missing label: %s"%label)
        
        target = labels[label] + 7   # skip NOPs
        ilist[index] = chr(dis.opmap['JUMP_ABSOLUTE'])
        ilist[index + 1] = chr(target & 255)
        ilist[index + 2] = chr(target >> 8)

    # create new function from existing function
    c = fn.func_code
    newcode = new.code(c.co_argcount,
                       c.co_nlocals,
                       c.co_stacksize,
                       c.co_flags,
                       ''.join(ilist),
                       c.co_consts,
                       c.co_names,
                       c.co_varnames,
                       c.co_filename,
                       c.co_name,
                       c.co_firstlineno,
                       c.co_lnotab)
    newfn = new.function(newcode,fn.func_globals)
    return newfn


if __name__ == '__main__':
    
    @goto
    def test1(n):

        s = 0

        label .myLoop

        if n <= 0:
            return s
        s += n
        n -= 1

        goto .myLoop

    assert(test1(10) == 55)

This is the recipe for you if you are sick of the slow speed of the existing goto module http://entrian.com/goto/. The goto in this recipe is about 60x faster and is also cleaner (abusing sys.settrace seems hardly pythonic). Because this is a decorator, it alerts the reader which functions use goto. It does not implement the comefrom command, although it is not difficult to extend it to do so (exercise for the reader). Also, computed gotos aren't supported; they're not pythonic.

  • Use dis.dis(fn) to show the bytecode disassembly of a function.
  • The bytecodes of a function are accessed by fn.func_code.co_code. This is readonly so:
  • The decorated function is created exactly the same as the old one, but with the bytecode updated to obey the goto commands.
  • This is 2.x only; the new module is not in python 3.x (another exercise for the reader!)

6 comments

Gabriel Genellina 14 years, 4 months ago  # | flag

How bizarre! And you're even concerned about speed! :)

Valentine Gogichashvili 14 years, 4 months ago  # | flag

I wonder, why you need goto operator at all?

I can imagine making 'break' and 'continue' operator for loops be aware of the labels, but for the God's sake, when do you use the goto?

Thank you for a nice example of adding new operators to the code :)

Paul W. Miller 14 years, 4 months ago  # | flag

+1 for hack value.

Carl Cerecke (author) 14 years, 4 months ago  # | flag

Valentine Gogichashvili said "I wonder, why you need goto operator at all?"

There is one use case that I can think of where having a fast goto is valuable: finite state machines. If you have a FSM that you want to run fast (perhaps a shift-reduce parser), then gotos will allow you to avoid the overhead of a function-call/dispatch method.

Alfe 11 years, 6 months ago  # | flag

Goto can be useful in a small number of cases. Its abuse (in cases outside of this small list) is responsible for the widely assumed harmfulness of goto.

Most cases of using goto without abuse involve patching existing code to get a new feature which otherwise would force the developer to restructure the existing code; for instance I assume goto a valid use to jump into and out of nested loops. Jumping out makes sense in case you found the result of a computation, jumping in makes sense in case you once interrupted a long computation and later want to continue it. (Again: By restructuring the existing code by using a complex iterator instead of nested loop or refactoring the nested loops in a function and using return to jump out of it you can solve this task as well; goto is an option in case you want to avoid the restructuring.)

Unfortunately, this goto (as well as the other I know) cannot jump into a nested loop and thus lacks usefulness. In fact, trying so made the python interpreter segfault:

from goto import *

@goto
def g():
  a, b, c = 2, 3, 1
  goto .innerLoop
  while a  > 0:
    b = 4 
    while b > 0:
      c = 4
      while c > 0:
        label .innerLoop
        print a, b, c
        c -= 1
      b -= 1
    a -= 1 

g()
2 3 1
Fatal Python error: XXX block stack underflow
Aborted (core dumped)
Alfe 11 years, 6 months ago  # | flag

Okay, it worked when the goto was done from the same nesting depth as the label; but this is new feasible ;-) Maybe the goto could be enhanced to do this itself?

from goto import *

@goto
def g(a=None, b=None, c=None):
  if a is not None:  # continuing old run?
    while True:  # one ...
      while True:  # ... two ...
        while True:  # ... three fake levels of nesting for the goto
          goto .innerLoop
  # no, starting new run:
  a = 4
  while a > 0:
    b = 4
    while b > 0:
      c = 4
      while c > 0:
        label .innerLoop
        print a, b, c
        c -= 1
      b -= 1
    a -= 1

g(1,2,3)
1 2 3
1 2 2
1 2 1
1 1 4
1 1 3
1 1 2
1 1 1

(Btw: the decorator @goto breaks the fact that the argument were optional by having a default value None, but that's just a minor flaw.)

Created by Carl Cerecke on Tue, 3 Nov 2009 (MIT)
Python recipes (4591)
Carl Cerecke's recipes (1)

Required Modules

Other Information and Tasks