[Python] un bel dilemma

[enrico franchi]

2015-07-29 13:09 GMT+01:00 Carlos Catucci <carlos.catucci a gmail.com>:

>
> Tu sei conscio che una certa fetta dei tuoi appassionati lettori a questo
> punto si e' persa da tempo? ;)
>

Ma no dai... basta fare passetti piccoli.

Stavamo parlando di come sarebbe Python se le funzioni non avessero il None
implicito. Da cui appunto si e' andato ad esplorare "gli altri come fanno",
per capire un po' lo spettro delle soluzioni. A questo punto siamo finiti
dentro un po' di type theory (il discorso sul fatto che null puo' essere
ficcato in tutti i reference type in Java). Ora null viene spesso associato
ad un concetto di type theory che e' bottom, il tipo che e' sottotipo di
tutti i tipi (e quindi se avesse un valore potresti assegnarlo a tutte le
variabili -- in quanto sottotipo --). In particolare bottom e' un tipo che
non puo' avere nessun valore: nessun entita' puo' avere effettivamente come
tipo bottom (questa e' la differenza con il null di Java e il motivo per
cui *non* e' bottom).

A cosa serve bottom? Immagina di volere dare il tipo ad un'espressione la
cui computazione non termina (perche' tipo che' il classico while 1). Ecco,
spesso si decide che il tipo di questa espressione e' bottom. Nota,
parliamo di tipi teorici, non necessariamente dei tipi dei linguaggi di
programmazione. Per intenderci, dal punto di vista della type theory,
Python ha un unico tipo "universale" (che cattura il fatto che in una
variabile ficchi quello che ti pare). Sono tipi *statici*. Se vuoi tipi
delle variabili, non degli oggetti.

A questo punto Nadir ha fatto alcune note su funzioni parziali e totali.
Essenzialmente una funzione totale quando la valuti ha *sempre* un valore
(e quindi termina sempre). Le funzioni parziali non hanno questa proprieta'
(per vari motivi, ma qui diventa complicato). Il collegamento e' che ci
eravamo messi a parlare di computazioni che non terminano discutendo di
bottom.

Piu' in dettaglio, ci sono alcuni "assiomi" e alcune "regole" che ti
consentono di costruire una classe di funzioni note come "primitive
ricorsive". Che sono quelli la sopra. Che so... la somma appartiene a
questa categoria. Se si ha a disposizione un linguaggio funzionale, e'
relativamente istruttivo implementarsele. Non ha un'utilita' pratica
enorme, ma e' un ottimo esercizio per padroneggiare la ricorsione.

L'insieme delle funzioni primitive ricorsive e' un insieme relativamente
piccolo rispetto a quello che puoi calcolare. Ci sono tante funzioni
"interessanti" che non appartengono a quell'insieme. In particolare, un
computer calcola "piu' cose". L'insieme delle funzioni che un computer puo'
calcolare e' appunto quello delle funzioni mu-ricorsive, altrimenti dette
intuitivamente calcolabili. Tutto questo e' interessante perche', per
esempio, non puoi "calcolare" se una generica funzione mu-ricorsiva termina
su un dato input. Scusa... quella non e' la parte interessante... la parte
interessante e' che ogni programma per computer implementa una determinata
funzione mu-ricorsiva. Di conseguenza, non puoi costruire una procedura
automatica che ti dice se un programma termina (o se contiene varie classi
di bachi).

Nota, il risultato e' molto piu' forte di un risultato come "non sappiamo
scrivere un computer che fa $X". Questo risultato dice "non e' possibile
scrivere un programma che fa sta roba".

Dopo di che' e' arrivato Maker che ha lanciato la bomba e direi che ci
siamo...

-- 
.
..: -enrico-
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://lists.python.it/pipermail/python/attachments/20150729/2d5b92cf/attachment.html>