Cos'è la supercompilazione?

Question

Breve e dolce: ho visto diverse fonti parlare di "supercompilazione". Ma devo ancora trovare un unico documento in qualsiasi punto della faccia di Internet che descrive che cosa è. Presumibilmente perché sembra abbastanza semplice a chiunque non valga la pena di spiegare.

Qualcuno sa che cosa è in realtà?

Answer 1

La supercompilazione può essere affrontata come una generalizzazione della valutazione parziale. L'idea alla base della valutazione parziale è che molte parti di un programma possono essere valutate in fase di compilazione, e così dovrebbe essere. La supercompilazione estende questo, valutando cose che non possono essere completate in fase di compilazione, come trasformare map f (map g xs) in map (f . g) xs senza nulla oltre la definizione di map (Almeno penso di aver ottenuto una valutazione parziale giusta - Ho letto solo molto sulla supercompilazione).

Un altro modo per vederlo è come una combinazione di molte altre ottimizzazioni, come la deforestazione, la specializzazione e l'inlining. Agendo come se conoscesse già gli input per le funzioni e valutando, può ottenere un metodo più diretto per calcolare il risultato - può sbarazzarsi delle strutture dati intermedie vedendo come verranno utilizzate o può collegare tutti i valori possibili e quindi avvolgere il risultato in un case o fare qualcos'altro con i suoi valori di finto.

Max Bolingbroke ha un numero di documenti utili sull'argomento - Raccomando il primo, Supercompilation by Evaluation, come introduzione. La Sezione 2 introduce l'argomento con l'esempio e il resto, anche se un po 'difficile da ottenere, è molto informativo sul processo. Neil Mitchell ha anche un number of good presentations che lo descrive.

Spero che questo aiuti.

Answer 2

Da Wikipedia on Metacompilation:

Metacompilation è un calcolo che coinvolge transizioni MetaSystem (MST) da una macchina di calcolo M ad un MetaMachine M' che controlla, analizza e imita il lavoro di M. basa sulla semantica la trasformazione del programma , come la valutazione parziale e la supercompilazione (SCP), è metacomputation.

Maggiori informazioni su Metasystems on Wikipedia.

Non sono a conoscenza dell'argomento, ma darò la mia comprensione della descrizione. Supponiamo di avere un semplice programma in grado di copiare lo stdin in stdout. Questa sarebbe la nostra macchina informatica M. La nostra metamachina M 'è un secondo programma che prende la sorgente di M come input (o è altrimenti costruito per inerentemente conoscere M) ed è quindi in grado di capire non solo cosa fa M, ma come lo fa.

Se la mia comprensione è corretta, allora la domanda ovvia è perché ci importa di M? Ciò che mi viene in mente sono le ottimizzazioni automatiche. Se riusciamo a capire sia il modo in cui M lavora e ciò che M sta cercando di realizzare, M 'può risolvere modi per migliorare il funzionamento di M, nello spazio o nel tempo. Inoltre, e soprattutto, M 'può sostituire M dal momento che M' può compiere qualsiasi cosa abbia fatto M. Ciò significa che M '' può migliorare i modi con cui M 'ottimizza M, e successivamente sostituisce M', e così via.