Corretto per la progettazione del ciclo

2

Qual è il design corretto per un ciclo for ?

Felix attualmente usa

if len a > 0 do
  for var i in 0 upto len a - 1 do 
    println a.[i]; 
  done
done

che include il limite superiore. Questo è necessario per supportare l'intera gamma di valori di un tipo intero tipico. Tuttavia il ciclo for mostrato non supporta array di lunghezza zero, quindi il test speciale, né la sottrazione di 1 funziona in modo convincente se la lunghezza dell'array è uguale al numero di numeri interi. (Dico in modo convincente perché potrebbe essere che 0 - 1 = maxval: questo è vero in C per unsigned int, ma sei sicuro che sia vero per unsigned char senza riflettere attentamente sulle promozioni integrali?)

L'effettiva implementazione del ciclo for dal mio compilatore gestisce correttamente 0 ma questo richiede due test per implementare il ciclo:

continue:
  if not (i <= bound) goto break
  body
  if i == bound goto break
  ++i
  goto continue
break:

Getta il controllo dello zero codificato a mano nell'esempio dell'array e sono necessari tre test.

Se il ciclo fosse esclusivo, gestirà lo zero correttamente, evitando il test speciale, ma non ci sarebbe modo di esprimere il limite superiore di un array con la dimensione massima.

Nota il modo C di fare questo:

for(i=0; predicate(i); increment(i))

ha lo stesso problema. Il predicato viene testato dopo l'incremento, ma l'incremento di terminazione non è universalmente valido!

Esiste un argomento generale secondo cui un semplice ciclo esclusivo è sufficiente: promuovere l'indice su un tipo grande per impedire l'overflow e presumere che nessuno eseguirà mai il ciclo fino al valore massimo di questo tipo .. ma non ne sono del tutto convinto : se hai promosso a C's size_t e fatto il loop dal secondo valore più grande al più grande otterresti un ciclo infinito!

    
posta Yttrill 12.12.2011 - 14:38
fonte

5 risposte

1

Hai dimenticato di menzionare che le tue variabili di stringa in Felix iniziano con l'indice 0 o 1. Cercando ciò nel web, il suo lavoro aggiuntivo per i lettori. E influenza il modo in cui viene valutato il tuo esempio.

In ogni caso. Sei sicuro che:

for(i=0; predicate(i); increment(i))

In C: "Il predicato viene testato dopo l'incremento, ma l'incremento finale non è universalmente valido!"

Trasparenti a questo:

i=0
continue:
  body
  increment(i)
  if not predicate(i) goto break
  goto continue
break:

Al posto di questo:

continue:
  i=0
  if not predicate(i) goto break
  body
  increment(i)
  goto continue
break:

Poiché il tuo ciclo per è più specifico come pascal, puoi considerare come deve essere tradotto e valutato nel caso in cui il valore dell'indice sia uguale o inferiore al valore iniziale.

Solitamente, se il valore iniziale e il valore finale sono gli stessi, il ciclo viene eseguito una volta, se il valore finale è maggiore del valore iniziale, il ciclo non viene eseguito.

    
risposta data 27.01.2012 - 04:56
fonte
0

In C sarebbe per (int i = 0; i < (len a); i ++) {}. Questo non eseguirà alcuna iterazione poiché 0 non è < 0 (i < (len a)).

Se intendi utilizzare un unsigned allora sì, devi circondarlo con il controllo delle condizioni.

Ha un elemento for nella funzione di tipo array {}?

Se è considerato funzionale, c'è un modo per farlo con la ricorsione.

    
risposta data 12.12.2011 - 15:09
fonte
0

Felix supporta break / continue? L'implementazione corretta potrebbe influire sul modo in cui ti avvicini alle cose.

Il mio approccio con C dovrebbe iniziare così:

for (int i = 0; i < len (a); i ++) {     // fare cose   }

Come hai notato, questo si rompe quando colpisce il limite int. Una possibile risposta è controllare prima dell'incremento, quindi evitiamo gli incrementi che superano, ma abbiamo bisogno di controllare prima dell'incremento, perché se len(a) == 0 , non vogliamo eseguire il corpo. Il seguente risolve il problema:

id: for (int i = 0; i < len (a); i ++) {     // fare cose     se (i == len (a) - 1) {       rompere l'id;     }   }

, dove id è un'etichetta univoca. Tuttavia questo è inefficiente, perché il controllo per è ridondante per tutte le iterazioni tranne il primo. A questo punto, si è tentati di utilizzare un ciclo while, ma si noti che un ciclo C for non è esattamente equivalente a un ciclo while, poiché break / continua funzionano in modo diverso (in base all'esecuzione dell'incremento).

la trasformazione più semplice che io possa pensare conservi queste semantiche

if (len (a) > 0) {     id: for (int i = 0;; i ++) {       // fare cose       se (i == len (a) - 1) {         rompere l'id;       }     }   }

    
risposta data 12.12.2011 - 19:47
fonte
0

Il tuo ultimo paragrafo non ha molto senso per me. Se in primo luogo si utilizza un int firmato, si presuppone che il limite di ciclo superiore più grande possibile sia il valore int con segno positivo più elevato. Se si utilizza un tipo più grande per il ciclo, non si verificherà un overflow. Se potrebbe esserci un overflow, quindi con un limite superiore del loop superiore al massimo del valore int con segno positivo positivo, che invalida l'ipotesi iniziale.

Inoltre, non dare per scontato che nessuno farà mai questo o quello. Se sei in dubbio per un ciclo specifico, prova a farlo ed esprimi esplicitamente ciò che presumi qui.

assert(UINT_MAX > INT_MAX);

if ((unsigned int)len(a) <= INT_MAX) {
    for (unsigned int i = 0; i < len(a); i++)
}
else {
    Handle an unexpected situation here.
}

EDIT (un po 'troppo lungo per un commento al tuo commento):

Forse stai guardando il problema dalla direzione sbagliata? Si noti che C for loop non è esclusivo di per sé. È spesso usato in questo modo a causa dell'indicizzazione dell'array a 0. Nulla ti impedisce di utilizzarlo inclusivo:

for (i = 0; i <= len(a)-1; i++)

Infatti, quasi tutte le espressioni possono essere usate per le tre parti, perché è più zucchero sintattico del suo stesso comando, quindi puoi anche usarlo per scorrere attraverso un elenco collegato:

for (p = start; p != NULL; p = p->next)

Quindi potresti prima definire cosa ti aspetti dai tuoi cicli for? Dovrebbero essere strettamente legati alle operazioni numeriche? Quindi potreste anche fornire loro "crescenti" intarsi che non si sovrappongono mai e vengono scalati automaticamente su bigints, in base alle esigenze. Oppure puoi definire che 0-1 è sempre considerato come -1, quindi hai for i in 0 upto -1 che non verrà eseguito affatto e ti farà risparmiare il controllo aggiuntivo per 0.

Qual è lo scopo della tua lingua? C'è davvero bisogno che io come programmatore mi interessi dei tipi esatti usati nel ciclo for?

    
risposta data 12.12.2011 - 21:03
fonte
0

C infatti non ha lo stesso problema. Il ciclo C for non esegue la fase di iterazione prima di controllare il predicato. Vedere la sezione 6.8.5.3 dello standard ISO C, che lo dichiara chiaramente.

L'argomento sulla promozione a cui ti stai riferendo è come dici tu, errato, ma per una ragione più diretta: potrebbe non esserci una promozione allargata. Ad esempio, nulla nello standard C garantisce che esista un tipo più ampio di unsigned char (vale a dire, sono consentite implementazioni in cui tutti i tipi non firmati hanno la stessa larghezza).

    
risposta data 12.05.2012 - 00:47
fonte

Leggi altre domande sui tag