Contents

1  Einführung

1.1  Funktionale Programmierung

1.1.1  Fallunterscheidungen

fak 0 = 1
fak n = n*fak (n-1)

main = print (fak 5)

fak n
  |n==0      = 1
  |otherwise = n*fak (n-1)

main = print (fak 5)

1.1.2  Generische Typen

lastOfList [x] = x
lastOfList (_:xs) = lastOfList xs

main = do
  print (lastOfList [1,2,3,4,5])
  print (lastOfList ["du","freches","lüderliches","weib"])

1.1.3  Objektorientierte Programmierung in Haskell

class DoubleThis a where
  doubleThis :: a -> a

instance DoubleThis [a] where
  doubleThis s =  s ++  s

instance DoubleThis Integer where
  doubleThis x = 2*x

main = do
  print (doubleThis "hallo")
  print (doubleThis [1,2,3,4])
  print (doubleThis (21::Integer))

1.2  Java

1.2.1  Überladung: pattern matching des armen Mannes

Beispiel:
In folgender Klasse ist die Methode doubleThis überladen, wie im entsprechenden Haskellprogramm oben. Einmal für Integer und einmal für Listen.

package example;
import java.util.*;
public class JavaDoubleThis {
  public static Integer doubleThis(Integer x){return 2*x;}
  public static List<Integer> doubleThis(List<Integer> xs){
    List<Integer> result = new ArrayList<Integer>();
    result.addAll(xs);
    result.addAll(xs);
    return result;
  }
  public static void main(String _){
    System.out.println(doubleThis(21));
    List<Integer> xs = new ArrayList<Integer>();
    xs.add(1);
    xs.add(2);
    xs.add(3);
    xs.add(4);
    System.out.println(doubleThis(xs));
  }
}

1.2.2  Generische Typen

2  Algebraische Typen

2.1  Algebraische Typen in funktionalen Sprachen

Beispiel:
Wir definieren einen algebraischen Typen für Binärbäume in Haskell. Der Typ heiße Tree und sei generisch über die im Baum gespeicherten Elemente. Hierfür steht die Typvariabel a. Es gibt zwei Konstruktoren:

• Empty: zur Erzeugung leerer Bäume
• Branch: zur Erzeugung einer Baumverzweigung. Branch hat drei Argumente: einen linken und einen rechten Teilbaum, sowie ein Element an der Verzweigung.

data Tree a =  Branch (Tree a) a (Tree a)
              |Empty

size Empty = 0
size (Branch l _ r) = 1+size l+size r

flatten Empty = []
flatten (Branch Empty x xs) = (x: (flatten xs))
flatten (Branch (Branch l y r) x xs) 
  = flatten (Branch l  y (Branch r x xs))

main =  do
  print (size (Branch Empty "hallo" Empty))
  print (flatten (Branch (Branch Empty "freches" Empty) 
                         "lüderliches" 
                         (Branch Empty "Weib" Empty )
                  )
         )

2.2  Implementierungen in Java

2.2.1  Objektmethoden

package example;
public abstract class Tree<a>{
  public abstract int size();
  public abstract java.util.List<a> flatten();
}

package example;
public class Empty<a> extends Tree<a>{
  public int size(){return 0;} 
  public java.util.List<a> flatten(){
    return new java.util.ArrayList<a>() ;
  }
}

package example;
public class Branch<a> extends Tree<a>{

  private a element;
  private Tree<a> left;
  private Tree<a> right;

  public a getElement(){return element;}
  public Tree<a> getLeft(){return left;}
  public Tree<a> getRight(){return right;}

  public Branch(Tree<a> l,a e,Tree<a> r){
    left=l;element=e;right=r;
  }

  public int size(){return 1+getLeft().size()+getRight().size();}

  public java.util.List<a> flatten(){
    if (getLeft() instanceof Empty){ 
      java.util.List<a> result = new java.util.ArrayList<a>();
      result.add(getElement());
      result.addAll(getRight().flatten());
      return result;
    }

    Branch<a> theLeft = (Branch<a>)getLeft();
    return new Branch<a>(theLeft.getLeft()
                        ,theLeft.getElement()
                        ,new Branch<a>(theLeft.getRight()
                                      ,getElement()
                                      ,getRight()) 
                        ).flatten() ;
  }

  public static void main(String []_){
    System.out.println(
      new Branch<String>
        (new Empty<String>(),"hallo",new Empty<String>())
        .size());
    System.out.println(
      new Branch<String>
       (new Branch<String>
          (new Empty<String>(),"freches",new Empty<String>())
       ,"lüderliches"
       ,new Branch<String>
          (new Empty<String>(),"Weib",new Empty<String>())
       ).flatten());
  }
}

2.2.2  Fallunterscheidung in einer Methode

package example;
class Size{
  static public <a> int size(Tree<a> t){
    if (t instanceof Empty) return 0;
    if (t instanceof Branch<a>) {
      Branch<a> dies = (Branch<a>) t;
      return
         1+size(dies.getLeft())
          +size(dies.getRight());
    }
    throw new RuntimeException("unmatched pattern: "+t);
  };
  public static void main(String [] _){
    System.out.println(size(
     new Branch<String>(new Empty<String>()
                       ,"hallo"
                       ,new Empty<String>())));
  }
}

package example;
import java.util.*;
class Flatten{
  static public <a> List<a> flatten(Tree<a> t){
    if (t instanceof Empty) return new ArrayList<a>();
    Branch<a> dies = (Branch<a>) t;
    if (dies.getLeft() instanceof Empty){ 
      List<a> result = new ArrayList<a>();
      result.add(dies.getElement());
      result.addAll(flatten(dies.getRight()));
      return result;
    }
    Branch<a> theLeft = (Branch<a>)dies.getLeft();
    return flatten(
           new Branch<a>(theLeft.getLeft()
                        ,theLeft.getElement()
                        ,new Branch<a>(theLeft.getRight()
                                      ,dies.getElement()
                                      ,dies.getRight()) 
                        )) ;
  }

  public static void main(String []_){
    System.out.println(flatten(
      new Branch<String>
       (new Branch<String>
          (new Empty<String>(),"freches",new Empty<String>())
       ,"lüderliches"
       ,new Branch<String>
          (new Empty<String>(),"Weib",new Empty<String>())
       )));
  }
}

3  Visitor

3.1  Besucherobjekte als Funktionen über algebraische Typen

package name.panitz.crempel.util;

public interface Visitor<arg,result> 
                      extends UnaryFunction<arg,result>{
}

package example;
import name.panitz.crempel.util.Visitor;

public interface TreeVisitor<a,result>
                     extends Visitor<Tree<a>,result>{
  public result eval(Tree<a> t);
  public result eval(Branch<a> t);
  public result eval(Empty<a> t);
}

package example;

public class TreeSizeVisitor<a> implements TreeVisitor<a,Integer>{
  public Integer eval(Branch<a> t){
    return 1+eval(t.getLeft())+eval(t.getRight());
  }

  public Integer eval(Empty<a> t){return 0;}

  public Integer eval(Tree<a> t){
    throw new RuntimeException("unmatched pattern: "+t);
  }
}

package example;
public class TreeSizeVisitorNonWorking{
  public static void main(String [] _){
    Tree<String> t = new Branch<String>(new Empty<String>()
                                       ,"hallo"
                                       ,new Empty<String>());
    System.out.println(new TreeSizeVisitor<String>().eval(t));
  }
}

sep@linux:~/fh/adt/examples> java example.TreeSizeVisitorNonWorking
Exception in thread "main" java.lang.RuntimeException: unmatched pattern: example.Branch@1a46e30
        at example.TreeSizeVisitor.eval(TreeSizeVisitor.java:12)
        at example.TreeSizeVisitorNonWorking.main(TreeSizeVisitorNonWorking.java:8)
sep@linux:~/fh/adt/examples>

3.2  Besucherobjekte und Späte-Bindung

package example;
import name.panitz.crempel.util.Visitor;

public abstract class VTree<a>{
  public <result> result visit(VTreeVisitor<a,result> v){
    return v.eval(this);
  }
}

package example;
import name.panitz.crempel.util.Visitor;

public interface VTreeVisitor<a,result> 
                      extends Visitor<VTree<a>,result>{
  public result eval(VTree<a> t);
  public result eval(VBranch<a> t);
  public result eval(VEmpty<a> t);
}

package example;
public class VEmpty<a> extends VTree<a>{
  public <result> result visit(VTreeVisitor<a,result> v){
    return v.eval(this);
  }
}

package example;
public class VBranch<a> extends VTree<a>{
  private a element;
  private VTree<a> left;
  private VTree<a> right;
  public a getElement(){return element;}
  public VTree<a> getLeft(){return left;}
  public VTree<a> getRight(){return right;}
  public VBranch(VTree<a> l,a e,VTree<a> r){
    left=l;element=e;right=r;
  }
  public <result> result visit(VTreeVisitor<a,result> v){
    return v.eval(this);
  }
}

package example;

public class VTreeSizeVisitor<a> 
            implements VTreeVisitor<a,Integer> {
  public Integer eval(VBranch<a> t){
    return 1+t.getLeft().visit(this)+t.getRight().visit(this);
  }
  public Integer eval(VEmpty<a> t){return 0;}
  public Integer eval(VTree<a> t){
    throw new RuntimeException("unmatched pattern: "+t);
  }

}

package example;
public class TreeSizeVisitorWorking{
  public static void main(String [] _){
    VTree<String> t = new VBranch<String>(new VEmpty<String>()
                                       ,"hallo"
                                       ,new VEmpty<String>());
    System.out.println(t.visit(new VTreeSizeVisitor<String>()));
  }
}

package example;
import java.util.*;

public class VFlattenVisitor<a> 
                   implements VTreeVisitor<a,List<a>>{

  public List<a> eval(VEmpty<a> t){return new ArrayList<a>();}

  public List<a> eval(VBranch<a> t){
    return t.getLeft().visit(
      new InnerFlattenVisitor(t.getElement(),t.getRight(),this)
    );
  }

  public List<a> eval(VTree<a> t){
    throw new RuntimeException("unmatched pattern: "+t);
  }

  public class InnerFlattenVisitor<a> 
            implements VTreeVisitor<a,List<a>> {

    final a element;
    final VTree<a> right; 
    final VFlattenVisitor<a> outer;

    InnerFlattenVisitor(a e,VTree<a> r,VFlattenVisitor<a> o){
     element=e;right=r;outer=o;}

    public List<a> eval(VEmpty<a> t){
      List<a> result = new ArrayList<a>();
      result.add(element);
      result.addAll(right.visit(outer));
      return result;
    }

    public List<a> eval(VBranch<a> t){
      return new VBranch<a>(t.getLeft()
                           ,t.getElement()
                           ,new VBranch<a>(t.getRight()
                                          ,element
                                          ,right) 
                           ).visit(outer) ;
    }

    public List<a> eval(VTree<a> t){
      throw new RuntimeException("unmatched pattern: "+t);
    }
  }
}

4  Generierung von Klassen für algebraische Typen

4.1  Eine Syntax für algebraische Typen

Beispiel:
In der solcherhand vorgeschlagenen Syntax lassen sich Binärbäume wie folgt deklarieren:

package example.tree;
data class T<a> {
  Branch(T<a> left,a element,T<a> right);
  Empty();
}

4.1.1  Generierte Klassen

package example.tree;

public abstract class T<a> implements TVisitable<a>{
  abstract public <b_> b_ visit(TVisitor<a,b_> visitor);
}

package example.tree;

public interface TVisitable<a>{
  public <_b> _b visit(TVisitor<a,_b> visitor);}

package example.tree;
import name.panitz.crempel.util.Visitor;

public abstract class TVisitor<a,result> 
  implements Visitor<T<a>,result>{
  public abstract result eval(Branch<a> _);
  public abstract result eval(Empty<a> _);
  public result eval(T<a> xs){
    throw new RuntimeException("unmatched pattern: "+xs.getClass());
  }}

package example.tree;
public class Empty<a> extends T<a>{
  public Empty(){}

  public <_b> _b visit(TVisitor<a,_b> visitor){
    return visitor.eval(this);
  }
  public String toString(){
    return "Empty("+")";
  }
  public boolean equals(Object other){
    if (!(other instanceof Empty)) return false;
    final Empty o= (Empty) other;
    return true  ;
  }
}

package example.tree;

public class Branch<a> extends T<a>{
  private T<a> left;
  private a element;
  private T<a> right;

  public Branch(T<a> left,a element,T<a> right){
    this.left = left;
    this.element = element;
    this.right = right;
  }

  public T<a> getLeft(){return left;}
  public a getElement(){return element;}
  public T<a> getRight(){return right;}
  public <_b> _b visit(TVisitor<a,_b> visitor){
    return visitor.eval(this);
  }
  public String toString(){
    return "Branch("+left+","+element+","+right+")";
  }
  public boolean equals(Object other){
    if (!(other instanceof Branch)) return false;
    final Branch o= (Branch) other;
    return true  &&left.equals(o.left)
                 &&element.equals(o.element)
                 &&right.equals(o.right);
  }
}

4.1.2  Schreiben von Funktionen auf algebraische Typen

package example.tree;
public class TSize<a> extends TVisitor<a,Integer>{
  public Integer eval(Branch<a> x){
    return 1+size(x.getLeft())+size(x.getRight());
  }
  public Integer eval(Empty<a> _){return 0;}

  public int size(T<a> t){
    return t.visit(this);}
}

4.1.3  Verschachtelte algebraische Typen

package example.baum;
data class Li<a> {
  Cons(a head ,Li<a> tail);
  Empty();
}

package example.baum;
data class Baum<a> {
  Zweig(Li<Baum<a>> children,a element);
  Leer();
}

Beispiel:
Für die Bäume mit beliebig großer Kinderanzahl ergeben sich folgende Besucher für das Zählen der Elemente:

package example.baum;
public class BaumSize<a> extends BaumVisitor<a,Integer>{
  final BaumVisitor<a,Integer> dies = this;
  final LiBaumSize inner = new LiBaumSize();

  public Integer size(Baum<a> t){return t.visit(this);}
  public Integer size(Li<Baum<a>> xs){return xs.visit(inner);}

  class LiBaumSize  extends LiVisitor<Baum<a>,Integer>{
    public Integer eval(Empty<Baum<a>> _){return 0;}
    public Integer eval(Cons<Baum<a>> xs){
      return size(xs.getHead()) + size(xs.getTail());}
  }
    public Integer eval(Zweig<a> x){
      return 1+size(x.getChildren());}
    public Integer eval(Leer<a> _){return 0;}
}

package example.baum;
public class BaumSizeTest{
  public static void main(String [] _){
    Baum<String> b
      = new Zweig<String>
         (new Cons<Baum<String>>
           (new Leer<String>()
           ,new Cons<Baum<String>>
              (new Zweig<String>
                    (new Empty<Baum<String>>(),"welt")
              ,new Empty<Baum<String>>()))
           ,"hallo");
    System.out.println(new BaumSize<String>().size(b));
  }
}

package example.baum;
import name.panitz.crempel.util.Visitor;

public class BaumSizeError<a> 
                 implements Visitor<Baum<a>,Integer>
                          , Visitor<Li<Baum<a>>,Integer>{
  public Integer size(Baum<a> t){return t.visit(this);}
  public Integer size(Li<Baum<a>> xs){return xs.visit(this);}

  public Integer eval(Empty<Baum<a>> _){return 0;}
  public Integer eval(Cons<Baum<a>> xs){
    return size(xs.getHead())+size(xs.getTail());}
  public Integer eval(Zweig<a> x){return size(x.getChildren());}
  public Integer eval(Leer<a> _){return 0;}

  public Integer eval(Li<Baum<a>> t){
    throw new RuntimeException("unsupported pattern: "+t);}
  public Integer eval(Baum<a> t){
    throw new RuntimeException("unsupported pattern: "+t);}
}

BaumSizeError.java:5: name.panitz.crempel.util.Visitor cannot
be inherited with different arguments: 
    <example.baum.Baum<a>,java.lang.Integer> 
and <example.baum.Li<example.baum.Baum<a>>,java.lang.Integer>

4.2  Java Implementierung

4.2.1  Abstrakte Typbeschreibung

package name.panitz.crempel.util.adt;

import java.util.List;
import java.util.ArrayList;
import java.io.File;
import java.io.FileWriter;
import java.io.Writer;
import java.io.IOException;

public class AbstractDataType {

• einen Typnamen für den den algebraischen Typen
• eventuell eine Paketspezifikation
• eine Liste Imports
• eine Liste von Typvariablen
• eine Liste von Konstrurtordefinitionen

  String name;
  String thePackage;
  List<String> typeVars;
  List<String> imports;
  public List<Constructor> constructors;

  public AbstractDataType(String p,String n,List tvs,List ps){
    this(p,n,tvs,ps,new ArrayList<String>());
  }

  public AbstractDataType
                 (String p,String n,List tvs,List ps,List im){
    thePackage = p;
    name=n;
    typeVars=tvs;
    constructors=ps;
    imports=im;
  }

  public String toString(){
    StringBuffer result = new StringBuffer("data class "+name);
    if (!typeVars.isEmpty()){
      result.append("<");
      for (String tv:typeVars){result.append("\u0020"+tv);}
      result.append(">");
    }
    result.append("{\n");
    for (Constructor c:constructors){result.append(c.toString());}
    result.append("}\n");
    return result.toString();
  }

  public String getFullName(){return name+getParamList();}

  public String getName(){return name;}

  String commaSepParams(){
    String paramList = "";
      boolean first=true;
      for (String tv:typeVars){
        if (!first)paramList=paramList+",";
        paramList=paramList+tv;
        first=false;
      }
      return paramList;
  }

  public String getParamList(){
    if (!typeVars.isEmpty()){return '<'+commaSepParams()+'>';}
    return "";
  }

  String getPackageDef(){
    return  thePackage.length()==0
           ?""
           :"package "+thePackage+";\n\n";
  }

  public void generateClasses(String path){
    try{
      generateVisitorInterface(path);
      generateVisitableInterface(path);
      generateClass(path);
    }catch (IOException _){}
}

  public void generateClass(String path) throws IOException{
    String fullName = getFullName();

    if (constructors.size()!=1){
      FileWriter out = new FileWriter(path+"/"+name+".java");
      out.write( getPackageDef());
      writeImports(out);
      out.write("public abstract class ");
      out.write(fullName);
      out.write(" implements "+name+"Visitable"+getParamList());
      out.write("{\n");
      out.write("  abstract public <b_> b_ visit("
              +name+"Visitor<"+commaSepParams()
                              +(typeVars.isEmpty()?"":",")
                              +"b_> visitor);\n");  
      out.write("}");
      out.close();
      for (Constructor c:constructors){c.generateClass(path,this);}

    }else{constructors.get(0).generateClass(path,this,true);}
  }

  void writeImports(Writer out) throws IOException{
    for (String imp:imports){
      out.write("\nimport ");
      out.write(imp);
    }
    out.write("\n\n");
  }

  public void generateVisitableInterface(String path){
    try{
      final String interfaceName = name+"Visitable";	
      final String fullName = interfaceName+getParamList();
      FileWriter out
        = new FileWriter(path+"/"+interfaceName+".java");
      out.write( getPackageDef());
      writeImports(out);
      out.write("public interface ");
      out.write(fullName+"{\n");
      out.write("  public <_b> _b visit("
		+name+"Visitor<"+commaSepParams()
                                +(typeVars.isEmpty()?"":",")
                                +"_b> visitor);"); 
      out.write("}");
      out.close();
    }catch (Exception _){}
  }

  public void generateVisitorInterface(String path){
    try{
      final String interfaceName = name+"Visitor";	
      final String fullName
       = interfaceName+"<"
                      +commaSepParams()
                      +(typeVars.isEmpty()?"":",")
                      +"result>";
      FileWriter out 
       = new FileWriter(path+"/"+interfaceName+".java");
      out.write( getPackageDef());
      out.write( "\n");
      out.write("import name.panitz.crempel.util.Visitor;\n");
      writeImports(out);
      out.write("public abstract class ");
      out.write(fullName+" implements Visitor<");
      out.write(getFullName()+",result>{\n");
      if (constructors.size()!=1){
        for (Constructor c:constructors) 
          out.write("  "+c.makeEvalMethod(this)+"\n");
      }

      out.write("  public result eval("+getFullName() +" xs){\n");
      out.write("    throw new RuntimeException(");
      out.write("\"unmatched pattern: \"+xs.getClass());\n");
      out.write("  }");

      out.write("}");
      out.close();
    }catch (Exception _){}
  }
}

4.2.2  Konstruktordarstellung

package name.panitz.crempel.util.adt;

import name.panitz.crempel.util.Tuple2;

import java.util.List;
import java.util.ArrayList;
import java.io.FileWriter;
import java.io.Writer;
import java.io.IOException;

public class Constructor {

  String name;
  List<Tuple2<Type,String>> params;

  public Constructor(String n,List ps){name=n;params=ps;}
  public Constructor(String n){this(n,new ArrayList());}

  public String toString(){
    StringBuffer result = new StringBuffer("  ");
    result.append(name);
    result.append("(");
    boolean first = true;
    for (Tuple2<Type,String> t:params){
	if (first) {first=false;}
	else {result.append(",");}
      result.append(t.e1+"\u0020"+t.e2);
    }
    result.append(");\n");
    return result.toString();
  }

• das Objekt, das den algebraischen Typen darstellt
• und der Pfad zum Order des Dateisystems.

  public void generateClass(String path,AbstractDataType theType){
    generateClass(path,theType,false);
  }

  public void generateClass
        (String path,AbstractDataType theType,boolean standalone){
    try{
      if (standalone) name=theType.getFullName();
      FileWriter out = new FileWriter(path+"/"+name+".java");
      out.write( theType.getPackageDef());
      theType.writeImports(out);

      out.write("public class ");
      out.write(name);
      out.write(theType.getParamList());
      if (!standalone){
        out.write(" extends ");
        out.write(theType.getFullName());
      } else{
        out.write(" implements "+theType.name+"Visitable");
      }
      out.write("{\n");

• Felder für die Argumente des Konstruktors
• Get-Methoden für diese Felder
• die Methode visit
• die Methode equals
• die Methode toString

      writeFields(out);
      writeConstructor(out);
      writeGetterMethods( out);
      writeVisitMethod(theType, out);
      writeToStringMethod(out);
      writeEqualsMethod(out);
      out.write("}\n");
      out.close();
    }catch (Exception _){}
  }

  private void writeFields(Writer out)throws IOException{
    for (Tuple2<Type,String> pair:params){
     out.write("  private final ");
     out.write(pair.e1.toString());
     out.write("\u0020");
     out.write(pair.e2);
     out.write(";\n");
    }
  }

  private void writeConstructor(Writer out)throws IOException{
    out.write("\n  public "+name+"(");
    boolean first= true;
    for (Tuple2<Type,String> pair:params){
      if (!first){out.write(",");}
      out.write(pair.e1.toString());
      out.write("\u0020");
      out.write(pair.e2);
      first=false;
    }
    out.write("){\n");
    for (Tuple2<Type,String> pair:params){
      out.write("    this."+pair.e2);
      out.write(" = ");
      out.write(pair.e2);
      out.write(";\n");
    }
    out.write("  }\n\n");
  }

  private void writeGetterMethods(Writer out)throws IOException{
    for (Tuple2<Type,String> pair:params){
      out.write("  public ");
      out.write(pair.e1.toString());
      out.write(" get");
      out.write(Character.toUpperCase(pair.e2.charAt(0)));
      out.write(pair.e2.substring(1));
      out.write("(){return "+pair.e2 +";}\n");
    }
  }

  private void writeVisitMethod
                   (AbstractDataType theType,Writer out)
         throws IOException{
      out.write("  public <_b> _b visit("
		+theType.name+"Visitor<"+theType.commaSepParams()
                                +(theType.typeVars.isEmpty()?"":",")
                                +"_b> visitor){"
                +"\n    return visitor.eval(this);\n  }\n"); 
  }

  private void writeToStringMethod(Writer out) throws IOException{
    out.write("  public String toString(){\n");
    out.write("    return \""+name+"(\"");
    boolean first=true;
    for (Tuple2<Type,String> p:params){
     if (first){first=false;}
     else out.write("+\",\"");
     out.write("+"+p.e2);
    }
    out.write("+\")\";\n  }\n"); 
  }

  private void writeEqualsMethod(Writer out) throws IOException{
    out.write("  public boolean equals(Object other){\n");
    out.write("    if (!(other instanceof "+name+")) ");
    out.write("return false;\n");
    out.write("    final "+name+" o= ("+name+") other;\n");
    out.write("    return true  ");
    for (Tuple2<Type,String> p:params){
      out.write("&& "+p.e2+".equals(o."+p.e2+")");
    }
    out.write(";\n  }\n"); 
  }

  public String makeEvalMethod(AbstractDataType theType){
    return "public abstract result eval("
            +name+theType.getParamList()+" _);";
  }
}

4.2.3  Parametertypen

package name.panitz.crempel.util.adt;

import java.util.List;
import java.util.ArrayList;

public class Type {

    private String name;
    private List<Type> params;
    public String getName(){return name;}
    public List<Type> getParams(){return params;}
    
    public Type(String n,List ps){name=n;params=ps;}
    public Type(String n){this(n,new ArrayList());}

    public String toString(){
      StringBuffer result = new StringBuffer(name);
      if (!params.isEmpty()){
	result.append("<");
	boolean first=true;
        for (Type t:params){
          if (!first) result.append(',');  
	  result.append(t);
          first=false;
	}
        result.append('>');  
      }
      return result.toString();
    }
}

4.2.4  Hauptgenerierungsprogramm

package name.panitz.crempel.util.adt;

import name.panitz.crempel.util.adt.parser.ADT;
import java.util.List;
import java.util.ArrayList;
import java.io.FileReader;
import java.io.File;

public class ADTMain {
  public static void main(String args[])  {
    try{
      List<String> fileNames = new ArrayList<String>();

      if (args.length==1 && args[0].equals("*.adt")){
        for (String arg:new File(".").list()){
          if (arg.endsWith(".adt")) fileNames.add(arg);
        }
      }else for (String arg:args) fileNames.add(arg);
     
      for (String arg:fileNames){
        File f = new File(arg);  
        ADT parser = new ADT(new FileReader(f));
        AbstractDataType adt = parser.adt();
        System.out.println(adt);
        final String path
          = f.getParentFile()==null?".":f.getParentFile().getPath();
        adt.generateClasses(path);
      }
    }catch (Exception _){_.printStackTrace();} 
  }
}

5  Beispiel: eine kleine imperative Programmiersprache

5.1  Algebraischer Typ für Klip

package name.panitz.crempel.util.adt.examples;

import java.util.List;

data class Klip{
  Num(Integer i);
  Add(Klip e1,Klip e2);
  Mult(Klip e1,Klip e2);
  Sub(Klip e1,Klip e2);
  Div(Klip e1,Klip e2);
  Var(String name);
  Assign(String var,Klip e);
  While(Klip cond,Klip body);
  Block(List stats);
}

5.2  Besucher zur textuellen Darstellung

Beispiel:
Ein kleines Beispiel für ein Klipprogramm zur Berechnung der Fakultät von 5.

x := 5;
y:=1;
while (x){y:=y*x;x:=x-1;};
y;

package name.panitz.crempel.util.adt.examples;
import name.panitz.crempel.util.*;
import java.util.*;

public class ShowKlip extends KlipVisitor<String> {
  public String show(Klip a){return a.visit(this);}

  public String eval(Num x){return x.getI().toString();}
  public String eval(Add x){
    return "("+show(x.getE1())+" + "+show(x.getE2())+")";}
  public String eval(Sub x){
    return "("+show(x.getE1())+" - "+show(x.getE2())+")";}
  public String eval(Div x){
    return "("+show(x.getE1())+" / "+show(x.getE2())+")";}
  public String eval(Mult x){
    return "("+show(x.getE1())+" * "+show(x.getE2())+")";}
  public String eval(Var v){return v.getName();}
  public String eval(Assign x){
    return x.getVar()+" := "+show(x.getE());}
  public String eval(Block b){
    StringBuffer result=new StringBuffer();
    for (Klip x:(List<Klip>)b.getStats()) 
      result.append(show(x)+";\n");
    return result.toString();
  }
  public String eval(While w){
    StringBuffer result=new StringBuffer("while (");
    result.append(show(w.getCond()));
    result.append("){\n");
    result.append(show(w.getBody()));
    result.append("\n}");
    return result.toString();
  }
}

5.3  Besucher zur Interpretation eines Klip Programms

package name.panitz.crempel.util.adt.examples;
import name.panitz.crempel.util.*;
import java.util.*;

public class EvalKlip extends KlipVisitor<Integer> {
  Map<String,Integer> env = new HashMap<String,Integer>();
  public Integer val(Klip x){return x.visit(this);}

 public Integer eval(Num x){return x.getI();}
 public Integer eval(Add x){return val(x.getE1())+val(x.getE2());}
 public Integer eval(Sub x){return val(x.getE1())-val(x.getE2());}
 public Integer eval(Div x){return val(x.getE1())/val(x.getE2());}
 public Integer eval(Mult x){return val(x.getE1())*val(x.getE2());}
 public Integer eval(Var v){return env.get(v.getName());}
 public Integer eval(Assign ass){
   Integer i = val(ass.getE());
   env.put(ass.getVar(),i);
   return i;
 }
 public Integer eval(Block b){
    Integer result = 0;
    for (Klip x:(List<Klip>)b.getStats()) result=val(x);
    return result;
 }
 public Integer eval(While w){
    Integer result = 0;
    while (w.getCond().visit(this)!=0){
      System.out.println(env); //this is a trace output
      result = w.getBody().visit(this);
    }    
    return result;
 }
}

5.4  javacc Parser für Klip

options {
   STATIC=false;
}

PARSER_BEGIN(KlipParser)
package name.panitz.crempel.util.adt.examples;

import name.panitz.crempel.util.Tuple2;
import java.util.List;
import java.util.ArrayList;
import java.io.FileReader;

public class KlipParser  {
  public static void main(String [] args)throws Exception{
    Klip klip = new KlipParser(new FileReader(args[0]))
                .statementList();

    System.out.println(klip.visit(new ShowKlip()));
    System.out.println(klip.visit(new EvalKlip()));
  }
}
PARSER_END(KlipParser)

5.4.1  Scanner

TOKEN :
{<WHILE: "while">
|<#ALPHA:	["a"-"z","A"-"Z","_","."]	>
|<NUM:		["0"-"9"]		>
|<#ALPHANUM:	<ALPHA> | <NUM>		>
|<NAME: <ALPHA> ( <ALPHANUM> )*>
|<ASS: ":=">
|<LPAR: "(">
|<RPAR: ")">
|<LBRACKET: "{">
|<RBRACKET: "}">
|<SEMICOLON: ";">
|<STAR: "*">
|<PLUS: "+">
|<SUB: "-">
|<DIV: "/">
}

SKIP :
{ "\u0020"
| "\t"
| "\n"
| "\r"
}

5.4.2  Parser

Klip statementList() : 
{  List stats = new ArrayList();
   Klip stat;}
{ 
  (stat=statement() {stats.add(stat);} <SEMICOLON>)*
  {return new Block(stats);}
}

Klip statement():
{Klip e2;Klip result;boolean sub=false;}
{  
  result=multExpr() 
  [ (<PLUS>|<SUB>{sub=true;}) e2=statement() 
   {result = sub?new Sub(result,e2):new Add(result,e2);}]
  {return result;}
}

Klip multExpr():
{Klip e2;Klip result;boolean div= false;}
{  
  result=atomicExpr() 
  [ (<STAR>|<DIV>{div=true;}) 
    e2=multExpr() 
    {result = div?new Div(result,e2):new Mult(result,e2);}]
  {return result;}
}

Klip atomicExpr():
{Klip result;}
{  
   (result=integerLiteral()
   |result=varOrAssign()
   |result=whileStat()
   |result=parenthesesExpr()
   )
  {return result;}
}

Klip integerLiteral():
{ int result = 0;
  Token n;
  boolean m=false;}
{  [<SUB> {m = true;}]
   (n=<NUM>  
    {result=result*10+n.toString().charAt(0)-48;})+
   {return new Num(new Integer(m?-result:result));}
}

Klip parenthesesExpr():
{Klip result;}
{ <LPAR> result = statement() <RPAR>
{return result;}}

Klip varOrAssign():
{ Token n;Klip result;Klip stat;}
{ n=<NAME>{result=new Var(n.toString());} 
  [<ASS> stat=statement() 
    {result = new Assign(n.toString(),stat);}
  ]
  {return result;}
}

Klip whileStat():{
  Klip cond; Klip body;}
{ <WHILE> <LPAR>cond=statement()<RPAR> 
  <LBRACKET> body=statementList()<RBRACKET>
  {return new While(cond,body);}
}

5.4.3  Klip-Beispiele

2*7+14*2;

2*(7+9)*2;

sep@linux:~> java name.panitz.crempel.util.adt.examples.KlipParser arith1.klip
((2 * 7) + (14 * 2));

42
sep@linux:~> java name.panitz.crempel.util.adt.examples.KlipParser arith2.klip
(2 * ((7 + 9) * 2));

64
sep@linux:~>

sep@linux:~> java name.panitz.crempel.util.adt.examples.KlipParser fak.klip
x := 5;
y := 1;
while (x){
y := (y * x);
x := (x - 1);

};
y;

{y=1, x=5}
{y=5, x=4}
{y=20, x=3}
{y=60, x=2}
{y=120, x=1}
120
sep@linux:~>

A  Javacc Definition für ATD Parser

options {
   STATIC=false;
}

PARSER_BEGIN(ADT)
package name.panitz.crempel.util.adt.parser;

import name.panitz.crempel.util.Tuple2;
import name.panitz.crempel.util.adt.*;
import java.util.List;
import java.util.ArrayList;
import java.io.FileReader;

public class ADT {

}
PARSER_END(ADT)

TOKEN :
{<DATA: "data">
|<CLASS: "class">
|<DOT: ".">
|<#ALPHA:	["a"-"z","A"-"Z","_","."]	>
|<#NUM:		["0"-"9"]		>
|<#ALPHANUM:	<ALPHA> | <NUM>		>
|<PAKET: "package">
|<IMPORT: "import">
|<NAME: <ALPHA> ( <ALPHANUM> )*>
|<EQ: "=">
|<BAR: "|">
|<LPAR: "(">
|<RPAR: ")">
|<LBRACKET: "{">
|<RBRACKET: "}">
|<LE: "<">
|<GE: ">">
|<SEMICOLON: ";">
|<COMMA: ",">
|<STAR: "*">
}

SKIP :
{ "\u0020"
| "\t"
| "\n"
| "\r"
}

AbstractDataType adt() : 
{ Token nameT;
  String name;
  String paket;
  List typeVars = new ArrayList();
  List constructors;
  List imports;
}
{
   paket=packageDef()
   imports=importDefs()
   
   <DATA> <CLASS> nameT=<NAME>{name=nameT.toString();} 

   [ <LE> 
       (nameT=<NAME> {typeVars.add(nameT.toString());}) 
       (<COMMA> nameT=<NAME> {typeVars.add(nameT.toString());})* 
     <GE>]
    <LBRACKET>
   constructors=defs()
    <RBRACKET>
{return 
  new AbstractDataType(paket,name,typeVars,constructors,imports);}
}

String packageDef():
{StringBuffer result=new StringBuffer();Token n;}
{
  [<PAKET> n=<NAME>{result.append(n.toString());} 
    (<DOT> n=<NAME>{result.append("."+n.toString());})*
    <SEMICOLON>
  ]
{return result.toString();}
}


List importDefs():{
  List result=new ArrayList();Token n;StringBuffer current;}
{
  ({current = new StringBuffer();}
    <IMPORT> n=<NAME>{current.append(n.toString());} 
    (<DOT> n=<NAME>{current.append("."+n.toString());})*
    [<DOT><STAR>{current.append(".*");}]
    <SEMICOLON>
    {current.append(";");result.add(current.toString());}
  )*
{return result;}
}


List defs() :
{
  Constructor def ;
  ArrayList result=new ArrayList();
}
{
   def=def(){result.add(def);} (def=def() {result.add(def);} )*
   {return result;}
}

Constructor def() : 
{ Token n;
  Type param ;
  String name;
  ArrayList params=new ArrayList();
}
{
  n=<NAME> {name=n.toString();}
     <LPAR>[(param=type() n=<NAME>
                {params.add(new Tuple2(param,n.toString()));}  ) 
         (<COMMA> param=type() n=<NAME> 
            {params.add(new Tuple2(param,n.toString()));}  )* 
     ]<RPAR>
  <SEMICOLON>
  {return new Constructor(name,params);}
}

Type type():
{ Type result;
  Token n;
  Type typeParam;
  ArrayList params=new ArrayList();
}
{
  ( n=<NAME>
   ([<LE>
         typeParam=type() {params.add(typeParam);}
        (<COMMA> typeParam=type() {params.add(typeParam);}   )* 
        {result = new Type(n.toString(),params);}
     <GE>])
 )
{
{result = new Type(n.toString(),params);}
return result;
}
}

B  Aufgaben

data HLi a 
  =   Empty 
    | Cons a (HLi a)

odds(Cons x (Cons y ys)) = (Cons x (odds(ys)))
odds(Cons x Empty)       = (Cons x Empty)
odds(Empty)              = Empty

data HBT a 
  =   T a
    | E 
    | B (HBT a) a (HBT a)

addLeft (T a)     = a
addLeft (E)       = 0
addLeft (B l x r) = x+addLeft(l)

package name.panitz.aufgaben;
data class BT<at>{
  E();
  Branch(BT<at> left,at mark,BT<at> right);
}

{\bf \alph{unteraufgabe})} Schreiben Sie einen Besucher HTMLTree<at>, der BTVisitor<at,StringBuffer> erweitert. Er soll in einem StringBuffer einen String erzeugen, der HTML-Code darstellt. Die Kinder eines Knotens sollen dabei mit einem <ul>-Tag gruppiert werden und jedes Kind als <li> Eintrag in dieser Gruppe auftreten.
Beispiel: Für folgenden Baum:
HTMLTreeExample

package name.panitz.aufgaben;
public class HTMLTreeExample{
  public static void main(String [] _){
    BT<String> bt 
     =new Branch<String>
       (new Branch<String>(new E<String>()
                          ,"brecht"
                          ,new E<String>())
       ,"horvath"
       ,new Branch<String>
         (new Branch<String>(new E<String>()
                            ,"ionesco"
                            ,new E<String>())
         ,"shakespeare"
         ,new E<String>()));
    System.out.println(bt.visit(new HTMLTree()));
  }
}

Wird folgenden HTML Code erzeugt:

horvath
<ul>
<li>brecht
<ul>
<li>E()</li>
<li>E()</li></ul></li>
<li>shakespeare
<ul>
<li>ionesco
<ul>
<li>E()</li>
<li>E()</li></ul></li>
<li>E()</li></ul></li></ul>

Lösung

HTMLTree
package name.panitz.aufgaben;
import java.util.List;
import java.util.ArrayList;
public class HTMLTree<at> extends  BTVisitor<at,StringBuffer>{
  StringBuffer result=new StringBuffer();
  public StringBuffer eval(E<at> _){
    result.append("E()");return result;} 

  public StringBuffer eval(Branch<at> n){
    result.append(n.getMark());    
    result.append("\n<ul>");
    result.append("\n<li>");
    n.getLeft().visit(this);
    result.append("</li>");
    result.append("\n<li>");
    n.getRight().visit(this);
    result.append("</li>");
    result.append("</ul>");
    return result;
  } 
}

{\bf \alph{unteraufgabe})} Schreiben Sie einen Besucher FlattenTree<at>, der BTVisitor<at,List<at>> erweitert. Er soll alle Knotenmarkierungen des Baumes in seiner Ergebnisliste sammeln.
Lösung

FlattenTree

package name.panitz.aufgaben;
import java.util.List;
import java.util.ArrayList;
public class FlattenTree<at> extends  BTVisitor<at,List<at>>{
  List<at> result = new ArrayList<at>();

  public List<at> eval(E<at> _){return result;} 
  public List<at> eval(Branch<at> n){
    n.getLeft().visit(this);
    result.add(n.getMark());
    n.getRight().visit(this);
    return result;
  } 
}

References

[GHJV95]

Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements od Reusable Object-Oriented Software. Addison-Wesley Professional Computing Series. Addison-Wesley Publishing Company, New York, NY, 1995.

[Ler97]

Xavier Leroy. The Caml Light system release 0.73. Institut National de Recherche en Informatique et Automatique, 1 1997.

[Mil78]

Robin Milner. A theory of type polymorphism in programming. J.Comp.Sys.Sci, 17:348-375, 1978.

[MTH90]

Robin Milner, Mads Tofte, and Robert Harper. The Definition of Standard ML. IT Press, Cambridge, Massachusetts, 1990.

[OW97]

Martin Odersky and Philip Wadler. Pizza into java: Translating theory into practice. In Proc. 24th ACM Symposium on Principles of Programming Languages, 1997.

[Pan03]

Sven Eric Panitz. Programmieren II. Skript zur Vorlesung, TFH Berlin, 2003. www.panitz.name/prog2/index.html.

[Pan04]

Sven Eric Panitz. Erweiterungen in Java 1.5. Skript zur Vorlesung, TFH Berlin, 2004. www.panitz.name/java1.5/index.html.

[PvE95]

R. Plasmeijer and M. van Eekelen. Concurrent clean: Version 1.0. Technical report, Dept. of Computer Science, University of Nijmegen, 1995. draft.