Quels sont exactement redexes administratives après la conversion CPS?

Question

Dans le cadre du schéma et CPS conversion, je vais avoir un peu du mal à décider ce que administrative redexes (lambdas) exactement sont:

• tous les expressions lambda qui sont introduites par la conversion CPS
• uniquement les expressions lambda qui sont introduites par la conversion CPS, mais vous ne l'auriez pas écrit si vous avez fait la conversion « à la main » ou par l'intermédiaire d'un CPS-convertisseur intelligent

Si possible, une bonne référence serait la bienvenue.

Answer 1

Redex signifie « expression réductibles », qui est une expression qui n'est pas une valeur. Par conséquent, un lambda n'est pas un Redex, mais un appel est.
Dans CPS, une redex administrative est un redex dont l'opérateur est un lambda de continuation. Ces redexes peuvent être réduits immédiatement parce que vous savez que la fonction que vous appelez.
Par exemple, ((lambda (u) ...) foo) est un redex administratif, mais (k foo) n'est pas.

Answer 2

Je pense avoir trouvé ma réponse. ( Modifier. J'ai accepté la réponse de dimvar à la place, il est plus court et plus correct)

En supposant que le programme d'entrée ne sont pas entièrement CPS, au moins un point de retour procédure devra être convertie en continuation par la conversion CPS. Donc, cette suite est à la fois introduite par la conversion et nécessaires. Parce qu'il est nécessaire, vous avez toujours besoin de le faire, aussi lors de la conversion à la main par exemple. Par conséquent, redexes administratives ne sont que les lambdas introduites par la conversion CPS qui ne sont pas vraiment nécessaires (ma deuxième définition).

J'ai trouvé un papier qui explique comme celui-ci (Souligné par l'auteur):

  

naïf λ-encodage dans CPS,   cependant, génère un assez impressionnant   in fl ation de lambdas, plus dont   former redexes administratives qui peuvent   être réduite en toute sécurité. Administratif   réductions donnent termes CPS   correspondant à ce que l'on pourrait écrire   par la main. Il est donc devenu un   défi d'éliminer autant   redexes administratives que possible, à   temps CPS-transformation.

Pourtant, des remarques ou suggestions sont les bienvenus, bien sûr.