What about goto in clojure?


#1

I’m very new to clojure, but not at all new to Lisp. I have not doubt that the clojure language is interesting and powerful and expressive and with it we can solve many problems quickly, easily, and readably.

Am I correct to understand that clojure does not offer a label/goto construct in the language? It seems that the JVM does indeed have a goto instruction which languages like clojure could potentially take advantage of. stackoverflow/goto Please correct me if I’m wrong, but this seems to present some problems.

  1. Sometimes I like to implement algorithms from Knuth’s Art of Computer Programming. These algorithms are often highly goto-based (for better or worse). If I can make my code look like Knuth’s code, I can easily be sure that it is correct, and I don’t really need to understand it–I can just trust Knuth. However, if I have to “improve” Knuth’s code, then I need to really understand it, and I must be very careful not to introduce errors in translating it to today’s coding style.

  2. I have several packages in Common Lisp which involve compiler time macros which analyse code (pattern matching, boolean algebra, type system calculations) and macro expand to code which is heavily goto based. I.e., the user doesn’t see the goto, but the macro uses goto to efficiently implement finite state machines and binary decision diagrams.

I’d love to hear anyone’s thoughts.


#2

You might be interested in ‘named loop/recur-to’:

https://dev.clojure.org/jira/browse/CLJ-2235


#3

re: CLJ-2235
Yes, these types of loop-exit constructions seem pretty common when goto is not available, but they are less expressive. They impede being able to freely jump forward and backward, which is the freedom you need to efficiently implement finite state machines.


#4

To your specific challenges,

(1) If someone gives you spaghetti code full of goto’s, do you know it is correct if they promise they copied it largely from Knuth?

(2) Mightn’t JVM run-time optimization, today or some day, shortcut Clojure’s flow controls into gotos?

In any event, goto’s very purpose is to promote “complexity” fitting Rich Hickey’s definition of “complex”, and Clojure overtly aims to be “simple”, so you might not get your goto very soon!


#5

(1) I do not trust my ability to create a correct an algorithm better than Knuth’s. Anyway his have been peer reviewed for many years, much more than mine will ever be. So The answer I’d say is “yes”.

(2) I don’t know what the limits of future JVM optimisation is. But taking your question into account, you can take the argument one step further. Why does the JVM have a goto operator, if the hope is that someday all code will be perfectly optimized to goto?

BTW the argument for and against goto is an old one. My argument of course is not that people especially beginners should heavily use goto in production code without careful consideration. However, just like side effects, they should be avoided except where they make sense. And even then, I am not bothered that my code compiles to something involving goto? (I include macro expansion as compilation).


#6

JVM byte code is at a level of machine programming where the goto statement is a very sensible way to create loops and branches. Letting the compiler emit goto statements is significantly different from letting programmers make arbitrary jumps in the code [1]. The fact that most high-level programming languages have decided to abstract away the goto statement by providing higher-level looping and branching constructs, is more a consequence of the fact that goto statements do not belong in that level of language abstraction.

[1] You can (mis)use the exception mechanism in Java to simulate goto, I think.


#7

I don’t really see the difference. (1) Compiler writers are programmers, and (2) if programming high level in all cases is better, then there should be no need for goto at the JVM level.

To me it is the same argument as functional vs imperative programming. It is usually better to think functionally, the benefits are rarely disputed in this forum (I’d suppose). However, side effecting is a feature of the language for good reason, not because people should use them pervasively, rather because they have their place.

If macros are not allowed to expand to goto based code, a certain amount of important flexibility seems sadly lost. Furthermore, code that needs it is implicitly required to be much more complicated, inefficient, and buggy.

However, my original question was “What do you think?” so even answers which disagree with my opinion are appreciated.


#8

I don’t think misused exception handling can implement goto, because java exceptions don’t provide restarts. However, if someone knows how to do it, it could indeed be a JVM-friendly workaround.

That being said, call/cc can implement goto as I understand (assuming first class continuations). My understanding is that unfortunately the JVM is not robust enough to allow a language like Scala or Clojure to implement first class continuations. I saw a post by Martin Odersky where he proposed a limited continuation which was implementable in Scala using the JVM. I don’t understand their limitation however. Odersky/continuations


#9

There’s a big difference between Common Lisp and Clojure: the former supports an imperative style with mutable data so a goto-like construct makes sense (as much as it makes sense in any high-level language), but the latter is much closer to “pure” functional with immutable data and “everything is an expression” – no statements – so a goto-like construct inherently makes a lot less sense in that world.

Clojure chooses to be a higher-level language and tries to discourage “low-level” coding (and thinking). There’s a focus on small, composable functions, built on abstractions. That’s a trade-off that is usually what you want (in the situations where someone would choose Clojure).

As for FSMs, the “Clojure way” is typically to model the FSM as data and reduce the incoming events onto an initial state – no gotos needed.


#10

Goto is an imperative construct, Clojure is a Functional language, and thus, it, in general, does not offer imperative constructs.

This is the primary reason. The other reason is that, even imperative language of the last 20 years have avoided goto as a language construct, due to its misuse. So if modern imperative langs don’t have it, I’d be surprised if a modern FP lang would add goto anytime soon.

There’s a proof that goto isn’t required, granted you have a few of the structured programming alternatives. Can’t remember what the paper is called (someone knows?).

Anyways, I love powerful languages that don’t restrict me, so I wouldn’t mind a goto in Clojure, the same way there is a while loop (which we like to forget about), it would probably be pretty catastrophic to mix it up with laziness, but there isn’t, sorry.

Maybe you can implement a GOTO as a macro using a state machine? That would be quite the fun meta-circular exercise!


#11

Again, lest my point be lost on the readers: I’m not at all saying that goto is required for the semantics of calculation, but I’m saying it is an important low level construct which has its place. Similar to assignment and variable modification, you can alway do without it, but if it is used under the hood to make a certain abstraction more efficient, then it is a good thing. Any powerful construct can be abused, but Donald Trump notwithstanding, we should not eliminate powerful things, because they might cause harm.

Again, a very good use case for using goto is when transcribing an algorithm which uses it and is known to be correct, such as many of Knuth’s algorithms.

It’s a similar argument to why lambda was added to java. You can always do without it by writing lots of code, but having it makes some things much easier, expressive, or even efficient. Even if I’m not a Java programmer, I can easily believe that occasional use of lambda even in imperative code can have a useful place. Same for variable modification, same for destructive list modification, same for destructive hash table modification, same for goto. Missing goto, some algorithms are simply going to necessarily be slower.


#12

BTW, is there a way in Clojure to specify how you want a macro or function compiled? In the sense, can I specify the JVM instructions to use? This is not a feature of standard Common Lisp, but certain implementations have it, and that is in fact how some CL compilers are implemented.


#13

Clojure is a Functional language, and thus, it, in general, does not offer imperative constructs.

This is a common idea but I think it’s a misconception. My understanding is that anything in a do block is imperative. Anything executed in the order provided explicitly by the programmer is imperative. When you specify a program and the order of your declared transformations don’t matter, that’s declarative. Probably all languages sit on a scale between these two. But as far as I can tell, functional lisp can be just as imperative as declarative.


#14

That’s tbe proof I was talking about. I believe this is false, and I remember there is a proof about this. It was during the whole structured programming debacle with Dikstra and all. Basically, there is nothing, even performance wise, that can’t be achieved with goto, that you can’t also achieve without, given a few structural constructs.


#15

Intriguing. Is you don’t need go-to for performance, then why does jvm have go-to?


#16

I mean, we’re heading in a useless debate of semantics, with no absolute truth.

But, I have found it more practical as my taxonomy to differentiate Imperative language as a set of instructions direct to memory and cpu.

So to me, imperative languages always return void. Data is always global. And operations take from memory and write back to memory. They provide abstractions over low level memory and cpu access and instructions. Apart from assembly languages, I don’t think there are many of these around. Java bytecode might be an example of this (I’m no expert in Java bytecode though). Goto is one of their fundamental construct. Maybe OpenGL is like this as well?

They can evolve towards Procedural, which is a structural convention over Imperative which creates the semantics of procedures that can be passed data and return data. C would be an example of this (in a very evolved way). Fortran would maybe be more appropriate.

OOP and FP further extends those structural conventions to create even more semantics.

In that respect, yes, do can be used imperatively, but still, Clojure tries to abstract further away from the turing model the underlying hardware is modeled, to a much higher level, in the spirit of the functional style.

So, if you contrast my definition with yours, in mine, do by itself isn’t imperative, unless you also have every operation in do return void and take zero arguments. In my taxonomy, do would be a procedural construct.


#17

Java doesn’t have goto. The JDK bytecode seems to have it, but at that point, it’s a lower level language, closer to assembly, which is later compiled JIT to machine code.

At the hardware level, everything is imperative, and goto or jump is the only way to branch or loop execution. So as things get compiled down, you will always have goto at some point. It seems JDK bytecode introduces it.

But there are two things involved for performance:

  1. Can algorithms be implemented within similar time and space complexities?

Which I believe this is true.

  1. Can the compiler do as good a job compiling to efficient machine code?

This will probably be compiler dependent.

BTW, I think this might be the paper: https://dspace.mit.edu/handle/1721.1/5753

And this is the proof: https://en.m.wikipedia.org/wiki/Structured_program_theorem


#18

Thanks for the paper references. I believe you are right in that without goto and jump higher level programming structures can indeed achieve the same “complexities”. However, keep in mind that every program of O(n^2) (for example) has the same complexity. But that does not mean they run at the same speed.

A compiler expert once told me that there are two rules of compiler optimization. 1) it is faster to do nothing than to do something, 2) everything else is surprising.

I also heard a presentation by Rich Hikey at ILC in 2009 where he explained the reason Clojure is missing tail call elimination is not because he thinks it is better that way, but rather he just accepted the limitations of the JVM. Even without tail call elimination, for a tightly controlled set of functions, tail call can be emulated by trampolining. Compiling tail calls directly to goto does not change the complexity of the code, but it does eliminate the redundant checks, and boxing needed for trampolining.

If I’m not mistaken the Steele paper you cite, more or less claims that if tail calls can be compiled to goto, then function calling becomes as efficient as goto.

The original application which I was interested in re-implementing in Clojure is more or less that. It is a state machine whose transitions can be represented as tail calls. However, the Common Lisp macro which represents it, goes ahead and expands to goto rather than tail call, eliminating the need for the compiler to do the transformation. The CL compiler I’m using does not do tail-call optimization when in debug mode, which was a problem for my application development.


#19

unless you also have every operation in do return void and take zero arguments.

But, in a sense, every return value, until the end of a do block, is thrown away into the void - side effects are implied. And at the end of a def block, the def gets registered to global state, but the “top level” of the code throws the return value of the form into the void. And in Clojure, the order of those definitions matter, which is even more imperative vs. Java or JavaScript.

Declarative programs are also pushing their definitions on to global state, but the order of those definitions are optimized by the compiler.

I agree this is mostly a useless debate in semantics, but these minutia fascinate me. You could probably argue that any given declarative expression will by necessity too have some sequentiality below some threshold, if at least the ordering of characters in a symbol and operator precedence. And all imperative languages do some level of rearranging the order of things beneath us, declaratively. Perhaps any verb/action/function/method/procedure is an abstraction over an underlying order that allows us to invoke that order declaratively. So, really, perhaps imperativeness and declarativeness are simply directionalities between explicitness and implicitness in the order of our programs, which will always be relative to the complexity of the problem being solved.


#21

And this is why Clojure has recur: to allow tail calls to be compiled to a simple loop/goto – and for the compiler to check that the call is in the tail position. This way you get a performance guarantee: you cannot use recur in a position where the compiler would not be able to turn the call into a loop/goto.