Kowalski, notazione di

Kowalski, notazione di

Kowalski, notazione di espressione con cui si indica la formula: algoritmo = logica + controllo. Tale formula esprime sinteticamente la teoria di R. Kowalski sugli algoritmi dei linguaggi di programmazione basati sulla logica. Secondo questa teoria ogni algoritmo si compone di una parte logica, che consiste nella specifica della struttura del problema e nei mezzi necessari per risolverlo, e di una parte di controllo, che indica i passi da compiere nel calcolo e quindi la strategia di risoluzione del problema stesso. La parte logica descrive l’obiettivo dell’algoritmo, mentre la parte di controllo ne determina l’efficienza; per questo motivo è possibile migliorare la funzionalità di un algoritmo modificandone la parte di controllo e lasciando inalterata la parte logica. Secondo Kowalski è auspicabile che, nella scrittura di un programma, la parte logica e la parte di controllo siano chiaramente distinte allo scopo di aumentarne la semplicità e di ottimizzarne l’implementazione. La componente logica di un programma è costituita dai dati e dalle relazioni logiche che intercorrono tra i dati stessi; la componente di controllo, invece, comprende le strutture di memoria in cui i dati vengono immagazzinati e resi accessibili all’occorrenza.

Per illustrare la distinzione fra componente logica e componente di controllo, Kowalski riporta l’esempio dell’algoritmo per il calcolo del fattoriale di un numero naturale n, indicato con il simbolo n!. In questo caso la componente logica consiste nella definizione di fattoriale assegnata attraverso le due regole seguenti:

• il fattoriale di 0 è 1: in simboli 0! = 1;

• il fattoriale di n + 1 è uguale al fattoriale di n moltiplicato per n + 1; in simboli (n + 1)! = n! ⋅ (n + 1).

Tale definizione può essere usata per calcolare il fattoriale di un numero con due metodi diversi, con il metodo top-down o con il metodo bottom-up. La scelta del metodo con cui utilizzare la definizione costituisce la componente di controllo dell’algoritmo. Il metodo top-down («dall’alto verso il basso») consiste nel ridurre la complessità del calcolo di (n + 1)! al calcolo di n!. Per esempio per calcolare 5! ci si riconduce al calcolo di 4! e lo si moltiplica per 5, allo stesso modo per calcolare 4! si passa al calcolo di 3! e poi si moltiplica per 4 e così via fino ad arrivare a 0!. In formule si ha:

Al contrario, nel metodo bottom-up («dal basso verso l’alto») il calcolo parte dagli elementi più semplici per arrivare via via a ottenere gli elementi più complessi. Per esempio per calcolare 5! si parte da 0! = 1 e si prosegue con 1! = 1, 2! = 2 … fino ad arrivare a 5! = 120. La stessa definizione di fattoriale può quindi essere usata in due modi differenti e ciascuno dei due dà origine a un differente algoritmo e quindi a una differente struttura di controllo: la procedura top-down dà origine a un algoritmo di tipo ricorsivo (→ calcolo ricorsivo); la procedura bottom-up a un algoritmo iterativo.

La distinzione fra logica e controllo è alla base dei linguaggi di programmazione logica (come per esempio il prolog) la cui caratteristica principale è quella di richiedere, nella risoluzione di un problema, la specifica di ciò che deve essere calcolato e non il modo in cui tale calcolo deve essere eseguito; nei linguaggi logici, infatti, il compito del programmatore si limita alla descrizione della parte logica mentre il controllo della computazione è affidato all’elaboratore.