È possibile scrivere un compilatore "Brainfuck with variables"?

Dipende se vuoi sostituire < e > con variabili o realmente aggiungere variabili alla lingua. Nel primo caso, probabilmente perdi la completezza di Turing (perché hai solo un numero finito di celle di memoria). Può rimanere Turing completo se ogni cella può contenere valori arbitrariamente grandi, ma sinceramente non ne sono sicuro.

Ad ogni modo, se non ci sono operazioni < e > , la traduzione è semplice: si conosce a quale variabile è stato accesso l'ultimo codice quindi è sufficiente confrontare gli indirizzi della variabile precedente e successiva. Solo i loop sono un po 'complicati, perché con codice come a+[b+] la cella corrente potrebbe essere a o b , sia nel corpo del ciclo che dopo la fine del ciclo. Una soluzione semplice consiste nel forzare tutti i percorsi a terminare sulla stessa cella, cioè a riscrivere il codice in a+[b+a] o a+b[b+] (che potrebbe essere semplificato in a+b[+] ).

Se la > e < rimangono disponibili nella tua lingua di origine, le cose sono più complicate. Come sottolinea un commento, Brainfuck è completo di Turing in modo da poter creare un programma equivalente con abbastanza complicazioni, ma una traduzione semplice ed efficiente potrebbe non essere sempre possibile. Determinare staticamente la cella corrente in un dato punto richiede generalmente la conoscenza del conteggio del trip di tutti i loop fino a quel punto. Anche ignorando la potenziale riduzione del problema dell'arresto (non sono convinto che ciò si applichi effettivamente qui), il conteggio del viaggio e quindi la posizione della memoria spesso dipende dall'input, cioè non può essere previsto staticamente nemmeno da una macchina Oracle. p>     

Va bene, per rispondere alla mia stessa domanda, è un modo per aggirare.

Tempo di compilazione e tempo di esecuzione

Il calcolo statico del numero di < è davvero impossibile, come suggerito da poche persone. A volte se il codice viene eseguito dipende da qualche input e non c'è modo di aggirare questo. Un esempio: ,[>]

Quindi l'unico modo per farlo è cercare le celle in fase di runtime. Se riesci a trovare l'inizio dello spazio di memoria (indirizzo 0), puoi semplicemente saltare 2 volte a destra per arrivare all'indirizzo 2.

Trovare uno zero è facile in Brainfuck: [<] # do something here

Tuttavia, non vuoi fermarti su una cella arbitraria che ha il valore 0 , devi assicurarti che sia l'effettivo inizio della memoria zero!

Questo è davvero scomodo. Indipendentemente dal valore con cui si sceglie di rappresentare l'indirizzo iniziale, questo potrebbe accidentalmente apparire nella memoria.

Dividere lo spazio di memoria

Quindi ho diviso la memoria in quello che chiamo spazio memoria e spazio valore . Le celle dispari sono valori, anche le celle sono "indirizzi". Beh, non ci sono esattamente numeri univoci che identificano le celle, ma più una "scala" che usi per muoverti.

Ecco il layout della memoria, dopo che è mappato:

memory = [0, 0, 1, 0, 1, 0 ...] start ^ ^ addr ^ value

Ora ogni volta che cerchi una posizione, vai a sinistra < una volta per entrare nello spazio degli indirizzi, quindi fai il loop fino a trovare uno zero, quindi sposta a destra n volte.

Questo schema richiede di riempire la memoria alternando 1 e 0 prima dell'esecuzione del programma. Data una dimensione di memoria fissa, il compilatore può generare codice che fa questo per te.

Questa soluzione non è perfetta. Per cominciare, perdi metà della memoria. Riempire con 1 è anche noioso e ti costa tempo all'inizio di ogni programma.

Appendice: segna l'inizio con un "1"

Potresti pensare: perché non invertire lo schema e contrassegnare l'indirizzo zero con 1 e lasciare che tutti gli altri indirizzi siano 0 ? In questo modo non è necessario riempire la memoria con 1 .

Proviamo.

Il codice di cui abbiamo bisogno, tradotto in parole sarebbe:

1. vai a sinistra di una cella per inserire lo spazio degli indirizzi
2. se il valore è 0, quindi sposta a sinistra 2 celle (continua a cercare)
3. else (hai raggiunto l'inizio) vai a destra N posti

Devi scrivere un costrutto if / then / else . In Brainfuck questo significa copiare alcuni valori in posizioni temporanee (ne abbiamo un sacco!), Quindi eseguire il ramo corretto, quindi ripulire.

Ma nel nostro caso "eseguire il codice" significa "andare in un altro posto e non tornare mai più" quindi è impossibile ripulire le variabili temporanee. E se non sono 0 non troverai di nuovo l'inizio.

Ho cercato di aggirare questo problema ma non ci sono riuscito.

Ecco il codice per il compilatore: link