Effets de pile complexes récursifs?

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

Le code ci-dessus se répètera sur tous les liens sur Wikipedia jusqu'à ce qu'il trouve celui qu'il recherche. C'est bon, car (espérons-le) findpath finira par "retourner" (c'est-à-dire ne pas s'appeler à nouveau) et laisser une énorme structure de données imbriquée sur la pile. Mais quand je tente de compiler, je reçois une erreur unbalanced-recursion:Effets de pile complexes récursifs?

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.

Peu importe ce que je fais, le facteur (compréhensible) se plaint de l'effet de pile ne sont pas correspondre. Que dois-je faire pour que cela se répète correctement?

Source

2016-04-10 cat

1- 'drop f' dans la branche false, et' sift' pour supprimer les falses dans la liste, si je comprends bien. 2- Je pense qu'il manque un 'dup' avant' G get = '(car le = consomme l'url). 3- Êtes-vous sûr que la récursivité se termine? La liste ne va-t-elle pas continuer de croître pour toujours? –

N'est-ce pas une recherche en profondeur d'abord sur les graphiques des liens? Si vous trouvez un cycle quelque part, vous serez coincé là pour toujours! –

@fedes. vous avez probablement raison, mais il est supposé fonctionner comme la solution récursive: http://codegolf.stackexchange.com/questions/34662/find-a-route-between-two-wikipedia-articles – cat

Observe de près le mot find-path. Je vais ajouter des commentaires afin que vous puissiez voir ce qui est sur la pile:

: 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

Le if Combinator consomme le dernier élément de la pile de sorte que ce code ne peut éventuellement fonctionner. Voici le code de travail pour le mot 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

Jetez aussi un coup d'œil à la Wikipedia vocab qui est destiné à des tâches telles que celles-ci.

Source

2016-04-30 15:59:29

Effets de pile complexes récursifs?

Répondre

Questions connexes