Mercurial > repos > icfp2013
changeset 56:f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
| author | Mike Pavone <pavone@retrodev.com> |
|---|---|
| date | Sun, 11 Aug 2013 14:11:47 -0700 |
| parents | 85242b96adcc |
| children | 27ee5051b1ec |
| files | src/bv.tp src/driver.tp src/solver.tp |
| diffstat | 3 files changed, 140 insertions(+), 77 deletions(-) [+] |
line wrap: on
line diff
--- a/src/bv.tp Sun Aug 11 14:08:13 2013 -0700 +++ b/src/bv.tp Sun Aug 11 14:11:47 2013 -0700 @@ -62,6 +62,17 @@ _opFold <- 0x400 _opTfold <- 0x800 _maskRemoveFold <- 0x3FF + _opPlusMask <- 1 xor 0xFFF + _opAndMask <- 2 xor 0xFFF + _opOrMask <- 4 xor 0xFFF + _opXorMask <- 8 xor 0xFFF + _opNotMask <- 0x10 xor 0xFFF + _opShl1Mask <- 0x20 xor 0xFFF + _opShr1Mask <- 0x40 xor 0xFFF + _opShr4Mask <- 0x80 xor 0xFFF + _opShr16Mask <- 0x100 xor 0xFFF + _opIf0Mask <- 0x200 xor 0xFFF + _names <- dict linear _names set: "plus" _opPlus _names set: "and" _opAnd @@ -289,20 +300,20 @@ self } - //TODO: memoize this to improve runtime for large n allOfSize:inFold? <- :n :infold? { + memoAdjust <- 1 memo <- if: infold? = 2 { _memoFoldBody } else: { if: infold? = 1 && n > 4 { + memoAdjust <- 5 _memoFoldParam } else: { _memo } } - if: n - 1 < (memo length) { - print: "Memo hit: " . (string: n) . "\n" - memo get: (n - 1) + if: n - memoAdjust < (memo length) { + memo get: (n - memoAdjust) } else: { if: n = 1 { res <- #[one zero input] @@ -394,117 +405,155 @@ allOfSize: (n - 1) inFold?: 0 } - allOfSize:inFold?:withOps <- :n :infold? :ops { - if: n = 1 { - res <- #[one zero input] - if: infold? = 2 { - res append: acc - res append: val + allOfSize:inFold?:withOps:needOps <- :n :infold? :ops :needed { + if: n <= 7 { + unfiltered <- allOfSize: n inFold?: infold? + if: (needed) > 0 { + _filterTrees: unfiltered needed + } else: { + unfiltered } - res } else: { res <- #[] origops <- ops if: (ops and _opTfold) > 0 { ops <- ops and _maskRemoveFold - } - if: (ops and (_opNot or _opShl1 or _opShr1 or _opShr4 or _opShr16)) > 0 { - foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops) :idx exp { - if: (ops and _opNot) > 0 { + } else: { + if: (ops and _opNot) > 0 { + foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops needOps: (needed and _opNotMask)) :idx exp { res append: (opNot: exp) } - if: (ops and _opShl1) > 0 { + } + if: (ops and _opShl1) > 0 { + foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops needOps: (needed and _opShl1Mask)) :idx exp { res append: (shl1: exp) } - if: (ops and _opShr1) > 0 { + } + if: (ops and _opShr1) > 0 { + foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops needOps: (needed and _opShr1Mask)) :idx exp { res append: (shr1: exp) } - if: (ops and _opShr4) > 0 { + } + if: (ops and _opShr4) > 0 { + foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops needOps: (needed and _opShr4Mask)) :idx exp { res append: (shr4: exp) } - if: (ops and _opShr16) > 0 { + } + if: (ops and _opShr16) > 0 { + foreach: (allOfSize: n - 1 inFold?: infold? withOps: ops needOps: (needed and _opShr16Mask)) :idx exp { res append: (shr16: exp) } } - } - if: n > 2 { numLeft <- 1 argTotal <- n - 1 if: (ops and (_opAnd or _opOr or _opXor or _opPlus)) > 0 { while: { numLeft < argTotal } do: { numRight <- argTotal - numLeft - choicesRight <- (allOfSize: numRight inFold?: infold? withOps: ops) - foreach: (allOfSize: numLeft inFold?: infold? withOps: ops) :idx leftExp { - foreach: choicesRight :idx rightExp { - if: (ops and _opAnd) > 0 { - res append: (opAnd: leftExp rightExp) + choicesRight <- (allOfSize: numRight inFold?: infold? withOps: ops needOps: 0) + foreach: (allOfSize: numLeft inFold?: infold? withOps: ops needOps: 0) :idx leftExp { + if: (ops and _opAnd) > 0 { + foreach: choicesRight :idx rightExp { + newop <- (opAnd: leftExp rightExp) + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop + } } - if: (ops and _opOr) > 0 { - res append: (opOr: leftExp rightExp) + } + if: (ops and _opOr) > 0 { + foreach: choicesRight :idx rightExp { + newop <- (opOr: leftExp rightExp) + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop + } } - if: (ops and _opXor) > 0 { - res append: (opXor: leftExp rightExp) + } + if: (ops and _opXor) > 0 { + foreach: choicesRight :idx rightExp { + newop <- (opXor: leftExp rightExp) + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop + } } - if: (ops and _opPlus) > 0 { - res append: (plus: leftExp rightExp) + } + if: (ops and _opPlus) > 0 { + foreach: choicesRight :idx rightExp { + newop <- (plus: leftExp rightExp) + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop + } } } } numLeft <- numLeft + 1 } } - if: n > 3 { - numLeft <- 1 - limitLeft <- n - 2 - if: (ops and _opIf0) > 0 { - while: { numLeft < limitLeft } do: { - numMid <- 1 - limitMid <- n - (1 + numLeft) - while: { numMid < limitMid } do: { - numRight <- n - (1 + numLeft + numMid) - choicesRight <- (allOfSize: numRight inFold?: infold? withOps: ops) - choicesMid <- (allOfSize: numMid inFold?: infold? withOps: ops) - foreach: (allOfSize: numLeft inFold?: infold? withOps: ops ) :idx leftExp { - foreach: choicesMid :idx midExp { - foreach: choicesRight :idx rightExp { - res append: (if0: leftExp then: midExp else: rightExp) + numLeft <- 1 + limitLeft <- n - 2 + if: (ops and _opIf0) > 0 { + while: { numLeft < limitLeft } do: { + numMid <- 1 + limitMid <- n - (1 + numLeft) + while: { numMid < limitMid } do: { + numRight <- n - (1 + numLeft + numMid) + choicesRight <- (allOfSize: numRight inFold?: infold? withOps: ops needOps: 0) + choicesMid <- (allOfSize: numMid inFold?: infold? withOps: ops needOps: 0) + foreach: (allOfSize: numLeft inFold?: infold? withOps: ops needOps: 0) :idx leftExp { + foreach: choicesMid :idx midExp { + foreach: choicesRight :idx rightExp { + newop <- (if0: leftExp then: midExp else: rightExp) + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop } } } - numMid <- numMid + 1 } - numLeft <- numLeft + 1 + numMid <- numMid + 1 } + numLeft <- numLeft + 1 } - if: n > 4 && infold? = 0 && (origops and (_opFold or _opTfold)) > 0 { - numSeq <- 1 - limitSeq <- n - 3 - while: { numSeq < limitSeq } do: { - numFun <- 1 - limitFun <- n - (2 + numSeq) - while: { numFun < limitFun } do: { - numStart <- n - (2 + numSeq + numFun) - choicesStart <- (allOfSize: numStart inFold?: 1 withOps: ops) - choicesFun <- (allOfSize: numFun inFold?: 2 withOps: ops) - foreach: (allOfSize: numSeq inFold?: 1 withOps: ops) :idx seqExp { - foreach: choicesFun :idx funExp { - foreach: choicesStart :idx startExp { - if: (origops and _opFold) > 0 { - res append: (fold: seqExp with: funExp startingAt: startExp) - } else: { - mtf <- fold: seqExp with: funExp startingAt: startExp - if: (mtf isTfold?) { - res append: mtf - } - } + } + } + if: infold? = 0 && (origops and (_opFold or _opTfold)) > 0 { + numSeq <- 1 + limitSeq <- n - 3 + oldlen <- res length + while: { numSeq < limitSeq } do: { + numFun <- 1 + limitFun <- n - (2 + numSeq) + while: { numFun < limitFun } do: { + numStart <- n - (2 + numSeq + numFun) + choicesStart <- false + choicesToFold <- false + choicesFun <- false + if: (origops and _opTfold) > 0 { + choicesStart <- #[zero] + choicesToFold <- #[input] + choicesFun <- (allOfSize: numFun inFold?: 2 withOps: ops needOps: (needed and _maskRemoveFold)) + } else: { + choicesStart <- (allOfSize: numStart inFold?: 1 withOps: ops needOps: 0) + choicesToFold <- (allOfSize: numSeq inFold?: 1 withOps: ops needOps: 0) + choicesFun <- (allOfSize: numFun inFold?: 2 withOps: ops needOps: 0) + } + foreach: choicesToFold :idx seqExp { + foreach: choicesFun :idx funExp { + foreach: choicesStart :idx startExp { + if: (origops and _opFold) > 0 { + newop <- fold: seqExp with: funExp startingAt: startExp + if: needed = 0 || (((newop operators) and needed) xor needed) = 0 { + res append: newop + } + } else: { + mtf <- fold: seqExp with: funExp startingAt: startExp + if: (mtf isTfold?) { + res append: mtf } } } - numFun <- numFun + 1 } - numSeq <- numSeq + 1 } + numFun <- numFun + 1 } + numSeq <- numSeq + 1 } } res @@ -515,14 +564,17 @@ ops <- strops fold: 0 with: :acc el { acc or (_names get: el withDefault: 0) } - allOfSize: size inFold?: 0 withOps: ops + allOfSize: (size - 1) inFold?: 0 withOps: ops needOps: ops } filterTrees <- :trees strops { - filtered <- #[] ops <- strops fold: 0 with: :acc el { acc or (_names get: el withDefault: 0) } + _filterTrees: trees ops + } + _filterTrees <- :trees ops { + filtered <- #[] if: (ops and _opTfold) > 0 { foreach: trees :idx tree { if: (tree isTfold?) {
--- a/src/driver.tp Sun Aug 11 14:08:13 2013 -0700 +++ b/src/driver.tp Sun Aug 11 14:11:47 2013 -0700 @@ -36,7 +36,7 @@ probtrees <- prog allOfSize: numops withOps: (el operators) print: "Generated " . (string: (probtrees length)) . " programs\n" probtrees <- prog filterTrees: probtrees (el operators) - print: "Running classifier " . (string: (probtrees length)) . " programs\n" + print: "Running classifier on " . (string: (probtrees length)) . " programs\n" info <- solver classify: prog probtrees nt solver solve: (el id) withAuth: authKey andInfo: info andProg: prog }
--- a/src/solver.tp Sun Aug 11 14:08:13 2013 -0700 +++ b/src/solver.tp Sun Aug 11 14:11:47 2013 -0700 @@ -218,7 +218,6 @@ } prog <- bv program if: size >= 2 { - trees <- (prog allOfSize: size) numTests <- 0 if: (args length) > 2 { numTests <- int32: (args get: 2) @@ -226,10 +225,22 @@ if: numTests <= 0 { numTests <- 16 } + trees <- #[] + if: (args length) > 3 { ops <- (args get: 3) splitOn: "," - trees <- prog filterTrees: trees ops + if: size < 10 { + trees <- prog filterTrees: (prog allOfSize: size) ops + } else: { + print: "Generating programs for operators: " . (ops fold: "" with: :acc el { acc . el }) . "\n" + trees <- prog allOfSize: size withOps: ops + print: "Generated " . (string: (trees length)) . " programs\n" + trees <- prog filterTrees: trees ops + } + } else: { + trees <- (prog allOfSize: size) } + print: "Running classifier on " . (string: (trees length)) . " programs\n" info <- classify: prog trees numTests if: (args length) > 5 { progId <- (args get: 4)