Comment calculer le point fixe sur un réseau de flux de données

Question

Vous vous demandez la vue d'ensemble générale de la façon de calculer le point fixe sur le réseau de flux de données d'un programme.

Un point fixe d'une fonction $ f (x) $ est celui où la sortie de la fonction est égale à l'entrée, donc:

$$ f (x) = x $$

Étant donné que $ f $ est une fonction de préservation de la commande (monotonique) $ x ⊑ y rightarrow f (x) ⊑ f (y) $, dans ce présentation, ils ont $ x_ bot $ le point le moins fixe de $ f: l à l $, donc $ f (x_ bot) = x_ bot $, où $ l $ est un réseau de programme. Ensuite, ils disent:

Maintenant, laissez $ x_0 = bot $ [la fin du réseau] et $ x_i = f (x_ {i - 1}) $

• Par induction, $ x_i ⊑ x_ bot $.
• De plus, la chaîne $ x_i $ est une chaîne ascendante.
• Si $ l $ n'a pas de chaînes ascendantes infinies, tôt ou tard $ x_i = x_ {i + 1} = x_ bot $

Je me demande ce que cela signifie. Ce qui se passe algorithmiquement (les étapes de haut niveau) lorsque nous itons vers un point fixe. Dans la présentation, ils disent "Faire le calcul en simulant l'exécution du programme jusqu'à atteindre le point fixe".

Ce doc dit "Dans cette situation [flux de données], la fonction mathématique est la fonction de flux donc $ f $], et le point fixe est un tuple des valeurs d'analyse du flux de données à chaque point du programme (jusqu'à et y compris la boucle)". Ils définissent fonction de flux comme carte des informations de flux de données immédiatement avant le Point de programme / instruction.

Donc, essentiellement, nous divisons le programme en nœuds ou points où chaque point est une instruction / instruction. Nous créons une fonction montrant le changement de valeurs de avant et après chaque point (dans et dehors, la fonction d'écoulement). Nous itons ensuite sur les valeurs d'une manière ou d'une autre, c'est là que je ne suis pas clair. Vous vous demandez si nous itons à travers les points du programme, appelant $ f $ pour chaque point, ou si nous restons à un moment donné et itérons dessus avec une sorte d'entrée jusqu'à ce que nous atteignions un point fixe. Puis se demande comment cela fonctionne. Je ne sais pas comment fonctionne l'itération, ou comment fonctionne $ x_ bot $ (si sa partie d'un sous-ensemble du programme pointe $ l $ pour chaque point (un peu comme un quartier) ou quoi.