Racket: Identifying tail recursion?

Question

I wrote two different functions in racket to determine whether a list of numbers is ascending:

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (and (< (car list) (car (cdr list))) (ascending (cdr list)))))

(define (ascending-tail list)
  (ascending-tail-helper #t list))

(define (ascending-tail-helper prevBool rest)
  (if (<= (length rest) 1)
      prevBool
      (ascending-tail-helper (and prevBool (< (car rest) (car (cdr rest)))) (cdr rest))))

I had the hardest time determining whether or not the first ascending was tail recursive, so I rewrote it using what I believe to be tail recursion.

The reason why I retrospectively believe the first one to not be tail recursive is that I believe at each level of recursion, the function will be waiting for the second argument in the "and" statement to return before it can evaluate the boolean expression. Conversely, for ascending-tail-helper, I am able to evaluate the lesser than expression before I do my recursive call.

Is this correct, or did I make myself even more confused than before?

Lambart

Answer 1

You are correct, in the first version the recursive call returns to and, whereas in the second version the recursive call is a tail call.

However, and is a macro, and is generally expanded using if

(define (ascending list)
  (if (<= (length list) 1)
      #t
      (if (< (car list) (car (cdr list)))
          (ascending (cdr list))
           #f)))

which is tail recursive.

Gasometer

Oh wow, I had no idea! That certainly explains why the function acted tail recursive in the debugger. – Lambart

This would be a bit stronger with a reference to the language manual. In some languages, e.g., Scheme, the last conjunct in an and is explicitly stated as tail context. That is, it doesn't matter how and is implemented (as a macro, built-in, etc.); the last position is a tail position. The way this is phrased now makes it sound like a (fortunate) coincidence that the macro-expansion but the last conjunct in tail position. Racket might actually specify that it is, for sure. – Empery

Just found it in the Racket docs. The final argument to and is in tail position. – Empery

Answer 2

DrRacket can help you determine whether a call is in tail position or not. Click the "Syntax Check" button. Then move the mouse pointer to the left parenthesis of the expression in question. In your example I get this:

The purple arrow shows that the expression is in tail-position.

From the manual:

Tail Calls: Any sub-expression that is (syntactically) in tail-position with respect to its enclosing context is annotated by drawing a light purple arrow from the tail expression to its surrounding expression.

Champollion

Racket's docs also say that the the final argument to and is in tail position. – Empery

Answer 3

One of the requirements for a function to be in tail position is that it's return value be usable as the return value of the parent function without modification or inspection. That is, the parent function should be able to return immediately, having evaluated the tail position statement.

On first appearance, your first function,inspects the return value of ascending. It seems that doesn't return ascending's value but, instead, a value derived from it. However, according to the relevant section of the R5RS spec, the final expression in an and statement is in tail position. (When I'm properly awake, I know this)

So you are wrong.

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5

(Note: edited to correct my initial hasty answer).

Weathered

Thanks. What was really throwing me off was the fact that when I was debugging the non-tail recursive function in DrRacket, it didn't properly hold onto the call stack in the "stack" pane; and at the base case the debugger didn't follow the "and" evaluations; but instead returned instantly, just like a tail recursive function would! Truly confusing. – Lambart

Not true, @itsbruce, and is a macro that does not inspect it's second value, just returning it when the first argument is true; see my answer for the usual expansion. – Gasometer

Ah, point, Doug. Now that I recall, and is implemented via a macro, unlike not. The r5rs spec, which I was re-reading just the other day, explicitly describes this. – Weathered

The implementation doesn't actually matter, though. It could be a built-in, or a macro, or whatever. The important thing is whether a spec says it's in a tail position. In Scheme, it is (as, e.g., the documentation shows). I don't know about Racket. – Empery

Answer 4

Racket's documentation on tail positions says that the place to check what's in tail position and what's not is the documentation for the particular form:

Tail-position specifications provide a guarantee about the asymptotic space consumption of a computation. In general, the specification of tail positions goes with each syntactic form, like if.

Racket's docs on and say (emphasis added):

(and expr ...)

If no exprs are provided, then result is #t.

If a single expr is provided, then it is in tail position, so the results of the and expression are the results of the expr.

Otherwise, the first expr is evaluated. If it produces #f, the result of the and expression is #f. Otherwise, the result is the same as an and expression with the remaining exprs in tail position with respect to the original and form.

Empery