复杂递归堆栈效应？

Question

USING: accessors html.parser.analyzer io kernel math namespaces
  present regexp sequences ;
IN: all-roads-to-wiki

SYMBOL: G

: match-good-pages ( a -- ?/f )
  R/ \/wiki\/[^:]*$/ first-match ;

: filter-urls ( tags -- urls )
  find-hrefs [ present ]     map
  [ match-good-pages ]       filter
  [ match-good-pages seq>> ] map ;

: findpath ( url -- url )
  G get =
  [
     ! false
  ]
  [ scrape-html nip
    [
      dup "title" find-by-name drop 1 + swap nth
      text>> R/ - Wikipedia,/ re-split first print
    ]
    [
      "bodyContent" find-by-id-between filter-urls [ findpath ] map
    ] bi
  ] if ; inline recursive

: allroads-entry ( -- a )
  readln "http://en.wikipedia.org/wiki/" prepend G set-global
  "enwp.org/Special:Random" findpath ; inline

上面的代码将递归遍历维基百科上的每个 link，直到找到它正在寻找的那个。

没关系，因为（希望）findpath 最终会“return”（即不再调用自身）并在堆栈上留下一个巨大的嵌套数据结构。但是当我尝试编译它时，我得到一个 unbalanced-recursion 错误：

The recursive word “findpath” leaves with the stack having the wrong height

unbalanced-recursion: Thrown when stack effect inference determines that an inline recursive word has an incorrect stack effect declaration.

无论我做什么，Factor（可以理解）抱怨堆栈效应不匹配。我需要做什么才能正确递归？

Answer 1

仔细看find-path这个词。我将添加评论，以便您可以看到堆栈中的内容：

: findpath ( url -- url )
    ! 1 item: { url }
    G 
    ! 2 items: { url G }
    get 
    ! 2 items: { url value-of-G }
    =
    ! 1: item { t/f }
    [
       ! 0 items!!!!
       ! false
    ]
    [ scrape-html nip
        [
            dup "title" find-by-name drop 1 + swap nth
            text>> R/ - Wikipedia,/ re-split first print
        ]
        [
            "bodyContent" find-by-id-between filter-urls 
            [ findpath ] map
        ] bi
    ] if ; inline recursive

if 组合器消耗堆栈中的最后一项，因此此代码可能无法运行。这是 findpath 字的工作代码：

: page-title ( seq -- title )
    dup "title" find-by-name drop 1 + swap nth
    text>> R/ - Wikipedia,/ re-split first ;

: page-links ( seq -- links )
    "bodyContent" find-by-id-between filter-urls ;

: scrape-en-wiki-url ( wiki-url -- seq )
    "https://en.wikipedia.org" prepend
    dup print flush scrape-html nip ;

: found-url? ( wiki-url -- ? )
    G get [ = ] [ drop t ] if* ;

: findpath ( wiki-url -- seq/f )
    dup found-url?
    [ drop f G set f ] [
        scrape-en-wiki-url
        [ page-title print flush ] [
            page-links [ findpath ] map
        ] bi
    ] if ; inline recursive

另请查看用于此类任务的 Wikipedia vocab。

复杂递归堆栈效应？

Complex-recursive stack effects?

recursion

tail-recursion

factor-lang