Les évaluateurs optimaux sont-ils réellement optimaux?

10

Le terme suivant (en utilisant les index bruijn):

BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0)))))))))

Lorsqu'il est appliqué à un numéro d'église, il prend Nrapidement sa forme normale dans plusieurs évaluateurs existants, y compris des naïfs . Pourtant, si vous codez ce terme en réseaux d'interaction et l'évaluez en utilisant l'algorithme abstrait de Lamping, il faut un nombre exponentiel de réductions bêta par rapport à N. Sur Optlam, en particulier:

N   interactions(betas)     (BADTERM N)
1   129(72)                 λλλ(1 (2 (2 (2 (2 (2 (2 (2 0))))))))
2   437(205)                λλλ(2 (1 (2 (2 (2 (2 (2 (2 0))))))))
3   976(510)                λλλ(1 (1 (2 (2 (2 (2 (2 (2 0))))))))
4   1836(1080)              λλλ(2 (2 (1 (2 (2 (2 (2 (2 0))))))))
5   3448(2241)              λλλ(1 (2 (1 (2 (2 (2 (2 (2 0))))))))
6   6355(4537)              λλλ(2 (1 (1 (2 (2 (2 (2 (2 0))))))))
7   11888(9181)             λλλ(1 (1 (1 (2 (2 (2 (2 (2 0))))))))
8   22590(18388)            λλλ(2 (2 (2 (1 (2 (2 (2 (2 0))))))))
9   43833(36830)            λλλ(1 (2 (2 (1 (2 (2 (2 (2 0))))))))
10  85799(73666)            λλλ(2 (1 (2 (1 (2 (2 (2 (2 0))))))))
11  169287(147420)          λλλ(1 (1 (2 (1 (2 (2 (2 (2 0))))))))
12  335692(294885)          λλλ(2 (2 (1 (1 (2 (2 (2 (2 0))))))))
13  668091(589821)          λλλ(1 (2 (1 (1 (2 (2 (2 (2 0))))))))
14  1332241(1179619)        λλλ(2 (1 (1 (1 (2 (2 (2 (2 0))))))))
15  2659977(2359329)        λλλ(1 (1 (1 (1 (2 (2 (2 (2 0))))))))

Sur des évaluateurs similaires tels que BOHM, cela prend beaucoup moins d'étapes bêta, mais plus d'interactions. Si les évaluateurs optimaux sont optimaux, comment peuvent-ils évaluer les termes asymptotiquement plus lentement que les évaluateurs existants?

Ce lien a une explication sur l'origine du terme, ainsi qu'une implémentation de la même fonction qui se comporte à l'opposé, presque bizarrement: il devrait fonctionner en temps exponentiel - il fonctionne en temps exponentiel dans la plupart des évaluateurs - pourtant, optimal les évaluateurs le normalisent en temps linéaire!

cc.complexity-theory lambda-calculus interaction-nets MaiaVictor
la source

Réponses:

5

Efficacité d'Optlam

Je n'ai pas étudié les détails de BADTERM ni de la mise en œuvre de l'évaluateur optlam, mais je trouve assez étrange qu'optlam effectue un certain nombre d'interactions ß radicalement différentes d'un autre évaluateur optimal comme BOHM. Un tel nombre doit, par définition, être fondamentalement le même sur un terme donné. Êtes-vous sûr de la justesse du noyau d'Optlam?

Efficacité des évaluateurs optimaux

Rappelons que la notion d'optimalité de ces évaluateurs est plus correctement connue sous le nom d'optimalité de Lévy, et ce n'est pas la naïve, car une stratégie de réduction effectuant le nombre minimum de ß-étapes n'est pas calculable. Ce qui est minimisé, alors, c'est le nombre d'étapes de réduction ß parallèles effectuées sur toute une famille de redex, c'est-à-dire à peu près l'ensemble obtenu par la fermeture symétrique et transitive de la relation qui lie deux redex quand l'une est copiée de l'autre. Il ne devrait en général pas surprendre de voir des écarts entre le nombre d'étapes bêta et le reste des étapes de duplication, car nous savons que la majeure partie de la charge de normalisation pourrait être transférée de la première à la seconde, comme le montrent Asperti, Coppola et Martini [1].

Cela ne devrait pas nous surprendre non plus de voir que le nombre total d'interactions nécessaires pour normaliser un terme avec un évaluateur optimal est moins élevé qu'avec un évaluateur ordinaire, car l'observation empirique précédente a déjà montré des améliorations de performances notables. Malgré cela, un énorme saut de complexité, du temps exponentiel au temps linéaire, est peut-être le tout premier du genre à être découvert. (Je vais vérifier cela.)

D'un autre côté, les résultats théoriques sur l'efficacité de la réduction optimale (ce qui est votre grande question), sont encore peu nombreux et pas encore généraux, car ils sont limités aux réseaux de preuve de type EAL (qui est fondamentalement la même restriction de l'optmal évaluateur, si je comprends bien), mais tous sont légèrement positifs, car dans le pire des cas, la complexité de la réduction du partage est limitée par l'ordinaire par un facteur constant [2,3].

Références

  1. A. Asperti, P. Coppola et S. Martini, (Optimal) Duplication is not elementary recursive , Information and Computation, vol. 193, 2004.
  2. P. Baillot, P. Coppola et U. Dal Lago, Logiques légères et réduction optimale: exhaustivité et complexité , Information et calcul, vol. 209, non. 2, p. 118-142, 2011.
  3. S. Guerrini, T. Leventis et M. Solieri, Deep into optimality - complex and correctness of sharing implementation of bounded logics , DICE 2012, Tallin, Estonia, 2012.
Marco Solieri
la source
Such a number must be, by definition, basically the same on a given termDonc je pensais. Cela m'a surpris car Optlam donne le même nombre de bêtas que BOHM dans de nombreux cas, j'ai testé. Dans certains cas, il donne moins, cependant, en raison de sa stratégie d'appel par besoin. Quelqu'un m'a dit que la réduction sans l'oracle n'était pas vraiment optimale et maintenant je ne sais plus. Dans l'ensemble, je suis profondément confus. Mais non, il n'y a absolument aucune preuve qu'Optlam fonctionne correctement. Je pense au reste de votre commentaire - merci.
MaiaVictor
De plus, j'ai trouvé de nombreux termes différents qui se comportent exactement comme Badterm. J'étudie davantage le problème afin de trouver des termes plus simples qui le reproduisent.
MaiaVictor
Une sorte de stratégie parallèle d'appel par besoin est standard pour les évaluateurs optimaux, y compris BOHM, car elle est nécessaire pour l'optimalité de Lévy elle-même. L'oracle n'est pas strictement nécessaire pour réduire de manière optimale les termes λ: les termes stratifiés, tels que ceux de type EAL, n'en ont pas besoin.
Marco Solieri
Oh, ma mauvaise, alors. Quoi qu'il en soit, juste pour m'assurer que je le comprends, lorsque vous tenez compte de la duplication (pas seulement des bêtas), il peut y avoir des termes qui sont asymptotiquement plus lents à réduire sur les évaluateurs optimaux, même sur le cas de type EAL? Dans ce cas, je me demande pourquoi il est important de ne compter que les étapes bêta et s'il y a vraiment un avantage à utiliser des réseaux d'interaction à des fins de réduction du λ-calcul ...
MaiaVictor
1
Ah! Il existe donc des termes non typables EAL qui peuvent être réduits sans l'oracle? J'ai supposé que si Optlam le réduisait, il était typable EAL (puisque je n'ai pas d'inférenceur de type EAL). Si ce n'est pas le cas, alors tout a du sens maintenant. Étant donné que le sous-ensemble de termes typables EAL a suffisamment de puissance pour exprimer n'importe quel algorithme poly-temps comme le tri, je suppose qu'il serait sage d'essayer spécifiquement de concevoir des termes typables EAL. Je me demande cependant comment cela pourrait être fait dans la pratique. Merci beaucoup.
MaiaVictor