Goto Considered Hilarious

# Goto Considered Hilarious ## What is `goto`? `goto` is a statement in C that provides an unconditional jump to another point in the code, marked by a label. It can be useful for breaking out of deeply nested loops or handling certain error conditions. However, `goto` is generally discouraged because it can lead to "spaghetti code," making programs difficult to understand and maintain. # Fortran Example ```neovim {"update":true,"path":"_/code/17262475273874.fortran","timestamp":1727713705081} <pre> PROGRAM GOTO_EXAMPLE INTEGER I I = 0 5 I = I + 1 PRINT *, 'I = ', I IF (I .LT. 5) THEN GOTO 5 END IF PRINT *, 'Loop ended.' END </pre> ``` ^17262475273874 ```neovim {"update":true,"path":"_/code/17262475273863.","timestamp":1726247565428} <pre> I = 1 I = 2 I = 3 I = 4 I = 5 Loop ended. </pre> ``` ^17262475273863 ### Simple Examples **1. Breaking out of nested loops:** ```neovim {"update":true,"path":"_/code/17262475273852.c","timestamp":1726247565175} <pre> #include <stdio.h> int main() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == 1 && j == 1) { goto end; } printf("i = %d, j = %d\n", i, j); } } end: printf("Exited loops.\n"); return 0; } </pre> ``` ^17262475273852 **2. Handling errors:** ```neovim {"update":true,"path":"_/code/17262475273831.c","timestamp":1726247564924} <pre> #include <stdio.h> int main() { int x = 10; if (x < 0) { goto error; } printf("Value is positive.\n"); return 0; error: printf("Error: Value is negative.\n"); return 1; } </pre> ``` ^17262475273831 **3. Simplifying cleanup tasks:** ```neovim {"update":true,"path":"_/code/17262475273730.c","timestamp":1726247564665} <pre> #include <stdio.h> #include <stdlib.h> int main() { FILE *file = fopen("example.txt", "r"); if (file == NULL) { goto cleanup; } // Use the file // ... cleanup: if (file) { fclose(file); } printf("Cleanup done.\n"); return 0; } </pre> ``` ^17262475273730 These examples show basic use cases for `goto`, but use it with caution. Avoid `goto` unless it's the simplest, clearest solution. # Goto Considered Harmful The "Goto Considered Harmful" paper, written by Edsger W. Dijkstra in 1968, makes the (now obvious) case that `goto` is very bad and confusing. You can go read his much smarter analysis if you're interested. The primary takeaway is Dijkstra recommends structured programming: which is where control structures like loops and conditionals replace arbitrary jumps in code. So obviously, I thought "Let's bring `goto` to OCaml" Actually, what really inspired me to try this was watching Tsoding's Video [here](https://www.youtube.com/watch?v=iPrltr1b6Q4). The summary is that you could use string "labels" to denote where you wanted to jump to next, and then `Exceptions` to change control-flow. ```neovim {"update":true,"path":"_/code/17262481951480.ml","timestamp":1726248198842} <pre> let goto_block _ = (* ... redacted ... *) assert false let () = let i = ref 0 in goto_block [("loop", (fun () -> if !i >= 10 then goto "out" else (); printf "%d: Hello, World\n" !i; i := !i + 1; goto "loop")); ("out", (fun () -> printf "Done!\n"))] </pre> ``` ^17262481951480 At the end of his video, he mentions that if you can think of a better (or worse) way to implement this, then to go ahead and leave a comment. Consider this my comment haha! # My Implementation There were a couple things I wanted to solve compared to Tsoding's example: 1. You could type any string you wanted into the `goto` function, which even C is going to complain when you try to jump to a label that doesn't exist. If we're going to implement a proper CompSoy solution, we **cannot** be one-upped by the C compiler. This would lead to a runtime error, which we don't want. 2. There's no way to exit from the loop early. Although OCaml is still a CompSoy language, I wanted to give the Sigma Developer a way to exit from the loop early with an early return! In C, you can do this by just using `return` (which is itself a certain kind of goto, think about it). 3. It just wasn't cursed enough - could we introduce something that even C programmers wouldn't dream of. More on that at the end of the post ;) To begin with, we will continue to use Exceptions to manage our control flow. The simplified flow looks like this, where we create a recursive function `handle` that "resumes" execution when we raise a new `Goto` exception. ```neovim {"update":true,"path":"_/code/17262517982491.ml","timestamp":1726251798294} <pre> let rec handle label ... = match (implementation) with | () -> (* do something when no exceptions raised *) | exception Goto label -> (* Call back into `handle` to "resume" control flow *) handle label </pre> ``` If we consider the loop example: ```neovim {"update":true,"path":"_/code/17262490742530.ml","timestamp":1726249078316} <pre> type t = | Loop | Done </pre> ``` ^17262490742530 We could imagine pattern matching over the labels with something like: ```neovim {"update":true,"path":"_/code/17262491949470.ml","timestamp":1726249194956} <pre> match labels with | Loop -> (* ... some code here ... *) | Done -> (* ... other code here ... *) </pre> ``` starts to look a lot like: ```neovim {"update":true,"path":"_/code/17262492297860.c","timestamp":1726249229793} <pre> int main() { loop: // some code here ... done: // other code here ... } </pre> ``` and now we could directly use the labels as names in our `goto` function, which means we would get compiler errors if it isn't a valid. Take the following example: ```neovim {"update":true,"path":"_/code/17262497198330.ml","timestamp":1726249725936} <pre> type t = | Loop | Done (* ... setup code redacted for now ... *) match labels with | Loop -> if !index >= stop then goto Donee; Format.printf "Looping: %d@." !index; incr index; goto Loop | Done -> Format.printf "Done!@."; return () </pre> ``` ^17262497198330 This would result in the following build error: ```neovim <pre> ; dune build File "bin/loop_compsoy.ml", line 17, characters 40-45: 17 | | Loop -> if !index >= stop then goto Donee; ^^^^^ Error: This variant expression is expected to have type Loop.t There is no constructor Donee within type Loop.t Hint: Did you mean Done?</pre> ``` Ok great, checked box number one - but how does it work? ## Problem 1: Solution The primary thing we need to build towards is that our `goto` function cannot take a `string` as an argument, but instead some "generic" `label` argument. In the end, we want our function to look like: `val goto : label -> unit` instead of `val goto : string -> unit`. We're going to hop through a few steps here, but the goal here is to create a way to tell the OCaml compiler that we want to ONLY allow values of some `label` type. We can start with declaring a Module Type (kind of like an interface) that tells us what a `label` needs to look like: ```neovim {"update":true,"path":"_/code/17262499043010.ml","timestamp":1726249914706} <pre> module type LABELS = sig type t val init : t val next : t -> t option end </pre> ``` ^17262499043010 And the Loop label looks like: ```neovim {"update":true,"path":"_/code/17262499497170.ml","timestamp":1726249953089} <pre> module Loop = struct type t = | Loop | Done let init = Loop let next = function | Loop -> Some Done | Done -> None end </pre> ``` ^17262499497170 In this example, we tell OCaml that we want to initialize our label to `Loop`. The `next` function is used to tell OCaml where to go next, if no `goto` is executed (this is one deficiency compared to Tsoding's way of just using a list). Once we have this module defined, we can begin to create the types that we need to enforce using the labels. The following code has some type annotations removed for clarity, but this is the general idea: > [!note] > Only the `make` and `call` functions have type annotations removed / syntax simplified (I have linked the actual code bloew). The usage example doesnt't require any addition CompSoy type annotations. They are just nice labels like you dream of when you miss C. ```neovim {"update":true,"path":"_/code/17262504131190.ml","timestamp":1726251595348} <pre> (* Function to "make" our new goto block *) let make (module L) impl = (* Add a new `Goto` exception variant *) let open struct type exn += | Goto of L.t end in let goto label = raise (Goto label) in let rec handle label = match impl ~goto label with | () -> let> label = L.next label in handle label | exception Goto label -> handle label in handle (* Function used to "call" our goto block *) let call (module L) impl = let handle = make l impl in let> label = Some L.init in handle label (* ====== Actual Usage ====== *) let do_loop start stop = let index = ref start in call (module Loop) @@ fun ~goto -> function | Loop -> if !index >= stop then goto Done; Format.printf "Looping: %d@." !index; incr index; goto Loop | Done -> Format.printf "Done!@." (* Run the loop from 2 to 10 *) let _ = do_loop 2 10 </pre> ``` ^17262504131190 The full code can be found: - `make` and `call`: [GotoFunc.ml](https://github.com/tjdevries/goto.ml/blob/master/lib/GotoFunc.ml) - simple loop: [loop_compsoy.ml](https://github.com/tjdevries/goto.ml/blob/master/bin/loop_compsoy.ml) (includes usage of our next feature though) But this is nice! Our `do_loop` function can use labels and get proper support from the compiler so that we don't provide any labels that don't exist! And it looks awfully similar to the corresponding C(had) version: ```neovim {"update":true,"path":"_/code/17262517982470.c","timestamp":1726251861274} <pre> #include <stdio.h> void do_loop(int start, int stop) { int index = start; Loop: if (index >= stop) goto Done; printf("Looping: %d\n", index); index++; goto Loop; Done: printf("Done!\n"); } </pre> ``` ^17262517982470 ## Problem 2: Early Return But we have a problem... in C, we could throw in a `return value;` whenever we wanted! We can't let OCaml be outshone by C so easily. Now this one might appear insurmountable at first... OCaml doesn't have any way to natively do an early return! So how are we going to implement it? Exceptions. Again. We only have one trick (for now) to change the control flow. We can now extend our `make` function to include `return` function, as well as our original `goto` function. ```neovim {"update":true,"path":"_/code/17262581855161.ml","timestamp":1726258192554} <pre> let make (module L) impl = let open struct type exn += | Goto of l | Return of r let goto label = raise (Goto label) let return result = raise (Return result) end in let rec handle label = match impl ~goto ~return label with | () -> let> label = L.next label in handle label | exception Goto label -> handle label | exception Return result -> Some result in handle </pre> ``` ^17262581855161 The primary difference from original `make` is that we create an additional exception for `Return`, so we can differentiate it from `Goto`. Notice as well that we pass an additional named parameter (`return`) to the `impl` function so that the `return` function is available to change the control flow. Now we can use it like this: ```neovim {"update":true,"path":"_/code/17262581855120.ml","timestamp":1726258192268} <pre> let filter ~start ~stop predicate = let index = ref 0 in call (module Filter) @@ fun ~goto ~return -> function | Init -> index := start; Format.printf "Starting: Searching until: %d@." stop; | Loop -> (* Exit the loop if we have reached the end. *) if !index >= stop then goto Done; (* Check if we have found what we are looking for. We even return early here! Very imperative of us *) if predicate !index then ( Format.printf "EARLY RETURN!@."; return !index; ); (* "Body" of the loop *) Format.printf "Looping: %d@." !index; index := !index + 1; (* Continue looping *) goto Loop | Done -> Format.printf "Done!@."; return (-1) let _ = match filter ~start:2 ~stop:10 (fun i -> i == 5) with | Some 5 -> Format.printf "Found 5! @." | _ -> failwith "I have failed" </pre> ``` ^17262581855120