ADTler ve sınıflar: bir örnek

February 21, 2013 - Tagged as: haskell, tr.

Bu yazı, bir önceki yazım gibi, yine bir mail için yazıldı. Birkaç düzenleme ve eklemeden sonra blog yazısı olarak yayınlıyorum.

Bir programlama dili meraklısı olarak sık sık yorumlayıcılar ve nadiren derleyiciler yazıyorum. Derleyici/yorumlayıcı yazarken çok sık yapılan işlemlerden biri şudur:

Programda(derleyici/yorumlayıcıda) kod üzerinde çalışabilmek için son kullanıcı tarafından metin olarak girilmiş kodun üzerinde çalışılabilinecek bir veri yapısına dönüştürülmesi gerekir. Buna “parsing” işlemi diyoruz ve yaptığı iş kısaca metni alıp, abstract syntax tree(AST) dediğimiz bir çeşit ağaç yapısına dönüştürmektir.

Bu aşamadan sonra elimizde bir ağaç yapısı olmuş olur. Fakat burdaki ağaç yapısını veri yapıların dersinde gösterilen “binary tree” vs. yapılarla karıştırmamak lazım, burda çok çeşitli nodelar oluyor ve her bir node farklı özelliklere sahip, her birine ayrı muameleler yapılacak oluyor. (kod örnekleri vereceğim)

Bir yorumlayıcı/derleyicinin bu ağaç yapısı üzerinde defalarca gezinmesi gerekir ve genelde her bir gezinmede farklı işlemler yapılır. Bir tur sonrası ağaç üzerinde değişiklikleri yapılabilir ve bir sonraki turda bu yeni ağaç üzerinden devam edilir vs.

Örnek: Statically typed bir dil için yorumlayıcı yazdığımızda, ilk başta type checker ağaç üzerinde gezerek programın type-safe olduğundan emin olur. Program type-safe ise, ağacın biraz değiştirilmiş hali üzerinde(örneğin type annotationları silinmiş, veya ağacın tagless bir hali) yorumlayıcı çalışır.

Derleyicilerde ise ağaç çok daha fazla sayıda adımlanır. Her bir adımlamada ağaç yapısı değiştirilebilir.¹

Yani kısaca problem şu: Elimde farklı tiplerde ağaçlar var(örnek: tip bilgilerini içeren, type checking/inference için oluşturulmuş bir ağaç ve tip bilgilerinin büyük oranda silindiği, yorumlama/derleme için kullanılan bir ağaç vs.), bu ağaçlar üzerinde turlar atacağım fakat tur atarken farklı işler yapacağım.

Katkı yaptığım bir derleyici kodundan birkaç örnek vereceğim: Fay, bir Haskell alt kümesinden JavaScript’e derleyici.

compileExp fonksiyonu, Exp ağacı üzerinde gezinir çıktı olarak JsExp (yine başka bir ağaç) üretir. Bu bir ağaç üzerinde gezinip farklı işlemler yapıp farklı bir ağaçlar üreten fonksiyonlara bir örnek.

Optimizer modulü çeşitli ağaçlar üzerinde gezinip başka ağaçlar üreten 13 tane fonksiyondan oluşur ve bunların 5-6 tanesi JsStmt ağacını dolaşır. Bu da aynı ağaç üzerinde gezinip farklı işlemler yapan fonksiyonlara örnek.

Algebraic data typelara ve pattern matchinge sahip olan fonksiyonel dillerde(yani belki de tüm statically typed fonksiyonel dillerde) bunu yapmanın bir yolunu göstermek için hemen hiçbir işlevi olmayan çok basit bir aritmetik ifade dili oluşturalım:

data Exp
    = Add Exp Exp
    | Mul Exp Exp
    | Number Float

Bu kadar işlevsiz bir dil olamaz. Şimdi bu ağaç üzerinde iki farklı işlem yapan iki fonksiyon:

run :: Exp -> Float
run (Add e1 e2) = run e1 + run e2
run (Mul e1 e2) = run e1 * run e2
run (Number f)  = f

run programı çalıştırıp sonucu dönüyor.

stringOfExp :: Exp -> String
stringOfExp (Add e1 e2) =
    concat [ "(", stringOfExp e1, " + ", stringOfExp e2, ")" ]
stringOfExp (Mul e1 e2) =
    concat [ "(", stringOfExp e1, " * ", stringOfExp e2, ")" ]
stringOfExp (Number f) = show f

stringOfExp ise programın string halini dönüyor. Örnek:

ghci> let prog1 = Add (Number 10) (Mul (Number 20) (Add (Number 30) (Number 40)))
ghci> run prog1
1410.0
ghci> stringOfExp prog1
"(10.0 + (20.0 * (30.0 + 40.0)))"

Yarın ağaca yeni bir node eklediğimde ağaç üzerinde çalışan tüm fonksiyonları güncellemem gerekecek.

Herkes için son derece basittir sanıyorum. Şimdi aynısını ADT’lara sahip olmayan, OO bir dil ile yazalım.

class Exp { // base class for expressions
public:
  virtual ~Exp() {}
};

class AddExp : public Exp {
public:
  const Exp * const e1, * const e2;
  AddExp(const Exp * const e1, const Exp * const e2)
    : e1(e1), e2(e2) {}
};

class MulExp : public Exp {
public:
  const Exp * const e1, * const e2;
  MulExp(const Exp * const e1, const Exp * const e2)
    : e1(e1), e2(e2) {}
};

class Number : public Exp {
public:
  const float f;
  Number(const float f) : f(f) {}
};

Örnek programımız da şu şekilde yazılabilir:

Exp *prog1 = new AddExp(
    new Number(10), new MulExp(
      new Number(20), new AddExp(
        new Number(30), new Number(40))));

Peki bu ağaç üzerinde gezinmek nasıl mümkün olabilir ? Bir kere, tüm nodelar alt node olarak Exp tipinde bir nesne tutuyor, kesin tip bilgisine sahip değiliz ve bu tip bilgisine sahip olmadan da yorumlamak mümkün değil mi, yorumladığımız node Number mı, MulExp mi vs. bilmemiz gerekir.

Bunu yapmanın çeşitli yolları var, ama güzel bir çözümü yok. Örneğin Exp sınıfında nodeların tipini tutan bir enum tutabiliriz ve Exp *leri gerekli tiplere cast ederiz. Veya Java gibi bir dilde instanceof kontrolü yapılıp cast edilebilir. Başka çözümler de bulunabilir.

Bu gibi durumlarda kabul edilen en yaygın çözüm visitor design patternı. Biraz aradığınızda onlarca tutorial bulabilirsiniz ki tutoriala ihtiyaç duyması bile aslında fonksiyonel dildeki çözümümüzden ne kadar kötü olduğunun bir göstergesi sayılabilir(8 satır son derece basit ve açık bir Haskell koduna denk bir iş yapmaya çalışıyoruz şu anda)

Bu probleme double dispatch problemi de deniyor. Sebebi yapacağımız işleme hem yorumlayıcıya, hem de ağaca göre karar vermek istiyoruz fakat bir yandan da ağaçlara ve yorumlayıcılara aynı muameleyi yapabilmeliyiz. C++ örneğinde her bir node’un bir ağaç oluşturduğuna dikkat.²

class AddExp;
class MulExp;
class Number;

class ExpVisitor {
public:
  virtual void visit(const AddExp * const exp) = 0;
  virtual void visit(const MulExp * const exp) = 0;
  virtual void visit(const Number * const exp) = 0;

  virtual ~ExpVisitor() {};
};

class Exp { // base class for expressions
public:
  virtual ~Exp() {}
  virtual void accept(ExpVisitor *visitor) const = 0;
};

class AddExp : public Exp {
public:
  const Exp * const e1, * const e2;
  AddExp(const Exp * const e1, const Exp * const e2)
    : e1(e1), e2(e2) {}
  void accept(ExpVisitor *visitor) const { visitor->visit(this); }
};

class MulExp : public Exp {
public:
  const Exp * const e1, * const e2;
  MulExp(const Exp * const e1, const Exp * const e2)
    : e1(e1), e2(e2) {}
  void accept(ExpVisitor *visitor) const { visitor->visit(this); }
};

class Number : public Exp {
public:
  const float f;
  Number(const float f) : f(f) {}
  void accept(ExpVisitor *visitor) const { visitor->visit(this); }
};

Detaylara çok fazla girmek istemiyorum, kısaca, virtual methodların yardımıyla artık bir nesneyi Exp tipine cast etsek de doğru visit methodları çağırılacak. Buna göre ilk yorumlayıcımızı şu şekilde yazabiliyoruz:

class Run : public ExpVisitor {
public:
  float result;
  Run() : result(0) {}

  void visit(const AddExp * const exp) {
    Run v1;
    exp->e1->accept(&v1);

    Run v2;
    exp->e2->accept(&v2);

    result = v1.result + v2.result;
  }

  void visit(const MulExp * const exp) {
    Run v1;
    exp->e1->accept(&v1);

    Run v2;
    exp->e2->accept(&v2);

    result = v1.result * v2.result;
  }

  void visit(const Number * const exp) {
    result = exp->f;
  }
};

Bu arada nesnesel çözümümüzün fonksiyonel çözümümüzden bir başka farkı da burda belli oluyor. Visitorlar arası değer dönmenin bir yolu yok ve bu yüzden buradaki result member değişkeni gibi bir mutable değişken kullanmak zorunda kalıyoruz.

İkinci yorumlayıcımız:

class StringOfExp : public ExpVisitor {
public:
  std::string result;
  StringOfExp() : result(new std::string()) {}

  void visit(const AddExp * const exp) {
    StringOfExp v1;
    exp->e1->accept(&v1);

    StringOfExp v2;
    exp->e2->accept(&v2);

    result = "(" + v1.result + " + " +  v2.result + ")";
  }

  void visit(const MulExp * const exp) {
    StringOfExp v1;
    exp->e1->accept(&v1);

    StringOfExp v2;
    exp->e2->accept(&v2);

    result = "(" + v1.result + " * " +  v2.result + ")";
  }

  void visit(const Number * const exp) {
    std::ostringstream ss;
    ss << exp->f;
    result = ss.str();
  }
};

result member değişkeninin tipinin farklı olduğuna dikkat. Buradaki farklılık Haskell fonksiyonlarındaki dönüş tiplerinin farklılığı ile aynı.

Son olarak programı şu şekilde çalıştırabiliyoruz:

Run r;
prog1->accept(&r);
std::cout << "return value Run: " << r.result << std::endl;

StringOfExp s;
prog1->accept(&s);
std::cout << "return value of StringOfExp: " << s.result << std::endl;

Çıktı:

➜  cpp  clang++ arith.cpp -g
➜  cpp  ./a.out
return value Run: 1410
return value of StringOfExp: (10 + (20 * (30 + 40)))

Burda 14 satır Haskell kodu ile aynı işi yapan 125 satır C++ kodundan bahsediyoruz. Tabii kodun aynı özelliğe sahip olduğunu sadece aynı sonuca ulaşmasına bakarak karar vermiyoruz. Yapı olarak da oldukça benzerler.

Haskell programında ağaca yeni bir node eklemek için ilk başta Exp tipine yeni bir constructor eklememiz gerekecek ve daha sonra tüm yorumlayıcılarda match edilecek bir pattern daha eklenecek.

C++ programında, Exp sınıfından yeni bir sınıf türeteceğiz ve tamamen aynı accept methoduna sahip olacak. ExpVisitor sınıfına da bir visit methodu daha eklememiz gerek. Daha sonra yorumlayıcılara teker teker alakalı visit methodunun eklenmesi gerek.

Haskell fonksiyonlarının dönüş değerleri, Visitor sınıflarının result değişkeni ile eşleşiyor.

Aslında aynı şeylerden bahsediyoruz yani.

C++ kodunun çalışan bir haline şuradan ulaşabilirsiniz.

Alıştırma: Hem Haskell hem C++ programı için, ağaç üzerinde gezinerek “x + 0” ifadesini “x” haline, “x * 1” ifadesini “x” haline, “x * 0” ifadesini “0” haline getirecek yorumlayıcılar yazın. Anlamı koruyacak şekilde daha küçük bir ağaç elde etmiş olacağız. (bu optimizasyonlar gerçek derleyiciler tarafından yapılıyor)

İfade problemi

Yukarıda anlattıklarımın ifade problemi diye tercüme ettiğim expression problem ile de alakalı.

Problemimiz şu, program iki boyutta gelişebiliyor, 1.si veri yapısı boyutunda, yani ağaca yeni nodelar eklemek, 2.si operasyonlar boyutunda, yani yeni yorumlayıcılar eklemek.

Yukarıdaki çözümler aslında birbirlerine denk: İkisinde de veri yapısını değiştirdiğimizde kodu yeniden derlememiz gerekiyor(dolayısıyla kodun elimizde olması gerekiyor), fakat koda sahip olmadan ve yeniden derleme yapmadan yeni operasyon(yani yorumlayıcı ekleyebiliyoruz).

Bu yazının amacı ifade problemi değil, o yüzden en azından şimdilik bahsetmeyeceğim(yazının orjinalinde bu kısım hiç yoktu), fakat aslında oldukça ilginç bir konu ve Haskell’ın ve Lisp dillerinin getirdiği ilginç çözümler var. OO dillerin çözümleri hakkında pek bir bilgim yok.