Είναι ο Νοέμβριος των Nibbles

Introduction

Γεια σε όλους. Καλώς ήρθες στον Νοέμβριο. Ελπίζω να είσαι καλά.

Είχαμε έναν πολύ γεμάτο Οκτώβριο. Μόλις κυκλοφορήσαμε μια μεγάλη βελτίωση στις λύσεις της κοινότητας. Τώρα αφαιρούμε τα διπλότυπα, ώστε οι παρόμοιες λύσεις να εμφανίζονται μόνο μία φορά, προσθέσαμε νέες επιλογές ταξινόμησης, τη δυνατότητα αναζήτησης με κώδικα, και αν κοιτάξεις τη C#, θα δεις ότι προσθέσαμε και τη δυνατότητα φιλτραρίσματος με βάση διαφορετικές έννοιες προγραμματισμού. Έτσι μπορείς να ψάξεις για λύσεις που χρησιμοποιούν ολισθήσεις bit, αναδρομή ή ό,τι άλλο θέλεις. Θα το επεκτείνουμε και σε άλλα tracks την εβδομάδα της κοινότητας.

Αλλά για την ώρα, ας επικεντρωθούμε στο #12in23. Ο Οκτώβριος ήταν ένας ενδιαφέρον μήνας, με εξερεύνηση των αντικειμενοστρεφών γλωσσών, αλλά αυτόν τον μήνα το πάμε στα δύσκολα. Επικεντρωνόμαστε στις γλώσσες assembly και συγκεκριμένα στη MIPS Assembly, τη x86-64 Assembly και τη WebAssembly. Ως συνήθως, ο Erik θα μας εξηγήσει τι κάνει αυτές τις γλώσσες ενδιαφέρουσες και μοναδικές.

Τα badge

Όπως πάντα, μπορείς να κερδίσεις το badge Nibbly November ολοκληρώνοντας 5 ασκήσεις σε αυτές τις γλώσσες. Έχουμε επίσης το badge της χρονιάς, τον στόχο που ξέρω ότι έχουν βάλει πολλοί. Γι' αυτό έχουμε 5 επιλεγμένες ασκήσεις για να ολοκληρώσεις. Είναι οι εξής:

• Καταμέτρηση Πληθυσμού: μέτρησε τα 1 bits σε έναν αριθμό
• Κόκκοι: υπολόγισε τον αριθμό των κόκκων σε μια σκακιέρα όπου τα τετράγωνα διπλασιάζονται
• Χρώμα Αντιστάτη: μετέτρεψε το χρώμα μιας ζώνης αντιστάτη στην αριθμητική του αναπαράσταση
• Περιστροφικό Κρυπτογράφημα: υλοποίησε το περιστροφικό κρυπτογράφημα (γνωστό και ως κρυπτογράφημα του Καίσαρα)
• Καταμέτρηση Νουκλεοτιδίων: υπολόγισε πόσες φορές εμφανίζεται κάθε νουκλεοτίδιο σε μια συμβολοσειρά DNA

Ιστορικό

Γιατί να το ονομάσουμε Nibble November;

Λοιπόν, όπως πιθανότατα ξέρεις, ένα byte είναι 8 bits. Και ένα nibble είναι 4 bits. Το όνομα αρχίζει να βγάζει νόημα αν αλλάξεις το y στο byte σε i, που σου δίνει το bite. Ένα nibble είναι τότε ένα μικρό δάγκωμα.

Τι είναι μια γλώσσα assembly;

Λοιπόν, ας ξεκινήσουμε με τα βασικά. Μια CPU εκτελεί εντολές, όπως "πρόσθεσε δύο αριθμούς" ή "ολίσθησε τα bits αριστερά", κ.λπ. Αυτές οι εντολές είναι γνωστές ως εντολές κώδικα μηχανής και δεν είναι τίποτα περισσότερο από συγκεκριμένες ακολουθίες bits. Η εκτέλεση ενός προγράμματος είναι "απλώς" (σε εισαγωγικά) η CPU που επεξεργάζεται και εκτελεί αυτές τις ακολουθίες bits.

Επειδή το να γράφεις απευθείας τις εντολές ως ακολουθίες bits είναι επίπονο και επιρρεπές σε λάθη, η Kathleen και ο Andrew Donald Booth επινόησαν το 1947 μια πιο φιλική προς τον άνθρωπο γλώσσα για να αναπαριστούν εντολές κώδικα μηχανής. Μια τέτοια γλώσσα που αναπαριστά εντολές κώδικα μηχανής ονομάζεται γλώσσα assembly. Αυτή η γλώσσα assembly μετατρέπεται στη συνέχεια σε εντολές κώδικα μηχανής μέσω ενός "assembler".

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

Παρεμπιπτόντως, αν θυμάσαι τις διάτρητες κάρτες, εκείνα τα μεγάλα κομμάτια χαρτιού που χρησιμοποιούνταν στους πρώτους υπολογιστές για να εκτελούν προγράμματα, ήταν κι αυτές μια γλώσσα assembly!

Σε τι διαφέρει η γλώσσα assembly από τις γλώσσες με τις οποίες προγραμματίζουμε σήμερα;

Η βασική διαφορά είναι ότι οι γλώσσες assembly είναι πολύ χαμηλού επιπέδου. Θα σου λείψουν πολλές αφαιρέσεις στις οποίες έχεις συνηθίσει. Κλάσεις ή αντικείμενα δεν υπάρχουν πουθενά. Βρόχοι; Θα πρέπει να τους γράψεις χειροκίνητα μέσω αλμάτων. Συναρτήσεις; Καθόλου! Το να γράφω κώδικα assembly μου έδωσε ένα μάθημα ταπεινοφροσύνης, γιατί τότε συνειδητοποιείς πόσο οι σύγχρονες γλώσσες σου κάνουν τη ζωή πιο εύκολη. Αλλά είναι επίσης απίστευτα χρήσιμο να γράφεις κώδικα assembly, γιατί αποκτάς πολύ καλύτερη κατανόηση του πώς λειτουργούν πραγματικά τα πράγματα.

Διασκεδαστική λεπτομέρεια: το 99% του πηγαίου κώδικα του RollerCoaster Tycoon ήταν χειρόγραφος κώδικας assembly! Είναι ένα εκπληκτικό επίτευγμα, το οποίο θα εκτιμήσεις ακόμα περισσότερο μόλις γράψεις λίγη assembly ο ίδιος.

Γράφει ακόμα ο κόσμος κώδικα assembly;

Λοιπόν, λιγότερο από ό,τι παλιά. Κάποτε η χειροποίητη assembly ξεπερνούσε συχνά τον κώδικα μηχανής που παρήγαγε ο compiler (ένας λόγος για τον οποίο η C++ επιτρέπει να ενσωματώνεις απευθείας κώδικα assembly), αλλά οι compilers έχουν γίνει τόσο καλοί στο να παράγουν κώδικα μηχανής που αυτό σπάνια ισχύει πια. Παρόλα αυτά, θα βρεις ακόμα γλώσσα assembly να χρησιμοποιείται σε περιβάλλοντα όπου η απόδοση είναι κρίσιμη ή οι πόροι περιορισμένοι.

Επισκοπήσεις

MIPS

• Η MIPS (Microprocessor without Interlocked Pipelined Stages) είναι μια οικογένεια αρχιτεκτονικών συνόλων εντολών RISC (reduced instruction set computer)
• Αναπτύχθηκε από τη MIPS Computer Systems και κυκλοφόρησε για πρώτη φορά το 1985
• Πολλαπλές εκδόσεις: MIPS I, II, III, IV, V και MIPS32/64. Οι δύο πρώτες εκδόσεις ήταν μόνο 32-bit, αλλά η MIPS III εισήγαγε υποστήριξη 64-bit.
• Αρκετές προαιρετικές επεκτάσεις, όπως εντολές SIMD και συμπίεση
• Πολύ σημαντική επιρροή σε μεταγενέστερες αρχιτεκτονικές RISC
• Η MIPS ανακοίνωσε το 2021 ότι η αρχιτεκτονική MIPS δεν αναπτυσσόταν πλέον και ότι μετανάστευσε στη RISC-V (η οποία είναι αρχιτεκτονική ανοιχτού κώδικα, χωρίς δικαιώματα εκμετάλλευσης)
• Χρησιμοποιείται κυρίως σε ενσωματωμένα συστήματα (π.χ. δρομολογητές) και servers (τους χρησιμοποιούσαν οι υπολογιστές της Silicon Graphics, γνωστοί για τη χρήση τους σε ειδικά εφέ ταινιών), στον υπερυπολογιστή NEC Cenju-4, στο αυτοκίνητο Tesla Model S, στο σκάφος New Horizons της NASA, αλλά και για τη διδασκαλία της assembly στα πανεπιστήμια και σε αρκετές κονσόλες παιχνιδιών (π.χ. το αρχικό PlayStation, το Playstation Portable και το Nintendo 64)

x86-64 Assembly

• Σχεδιάστηκε από την AMD και κυκλοφόρησε το 1999 ως αρχιτεκτονική AMD64
• Είναι μια έκδοση 64-bit του συνόλου εντολών x86, το οποίο χρονολογείται από το 1978, όταν η Intel κυκλοφόρησε τον μικροεπεξεργαστή 8086. Εκείνος ήταν επεξεργαστής 16-bit, αλλά αργότερα ο 80386 πρόσθεσε εντολές 32-bit, και αυτό το σύνολο εντολών έχει ταυτιστεί με το x86.
• Το βασικό που επέτρεψαν τα 64-bit ήταν η προσπέλαση περισσότερης μνήμης (η διευθυνσιοδότηση 32-bit περιορίζεται στα 4GB), κάτι που είχε γίνει σημείο συμφόρησης. Τα 64-bit μπορούν, θεωρητικά, να προσπελάσουν 16 Exabytes, αλλά προς το παρόν χρησιμοποιούνται μόνο 48 bits, που επιτρέπουν την προσπέλαση 256 TB (μπορεί να επεκταθεί αργότερα όταν χρειαστεί)
• Το AMD64 επεκτείνει το σύνολο εντολών x86 και σχεδιάστηκε ώστε να είναι πλήρως συμβατό με τις υπάρχουσες εφαρμογές 16 και 32-bit μέσω μιας λειτουργίας συμβατότητας
  • Η Intel είχε σχεδιάσει το IA-64 χωρίς τη συμμετοχή της AMD. Ήταν ένα νέο, πολύ διαφορετικό και μη συμβατό προς τα πίσω σύνολο εντολών 64-bit. Τελικά, το AMD64 επικράτησε και η Intel υλοποίησε τη δική της εκδοχή του (με μόνο μικρές σημασιολογικές διαφορές)
• Χρησιμοποιείται παντού. Από σταθμούς εργασίας μέχρι servers (συμπεριλαμβανομένων των υπερυπολογιστών), από ενσωματωμένα συστήματα μέχρι κονσόλες παιχνιδιών (π.χ. PS5 και Xbox Series X).

WebAssembly

• Σχεδιάστηκε από το W3C, έναν οργανισμό προτύπων για τεχνολογίες web
• Οι στόχοι του σχεδιασμού είναι:
  • Γρήγορο, ασφαλές και φορητό
  • Αποδοτική και φορητή αναπαράσταση
• Παλιότερα, η γρήγορη εκτέλεση στο web επιτυγχανόταν συνήθως μέσω εξειδικευμένων πρόσθετων του browser, όπως το Flash και το Silverlight, καθώς η ίδια η JavaScript δεν προσφέρεται πολύ για υπολογισμούς υψηλών επιδόσεων. Τα βασικά μειονεκτήματα αυτών των πρόσθετων ήταν ότι συνήθως είχαν πολλά προβλήματα ασφάλειας και δεν ήταν τυποποιημένα.
  • Η Mozilla σχεδίασε το asm.js, ένα υποσύνολο της JavaScript που στόχευε να επιτρέπει την εκτέλεση κώδικα στον browser με εξαιρετικά χαρακτηριστικά απόδοσης, κάτι που πέτυχε μέσω συνέπειας τύπων (χωρίς δυναμική αλλαγή τύπων) και χωρίς συλλογή απορριμμάτων. Οι γλώσσες μπορούσαν τότε να μεταγλωττίζονται σε asm.js και να έχουν ακόμα καλή απόδοση όταν εκτελούνται στο web. Ήταν όμως ακόμα JS, άρα περιορισμένο στο τι μπορούσε να επιτευχθεί. Εξ ου και η πρόταση για μια νέα γλώσσα: WASM.
• Γλώσσα παρόμοια με assembly, υπό την έννοια ότι παρέχει ένα σύνολο εντολών προς εκτέλεση. Το κρίσιμο είναι ότι δεν είναι δεσμευμένη σε συγκεκριμένη CPU, άρα είναι ανεξάρτητη από την πλατφόρμα και απαιτεί υλοποίηση για κάθε πλατφόρμα (μια εικονική μηχανή). Αυτό σημαίνει ότι η WebAssembly είναι στην πραγματικότητα bytecode, όχι κώδικας μηχανής
• Στατικά τυποποιημένη (κρίσιμη διαφορά από τη JS)
• Χρησιμοποιεί συνήθως μεταγλώττιση ahead-of-time ή just-in-time (αλλά μπορεί να ερμηνευτεί)
• Ανοιχτό πρότυπο και ορίζει δύο πράγματα:
  • Μια δυαδική μορφή
  • Μια μορφή κειμένου (η οποία μεταγλωττίζεται στη δυαδική μορφή)
• Υλοποιήσεις σε όλους τους μεγάλους browsers
• Χρησιμοποιείται σε πολλές ιστοσελίδες που απαιτούν υψηλή απόδοση, όπως το Google Earth, το Figma, το Unity και το Autocad. Έχει επίσης κερδίσει έδαφος στην πλευρά του server, π.χ. για εκτέλεση microservices, για εκτέλεση σε πλατφόρμες SaaS (π.χ. CloudFlare workers) ή μέσα σε Docker

Και από προγραμματιστική σκοπιά, σε τι διαφέρουν;

MIPS

• Χρησιμοποιεί αρχιτεκτονική load-store (γνωστή και ως register-register), όπου οι εντολές είτε κάνουν προσπέλαση μνήμης είτε αριθμητικές πράξεις, αλλά λειτουργούν αποκλειστικά σε δεδομένα που βρίσκονται σε καταχωρητές

x86-64 Assembly

• Χρησιμοποιεί αρχιτεκτονική register-memory, η οποία επιτρέπει πράξεις να εκτελούνται πάνω σε (ή από) μνήμη, καθώς και σε καταχωρητές

WebAssembly

• Χρησιμοποιεί προγραμματισμό βασισμένο σε στοίβα (χωρίς καταχωρητές) με δυνατότητα ανάγνωσης δεδομένων από και προς τη μνήμη

Ποια είναι τα χαρακτηριστικά που κάνουν αυτές τις γλώσσες σπουδαίες;

MIPS

• Μικρή. Το σύνολο εντολών της MIPS χωράει όλες τις εντολές του σε μία σελίδα
• Καθιερωμένες συμβάσεις κλήσης βοηθούν να προσδιορίσεις πώς να χρησιμοποιείς τους διαθέσιμους καταχωρητές, π.χ. ποιους να χρησιμοποιείς για να περνάς ορίσματα και ποιους για να επιστρέφεις αποτελέσματα.
• Σταθερή. Η τελευταία έκδοση κυκλοφόρησε το 2014
• Ευρέως τεκμηριωμένη, ιδιαίτερα σε ακαδημαϊκά συγγράμματα
• Μεγάλη χρήση στον πραγματικό κόσμο. Δισεκατομμύρια συσκευές

x86-64 Assembly

• Αν και επέκταση του x64, προστέθηκαν πολλά νέα χαρακτηριστικά, όπως:
  • Υποστήριξη ακεραίων 64-bit
  • Επιπλέον καταχωρητές
  • Εντολές SSE (εντολές διανυσμάτων)
  • Σχετική προσπέλαση δεδομένων (πιο αποδοτική όταν χρησιμοποιείς κοινόχρηστες βιβλιοθήκες)
  • No-Execute Bit (χαρακτηριστικό ασφάλειας που αποτρέπει την εκτέλεση κώδικα σε συγκεκριμένες σελίδες μνήμης)
• Οικεία. Καθώς επεκτείνει το σύνολο εντολών x86, θα είναι σχετικά εύκολη στην εκμάθηση για όσους γνωρίζουν το σύνολο εντολών x86 Εκτενής και λεπτομερής τεκμηρίωση
• Σταθερή. Αν και προστίθενται τακτικά νέες εκδόσεις, ο πυρήνας παραμένει εξαιρετικά σταθερός και συμβατός προς τα πίσω

WebAssembly

• Η βασισμένη σε στοίβα εικονική μηχανή της WebAssembly είναι λιτή και απλή σε σύγκριση με τις γλώσσες assembly των φυσικών επεξεργαστών (συμπεριλαμβανομένης της RISC). Αυτό την κάνει σχετικά εύκολη στη μεταγλώττιση.
• Η Μορφή Κειμένου της WebAssembly χρησιμοποιεί τη "ζάχαρη" των S-Expressions για να πετύχει ένα οικείο προστακτικό ύφος, το οποίο μετασχηματίζεται σε κώδικα βασισμένο σε στοίβα. Η μορφή με S-Expressions ονομάζεται "ζαχαρούχα μορφή" και "αποζαχαρινώνεται" στην άλλη μορφή, που είναι ισοδύναμη με αυτό που υπάρχει στο δυαδικό αρχείο. Οι S-expressions θα είναι οικείες σε όποιον έχει δουλέψει ποτέ με LISP
• Ισχυρή διαλειτουργικότητα με τη JavaScript. Εύκολη μεταφορά δεδομένων από και προς τη JavaScript. Σημαντική επιφύλαξη: η WASM δεν επιτρέπει (ακόμα) την αλληλεπίδραση με το DOM
• Βελτιώνεται συνεχώς. Δεν βελτιώνονται μόνο οι εικονικές μηχανές WASM, αλλά και το ίδιο το πρότυπο βρίσκεται σε ενεργή ανάπτυξη. Ένας σωρός νέα χαρακτηριστικά σχεδιάζονται και υλοποιούνται, όπως εντολές σχετικές με SIMD, συλλογή απορριμμάτων, νήματα, βελτιστοποιήσεις tail-call και άλλα
• Ασφαλής. Ο κώδικας επικυρώνεται και εκτελείται σε περιβάλλον sandbox, παρέχοντας υψηλότερο βαθμό στατικής επικύρωσης σε σύγκριση με τη JavaScript ή τις εγγενείς γλώσσες assembly. Η σημασιολογία είναι καλά ορισμένη, κάνοντάς την εύκολη στον έλεγχο και τη συλλογιστική

Ξεχωριστά χαρακτηριστικά

MIPS

• Αποδοτικότητα. Οι επεξεργαστές MIPS είναι πολύ αποδοτικοί, κάνοντάς τους ιδανικούς για ενσωματωμένα συστήματα.
• Απόδοση. Εξαιρετική απόδοση, γι' αυτό η MIPS έχει χρησιμοποιηθεί σε υπερυπολογιστές
• Εύκολη στην εκμάθηση. Με λίγες εντολές και κάθε εντολή να κάνει μόνο ένα απλό πράγμα, γίνεται εύκολη στην εκμάθηση. Ιδανική για διδακτικούς σκοπούς.

x86-64 Assembly

• Ισχυρή. Το x86-64 έχει βελτιστοποιηθεί επί δεκαετίες, με έναν σωρό εντολές που βοηθούν στην απόδοση. Ένα παράδειγμα είναι το SIMD (Single Instruction, Multiple Data), που είναι εντολές οι οποίες, λοιπόν, μπορούν να εκτελέσουν μία εντολή παράλληλα σε πολλαπλά δεδομένα.
• Πανταχού παρούσα. Οι συσκευές που τρέχουν x86-64 είναι παντού. Οι CPU της Intel και της AMD το υλοποιούν. Είναι το de facto πρότυπο εδώ και αρκετό καιρό
• Ενημερώνεται τακτικά. Π.χ. νέες εντολές διανυσμάτων, με SSE3-5, AVX, AVX-512 και άλλα

WebAssembly

• Αποδοτική. Η δυαδική μορφή είναι συμπαγής και μπορεί να αποκωδικοποιηθεί, να επικυρωθεί και να μεταγλωττιστεί σε ένα γρήγορο πέρασμα. Είναι επίσης streamable, κάτι που επιτρέπει την αποκωδικοποίηση, την επικύρωση και τη μεταγλώττιση να ξεκινήσουν όσο το δυνατόν νωρίτερα, πριν ειδωθούν όλα τα δεδομένα. Και είναι επίσης παραλληλοποιήσιμη. Αυτό την κάνει ιδανική για εφαρμογές web υψηλών επιδόσεων.
• Εξαιρετικός στόχος μεταγλώττισης. Επιτρέπει σε κώδικα πολλών γλωσσών να εκτελείται στο web. Οι περισσότερες μεγάλες γλώσσες υποστηρίζουν μεταγλώττιση σε δυαδικά αρχεία WebAssembly, που σημαίνει ότι ο κώδικάς σου μπορεί να εκτελεστεί στο web χωρίς να χρειάζεται να γράψεις JavaScript. Κάποιες γλώσσες δεν μεταγλωττίζουν τον κώδικά σου σε WebAssembly, αλλά μεταγλωττίζουν το runtime σε WebAssembly, το οποίο μετά μπορεί να εκτελέσει αμετάβλητο bytecode.
• Εύκολη στην ανάπτυξη και την εκτέλεση. Το μόνο που χρειάζεσαι είναι μια εικονική μηχανή που μπορεί να ερμηνεύσει το bytecode, και όλοι οι μεγάλοι browsers περιλαμβάνουν μία.
• Δεν είναι δεσμευμένη στο web, αλλά μπορεί να εκτελεστεί και στην πλευρά του server. Το WebAssembly System Interface (WASI) είναι μια διασύνδεση (ABI και API) σχεδιασμένη να είναι φορητή σε οποιαδήποτε πλατφόρμα. Είναι παρόμοια με το POSIX (πρότυπες διασυνδέσεις για συστήματα Unix) και παρέχει πράγματα όπως I/O. Η ασφάλεια είναι βασικό μέρος του σχεδιασμού του, που περιλαμβάνει sandboxing και προσανατολισμό στις δυνατότητες (πρέπει να ζητήσεις ρητά άδειες για πράγματα όπως αρχεία ή sockets). Το WASI έχει επίσης τη δυνατότητα να επιτρέπει εύκολη διασύνδεση μεταξύ γλωσσών. Ο Solomon Hykes, συνιδρυτής του Docker, έγραψε το 2019: "Αν το WASM+WASI υπήρχε το 2008, δεν θα χρειαζόταν να δημιουργήσουμε το Docker"

Ποια να διαλέξεις

• Αν δεν έχεις δουλέψει ποτέ με γλώσσα assembly, η WebAssembly είναι πιθανώς η πιο εύκολη για να ξεκινήσεις. Παρόλα αυτά, αν θέλεις να μάθεις μια γλώσσα assembly που μεταγλωττίζεται σε κώδικα μηχανής, δοκίμασε τη MIPS Assembly
• Αν δουλεύεις σε μηχάνημα x86-64 (πολύ πιθανό), δοκίμασε τη x86-64 Assembly
• Αν είσαι εξοικειωμένος με τη LISP, θα εκτιμήσεις ότι η WebAssembly χρησιμοποιεί S-expressions
• Αν δουλεύεις με εφαρμογές web, η WebAssembly είναι η πιο λογική επιλογή
• Αν σε νοιάζει η απόδοση, το x86-64 και η MIPS είναι εξαιρετικές επιλογές. Ή αν σε νοιάζει η απόδοση στο web, δοκίμασε τη WebAssembly