BRAINFUCK - ΓΛΏΣΣΑ ΠΟΥ ΘΑ ΣΚΟΤΏΣΕΙ ΤΟΝ ΕΓΚΈΦΑΛΌ ΣΑΣ

Παρόλο που κάποιοι μπορεί να ισχυριστούν ότι η προσπάθεια είναι υπερβολική, θα μπορούσαμε όλοι να συμφωνήσουμε ότι μπορεί να είναι μια καλή ιδέα. Η επιλογή μιας νέας γλώσσας για εκμάθηση δεν είναι τόσο εύκολη. Δεν θέλουμε να αφιερώσουμε τον χρόνο μας σε κάτι που μπορεί να μην χρησιμοποιήσουμε ποτέ στην πράξη, έτσι δεν είναι; Ίσως όμως μερικές φορές θα πρέπει να κάνουμε μια εξαίρεση και να μάθουμε κάτι μόνο και μόνο για τη διασκέδαση; Θα ήθελα να σας παρουσιάσω τη γλώσσα Brainfuck. Πρόκειται για μια γλώσσα την οποία μπορείτε να μάθετε μέσα σε λίγα λεπτά, οπότε δεν υπάρχει το πρόβλημα να επενδύσετε πολύ από το χρόνο σας μάταια. Επίσης, μπορώ να σας υποσχεθώ ότι η επίλυση οποιουδήποτε προβλήματος με τη γλώσσα Brainfuck θα τονώσει τον εγκέφαλό σας (όλα τα f*cks είναι απλώς ένα μπόνους ;)). Ας ξεκινήσουμε!Σύμφωνα με τη Wikipedia:

Brainfuck είναι μια εσωτερική γλώσσα προγραμματισμού δημιουργήθηκε το 1993 από τον Urban Müller. Η γλώσσα αποτελείται μόνο από οκτώ απλές εντολές και έναν δείκτη εντολών. Αν και είναι πλήρως πλήρης κατά Turing, δεν προορίζεται για πρακτική χρήση, αλλά για να προκαλεί και να διασκεδάζει τους προγραμματιστές.

Επισκόπηση της γλώσσας

Φανταστείτε μια ταινία (ή ταινία) απείρου μήκους που αποτελείται από κελιά, καθένα από τα οποία έχει αρχικοποιηθεί στο 0. Υπάρχει επίσης ένας κινητός δείκτης δεδομένων που δείχνει αρχικά στο πρώτο κελί. Υπάρχουν επίσης δύο ροές bytes για την είσοδο και την έξοδο. Οι εντολές εκτελούνται διαδοχικά, μία προς μία. Η μηχανή σταματάει μετά την εκτέλεση της τελευταίας.

Εντολή

Τι κάνει;

>

μετακίνηση του δείκτη δεδομένων στο επόμενο κελί στα δεξιά

<

μετακίνηση του δείκτη δεδομένων στο επόμενο κελί στα αριστερά

+

αύξηση της τιμής του τρέχοντος κελιού

–

μείωση της τιμής του τρέχοντος κελιού

.

έξοδος του byte ενός τρέχοντος κελιού σε ASCII κωδικός

,

διαβάζει ένα byte από το stdin και αποθηκεύει την τιμή του στο τρέχον κελί

[

αν το τρέχον κελί είναι 0, τότε μεταπηδήστε στο αντίστοιχο ]

]

μεταβείτε στην αντίστοιχη [

Όλοι οι χαρακτήρες εκτός από ><+-.,[] αγνοούνται.

Ας δούμε ένα απλό παράδειγμα:

,+.

Θα ερμηνεύεται ως εξής:

• διαβάζει ένα byte και το αποθηκεύει στο τρέχον κελί (cell0)
• αύξηση της τιμής του τρέχοντος κελιού (cell0 = cell0 + 1)
• γράφει το περιεχόμενο του τρέχοντος κελιού στην έξοδο

Ως αποτέλεσμα, ένας χαρακτήρας θα διαβαστεί από την είσοδο και θα εκτυπωθεί ο επόμενος χαρακτήρας από τον πίνακα ASCII.

Διερμηνευτής / Μεταγλωττιστής

Πριν γράψουμε κάποια χρήσιμα (;) προγράμματα στο Brainfuck, χρειαζόμαστε έναν διερμηνέα ή έναν μεταγλωττιστή. AFAIK, δεν υπάρχει επίσημος, αλλά αυτό δεν είναι πρόβλημα. Υπάρχουν δεκάδες ανεπίσημοι στο διαδίκτυο. Μπορώ να προτείνω αυτούς τους δύο:

• https://github.com/apankrat/bff - εγκαθίσταται και χρησιμοποιείται τοπικά
• https://copy.sh/brainfuck/ - σε απευθείας σύνδεση
• https://ideone.com/ - σε απευθείας σύνδεση

H

Το "Hello World!" θα πρέπει να είναι το πρώτο πρόγραμμα που γράφουμε όταν μαθαίνουμε μια νέα γλώσσα. Ωστόσο, το να το γράψουμε στο Brainfuck είναι λίγο πιο δύσκολο από ό,τι σε άλλες γλώσσες. Πρέπει να ξεκινήσουμε με κάτι πιο εύκολο... Ας γράψουμε ένα πρόγραμμα που θα εκτυπώνει ένα μόνο γράμμα "H" στην οθόνη (τόσο συναρπαστικό :D):

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.

Πώς λειτουργεί; Θέτει την τιμή του τρέχοντος κελιού σε 72 (εκτελώντας 72 βήματα) και την εκτυπώνει στην οθόνη χρησιμοποιώντας "." (το H έχει κωδικό 72 σε ASCII). Τώρα ξέρετε τι πρέπει να κάνουμε για να εκτυπώσουμε το "Hello World!" στην οθόνη, αλλά πριν από αυτό, θα κάνουμε ένα μικρό refactoring. Η συγγραφή όλων αυτών των "+" απαιτεί πάρα πολύ δακτυλογράφηση και καταμέτρηση. Μπορούμε να το κάνουμε πιο σύντομο χρησιμοποιώντας [ και ] για βρόχο. Για να θέσουμε την τιμή σε 72 μπορούμε π.χ. να κάνουμε έναν βρόχο που αυξάνει την τιμή 7 φορές κατά 10. Με αυτόν τον τρόπο παίρνουμε 70. Προσθέτοντας 2 θα γίνει 72. Φαίνεται ως εξής:

++++++++++ # set cell0 to 10
[ # βρόχος μέχρι το cell0 να γίνει 0
- # μείωση cell0
> # μετακίνηση του δείκτη δεδομένων προς τα δεξιά (cell1)
+++++++ # αύξηση cell1 κατά 7
 # μετακίνηση του δείκτη δεδομένων προς τα δεξιά (cell1)
++ # αύξηση κατά 2
.            # εκτύπωση του αποτελέσματος

Έχω συμπεριλάβει σχόλια για να καταστήσω σαφές πώς λειτουργούν όλα. Το ίδιο πρόγραμμα χωρίς σχόλια:

++++++++++[->+++++++++.

Δεν είναι πανέμορφο; 🙂

Γεια σας κόσμε!

Επιστρέφοντας πίσω στο πρόγραμμα "Hello World!". Θα μπορούσαμε να ορίσουμε την τιμή του πρώτου κελιού σε 72 (H) και να το εκτυπώσουμε, να ορίσουμε την τιμή του 2ου κελιού σε 101 (e) και να το εκτυπώσουμε, να ορίσουμε την τιμή του 3ου κελιού σε 108 και να το εκτυπώσουμε κ.ο.κ. Ακολουθεί η υλοποίηση αυτού του αλγορίθμου:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++.>

Καθώς δεν είμαι αρκετά τρελός για να το γράψω πρόσημο προς πρόσημο, έκλεψα λίγο και δημιούργησα αυτό το πρόγραμμα με Ruby:

εισάγει "Hello World!".chars.map { |c| c.ord.times.map { "+" }.join + ".>" }.join("n")`

Ναι, μόνο 1120 bytes για να εκτυπωθεί το "Hello World!"... Αλλά μπορούμε να κάνουμε κάτι καλύτερο! Αντί να χρησιμοποιούμε νέο κελί για κάθε χαρακτήρα, ας χρησιμοποιήσουμε μόνο ένα. Για να εκτυπώσουμε το γράμμα "e" (101) μπορούμε να επαναχρησιμοποιήσουμε την τιμή στο κελί0 (72). Μπορούμε να την αυξήσουμε κατά ένα 29 φορές (101 - 72). Και το αποτέλεσμα έχει ως εξής:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
+++++++++++++++++++++++++++++.
+++++++.
.
+++.
-------------------------------------------------------------------------------.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++.
++++++++++++++++++++++++.
+++.
------.
--------.
-------------------------------------------------------------------.

Έκλεψα για άλλη μια φορά!:

puts "Hello World!".chars.inject(["", 0]) { |(code, prev), char| [code + "++-"[char.ord - prev  0] * (char.ord - prev).abs + ".n", char.ord] }[0]`)

Κάναμε σημαντική πρόοδο. 377 bytes αντί για 1120 bytes. Ωστόσο, υπάρχουν ακόμη περιθώρια βελτίωσης. Θα σας δώσω μερικές ιδέες:

• χρήση 3 (ή περισσότερων) κελιών για χαρακτήρες που βρίσκονται πιο κοντά μεταξύ τους στο ASCII (πεζά, κεφαλαία γράμματα, κενό και θαυμαστικό)
• χρησιμοποιήστε βρόχους αντί για επαναλαμβανόμενες + και -

Εδώ είναι η έκδοση από τη Wikipedia που χρησιμοποιεί αυτές τις ιδέες:

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

Είναι μόνο 106 bytes και εκτυπώνει νέα γραμμή στο τέλος! Καταπληκτικό.

Αντιστροφή μιας συμβολοσειράς

Τώρα είμαστε έτοιμοι να γράψουμε κάτι πιο δύσκολο. Ας γράψουμε ένα πρόγραμμα που θα διαβάζει μια γραμμή από την είσοδο και θα την εκτυπώνει με αντίστροφη σειρά. Το πρώτο πρόβλημα είναι να διαβάζουμε χαρακτήρες και να σταματάμε στο χαρακτήρα της νέας γραμμής. Θυμηθείτε ότι δεν υπάρχει διάλειμμα, εάν ή άλλες παρόμοιες δηλώσεις. Πρέπει να χρησιμοποιήσουμε [ και ]. Ας ξεκινήσουμε με ένα πρόγραμμα που διαβάζει όλους τους χαρακτήρες από την είσοδο και τους τοποθετεί σε διαδοχικά κελιά:

,[>,]

Ξεκινά με την ανάγνωση του πρώτου χαρακτήρα και θα συνεχιστεί μέχρι τον τελευταίο , η λειτουργία επιστρέφει 0. Όμως, θα κάνει βρόχο για πάντα σε εφαρμογή που επιστρέφει κάτι διαφορετικό από το O για το EOF (η γλώσσα δεν καθορίζει αυτή τη συμπεριφορά). Πώς μπορούμε λοιπόν να σταματήσουμε στο χαρακτήρα της νέας γραμμής; Εδώ είναι το κόλπο:

+[++++++++++>,----------]

Ξεκινάμε με το cell0 να έχει την τιμή 1 για να βεβαιωθούμε ότι ο βρόχος μας εκτελείται τουλάχιστον μία φορά. Σε έναν βρόχο αυξάνουμε την τιμή του τρέχοντος κελιού κατά 10, μετακινούμε τον δείκτη δεδομένων στο επόμενο κελί, διαβάζουμε έναν χαρακτήρα και μειώνουμε την τιμή του κατά 10. Με αυτόν τον τρόπο, αν διαβαστεί ένας νέος χαρακτήρας γραμμής (10 σε ASCII), το πρόγραμμα θα σταματήσει σε μια επόμενη επανάληψη, διαφορετικά η τιμή του θα αποκατασταθεί προσθέτοντας 10.

Μετά από αυτό το βήμα, τα κελιά μας θα έχουν την εξής μορφή:

11 C1 C2 C3 0* 0 0 0

Cn είναι ο n-οστός χαρακτήρας από την είσοδο, και * είναι η τρέχουσα θέση του δείκτη δεδομένων. Τώρα πρέπει να αρχίσουμε να μετακινούμε τον δείκτη δεδομένων προς τα αριστερά και να εκτυπώσουμε όλα τα κελιά μέχρι να φτάσουμε στην τιμή 11. Ακολουθεί η δική μου άποψη για την εργασία:

+[++++++++++>,----------]<-----------[+++++++++++.<-----------]

Σας ενθαρρύνω να το αναλύσετε μόνοι σας :-).

Περίληψη

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

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

Το Brainfuck είναι μια πλήρης γλώσσα Turing που τονίζει περαιτέρω τη σημασία της ύπαρξης ενός σαφούς, συνεκτικού πηγαίου κώδικα. Παρά το γεγονός ότι αναγνωρίζεται ως μία από τις πιο δύσκολες εσωτεριστικές γλώσσες για τη συγγραφή προγραμμάτων, με ειρωνικό τρόπο λάμπει ως η αγαπημένη γλώσσα των αρχαρίων για όποιον θέλει να δημιουργήσει έναν δικό του μεταγλωττιστή Brainfuck ή έναν δικό του διερμηνέα Brainfuck. Ο λόγος είναι η απλότητα του συνόλου των εντολών της και το γεγονός ότι δεν απαιτεί πολύπλοκη ανάλυση.

Η δημιουργία ενός προγράμματος Brainfuck είναι μοναδική με δύο τρόπους. Πρώτον, πρέπει να προσαρμοστείτε στη χρήση ενός μόνο δείκτη μνήμης, γεγονός που σας αναγκάζει να σκεφτείτε διαφορετικά για τον πηγαίο σας κώδικα. Και δεύτερον, έχετε την "επιλογή μηδέν", δηλαδή τη δυνατότητα να μηδενίσετε το κελί μνήμης, ένα χαρακτηριστικό που δεν είναι συνηθισμένο σε άλλες επίσημες γλώσσες προγραμματισμού.

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

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