Starting a HaStABeL library...

14 files changed, 1237 insertions, 0 deletions

diff --git a/src/hastabel/Elements.java b/src/hastabel/Elements.java
new file mode 100644
index 0000000..0d493f9
--- /dev/null
+++ b/src/hastabel/Elements.java
@@ -0,0 +1,98 @@
+package hastabel;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.HashMap;
+
+public class Elements
+{
+   private final boolean is_root_mgr;
+
+   private final Map<String, Element> from_name;
+
+   public Elements (final boolean is_root_mgr)
+   {
+      from_name = new HashMap<String, Element>();
+      this.is_root_mgr = is_root_mgr;
+   }
+
+   public Element declare (final Type type, final String name)
+   {
+      final Element result, previous_instance;
+
+      result = new Element(type, name);
+
+      previous_instance = from_name.get(name);
+
+      if (previous_instance == null)
+      {
+         from_name.put(name, result);
+
+         if (is_root_mgr)
+         {
+            type.add_element(result);
+         }
+
+         return result;
+      }
+
+      if (type.equals(previous_instance.get_type()))
+      {
+         return previous_instance;
+      }
+
+      if (previous_instance.get_type().includes(type))
+      {
+         System.err.println
+         (
+            "[W] Element \""
+            + name
+            + "\" was declared as a \""
+            + previous_instance.get_type().get_name()
+            + "\", but is now declared as its \""
+            + type.get_name()
+            + "\" sub-type. \""
+            + type.get_name()
+            + "\" declaration ignored."
+         );
+
+         return previous_instance;
+      }
+
+      System.err.println
+      (
+         "[E] Conflicting types for element \""
+         + name
+         + "\": was \""
+         + previous_instance.get_type().get_name()
+         + "\", is now \""
+         + type.get_name()
+         + "\"."
+      );
+
+      return null;
+   }
+
+   public Element get (final String name)
+   {
+      final Element result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         System.err.println("[F] Undeclared element \"" + name + "\".");
+
+         System.exit(-1);
+
+         return null;
+      }
+
+      return result;
+   }
+
+   public Collection<Element> get_all ()
+   {
+      return from_name.values();
+   }
+}
diff --git a/src/hastabel/LangLexer.g4 b/src/hastabel/LangLexer.g4
new file mode 100644
index 0000000..45062f0
--- /dev/null
+++ b/src/hastabel/LangLexer.g4
@@ -0,0 +1,25 @@
+lexer grammar LangLexer;
+
+@header {package hastabel;}
+
+fragment SEP: [ \t\r\n]+;
+
+L_PAREN: '(';
+R_PAREN: ')';
+L_BRAKT: '{';
+R_BRAKT: '}';
+COMMA: ',';
+SUB_TYPE_OF: '::';
+STAR: '*';
+
+ADD_TYPE_KW: 'add_type' SEP;
+ADD_RELATION_KW: 'add_relation' SEP;
+ADD_TEMPLATE_KW: 'add_template' SEP;
+
+WS: SEP;
+
+ID: [a-zA-Z0-9_.]+;
+
+STRING: '"' ~('\r' | '\n' | '"')* '"';
+
+COMMENT: (';;'|'#'|'//'|'%') .*? '\n' -> channel(HIDDEN);
diff --git a/src/hastabel/LangParser.g4 b/src/hastabel/LangParser.g4
new file mode 100644
index 0000000..0333bc1
--- /dev/null
+++ b/src/hastabel/LangParser.g4
@@ -0,0 +1,279 @@
+parser grammar LangParser;
+
+options
+{
+   tokenVocab = LangLexer;
+}
+
+@header
+{
+   package hastabel;
+
+   import hastabel.lang.Predicate;
+   import hastabel.lang.Element;
+}
+
+@members
+{
+   World WORLD;
+   /* of the class */
+}
+
+lang_file [World init_world]:
+   @init
+   {
+      WORLD = init_world;
+   }
+
+   (lang_instr)*
+   {
+   }
+;
+
+lang_instr:
+   (WS)* ADD_TYPE_KW (WS)* new_type (WS)*
+   {
+   }
+
+   | (WS)* ADD_RELATION_KW (WS)* new_predicate (WS)*
+   {
+   }
+
+   | (WS)* ADD_TEMPLATE_KW (WS)* new_template (WS)*
+   {
+   }
+
+   | (WS)* ID (WS)* L_PAREN (WS)* ident_list (WS*) R_PAREN (WS)*
+   {
+      final Predicate predicate;
+      final List<Element> params;
+      final Iterator<String> param_names;
+
+      predicate = WORLD.get_predicates_manager().get(($ID.text));
+
+      if (predicate == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         params = new ArrayList<Element>();
+
+         param_names = ($ident_list.list).iterator();
+
+         while (param_names.hasNext())
+         {
+            params.add(WORLD.get_elements_manager().get(param_names.next()));
+         }
+
+         predicate.add_member(params);
+      }
+   }
+
+   | (WS)* ID (WS)+ ident_list (WS)*
+   {
+      final Type type;
+      final Iterator<String> elem_names;
+
+      type = WORLD.get_types_manager().get(($ID.text));
+
+      if (type == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         elem_names = ($ident_list.list).iterator();
+
+         while (elem_names.hasNext())
+         {
+            WORLD.get_elements_manager().declare(type, elem_names.next());
+         }
+      }
+   }
+
+   | (WS)* STAR (WS)* ID (WS)+ ident_list (WS)*
+   {
+      final Template subtemplate;
+      final Iterator<String> elem_names;
+
+      subtemplate = WORLD.get_templates_manager().get(($ID.text));
+
+      if (subtemplate == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         elem_names = ($ident_list.list).iterator();
+
+         while (elem_names.hasNext())
+         {
+            final TemplateInstance ti;
+
+            ti =
+               WORLD.get_template_instances_manager().declare
+               (
+                  subtemplate,
+                  elem_names.next()
+               );
+
+            ti.add_contents_to
+            (
+               WORLD.get_elements_manager(),
+               WORLD.get_predicates_manager()
+            );
+         }
+      }
+   }
+;
+
+new_type:
+   parent=ID (WS)* SUB_TYPE_OF (WS)* type=ID
+   {
+      final Type parent_type;
+
+      parent_type = WORLD.get_types_manager().get(($parent.text));
+
+      WORLD.get_types_manager().declare(parent_type, ($type.text));
+   }
+
+   | ID
+   {
+      WORLD.get_types_manager().declare(null, ($ID.text));
+   }
+;
+
+new_predicate:
+   ID (WS)* L_PAREN (WS)* ident_list (WS)* R_PAREN
+   {
+      final List<Type> signature;
+      final Iterator<String> type_names;
+
+      signature = new ArrayList<Type>();
+
+      type_names = ($ident_list.list).iterator();
+
+      while (type_names.hasNext())
+      {
+         signature.add(WORLD.get_types_manager().get(type_names.next()));
+      }
+
+      WORLD.get_predicates_manager().declare(signature, ($ID.text));
+   }
+;
+
+new_template
+   @init
+   {
+      Template template;
+   }:
+
+   ID { template = WORLD.get_templates_manager().declare(($ID.text)); }
+   (WS)* L_BRAKT (WS)* (template_instr[template])* (WS)* R_BRAKT
+   {
+   }
+;
+
+template_instr [Template template]:
+   (WS)* ID (WS)* L_PAREN (WS)* ident_list (WS*) R_PAREN (WS)*
+   {
+      final Predicate predicate;
+      final List<Element> params;
+      final Iterator<String> param_names;
+
+      predicate =
+         template.get_predicates_manager().get_or_duplicate(($ID.text));
+
+      if (predicate == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         params = new ArrayList<Element>();
+
+         param_names = ($ident_list.list).iterator();
+
+         while (param_names.hasNext())
+         {
+            params.add(template.get_elements_manager().get(param_names.next()));
+         }
+
+         predicate.add_member(params);
+      }
+   }
+
+   | (WS)* ID (WS)+ ident_list (WS)*
+   {
+      final Type type;
+      final Iterator<String> elem_names;
+
+      type = WORLD.get_types_manager().get(($ID.text));
+
+      if (type == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         elem_names = ($ident_list.list).iterator();
+
+         while (elem_names.hasNext())
+         {
+            template.get_elements_manager().declare(type, elem_names.next());
+         }
+      }
+   }
+
+   | (WS)* STAR (WS)* ID (WS)+ ident_list (WS)*
+   {
+      final Template subtemplate;
+      final Iterator<String> elem_names;
+
+      subtemplate = WORLD.get_templates_manager().get(($ID.text));
+
+      if (subtemplate == null)
+      {
+         WORLD.invalidate();
+      }
+      else
+      {
+         elem_names = ($ident_list.list).iterator();
+
+         while (elem_names.hasNext())
+         {
+            final TemplateInstance ti;
+
+            ti = template.get_template_instances_manager.declare
+               (
+                  subtemplate,
+                  elem_names.next()
+               );
+
+            ti.add_contents_to(template);
+         }
+      }
+   }
+;
+
+ident_list returns [List<String> list]
+   @init
+   {
+      final List<String> result = new ArrayList<String>();
+   }
+
+   :
+   first_element=ID
+   (
+      (WS)* COMMA (WS)* next_element=ID
+      {
+         result.add(($next_element.text).replaceAll("\\.", "__"));
+      }
+   )*
+   {
+      result.add(0, ($first_element.text).replaceAll("\\.", "__"));
+
+      $list = result;
+   }
+;
diff --git a/src/hastabel/LogicWorld.java b/src/hastabel/LogicWorld.java
new file mode 100644
index 0000000..c14331a
--- /dev/null
+++ b/src/hastabel/LogicWorld.java
@@ -0,0 +1,34 @@
+package hastabel;
+
+import java.io.IOException;
+
+import org.antlr.v4.runtime.CharStreams;
+import org.antlr.v4.runtime.CommonTokenStream;
+
+class LogicWorld
+{
+   protected final Elements elements_mgr;
+   protected final Predicates predicates_mgr;
+
+   public LogicWorld ()
+   {
+      elements_mgr = new Elements();
+      predicates_mgr = new Predicates(null);
+   }
+
+   public LogicWorld (final LogicWorld parent)
+   {
+      elements_mgr = new Elements();
+      predicates_mgr = new Predicates(parent.get_predicates_manager());
+   }
+
+   public Elements get_elements_manager ()
+   {
+      return elements_mgr;
+   }
+
+   public Predicates get_predicates_manager ()
+   {
+      return predicates_mgr;
+   }
+}
diff --git a/src/hastabel/Predicates.java b/src/hastabel/Predicates.java
new file mode 100644
index 0000000..07c47a3
--- /dev/null
+++ b/src/hastabel/Predicates.java
@@ -0,0 +1,101 @@
+package hastabel;
+
+import hastabel.lang.Predicate;
+import hastabel.lang.Type;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.List;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.ArrayList;
+
+public class Predicates
+{
+   private final Map<String, Predicate> from_name;
+   private final Predicates parent_mgr;
+
+   public Predicates (final Predicates parent_mgr)
+   {
+      from_name = new HashMap<String, Predicate>();
+      this.parent_mgr = parent_mgr;
+   }
+
+   public Predicate declare (final List<Type> signature, final String name)
+   {
+      final Predicate result, previous_instance;
+
+      result = new Predicate(signature, name);
+
+      previous_instance = from_name.get(name);
+
+      if (previous_instance == null)
+      {
+         from_name.put(name, result);
+
+         return result;
+      }
+
+      if (signature.equals(previous_instance.get_signature()))
+      {
+         return previous_instance;
+      }
+
+      System.err.println
+      (
+         "[F] Conflicting signatures for predicate \""
+         + name
+         + "\"."
+      );
+
+      return null;
+   }
+
+   public Predicate get_or_duplicate (final String name)
+   {
+      Predicate result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         final Predicate main_predicate;
+
+         main_predicate = parent_mgr.get(name);
+
+         if (main_predicate == null)
+         {
+            return null;
+         }
+
+         result = main_predicate.shallow_copy();
+
+         from_name.put(name, result);
+      }
+
+      return result;
+   }
+
+   public Predicate get (final String name)
+   {
+      final Predicate result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         System.err.println("[E] Undeclared predicate \"" + name + "\".");
+
+         return null;
+      }
+
+      return result;
+   }
+
+   public Collection<Predicate> get_all ()
+   {
+      return from_name.values();
+   }
+}
diff --git a/src/hastabel/Template.java b/src/hastabel/Template.java
new file mode 100644
index 0000000..d1077d3
--- /dev/null
+++ b/src/hastabel/Template.java
@@ -0,0 +1,105 @@
+package hastabel;
+
+import hastabel.lang.Element;
+import hastabel.lang.Predicate;
+
+import java.util.List;
+import java.util.Collection;
+import java.util.ArrayList;
+
+public class Template extends LogicWorld
+{
+   private final static String INSTANCE_SEP = "__";
+
+   private final TemplateInstances template_instances;
+   private final String name;
+
+   public Template (final LogicWorld parent, final String name)
+   {
+      super(parent);
+
+      template_instances = new TemplateInstances();
+
+      this.name = name;
+   }
+
+   public String get_name ()
+   {
+      return name;
+   }
+
+   public TemplateInstances get_template_instances_manager ()
+   {
+      return template_instances;
+   }
+
+   public void add_contents_to (final String prefix, final Template t)
+   {
+      add_contents_to(prefix, t.elements, t.predicates);
+   }
+
+   public void add_contents_to
+   (
+      final String prefix,
+      final Elements dest_elements,
+      final Predicates dest_predicates
+   )
+   {
+      final String actual_prefix;
+
+      actual_prefix = prefix + INSTANCE_SEP;
+
+      for (final Element e: elements_mgr.get_all())
+      {
+         dest_elements.declare(e.get_type(), (actual_prefix + e.get_name()));
+      }
+
+      for (final Predicate orig_rel: predicates_mgr.get_all())
+      {
+         final Predicate dest_rel;
+
+         dest_rel = dest_predicates.get_or_duplicate(orig_rel.get_name());
+
+         for (final List<Element> orig_membs: orig_rel.get_members())
+         {
+            final List<Element> dest_membs;
+
+            dest_membs = new ArrayList<Element>(orig_membs.size());
+
+            for (final Element e: orig_membs)
+            {
+               dest_membs.add(dest_elements.get(actual_prefix + e.get_name()));
+            }
+
+            dest_rel.add_member(dest_membs);
+         }
+      }
+   }
+
+   @Override
+   public boolean equals (Object o)
+   {
+      final Template t;
+
+      if ((o == null) || !(o instanceof Template))
+      {
+         return false;
+      }
+
+      t = (Template) o;
+
+      return (t.name.equals(name));
+   }
+
+   @Override
+   public int hashCode ()
+   {
+      return name.hashCode();
+   }
+
+   @Override
+   public String toString ()
+   {
+      return "Template " + name;
+   }
+}
diff --git a/src/hastabel/TemplateInstance.java b/src/hastabel/TemplateInstance.java
new file mode 100644
index 0000000..16fa2a1
--- /dev/null
+++ b/src/hastabel/TemplateInstance.java
@@ -0,0 +1,37 @@
+package hastabel;
+
+public class TemplateInstance
+{
+   private final Template template;
+   private final String name;
+
+   public TemplateInstance
+   (
+      final Template template,
+      final String name
+   )
+   {
+      this.template = template;
+      this.name = name;
+   }
+
+   public String get_name ()
+   {
+      return name;
+   }
+
+   public Template get_template ()
+   {
+      return template;
+   }
+
+   public void add_contents_to (final Template t)
+   {
+      template.add_contents_to(name, t);
+   }
+
+   public void add_contents_to (final Elements e, final Predicates r)
+   {
+      template.add_contents_to(name, e, r);
+   }
+}
diff --git a/src/hastabel/TemplateInstances.java b/src/hastabel/TemplateInstances.java
new file mode 100644
index 0000000..35bba7f
--- /dev/null
+++ b/src/hastabel/TemplateInstances.java
@@ -0,0 +1,61 @@
+package hastabel;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.HashMap;
+
+public class TemplateInstances
+{
+   private final Map<String, TemplateInstance> from_name;
+
+   public TemplateInstances ()
+   {
+      from_name = new HashMap<String, TemplateInstance>();
+   }
+
+   public TemplateInstance declare (final Template template, final String name)
+   {
+      final TemplateInstance result, previous_instance;
+
+      result = new TemplateInstance(template, name);
+
+      previous_instance = from_name.get(name);
+
+      if (previous_instance == null)
+      {
+         from_name.put(name, result);
+
+         return result;
+      }
+
+      System.err.println
+      (
+         "[E] Multiple declarations for template instance \""
+         + name
+         + "\"."
+      );
+
+      return null;
+   }
+
+   public TemplateInstance get (final String name)
+   {
+      final TemplateInstance result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         System.err.println("[F] Undeclared template \"" + name + "\".");
+
+         return null;
+      }
+
+      return result;
+   }
+
+   public Collection<TemplateInstance> get_all ()
+   {
+      return from_name.values();
+   }
+}
diff --git a/src/hastabel/Templates.java b/src/hastabel/Templates.java
new file mode 100644
index 0000000..287906f
--- /dev/null
+++ b/src/hastabel/Templates.java
@@ -0,0 +1,63 @@
+package hastabel;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.HashMap;
+
+public class Templates
+{
+   private final Map<String, Template> from_name;
+
+   public Templates ()
+   {
+      from_name = new HashMap<String, Template>();
+   }
+
+   public Template declare (final LogicWorld parent, final String name)
+   {
+      final Template previous_instance;
+
+      previous_instance = from_name.get(name);
+
+      if (previous_instance == null)
+      {
+         final Template result;
+
+         result = new Template(parent, name);
+
+         from_name.put(name, result);
+
+         return result;
+      }
+
+      System.err.println
+      (
+         "[E] Multiple declarations for template \""
+         + name
+         + "\"."
+      );
+
+      return null;
+   }
+
+   public Template get (final String name)
+   {
+      final Template result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         System.err.println("[E] Undeclared template \"" + name + "\".");
+
+         return null;
+      }
+
+      return result;
+   }
+
+   public Collection<Template> get_all ()
+   {
+      return from_name.values();
+   }
+}
diff --git a/src/hastabel/Types.java b/src/hastabel/Types.java
new file mode 100644
index 0000000..1d7395e
--- /dev/null
+++ b/src/hastabel/Types.java
@@ -0,0 +1,75 @@
+package hastabel;
+
+import hastabel.lang.Type;
+
+import java.util.Map;
+import java.util.Set;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+
+public class Types
+{
+   private final Map<String, Type> from_name;
+
+   public Types ()
+   {
+      from_name = new HashMap<String, Type>();
+   }
+
+   public Type declare (final Type super_type, final String name)
+   {
+      final Type result, previous_instance;
+
+      result = new Type(super_type, name);
+
+      previous_instance = from_name.get(name);
+
+      if (previous_instance == null)
+      {
+         from_name.put(name, result);
+
+         if (super_type != null)
+         {
+            super_type.add_sub_type(result);
+         }
+
+         return result;
+      }
+
+      if (result.equals(previous_instance))
+      {
+         return previous_instance;
+      }
+
+      System.err.println
+      (
+         "[F] Conflicting declarations for type \""
+         + name
+         + "\"."
+      );
+
+      return null;
+   }
+
+   public Type get (final String name)
+   {
+      final Type result;
+
+      result = from_name.get(name);
+
+      if (result == null)
+      {
+         System.err.println("[F] Undeclared type \"" + name + "\".");
+
+         return null;
+      }
+
+      return result;
+   }
+
+   public Collection<Type> get_all ()
+   {
+      return from_name.values();
+   }
+}
diff --git a/src/hastabel/World.java b/src/hastabel/World.java
new file mode 100644
index 0000000..7dfce94
--- /dev/null
+++ b/src/hastabel/World.java
@@ -0,0 +1,54 @@
+package hastabel;
+
+import java.io.IOException;
+
+import org.antlr.v4.runtime.CharStreams;
+import org.antlr.v4.runtime.CommonTokenStream;
+
+public class World extends LogicWorld
+{
+   private final Templates templates_mgr;
+   private final TemplateInstances template_inst_mgr;
+
+   private final Types types_mgr;
+
+   private boolean is_erroneous;
+
+   public World ()
+   {
+      super();
+
+      templates_mgr = new Templates();
+      template_inst_mgr = new TemplateInstances();
+
+      types_mgr = new Types();
+
+      is_erroneous = false;
+   }
+
+   public boolean load (final String filename)
+   throws IOException
+   {
+      final CommonTokenStream tokens;
+      final LangLexer lexer;
+      final LangParser parser;
+
+      lexer = new LangLexer(CharStreams.fromFileName(filename));
+      tokens = new CommonTokenStream(lexer);
+      parser = new LangParser(tokens);
+
+      parser.lang_file(this);
+
+      return !is_erroneous;
+   }
+
+   public void invalidate ()
+   {
+      is_erroneous = true;
+   }
+
+   public boolean is_valid ()
+   {
+      return !is_erroneous;
+   }
+}
diff --git a/src/hastabel/lang/Element.java b/src/hastabel/lang/Element.java
new file mode 100644
index 0000000..b167885
--- /dev/null
+++ b/src/hastabel/lang/Element.java
@@ -0,0 +1,50 @@
+package hastabel.lang;
+
+public class Element
+{
+   public final Type type;
+   public final String name;
+
+   public Element (final Type type, final String name)
+   {
+      this.type = type;
+      this.name = name;
+   }
+
+   public String get_name ()
+   {
+      return name;
+   }
+
+   public Type get_type ()
+   {
+      return type;
+   }
+
+   @Override
+   public boolean equals (Object o)
+   {
+      final Element e;
+
+      if ((o == null) || !(o instanceof Element))
+      {
+         return false;
+      }
+
+      e = (Element) o;
+
+      return (e.name.equals(name) && e.type.equals(type));
+   }
+
+   @Override
+   public int hashCode ()
+   {
+      return (name + '@' + type.get_name()).hashCode();
+   }
+
+   @Override
+   public String toString ()
+   {
+      return (type.get_name() + " " + name);
+   }
+}
diff --git a/src/hastabel/lang/Predicate.java b/src/hastabel/lang/Predicate.java
new file mode 100644
index 0000000..835206c
--- /dev/null
+++ b/src/hastabel/lang/Predicate.java
@@ -0,0 +1,155 @@
+package hastabel.lang;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.List;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.ArrayList;
+
+public class Predicate
+{
+   private final List<Type> signature;
+   private final Set<List<Element>> members;
+   private final String name;
+
+   public Predicate (final List<Type> signature, final String name)
+   {
+      this.signature = signature;
+      this.name = name;
+
+      members = new HashSet<List<Element>>();
+   }
+
+   public void add_member (final List<Element> elements)
+   {
+      if (is_compatible_with(elements))
+      {
+         members.add(elements);
+      }
+   }
+
+   public boolean is_compatible_with (final List<Element> elements)
+   {
+      final Iterator<Element> e_iter;
+      final Iterator<Type> s_iter;
+
+      if (elements.size() != signature.size())
+      {
+         return false;
+      }
+
+      e_iter = elements.iterator();
+      s_iter = signature.iterator();
+
+      while (e_iter.hasNext())
+      {
+         if (!s_iter.next().includes(e_iter.next().get_type()))
+         {
+            return false;
+         }
+      }
+
+      return true;
+   }
+
+   public String get_name ()
+   {
+      return name;
+   }
+
+   public List<Type> get_signature ()
+   {
+      return signature;
+   }
+
+   public Set<List<Element>> get_members ()
+   {
+      return members;
+   }
+
+   public Predicate shallow_copy ()
+   {
+      return new Predicate(signature, name);
+   }
+
+   @Override
+   public boolean equals (Object o)
+   {
+      final Predicate e;
+
+      if ((o == null) || !(o instanceof Predicate))
+      {
+         return false;
+      }
+
+      e = (Predicate) o;
+
+      return (e.name.equals(name));
+   }
+
+   @Override
+   public int hashCode ()
+   {
+      return name.hashCode();
+   }
+
+   public String get_definition ()
+   {
+      final StringBuilder sb;
+
+      sb = new StringBuilder();
+
+      sb.append(toString());
+      sb.append("\n");
+
+      for (final List<Element> params: members)
+      {
+         sb.append(name);
+         sb.append("(");
+
+         for (final Element param: params)
+         {
+            sb.append(param.get_name());
+            sb.append(", ");
+         }
+
+         sb.append(")\n");
+      }
+
+      return sb.toString();
+   }
+
+   @Override
+   public String toString ()
+   {
+      final StringBuilder sb;
+      final Iterator<Type> s_iter;
+
+      sb = new StringBuilder();
+      s_iter = signature.iterator();
+
+      sb.append(name);
+      sb.append(": ");
+
+      if (!s_iter.hasNext())
+      {
+         sb.append("(no params)");
+
+         return sb.toString();
+     }
+
+      sb.append(s_iter.next().get_name());
+      sb.append(" ");
+
+      while (s_iter.hasNext())
+      {
+         sb.append("x ");
+         sb.append(s_iter.next().get_name());
+      }
+
+      return sb.toString();
+   }
+}
diff --git a/src/hastabel/lang/Type.java b/src/hastabel/lang/Type.java
new file mode 100644
index 0000000..9676605
--- /dev/null
+++ b/src/hastabel/lang/Type.java
@@ -0,0 +1,100 @@
+package hastabel.lang;
+
+import java.util.Map;
+import java.util.Set;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+
+public class Type
+{
+   private final Set<Element> elements;
+   private final Set<Type> sub_types;
+   private final Type super_type;
+   private final String name;
+
+   public Type (final Type super_type, final String name)
+   {
+      this.name = name;
+      this.elements = new HashSet<Element>();
+      this.sub_types = new HashSet<Type>();
+      this.super_type = super_type;
+   }
+
+   public void add_sub_type (final Type t)
+   {
+      sub_types.add(t);
+
+      if (super_type != null)
+      {
+         super_type.add_sub_type(t);
+      }
+   }
+
+   public String get_name ()
+   {
+      return name;
+   }
+
+   public void add_element (final Element e)
+   {
+      elements.add(e);
+   }
+
+   public Set<Element> get_elements ()
+   {
+      return elements;
+   }
+
+   public boolean includes (final Type t)
+   {
+      return (this.equals(t) || sub_types.contains(t));
+   }
+
+   @Override
+   public boolean equals (Object o)
+   {
+      final Type t;
+
+      if ((o == null) || !(o instanceof Type))
+      {
+         return false;
+      }
+
+      t = (Type) o;
+
+      return
+         (
+            t.name.equals(name)
+            &&
+            (
+               ((super_type == null) && (t.super_type == null))
+               || super_type.equals(t.super_type)
+            )
+         );
+   }
+
+   @Override
+   public int hashCode ()
+   {
+      return name.hashCode();
+   }
+
+   @Override
+   public String toString ()
+   {
+      final StringBuilder sb;
+
+      sb = new StringBuilder();
+
+      if (super_type != null)
+      {
+         sb.append(super_type.get_name());
+         sb.append("::");
+      }
+
+      sb.append(name);
+
+      return sb.toString();
+   }
+}