Το προφίλ μας στο Google Plus
0

Brainf*ck [μέρος 2ο]

Το να εφευρίσκει κανείς τον τροχό, ξανά και ξανά, είναι τις περισσότερες φορές κουραστικό και αντιπαραγωγικό. Μερικές φορές όμως μπορεί να γίνει συναρπαστικό. Συνεχίζοντας τη μύηση στον κόσμο Brainfuck, θα προχωρήσουμε σ’ ορισμένα πιο σύνθετα ζητήματα: Θα υλοποιήσουμε τους τελεστές και τις δομές ελέγχου που υπάρχουν σε όλες τις “φυσιολογικές” γλώσσες προγραμματισμού.

Στο προηγούμενο άρθρο, για την υλοποίηση του “Hello World!” χρησιμοποιήσαμε τις εντολές μετακίνησης του δείκτη. Παρά τη γενική σύγχυση που μπορεί να προκαλέσει η εκτεταμένη χρήση των συγκεκριμένων εντολών, η λειτουργία τους γίνεται εύκολα κατανοητή. Με λίγη προσοχή και άλλη τόση υπομονή, είναι εύκολο να παρακολουθήσει κανείς τις μεταβολές του δείκτη και, κατ’ επέκταση, το πώς τροποποιούνται τα δεδομένα της μνήμης. Τώρα που πήραμε μια πρώτη γεύση από το χειρισμό του δείκτη, μπορούμε να εξετάσουμε πιο προχωρημένες τεχνικές. Μη φαντάζεστε τεχνικές σχεδίασης γραφικών και σχηματισμού σκιών. Μιλάμε για τις απλές πράξεις και τις βασικές δομές ελέγχου. Μην ξεχνάτε άλλωστε ότι η Brainfuck δεν πήρε τυχαία το όνομά της.

Αντιγραφή τιμών
Πρώτα απ’ όλα θα δούμε πώς μπορούμε να αντιγράψουμε την τιμή ενός κελιού σε ένα άλλο. Χρησιμοποιώντας την κλασική ορολογία, θα δούμε πώς μπορούμε να εκχωρήσουμε την τιμή μιας μεταβλητής σε μια άλλη. Στην PHP, για παράδειγμα, θα δίναμε κάτι τέτοιο:

$my_variable_A = $my_variable_B;

Για να πετύχουμε κάτι τέτοιο στην Brainfuck πρέπει να χρησιμοποιήσουμε ένα βοηθητικό κελί. Συνολικά δηλαδή θα χρειαστούμε τρία κελιά: ένα για κάθε μεταβλητή και το βοηθητικό. Ας υποθέσουμε ότι η τιμή που θέλουμε να αντιγράψουμε βρίσκεται στο κελί 0 και ας δούμε τον κώδικα που δημιουργεί ένα αντίγραφο αυτής της τιμής:

+++++  Τιμή προς αντιγραφή (π.χ. το 5)
[      Έναρξη βρόχου
   >+     Μετάβαση στο κελί 1 και αύξηση της τιμής
   >+     Μετάβαση στο κελί 2 και αύξηση της τιμής
   <<-    Επιστροφή σε κελί 0 και μείωση τιμής
]           Επανάληψη μέχρι να μηδενιστεί το κελί 0
>>     Μετάβαση στο κελί 2
[      Έναρξη βρόχου
   -      Μείωση τιμής κελιού 2
   <<+    Μετάβαση στο κελί 0 και αύξηση της τιμής
   >>     Επιστροφή σε κελί 2
]      Επανάληψη μέχρι να μηδενιστεί το κελί 2

Αρχικά αντιγράψαμε την τιμή του κελιού 0 στα κελιά 2 και 3, αλλά την ίδια στιγμή, μηδενίσαμε το κελί 0. Έτσι, ολοκληρώσαμε την αντιγραφή μεταφέροντας την τιμή του κελιού 2 στο κελί 0. Όπως καταλαβαίνετε, το κελί 1 αποτέλεσε τον προορισμό της αντιγραφής, ενώ το κελί 2 ήταν το βοηθητικό. Αν απομακρύνουμε τα σχόλια, ο κώδικας της αντιγραφής παίρνει την ακόλουθη μορφή:

+++++[>+>+<<-]>>[-<<+>>]

Αριθμητικές πράξεις
Σε ένα οποιοδήποτε πρόγραμμα, εκτός από το να αποθηκεύουμε τιμές σε διάφορες μεταβλητές, θέλουμε να κάνουμε και πράξεις. Αυτός είναι άλλωστε και ο λόγος για τον οποίο αποθηκεύουμε τις τιμές. Ας ξεκινήσουμε με την πρόσθεση, που στην PHP γίνεται με τον εξής απλούστατο τρόπο:

$a = $a + $b ;
// ή ισοδύναμα...
$a += $b ;

Στην Brainfuck, όπως υποψιάζεστε, αυτή η τόσο απλή πράξη απαιτεί λίγο παραπάνω κόπο. Θα επιστρατεύσουμε και πάλι ένα βοηθητικό κελί (το 2) και θα προσθέσουμε την τιμή του κελιού 1 σε αυτήν του κελιού 0. Απολαύστε τον κώδικα:

+++    Τιμή στην οποία θα προστεθεί το κελί 1
>++    Κελί 1: Τιμή που θα προστεθεί στο κελί 0
[      Έναρξη βρόχου
   &lt;+     Μετάβαση στο κελί 0 και αύξηση τιμής
   &gt;&gt;+    Μετάβαση στο κελί 2 και αύξηση τιμής
   &lt;-     Μετάβαση στο κελί 1 και μείωση τιμής
]      Επανάληψη μέχρι να μηδενιστεί το κελί 1
>      Μετάβαση στο κελί 2
[      Έναρξη βρόχου
   -      Μείωση τιμής κελιού 2
   &lt;+     Μετάβαση στο κελί 1 και αύξηση τιμής
   &gt;      Μετάβαση στο κελί 2
]      Επανάληψη μέχρι να μηδενιστεί το κελί 2

Δείτε τον κώδικα χωρίς τα περιττά (!;) σχόλια:

+++>++[<+>>+<-]>[-<+>]

Όπως διαπιστώσατε, για να προσθέσουμε την τιμή του κελιού 1 σε αυτήν του κελιού 0, υποχρεωθήκαμε να μηδενίσουμε το κελί 1. Ακριβώς γι’ αυτό, φροντίσαμε να αντιγράψουμε την τιμή του στο βοηθητικό κελί 2. Φυσικά, στο τέλος δεν παραλείψαμε να πραγματοποιήσουμε και την αντίστροφη μεταφορά (από το κελί 2 στο κελί 1).

Η αφαίρεση υλοποιείται με τον ίδιο μηχανισμό. Αν υποθέσουμε ότι το κελί 0 είναι ο αφαιρετέος και το κελί 1 είναι ο αφαιρέτης (keli0 = keli0 – keli1), επαναλαμβάνουμε τον κώδικα που είδαμε προηγουμένως και σε κάθε επανάληψη του πρώτου βρόχου, αντί να αυξάνουμε την τιμή του κελιού 0 τη μειώνουμε. Τον πολλαπλασιασμό τον έχουμε μελετήσει ήδη. Αναρωτιέστε πότε; Μα, όταν παρουσιάσαμε το “Hello World!”. Εν ολίγοις, ο πολλαπλασιασμός επιτυγχάνεται με την επανάληψη των απαιτούμενων αυξήσεων.

Έλεγχος αν…
Εκτός από τους βασικούς αριθμητικούς τελεστές, η Brainfuck στερείται και κάποιων μηχανισμών που δεν απουσιάζουν από καμία άλλη γλώσσα. Τι γίνεται, ας πούμε, με τη δομή switch; Ας μην το χοντραίνουμε όμως! Η Brainfuck δεν έχει ούτε καν τους απλούς ελέγχους IF. Τώρα ενδέχεται να διαμαρτυρηθείτε — και δικαίως. Η αλήθεια είναι ότι η εντολή έναρξης βρόχου ([) πραγματοποιεί κάτι παραπλήσιο με αυτό που θέλουμε: Ελέγχει αν η τιμή του τρέχοντος κελιού είναι 0 ή όχι και είτε συνεχίζει την εκτέλεση από την επόμενη γραμμή είτε μεταπηδά στην αντίστοιχη δεξιά αγκύλη. Ο αντίστοιχος κώδικας σε PHP θα ήταν κάπως έτσι:

While ($current_cell != 0) {
   ...
   ...
}

Η παραπάνω δομή μοιάζει κάπως με τον έλεγχο IF, αλλά δεν πρέπει να ξεχνάμε ότι πρόκειται για κάτι διαφορετικό: Για ένα βρόχο επαναλήψεων. Αυτό σημαίνει ότι το μπλοκ του κώδικα ενδέχεται να εκτελεστεί παραπάνω από μία φορές και όχι ακριβώς μία, όπως θα συνέβαινε με έναν έλεγχο IF. Σκεφτείτε, λοιπόν, την περίπτωση που θέλουμε να υλοποιήσουμε κάτι τέτοιο:

If ($current_cell != 0) {
   ...
   ...
}

Για να πετύχουμε κάτι παρόμοιο στη Brainfuck θα χρειαστούμε ένα βοηθητικό κελί. Η τιμή αυτού του κελιού είναι αδιάφορη, αλλά πρέπει να θυμόμαστε ότι θα καταστραφεί. Αν χρησιμοποιήσουμε το κελί 1 σαν βοηθητικό, ο κώδικας για τον παραπάνω έλεγχο έχει ως εξής:

[      Έναρξη βρόχου, αν το κελί 0 *δεν* είναι μηδέν
   ...    Κώδικας που εκτελείται όταν το κελί 0 *δεν* είναι μηδέν
   >      Μετάβαση στο κελί 1 (βοηθητικό)
   [-]    Επαναλαμβανόμενες μειώσεις μέχρι να μηδενιστεί
]      Έξοδος από το βρόχο!

Τι λέτε; Το καινούργιο κόλπο φαίνεται στην προτελευταία γραμμή του βρόχου. Αφού μεταβούμε στο βοηθητικό κελί, ξεκινάμε ένα δεύτερο βρόχο που περιλαμβάνει μόνο την εντολή μείωσης. Ο φωλιασμένος βρόχος θα τερματιστεί όταν το τρέχον κελί μηδενιστεί. Αμέσως μετά, όμως, θα τερματιστεί και ο εξωτερικός βρόχος. Τελικά, η ακολουθία εντολών ‘[-]’ λειτουργεί σαν τη γνωστή εντολή break. Με τη βοήθεια αυτού του χειροποίητου break, εξασφαλίζουμε ότι ο κώδικας που περικλείεται στο εξωτερικό ζεύγος αγκυλών θα εκτελεστεί μόνο μια φορά.

Σύγκριση κελιών
Για την ώρα έχουμε μάθει να ελέγχουμε αν ένα κελί έχει μηδενική τιμή ή όχι. Αυτός ο έλεγχος είναι χρήσιμος, αλλά δεν αρκεί. Υπάρχει ένας εξίσου απλός έλεγχος, ο οποίος παρουσιάζει ακόμα μεγαλύτερη χρησιμότητα. Πρόκειται για τη σύγκριση δύο τιμών και την εκτέλεση ενός τμήματος κώδικα, ανάλογα με το ποια τιμή είναι μεγαλύτερη. Πριν παρουσιάσουμε την υλοποίηση των συγκρίσεων πρέπει να εξετάσουμε μια φαινομενικά άσχετη τεχνική, η οποία όμως θα φανεί ιδιαίτερα χρήσιμη στη συνέχεια. Πρόκειται για ένα κολπάκι με το οποίο εντοπίζουμε το πρώτο κελί, είτε προς τα “αριστερά” είτε προς τα “δεξιά”, που έχει μηδενική τιμή. Ο κώδικας που πετυχαίνει τον εντοπισμό είναι ιδιαίτερα απλός:

[>]   συνεχής μετακίνηση προς τα δεξιά, μέχρι να βρεθεί μηδενικό κελί
[<]   συνεχής μετακίνηση προς τα αριστερά, μέχρι να βρεθεί μηδενικό κελί

Όπως βλέπετε, για να βρούμε το πλησιέστερο μηδενικό κελί χρησιμοποιούμε έναν μικρό βρόχο. Μέσα στο βρόχο πραγματοποιούμε μόνο τη μετακίνηση προς την επιθυμητή κατεύθυνση. Ξέρουμε ότι αυτό το κόλπο μοιάζει τόσο ενδιαφέρον, όσο και άχρηστο για το ζήτημα των συγκρίσεων. Σε λίγο όμως θα διαπιστώσετε ότι είναι απολύτως απαραίτητο.

Για να πετύχουμε τη σύγκριση δύο τιμών στη Brainfuck, χρειαζόμαστε έξι διαδοχικά κελιά. Στο πρώτο πρέπει να βάλουμε την τιμή 0, στο δεύτερο την τιμή 1 και στο τρίτο την τιμή 0. Στα επόμενα δύο κελιά πρέπει να τοποθετήσουμε τους αριθμούς που θέλουμε να συγκρίνουμε, ενώ στο έκτο πρέπει να δώσουμε και πάλι την τιμή μηδέν…

>++     Μετάβαση στο κελί 1 και ορισμός τιμής 1
>&gt;++    Μετάβαση στο κελί 3 και ορισμός τιμής 2
>+++++  Μετάβαση στο κελί 2 και ορισμός τιμής 5

Χάρτης μνήμης:
Κ0=0 | Κ1=1 | Κ2=0 | Κ3=2 | Κ4=4 | Κ5=0

Τα κελιά 0, 2 και 5, όπως όλα τα κελιά της μνήμης,
μηδενίζονται κατά την έναρξη του προγράμματος

&lt;       Μετάβαση στο κελί 3
[       Έναρξη βρόχου
   -       Μείωση τιμής στο τρέχον κελί
   &gt;-      Μετάβαση στο κελί 4 και μείωση
   [&gt;]     Εύρεση πρώτου μηδενικού κελιού προς τα δεξιά
   &lt;&lt;      Μετάβαση 2 κελιά προς τα αριστερά (πίσω)
]       Τερματισμός βρόχου

Μετά την αποθήκευση των επιθυμητών τιμών, μεταβαίνουμε στο κελί με τον πρώτο προς σύγκριση αριθμό και ξεκινάμε ένα βρόχο. Μέσα στο βρόχο μειώνουμε κατά μία μονάδα τους δύο αριθμούς και μεταβαίνουμε στο πρώτο μηδενικό κελί προς τα δεξιά. Ακολούθως μεταβαίνουμε δύο κελιά προς τα πίσω κι επαναλαμβάνουμε το βρόχο με τις μειώσεις. Αναρωτιέστε σε τι ωφελούν αυτές οι μανούβρες;

Αν ο αριθμός στο κελί 3 είναι μικρότερος από τον αριθμό στο κελί 4, θα μηδενιστεί πρώτος. Συγκεκριμένα, σε κάποια από τις επαναλήψεις του βρόχου το κελί 3 θα μηδενιστεί, ενώ το κελί 4 θα έχει μη μηδενική τιμή. Αμέσως μετά, αναζητώντας το πρώτο μηδενικό κελί προς τα δεξιά, θα καταλήξουμε στο κελί 5. Κι όταν στη συνέχεια κάνουμε δύο βήματα πίσω (προς τα αριστερά), θα βρεθούμε στο κελί 3. Αυτό το κελί όμως έχει μηδενιστεί κι έτσι ο βρόχος των μειώσεων θα τερματιστεί. Με λίγα λόγια, αν ο αριθμός στο κελί 3 είναι μικρότερος ο βρόχος θα τερματιστεί, με το δείκτη μνήμης να παραπέμπει στο κελί 3. Ας εξετάσουμε τώρα και την άλλη περίπτωση.

Αν ο αριθμός στο κελί 3 είναι μεγαλύτερος από τον αριθμό στο κελί 4, σε κάποια από τις επαναλήψεις του βρόχου θα μηδενιστεί το κελί 4, ενώ το κελί 3 θα έχει μη μηδενική τιμή. Στη συνέχεια, αναζητώντας το πρώτο μηδενικό κελί προς τα δεξιά και εφόσον το κελί στο οποίο βρισκόμαστε (κελί 4) έχει ήδη μηδενιστεί, δεν θα μετακινηθούμε καθόλου! Έτσι, κάνοντας δύο βήματα πίσω (προς τα αριστερά) θα καταλήξουμε στο κελί 2. Αυτό το κελί, όμως, έχουμε φροντίσει εξαρχής να είναι μηδενισμένο. Κατά συνέπεια, ο βρόχος των μειώσεων θα τερματιστεί. Τελικά, αν ο αριθμός στο κελί 3 είναι μεγαλύτερος, ο βρόχος θα τερματιστεί με το δείκτη μνήμης να παραπέμπει στο κελί 2. Το ίδιο θα συμβεί και στην περίπτωση που οι δύο αριθμοί είναι ίσοι.

Ωραία όλα αυτά, θα πείτε, αλλά σε τι ωφελούν; Η αλήθεια είναι ότι ο κώδικας που είδαμε δεν είναι ολοκληρωμένος. Στις παραπάνω γραμμές κώδικα, πρέπει να προσθέσουμε τις ακόλουθες:

<<      Μετάβαση 2 κελιά προς τα αριστερά
[       Εκτέλεση αν κελί_3 < κελί_4 
   ...
]

Θυμηθείτε τι είπαμε προηγουμένως. Αν ο αριθμός στο κελί 3 είναι μικρότερος, ο δείκτης μνήμης θα καταλήξει να παραπέμπει στο κελί 3. Διαφορετικά, ο δείκτης μνήμης θα καταλήξει να παραπέμπει στο κελί 2. Κάνοντας δύο ακόμα βήματα πίσω (προς τα αριστερά), αν ο αριθμός στο κελί 3 είναι μικρότερος θα καταλήξουμε στο κελί 1. Στην αντίθετη περίπτωση θα καταλήξουμε στο κελί 0. Όμως, το κελί μηδέν έχει την τιμή 0, ενώ το κελί 1 έχει την τιμή 1. (Ουφ!) Επομένως, αν ο αριθμός στο κελί 3 είναι μικρότερος κι έχουμε καταλήξει στο κελί 1, ο τελικός βρόχος θα εκτελεστεί. Στην αντίθετη περίπτωση θα έχουμε καταλήξει στο κελί 0, κι ο τελικός βρόχος δεν θα εκτελεστεί.

Απλό δεν ήταν; Και για το κερασάκι στην τούρτα, αξίζει να σημειώσουμε το εξής: Όταν ο αριθμός στο κελί 3 είναι μεγαλύτερος ή ίσος με τον αριθμό στο κελί 4, στο τέλος της σύγκρισης το κελί 3 θα διατηρεί την διαφορά των δύο. Προφανώς, αν αυτή η διαφορά είναι μηδενική, τότε οι δύο αριθμοί είναι ίσοι. Αυτή τη λεπτομέρεια μπορούμε να την έχουμε κατά νου και να την αξιοποιήσουμε όταν θέλουμε να τσεκάρουμε την ισότητα δύο αριθμών.

Brainfuck IDE;
Όπως θα έχετε καταλάβει, ο προγραμματισμός στη Brainfuck είναι αρκετά σκληρός και απαιτεί μια πολύ διαφορετική λογική από αυτήν που έχουμε αναπτύξει. Ακριβώς γι’ αυτό, κατά τη γνώμη μας πάντα, η γλώσσα αποτελεί μια πολύ ενδιαφέρουσα πρόκληση/άσκηση για τη σκέψη. Για καλή μας τύχη, αν και πρόκειται για γλώσσα που δεν χρησιμοποιείται σε αληθινές εφαρμογές, κάποιοι προγραμματιστές έχουν δημιουργήσει ολόκληρα IDE γι’ αυτή. Ένα από αυτά είναι το λεγόμενο Brainfuck Developer. Το πρόγραμμα ενσωματώνει έναν interpreter για τη Brainfuck, όπως επίσης και τις βασικές λειτουργίες ενός debugger. Μέσα από το περιβάλλον του μπορούμε να εκτελούμε προγράμματα σε Brainfuck γραμμή προς γραμμή και, ταυτόχρονα, να παρακολουθούμε τις αλλαγές στη μνήμη.

Το λιτό περιβάλλον του Brainfuck Developer κατάφερε να κερδίσει την καρδιά μας, κυρίως χάρη στην αμεσότητα που προσφέρει. Το γεγονός ότι δεν παράγει εκτελέσιμα δεν μας πτόησε καθόλου, ούτε μείωσε τη χαρά του παιχνιδιού με τη Brainfuck.

Ένα ακόμα IDE που αξίζει την προσοχή μας είναι το Visual Brainfuck. Το συγκεκριμένο IDE περιλαμβάνει όλες τις δυνατότητες του “Brainfuck Developer”, ενώ επιπρόσθετα δημιουργεί κι εκτελέσιμα προγράμματα με τη βοήθεια του ενσωματωμένου compiler.

Το Visual Brainfuck διαθέτει όμορφες απεικονίσεις, οι οποίες ωστόσο δεν είναι ιδιαίτερα χρήσιμες. Θα το χαρακτηρίζαμε απλά φανταιζί! Ο ενσωματωμένος compiler, όμως, αποτελεί μεγάλη ευκολία.

Πάντως, αν δοκιμάσετε τα δύο IDE και καταλήξετε στο πρώτο, μπορείτε να μετατρέψετε τα προγράμματά σας σε εκτελέσιμα με τη βοήθεια ενός εξωτερικού μεταγλωττιστή. Μια καλή λύση αποτελεί ο λεγόμενος Brainfucked. Ο συγκεκριμένος compiler παράγει λιλιπούτεια προγράμματα “COM”, που εκτελούνται σε οποιοδήποτε σύστημα Windows μπορείτε να τρέξει 16μπιτο κώδικα.

Η ενασχόληση με την Brainfuck μας χάρισε αρκετά απογεύματα διασκέδασης και ακονίσματος του μυαλού. Ελπίζουμε να την απολαύσετε κι εσείς και περιμένουμε να δούμε τα δικά σας δημιουργήματα :)

Leave a Reply

You must be logged in to post a comment.

Σύνδεση

Αρχείο δημοσιεύσεων