Perché le funzioni in Ocaml/F # non sono ricorsive di default?

Question

Perché le funzioni in F # e in Ocaml (e probabilmente in altre lingue) non sono di default ricorsive?

In altre parole, perché i progettisti di linguaggi decidere che fosse una buona idea per fare in modo esplicito si digita rec in una dichiarazione del tipo:

let rec foo ... = ... 

e non dare la funzione ricorsiva funzionalità di default? Perché la necessità di un costrutto esplicito rec?

Answer 1

I discendenti francesi e britannici dell'originale ML fatto scelte diverse e le loro scelte sono state ereditate nel corso dei decenni per le varianti moderne. Quindi questo è solo legacy, ma influenza gli idiomi in queste lingue.

Le funzioni non sono ricorsive per impostazione predefinita nella famiglia di lingue CAML francese (incluso OCaml). Questa scelta facilita il superamento delle definizioni di funzioni (e variabili) usando let in quelle lingue perché è possibile fare riferimento alla definizione precedente all'interno del corpo di una nuova definizione. F # ha ereditato questa sintassi da OCaml.

Ad esempio, sostituiscono la funzione p quando si calcola l'entropia di Shannon di una sequenza in OCaml:

let shannon fold p = 
    let p x = p x *. log(p x) /. log 2.0 in 
    let p t x = t +. p x in 
    -. fold p 0.0 

Si noti come l'argomento p al ordine superiore shannon funzione viene soppiantata da un'altra p nella prima riga del corpo e poi un altro p nella seconda riga del corpo.

Al contrario, il ramo SML britannico della famiglia di lingue ML ha preso l'altra scelta e le funzioni di SML fun -bound sono ricorsive per impostazione predefinita. Quando la maggior parte delle definizioni di funzioni non ha bisogno di accedere ai bind precedenti del loro nome di funzione, ciò si traduce in un codice più semplice.Tuttavia, le funzioni sostituite vengono utilizzate per utilizzare nomi diversi (f1, f2 ecc.) Che inquinano l'ambito e consentono di invocare accidentalmente la "versione" errata di una funzione. E ora c'è una discrepanza tra le funzioni implicite-ricorsive fun -bound e le funzioni non ricorsive val -bound.

Haskell consente di dedurre le dipendenze tra definizioni limitandole a essere puri. Ciò rende i campioni di giocattoli più semplici ma a un costo grave altrove.

Si noti che le risposte fornite da Ganesh e Eddie sono false. Hanno spiegato perché gruppi di funzioni non possono essere collocati all'interno di un gigante let rec ... and ... perché influisce quando le variabili di tipo vengono generalizzate. Questo non ha nulla a che fare con rec di default in SML ma non in OCaml.

Answer 2

alcune ipotesi:

• let non solo è utilizzato per legare le funzioni, ma anche altri valori normali. La maggior parte delle forme di valori non possono essere ricorsive. Alcune forme di valori ricorsivi sono consentite (ad es. Funzioni, espressioni pigro, ecc.), Quindi è necessaria una sintassi esplicita per indicarlo.
• Potrebbe essere più facile ottimizzare le funzioni non ricorsive
• La chiusura creata quando si crea una funzione ricorsiva deve includere una voce che punta alla funzione stessa (in modo che la funzione possa chiamare in modo ricorsivo), che rende le chiusure ricorsive più complicato delle chiusure non ricorsive. Quindi potrebbe essere bello essere in grado di creare chiusure non ricorsive più semplici quando non si ha bisogno di ricorsione
• Permette di definire una funzione in termini di una funzione o di un valore con lo stesso nome precedentemente definiti; anche se penso che questa sia una pessima pratica
• Extra sicurezza? Fa in modo che tu stia facendo ciò che volevi. per esempio. Se non intendi che sia ricorsivo ma hai accidentalmente usato un nome all'interno della funzione con lo stesso nome della funzione stessa, molto probabilmente si lamenterà (a meno che il nome non sia stato definito prima)
• Il costrutto let è simile al costrutto let in Lisp e Scheme; che non sono ricorsivi. V'è un separato letrec costrutto nello Schema per Let ricorsiva

Answer 3

Ci sono due ragioni principali questa è una buona idea:

In primo luogo, se si attiva definizioni ricorsive allora non si può fare riferimento a un precedente vincolante di un valore con lo stesso nome. Questo è spesso un utile idioma quando stai facendo qualcosa come estendere un modulo esistente.

In secondo luogo, i valori ricorsivi e, in particolare, i set di valori reciprocamente ricorsivi, sono molto più difficili da ragionare in merito a definizioni che procedono in ordine, ogni nuova definizione che si basa su ciò che è già stato definito. È bello leggere questo codice per avere la garanzia che, salvo definizioni esplicitamente contrassegnate come ricorsive, le nuove definizioni possono riferirsi solo a definizioni precedenti.

Answer 4

Una ragione fondamentale per l'uso esplicito di rec ha a che fare con l'inferenza di tipo Hindley-Milner, che è alla base di tutti i linguaggi di programmazione funzionale tipizzati in modo statico (anche se modificati ed estesi in vari modi).

Se si dispone di una definizione let f x = x, ci si aspetta che abbia il tipo 'a -> 'a e che sia applicabile a diversi tipi 'a in diversi punti. Allo stesso modo, se scrivi let g x = (x + 1) + ..., ti aspetteresti che lo x sia trattato come int nel resto del corpo di g.

Il modo in cui le offerte di inferenza Hindley-Milner con questa distinzione è attraverso un esplicito generalizzazione passo. A determinati punti durante l'elaborazione del programma, il sistema di tipi si interrompe e dice "ok, i tipi di queste definizioni saranno generalizzati a questo punto, così che quando qualcuno li usa, qualsiasi variabile di tipo libero nel suo tipo sarà appena istanziata, e quindi non interferirà con altri usi di questa definizione. "

Si scopre che il luogo sensato per fare questa generalizzazione è dopo aver controllato un insieme di funzioni reciprocamente ricorsive. Qualsiasi prima, e generalizzerete troppo, portando a situazioni in cui i tipi potrebbero effettivamente scontrarsi. Più tardi, e generalizzerete troppo poco, creando definizioni che non possono essere usate con istanze multiple di tipi.

Quindi, dato che il correttore di tipi deve sapere quali serie di definizioni sono reciprocamente ricorsive, che cosa può fare? Una possibilità è semplicemente fare un'analisi di dipendenza su tutte le definizioni in un ambito e riordinarle nei gruppi più piccoli possibili. Haskell lo fa in realtà, ma in linguaggi come F # (e OCaml e SML) che hanno effetti collaterali illimitati, questa è una cattiva idea perché potrebbe riordinare anche gli effetti collaterali. Così, invece, chiede all'utente di contrassegnare esplicitamente quali definizioni sono reciprocamente ricorsive, e quindi per estensione dove dovrebbe avvenire la generalizzazione.

Answer 5

Una gran parte di esso è che dà al programmatore un maggiore controllo sulla complessità dei propri ambiti locali. Lo spettro di let, let* e let rec offre un livello crescente di potenza e costi. let* e let rec sono essenzialmente versioni annidate del semplice let, quindi l'utilizzo di uno dei due è più costoso. Questa valutazione ti consente di eseguire l'ottimizzazione del tuo programma tramite microgestione, in quanto puoi scegliere il livello di cui hai bisogno per il compito da svolgere. Se non hai bisogno di ricorsione o la possibilità di fare riferimento alle associazioni precedenti, puoi ricorrere a una semplice let per risparmiare un po 'di prestazioni.

È simile ai predicati di uguaglianza graduata in Schema. (Vale a dire eq?, eqv? e equal?)

Answer 6

Dato questo:

let f x = ... and g y = ...;; 

Confronta:

let f a = f (g a) 

Con questo:

let rec f a = f (g a) 

Gli ex ridefinisce f di applicare precedentemente definito f al risultato dell'applicazione g a a. Quest'ultimo ridefinisce lo f in modo continuo applicando g a a, che di solito non è quello che si desidera nelle varianti ML.

Detto questo, si tratta di uno stile di stile del linguaggio. Vai e basta.