Another Example of Range Termination
Continuing on from my previous post on Range Termination in Go, I’d just like to present another example I’ve come across on how it can be helpful, especially with declarative programming. The following code is for a Graph data structure I’m working on in Scala (available on my github). At the moment, without range termination, a definition for the boolean function, `isDirectedForest`, looks like this:
def isDirectedForest: Boolean =
if ( this is cyclic )
return false
else {
for ( v <- BFS over this from lastVertex )
if ( ( this indegreeOf v ) > 1 )
return false
return true
}
It works, but there are several problems. First, the most obvious, is that it’s not immediately clear what the function is actually doing. Secondly, there are several exit points; clean coding style encourages having only one exit point for each function. Third, for the loop, this is the only way we can actually achieve early termination (sorry, I refuse to use `break`). The range termination syntax I presented in the previous post can be used here to give a much more elegant definition for this function:
def isDirectedForest: Boolean = {
var maxIndegreeIs1 = true
if ( this isNot cyclic )
for ( v <- BFS over this from lastVertex; maxIndegreeIs1 )
maxIndegreeIs1 = ( this indegreeOf v ) <= 1
return ( this isNot cyclic ) && maxIndegreeIs1
}
Which is a much more declarative definition of the function – we’re not defining it so much as we are describing what it does. The final (and only) return statement succinctly tells us what makes a graph a directed forest – it is such if the graph (this) is acyclic and the maximum indegree of any vertex is 1.
The Quest for Gurudom 
The first function looks a lot better. You can easily tell what conditions are causing what return values. It uses a guard clause to return early from a simple condition and the loop condition is a lot easier to understand. I’d remove the else as it’s not needed.
def isDirectedForest: Boolean = { if ( this is cyclic ) return false for ( v 1 ) return false return true }In modern programming languages clean coding doesn’t encourage one exit point. In certain cases e.g. guard clause as per Fowler and Beck, it’s the best way. http://stackoverflow.com/questions/36707/should-a-function-have-only-one-return-statement. Indeed the 2nd function is veering towards the arrow anti pattern http://c2.com/cgi/wiki?ArrowAntiPattern.
As with all other matters of elegance and clarity, it’s purely a matter of personal taste 🙂 I personally dislike the look of Fowler’s “guard statement”, and I find that scattering “return x”s around the place is less descriptive than one return statement at the end that says “return thisConditionHolds && thatConditionHolds”. I find that this style of coding also helps define the invariants that you are proving.
It depends what “modern programming language” you’re using! 🙂 If you are programming in the pure with a functional language, you actually have no choice! I agree that some of the time two or three return statements can look a lot better than one, but more often than not I fall back to expressing my function implicitly as a relation between operations and data, instead of explicitly, by telling some data to go here, some data to go there, then if one thing equals another thing return yet another thing.
Finally, it’s the first function that is veering towards the arrow anti pattern, if any, as it has three levels of nesting, whereas the second function has only two. Also, the inner if statement in the first function, which is leading the function to looking arrow-like, is eliminated in the second function through the combined use of an intention-revealing assignment and the range termination that I am advocating 🙂
The wordpress comment seems to have messed up the contents of my code sample. I must be past it if I can’t manage copy and paste 🙂
And no I’m not counting functional languages as modern 🙂 How old is Lisp anyway 🙂
So does the second function – if, for, statement
At first glance I’m not sure the range termination syntax is very clear. Maybe a for, while syntax would be clearer?
for(v <- BFS over this from lastVertex) while maxIndegreeIs1 { }Actually now that I see it, I think you're onto something with this range termination. It would look and read a lot better than break statements.
Will try to inlcude updated sample code with only two levels of nesting. It seemed to mess up at the less than symbols so removing those.
def isDirectedForest: Boolean = if ( this is cyclic ) return false var maxIndegreeIs1 = true for ( v <- BFS over this from lastVertex) while maxIndegreeIs1 maxIndegreeIs1 = ( this indegreeOf v ) <= 1 return maxIndegreeIs1 }Don’t worry, I’ve fixed your syntax for you 🙂 (I’m not sure if you’re able to insert tags in the comments).
Ha, if you’re going to play that game, you’re on the losing side, because I can argue that your precious Java and C++, imperative languages are derived from the oldest language, Fortran (1957) *shudder* whereas Lisp was developed in 1958 🙂
Sorry, I think our interpretations of nesting is different, but by your interpretation, the first example actually has four levels of nesting – else, for, if, statement 🙂
My DSL-like example with depth first search over a graph does overshadow the very feature I’m trying to encourage alright 😛 both a semi-colon and a while have their merits – the semi-colon is reminiscent of the typical for-loop style, and has brevity on it’s side, whereas while does make the separation between the generator and the exit clause clear. The only problem with using while is that you would need an extra pair of parentheses, in case the exit condition is a union of multiple conditions. Otherwise, the compiler may not be able to make the distinction between the end of the condition and the next statement, especially in a language that has as many syntax exceptions as Scala does. Take the following code for instance:
Scala could very well consider the maxIndegreeIs1 beginning the second statement to be a method of the first maxIndegreeIs1 and fail to compile. Of course, this would not be a problem in a language like Google's Go, where the parentheses are implied but the curly braces are mandatory.
Thanks very much for the kind words (finally :P). Spread the word! 🙂