Text/ParserCombinators/Parsec/examples/tiger/matrix.tig

   1 let
   2
   3 type vec    = array of int
   4 type vector = {dim : int, d : vec}
   5
   6 type mat    = array of vector
   7 type matrix = {x : int, y : int, d : mat}
   8
   9 function vectorCreate(n : int) : vector =
  10   vector{dim = n, d = vec[n] of 0}
  11
  12 function vectorLiftedAdd(X : vector, Y : vector) : vector =
  13   let var tmp : vector := vectorCreate(X.dim)
  14    in for i := 0 to X.dim do
  15         tmp.d[i] := X.d[i] + Y.d[i];
  16       tmp
  17   end
  18
  19 function vectorLiftedMul(X : vector, Y : vector) : vector =
  20   let var tmp : vector := vectorCreate(X.dim)
  21    in for i := 0 to X.dim do
  22         tmp.d[i] := X.d[i] * Y.d[i];
  23       tmp
  24   end
  25
  26 function vectorInProduct(X : vector, Y : vector) : int =
  27   let var tmp : int := 0
  28    in for i := 0 to X.dim do
  29         tmp := tmp + X.d[i] * Y.d[i];
  30       tmp
  31   end
  32
  33
  34
  35 function matrixCreate(n : int, m : int) : matrix =
  36   let var tmp := matrix{x = n, y = m, d = mat[n] of nil}
  37    in for i := 0 to n do
  38         tmp.d[i] := vectorCreate(m);
  39       tmp
  40   end
  41
  42 function matrixRow(A : matrix, i : int) : vector =
  43   A.d[i]
  44
  45 function matrixCol(A : matrix, j : int) : vector =
  46   let var tmp := vectorCreate(A.y)
  47    in for i := 0 to A.y do
  48         tmp.d[i] := A.d[i].d[j];
  49       tmp
  50   end
  51
  52 function matrixTranspose(A : matrix) : matrix =
  53   let var tmp := matrixCreate(A.y, A.x)
  54    in for i := 0 to A.x do
  55         for j := 0 to A.y do
  56           tmp.d[j].d[i] := A.d[i].d[j];
  57       tmp
  58   end
  59
  60 function matrixLiftedAdd(A : matrix, B : matrix) : matrix =
  61   let var tmp := matrixCreate(A.x, A.y)
  62    in if A.x <> B.x | A.y <> B.y then exit(1)
  63       else for i := 0 to A.x do
  64              for j := 0 to A.y do
  65                tmp.d[i].d[j] := A.d[i].d[j] + B.d[i].d[j];
  66       tmp
  67   end
  68
  69 function matrixLiftedMul(A : matrix, B : matrix) : matrix =
  70   let var tmp := matrixCreate(A.x, A.y)
  71    in if A.x <> B.x | A.y <> B.y then exit(1)
  72       else for i := 0 to A.x do
  73              for j := 0 to A.y do
  74                tmp.d[i].d[j] := A.d[i].d[j] * B.d[i].d[j];
  75       tmp
  76   end
  77
  78 function matrixMul(A : matrix, B : matrix) : matrix =
  79   let var tmp := matrixCreate(A.x, B.y)
  80    in if A.y <> B.x then exit(1)
  81       else for i := 0 to A.x do
  82              for j := 0 to B.y do
  83                tmp.d[i].d[j] := vectorInProduct(matrixRow(A,i), matrixCol(B,j));
  84       tmp
  85   end
  86
  87 function createDiagMat(X : vector) : matrix =
  88   let var tmp := matrixCreate(X.dim, X.dim)
  89    in for i := 0 to X.dim do
  90         tmp.d[i].d[i] := X.d[i];
  91       tmp
  92   end
  93
  94 /* matrixMul(A, B) where B is a diagonal matrix, which can be represented
  95  by a vector
  96 */
  97
  98 function matrixMulDiag(A : matrix, X : vector) : matrix =
  99   let var tmp := matrixCreate(A.x, A.y)
 100    in if A.y <> X.dim then exit(1)
 101       else for i := 0 to A.x do
 102              for j := 0 to A.y do
 103                tmp.d[i].d[j] := A.d[i].d[j] * X.d[j];
 104       tmp
 105   end
 106
 107 /* Challenge: matrixMul(A, createDiagMat(X)) == matrixMulDiag(A, X)
 108 i.e., derive the rhs from the lhs by specialization
 109
 110 What are the laws involved?
 111
 112 Challenge: matrixMul(A, create5shapeMatrix(a,b,c,d,e)) == efficient algorithm
 113
 114 */
 115
 116 in
 117
 118   /* matrixLiftedAdd(matrixCreate(8),matrixCreate(8)) */
 119
 120   matrixMul(A, createDiagMat(X))
 121
 122 end