Multiple Comparisons

[uninhm]

Implement multiple comparisons like math

Examples: 1 < x and x < 3 will be 1 < x < 3 a == b and b == 2 will be a == b == 2 1 < a and a != 2 will be 1 < a != 2

More examples: 1 <= a < b, c <= 12 a < b < c, d < 24

[Araq]

What are the typing rules that make this work? < produces a bool.

[juancarlospaco]

This can be a macro on sugar.

[zah]

This is a parsing rule, not a typing rule. It cannot be done with a macro, but it does exist in some languages (e.g. CoffeeScript).

[alehander92]

also in python

On Fri, Jul 17, 2020 at 7:37 PM zah notifications@github.com wrote:

This is a parsing rule, not a typing rule. It cannot be done with a macro, but it does exist in some languages (e.g. CoffeeScript).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/nim-lang/RFCs/issues/242#issuecomment-660210860, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAGKZ6ZODU7YFRGUZ2Y7GBTR4B427ANCNFSM4O5KEE3Q .

[Vindaar]

This is a parsing rule, not a typing rule. It cannot be done with a macro, but it does exist in some languages (e.g. CoffeeScript).

I know what you're trying to say, but your wording is easy to be misunderstood. With a tiny bit of verbosity (well, if done via a macro we have to call that macro somehow), it can be done quite nicely:

import macros

proc processBool(n: NimNode): NimNode =
  echo n.treeRepr
  result = copyNimTree n
  expectKind(n, nnkInfix)
  var id: NimNode
  case n[1].kind
  of nnkInfix:
    id = n[1][2]
    result[1] = id
    result = nnkInfix.newTree(ident("and"), result)
    result.add n[1]
    result = newStmtList(result)
    echo result.treerepr
  else: discard

macro `{}`(x, y: untyped): untyped =
  if x.strVal == "eq":
    result = processBool(y)

let x = 6
let a = 2
let b = 2
echo eq{ 4 < x <= 10 }
echo eq{ 8 < x < 10 }
echo eq{ a == b == 2 }
echo eq{ 1 < a != 2 }

edit: the above is obviously very brittle in this implementation.

[juancarlospaco]

I think that @Vindaar solution is very good solution. :+1:

[uninhm]

@Vindaar but that is only when comparing 3

eq{1 < x < 3 < y} doesn't work

[ghost]

@Vindaar but that is only when comparing 3

eq{1 < x < 3 < y} doesn't work

Well, as they said it's a very naive implementation just to show a PoC

[Vindaar]

@unihernandez22 ok, here's a slightly improved version, which recurses and conserves the desired evaluation order (left to right):

import macros

proc processBool(n: NimNode): NimNode =
  result = n
  case n.kind
  of nnkInfix:
    if n[1].kind == nnkInfix:
      # process first infix arg
      let a = processBool(n[1])
      var tmp = nnkInfix.newTree(ident("and"), a)
      # reorder the resulting infix (otherwise evaluated in wrong order)
      result = copyNimTree n
      result[1] = n[1][2]
      tmp.add result
      result = newStmtList(tmp)
    else: discard
  else: discard

proc flatten(n: NimNode): NimNode =
  ## since we generate nested stmt lists, flatten them
  result = copyNimTree n
  case n.kind
  of nnkStmtList: result[0] = flatten result[0]
  of nnkInfix:
    if n[1].kind == nnkStmtList:
      result[1] = flatten result[1][0]
  else: discard

macro `{}`(x, y: untyped): untyped =
  if x.strVal == "eq":
    expectKind(y, nnkInfix)
    result = processBool(y).flatten
    echo result.treeRepr
    echo result.repr

let x = 6
let a = 2
let b = 2
echo eq{ 4 < x }
echo eq{ 4 < x <= 10 }
echo eq{ 4 < a < x <= 10 }
echo eq{ 4 < a < x < b <= 10 }
echo eq{ 8 < x < 10 }
echo eq{ a == b == 2 }
echo eq{ 1 < a != 2 }

This still doesn't really do any checks though, so you can probably break it easily.

[solo989]

If you add

type
  EqObject = object
const
  eq = EqObject()

then the header for {} can be

macro `{}`(x : EqObject, y: untyped): untyped

[juancarlospaco]

is nice to see the evolution of the idea, with some Documentation and Examples it worth a Pull Request somewhere. :sweat_smile: (I know it has limitations, like everything, but documenting them, is more than enough for users).

[juancarlospaco]

Theres https://github.com/Yardanico/nimpylib that has some macros that resembles Python-like stuff, maybe the macro can live there instead (given thats too Python-like for stdlib) if @Yardanico agrees and @Vindaar Pull Request it. :thinking:

[mratsim]

I have a parser that properly handles that for expressing contraint solving:

https://github.com/mratsim/hydra/blob/89fd253/tests/test_sets.nim#L26-L40

suite "Creating a Presburger set of constraints":
  test "Smoke test - with environment parameters":
    var x = initRawSet()

    x.incl:
      [T,N] -> { S[t,i] : 1<=t-i<T}

    echo "Raw set: "
    echo x

  test "Smoke test - without environment parameters":
    var x = initRawSet()

    x.incl:
      { S[i,j] : 1<=i<=2 and 1<=j<=3 }

    echo "Raw set: "
    echo x

This is similar to Vindaar eq{} except it's incl{} as it's for representing set of constraints.

The implementation is significantly more involved but should handle the corner cases and is based on bubbling up the RHS: https://github.com/mratsim/hydra/blob/89fd253/hydra/ilp/constraints.nim#L36-L155

proc walkSetExpr(rawSet, node: NimNode, coef: BiggestInt, constraint: NimNode, stmts: var NimNode): NimNode =
  ## Walk the expression
  ## returns the RHS of comparison
  ## to bubble it up for nested comparisons

  node.expectKind({nnkIdent, nnkIntLit, nnkInfix})
  case node.kind:
  of nnkIdent:
    # Find the term in the space
    let strId = $node
    stmts.add quote do:
      let term = `rawSet`.space.idents[`strId`]
      `constraint`.terms.add term
    stmts.add quote do:
      `constraint`.coefs.add `coef`
    return node
  of nnkIntLit:
    let val = coef * node.intVal
    stmts.add quote do:
      `constraint`.constant += `val`
    return node
  of nnkInfix:
    if node[0].eqIdent"+":
      discard walkSetExpr(rawSet, node[1], coef, constraint, stmts)
      discard walkSetExpr(rawSet, node[2], coef, constraint, stmts)
      return node
    elif node[0].eqIdent"-":
      if node.len == 2: # Unary
        discard walkSetExpr(rawSet, node[1], -coef, constraint, stmts)
      elif node.len == 3: # Binary
        discard walkSetExpr(rawSet, node[1], coef, constraint, stmts)
        discard walkSetExpr(rawSet, node[2], -coef, constraint, stmts)
      else:
        error"Unreachable"
      return node
    elif node[0].eqIdent"*":
      if node[1].kind == nnkIntLit:
        discard walkSetExpr(rawSet, node[2], coef * node[1].intVal, constraint, stmts)
      elif node[2].kind == nnkIntLit:
        discard walkSetExpr(rawSet, node[1], coef * node[2].intVal, constraint, stmts)
      else:
        error "[Non-affine constraint error] One of the multiplication term must be a integer constant."
      return node
    elif node[0].eqIdent">=":
      # Canonical form is "expr >= 0"
      # left hand-side is as is
      # right hand-side is negated
      # a >= b  <=> a - b >= 0
      let subconstraint = genSym(nskVar, "constraintGE_")
      stmts.add quote do:
        var `subconstraint` = Constraint(eqKind: ckGEZero)

      let lhs = walkSetExpr(rawSet, node[1], 1, subconstraint, stmts)
      let rhs = walkSetExpr(rawSet, node[2], -1, subconstraint, stmts)

      # Nested comparison 0 <= i < N
      # Solve 0 <= i then i < N
      if lhs != node[1]:
        discard walkSetExpr(rawSet, lhs, 1, subconstraint, stmts)

      stmts.add quote do:
        `rawSet`.constraints.add `subconstraint`
      return rhs
    elif node[0].eqIdent">":
      # a > 0   <=>   a - 1 >= 0
      let subconstraint = genSym(nskVar, "constraintGR_")
      stmts.add quote do:
        var `subconstraint` = Constraint(eqKind: ckGEZero, constant: -1)

      let lhs = walkSetExpr(rawSet, node[1], 1, subconstraint, stmts)
      let rhs = walkSetExpr(rawSet, node[2], -1, subconstraint, stmts)

      if lhs != node[1]:
        discard walkSetExpr(rawSet, lhs, 1, subconstraint, stmts)

      stmts.add quote do:
        `rawSet`.constraints.add `subconstraint`
      return rhs
    elif node[0].eqIdent"<=":
      # a <= 10   <=>   0 <= 10 - a  <=>  10 - a >= 0
      let subconstraint = genSym(nskVar, "constraintLE_")
      stmts.add quote do:
        var `subconstraint` = Constraint(eqKind: ckGEZero)

      let lhs = walkSetExpr(rawSet, node[1], -1, subconstraint, stmts)
      let rhs = walkSetExpr(rawSet, node[2], 1, subconstraint, stmts)

      if lhs != node[1]:
        discard walkSetExpr(rawSet, lhs, -1, subconstraint, stmts)

      stmts.add quote do:
        `rawSet`.constraints.add `subconstraint`
      return rhs
    elif node[0].eqIdent"<":
      # a < 10   <=>   0 < 10 - a  <=>  10 - a > 0 <=>  10 - a - 1 >= 0
      let subconstraint = genSym(nskVar, "constraintLR_")
      stmts.add quote do:
        var `subconstraint` = Constraint(eqKind: ckGEZero, constant: -1)

      let lhs = walkSetExpr(rawSet, node[1], -1, subconstraint, stmts)
      let rhs = walkSetExpr(rawSet, node[2], 1, subconstraint, stmts)

      if lhs != node[1]:
        discard walkSetExpr(rawSet, lhs, -1, subconstraint, stmts)

      stmts.add quote do:
        `rawSet`.constraints.add `subconstraint`
      return rhs
    elif node[0].eqIdent"and":
      discard walkSetExpr(rawSet, node[1], 1, NimNode(), stmts)
      discard walkSetExpr(rawSet, node[2], 1, NimNode(), stmts)
    elif node[0].eqIdent"or":
      error "[\"or\" operator error] Expression requires a disjoint set or map"
    else:
      error "Unsupported infix operator: " & $node[0]
  else:
    error "Unreachable"

proc parseSetConstraints*(rawSet, expression: NimNode, stmts: var NimNode) =
  discard walkSetExpr(rawSet, expression, 1, NimNode(), stmts)

[Araq]

-6 votes vs +4 votes, sorry, rejected.