回文和丹维对直接文体的评论

Question

下面是一些代码，用于在 n+1 次比较中以“直接方式”判断列表是否为回文

pal_d1 :: Eq a => [a] -> Bool
pal_d1 l = let (r,_) = walk l l in r
        where walk l           [] = (True,l) 
              walk l       (_:[]) = (True,tail l)
              walk (x:l) (_:_:xs) = let (r, y:ys) = walk l xs
                                    in (r && x == y, ys)

可以用几个例子来测试

-- >>> pal_d1 [1,2,1]
-- True

-- >>> pal_d1 [1,2,2,1]
-- True

-- >>> pal_d1 [1,2,3,4,2,1]
-- False

Danvy 在“There and back again”中声称没有控制运算符的直接样式解决方案（就在 4.2 之前），因为在下面的 CPS 样式解决方案中非线性使用延续：

pal_cps1 :: Eq a => [a] -> Bool
pal_cps1 l = walk l l (\_ -> trace "called" True) 
    where 
          walk  l          []  k = k l
          walk  l       (_:[]) k = k (tail l)
          walk (x:xs) (_:_:ys) k = walk xs ys (\(r:rs) ->  x == r && k rs)

第一个代码如何不与此断言相矛盾？

（延续性如何不被线性使用？）

Answer 1

他并不是说没有控制算子就没有解

The continuation is not used linearly and therefore mapping this program back to direct style requires a control operator.

本文的背景是研究直接风格和 CPS 之间的系统转换，该段的主张是，如果继续以花哨的方式使用，从 CPS 返回是棘手的。

通过一些努力，您可以将其重新整理成一个漂亮的形状，但问题仍然存在，编译器如何自动执行此操作？

(and how is the continuation not used linearly ?)

在论文中，continuation在andalso的右边（&&）所以如果左边的操作数是False.

就被丢弃

在操作语义中，您可以将延续视为评估上下文，在该视图中，丢弃延续对应于抛出异常。当然可以做到，但关键是这需要源语言的额外机制。

Answer 2

CPS 代码（在问题的原始版本中——因为由 OP 编辑）似乎有问题。看起来应该是

      walk (x:xs) (_:_:ys) k  =  walk xs ys (\(z:zs) -> x == z && k zs)

非 CPS 代码从中间开始比较，并进行 n `div` 2 次比较，列表长度为 n。即使发现不匹配，它也会继续测试，因此 "linear".

在这种情况下，CPS 代码会立即退出，因为 (False && undefined) == False 成立； “非线性” 也是如此。这两个不等价，所以第一个没有说明第二个。

正如所说，不调用延续相当于在没有延续的代码中抛出异常，论文的作者显然称之为“直接 [即非 CPS( ?) --wn] 样式".

_{（没看过论文）}

顺便说一下，以“直接”方式编写早期退出的解决方案并不困难。我们将使用相同的龟兔赛跑技巧来发现两半，同时反向构建前半部分，然后在 Haskell 中调用 and $ zipWith (==) first_half_reversed second_half 或其等效的短路直接递归变体，用严格的语言，例如方案.

回文和丹维对直接文体的评论

Palindrome and Danvy's remark on direct style

haskell

recursion

continuations

continuation-passing

callcc