自动检测Haskell函数是否为尾递归。

Question

我正在编写一个Haskell课程的自动评分程序。在“尾递归”部分，我需要一种自动且安全地检测给定Haskell函数是否为尾递归的方法。

我已经搜索过现有的工具，但没有找到任何东西。我认为一定有一种自动化方法可以实现这一点，因为毕竟这就是Haskell编译器为我们做的事情。由于评分程序是项目中的外部实体，所以该方法不必使用特定语言或任何其他语言编写（例如，它可以是一个Haskell库、命令行工具或使用任何其他语言编写的代码（C、Java、Python等））。

如果实际上没有这样的工具，我认为我将不得不使用类似于Haskell的词法分析器，并编写自定义代码来检测尾递归。

- Mobin

---

只需向其输入足够的数据以溢出栈。 - n. m.

你试过编译代码并查看是否进行了尾递归优化吗？ - jthulhu

Answer 1

我首先要指出，在Haskell中，尾递归很少是一种优点。如果你想使用Haskell作为教授尾递归的媒介，那么这是可以的，但实际上在Haskell中编写尾递归函数通常是不明智的。

假设你仍然想这样做，我会强调：

“毕竟这就是Haskell编译器为我们做的事情。”

确实是这样。那么除了编译器之外，为什么还需要其他工具呢？编译器已经完全做到了这一点。所以，当你想要这样做时，使用编译器。我相信这并不容易，因为你将不得不学习编译器的类型和其他API。但这将是正确的。

我会从查看类似isAlwaysTailCalled的函数开始，并查看它是否符合您的要求。如果不行，也许您需要消耗函数定义的AST。

- amalloy

---

调用栈在 Haskell 中并不存在。 - Fyodor Soikin

@MarkSeemann 我最近回答了另一个问题，详细解释了为什么在 Haskell 中深递归不会导致堆栈消耗。您可能会感兴趣：https://dev59.com/vX4QtIcB2Jgan1zntrD6#75168800 - Ben

调用栈是Haskell中的一个概念。但它的使用方式与其他语言中的调用栈不同；即：它用于跟踪在评估某些内容的过程中已输入哪些thunk。深度嵌套的thunk会导致深度堆栈，如果尝试评估其中一个，您可能会使堆栈溢出。但尾递归并不能真正帮助避免深度嵌套的thunk。 - Daniel Wagner

事实上，我刚想起来这个问题，其中尾递归导致堆栈溢出，修复需要编写一些在技术上不是尾递归的东西。 - Daniel Wagner

@MarkSeemann 一般而言不会。像 f x = 1 + f x 这样的非尾调用确实会耗尽堆栈，但是 f x = 1 : f x 不会耗尽堆栈。关键在于 a+b 需要在“返回”之前评估 a 和 b，而 a:b 可以在不评估任何一个的情况下“返回”。在严格语言中，尾调用是基本的，但在像 Haskell 这样的惰性/非严格语言中，使用尾调用通常会严重影响性能。 - chi

Answer 2

我基本上同意amalloy的观点，但对于这个自动评分系统（假设它只是一种快速筛选明显错误而不是完全可靠的认证工具），我会在模板哈斯克尔中组合一些代码。

{-# 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

使用方法：

{-# 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: 错误：
    函数h_6989586621679042356不是尾递归函数。
  |
7 | assertTailRecursiveDefs [d|
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^...

- leftaroundabout