Changeset 1825

Timestamp:

06/06/08 17:43:51 (6 months ago)

Author:

jmaessen

Message:

New comprehension/reduction desugaring (part I). Big operators now
take no arguments and return a BigOperator? object; this and the old
desugaring are taken as arguments by the bigOperator function to
produce the result of the comprehension or reduction. Next step is
double reductions.

Files:

• trunk/Library/FortressLibrary.fsi (modified) (2 diffs)
• trunk/Library/FortressLibrary.fss (modified) (16 diffs)
• trunk/Library/List.fsi (modified) (2 diffs)
• trunk/Library/List.fss (modified) (1 diff)
• trunk/Library/Map.fss (modified) (1 diff)
• trunk/Library/PureList.fss (modified) (1 diff)
• trunk/Library/Set.fss (modified) (2 diffs)
• trunk/ProjectFortress/demos/wordcount.fss (modified) (1 diff)
• trunk/ProjectFortress/demos/zeno.fss (modified) (1 diff)
• trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/OverloadedFunction.java (modified) (1 diff)
• trunk/ProjectFortress/src/com/sun/fortress/interpreter/rewrite/Desugarer.java (modified) (2 diffs)
• trunk/ProjectFortress/src/com/sun/fortress/nodes_util/ExprFactory.java (modified) (1 diff)
• trunk/ProjectFortress/src/com/sun/fortress/nodes_util/Span.java (modified) (1 diff)
• trunk/ProjectFortress/tests/HeapTest.fss (modified) (2 diffs)
• trunk/ProjectFortress/tests/MapExprTest.fss (modified) (1 diff)
• trunk/ProjectFortress/tests/WordCountSmall.fss (modified) (2 diffs)
• trunk/ProjectFortress/tests/simpleBig.fss (modified) (1 diff)

trunk/Library/FortressLibrary.fsi

@@ -500 +500 @@
-__generate[\E,R\](g:Generator[\E\], r: Reduction[\R\], b:E->R): R
-
+__filter[\E\](g:Generator[\E\], p:E->Condition[\()\]): Generator[\E\]
+__bigOperator[\I,O,R,L\](o:BigOperator[\I,O,R,L\],desugaredClauses:(Reduction[\L\],I->L)->L): O
+
-(* Not currently used for desugaring, but will be used in future.
-__nest[\E1,E2\](g:Generator[\E1\], f:E1->Generator[\E2\]):Generator[\E2\]
@@ -1445 +1448 @@
-end
-
-
+O,
-    abstract getter reduction(): ActualReduction[\R,L\]
-    abstract getter body(): I->R
-
-
-
+
+
+
+
-    getter reduction(): ActualReduction[\R,L\]
-    getter body(): R->R
-
-
-
-
+
+
+
+
+
-    getter reduction(): ActualReduction[\R,L\]
-    getter body(): I->R
+    getter unwrap(): R->O
-end
-

trunk/Library/FortressLibrary.fss

@@ -620 +620 @@
-        SimpleNestedGenerator[\E,G\](self,f)
-
+    (** Filtering data from a generator.  Only elements that satisfy
+        the predicate p are retained.  Natural order and cross product
+        properties are otherwise preserved. **)
+    filter(f: E -> Condition[\()\]): Generator[\E\] =
+        SimpleFilterGenerator[\E\](self,f)
+
-    (** Cross product of two generators.  This is specifically
-        designed to be overloaded, such that pairs of independent
@@ -699 +705 @@
-
-(** Unlike the user-visible dotted map method, this method is used for
-
-
-
-
+
+
+
+
+
-__map[\E,R\](g:Generator[\E\], f:E->R): Generator[\R\] =
-    typecase g of
+        SomeMappedGenerator[\E\] => g.map[\R\](f)
-        SequentialGenerator[\E\] => SimpleMappedSeqGenerator[\E,R\](g,f)
-        else => SimpleMappedGenerator[\E,R\](g,f)
-    end
+
+(** Unlike the user-visible dotted filter method, but like the __map
+    method, this method is intended for use in the internals of
+    comprehension desugaring.  Again its result will immediately be
+    consumed, and we do not create an intermediate collection but
+    perform the filtering lazily on demand. **)
+__filter[\E\](g:Generator[\E\], p:E->Condition[\()\]): Generator[\E\] =
+    typecase g of
+        FilterGenerator[\E\] => g.filter(p)
+        SequentialGenerator[\E\] => SimpleSeqFilterGenerator[\E\](g,p)
+        else => SimpleFilterGenerator[\E\](g,p)
+    end
+
+(** Application of a BIG operator, the topmost level of comprehension desugaring. **)
+__bigOperator[\I,O,R,L\](o:BigOperator[\I,O,R,L\],desugaredClauses:(Reduction[\L\],I->L)->L): O = do
+    r = o.reduction()
+    body(i): L = r.lift((o.body())(i))
+    (o.unwrap())(r.unlift(desugaredClauses(r,body)))
+  end
-
-trait SequentialGenerator[\E\] extends { Generator[\E\] }
@@ -770 +797 @@
-    opr IN(x:E, self):Boolean = cond[\Boolean\](fn (e:E):Boolean => x=e, fn () => false)
-end
+
+(** Conjunction and disjunction of condition functions **)
+opr ANDCOND[\I\](p1:I->Condition[\()\], p2:I->Condition[\()\]): I->Condition[\()\] =
+    fn (i:I):Boolean => p1(i).holds() AND: p2(i).holds()
+
+(** Conjunction and disjunction of condition functions **)
+opr ORCOND[\I\](p1:I->Condition[\()\], p2:I->Condition[\()\]): I->Condition[\()\] =
+    fn (i:I):Boolean => p1(i).holds() OR: p2(i).holds()
-
-(** Operations which use generation internally.  Should be functional
@@ -2159 +2194 @@
-    empty(): L
-    join(a: L, b: L): L
-R
+ Any
-    unlift(l:L): R
-    (** If this reduction left-distributes over r, return a pair of
-        reductions with the same lift and unlift **)
-Maybe[\(Reduction[\R\],Reduction[\R\])
+SomeReductionPair[\R
-        distribute(r)
-    (** If this reduction right-distributes over r, return a pair of
-        reductions with the same lift and unlift **)
-Maybe[\(Reduction[\R\],Reduction[\R\])
+SomeReductionPair[\R
-        distribute(r)
-    (** If this reduction distributes over r, return a pair of
-        reductions with the same lift and unlift **)
-(r: Reduction[\R\]): Maybe[\(Reduction[\R\],Reduction[\R\])
-thing[\(Reduction[\R\],Reduction[\R\])
+[\K\](r: ActualReduction[\R,K\]): SomeReductionPair[\R
+ReductionPair[\R
-end
-
@@ -2197 +2232 @@
-
-(** The usual lifting to Maybe for identity-less operators **)
-Maybe[\R\]
+AnyMaybe
-    empty(): Nothing[\R\] = Nothing[\R\]
-Maybe[\R\], b: Maybe[\R\]): Maybe[\R\]
+AnyMaybe, b: AnyMaybe): AnyMaybe
-        if av <- a then
-            if bv <- b then
-[\R\]
+
-            else
-                a
@@ -2209 +2244 @@
-            b
-        end
-R, b:R): R
-R): Maybe[\R\] = Maybe[\R\]
-Maybe[\R\]
+Any, b:Any): Any
+Any): AnyMaybe = Just
+AnyMaybe
-end
-
@@ -2218 +2253 @@
-(** Monoids don't require a special lift and unlift operation. **)
-trait MonoidReduction[\R\] extends ActualReduction[\R,R\]
-R
+Any
-    unlift(r:R): R = r
-end
@@ -2230 +2265 @@
-end
-
-
+O,
-    getter reduction(): ActualReduction[\R,L\]
-    getter body(): I->R
-
-
-
+
+
+
+
-    getter reduction(): ActualReduction[\R,L\] = r
-
-
-
-
-
+
+
+
+
+
+
-    getter reduction(): ActualReduction[\R,L\] = r
-    getter body(): I->R = singleton
+    getter unwrap(): R->O = u
-end
-
@@ -2263 +2301 @@
-end
-
-\](g:(Reduction[\Number\],T->Number)->Number): Number
-g(SumReduction,
+ extends Number\](): Comprehension[\T,Number,Number,Number\]
+Comprehension[\T,Number,Number,Number\](fn x => x, SumReduction, 
-
-object ProdReduction extends CommutativeMonoidReduction[\Number\]
@@ -2272 +2310 @@
-end
-
-\](g:(Reduction[\Number\],T->Number)->Number): Number
-g(ProdReduction,
+ extends Number\](): Comprehension[\T,Number,Number,Number\]
+Comprehension[\T,Number,Number,Number\](fn x => x, ProdReduction, 
-
-object MinReduction[\T extends StandardMin[\T\]\] extends CommutativeReduction[\T\]
-    getter toString() = "MinReduction"
-
-
-
-
-
-
+
+
+
+
+
-
-object MaxReduction[\T extends StandardMax[\T\]\] extends CommutativeReduction[\T\]
-    getter toString() = "MaxReduction"
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-(** AndReduction and OrReduction take advantage of natural zeroes for early exit. **)
@@ -2311 +2347 @@
-end
-
-
-
-
-
-
-
-
-
-
+
+
-
-object OrReduction
@@ -2330 +2359 @@
-end
-
-
-
-
-
-
-
-
-
-
+
+
-
-(** A reduction performing String concatenation **)
@@ -2357 +2379 @@
-object NewlineReduction extends AssociativeReduction[\String\]
-    getter toString() = "StringReduction"
-:String, b:String): String
+, b)
-end
-
-(** This operator performs string concatenation, first converting
-    its inputs (of type Any) to String if necessary. **)
-
-
+
+
+
-
-(** This operator performs string concatenation, first converting
-    its inputs (of type Any) to String if necessary, and separating
-    non-empty components by a space. **)
-
-
+
+
+
-
-(** This operator performs string concatenation with newline
-    separation, first converting its inputs (of type Any) to String if
-    necessary. **)
-
-
+
+
+
-
-(** A %MapReduceReduction% takes an associative binary function %j% on
@@ -2403 +2428 @@
-    g(MIOprReduction[\T,OP\](z), fn (x) => x)
-*)
-Any, g:(Reduction[\T\],T->Any) -> Any) : T
-g(
+T) : Comprehension[\T,T,Any,Any\]
+Comprehension[\T,T,Any,Any\](fn (x) => x, 
-
-(** Helpers for maps and cross products of generators.  These can be
@@ -2410 +2435 @@
-    outwards if we think that'd be useful), but let's get this much
-    working first. *)
-
-
+
+
+
-    getter g(): Generator[\E\]
-    getter f(): E -> F
@@ -2456 +2482 @@
-    getter toString() = "seq(" g0 ".map(f))"
-    seq(self): SimpleMappedSeqGenerator[\E,F\] = self
+end
+
+trait FilterGenerator[\E\] extends Generator[\E\]
+    getter g(): Generator[\E\]
+    getter p(): E -> Condition[\()\]
+    getter toString(): String = g() ".filter(p)"
+    generate[\R\](r:Reduction[\R\], m: E->R): R =
+        g().generate[\R\](r, fn(e:E):R => if (p())(e).holds() then m(e) else r.empty() end)
+    reduce(r: Reduction[\E\]): E =
+        g().generate[\E\](r, fn(e:E):E => if (p())(e).holds() then e else r.empty() end)
+    filter(p': E -> Condition[\E\]): SimpleFilterGenerator[\E\] =
+        SimpleFilterGenerator[\E\](g(), p() ANDCOND p')
+    seq(self) = SimpleSeqFilterGenerator[\E\](g(),p())
+end
+
+object SimpleFilterGenerator[\E\](g0:Generator[\E\], p0: E->Condition[\()\])
+        extends FilterGenerator[\E\]
+    getter g(): Generator[\E\]       = g0
+    getter p(): E -> Condition[\()\]  = p0
+end
+
+object SimpleSeqFilterGenerator[\E\](g0: SequentialGenerator[\E\], p0: E->Condition[\()\])
+        extends { FilterGenerator[\E\], SequentialGenerator[\E\] }
+    getter g(): Generator[\E\]       = g0
+    getter p(): E -> Condition[\()\]  = p0
+    getter toString() = "seq(" g0 ".filter(p))"
+    seq(self): SimpleSeqFilterGenerator[\E\] = self
-end
-

trunk/Library/List.fsi

@@ -115 +115 @@
-opr <|[\E\] xs: E... |>: List[\E\]
-(** List comprehensions: *)
- g: ( Reduction[\SomeList\], T->SomeList) -> SomeList |>: List[\T
+|>:Comprehension[\T,List[\T\],List[\T\],List[\T\]
-
-(** Convert generator into list (simpler type than comprehension above): *)
@@ -139 +139 @@
-(** Utility for cooking up covariant comprehensions of other
-    (non-covariant) types. **)
-\]( g: (Reduction[\SomeList\], T->SomeList) -> SomeList): List[\T
+,R\](unwrap:List[\T\]->R): Comprehension[\T,R,List[\T\],List[\T\]
-
-end

trunk/Library/List.fss

@@ -176 +176 @@
-(** Vararg factory for lists; provides aggregate list constants **)
-opr <|[\E\] xs: E... |>: List[\E\] = list(xs)
-
-
-
-
-
+
+
+
+
+
+
-
-(** Convert generator into list; can be used to desugar list

trunk/Library/Map.fss

@@ -158 +158 @@
-    mapping[\Key,Val\](xs)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-
-object SeqMapGenerator[\Key,Val\](o:Map[\Key,Val\])

trunk/Library/PureList.fss

@@ -80 +80 @@
-(** Vararg factory for lists; provides aggregate list constants **)
-opr <|[\E\] xs: E... |>: List[\E\] = list(xs)
- g: ( Reduction[\SomeList\], T->SomeList) -> SomeList|>: List[\T
-list(covariantComprehension[\T\](g
+|>: Comprehension[\T,List[\T\],SomeList,SomeList
+covariantComprehension[\T,List[\T\]\](fn x => list(x
-
-(** Convert generator into list; can be used to desugar list

trunk/Library/Set.fss

@@ -85 +85 @@
-    es.generate[\Set[\E\]\](Union[\E\],
-                                fn (e:E): Set[\E\] => singleton[\E\](e))
-
-
-
-
-
-
+
+
+
+
+
-
-object Union[\E extends StandardTotalOrder[\E\]\] extends CommutativeMonoidReduction[\Set[\E\]\]
@@ -98 +97 @@
-end
-
-
-
-
-
-
-
+
+
+
-
-object Intersection[\E extends StandardTotalOrder[\E\]\]

trunk/ProjectFortress/demos/wordcount.fss

@@ -71 +71 @@
-        a.union(fn(_,x,y)=>x+y, b)
-
-
-
-
-
-
+
+
+
+
-
-opr UNIONUNION(a:Map[\ZZ32,List[\String\]\], b:Map[\ZZ32, List[\String\]\]):Map[\ZZ32,List[\String\]\] =
-    a.union(fn(k,x,y) =>x.append(y),b)
-
-
-
-
-
-
+
+
-
-processFile(name:String):() = do

trunk/ProjectFortress/demos/zeno.fss

@@ -44 +44 @@
- **)
-
-2
+1
-
-(** Represents m / 2^n and 2 - (m / 2^n) **)

trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/OverloadedFunction.java

@@ -251 +251 @@
-            Overload o1 = new_overloads.get(i);
-            Fcn fn = o1.getFn();
-
-
-
-
-
+
-                FType ty = fn.type();
-
+if (ty != null) 
-            }
-

trunk/ProjectFortress/src/com/sun/fortress/interpreter/rewrite/Desugarer.java

@@ -1040 +1040 @@
-        int i = gens.size();
-        if (i==0) {
-Boolean guard
+Single generator as body, with no generator clauses.
-            body = new TightJuxt(span, false,
-
+
+
-        } else {
-            body = new TightJuxt(body.getSpan(), false,
@@ -1059 +1060 @@
-                          OpName op, Expr body, List<StaticArg> staticArgs) {
-        body = visitGenerators(span, gens, body);
-
+
+
+
+
-        // System.out.println("Desugared to "+res.toStringVerbose());
-        return (Expr)visitNode(res);

trunk/ProjectFortress/src/com/sun/fortress/nodes_util/ExprFactory.java

@@ -318 +318 @@
-    }
-
+    public static OpExpr makeOpExpr(Span span, OpName op, List<StaticArg> staticArgs) {
+        return new OpExpr(span, false, makeOpRef(op, staticArgs));
+    }
+
-    public static OpExpr makeOpExpr(Span span, OpName op, Expr arg,
-                                      List<StaticArg> staticArgs) {

trunk/ProjectFortress/src/com/sun/fortress/nodes_util/Span.java

@@ -123 +123 @@
-        if (file_names_differ || begin.getLine() != end.getLine()
-                || left_col != right_col) {
-Printer.tilde
+printer ? Printer.tilde : "-"
-            if (file_names_differ) {
-                if (printer) w.append("\"");

trunk/ProjectFortress/tests/HeapTest.fss

@@ -66 +66 @@
-object TestReduction extends AssociativeReduction[\(ZZ32,ZZ32,ZZ32)\]
-    getter toString(): String = "HeapTest.TestReduction"
+    simpleJoin(a:Any, b:Any): Any = fail("Bogus non-tuple data in TestReduction")
-    simpleJoin(a:(ZZ32,ZZ32,ZZ32), b:(ZZ32,ZZ32,ZZ32)):(ZZ32,ZZ32,ZZ32) = do
-        (mn_a,sz_a,mx_a) = a
@@ -83 +84 @@
-        Just[\(ZZ32,ZZ32,ZZ32)\](k,1,k)
-      end
-Maybe[\(ZZ32,ZZ32,ZZ32)\]
+AnyMaybe
-    assert(n,sz," size versus computed size")
-    if (sz > 0) then

trunk/ProjectFortress/tests/MapExprTest.fss

@@ -22 +22 @@
-
-opr { |->[\ K,V \] xs: (K,V)... }: Map[\K,V\] = Map[\K,V\]
-g: (Reduction[\Map[\K,V\]\], T -> Map[\K,V\]) -> Map[\K,V\] 
+
-
-run(args:String...):() = ()

trunk/ProjectFortress/tests/WordCountSmall.fss

@@ -26 +26 @@
-isDelimiter(c:Char):Boolean =   c IN <| ' ',  ',', '.', '?' |>
-
- 
+
-                         database:Map[\String,ZZ32\]):Map[\String,ZZ32\]= do
-    var result:Map[\String,ZZ32\] := mapping[\String,ZZ32\]()
-    occurs = database.member(word,0)
- 
+
-        result := database.update(word,occurs+1)
- 
+
-        result := database.add(word,1)
-    end
@@ -73 +73 @@
-opr UNIONSUM(a:Map[\String,ZZ32\], b:Map[\String,ZZ32\]):Map[\String,ZZ32\] = a.union(fn(k,x,y)=>x+y, b)
-
-
-
+
+
+
-
-
+
+
-
-g:(Reduction[\Map[\ZZ32,List[\String\]\]\], Map[\ZZ32,List[\String\]\]->Map[\ZZ32,List[\String\]\])->Map[\ZZ32,List[\String\]\]):Map[\ZZ32,List[\String
-mapping[\ZZ32,List[\String\]\](),g
+): BigReduction[\Map[\ZZ32, List[\String\]\],Map[\ZZ32, List[\String\]
+{[\ZZ32,List[\String\]\]}
-
-processFile(name:String):() = do
-    println("Processing file " name)
-    var rs:FileReadStream = FileReadStream(name)
+    rs.close()
-    database:Map[\String, ZZ32\] = BIG UNIONSUM [l<-rs.lines()] (getWords(l))
-    var invDatabase:Map[\ZZ32,List[\String\]\] = BIG UNIONUNION [(x,y) <-database] (makeInv(x,y))
- 
- 
+
+
-            (c:ZZ32,m:List[\String\]) = invDatabase.maximum().get()
-            invDatabase := invDatabase.deleteMaximum()
- 
- 
- 
+
+
+
-            NotFound => println("end")
-    end
-    rs.close()
-end
-
-
-run(args:String...)= do
-   
+
-end
-end

trunk/ProjectFortress/tests/simpleBig.fss

@@ -20 +20 @@
-export Executable
-
-\](g:(Reduction[\Number\],T->Number)->Number):Number
-g(SumReduction,
+ extends Number\](): Comprehension[\T,Number,Number,Number\]
+Comprehension[\T,Number,Number,Number\](fn x => x, SumReduction, 
-
-run(args:String...):() = do