goto

This article is about the programming statement. For other uses, see Goto (disambiguation).

goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control. The jumped-to locations are usually identified using labels, though some languages use line numbers. At the machine code level, a goto is a form of branch or jump statement.

Many languages support the goto statement, and many do not. In Java, goto is a reserved word, but is unusable.^[1][2]

The structured program theorem proves that the availability of the goto statement is not necessary to write programs; some combination of the three programming constructs of sequence, selection/choice, and repetition/iteration are sufficient to perform any computation.

Usage

   goto label

The goto statement is often combined with the if statement to cause a conditional transfer of control.

   IF condition THEN goto label

Programming languages impose different restrictions with respect to the destination of a goto statement. For example, the C programming language does not permit a jump to a label contained within another function.^[3] The setjmp/longjmp functions provide support for non-local gotos.

Criticism and decline

The 1960s and 1970s saw computer scientists move away from GOTO statements in favor of the "structured programming" paradigm. Some^[which?] programming style coding standards prohibit use of GOTO statements, particularly in view of the aforementioned structured program theorem. The Böhm-Jacopini proof did not settle the question of whether to adopt structured programming for software development, partly because the construction was more likely to obscure a program than to improve it. It has, however, sparked a prominent debate among computer scientists, educators, language designers and application programmers that saw a slow but steady shift away from the formerly ubiquitous use of the GOTO. Probably the most famous criticism of GOTO is a 1968 letter by Edsger Dijkstra called Go To Statement Considered Harmful.^[4] In that letter Dijkstra argued that unrestricted GOTO statements should be abolished from higher-level languages because they complicated the task of analyzing and verifying the correctness of programs (particularly those involving loops). An alternative viewpoint is presented in Donald Knuth's Structured Programming with go to Statements^[5] which analyzes many common programming tasks and finds that in some of them GOTO is the optimal language construct to use. Some programmers, such as Linux Kernel designer and coder Linus Torvalds or software engineer and book author Steve McConnell also object to Dijkstra's point of view, stating that GOTOs can be a useful language feature, improving program speed, size and code clearness, but only when used in a sensible way by a comparably sensible programmer.^[6][7]

The viewpoint that use of GOTO is sometimes undesirable is evident in the design of some programming languages, for instance Ada^[8] visually emphasizes label definitions using angle brackets.

Fortran introduced structured programming constructs in 1978 and in successive revisions the relatively loose semantic rules governing the allowable use of goto were tightened; the "extended range" in which a programmer could use a GOTO to enter and leave a still-executing DO loop was removed from the language in 1978,^[9] and by 1995 several of forms of Fortran GOTO, including the Computed GOTO and the Assigned GOTO, had been deleted from the language.^[10] Some widely used modern programming languages, such as Java and Python lack the GOTO statement, though most provide some means of breaking out of a selection, or either breaking out of or moving on to the next step of an iteration.

Alternatives

Structured programming

In classical structured programming, three basic structures are used: sequence, repetition, and selection. Sequence is the execution of one program unit following another; repetition is the repeated execution of the same program unit until a desired program state is reached; and selection is the executing of one and only one of a fixed set of possible alternative program units depending on the program state. Here typically the "program unit" is a compound statement constructed in turn using the three basic structures.

Although these three control structures can all be hand-coded using gotos and ifs, the desire for clarity and efficient optimization led to the introduction and refinement of supporting structures such as (in Pascal) procedure and function blocks, while, repeat until, and for statements, and case statements (multiway branching - a form of multiple goto that is apparently more accepted than a single variety).

In practice the need arose to refine this basic three-structure template, because the attempt to eliminate exceptional changes of control altogether generated a need for quite complex program state data, and language design had to adapt in order to reduce the combinatorial explosion. Typically the language designers provided a way to exit a structured unit prematurely (in C, break and continue). For handling exceptional situations, specialized exception handling constructs were added, such as try/catch/finally in Java.

Tail calls

Main article: Tail call

In a paper delivered to the ACM conference in Seattle in 1977, Guy L. Steele summarized the debate over the GOTO and structured programming, and observed that procedure calls in the tail position of a procedure can be most optimally treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations.^[11] Since such "tail calls" are very common in Lisp, a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to the GOTO used in other languages. Steele argued that poorly implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that "in general procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions", with the machine code stack manipulation instructions "considered an optimization (rather than vice versa!)".^[11] Steele cited evidence that well optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In Scheme, a Lisp dialect developed by Steele with Gerald Jay Sussman, tail call optimization is mandatory.^[12]

Although Steele's paper did not introduce much that was new to computer science, at least as it was practised at MIT, it brought to light the scope for procedure call optimization, which made the modularity-promoting qualities of procedures into a more credible alternative to the then-common coding habits of large monolithic procedures with complex internal control structures and extensive state data. In particular, the tail call optimizations discussed by Steele turned the procedure into a credible way of implementing iteration through tail recursion.

Object oriented programming

The influential languages Simula and Smalltalk were among the first to introduce the concepts of messages and objects. By encapsulating state data, object-oriented programming reduced software complexity to interactions (messages) between objects.

Variations

There are a number of different language constructs under the class of goto statements.

Computed GOTO

A computed GOTO (originally Fortran terminology) jumps to one of several labels based on the value of an expression. The ON ... GOTO statement in BASIC supports the computed GOTO and is useful for case-by-case branching, as in C's switch statement.^[13] Some variants of BASIC support a computed GOTO that can be any line number, not just one from a list. For example, one could write GOTO i*1000 to jump to the line numbered 1000 times the value of a variable i (which might represent a selected menu option, for example).

Assigned GOTO

Originally found in Fortran, this variant transfers control to a statement label which is stored in (assigned to) a variable.

Some C compilers (e.g., gcc) support goto with a label variable using the label value operator. The label value operator && returns the address of its operand, which must be a label defined in the current function or a containing function. The value is a constant of type void * and should be used only in a computed goto statement. The feature is an extension to C and C++, implemented to facilitate porting programs developed with GNU C.^[14] This C extension is sometimes referred to as a Computed goto, but it has the semantics of an assigned goto.

ALTER

The 1985 ANSI COBOL standard had the ALTER verb which could be used to change the destination of an existing GO TO, which had to be in a paragraph by itself.^[15] The feature, which allowed polymorphism, was frequently condemned and seldom used.^[16]

Continuations

A continuation is similar to a GOTO in that it transfers control from an arbitrary point in the program to a previously marked point. A continuation is more flexible than GOTO in those languages that support it, because it can transfer control out of the current function, something that a GOTO cannot do in most structured programming languages. In those language implementations that maintain stack frames for storage of local variables and function arguments, executing a continuation involves adjusting the program's call stack in addition to a jump. The longjmp function of the C programming language is an example of an escape continuation that may be used to escape the current context to a surrounding one. The Common Lisp GO operator also has this stack unwinding property, despite the construct being lexically scoped, as the label to be jumped to can be referenced from a closure.

In Scheme, continuations can even move control from an outer context to an inner one if desired. This almost limitless control over what code is executed next makes complex control structures such as coroutines and cooperative multitasking relatively easy to write.^[17]

Perl GOTO

In Perl, there is a variant of the goto statement that is not a traditional GOTO statement at all. It takes a function name and transfers control by effectively substituting one function call for another (a tail call): the new function will not return to the GOTO, but instead to the place from which the original function was called.^[18]

See also

• COMEFROM
• Control flow
• GOSUB
• Switch statement - a multiway branch (or conditional goto)
• Unstructured programming
• Considered harmful

References

1. ^ "The Java Language Specification, Third Edition". http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.9. "The keywords const and goto are reserved, even though they are not currently used. This may allow a Java compiler to produce better error messages if these C++ keywords incorrectly appear in programs." 
2. ^ "The Java Language Specification, Third Edition". http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.7. "Unlike C and C++, the Java programming language has no goto statement; identifier statement labels are used with break (§14.15) or continue (§14.16) statements appearing anywhere within the labeled statement." 
3. ^ C Standard section 6.8.6.1 The goto statement
4. ^ Edsger Dijkstra (March 1968). "Go To Statement Considered Harmful". Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. http://portal.acm.org/citation.cfm?id=1241518&coll=ACM&dl=ACM&CFID=11218690&CFTOKEN=24551268. 
5. ^ Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys 6 (4): 261–301. doi:10.1145/356635.356640. http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf. 
6. ^ http://kerneltrap.org/node/553
7. ^ http://www.stevemcconnell.com/ccgoto.htm
8. ^ John Barnes (2006-06-30). Programming in Ada 2005. Addison Wesley. p. 114–115. ISBN 0-32-134078-7. 
9. ^ ANSI X3.9-1978. American National Standard – Programming Language FORTRAN. American National Standards Institute. Also known as ISO 1539-1980, informally known as FORTRAN 77
10. ^ ISO/IEC 1539-1:1997. Information technology – Programming languages – Fortran – Part 1: Base language. Informally known as Fortran 95. There are a further two parts to this standard. Part 1 has been formally adopted by ANSI.
11. ^ ^{a b} Guy Lewis Steele, Jr.. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.
12. ^ R5RS Sec. 3.5, Richard Kelsey, William Clinger, Jonathan Rees et al. (August 1998). "Revised⁵ Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation 11 (1): 7–105. doi:10.1023/A:1010051815785. http://www.schemers.org/Documents/Standards/R5RS/. 
13. ^ "Microsoft QuickBASIC: ON...GOSUB, ON...GOTO Statements QuickSCREEN.". Microsoft. 1988. http://www.qbasicnews.com/qboho/[e-mail]. Retrieved 2008-07-03. 
14. ^ Computed goto, IBM XL C/C++ compiler
15. ^ HP COBOL II/XL Reference Manual, "The ALTER statement is an obsolete feature of the 1985 ANSI COBOL standard."
16. ^ Van Tassel, Dennie (July 8, 2004.). "History of Labels in Programming Languages". http://www.gavilan.edu/csis/languages/labels.html#_Toc76036283. Retrieved 4 January 2011. 
17. ^ Revised⁵ Report on the Algorithmic Language Scheme (R5RS), section 6.4, standard procedures: call-with-current-continuation
18. ^ Goto, from the perl.syn (Perl syntax) manual