Implémentation de l'algorithme de SUBTYPEP de Baker

Auteurs

Leo Valais

Type

techreport

Année

2019

Numéro

1914

Résumé

Le langage Common Lisp fournit un prédicat, SUBTYPEPqui permet d'introspecter la relation de sous-typage. Dans certaines situations, étant donné le système de typage du langage, il est impossible de déterminer si un type est un sous-type d'un autre sans en énumérer tous les éléments, possiblement en nombre infini. À cause de cela, SUBTYPEP est autorisé à retourner deux valeurs (NIL, NIL), indiquant qu'il n'a pas pu trouver de réponse. Les implémentations de cette fonction ont trop souvent tendance à ne pas répondre, même dans des situations où c'est théoriquement possible. Ce comportement abusif peut alors empêcher certaines optimisations potentielles du compilateur, voire même rendre l'implémentation non conforme au standard. Dans son article og A Decision Procedure for Common Lisp's SUBTYPEP Predicate fg, Henry Baker propose un algorithme qu'il prétend plus précis et plus performant que l'implémentation moyenne de SUBTYPEP. Nous présentons ici l'état de notre implémentation de l'algorithme de Baker ainsi qu'une potentielle amélioration de celui-ci faisant usage des R-trees.