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.
Intriguing. Is you don’t need go-to for performance, then why does jvm have go-to?
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.
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:
- Can algorithms be implemented within similar time and space complexities?
Which I believe this is true.
- 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: Structured program theorem - Wikipedia
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.
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.
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.
Yea, that was my #2 consideration. I wasn’t talking specifically of Clojure. I meant in general, people moved away from goto, because it was eventually demonstrated to be unnecessary given a good compiler and people found the non goto using code to be simpler.
You’re right, when it comes to Clojure, mutual recursion will add boxing into thunks, and require an extra trampoline. But, I would try it before calling it slower. The JDK is quite an advanced compiler, it might still end up faster then the CL implementation you are mimicking.
If it doesn’t, you’ll have to implement it in Java. It doesn’t have goto, but you instead need to use label breaks and continues: Branching Statements (The Java™ Tutorials > Learning the Java Language > Language Basics)
It is halfway between a goto and a loop. Should allow equal performance, but you might need to rewrite the algo to suit it.
You could also, if you are adventurous, try to use core.async, I believe csp can mimick goto behaviour. Now the implementarion might be trickier.
You can use the clojure.asm namespace to compile directly to bytecode. This gives you full control, but at that point, you are almost hand coding in the JDK bytecode, which is close to assembly. There’s also tools.emitter.jvm, and insn which allow for similar control, but are not baked into clojure core.
Yes, me too. I just prefaced my post, because there’s obviously going to be differences in opinion here, and it’s not like anyone can say one opinion is better than the other.
Ya, I agree. I think I just like to distinguish things more granularity as well as more generally.
For example, I think a def is imperative, in that it is a global write to memory, it isn’t a procedure or a function, but almost a pure instruction directly to memory or cpu.
A do I feel is more challenging. It can be used imperatively, for example:
(do
(def a 20)
(def b 30)
(if (> a b)
(def b "Hello World!")
(def b "Bye bye World!"))
(println b))
But I wasn’t free to use whatever I wanted inside the do, or in my opinion, it would have already started to become procedural. For example:
(do
(let [a 20 b 30]
(if (> a b)
(println "Hello World!")
(println "Bye bye World!"))))
This is now procedural code to me. I introduced local variables, and the idea of subroutines (the nesting of println inside if).
What do isn’t is functional. Or used functionally it is redundant and can be removed.
So I say, imperative is a series of instructions direct to cpu and memory. Even my use of if is pushing it in my opinion. Normally it would be a conditional jump to the instructions that defs b, but Clojure doesn’t have goto, so I had to cheat a bit.
Procedural is a set of instructions where instructions can be grouped inside of subroutines, aka, procedures, which can be nested in one another, and call each other, where execution automatically returns back to where we were and values can be passed in and out of them at known jump points. This adds the idea of scoped data, a move away from global data, and new instructions to manipulate that local data.
Functional makes away completly with global data, and with series of instructions. There are no instructions to cpu, or access to global memory. The entire program is a tree of functions composed together, which gets reduced using term re-writing into the final result:
(println (#(if (> a b) "Hello World!" "Bye bye world!") 20 30))
This is cheating as well, because println is an instruction, but since the computer only executes instructions, you need some somewhere to be useful, so normally in functional it is pushed to the edge like I did.
And where you contrast imperative and declarative. I think I don’t associate functional with declarative per say. It isn’t imperative for sure. But declarative to me is more orthogonal. Imperative is when you say “How to do something, but not what”. And declarative is when you say “What to do, but not how”, and the computer figures out how automatically. For example, html is like that, or Apache Ant, yet those are not functional languages, but they are declarative. Logic programming is another example. You could say ML is declarative as well. Sometimes, FP is said to be more declarative, but that’s more to do with the available libraries and features common to FP langs then FP itself I feel. Like higher level functions, like filter, remove, partition, etc., are closer to What then How. But you could have an FP lang without them. Or monadic let is more declarative in that you say What, and the computer figures out how to order the things for it to work. But you can have an FP lang without monadic let.
Edit: Oh, and I had kind of lost my train of thought. So above is my granular differentiation. In practice, borders are blurred. That’s when I switch to a more general taxonomy. The essence of Clojure is functional. It tries to be as much as is practical. So in that way, it isn’t an imperative or procedural language. Just like a SUV isn’t a truck, even though I can use it to move a TV around, or I can attach a UHAUL to it. That’s because the essence of an SUV is different to that of a truck. Yet, it is still a car, with an above average cargo size, and a potentially more powerful motor, which could have higher clearance, etc.
Anyways, that’s just how I like to model these.
3 Likes
@seancorfield, correct me if I’m wrong, but recur does not really give tail call semantics; it only allows looping. Right? For example I cannot use recur to make two different functions tail call each other. I can only use it to emulate a function calling itself in tail position. As I understand, I cannot even use recur to have a local function call its parent function in tail position.
@didibus, that is a really good suggestion. Thanks for the tip. It would indeed be interesting to get some real data on how well the JVM handles this situation.
In fact, with trampolining I should be able to implement the TAGBODY/GO from CL.
(tagbody
(setq val 1)
(go point-a)
(incf val 16)
point-c
(incf val 04)
(go point-b)
(incf val 32)
point-a
(incf val 02)
(go point-c)
(incf val 64)
point-b
(incf val 08))
Correct, you’d need to use trampoline there if you didn’t want actual recursive calls.
Correct, recur is specifically for self-call tail recursion.
In reality, there is a lot less recursion in Clojure than you might think. reduce, transducers, and other higher-level constructs are the idiomatic way to deal with a lot of things where you might use recursion in CL, for example.
We have a 90,000 line code base and the perceived limitations you are asking about are not a concern in real-world code, in my experience.
I think it’s important to understand that Clojure != Lisp in the classic sense (even tho’ it is in the Lisp family). Clojure takes a different, and very carefully designed, path based on being a high-level but general purpose JVM-based language, first and foremost. That means that its idioms are sometimes different from other Lisps, as well as to other functional languages – and it is very strongly influenced by the JVM being its host in certain places.
1 Like
Perhaps I am repeating someone else’s comment. Apologies if so.
I think the short answer is that no, Clojure does not have an arbitrary goto capability. If you want that, you can write Java code and use its goto. Java is effectively Clojure’s “in-line assembler” language, except it is not in-line.
It seems that leaving out an arbitrary goto construct was an explicit design choice, not an accident.
What to do in the situations you have described where it might be nice to have it? You could use Java. You could use C, compile it, and then JNI or JNA to link that code into a JVM and call that from Java or from Clojure. But it seems unlikely to me that the Clojure maintainers believe they are missing the boat of a bunch of capabilities that they want in the language by not having goto. The use cases you describe are unlikely to be theirs, or else they would have added it.
2 Likes
Actually, Java does not have a goto either. JVM bytecode does. Which is very different.
Right you are. Learn something new every day: https://stackoverflow.com/questions/2545103/is-there-a-goto-statement-in-java
There is a bytecode for it, and it is a reserved keyword in Java source code so they could add it to Java later if they wanted to, without breaking existing Java programs that might have otherwise used ‘goto’ as an identifier name. But it has never been added to Java.
So it looks like if you want to use the JVM goto byte code, you must generate JVM byte code yourself (which a few libraries enable you to do, including one used by Clojure’s compiler itself), or find another JVM-based language that issues such goto JVM opcodes. I do not know of any, but I haven’t looked, either.
Like James Gosling for Java (and Java language developers since him), Rich Hickey chose not to include goto in Clojure.
FWIW, I’m developing an embedded DSL library right now to make it easier to write imperative (and efficient) code in Clojure.
JiSE compiles Clojure-flavored Java code (or Java-flavored Clojure code?) into JVM bytecode at macro expansion time. It’s still far from complete, but is already equipped with some convenient features to write imperative code, such as assignment, nested loops, labeled break/continue, etc. Also, I’m considering adding Common Lisp’s tagbody-like construct as an extension for future work.
1 Like
In CL (tagbody) and (go) are not really a goto like a setjmp/longjmp C style branching but is implemented in CL…
From an implementation standpoint, if you’re interpreting a Lisp-like program, you might do something a bit like this:
- Upon entering a
tagbody, begin a table of destinations. (a map of symbol→list after tag) - Iterate each form within the
tagbody -
if (symbolp this-element), then store the address (a pointer to that form) into the table - otherwise,
(eval this-element)as usual - When encountering a
goform, look up the destination symbol, and (destructively) change your program’s “current instruction” pointer to that value (in our case recur to loop). Then, jump to your routine to fetch the next instruction. - When exiting the
tagbody, just discard the destination table.
The destination tables will (ultimately) need to be a stack (referred-to in older Lisp documentation as a “push-down list” or PDL), since you’ll search upwards through dynamic scope to find the tag in question. Keep in mind, in Common Lisp, go tags are a separate namespace from variables, functions, classes, et al.
You can write your tagbody/go functions in Clojure probably in a Macro/function with a loop/recur to manage the go. Excellent exercise trying to make it as pure function…
But anyway tagbody/go was not meant to create spaghetti pseudo FORTRAN IV- or BASIC code, but to create looping macros for the CL language… 
You can read this excellent post : https://malisper.me/loops-in-lisp-part-1-goto/
1 Like
In conversation on Slack about this, @leonoel threw this together: https://gist.github.com/leonoel/770ac5383c1c85ec16ae57cc1d8c7d63
1 Like
Now that’s cool. But I didn’t understand how you make the execution flow fall through in case there is no go within a block between two labels.
(let []
(tag body
(print "h")
(go point-a)
point-c
(println "world")
(go point-d) // I'd like to exit directly from here ????
point-a
(print "el")
point-b
(print "lo ")
(go point-c)
point-d))
1 Like