nimforum mirror - Help with metaprogramming

keks84 (orginal) [2022-01-02T18:08:00+01:00] view original

Hi,

I am considering Nim as programming language for its metaprogramming capabilities. As a test case for code generation, I would like to convert matrix expressions like A[i,j] to Avec[3], given` i = 1`,` j = 2`.

In Matlab this could be done using string manipulations, in Julia on the AST using the Expr type. The expressions then arebe manipulated like nested structs, deleting, adding or modifying elements.

Some helpful conversion in Julia include:


A = rand(2,2)
i = 1, j = 2
e = :(A[i, j]) # :(A[i, j])     quoting an expression -> Expr
dump(e)        #                Expr -> AST (for humans)
#=
Expr
    head: Symbol ref
    args: Array{Any}((3,))
        1: Symbol A
        2: Symbol i
        3: Symbol j
=#
symbs = (e.head, e.args...) # (:ref, :A, :i, :j)   Expr -> (symbols...)
Expr(:ref, :A, :i, :j)      # :(A[i, j])           (symbols...) -> Expr
string(:(A[i, j]))          # "A[i, j]"            Expr   -> String
Meta.parse("A[i, j]")       # :(A[i, j])           String -> Expr
eval(:(A[i, j]))            # a random number

I understand that Nim is a bit more verbose here. What is the best approach?

planetis (orginal) [2022-01-02T20:00:42+01:00] view original

I don't think a macro is necessary in your case, a proc can work just fine:

proc `[]`*[T](m: Matrix[T], i, j: int): T {.inline.} =
  result = m.data[i * m.n + j]

keks84 (orginal) [2022-01-02T20:48:58+01:00] view original

Thanks for replying. I am an absolute beginner in Nim, so please bear with me. Looks like an ordinary numerical function, where is the code generation?

As use case, an algorithm for x=Ab (like gaussian elimination) and sparsity pattern for A and b, is converted to an array of simple expressions acting on a vector Avec. Thus, avoiding zero-ops. The array of expressions is evaluated many times with different values for Avec and b, hence amortizing the time for generation.

SolitudeSF (orginal) [2022-01-02T22:03:39+01:00] view original

Huh?

keks84 (orginal) [2022-01-02T23:32:29+01:00] view original

Sample generated code from "symbolically" running the for-loops using https://en.wikipedia.org/wiki/LU_decomposition for x = A\b

// loading A

A[1] = gn_C1 + 1/RC1;

A[2] = - gn_C1 - 1/RC1; A[3] = -1; A[4] = - gn_C1 - 1/RC1; A[5] = gn_C1 + gn_C2n + 1/RC1 + 1/RC2N + 1/Rshort_antp_antn; A[6] = -1/Rshort_antp_antn; A[7] = - gn_C2n - 1/RC2N; A[8] = -1/Rshort_antp_antn; A[9] = gn_C2p + 1/RC2P + 1/Rshort_antp_antn; A[10] = - gn_C2p - 1/RC2P; A[11] = 1; A[12] = 1/Rnormp; A[13] = -1/Rnormp; A[14] = 1; A[15] = 1/Rnormn; A[16] = -1/Rnormn; A[17] = 1; A[18] = -1/Rnormp; A[19] = 1/RantP + 1/Rnormp + 1/Rshort; A[20] = -1/Rshort; A[21] = -1/RantP; A[22] = -1/Rnormn; A[23] = -1/Rshort; A[24] = 1/RantN + 1/Rnormn + 1/Rshort; A[25] = -1/RantN; A[26] = - gn_C2p - 1/RC2P; A[27] = -1/RantP; A[28] = gn_C2p + 1/RC2P + 1/RantP; A[29] = - gn_C2n - 1/RC2N; A[30] = -1/RantN; A[31] = gn_C2n + 1/RC2N + 1/RantN; A[32] = -1; A[33] = 1; A[34] = -rt_Lant; A[35] = 1; A[36] = 1;

// LU-factorization (in-place)

A[1] = -A[1]; A[3] = A[3] - A[1]*A[34]; A[37] = -A[1]; A[4] = -A[4]; A[38] = -A[4]*A[34]; A[6] = A[6] - A[4]; A[23] = A[23]/A[19]; A[24] = A[24] - A[23]*A[20]; A[39] = -A[23]*A[21]; A[27] = A[27]/A[19]; A[40] = -A[27]*A[20]; A[28] = A[28] - A[27]*A[21]; A[40] = A[40]/A[24]; A[28] = A[28] - A[40]*A[39]; A[41] = -A[40]*A[25]; A[30] = A[30]/A[24]; A[42] = -A[30]*A[39]; A[31] = A[31] - A[30]*A[25]; A[42] = A[42]/A[28]; A[31] = A[31] - A[42]*A[41]; A[43] = -A[42]*A[26]; A[10] = A[10]/A[28]; A[44] = -A[10]*A[41]; A[9] = A[9] - A[10]*A[26]; A[7] = A[7]/A[31]; A[5] = A[5] - A[7]*A[29]; A[6] = A[6] - A[7]*A[43]; A[44] = A[44]/A[31]; A[8] = A[8] - A[44]*A[29]; A[9] = A[9] - A[44]*A[43]; A[5] = A[5] - A[38]*A[8]; A[6] = A[6] - A[38]*A[9]; A[2] = A[2] - A[3]*A[8]; A[37] = A[37] - A[3]*A[9]; A[2] = A[2]/A[5]; A[37] = A[37] - A[2]*A[6];

// loading b (in-place b->x): x[12] = 0; x[11] = 0; x[5] = VNin; x[4] = VPin; x[1] = vt_Lant; x[6] = 0; x[7] = 0; x[8] = in_C2p; x[9] = in_C2n; x[10] = -in_C2p; x[2] = in_C1 - in_C2n; x[3] = -in_C1;

// forward/backward backsubstitution

x[6] = x[6] - A[18]*x[4]; x[7] = x[7] - A[22]*x[5]; x[7] = x[7] - A[23]*x[6]; x[8] = x[8] - A[27]*x[6]; x[8] = x[8] - A[40]*x[7]; x[9] = x[9] - A[30]*x[7]; x[9] = x[9] - A[42]*x[8]; x[10] = x[10] - A[10]*x[8]; x[10] = x[10] - A[44]*x[9]; x[2] = x[2] - A[4]*x[1]; x[2] = x[2] - A[7]*x[9]; x[2] = x[2] - A[38]*x[10]; x[3] = x[3] - A[1]*x[1]; x[3] = x[3] - A[3]*x[10]; x[3] = x[3] - A[2]*x[2]; x[3] = x[3]/A[37]; x[2] = x[2] - A[6]*x[3]; x[2] = x[2]/A[5]; x[10] = x[10] - A[8]*x[2]; x[10] = x[10] - A[9]*x[3]; x[9] = x[9] - A[29]*x[2]; x[9] = x[9] - A[43]*x[3]; x[9] = x[9]/A[31]; x[8] = x[8] - A[41]*x[9]; x[8] = x[8] - A[26]*x[3]; x[8] = x[8]/A[28]; x[7] = x[7] - A[39]*x[8]; x[7] = x[7] - A[25]*x[9]; x[7] = x[7]/A[24]; x[6] = x[6] - A[20]*x[7]; x[6] = x[6] - A[21]*x[8]; x[6] = x[6]/A[19]; x[1] = x[1] - A[34]*x[10]; x[1] = x[1] - x[3]; x[1] = -x[1]; x[11] = x[11] - A[12]*x[4]; x[11] = x[11] - A[13]*x[6]; x[12] = x[12] - A[15]*x[5]; x[12] = x[12] - A[16]*x[7];

DeletedUser (orginal) [2022-01-03T10:34:14+01:00] view original

From what I understand you are asking for the same thing as the code given does. This might be wrong though. The point of the given code is that in Nim, a[b, c] is a valid expression that parses to a call to a routine named [] with the arguments a, b, c. Here is how the given code is used in case it is what you're asking for:

type Matrix[T] = object
  rows: int
  data: seq[T]

proc `[]`*[T](m: Matrix[T], i, j: int): T {.inline.} =
  return m.data[i * m.rows + j]

let matrix = Matrix[int](rows: 2, data: @[
  1, 2,
  3, 4])

assert matrix[0, 0] == 1
assert matrix[0, 1] == 2
assert matrix[1, 0] == 3

If you want AST substitution at compile time instead of an inline proc (which is not always a good idea), you can use template or macro. template s are analogous to quote macros in other languages while macro s are like regular procs that generate AST.

template `[]`*[T](m: Matrix[T], i, j: int): T =
  m.data[i * m.rows + j]

# macro version

import macros

macro `[]`*[T](m: Matrix[T], i, j: int): T =
  # quote version
  result = quote do:
    `m`.data[`i` * `m`.rows + `j`]
  # procedural version
  result = newTree(nnkBracketExpr,
    newDotExpr(m, ident("data")),
    infix(
      infix(i, "*", newDotExpr(m, ident("rows"))),
      "+",
      j
    )
  )

planetis (orginal) [2022-01-03T12:38:55+01:00] view original

This is a very nice use case, I made an example for you

import std/macros

type
  Matrix[M, N: static[int]] = array[M * N, float32]

macro transposeImpl(M, N: static[int]; x, res: typed): untyped =
  result = newNimNode(nnkStmtList)
  for n in 0 ..< N * M:
    let i = n div N
    let j = n mod N
    result.add nnkAsgn.newTree(nnkBracketExpr.newTree(res, newLit(n)), nnkBracketExpr.newTree(x, newLit(j * M + i)))
  echo result.repr

proc transpose*[M, N: static[int]](x: Matrix[M, N]): Matrix[N, M] {.inline.} =
  transposeImpl(M, N, x, result)

#proc transpose*[M, N: static[int]](x: Matrix[M, N]): Matrix[N, M] {.inline.} =
  #for n in 0 ..< N * M:
    #let i = n div N
    #let j = n mod N
    #result[n] = x[j * M + i]

when isMainModule:
  let
    a: Matrix[2, 3] = [1'f32, 2, 3, 4, 5, 6]
    b = transpose(a)
  echo b

As you can see it generates the following code:

result[0] = x[0]
result[1] = x[2]
result[2] = x[4]
result[3] = x[1]
result[4] = x[3]
result[5] = x[5]

planetis (orginal) [2022-01-03T12:48:13+01:00] view original

with fusion astdsl, it becomes a little simpler to write (not by much, for this example though):

import fusion/astdsl

macro transposeImpl(M, N: static[int]; x, res: typed): untyped =
  result = buildAst(stmtList):
    #let typeSym = getTypeInst(res)
    #let typeNode = getTypeImpl(typeSym)
    #expectKind(typeNode[1], nnkInfix)
    for i in 0 ..< M:
      for j in 0 ..< N:
        asgn(bracketExpr(res, newLit(i * N + j)),
             bracketExpr(x, newLit(j * M + i)))
  echo result.repr

keks84 (orginal) [2022-01-03T13:29:39+01:00] view original

A big THANK YOU to all of you guys!

Your replies give a lot of things to consider: quote and procedural version, even a dsl package.

Well worth to have a closer look at Nim.

Mirror of forum.nim-lang.org

8762 :: Help with metaprogramming