combinatore

combinatore

combinatore in logica, funzione che trasforma una data sequenza di simboli, che appartengono a un linguaggio formale, in un’altra sequenza. Per esempio, in un linguaggio formale contenente le variabili x, y, z, ... e le parentesi ( , ) si definisce il combinatore S che agisce sulla sequenza di simboli xyz nel modo seguente: Sxyz = xz(yz). Lo scopo delle manipolazioni di simboli operate dai combinatori è quello di rappresentare formalmente il procedimento di calcolo di una funzione (→ algoritmo). In particolare, nel λ-calcolo (→ lambda-calcolo), un combinatore è una formula in forma normale che non contiene occorrenze libere di variabili.

Esempi di combinatori sono:

• il combinatore identità, che ha la forma seguente: I ≡ λxx; esso viene detto «combinatore identità» perché applicandolo a una qualsiasi formula A si ottiene la formula stessa, ovvero: A ≡ (λxx)A → A (qui e nelle altre esemplificazioni la freccia indica la conversione);

• il combinatore cancellatore: K ≡ λxyx il quale, data una coppia di formule A e B, cancella la seconda, ovvero: KAB ≡ (λxyx)AB → A;

• il combinatore nullo: 0 ≡ λxyy il quale, data una coppia di formule A e B, cancella la prima, ovvero: 0AB ≡ (λxyy)AB → B.

L’importanza dei combinatori risiede nel fatto che essi sono alla base dei linguaggi di programmazione, in particolare dei linguaggi funzionali come il lisp.