标签: trampolines

在最近的工作讨论中,有人提到了蹦床功能.

我已经阅读了维基百科的描述.这足以给出功能的一般概念,但我想要更具体的东西.

你有一个简单的代码片段来说明蹦床吗？

这是代码:

function repeat(operation, num) {
  return function() {
    if (num <= 0) return
    operation()
    return repeat(operation, --num)
  }
}

function trampoline(fn) {
  while(fn && typeof fn === 'function') {
    fn = fn()
  }
}

module.exports = function(operation, num) {
  trampoline(function() {
    return repeat(operation, num)
  })
}

我已经读过蹦床用于处理溢出问题,因此该函数不仅会保持调用自身和堆栈.

但是这个片段的功能如何呢？特别是trampoline功能？它究竟做了什么while以及它是如何实现其目标的？

感谢您的任何帮助 :)

由于 Scala 开发人员正在学习 IO Monad，因此一般来说，在无法进行尾调用优化的情况下，对于递归来说是必需的 Trampoliing 技术细节，我想知道 Haskell 是如何在本机上避免它的。

我知道 Haskell 是一种懒惰的语言，但是我想知道是否有人可以进一步详细说明。

例如，为什么 ForeverM stackoverflow 在 Scala 中没有？嗯，我可以回答蹦床，我可以在库和博客中找到执行此操作的实际代码。我实际上自己实现了一个基本的蹦床来学习。

它是如何在 Haskell 中发生的？有没有办法稍微解开懒惰，给出一些指示，也许还有有助于更好地理解它的文档？

sealed trait IO[A] {

.....


  def flatMap[B](f: A => IO[B]): IO[B] =
    FlatMap[A,B](this, f) // we do not interpret the `flatMap` here, just return it as a value
  def map[B](f: A => B): IO[B] =
    flatMap[B](f andThen (Return(_)))

}
case class Return[A](a: A) extends IO[A]
case class Suspend[A](resume: () => A) extends IO[A]
case class FlatMap[A,B](sub: IO[A], k: A …

如果我理解正确,可以使用scala.util.control.TailCalls通过使用trampoline来避免非尾递归函数的堆栈溢出.API中给出的示例很简单:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result 

但是,更有趣的情况是,如果要在重新调用之后执行某些操作.我有一个"天真"的因子实现以某种方式运行

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

但这看起来很可怕,我怀疑这是用途.所以我的问题是如何使用TailCalls正确编写阶乘或斐波纳契函数(是的,我知道如何使用累加器来使它们尾递归)？或者TailCalls不适合这种问题吗？

我用C/C++的混合编写了一个小的Scheme解释器,但我还没有实现正确的尾调用.

我知道MTA算法上的经典切尼,但还有其他很好的实现方法吗？我知道我可以将Scheme堆栈放在堆上,但这仍然不能正确消除,因为标准表示应该支持无限数量的活动尾部调用.

我也摆弄了longjmps,但到目前为止,我认为它只适用于非相互递归尾调用.

基于C的主要方案如何实现正确的尾递归？

我有兴趣挂钩,我决定看看我是否可以挂钩一些功能.我对使用类似弯路的图书馆不感兴趣,因为我想拥有自己做的经验.通过我在互联网上找到的一些资料,我能够在下面创建代码.这是基本的,但它可以正常工作.但是当挂钩由多个线程调用的函数时,它被证明是非常不稳定的.如果几乎同时进行两次通话,它就会崩溃.经过一些研究,我认为我需要创建一个蹦床功能.在寻找了几个小时后,我无法找到任何其他关于蹦床的概述.我找不到任何具体的关于编写蹦床功能,或者它们是如何工作的.如果任何人可以帮我写一个,发布一些消息来源,或者至少通过推荐一些文章,网站,书籍等指向我正确的方向.我将非常感激.

以下是我写的代码.这是非常基本的,但我希望其他人可以从中吸取教训.

TEST.CPP

#include "stdafx.h"

Hook hook;

typedef int (WINAPI *tMessageBox)(HWND hWnd, LPCTSTR lpText, LPCTSTR lpCaption, UINT uType);

DWORD hMessageBox(HWND hWnd, LPCTSTR lpText, LPCTSTR lpCaption, UINT uType)
{
    hook.removeHook();
    tMessageBox oMessageBox = (tMessageBox)hook.funcPtr; 
    int ret =oMessageBox(hWnd, lpText, "Hooked!", uType);
    hook.applyHook(&hMessageBox);

    return ret;
}

void hookMessageBox()
{
    printf("Hooking MessageBox...\n");
    if(hook.findFunc("User32.dll", "MessageBoxA")) 
    {
        if(hook.applyHook(&hMessageBox))
        {
            printf("hook applied! \n\n");
        } else printf("hook could not be applied\n");
    }   
}

hook.cpp

#include "stdafx.h"

bool Hook::findFunc(char* libName, char* funcName) 
{
    Hook::funcPtr = (void*)GetProcAddress(GetModuleHandleA(libName), funcName); 
    return (Hook::funcPtr …

几个星期前,Dragisa Krsmanovic 在这里问了一个关于如何在Scalaz 7中使用免费monad来避免堆栈溢出的问题(我已经调整了他的代码):

import scalaz._, Scalaz._

def setS(i: Int): State[List[Int], Unit] = modify(i :: _)

val s = (1 to 100000).foldLeft(state[List[Int], Unit](())) {
  case (st, i) => st.flatMap(_ => setS(i))
}

s(Nil)

我认为只是举起一个蹦床StateT应该工作:

import Free.Trampoline

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st.flatMap(_ => setS(i).lift[Trampoline])
}

s(Nil).run

但它仍然打击堆栈,所以我只是将其作为评论发布.

Dave Stevens刚刚指出用应用程序*>而不是monadic 进行排序flatMap实际上运行得很好:

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case …

让我们从 的简单定义开始foldRight：

def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
  as match {
    case Nil => base
    case head +: next => f(head, foldRight(base)(f)(next))
  }
}

这种组合器的优点之一是它允许我们编写类似的内容（我使用 anif来使 的短路行为||更加明确）：

def containsElement[T](e: T)(as: Seq[T]): Boolean = {
  foldRight(false)((el: T, acc) => if (el == e) true else acc)(as)
}

然后它适用于无限结构：

val bs = 0 #:: 1 #:: 2 #:: 3 #:: LazyList.continually(1)
containsElement(3)(bs)

然而，它不适用于非常长的序列，因为我们正在炸毁堆栈：

val veryLongList = List.fill(1_000_000)(0) …

我们正在开发一款iOS应用.当我们在PC上测试应用程序时,一切运行良好,但是当我们在iPad/iPhone4上运行时,我们经常收到"Ran out of Trampolines type 2"错误消息和应用程序崩溃.过去几天我们一直在努力找出原因并解决问题并尝试了我们在网上找到的所有建议,但我们仍然没有取得任何进展.我们找到的唯一解决方案是从帖子/网页上讨论使用如下编译器设置调整蹦床设置:-aot"nrgctx-trampolines = 4048"-aot"nimt-trampolines = 4048"in monouchouch.但我们正在使用Unity3D开发我们的应用程序,因此我们没有向我们公开此编译器选项.但是我相信Monotouch和Unity3D都基于Mono框架,所以我猜相同的编译器设置也可以应用到我们的unity3D项目中？

有谁知道这是否正确？如果是的话,是否有人能够给我一些关于如何在我们的Unity3D项目中启用此选项的说明？

非常感谢提前!

这些语言不支持"原生"的相互递归函数优化,所以我猜它必须是蹦床或者......嘿......重写为循环)我想念一些东西吗？

更新:似乎我对FSharp撒了谎,但我只是没有看到谷歌搜索时相互尾调用的例子