From d4eb4ff9a013c870936b7546a65bdfd048c60133 Mon Sep 17 00:00:00 2001 From: nsensfel Date: Tue, 15 Sep 2020 10:03:29 +0200 Subject: Fully implements shuffle. --- data/tests/extra_functionals.fate | 13 +++ .../v1/compiler/fate/v1/ComputationCompiler.java | 35 +++++- .../v1/compiler/fate/v1/InstructionCompiler.java | 5 +- .../tonkadur/wyrd/v1/compiler/util/Shuffle.java | 118 +++++++++++++++++++++ 4 files changed, 166 insertions(+), 5 deletions(-) create mode 100644 src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java diff --git a/data/tests/extra_functionals.fate b/data/tests/extra_functionals.fate index 090ab5b..bc629cb 100644 --- a/data/tests/extra_functionals.fate +++ b/data/tests/extra_functionals.fate @@ -42,4 +42,17 @@ (car (cdr (cdr (cdr (cons 1 (cons 2 (cons 3 (cons 4 5)))))))) (cdr (cdr (cdr (cdr (cons 1 (cons 2 (cons 3 (cons 4 5)))))))) +(global (list int) int_list_a) +(global (list int) int_list_b) +(global (list int) int_list_c) +(global int i) + +(for (set i 0) (< (var i) 10) (set i (+ (var i) 1)) + (add! (var i) int_list_a) + (add! (var i) int_list_c) +) + +(set int_list_b (shuffle int_list_a)) +(shuffle! int_list_c) + (end) 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 f7893be..ccfc525 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 @@ -23,6 +23,7 @@ import tonkadur.wyrd.v1.lang.instruction.SetPC; 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.Shuffle; import tonkadur.wyrd.v1.compiler.util.RemoveAt; import tonkadur.wyrd.v1.compiler.util.CreateCons; import tonkadur.wyrd.v1.compiler.util.IterativeSearch; @@ -2059,7 +2060,39 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor ) throws Throwable { - /* TODO */ + final ComputationCompiler address_compiler; + final Address collection_address; + 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); + + 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); + + init_instructions.add + ( + Shuffle.generate + ( + compiler.registers(), + compiler.assembler(), + result_as_address + ) + ); } @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 c8488d8..1f47d8f 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 @@ -48,6 +48,7 @@ import tonkadur.wyrd.v1.compiler.util.IfElse; import tonkadur.wyrd.v1.compiler.util.InstructionManager; import tonkadur.wyrd.v1.compiler.util.NOP; import tonkadur.wyrd.v1.compiler.util.While; +import tonkadur.wyrd.v1.compiler.util.Shuffle; import tonkadur.wyrd.v1.compiler.util.Clear; import tonkadur.wyrd.v1.compiler.util.IterativeSearch; import tonkadur.wyrd.v1.compiler.util.RemoveAllOf; @@ -572,19 +573,15 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor collection_address = address_compiler.get_address(); - /* - * TODO result.add ( Shuffle.generate ( compiler.registers(), compiler.assembler(), - new Size(collection_address), collection_address ) ); - */ address_compiler.release_registers(result); } diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java new file mode 100644 index 0000000..45dbd81 --- /dev/null +++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/Shuffle.java @@ -0,0 +1,118 @@ +package tonkadur.wyrd.v1.compiler.util; + +import java.util.List; +import java.util.ArrayList; + +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.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 Shuffle +{ + /* Utility Class */ + private Shuffle () {} + + /* Uses Durstenfeld's shuffling algorithm */ + public static Instruction generate + ( + final RegisterManager registers, + final InstructionManager assembler, + final Address collection + ) + { + final List result, while_body; + final Type element_type; + final Register iterator, target_index; + final Register storage; + final Address a_i, a_j; + + result = new ArrayList(); + while_body = new ArrayList(); + + element_type = + ((MapType) collection.get_target_type()).get_member_type(); + + iterator = registers.reserve(Type.INT, result); + target_index = registers.reserve(Type.INT, result); + storage = registers.reserve(element_type, result); + + a_i = + new RelativeAddress + ( + collection, + new Cast(iterator.get_value(), Type.STRING), + element_type + ); + + a_j = + new RelativeAddress + ( + collection, + new Cast(target_index.get_value(), Type.STRING), + element_type + ); + + while_body.add + ( + new SetValue + ( + target_index.get_address(), + Operation.rand(Constant.ZERO, iterator.get_value()) + ) + ); + + while_body.add(new SetValue(storage.get_address(), new ValueOf(a_i))); + while_body.add(new SetValue(a_i, new ValueOf(a_j))); + while_body.add(new SetValue(a_j, storage.get_value())); + + while_body.add + ( + new SetValue + ( + iterator.get_address(), + Operation.minus(iterator.get_value(), Constant.ONE) + ) + ); + + result.add + ( + new SetValue + ( + iterator.get_address(), + Operation.minus(new Size(collection), Constant.ONE) + ) + ); + + result.add + ( + While.generate + ( + registers, + assembler, + Operation.greater_than(iterator.get_value(), Constant.ZERO), + assembler.merge(while_body) + ) + ); + + registers.release(iterator, result); + registers.release(target_index, result); + registers.release(storage, result); + + return assembler.merge(result); + } +} -- cgit v1.2.3-70-g09d2