Projektvorstellung: MVar - low-level Bibliothek für Nebenläufigkeit

[Rolf B]

Hallo 1unitedpower,

ich habe mir das jetzt mal näher angeschaut, und, nein, ich verstehe den Sinn noch nicht so ganz. Es sei denn, der Zweck ist es, genau zwei parallel laufende Aktionen irgendwie zu syncen.

Unter Nebenläufigkeit verstehe ich zwei Threads, die parallel laufen und bei dem der eine den Output des anderen konsumiert. Das ergibt in JavaScript oder TypeScript grundsätzlich nicht den meisten Sinn, weil JavaScript per Definition single threaded ist. Das lässt sich mit Workern lösen, die es im Browser und auch in Node.js gibt. Befasst habe ich mich damit noch nicht. Die Implementierungen scheinen ähnlich, aber nicht gleich, und sie sind Event-basiert, nicht Promise-basiert. Ob eine Lib, die Browser und Node abstrahiert, sinnvoll oder nötig ist, weiß ich nicht.

Deine MVars scheinen aber mit Workern nichts am Hut zu haben, insbesondere kannst Du eine MVar nicht dazu bringen, auf Messages von echten Workern zu lauschen (bzw. dafür müsste man einen eigenen Adapter zimmern).

Eine andere Form von Nebenläufigkeit sind Generatorfunktionen. Hier ist es aber so, dass der Generator immer erst dann weiterläuft, wenn der Konsument das nächste Element anfordert. Ein Generator, der das nächste Element schonmal in einem Worker ermittelt, während der Konsument das vorige Element noch verarbeitet, das wär was cooles. Kann man das mit MVars realisieren?

Dein Einsatzbeispiel zeigt, wie man mehrere Eventquellen in einen gemeinsamen Event-Strom steckt (bzw. Actions in deinem Fall), um sie nachher per if wieder auseinanderzuklamüsern. Ja, ich verstehe, das ist eine einfache Demonstration, wie man MVars benutzen kann. Aber ein Beispiel, wo die Motivation klarer ist, wäre schon gut.

Dein API und deine Implementierung werfen bei mir ebenfalls Fragen auf. Nimm das bitte nicht als "Oh Mann ist das ein Scheiß", sondern einfach als Liste von Unklarkeiten, die ich beim Lesen des Codes empfunden habe.

• Warum MVar.newEmpty() und MVar.new(x)? Das ist doch ein Konstruktor. Warum machst Du den vorhandenen Konstruktor private und klemmst statische Methoden davor? Das Verpacken in ein Array und das Bereitstellen der leeren TaskQueue kann der Konstruktor auch erledigen.
• Mir ist unklar, was MVar tut, wenn ich zwei put() mache ohne dass ein take() gelaufen ist. Kann MVar das?
• deine Actionqueue ist merkwürdig. Warum verwendest Du keine Polymorphie? Statt dessen fragst Du ab, ob das Actionelement read, take oder swap enthält. Deine Actions sind private, also dürfen sie auch private Dinge tun. Siehe meinen Codevorschlag weiter unten.
• swap() tut nicht was sein Name verspricht. Es tauscht nicht. Es stellt den Austauschwert ans Ende der putQueue, statt den gelesenen Wert zu ersetzen. Der Name passt nicht.
• Die Promise-Implementierung und die Do-It-Now Implementierung von Swap unterscheiden sich in der Reihenfolge der Teilaktionen. Nach reiflicher Überlegung bin ich zwar drauf gekommen, dass das egal sein sollte, aber besserer Stil wäre, die Reihenfolge gleich zu halten (lese queue, schreibe queue, resolve Promise)
• Warum wirft tryTake eine Exception? Try-Funktionen haben doch gerade den Sinn, Exceptions zu vermeiden. Und da JavaScript singlethreaded konzipiert ist: Warum gibt's tryTake() überhaupt? Eine Abfolge von isEmpty() und take() ist nicht unterbrechbar, weil Threads nur per Message kommunizieren und es keinen thread-übergreifenden Speicher gibt. Warum also eine künstliche und scheinbar atomare tryTake Methode?
• Warum heißen die beiden überhaupt take und read? Unter read versteht man normalerweise eine konsumierende Funktion. Eine nichtkonsumierende Lesefunktion sollte peek() heißen. Und weil eine MVar nicht viel anderes als eine Queue ist, wären enqueue() und dequeue() wohl die besseren Namen für put() und take(), denn das sind die bekannten Operationsnamen auf dem ADT Queue.

Hier nun der Vorschlag für eine Implementierung mit Polymorphie in der put-Methode und weitgehender Abstraktion des Queue-Handlings. Ich habe deinen Stil, Temp-Variablen zu bilden, beibehalten. Man könnte drauf verzichten und etliche Methoden zu Einzeilern machen (und sich dabei Debug-Hürden einfangen). Dafür habe ich es so gemacht, dass die drei Handler-Funktionen sowohl die Promise- als auch die Direktimplementierung bilden. Ich weiß nur nicht, wie man dafür die Typisierung in Typescript angeben muss. Die performAction Methode fiel mir zum Schluss ein, als ich bemerkte, dass read, take und swap nur noch aus Boilerplate-Code bestanden, die den Action-Handler entweder direkt oder via Promise aufriefen.

Keine Ahnung ob's funktioniert. Einiges an TypeScript-Spezifika wirst Du nachtragen müssen - ich kann Typescript eigentlich gar nicht und habe nur blindlings imitiert, was ich bei Dir gesehen habe.

  public put (y: a): void {
    this.putQueue.push(y)
    while (this.taskQueue.length !== 0 && this.putQueue.length !== 0) {
      const nextTask = this.taskQueue.shift()!
      nextTask();
    }
  }

  public read (): Promise<a> {
    return enqueueOrPerformAction( resolve => this.handleReadTask(resolve) )
  }

  public take (): Promise<a> {
    return enqueueOrPerformAction( resolve => this.handleTakeTask(resolve) )
  }

  public swap (swapValue: a): Promise<a> {
    return enqueueOrPerformAction( resolve => this.handleSwapTask(resolve, swapValue) )
  }

  // Bekommt eine Function, die einen Ding vom Typ wie Promise<a>.resolve 
  // erhält und auch zurückgibt. 
  // Gibt selbst ebenfalls so ein Ding zurück.
  private enqueueOrPerformAction(handler: ???) : Promise<a> {
    if (this.putQueue.length === 0) {
      return new Promise<a>(resolve => this.taskQueue.push(_ => handler(resolve)))
    } else {
      return handler(Promise<a>.resolve, data)
    }
  }

  private handleReadTask(resolve: ???): ??? {
    const nextValue = this.putQueue[0]!
    return resolve(nextValue)
  }

  private handleTakeTask(resolve: ???): ??? {
    const nextValue = this.putQueue.shift()!
    return resolve(nextValue)
  }

  private handleSwapTask(resolve: ???, swapValue: a): ??? {
    const nextValue = this.putQueue.shift()!
    this.putQueue.push(swapValue)
    return resolve(nextValue)
  }

Das Handling von Swap finde ich übrigens bemerkenswert komplex. Ich kann auf einer leeren MVar zweimal Swap aufrufen. Beide gehen erstmal in die Taskqueue. Nun schiebe ich einen Wert in die MVar und der Pingpong geht los. Der erste Swap liest den Wert und schreibt einen neuen. Der triggert den anderen Swap, der wiederum den ersten Swap triggert. Da JS je nach Implementierung keine Tail-Rekursion macht, und in deiner Put-Methode wegen der while-Schleife auch keine Tail-Rekursion greifen wird, läuft das Ratzfatz auf einen Stackoverflow.

Rolf