...

3 files changed, 256 insertions, 219 deletions

diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
index 0712319..2e595cd 100644
--- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java
@@ -22,9 +22,11 @@ import tonkadur.wyrd.v1.lang.instruction.SetValue;
 import tonkadur.wyrd.v1.lang.instruction.Initialize;
 import tonkadur.wyrd.v1.lang.instruction.SetPC;
 
+import tonkadur.wyrd.v1.compiler.util.AddElement;
 import tonkadur.wyrd.v1.compiler.util.BinarySearch;
 import tonkadur.wyrd.v1.compiler.util.IfElse;
 import tonkadur.wyrd.v1.compiler.util.If;
+import tonkadur.wyrd.v1.compiler.util.Fold;
 import tonkadur.wyrd.v1.compiler.util.Shuffle;
 import tonkadur.wyrd.v1.compiler.util.RemoveAt;
 import tonkadur.wyrd.v1.compiler.util.InsertAt;
@@ -1955,7 +1957,48 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor
    )
    throws Throwable
    {
-      /* TODO */
+      final ComputationCompiler address_compiler, element_compiler;
+      final Register result;
+
+      result = reserve(TypeCompiler.compile(compiler, n.get_type()));
+
+      result_as_address = result.get_address();
+      result_as_computation = result.get_value();
+
+      address_compiler = new ComputationCompiler(compiler);
+      element_compiler = new ComputationCompiler(compiler);
+
+      n.get_collection().get_visited_by(address_compiler);
+
+      if (address_compiler.has_init())
+      {
+         init_instructions.add(address_compiler.get_init());
+      }
+
+      init_instructions.add
+      (
+         new SetValue(result_as_address, address_compiler.get_computation())
+      );
+
+      address_compiler.release_registers(init_instructions);
+
+      n.get_element().get_visited_by(element_compiler);
+      assimilate(element_compiler);
+
+      init_instructions.add
+      (
+         AddElement.generate
+         (
+            compiler.registers(),
+            compiler.assembler(),
+            element_compiler.get_computation(),
+            result_as_address,
+            (
+               (tonkadur.fate.v1.lang.type.CollectionType)
+               n.get_collection().get_type()
+            ).is_set()
+         )
+      );
    }
 
    @Override
@@ -1994,18 +2037,10 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor
       n.get_index().get_visited_by(index_compiler);
 
       index_compiler.generate_address();
-
-      if (index_compiler.has_init())
-      {
-         init_instructions.add(index_compiler.get_init());
-      }
+      assimilate(index_compiler);
 
       n.get_element().get_visited_by(element_compiler);
-
-      if (element_compiler.has_init())
-      {
-         init_instructions.add(element_compiler.get_init());
-      }
+      assimilate(element_compiler);
 
       collection_size = reserve(Type.INT);
       index = reserve(Type.INT);
@@ -2068,7 +2103,54 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor
    )
    throws Throwable
    {
-      /* TODO */
+      final ComputationCompiler lambda_cc, in_collection_cc, default_cc;
+      final Register result;
+
+      result = reserve(TypeCompiler.compile(compiler, n.get_type()));
+
+      result_as_address = result.get_address();
+      result_as_computation = result.get_value();
+
+      default_cc = new ComputationCompiler(compiler);
+
+      n.get_default().get_visited_by(default_cc);
+
+      if (default_cc.has_init())
+      {
+         init_instructions.add(default_cc.get_init());
+      }
+
+      init_instructions.add
+      (
+         new SetValue(result_as_address, default_cc.get_computation())
+      );
+
+      default_cc.release_registers(init_instructions());
+
+      lambda_cc = new ComputationCompiler(compiler);
+
+      n.get_lambda_function().get_visited_by(lambda_cc);
+
+      assimilate(lambda_cc);
+
+      in_collection_cc = new ComputationCompiler(compiler);
+
+      n.get_collection().get_visited_by(in_collection_cc);
+
+      assimilate(in_collection_cc);
+
+      init_instructions.add
+      (
+         Fold.generate
+         (
+            compiler.registers(),
+            compiler.assembler(),
+            lambda_cc.get_computation(),
+            result_as_address,
+            in_collection_cc.get_address(),
+            n.is_foldl()
+         )
+      );
    }
 
    @Override
@@ -2113,7 +2195,6 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor
             ).is_set()
          )
       );
-
    }
 
    @Override
diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
index 5d46b79..931a8ca 100644
--- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java
@@ -41,6 +41,7 @@ import tonkadur.wyrd.v1.lang.instruction.ResolveChoices;
 import tonkadur.wyrd.v1.lang.instruction.SetPC;
 import tonkadur.wyrd.v1.lang.instruction.SetValue;
 
+import tonkadur.wyrd.v1.compiler.util.AddElement;
 import tonkadur.wyrd.v1.compiler.util.BinarySearch;
 import tonkadur.wyrd.v1.compiler.util.InsertAt;
 import tonkadur.wyrd.v1.compiler.util.If;
@@ -74,188 +75,6 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor
       return compiler.assembler().merge(result);
    }
 
-   protected void add_element_to_set
-   (
-      final tonkadur.fate.v1.lang.instruction.AddElement ae
-   )
-   throws Throwable
-   {
-      /*
-       * Fate:
-       * (add_element element collection)
-       *
-       * Wyrd:
-       * (declare_variable local <element.type> .anon0)
-       * (set .anon0 element)
-       * (declare_variable local boolean .found)
-       * <binary_search .anon0 collection .found .index>
-       * (ifelse (var .found)
-       *    (nop)
-       *    <insert_at ...>
-       * )
-       */
-      final ComputationCompiler element_compiler, address_compiler;
-      final Address element, collection;
-      final Register collection_size, element_found, element_index;
-      final Type element_type;
-
-      element_compiler = new ComputationCompiler(compiler);
-      ae.get_element().get_visited_by(element_compiler);
-
-      element_compiler.generate_address();
-
-      if (element_compiler.has_init())
-      {
-         result.add(element_compiler.get_init());
-      }
-
-      element_type = element_compiler.get_computation().get_type();
-      element = element_compiler.get_address();
-
-      address_compiler = new ComputationCompiler(compiler);
-      ae.get_collection().get_visited_by(address_compiler);
-
-      if (address_compiler.has_init())
-      {
-         result.add(address_compiler.get_init());
-      }
-
-      collection = address_compiler.get_address();
-
-      element_found = compiler.registers().reserve(Type.BOOL, result);
-      element_index = compiler.registers().reserve(Type.INT, result);
-      collection_size = compiler.registers().reserve(Type.INT, result);
-
-      result.add
-      (
-         new SetValue(collection_size.get_address(), new Size(collection))
-      );
-
-      result.add
-      (
-         BinarySearch.generate
-         (
-            compiler.registers(),
-            compiler.assembler(),
-            new ValueOf(element),
-            collection_size.get_value(),
-            collection,
-            element_found.get_address(),
-            element_index.get_address()
-         )
-      );
-
-      result.add
-      (
-         If.generate
-         (
-            compiler.registers(),
-            compiler.assembler(),
-            Operation.not(element_found.get_value()),
-            InsertAt.generate
-            (
-               compiler.registers(),
-               compiler.assembler(),
-               element_index.get_address(),
-               new ValueOf(element),
-               collection_size.get_value(),
-               collection
-            )
-         )
-      );
-
-      compiler.registers().release(element_found, result);
-      compiler.registers().release(element_index, result);
-      compiler.registers().release(collection_size, result);
-
-      element_compiler.release_registers(result);
-      address_compiler.release_registers(result);
-   }
-
-   protected void add_element_to_list
-   (
-      final tonkadur.fate.v1.lang.instruction.AddElement ae
-   )
-   throws Throwable
-   {
-      /*
-       * Fate:
-       * (add_element element collection)
-       *
-       * Wyrd:
-       * (set
-       *    (relative_address collection ( (cast int string (size collection)) ))
-       *    (element)
-       * )
-       */
-      final Address collection_as_address;
-      final ComputationCompiler element_compiler, address_compiler;
-
-      element_compiler = new ComputationCompiler(compiler);
-
-      ae.get_element().get_visited_by(element_compiler);
-
-      address_compiler = new ComputationCompiler(compiler);
-
-      ae.get_collection().get_visited_by(address_compiler);
-
-
-      if (address_compiler.has_init())
-      {
-         result.add(address_compiler.get_init());
-      }
-
-      if (element_compiler.has_init())
-      {
-         result.add(element_compiler.get_init());
-      }
-
-      collection_as_address = address_compiler.get_address();
-
-      result.add
-      (
-         new Initialize
-         (
-            new RelativeAddress
-            (
-               collection_as_address,
-               new Cast
-               (
-                  new Size(collection_as_address),
-                  Type.STRING
-               ),
-               element_compiler.get_computation().get_type()
-            ),
-            element_compiler.get_computation().get_type()
-         )
-      );
-
-      result.add
-      (
-         new SetValue
-         (
-            new RelativeAddress
-            (
-               collection_as_address,
-               new Cast
-               (
-                  Operation.minus
-                  (
-                     new Size(collection_as_address),
-                     Constant.ONE
-                  ),
-                  Type.STRING
-               ),
-               element_compiler.get_computation().get_type()
-            ),
-            element_compiler.get_computation()
-         )
-      );
-
-      address_compiler.release_registers(result);
-      element_compiler.release_registers(result);
-   }
-
    @Override
    public void visit_local_variable
    (
@@ -400,41 +219,46 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor
    @Override
    public void visit_add_element
    (
-      final tonkadur.fate.v1.lang.instruction.AddElement ae
+      final tonkadur.fate.v1.lang.instruction.AddElement n
    )
    throws Throwable
    {
-      final tonkadur.fate.v1.lang.type.Type collection_type;
-      final tonkadur.fate.v1.lang.type.CollectionType collection_true_type;
+      final ComputationCompiler address_compiler, element_compiler;
 
-      collection_type = ae.get_collection().get_type();
+      address_compiler = new ComputationCompiler(compiler);
+      element_compiler = new ComputationCompiler(compiler);
 
-      if
-      (
-         !(collection_type instanceof tonkadur.fate.v1.lang.type.CollectionType)
-      )
+      n.get_collection().get_visited_by(address_compiler);
+
+      if (address_compiler.has_init())
       {
-         System.err.println
-         (
-            "[P] (add_element item collection), but this is not a collection: "
-            + ae.get_collection()
-            + ". It's a "
-            + collection_type.get_name()
-            + "."
-         );
+         result.add(address_compiler.get_init());
       }
 
-      collection_true_type =
-         (tonkadur.fate.v1.lang.type.CollectionType) collection_type;
+      n.get_element().get_visited_by(element_compiler);
 
-      if (collection_true_type.is_set())
-      {
-         add_element_to_set(ae);
-      }
-      else
+      if (element_compiler.has_init())
       {
-         add_element_to_list(ae);
+         result.add(element_compiler.get_init());
       }
+
+      result.add
+      (
+         AddElement.generate
+         (
+            compiler.registers(),
+            compiler.assembler(),
+            element_compiler.get_computation(),
+            address_compiler.get_address(),
+            (
+               (tonkadur.fate.v1.lang.type.CollectionType)
+               n.get_collection().get_type()
+            ).is_set()
+         )
+      );
+
+      element_compiler.release_registers(result);
+      address_compiler.release_registers(result);
    }
 
    @Override
diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/Fold.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/Fold.java
new file mode 100644
index 0000000..1596dff
--- /dev/null
+++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/Fold.java
@@ -0,0 +1,132 @@
+package tonkadur.wyrd.v1.compiler.util;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Collections;
+
+import tonkadur.wyrd.v1.lang.Register;
+
+import tonkadur.wyrd.v1.lang.type.Type;
+import tonkadur.wyrd.v1.lang.type.MapType;
+
+import tonkadur.wyrd.v1.lang.meta.Instruction;
+import tonkadur.wyrd.v1.lang.meta.Computation;
+
+import tonkadur.wyrd.v1.lang.computation.Cast;
+import tonkadur.wyrd.v1.lang.computation.Constant;
+import tonkadur.wyrd.v1.lang.computation.Operation;
+import tonkadur.wyrd.v1.lang.computation.Address;
+import tonkadur.wyrd.v1.lang.computation.RelativeAddress;
+import tonkadur.wyrd.v1.lang.computation.ValueOf;
+import tonkadur.wyrd.v1.lang.computation.Size;
+
+import tonkadur.wyrd.v1.lang.instruction.SetValue;
+
+import tonkadur.wyrd.v1.compiler.util.registers.RegisterManager;
+
+public class Fold
+{
+   /* Utility Class */
+   private Fold () {}
+
+   /* Uses Durstenfeld's shuffling algorithm */
+   public static Instruction generate
+   (
+      final RegisterManager registers,
+      final InstructionManager assembler,
+      final Computation lambda,
+      final Address storage_address,
+      final Address collection_in,
+      final boolean is_foldl
+   )
+   {
+      final List<Computation> params;
+      final List<Instruction> result, while_body;
+      final Register iterator, collection_in_size;
+      final Computation start_point, end_point, condition, increment;
+
+      params = new ArrayList<Computation>();
+      result = new ArrayList<Instruction>();
+      while_body = new ArrayList<Instruction>();
+
+      iterator = registers.reserve(Type.INT, result);
+      collection_in_size = registers.reserve(Type.INT, result);
+
+      if (is_foldl)
+      {
+         end_point = collection_in_size.get_value();
+         start_point = Constant.ZERO;
+         condition = Operation.less_than(iterator.get_value(), end_point);
+         increment = Operation.plus(iterator.get_value(), Constant.ONE);
+      }
+      else
+      {
+         end_point = Constant.ZERO;
+         start_point =
+            Operation.minus(collection_in_size.get_value(), Constant.ONE);
+         condition = Operation.greater_equal_than(iterator.get_value(), end_point);
+         increment = Operation.minus(iterator.get_value(), Constant.ONE);
+      }
+
+
+      result.add
+      (
+         new SetValue
+         (
+            collection_in_size.get_address(),
+            new Size(collection_in)
+         )
+      );
+
+      result.add(new SetValue(iterator.get_address(), start_point));
+
+      params.add(new ValueOf(storage_address));
+      params.add
+      (
+         new ValueOf
+         (
+            new RelativeAddress
+            (
+               collection_in,
+               new Cast(iterator.get_value(), Type.STRING),
+               (
+                  (MapType) collection_in.get_target_type()
+               ).get_member_type()
+            )
+         )
+      );
+
+      while_body.add
+      (
+         LambdaEvaluation.generate
+         (
+            registers,
+            assembler,
+            lambda,
+            /* Can't put it in the target collection directly, since that may
+             * be a set.
+             */
+            storage_address,
+            params
+         )
+      );
+
+      while_body.add(new SetValue(iterator.get_address(), increment));
+
+      result.add
+      (
+         While.generate
+         (
+            registers,
+            assembler,
+            condition,
+            assembler.merge(while_body)
+         )
+      );
+
+      registers.release(iterator, result);
+      registers.release(collection_in_size, result);
+
+      return assembler.merge(result);
+   }
+}