Come calcolare il punto fisso su un reticolo del flusso di dati

Question

Chiedendosi la panoramica generale di come calcolare il punto fisso sul reticolo del flusso di dati di un programma.

Un punto fisso di una funzione $ f (x) $ è quello in cui l'output della funzione è uguale all'ingresso, quindi:

$$ f (x) = x $$

Dato $ f $ è una funzione di conservazione dell'ordine (monotonica) $ x ⊑ y destra f (x) ⊑ f (y) $, in questo presentazione, hanno $ x_ bot $ essere il punto meno fisso di $ f: da L a l $, quindi $ f (x_ bot) = x_ bot $, dove $ l $ è un reticolo del programma. Quindi dicono:

Ora, lascia $ x_0 = bot $ [la fine del reticolo] e $ x_i = f (x_ {i - 1}) $

• Per induzione, $ x_i ⊑ x_ bot $.
• Inoltre, la catena $ x_i $ è una catena ascendente.
• Se $ l $ non ha catene ascendenti infinite, prima o poi $ x_i = x_ {i+1} = x_ bot $

Mi chiedo cosa significhi. Cosa succede algoritmicamente (i passaggi di alto livello) quando stiamo ripetendo verso un punto fisso. Nella presentazione dicono "Eseguire il calcolo simulando l'esecuzione del programma fino a raggiungere il punto fisso".

Questo doc dice "In questa situazione [flusso di dati], la funzione matematica è la funzione di flusso Quindi $ f $], e il punto fisso è una tupla dei valori di analisi del flusso di dati in ciascun punto del programma (fino al loop)". Definiscono funzione di flusso come una mappa dalle informazioni sul flusso di dati immediatamente prima a Punto / istruzione del programma.

Quindi, essenzialmente, dividiamo il programma in nodi o punti in cui ogni punto è un'istruzione/dichiarazione. Creiamo una funzione che mostra la modifica dei valori da prima e dopo ogni punto (in e fuori, la funzione di flusso). Quindi iteamiamo in qualche modo sui valori, ecco dove non sono chiaro. Chiedendoci se stiamo iteterando i punti del programma, chiamando $ f $ per ogni punto o se rimaniamo ad un punto e citeriamo su di esso con una sorta di input fino a raggiungere un punto fisso. Quindi chiedendosi come funziona. Non sono sicuro di come funziona l'iterazione, o come funziona $ x_ bot $ (se la sua parte di un sottoinsieme dei punti del programma $ l $ per ogni punto (un po 'come un quartiere) o cosa.