Projekte, an denen sich jeder Programmierer versuchen sollte (2019)

 (austinhenley.com)
7 Punkte von GN⁺ 2023-12-27 | 1 Kommentare | Auf WhatsApp teilen
  • Wenn es schwerfällt, ein Side-Project auszuwählen, sind Projekte wie Texteditor, 2D-Spiel, Compiler oder ein Mini-Betriebssystem ein guter Einstieg, weil man beim wiederholten Bauen den Lernhorizont stark erweitert
  • Ein Texteditor vermittelt Datenstrukturen und Abstraktion, indem man Dokumentenspeicherung, Cursorverhalten, Undo/Redo und Zeilenumbruch selbst implementiert
  • Selbst ein einfaches 2D-Spiel wie Space Invaders zeigt die Grundstruktur der Spieleprogrammierung: Rendering, Eingabeverarbeitung, Game Loop, Verwaltung von Objektzuständen, Gegner-KI, Sound, Shader und Networking
  • Ein Tiny-BASIC-Compiler und ein Mini-Betriebssystem behandeln jeweils Low-Level-Konzepte direkt, etwa Lexing, Parsing, semantische Analyse und Codegenerierung bzw. Cross-Compiling, Bootloading, Speicherverwaltung und Scheduling
  • Tabellenkalkulationen und Konsolen-Emulatoren verbinden die Schwierigkeit der vorherigen Projekte und erweitern sie bis zur Stufe, auf der man sogar eine virtuelle Maschine baut, die echtes Verhalten nachahmt

Projekte, die man immer wieder bauen kann

  • Wenn man ein Side-Project braucht oder eine neue Programmiersprache bzw. ein neues Framework lernen möchte, kann man aus demselben Projekt bei jedem neuen Versuch etwas anderes mitnehmen
  • Die empfohlenen Projekte unterscheiden sich in Schwierigkeitsgrad und Lernbereichen
    • Texteditor: Datenstrukturen, Cursorverhalten, Undo/Redo, Bildschirmdarstellung
    • 2D-Spiel: Rendering, Eingabeverarbeitung, Game Loop, Objekt- und Zustandsverwaltung
    • Compiler: Lexing, Parsing, semantische Analyse, Codegenerierung
    • Mini-Betriebssystem: Booten, Speicherverwaltung, Scheduling, Dateisystem
    • Tabellenkalkulationen und Konsolen-Emulatoren: verbinden die Konzepte der vorherigen Projekte in einer größeren Struktur

Texteditor

  • Ein Texteditor ist ein Werkzeug, das man täglich benutzt, aber wenn man ihn ohne eine grundlegende Textbox-Komponente direkt implementiert, muss man sich mit den Details von Cursorbewegung, Auswahl, Einfügen und Löschen befassen
  • Die größte Aufgabe ist die Art, wie das Textdokument im Speicher abgelegt wird
    • Ein einfaches Array hat schlechte Performance, wenn Text an einer Stelle eingefügt wird, die nicht am Dokumentende liegt
    • Zum Vergleichen bieten sich Array, rope, gap buffer und piece table an
  • Ein Cursor bewegt sich nicht einfach nur nach oben und unten
    • Wechselt man auf eine kürzere Zeile, geht er zunächst an die mögliche Position und versucht später, wenn wieder eine ausreichend lange Zeile kommt, zur ursprünglichen Spalte zurückzukehren – ein Verhalten mit gemerkter Spalte
  • Nach dem Basis-Editor kann man Undo/Redo und Zeilenumbruch ergänzen
    • Bei Undo/Redo vergleicht man Entwürfe wie Arrays früherer Zustände, das memento- und das command-Muster
    • Zeilenumbruch trennt die visuelle Darstellung von Textzeilen von ihrer Darstellung im Speicher
  • Referenzen

2D-Spiel – Space Invaders

  • Selbst ein einfaches Spiel verlangt eigene Datenstrukturen und Design Patterns
  • Nutzt man statt einer großen Game Engine eine grundlegende 2D-Grafikbibliothek wie SDL, SFML oder PyGame, werden die interessanten Teile nicht verborgen
  • Das Spiel erzeugt den Eindruck von Bewegung, indem es den Bildschirm leert und alle Elemente schnell neu zeichnet
  • Der tatsächliche Ablauf ist eine Struktur, in der innerhalb einer Game Loop Zeichnen, Einlesen von Benutzereingaben und Verarbeitung der Spiellogik wiederholt werden
  • Bei der Eingabeverarbeitung muss man Details wie erstes Drücken einer Taste oder Maustaste, Gedrückthalten, Loslassen und Doppelklick berücksichtigen
    • Wenn man nur ständig Eingaben prüft, bleibt der Rest des Spiels stehen
  • Auch Spielobjekte und Zustandsverwaltung muss man selbst behandeln
    • Zum Erzeugen dynamisch wachsender Gegnerzahlen hilft das factory pattern
    • Für Gegner-KI kann man Zustandsmaschinen einsetzen
  • Nach dem Grundspiel kann man ein Titelmenü, einen Game-Over-Bildschirm, eine Verarbeitung für gleiche Geschwindigkeit auf verschiedenen Rechnern und interessantere Gegner-KI ergänzen
  • Ausgebaut lässt sich das bis zu Shader-Effekten, Sound und Online-Multiplayer erweitern
  • Referenzen

Compiler – Tiny BASIC

Mini-Betriebssystem

  • Algorithmen und Datenstrukturen aus Betriebssystemen wirken im Unterricht oft abstrakt oder nutzlos, lassen sich aber auch auf viele andere Bereiche anwenden, etwa Spiele oder Modelle zur Vorhersage menschlichen Verhaltens
  • Wenn man sie selbst implementiert, versteht man viel tiefer, was im Inneren eines Betriebssystems geschieht
  • Wegen der Hardware-Abhängigkeit gibt es eine höhere Einstiegshürde und eine steilere Lernkurve, aber mit Büchern oder Tutorials kann man ein bootfähiges OS bauen, das eigene Programme ausführt
  • Zu den Lerninhalten gehören
  • Referenzen

Anspruchsvollere Projekte: Tabellenkalkulationen und Konsolen-Emulatoren

  • Eine Tabellenkalkulations-Anwendung wie Excel verbindet die Aufgaben eines Texteditors mit denen eines Compilers
    • Man muss Zellinhalte im Speicher darstellen
    • Man muss einen Interpreter für die in Formeln verwendete Programmiersprache implementieren
  • Referenzen zu Tabellenkalkulationen
  • Ein Emulator für Videospielkonsolen vereint die Schwierigkeiten aus Compiler-, Betriebssystem- und Game-Engine-Implementierung in einem Projekt
  • Um eine echte Konsole zu emulieren, muss man eine virtuelle Maschine schreiben, die sich wie CPU und andere Hardware-Komponenten verhält
    • Auf dieser virtuellen Maschine können dann Spiele für die betreffende Konsole laufen
  • Als Einstieg wird empfohlen, statt einer echten Konsole die einfachere virtuelle Konsole CHIP-8 zu emulieren
  • Auch NES, SNES, Gameboy und Gameboy Advance lassen sich emulieren, und es gibt dafür recht viele Dokumente und Open-Source-Emulatoren, aber jede Konsole hat interessante Eigenheiten
    • Bestimmte Spiele können von undokumentierten Bugs oder Funktionen bestimmter Hardware abhängen
  • PICO-8 ist zu einer profitablen „fantasy“-Konsole geworden
  • Referenzen zu Emulatoren

Zusätzlich vorgeschlagene Projekte

  • Über Hacker News, Reddit, Twitter und E-Mail kamen weitere Projektideen zusammen
    • Eine Datenbank von Grund auf
    • Ein Raytracer
    • Ein MS-Paint-Klon
    • Ein Vektorgrafik-Editor
    • Ein Bilddecoder
    • Eine Chatroom-Web-App
    • Ein Rechner für Stellen von Pi
    • Allgemeine Terminal-Utilities wie grep
    • FTP-Client und -Server

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-12-27
Hacker-News-Meinungen

  • Einen Texteditor, Compiler, ein Betriebssystem oder einen Raytracer zu bauen kann einen zu einem besseren Programmierer machen, aber nicht unbedingt zu einem besseren Software Engineer.
    Im Gegenteil: Man könnte sich dadurch die katastrophale „Not Invented Here“-Doktrin aneignen und im Software Engineering sogar schlechter werden.
    Hacker sind besessen von Hochtheorie wie Big-O, Datenstrukturen und HoTT, aber über Dinge, die für echtes Engineering unverzichtbar sind – „entscheiden, was man selbst baut und wofür man eine Library nutzt“, „gute Libraries und Frameworks erkennen“, „beurteilen, wo sich Optimierung lohnt“, „Code schreiben, der auch Jahre später noch lesbar ist“, „ein Projekt als großes komplexes System einschließlich Software- und Nicht-Software-Abhängigkeiten betrachten“ – wird kaum diskutiert oder geübt.
    Als alternative Aufgabe schlage ich daher eine Web-Suchmaschine vor. Algorithmen zum String-Matching und dergleichen haben andere bereits erledigt, darum muss man sich nicht kümmern; man kann am Anfang einfach „nur“ eine tatsächlich funktionierende Suchmaschine samt Crawler bauen, selbst wenn sie nur einen Teil des Webs und einen gleichzeitigen Nutzer unterstützt.

    • Ich sehe nicht, warum gerade eine Suchmaschine in besonderem Maß „echte Engineering-Fähigkeiten“ wie die Auswahl von Libraries oder das Erkennen von Optimierungsmöglichkeiten erfordern sollte.
      Mit einem Texteditor, Compiler, Betriebssystem oder Raytracer kann man all diese Tätigkeiten genauso trainieren.
      Aus der Perspektive von jemandem, der an einem Raytracer gearbeitet hat, der in mehreren Spielfilmen verwendet wurde: Die oben genannten Punkte trafen auf dieses Projekt allesamt zu.
      Am Ende ist es eher der Unterschied, ob man etwas Kleines und Spaßiges macht oder ob man die seelenzerfressenden Einschränkungen, für die man in der Firma bezahlt wird, unverändert übernimmt und sich damit den Spaß nimmt.
    • Dieser Rat klingt vernünftig, aber es gibt ein Problem, wenn man Software nur aus vorbereiteten Bausteinen baut.
      Erstens sind solche fertigen Bausteine meistens deutlich häufiger schlecht als gut; die daraus entstehende Software spiegelt diese Schlechtigkeit wider, und das Leben besteht dann nicht darin, Software zu benutzen, sondern diese schlechten Dinge zu warten und zu besänftigen.
      Zweitens begrenzen sie, selbst wenn die Qualität der Bausteine gut ist, die Arten von Software, die man bauen kann. Idealerweise stellt man sich das gewünschte Verhalten vor, schreibt Software, damit sie genau das tut, und baut dabei die nötigen Bausteine.
      Wenn man nur fertige Bausteine verwendet, lässt sich ein großer Teil wirklich guter Software gar nicht bauen; meiner Meinung nach ist das auch der Grund, warum es um uns herum nicht viel wirklich gute Software gibt.
      Wenn man „Software baut, die fast genauso ist wie das, was man immer schon gesehen hat“, trifft das zweite Problem weniger zu, und auch das erste kann beherrschbar sein, weil man hauptsächlich den Happy Path nutzt. Aber solche Software wird bald nicht mehr von Menschen, sondern von KI benutzt werden.
    • Das ist so ähnlich, als würde man einem Musikschüler sagen, er solle keine Tonleitern oder Etüden üben, weil man im Orchester noch andere Fähigkeiten braucht.
      Solche Fähigkeiten sind ebenfalls wichtig, aber irgendwann muss man Grundfertigkeiten aufbauen, und ein besserer Programmierer zu werden hilft ganz sicher auch bei der gesamten oben genannten Palette an Fähigkeiten.
    • Im Artikel war von Programmierern die Rede, nicht von Software Engineers.
      Persönlich ist Software Engineering für mich das, was man macht, um Rechnungen zu bezahlen; Programmieren ist das, womit ich angefangen habe, weil es Spaß macht.
      Die Projekte in diesem Artikel sind die Art von Dingen, die ich, wenn ich Zeit hätte, zum Spaß ausprobieren würde.

  • Aus Sicht von UI/Web würde ich neben Tabellenkalkulationen, die sehr nützlich sind, um Datenflusssysteme zu verstehen, Folgendes empfehlen:
    Wer mit Unity oder Unreal ein einfaches Videospiel baut, versteht Performance-Einschränkungen in Spielen, bei denen 30–60 fps wichtig sind; das hilft auch dabei, schnelle Interfaces an anderen Stellen zu bauen, einschließlich im Web.
    Ein einfaches JavaScript-Framework ähnlich wie React zu bauen hilft, Datenfluss und Event-Handling zu verstehen.
    Wer selbst eine HTTP-Library baut, die XMLHTTPRequest kapselt, versteht von Grund auf, wie HTTP-Requests gesendet und gelesen werden – auch wenn es heute fetch gibt –, was später beim Debugging von CORS-Problemen oder OPTIONS-Requests hilft.

    • Für diesen Zweck könnte Godot eine bessere Alternative als Unity oder Unreal sein. Man muss sich nicht nur nicht auf eine proprietäre Lizenz einlassen, sondern kann auch sehen, was intern passiert.

  • Das wurde damals ebenfalls diskutiert.
    Challenging projects every programmer should try - https://news.ycombinator.com/item?id=21790779 - Dec 2019 (297 comments)
    Es gibt auch einen verwandten Artikel.
    More challenging projects every programmer should try - https://news.ycombinator.com/item?id=25489879 - Dec 2020 (223 comments)

    • Der externe Link im zweiten Artikel gibt einen 404 zurück.

  • +1 für ein Mini-Betriebssystem.
    Anwendungsentwickler sind auf viele Betriebssystemfunktionen wie Speicherverwaltung und Dateisysteme angewiesen, und irgendwann fragt man sich: „Wie funktionieren diese Dinge eigentlich im Hintergrund?“
    Deshalb habe ich in meiner Freizeit mit xv6 (https://github.com/mit-pdos/xv6-public) herumgespielt.
    Es ist etwas völlig anderes, in einem Lehrbuch verschiedene Prozess-Scheduling-Algorithmen zu lernen, als sie selbst zu implementieren, und ich habe viel gelernt.
    Als Mobile-App-Entwickler ist die Wahrscheinlichkeit, dass dieses Wissen für meine Arbeit relevant wird, nahezu null, aber es macht definitiv Spaß.

  • Ein 2D-Spiel ohne Engine zu entwickeln, war die demütigendste Erfahrung, die mir klar gemacht hat, wie absurd schnell Computer geworden sind.
    Selbst wenn man etwas tut, von dem man überzeugt ist, dass es viel zu langsam sein wird: Schon auf dem Game Boy schafft man eine Million Operationen pro Sekunde, also läuft es einfach. Eine Million ist eben größer, als man denkt.
    Man denkt: „Moment, du suchst und zeichnest jedes Sprite jedes Mal neu? Keine clevere Differenzberechnung, die nur weiß, was geändert werden muss, und kein zweiter Buffer, der auf den vorherigen Frame Bezug nimmt, um Arbeit zu sparen?“ Und dann ist man noch erstaunter, wenn man viel komplexere Spiele sieht, die solche Techniken tatsächlich erst später einsetzen.

    • Auch früher gab es sowohl auf Anwendungs- als auch auf Hardwareseite interessante Tricks, die bei solchen Problemen halfen.
      Ein Sprite-Atlas ist zum Beispiel eine typische Art, wie solche Datenstrukturen genutzt werden. Es gibt keinen Grund, mehrere Sprites, die normalerweise auf vorhersehbare Weise gerendert werden, jedes Mal hochzuladen; man lädt einfach ein großes Bild hoch und sampelt einen Teil davon.
      Nach heutigen Maßstäben stimmt das. Günstige handelsübliche Hardware, sogar ohne Gaming-PC, kann fast alles von vor etwa 15 Jahren mit brachialem Rendern bewältigen, bei dem die Szene einfach gezeichnet und neu gezeichnet wird.
    • Ich habe auf dem TRS-80 Color Computer mit dem Entwickeln von 2D-Spielen angefangen, und das hat mir ein gutes Grundverständnis von Computern vermittelt.
      Da es nur reine Hardware und Assembly gab, musste man Grafik, Sound, Eingabe, Speicherverwaltung usw. komplett von Hand erledigen.
      Eine vereinfachte Umgebung, in der Programmieranfänger all diese Dinge anfassen und ein 2D-Spiel bauen können, ohne die übermäßige Last, es überhaupt zum Laufen zu bringen, wäre meiner Meinung nach ein idealer Einstieg.

  • Wenn man glaubt, man brauche das Factory Pattern, um Space Invaders zu bauen, läuft etwas falsch.
    Ich halte es für äußerst unwahrscheinlich, dass im Original solche Designkonzepte steckten.

    • Das ist das Ergebnis von 30 Jahren objektorientierter Programmierung und Design Patterns.
      Wenn das Gehirn einmal davon infiziert ist, beginnt es, Wege zu finden, die Infektion weiterzuverbreiten.
    • Nirgendwo im Artikel wird gesagt oder angedeutet, dass man für die Implementierung von Space Invaders das Factory Pattern braucht.
      Haben wir unterschiedliche Artikel gelesen?

  • Ich würde gern etwas deutlich Physischeres ausprobieren, etwa eine präzise Simulation der Flugdynamik von Robotern, autonom gesteuerten Drohnen oder Raumfahrzeugen mit programmierbaren GNC-Parametern.
    Ich habe „Fundamentals of Astrodynamics“ von Bate, Mueller und anderen und würde in dieser Urlaubssaison gern etwas damit machen.
    Bei den übrigen Dingen gehe ich von Simulationen aus, weil sie sonst teuer werden dürften. Mich interessiert die GNC-Seite von Robotern wirklich sehr, und ich würde mich über gute Materialempfehlungen freuen.

    • https://ksp-kos.github.io/KOS/ Kerbal Space Program simuliert Aerodynamik vielleicht nicht so realistisch, wie du es dir wünschst, aber viele Leute scheinen Spaß daran zu haben, dort GNC-Software zu schreiben.
    • Ein selbstbalancierender Zweiradroboter wäre wahrscheinlich ein interessantes und vergleichsweise sicheres Projekt.
      Ich meine so etwas wie einen Segway, der an einer Stelle stehen kann, ohne umzufallen oder vom Tisch zu fliegen.
      Man bräuchte wohl einen Mikrocontroller, eine IMU, Stepper-Motorcontroller, Motoren, LEGO-Räder und vielleicht ein Stück Holz.
      Ich habe das selbst nicht gemacht, also können meine Vermutungen ziemlich danebenliegen.
    • Ich bin neugierig, was du mit „Fundamentals of Astrodynamics“ vorhast.
      Ich würde gern mehr darüber hören, worum es in dem Buch geht und welche Projekte man damit angehen könnte.
    • Geht mir genauso. Fast alle meine persönlichen Projekte haben eine Hardware-Komponente.
      Nachdem man den ganzen Tag mit Software zu tun hatte, ist es wirklich schön, auf ein physisches Objekt hinzuarbeiten.

  • Ein kleiner Spielzeug-Raytracer ist meiner Meinung nach ebenfalls eine großartige Aufgabe.
    Es reicht, Kugeln und ein paar Lichtquellen zu verarbeiten, diffuse und spiegelnde Reflexionen zu behandeln und Bitmap-Grafik auszugeben.
    Solange man es nicht zu sehr ausufern lässt, kann das ein Projekt mit relativ gut begrenztem Umfang sein.

  • Eine interessante Liste, und auch wenn es von persönlicher Neigung und Situation abhängt, ist sie ein guter Ausgangspunkt, wenn man nach Ideen sucht.
    Ich würde nicht so weit gehen zu sagen, dass jeder Programmierer irgendetwas davon gemacht haben sollte; ich schreibe nur auf, wofür ich mich persönlich entschieden habe.
    Auf dem Sinclair ZX Spectrum habe ich einen sehr groben Noteneditor und Tracker gebaut, und als 2D-Spiel ein Space Invaders mit nur einem einzigen Eindringling.
    Der Computer gehörte nicht einmal mir. Auf meinem ersten eigenen Computer, einem 386er, habe ich einen Huffman-Kompressor, einen B-Tree-Index, der schneller war als DBase/Clipper, einen objektorientierten Formular-Generator und mehrere DOS-Hintergrundprogramme gebaut; eines davon wurde später im Installationsprozess eines großen Unternehmens verwendet.
    Ein paar Jahre später baute ich einen E-Mail-Checker für Dial-up, einen handgeschriebenen Parser für Syntax-Highlighting und sogar etwas Tabellenkalkulationsähnliches, und das mache ich bis heute. Ich bin mir sicher, dass ich noch einiges ausgelassen habe.

  • Gute Liste. Es wäre schön, sie als lebendige Liste zu pflegen, damit sie sich mit der Zeit weiterentwickeln kann.
    Ich würde gern zwei Dinge ergänzen.
    Wenn man ein leichtgewichtiges memcached baut, braucht man eine Mischung aus grundlegenden Algorithmen und guter System-Design-Praxis. Es ist ein „einfaches“ Problem, aber man muss es aus vielen Blickwinkeln gut durchdenken, etwa Invalidierung, Nebenläufigkeit und Speicherverwaltung.
    Auch ein eigenes Docker zu bauen, ist eine gute Idee. Es ist nicht so kompliziert, wie es klingt, und bietet die Gelegenheit, Grundlagen der Betriebssystemprogrammierung zu verstehen, die heutige Engineers in ihrer täglichen Arbeit nicht mehr oft nutzen.