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

Question

我目前正在为 Haskell 课程编写自动评分器。对于“尾递归”部分，我需要一种方法来自动、安全地检测给定的 Haskell 函数是否是尾递归。

我搜索了现有的工具但找不到任何东西。我认为必须有一种方法可以自动执行此操作，因为毕竟这就是 Haskell 编译器为我们所做的事情。该方法不必采用特定语言或任何语言，因为评分者是项目中的外部实体。例如，它可以是 Haskell 库、命令行工具或用任何其他语言（C、Java、Python 等）编写的代码。

如果实际上没有任何这样的工具，我想我将不得不使用 Haskell 的词法分析器之类的东西，并自己编写检测尾递归的自定义代码。

Answer 1

我首先要指出，尾递归在 Haskell 中很少是一种优点。如果您想使用 Haskell 作为教授尾递归的媒介，那没问题，但实际上在 Haskell 中编写尾递归函数通常会被误导。

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

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

确实是的。那么为什么除了编译器之外还会有其他工具存在呢？编译器已经做到了这一点。所以，当你想这样做时，请使用编译器。我确信这不会是微不足道的，因为您必须学习编译器的类型和其他 API。但它实际上是正确的。

我会首先查看像 这样的函数isAlwaysTailCalled，看看它是否符合您的要求。如果没有，也许您需要使用函数定义的 AST。

Answer 2

我基本上同意 amalloy，但是对于这个自动评分器（大概应该只是一种消除明显错误的快速方法，而不是一个完整可靠的认证工具），我只是在 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

像这样使用

{-# 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 | 断言TailRecursiveDefs [d|
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...