Was sind Datenstrukturen auf unterster Ebene?

Question

Ich beobachtete eine SICP-Vorlesung, in der Sussman demonstrierte, wie es möglich war, Schemes conscar und cdr nur mit Hilfe von Prozeduren zu implementieren.

Es ging ungefähr so:

(define (cons x y) 
    (lambda (m) (m x y))) 

(define (car z) 
    (z (lambda (p q) p))) 

Dies hat mir denken; Was genau sind Datenstrukturen? Wenn eine Sprache erstellt wird, werden Datenstrukturen als Abstraktionen implementiert, die durch Prozeduren aufgebaut werden? Wenn sie nur aus Prozeduren bestehen, was sind Prozeduren wirklich auf dem niedrigsten Niveau?

Ich denke, was ich wissen will ist, was am Ende der Abstraktionskette ist (es sei denn, es handelt sich um Abstraktionen den ganzen Weg hinunter). Ab wann wird es Hardware?

Answer 1

Der Trick ist, dass Sie sich nicht kümmern müssen. cons, cdr und car sind Abstraktionen und so ihre zugrunde liegende Implementierung sollte keine Rolle spielen.

Was Sie dort haben, sind sogenannte "Kirchenpaare", wir bauen alles aus Funktionen. In modernen Maschinen bauen wir alles aus Strings von 1s und 0s, aber eigentlich spielt es keine Rolle.

Nun, wenn Sie sich fragen, wie alle diese Abstraktionen in Ihrer speziellen Implementierung implementiert werden, hängt das ab. Aller Wahrscheinlichkeit nach springt Ihr Compiler/Interpeter hinter den Kulissen durch die Zuweisung von Zellen als dicht gepackte Zeiger (oder ähnlich) und verwandelt Ihre Funktionen in eine Kette von Nullen und Einsen, die den passenden Maschinencode bilden und diesen mit einem Zeiger verbinden seine Umgebung.

Aber wie gesagt, die ganze Schönheit dieser Abstraktionen zu bauen ist, dass Sie nicht als Benutzer zu kümmern haben :)

Answer 2

Es Abstraktionsketten mehrere Böden besteht. Abhängig von der zugrunde liegenden Aufgabe kann der Informatiker eine auswählen, die besser passt. Die gebräuchlichsten sind Turing Machine und Lambda Calculus.

Answer 3

Das Substrat am Ende der Abstraktionskette hängt von der Hardware ab, aber es wird wahrscheinlich eine Art Registermaschine sein, die eine Art nativen Befehlssatz hat.

SICP last chapter ist alles über diese Schicht. Das Buch präsentiert keine echte Hardware, aber eine abstrakte Maschine (ähem Schildkröten!) Maschine, die Art ähnelt, was tatsächlich passieren könnte ..., die in Scheme modelliert ist, nur für extra metacircular Spaß . Ich fand es schwer zu lesen, aber es lohnt sich.

Wenn Sie an solchen Sachen interessiert sind, können Sie auch Knuth ausprobieren.

Answer 4

Coole Frage!

Es wird Hardware, wenn jemand es an Anrufe an den Prozessor (CPU) übergibt. Wenn Sie ein Handbuch von einem Chiphersteller lesen müssen, um zu verstehen, wie Sie vorgehen, was Sie tun möchten, befinden Sie sich auf der Ebene, die Sie beschreiben.

chipset http://www.micro-examples.com/pics/087-PIC16-SECRET-OPCODE-instructionset.JPG

Hier ist ein Überblick über den Weg von der Physik zur Hardware an Benutzer-Code: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-002-circuits-and-electronics-spring-2007/video-lectures/lecture-1/ obwohl ich nicht glaube, es mit Lambda-Kalkül zu tun ist. (Aber Sie sagen nur, dass das die Frage inspiriert hat - es ist nicht die Frage an sich, oder?)

Es gibt einen Schritt, in dem die Person, die die Sprache schreibt, eine Schnittstelle zu Prozessoranweisungen hat, zB https://en.wikipedia.org/wiki/X86_instruction_listings || https://en.wikipedia.org/wiki/X86_calling_conventions.

Blick auf kernel programming oder denken über eingebettete Systeme (in einer Mikrowelle, auf dem Flügel eines Flugzeugs), ARMs, oder mobile Geräte-das sind die Dinge, die Menschen programmieren, die nicht-Laptop-Chipsätze haben.

Wer BLAS (lineare Algebra-Löser-Bibliotheken) schreibt, kommt manchmal auf diese Detailebene. Zum Beispiel https://en.wikipedia.org/wiki/Math_Kernel_Library oder https://en.wikipedia.org/wiki/Automatically_Tuned_Linear_Algebra_Software. Wenn sie sagen, dass das BLAS "abgestimmt" ist, was meinen sie? Sie reden davon, Fakten über Ihren Prozessor auszuschnüffeln und zu ändern, wie innere-innere-innere Schleifen ihre Entscheidungen treffen, um weniger Zeit mit der Art und Weise zu verschwenden, wie das physische Ding konfiguriert ist.

Wenn ich mich richtig erinnere, High-Level-Programmiersprachen (wie C;)) machen keine Annahmen über welches System sie so ausgeführt werden, auf sie Agnostiker Anrufe zu tätigen, die wie zehnmal laufen † langsamer als sie Wenn sie vorher wüssten, welche Art von Anruf zu machen ist. Jeden. Zeit. Dies ist die Art von Sache, die Sie verrückt machen könnte, aber es ist dieser klassische technische Kompromiss zwischen der Zeit des technischen Personals und der Leistung des Endbenutzers. Ich schätze, wenn Sie ein Kernel-Programmierer oder Embedded-System-Programmierer werden, können Sie all den verschwendeten Taktzyklen auf Computern auf der ganzen Welt ein Ende setzen - Prozessoren werden heiß, weil sie eine Menge unnötiger Hin- und Herbewegungen verschwenden. (Obwohl es eindeutig schlimmere Dinge gibt, die auf der Welt passieren.)

†: Ich habe einfach schnell gesucht, wie viel BLAS-Beschleunigungen sind und ja, es kann ein Faktor von 15 oder 20 sein. Also denke ich nicht Ich übertreibe, was ich über verschwendete Bewegung gehört habe. Übrigens, bei der Stromerzeugung läuft etwas ähnliches: Der letzte Schritt (die Turbine) bei der Stromerzeugung ist nur 20% effizient. Verliert nicht die ganze Verschwendung Sie nur verrückt ?! Zeit, Ingenieur zu werden. ;)

---

Ein cooles Projekt, das Sie überprüfen können, ist MenuetOS; jemand hat ein Betriebssystem in Assembler geschrieben.

Noch mehr coole Sachen zu sehen könnte this guy sein, der sagt, dass es eigentlich ziemlich einfach ist und Spaß zu lernen x86 Assemblersprache. (!)

punch card programmer http://blog.iqsdirectory.com/wp-content/uploads/files/punch-card%20operator.jpg

Sie auch wieder auf den alten Tage lesen, wenn es weniger Abstand zwischen Software und Hardware (zB Programmierung mit einem Lochkarte). Zum Glück haben die Leute "High-Level" -Sprachen geschrieben, die eher der Art und Weise sind, wie Menschen reden und denken, und weniger wie das Bewegen von Tape. Datenstrukturen sind vielleicht nicht die offensichtlichste Sache aus alltäglichen Konversationen, aber sie sind abstrakter als [lists a sequence of GOTO and STORE instructions...].

HTH