Automatically detect whether a Haskell function is tail recursive

Question

I'm currently writing an auto-grader for a Haskell course. For the section on "tail-recursion", I need a way to automatically and safely detect whether a given Haskell function is tail-recursive or not.

I've searched for existing tools but couldn't find anything. I assume there must be a way to do this automatically, because after all that's what the Haskell compiler does for us. The method doesn't have to be in a specific language or anything since the grader is an external entity in the project. For example, it can be a Haskell library, a command line tool, or code written in any other language (C, Java, Python, etc).

If there actually isn't any such tools, I assume I'm gonna have to use something like a lexical analyzer for Haskell, and write custom code that detects tail recursion myself.

Have you tried compiling the code, and looking if the tail call optimization is done? — jthulhu
– jthulhu, Commented Jan 25, 2023 at 21:46

amalloy · Accepted Answer · 2023-01-25 07:54:19Z

9

I would first point out that tail recursion is rarely a virtue in Haskell. It's fine if you want to use Haskell as a medium for teaching tail recursion, but actually writing tail recursive functions in Haskell is usually misguided.

Presuming you still want to do this, I would highlight

after all that's what the Haskell compiler does for us

Yes, indeed. So why would any tool other than the compiler exist? The compiler already does exactly this. So, when you want to do this, use the compiler. I'm sure it won't be trivial, because you'll have to learn the compiler's types and other API. But it will actually be correct.

I would start by looking at a function like isAlwaysTailCalled, and see if that does what you want. If it doesn't, maybe you need to consume the AST of the function definition.

answered Jan 25, 2023 at 7:54

amalloy

93k8 gold badges149 silver badges216 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

chi Over a year ago

@MarkSeemann You can define map in a non-tail recursive fashion, map f (x:xs) = f x : map f xs, but you can also define it using tail recursion using an accumulator parameter. The first definition also works on infinite lists, and usually leads to more efficient code: e.g. sum (map f xs) can run in constant space with the first definition, but requires linear space if map if defined using tail recursion. As a fast and loose thumb rule, if g returns a small-sized result like an Int, then tail recursion might be good, but if g returns a large structure (list/tree/...) not so much.

Fyodor Soikin Over a year ago

Call stack is not a thing in Haskell

Ben Over a year ago

@MarkSeemann I recently wrote an answer to a different question that gave some more detail on why deep recursion doesn't cause stack consumption in Haskell, which you might be interested in: stackoverflow.com/a/75168800/450128

Daniel Wagner Over a year ago

In fact, I just remembered this question, where tail recursion caused a stack overflow, and the fix required writing something that is technically not tail recursive.

chi Over a year ago

@MarkSeemann Not in general. A non-tail call like f x = 1 + f x will indeed exhaust the stack, but f x = 1 : f x will not exhaust the stack. The point is that a+b needs to evaluate a and b before "returning", while a:b can "return" without evaluating either. In a strict language tail calls are fundamental, but in a lazy/non-strict language like Haskell using tail calls can often be severely detrimental in terms of performance.

|

leftaroundabout · Accepted Answer · 2023-01-25 10:50:18Z

I basically agree with amalloy, however for this auto-grader (which presumably should only be a quick way to weed out clear-cut mistakes, not a complete reliable certification tool) I would just cobble something together in Template Haskell.

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE LambdaCase      #-}

module TailRecCheck where

import Language.Haskell.TH

isTailRecursive :: Dec -> Bool
isTailRecursive (FunD fName clauses) = all isClauseTR clauses
 where 
       isClauseTR (Clause _ (NormalB (AppE f x)) _)
          -- Function application that could be a tail call
          = case f of
             -- It's only a tail call if the function is the
             -- one we're currently defining, and if the rest
             -- is not recursive
             VarE fn -> fn==fName && isConstant x
       -- Constant expressions are allowed as base cases
       isClauseTR (Clause _ (NormalB body) _) = isConstant body
       --isClauseTR _ ... _ = ...

       isConstant (VarE n) = n /= fName
       isConstant (ConE _) = True
       isConstant (LitE _) = True
       isConstant (AppE f x) = isConstant f && isConstant x
       isConstant (InfixE l op r)
          = all isConstant l && isConstant op && all isConstant r
       --isConstant ... = ...

assertTailRecursiveDefs :: Q [Dec] -> Q [Dec]
assertTailRecursiveDefs n = n >>= mapM`id`\case
   dec
     | isTailRecursive dec -> return dec
     | otherwise -> fail ("Function "++showName dec
                              ++" is not tail recursive.")
 where showName (FunD n _) = show n

To be used like

{-# LANGUAGE TemplateHaskell #-}

module TailRecCheckExample where

import TailRecCheck

assertTailRecursiveDefs [d|
    f x = 4

    g 0 = 1
    g x = g (x-1)

    h 0 = 1
    h x = 1 + h (x-1)
  |]

TailRecCheckExample.hs:7:1: error:
    Function h_6989586621679042356 is not tail recursive.
  |
7 | assertTailRecursiveDefs [d|
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^...

Collectives™ on Stack Overflow

Automatically detect whether a Haskell function is tail recursive

2 Answers 2

9 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related