Do Not Pass Go

When I was in middle school, I found a bunch of books at my local library that explained how to create games for the Atari console in BASIC.  This was my first introduction to coding.

BASIC is a great first language to learn to the extent that, as its name implies, it is an extremely basic programming language and is easy to understand (as you'll be able to tell after reading this post, it is not a good way to learn how to program in general, at least if your goal is to use modern programming languages). BASIC is also based off of FORTRAN II, which is of course based off of FORTRAN, which is the language that invented the GOTO statement.

The GOTO statement takes its inspiration from the most fundamental of computers, the Turing machine.  Turing machines are an abstraction in which a head reads and writes ones and zeros from an infinite tape of individual cells. The head moves back and forth along the tape based off of a finite list of instructions and what those instructions say to do based on what the cells the head reads contain.  GOTO mimics these "conditional jump instructions" by sending the computer off to another section of code.  Here's an example of a program that prints "HELLO WORLD" five times using GOTO:

10 LET C=0
20 PRINT C
30 C = C + 1
40 IF C<5 THEN GOTO 20

After learning how to code an Atari, my next coding languages were Liberty BASIC and TI-BASIC, which meant that my earliest coding journeys relied quite heavily on GOTO statements.  I was thus in for a rude awakening when I learned to code in Ruby and discovered that, not only were GOTO statements not used any more, literally 4 years after the creation of BASIC they were deemed harmful, a decree which has become only more popular with time.

For a beginner like me, GOTO seemed straightforward and easy - the way to figure out what a program does is simply to read it, line by line, and follow along with the calculations and outputs it creates.  GOTO statements are fairly easy to follow - they just shuttle you off to another segment of code where you continue following along.  Why is something so simple considered bad?

The main reason (and one that wouldn't occur to a beginner writing simple programs) is that GOTO can create complicated and unmaintainable spaghetti code.  Creating a little for-loop out of GOTO statements is easy enough to follow, but when your GOTOs are based off of conditions that could have different results every time you run a program, then your GOTOs end up creating a complicated flowchart of different possible paths the program can run through, and the more GOTOs, the more complicated the flowchart gets, until any normal person can't follow it anymore.

To be fair, most reasonably complex programs, even those without GOTO statements, would also create fairly complicated flowcharts if you analyzed all the possible inputs.  What makes GOTO statements bad is that, because they sometimes send you off to completely different sections of code, they effectively hide what code does.

Still, for someone like me, there's a nostalgia and even a simplicity to GOTO statements - sometimes it's mentally easier to just send your program away when you hit upon a special condition than to figure out how to keep a program going in a way that makes sense for both the special condition and the normal condition.  Take for example this code, which returns all the prime numbers less than some number n:

let array = [2]
for (let i=3; i < n; i +=2) {
let prime =true

for (let j=1; j < array.length; j++) {
if (i % array[j] === 0) {
prime = false
}
}

if (prime) {
array.push(i)
}
}

return array

How this works is, starting with the number 3 and testing all odd numbers after that, we assume the number is prime and then divide it by all the prime numbers before.  If one of them divides evenly, we know the number is not prime.

This program has some problems, the main one being that it's slow - if n is 10, it runs reasonably fast for what it does since all odd numbers less than 10 except 9 are prime.  But for that 9, even though we know it's not prime after our first division (9/3 === 0) we still test 9/5 and 9/7.  Two extra tests don't matter that much, but if we were calculating all primes less than 100,000 it's a serious drag to run thousands of tests when 91,377/3 === 0 gives us the answer we need, to name one badly-behaving number out of a myriad.

For reasons like this, the GOTO statement has lived on through its badly malnourished cousins like break.  Take a look at this optimization of the code above:


let array = [2]
for (let i=3; i < n; i +=2) {
let prime =true

for (let j=1; j < array.length; j++) {
if (i % array[j] === 0) {
prime = false
break
}
if (array[j] ** 2 > i) {
break
}
}
if (prime) {
array.push(i)
}
}

Here we are rescued from our unnecessary computations by break-ing out of our for loop whenever we discover our number j is not, in fact, a prime number.  This seems simple enough.

But what if, when we encounter our break condition inside a loop, we need to break out of not only the loop we're in, but the outer loop as well?  Let's take this contrived example below* for instance. In the code below, we have two arrays, arr1 and arr2.  We loop through arr1, looking for any instance of the string "foo" and when we find it we start at the same index in arr2 and look through the next 3 indices for "bar".  If we find it, we break out of our inner loop, and then we've got a conditional that allows us to break out again so that we can run into our foobar detection reaction print statements without spending any unnecessary time pouring through arr1 and arr2.


let someSubsetOfArray2ContainsBar = false

for (let i=0; i < arr1.length; i++) {
if (arr1[i] === "foo") {
for (let j=i; j <= i+3; j++) {
if (arr2[j] === "bar") {
someSubsetOfArray2ContainsBar = true
break
}
}
}
if (someSubsetOfArray2ContainsBar) {
break
}
}

if (someSubsetOfArray2ContainsBar) {
return "Woo hoo!"
} else {
return "Oh no!"
}

Not only is writing two breaks annoying and visually cluttering, it also impacts performance - we have to check our someSubsetOfArray2ContainsBar variable for every single element of arr1 when all we really want to do is just get us out of our checks once we've found "bar" in arr2.

Wouldn't something like this be nicer?


for (let i=0; i < arr1.length; i++) {
if (arr1[i] === "foo") {
for (let j=i; j <= i+3; j++) {
if (arr2[j] === "bar") {
goto A1
}
}
}
}

return ("Oh no!")

A1
return "Woo hoo!"

Isn't that nicer?  Most of you are probably saying, "Well, in this extremely contrived example, yes it does make the code shorter and simpler, but real life isn't like that and you're making a mountain out of a molehill.  What's more, you could just write a function to do the same work:"


function weFoundFooBar() {
return "Woo hoo!"
}

for (let i=0; i < arr1.length; i++) {
if (arr1[i] === "foo") {
for (let j=i; j <= i+3; j++) {
if (arr2[j] === "bar") {
return weFoundFooBar()
}
}
}
}

return "Oh no!"

To which I have to say, sure, GOTO itself is not necessary, and the example above even gets rid of our A1 label.  But while we've removed the syntax, we've kept the essential problem with GOTO - we've made spaghetti code that sends our programmer running all over the codebase trying to find what happens once we hit a certain condition instead of giving them a straightforward piece of code that you read from top to bottom.

My extremely uppity take on all of this is that the crusade against GOTO is, at its heart, simply an aesthetic preference that got justified by an unfortunate association with badly-written code, and that many of the worst examples of GOTO usage are not, in fact, problems with GOTO, but actually a reflection of that fact that programming is complicated and people can't naturally keep track of huge decision trees.

I'll leave with a brief, sad look at another impoverished child of GOTO - exit exception handling, which is actually considered by some to be an example of one of the good uses for GOTO.  The focus on object-oriented programming and lack of GOTO support in languages like Ruby** has led to things like exit hooks, which have inevitably ended up generating absurd Stack Overflow questions like "Can I stop Sinatra from within a Sinatra application?"

*Let the reader please forgive me for how contrived this example is; this situation is something I feel like happens a lot in my code but since I've had to come up with creative solutions to avoid it I'm having a hard time thinking of a good example I've used before.

**Not actually true, but... we have purposely trained him wrong as a joke.

Comments

Post a Comment

Popular posts from this blog

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...
Read more

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...
Read more