STGM in C++



  • Hollerö.

    Aus reinem Interesse versuche ich, eine Spineless (Tagless) G-Machine in C++ zu schreiben. Tagless wohl nicht so, weil das ja inzwischen nicht mehr so modern ist. Eigentlich wollte ich es in C schreiben weil ich reines C mit Lowlevel-Gefrickel besser kann, aber ein paar Lüfterjungen meinten, das was ich probieren will, ginge besonders gut mit C++: Ich wüsste gerne, ob das Gerücht, die STGM-Performance sei schlecht mit einem Referenzzähler, und besser mit einem kopierenden GC, wirklich stimmt, für das übliche Haskelloide Programm. Nun habe ich folgenden C++-Kot produziert. Ich nutze boost::variant weil ich davon ausgehe, dass das Leute die schlauer sind als ich gut optimiert haben. Und ich benutze std::shared_ptr, weil Referenzzähler. Das Programm selber tut ungefähr das, was man in Haskell machen würde mittels

    take 10 [1..]
    

    Also dies ist nun der Kot:

    #include <iostream>
    #include <memory>
    #include <functional>
    #include <boost/variant.hpp>
    #include <list>
    
    template<class T>
    class lazy_ptr {  
      using Tf = std::function<T()>;
      using C = boost::variant<T, Tf>;
      using Cp = std::shared_ptr<C>;
      Cp _content;
    
      class my_visitor : public boost::static_visitor<T&> {
      public:
        C& c;
        my_visitor(C& c) : c(c) {};
        T& operator() (Tf func) {
          auto t = func();
          c = t;
          return boost::get<T>(c);
        }
    
        T& operator() (T& t) {
          return t;
        }
      };
    
    public:
    
      lazy_ptr (Tf func) : _content(std::make_shared<C>(func)) {}
      lazy_ptr (T t) : _content(std::make_shared<C>(std::move(t))) {}
    
      T& operator* () {
        my_visitor q(*_content);
        return boost::apply_visitor(q, *_content);
      };
    
      T* operator-> () {
        return &**this;
      };
    
      using value = T;
      using creator = Tf;
    };
    
    template<class T>
    struct list {
      lazy_ptr<T> _car;
      lazy_ptr<list<T>> _cdr;
      list(lazy_ptr<T> car, lazy_ptr<list<T>> cdr) : _car(car), _cdr(cdr) {}
    };
    
    list<int> from (int n) {
      std::function<int()> car = [=]() { return n; };
      std::function<list<int>()> cdr = [=]() { return from(n+1); };
      return list<int>(car, cdr);
    }
    
    std::list<int> take (int n, lazy_ptr<list<int>> l) {
      std::list<int> ret;
      for (--n; n >= 0; --n) {
        lazy_ptr<int> pcar = l->_car;
        int k = *pcar;
        ret.push_back(k);
        lazy_ptr<list<int>> pcdr = l->_cdr;
        l = *pcdr;
      }
      return ret;
    }
    
    int main (void) {
      auto q = from(0);
      auto k = take(10, q);
      for (int x : k) {
        std::cout << x << " ";
      }
      std::cout << std::endl;
    }
    

    Nun gibt es zwei Probleme: Zum Einen komme ich aus der Compilerbau-Schiene, und habe keine wirkliche Ahnung von feinen C++-Gepflogenheiten. Zum Anderen würde man, wenn man in C++ laziness wöllte, alles in eine Wrapperklasse packen, aber ich will ja nicht laziness in C++, ich will im Grunde die Effizienz von etwas testen, was eigentlich nicht so ganz dem C++-Paradigma entspricht. Entsprechend geht es mir nicht darum, irgendwas konkretes zu erledigen, sondern ich will nur eine möglichst portable Möglichkeit haben, ein paar Paradigmen zu testen, und laut einem Lüfterjungen eignet sich C++ für deren Implementierung.

    Somit fände ich Kommentare und Verbesserungsvorschläge oder Fallstricke über die ich stolpern könnte nett.



  • Und wie würde man das in Common Lisp machen?



  • hmmmmmmmm schrieb:

    Und wie würde man das in Common Lisp machen?

    Common Lisp ist eine highlevel-Sprache und hat einen vorgegebenen Garbage Collector. Den könnte man zwar unterminieren, bzw. abschalten, aber das ist komisch. Ansonsten würde man es da aber genauso machen: Man würde vermutlich Referenzen nehmen, und dann mittels typep schauen ob es sich um ein fertiges objekt handelt, oder eine Funktion die man aufrufen kann. Sollte nicht so schwer sein.



  • Mach mal Beispiel-Kot. 😋 🕶



  • hmmmmmmmm schrieb:

    Mach mal Beispiel-Kot. 😋 🕶

    Na gut, meinetwegen:

    (defmacro lazy-deref (ptr)
      `(cond ((typep ,ptr 'function)
    	  (setf ,ptr (funcall ,ptr))
    	  ,ptr)
    	 (t ,ptr)))
    
    (defun range (n)
      (declare (type integer n))
      (assert (> n 0))
      (cons n (lambda () (range (1+ n)))))
    
    (defun take (n l)
      (declare (type integer n))
      (cond ((zerop n) '())
    	(t (let ((c (lazy-deref l)))
    	     (cons (car c) (take (1- n) (cdr c)))))))
    

    Aber nun bitte zurück zu C++.



  • Haskell > Common Lisp 🕶



  • hmmmmmmmm schrieb:

    Haskell > Common Lisp 🕶

    Hm. Also eine STGM in Haskell zu implementieren halte ich für schwer.

    Wie gesagt, ich gebe C++ hier mal ne chance, aber es scheint nicht sonderlich gut zu performen. Und ich wüsste gerne wieso.


Log in to reply