README
¶
About
Package shapes provides the algebra and machinery for dealing with the metainformation of shapes of a tensor.
Why a shape package?
The shape package defines a syntax and semantics that describes shapes of values.
The goal is:
- to describe the notion of shape;
- to implement various automation to work with shapes (example a a tool that verify if shapes of different inputs are compatible to be used with one operator)
What is a Shape?
A shape is a piece of meta-information that tells you something about a tensor.
A rank-2 tensor is also commonly known as a matrix (mathematicians and physicists, please bear with the inaccuracies and informalities).
Example
Let's consider the following matrix:
⎡1 2 3⎤
⎣4 5 6⎦
We can describe this matrix by saying "it's a matrix with 2 rows and 3 columns". We can write this as (2, 3).
(2, 3) is the shape of the matrix.
This is a very convenient way of describing N-dimensiional tensors. We don't have to give the dimensions names like "layer", "row" or "column". We would rapidly run out of names! Instead, we just index them by their number. So in a 3 dimensional shape, instead of saying "layer", we say "dimension 0". In a 2 dimensional shape, "row" would be "dimension 0".
Components of a Shape
Given a shape, let's explore the components of the shape:
+--+--+--------- size
v v v
(2, 3, 4) <------ shape
^̄ ^̄ ^̄
+--+--+--------- dimension/axis
Each "slot" in a shape is called a dimension/axis. The number of dimensions in a shape is called a rank (though confusingly enough, in the Gorgonia family of libraries, it's called .Dims()). There are 3 slots in the example, so it's a 3 dimensional shape. Each number in a slot is called the size of the dimension. When refering to them by their number, the preferred term is to use "axis". So, axis 1 has a size of 3, therefore, the first dimension is of size 3.
To use the traditional named dimensions - recall in this instance, that dimension 1 is "rows" - We say there are 3 rows.
Shape Expr: Syntax
The primary data structure that the package provides is the shape expression. A shape expression is given by the following BNF
<shape> ::= <unit>| "("<integer>",)" | "("<integer>","<shape>")" |
"("<shape>","<integer>")" | "("<variable>",)" |
<binaryOperationExpression> | <nameOfT>
<integer> ::= <digit> [ <integer> ]
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<unit> ::= "()"
<variable> ::= ...
<binaryOperationExpression> ::= "("<variable> <binop> <integer>",)" |
"("<variable> <binop> <variable>",) |
"("<integer> <binop> <variable>",)"
<binop> ::= + | *
<expression> ::= <shape> | I n <expression> | D <expression |
K <expression> | Σ <expression> | Π <expression> |
<variable> | <expression → <expression> |
(<expression> → <expression>) @ <expression> // TODO
T ::= (I n E,) | (D E,) | (Σ E,) | (Π E,) // TODO
A compact BNF
The original design for the language of shapes was written in a compact BNF. This was expanded by Olivier Wulveryck into something that traditional computer scientists are more familiar with.
Here, the original compact BNF is preserved.
E ::= S | I n E | D E | K E | Σ E | Π E | a | E -> E | (E -> E) @ E
S ::= () | (n,) | (n, S) | (S, n) | (a,) | B | T
T ::= (I n E,) | (D E,) | (Σ E,) | (Π E,)
B ::= (a O n,) | (a O b,) | (n O a,)
O ::= + | ×
n,m ::= ℕ
a,b ::= variables
The BNF might be brief, but it is dense, so let's break it down.
Primitive Shape Construction
<shape> ::= <unit>| "("<integer>",)" | "("<integer>","<shape>")" |
"("<shape>","<integer>")" | "("<variable>",)" |
<binaryOperationExpr> | <nameOfT>
What this snippet says is: a shape (<shape>) is one of: the four possible definitions of a shape:
<unit>- This is the shape of scalar values.()is pronounced "unit"."("<integer>",)"-<integer>is any positive number. Example of a shape:(10,)."("<integer>","<shape>")"- an<interer>folowwed by another<shape>. Example:(8, (10,))."("<shape>","<integer>")"- a<shape>followed by another<integer>. Example:((8, (10,)), 20).
From the snippet, we have generated 4 examples of shapes: (), (10,), (8, (10,)) and ((8, (10,)), 20). This isn't how we normally write shapes. We would normally write them as (10,), (8, 10) and (8, 10, 20). So what's the difference?
In fact, the following are equivalent;
(8, (10,))=(8, 10)((8, (10,)), 20)=((8, 10), 20)=(8, (10, 20))=(8, 10, 20)
What this says is that the primitive shape construction is associative. This is useful as we can now omit the additional parentheses.
On <unit>
The unit () is particularly interesting. In a while we'll see why it's called a "unit".
For now, given the associativity rules, what would (10, ()) be equivalent to? One possible answer is (10, ) - afterall, we're just removing the internal parentheses. Another possible answer is (10, 1).
TODO write more.
Introducing Variables
Now, let us focus, once again on line 2 of the BNF, but on the latter parts:
<shape> ::= ... | (<variable>,) | ...
What this says is that you can create a <shape> using a variable. I'll use x and y for real variables.
Example: (x,) is a shape. Combining this rule with the rules from above, we can see that (x, y) is also a valid shape. So is (10, x) or (x, 10)
To recap using the examples we have seen so far, these are exammples of valid shapes:
(x,)(x, 10)(10, x)(10, 20, x)(10, x, 20)
Introducing Binary Operations
In the following snippet (still on line 2 of the BNF), this is introduced:
<shape> ::= ... | <binaryOperationExpression> | ...
And <binaryOperationExpression> is defined in the following line as:
<binaryOperationExpr> ::= "("<variable> <binop> <integer>",)" |
"("<variable> <binop> <variable>",) |
"("<integer> <binop> <variable>",)"
What this says is any valid <binaryOperationExpr> is also a valid <shape>.
<binop> is defined as:
<binop> ::= + | *
That is, a valid mathematical operation is a addition or a multiplication.
So what line 3 of the BNF says is that these are valid shapes:
(x + 10,)(x + y,)(10 + x,)
An astute reader will observe that "("<integer> <binop> <integer>")" (example: (10 × 20,)) isn't allowed. The reasoning is clear - if you know ahead of time what the resulting shape will be, don't put a mathematical expression in. Note that though there is a restriction in the fomal language, this is not enforced by the package machinery.
Recap 1
To recap, these are all examples valid shapes:
()(10,)(10, 20)(x,)(x, 10)(10, x)(x, y)(x+20,)(x×y,)(x+20, 10)(10, x×y)
We wil leave the last part of the definition of S (S ::= ... | T) to after we've introduced the notion of expressions.
Shape Expr: Semantics
TODO: write more
Why So Complicated?
Why introduce all these complicated things? We introduce these complicated things because we want to do things with shape expressions.
It is a System of Constraints
Ideally, the shape expression should be enough to tell you what an operation does to the shape of its inputs.
Consider for example, a shape expression that is the following:
(a, b) → (b, c) → (a, c)
What does this expression say? It says the operation takes a matrix with shape (a, b), and then takes another matrix with the shape (b, c), finally, it returns a matrix of shape (a, c).
This simple expression contains a lot of information:
- The inputs are matrices only.
- The inner dimension of the first input must be the same as the outer dimension of the second input.
- The output is a matrix only, not of any other rank.
- The matching dimensions disappear.
In fact, there is precisely one operation that is described by this expression: Matrix Multiplication.
Here we see one of the functions of the shape expression: it's to provide constraints to the inputs. e.g. the inputs must be matrices; the matching dimensions; etc.
A Second Example
Here's another example. Consider this shape expression, can you guess what it does?
(a, b) → (a, c) → (a, b+c)
Amswer
It's a concatenation on axis 1. A concrete example is given:
t :=
shape: (2, 3)
⎡0 1 2⎤
⎣3 4 5⎦
u :=
shape: (2, 2)
⎡100 200⎤
⎣300 400⎦
Concat(1, t, u) =
shape: (2, 5)
⎡ 0 1 2 100 200⎤
⎣ 3 4 5 300 400⎦
It is a System of Evolving Constraints
The shape expression system can not only define constraints, it can also evolve them.
Going back to the matrix multiplication example, now let's extend it.
(a, b) → (b, c) → (a, c) @ (2, 3)
When this is run through the interpreter of the expression, the result will be the following shape expression:
(3, c) → (2, c)
The constraints have now evolved.
Recall that the @ symbol is an application of a function to an input. So when given an input matrix of a known size - (2, 3), we can evolve the constraints, so the next input will only require one check instead of two.
Documentation
¶
Overview ¶
package shapes provides an algebra for dealing with shapes.
Example (Add) ¶
This examples shows how to describe a particular operation (addition), and how to use the infer functions to provide inference for the following types.
// Consider the idea of adding two tensors - A and B - together.
// If it's a matrix, then both A and B must have a same shape.
// Thus we can use the following shape expression to describe addition:
// Add: a → a → a
//
// if A has shape `a`, then B also has to have shape `a`. The result is also shaped `a`.
add := Arrow{
Var('a'),
Arrow{
Var('a'),
Var('a'),
},
}
fmt.Printf("Add: %v\n", add)
// pass in the first input
fst := Shape{5, 2, 3, 1, 10}
retExpr, err := InferApp(add, fst)
if err != nil {
fmt.Printf("Error %v\n", err)
}
fmt.Printf("Applying %v to Add:\n", fst)
fmt.Printf("%v @ %v ↠ %v\n", add, fst, retExpr)
// pass in the second input
snd := Shape{5, 2, 3, 1, 10}
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Printf("Error %v\n", err)
}
fmt.Printf("Applying %v to the result\n", snd)
fmt.Printf("%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
// bad example:
bad2nd := Shape{2, 3}
_, err = InferApp(retExpr, bad2nd)
fmt.Printf("Passing in a bad second input\n")
fmt.Printf("%v @ %v ↠ %v", retExpr, bad2nd, err)
Output: Add: a → a → a Applying (5, 2, 3, 1, 10) to Add: a → a → a @ (5, 2, 3, 1, 10) ↠ (5, 2, 3, 1, 10) → (5, 2, 3, 1, 10) Applying (5, 2, 3, 1, 10) to the result (5, 2, 3, 1, 10) → (5, 2, 3, 1, 10) @ (5, 2, 3, 1, 10) ↠ (5, 2, 3, 1, 10) Passing in a bad second input (5, 2, 3, 1, 10) → (5, 2, 3, 1, 10) @ (2, 3) ↠ Failed to solve [{(5, 2, 3, 1, 10) → (5, 2, 3, 1, 10) = (2, 3) → a}] | a: Unification Fail. (5, 2, 3, 1, 10) ~ (2, 3) cannot proceed as they do not contain the same amount of sub-expressions. (5, 2, 3, 1, 10) has 5 subexpressions while (2, 3) has 2 subexpressions
Example (Broadcast) ¶
add := Arrow{Var('a'), Arrow{Var('b'), BroadcastOf{Var('a'), Var('b')}}}
expr := Compound{add, SubjectTo{
Bc,
UnaryOp{Const, Var('a')},
UnaryOp{Const, Var('b')},
}}
fst := Shape{2, 3, 4}
snd := Shape{2, 1, 4}
retExpr1, err := InferApp(expr, fst)
if err != nil {
fmt.Println(err)
}
retExpr2, err := InferApp(retExpr1, snd)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Add: %v\n", expr)
fmt.Printf("Applying %v to %v\n", fst, expr)
fmt.Printf("\t%v @ %v → %v\n", expr, fst, retExpr1)
fmt.Printf("Applying %v to %v\n", snd, retExpr1)
fmt.Printf("\t%v @ %v → %v", retExpr1, snd, retExpr2)
Output: Add: { a → b → (a||b) | (K a ⚟ K b) } Applying (2, 3, 4) to { a → b → (a||b) | (K a ⚟ K b) } { a → b → (a||b) | (K a ⚟ K b) } @ (2, 3, 4) → { b → ((2, 3, 4)||b) | (K (2, 3, 4) ⚟ K b) } Applying (2, 1, 4) to { b → ((2, 3, 4)||b) | (K (2, 3, 4) ⚟ K b) } { b → ((2, 3, 4)||b) | (K (2, 3, 4) ⚟ K b) } @ (2, 1, 4) → (2, 3, 4)
Example (ColwiseSumMatrix) ¶
The following shape expressions describe a columnwise summing of a matrix.
// Given A:
// 1 2 3
// 4 5 6
//
// The columnwise sum is:
// 5 7 9
//
// The basic description can be explained as such:
// (r, c) → (1, c)
//
// Here a matrix is given as (r, c). After a columnwise sum, the result is 1 row of c columns.
// However, to keep compatibility with Numpy, a colwise sum would look like this:
// (r, c) → (c, )
//
// Lastly a generalized single-axis sum that would work across all tensors would be:
// a → b | (D b = D a - 1)
//
// Here, it says that the sum is a function that takes a tensor of any shape called `a`, and returns a tensor with a different shape, called `b`.
// The constraints however is that the dimensions of `b` must be the dimensions of `a` minus 1.
basic := MakeArrow(
Abstract{Var('r'), Var('c')},
Abstract{Size(1), Var('c')},
)
fmt.Printf("Basic: %v\n", basic)
compat := MakeArrow(
Abstract{Var('r'), Var('c')},
Abstract{Var('c')},
)
fmt.Printf("Numpy Compatible: %v\n", compat)
general := Arrow{Var('a'), ReductOf{Var('a'), Axis(1)}}
fmt.Printf("General: %v\n", general)
fst := Shape{2, 3}
retExpr, err := InferApp(general, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n", fst, general)
fmt.Printf("\t%v @ %v → %v", general, fst, retExpr)
Output: Basic: (r, c) → (1, c) Numpy Compatible: (r, c) → (c) General: a → /¹a Applying (2, 3) to a → /¹a: a → /¹a @ (2, 3) → (2)
Example (Im2col) ¶
type im2col struct {
h, w int // kernel height and width
padH, padW int
strideH, strideW int
dilationH, dilationW int
}
op := im2col{
3, 3,
1, 1,
1, 1,
1, 1,
}
b := Var('b')
c := Var('c')
h := Var('h')
w := Var('w')
in := Abstract{b, c, h, w}
// h2 = (h+2*op.padH-(op.dilationH*(op.h-1)+1))/op.strideH + 1
h2 := BinOp{
Op: Add,
A: E2{BinOp{
Op: Div,
A: E2{BinOp{
Op: Sub,
A: E2{BinOp{
Op: Add,
A: h,
B: E2{BinOp{
Op: Mul,
A: Size(2),
B: Size(op.padH),
}},
}},
B: Size(op.dilationH*(op.h-1) + 1),
}},
B: Size(op.strideH),
}},
B: Size(1),
}
// w2 = (w+2*op.padW-(op.dilationW*(op.w-1)+1))/op.strideW + 1
w2 := BinOp{
Op: Add,
A: E2{BinOp{
Op: Div,
A: E2{BinOp{
Op: Sub,
A: E2{BinOp{
Op: Add,
A: w,
B: E2{BinOp{
Op: Mul,
A: Size(2),
B: Size(op.padW),
}},
}},
B: Size(op.dilationW*(op.w-1) + 1),
}},
B: Size(op.strideW),
}},
B: Size(1),
}
c2 := BinOp{
Op: Mul,
A: c,
B: Size(op.w * op.h),
}
out := Abstract{b, h2, w2, c2}
im2colExpr := MakeArrow(in, out)
s := Shape{100, 3, 90, 120}
s2, err := InferApp(im2colExpr, s)
if err != nil {
fmt.Printf("Unable to infer %v @ %v", im2colExpr, s)
}
fmt.Printf("im2col: %v\n", im2colExpr)
fmt.Printf("Applying %v to %v:\n", s, im2colExpr)
fmt.Printf("\t%v @ %v → %v", im2colExpr, s, s2)
Output: im2col: (b, c, h, w) → (b, (((h + 2 × 1) - 3) ÷ 1) + 1, (((w + 2 × 1) - 3) ÷ 1) + 1, c × 9) Applying (100, 3, 90, 120) to (b, c, h, w) → (b, (((h + 2 × 1) - 3) ÷ 1) + 1, (((w + 2 × 1) - 3) ÷ 1) + 1, c × 9): (b, c, h, w) → (b, (((h + 2 × 1) - 3) ÷ 1) + 1, (((w + 2 × 1) - 3) ÷ 1) + 1, c × 9) @ (100, 3, 90, 120) → (100, 90, 120, 27)
Example (Index) ¶
sizes := Sizes{0, 0, 1, 0}
simple := Arrow{
Var('a'),
Arrow{
Var('b'),
Abstract{},
},
}
fmt.Printf("Unconstrained Indexing: %v\n", simple)
st := SubjectTo{
And,
SubjectTo{
Eq,
UnaryOp{Dims, Var('a')},
UnaryOp{Dims, Var('b')},
},
SubjectTo{
Lt,
UnaryOp{ForAll, Var('b')},
UnaryOp{ForAll, Var('a')},
},
}
index := Compound{Expr: simple, SubjectTo: st}
fmt.Printf("Indexing: %v\n", index)
fst := Shape{1, 2, 3, 4}
retExpr, err := InferApp(index, fst)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", fst, index)
fmt.Printf("\t%v @ %v ↠ %v\n", index, fst, retExpr)
snd := sizes
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
Output: Unconstrained Indexing: a → b → () Indexing: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } Applying (1, 2, 3, 4) to { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) }: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } @ (1, 2, 3, 4) ↠ { b → () | ((D (1, 2, 3, 4) = D b) ∧ (∀ b < ∀ (1, 2, 3, 4))) } Applying Sz[0 0 1 0] to { b → () | ((D (1, 2, 3, 4) = D b) ∧ (∀ b < ∀ (1, 2, 3, 4))) }: { b → () | ((D (1, 2, 3, 4) = D b) ∧ (∀ b < ∀ (1, 2, 3, 4))) } @ Sz[0 0 1 0] ↠ ()
Example (Index_scalar) ¶
sizes := Sizes{}
simple := Arrow{
Var('a'),
Arrow{
Var('b'),
Abstract{},
},
}
fmt.Printf("Unconstrained Indexing: %v\n", simple)
st := SubjectTo{
And,
SubjectTo{
Eq,
UnaryOp{Dims, Var('a')},
UnaryOp{Dims, Var('b')},
},
SubjectTo{
Lt,
UnaryOp{ForAll, Var('b')},
UnaryOp{ForAll, Var('a')},
},
}
index := Compound{Expr: simple, SubjectTo: st}
fmt.Printf("Indexing: %v\n", index)
fst := Shape{}
retExpr, err := InferApp(index, fst)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", fst, index)
fmt.Printf("\t%v @ %v ↠ %v\n", index, fst, retExpr)
snd := sizes
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
Output: Unconstrained Indexing: a → b → () Indexing: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } Applying () to { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) }: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } @ () ↠ { b → () | ((D () = D b) ∧ (∀ b < ∀ ())) } Applying Sz[] to { b → () | ((D () = D b) ∧ (∀ b < ∀ ())) }: { b → () | ((D () = D b) ∧ (∀ b < ∀ ())) } @ Sz[] ↠ ()
Example (Index_unidimensional) ¶
sizes := Sizes{0}
simple := Arrow{
Var('a'),
Arrow{
Var('b'),
Abstract{},
},
}
fmt.Printf("Unconstrained Indexing: %v\n", simple)
st := SubjectTo{
And,
SubjectTo{
Eq,
UnaryOp{Dims, Var('a')},
UnaryOp{Dims, Var('b')},
},
SubjectTo{
Lt,
UnaryOp{ForAll, Var('b')},
UnaryOp{ForAll, Var('a')},
},
}
index := Compound{Expr: simple, SubjectTo: st}
fmt.Printf("Indexing: %v\n", index)
fst := Shape{5}
retExpr, err := InferApp(index, fst)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", fst, index)
fmt.Printf("\t%v @ %v ↠ %v\n", index, fst, retExpr)
snd := sizes
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
Output: Unconstrained Indexing: a → b → () Indexing: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } Applying (5) to { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) }: { a → b → () | ((D a = D b) ∧ (∀ b < ∀ a)) } @ (5) ↠ { b → () | ((D (5) = D b) ∧ (∀ b < ∀ (5))) } Applying Sz[0] to { b → () | ((D (5) = D b) ∧ (∀ b < ∀ (5))) }: { b → () | ((D (5) = D b) ∧ (∀ b < ∀ (5))) } @ Sz[0] ↠ ()
Example (KeepDims) ¶
keepDims1 := MakeArrow(
MakeArrow(Var('a'), Var('b')),
Var('a'),
Var('c'),
)
expr := Compound{keepDims1, SubjectTo{
Eq,
UnaryOp{Dims, Var('a')},
UnaryOp{Dims, Var('c')},
}}
fmt.Printf("KeepDims1: %v", expr)
Output: KeepDims1: { (a → b) → a → c | (D a = D c) }
Example (MatMul) ¶
matmul := Arrow{
Abstract{Var('a'), Var('b')},
Arrow{
Abstract{Var('b'), Var('c')},
Abstract{Var('a'), Var('c')},
},
}
fmt.Printf("MatMul: %v\n", matmul)
// Apply the first input to MatMul
fst := Shape{2, 3}
expr2, err := InferApp(matmul, fst)
if err != nil {
fmt.Printf("Error: %v\n", err)
return
}
fmt.Printf("Applying %v to MatMul:\n", fst)
fmt.Printf("%v @ %v ↠ %v\n", matmul, fst, expr2)
// Apply the second input
snd := Shape{3, 4}
expr3, err := InferApp(expr2, snd)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to the result:\n", snd)
fmt.Printf("%v @ %v ↠ %v\n", expr2, snd, expr3)
// Bad example:
bad2nd := Shape{4, 5}
_, err = InferApp(expr2, bad2nd)
fmt.Printf("What happens when you pass in a bad value (e.g. %v instead of %v):\n", bad2nd, snd)
fmt.Printf("%v @ %v ↠ %v", expr2, bad2nd, err)
Output: MatMul: (a, b) → (b, c) → (a, c) Applying (2, 3) to MatMul: (a, b) → (b, c) → (a, c) @ (2, 3) ↠ (3, c) → (2, c) Applying (3, 4) to the result: (3, c) → (2, c) @ (3, 4) ↠ (2, 4) What happens when you pass in a bad value (e.g. (4, 5) instead of (3, 4)): (3, c) → (2, c) @ (4, 5) ↠ Failed to solve [{(3, c) → (2, c) = (4, 5) → d}] | d: Unification Fail. 3 ~ 4 cannot proceed
Example (Package) ¶
package main
import (
"fmt"
"github.com/pkg/errors"
"gorgonia.org/shapes"
)
type Dense struct {
data []float64
shape shapes.Shape
}
func (d *Dense) Shape() shapes.Shape { return d.shape }
type elemwiseFn func(a, b *Dense) (*Dense, error)
func (f elemwiseFn) Shape() shapes.Expr {
return shapes.Arrow{
shapes.Var('a'),
shapes.Arrow{shapes.Var('a'), shapes.Var('a')},
}
}
type matmulFn func(a, b *Dense) (*Dense, error)
func (f matmulFn) Shape() shapes.Expr {
return shapes.Arrow{
shapes.Abstract{shapes.Var('a'), shapes.Var('b')},
shapes.Arrow{
shapes.Abstract{shapes.Var('b'), shapes.Var('c')},
shapes.Abstract{shapes.Var('a'), shapes.Var('c')},
},
}
}
type applyFn func(*Dense, func(float64) float64) (*Dense, error)
func (f applyFn) Shape() shapes.Expr {
return shapes.Arrow{
shapes.Var('a'),
shapes.Arrow{
shapes.Arrow{
shapes.Var('b'),
shapes.Var('b'),
},
shapes.Var('a'),
},
}
}
func (d *Dense) MatMul(other *Dense) (*Dense, error) {
expr := matmulFn((*Dense).MatMul).Shape()
sh, err := infer(expr, d.Shape(), other.Shape())
if err != nil {
return nil, err
}
retVal := &Dense{
data: make([]float64, sh.TotalSize()),
shape: sh,
}
return retVal, nil
}
func (d *Dense) Add(other *Dense) (*Dense, error) {
expr := elemwiseFn((*Dense).Add).Shape()
sh, err := infer(expr, d.Shape(), other.Shape())
if err != nil {
return nil, err
}
retVal := &Dense{
data: make([]float64, sh.TotalSize()),
shape: sh,
}
return retVal, nil
}
func (d *Dense) Apply(fn func(float64) float64) (*Dense, error) {
expr := applyFn((*Dense).Apply).Shape()
fnShape := shapes.ShapeOf(fn)
sh, err := infer(expr, d.Shape(), fnShape)
if err != nil {
return nil, err
}
return &Dense{shape: sh}, nil
}
func infer(fn shapes.Expr, others ...shapes.Expr) (shapes.Shape, error) {
retShape, err := shapes.InferApp(fn, others...)
if err != nil {
return nil, err
}
sh, err := shapes.ToShape(retShape)
if err != nil {
return nil, errors.Wrapf(err, "Expected a Shape in retShape. Got %v of %T instead", retShape, retShape)
}
return sh, nil
}
func main() {
A := &Dense{
data: []float64{1, 2, 3, 4, 5, 6},
shape: shapes.Shape{2, 3},
}
B := &Dense{
data: []float64{10, 20, 30, 40, 50, 60},
shape: shapes.Shape{3, 2},
}
var fn shapes.Exprer = matmulFn((*Dense).MatMul)
C, err := A.MatMul(B)
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("×: %v\n", fn.Shape())
fmt.Printf("\t A × B = C\n\t%v × %v = %v\n", A.Shape(), B.Shape(), C.Shape())
fmt.Println("---")
fn = elemwiseFn((*Dense).Add)
D := &Dense{
data: []float64{0, 0, 0, 0},
shape: shapes.Shape{2, 2},
}
E, err := C.Add(D)
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("+: %v\n", fn.Shape())
fmt.Printf("\t C + D = E\n")
fmt.Printf("\t%v + %v = %v\n", C.Shape(), D.Shape(), E.Shape())
fmt.Println("---")
square := func(a float64) float64 { return a * a }
squareShape := shapes.ShapeOf(square)
fn = applyFn((*Dense).Apply)
F, err := E.Apply(square)
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("@: %v\n", fn.Shape())
fmt.Printf("square: %v\n", squareShape)
fmt.Printf("\t E @ square = F\n")
fmt.Printf("\t%v @ (%v) = %v\n", E.Shape(), squareShape, F.Shape())
fmt.Println("---")
// trying to do a bad add (e.g. adding two matrices with different shapes) will yield an error
fn = elemwiseFn((*Dense).Add)
_, err = E.Add(A)
fmt.Printf("+: %v\n", fn.Shape())
fmt.Printf("\t E + A =\n")
fmt.Printf("\t%v + %v = ", E.Shape(), A.Shape())
fmt.Println(err)
}
Output: ×: (a, b) → (b, c) → (a, c) A × B = C (2, 3) × (3, 2) = (2, 2) --- +: a → a → a C + D = E (2, 2) + (2, 2) = (2, 2) --- @: a → (b → b) → a square: () → () E @ square = F (2, 2) @ (() → ()) = (2, 2) --- +: a → a → a E + A = (2, 2) + (2, 3) = Failed to solve [{(2, 2) → (2, 2) = (2, 3) → a}] | a: Unification Fail. 2 ~ 3 cannot proceed
Example (Ravel) ¶
ravel := Arrow{
Var('a'),
Abstract{UnaryOp{Prod, Var('a')}},
}
fmt.Printf("Ravel: %v\n", ravel)
fst := Shape{2, 3, 4}
retExpr, err := InferApp(ravel, fst)
if err != nil {
fmt.Printf("Error %v\n", err)
}
fmt.Printf("Applying %v to Ravel:\n", fst)
fmt.Printf("%v @ %v ↠ %v", ravel, fst, retExpr)
Output: Ravel: a → (Π a) Applying (2, 3, 4) to Ravel: a → (Π a) @ (2, 3, 4) ↠ (24)
Example (Reshape) ¶
expr := Compound{
Arrow{
Var('a'),
Arrow{
Var('b'),
Var('b'),
},
},
SubjectTo{
Eq,
UnaryOp{Prod, Var('a')},
UnaryOp{Prod, Var('b')},
},
}
fmt.Printf("Reshape: %v\n", expr)
fst := Shape{2, 3}
snd := Shape{3, 2}
retExpr, err := InferApp(expr, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n", fst, expr)
fmt.Printf("\t%v @ %v ↠ %v\n", expr, fst, retExpr)
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
bad := Shape{6, 2}
_, err = InferApp(retExpr, bad)
fmt.Printf("Applying a bad shape %v to %v:\n", bad, retExpr)
fmt.Printf("\t%v\n", err)
Output: Reshape: { a → b → b | (Π a = Π b) } Applying (2, 3) to { a → b → b | (Π a = Π b) }: { a → b → b | (Π a = Π b) } @ (2, 3) ↠ { b → b | (Π (2, 3) = Π b) } Applying (3, 2) to { b → b | (Π (2, 3) = Π b) }: { b → b | (Π (2, 3) = Π b) } @ (3, 2) ↠ (3, 2) Applying a bad shape (6, 2) to { b → b | (Π (2, 3) = Π b) }: SubjectTo (Π (2, 3) = Π (6, 2)) resolved to false. Cannot continue
Example (Slice) ¶
sli := Range{0, 2, 1}
simple := Arrow{
Var('a'),
Arrow{
Var('b'),
SliceOf{
Var('b'),
Var('a'),
},
},
}
slice := Compound{
Expr: simple,
SubjectTo: SubjectTo{
OpType: Gte,
A: IndexOf{I: 0, A: Var('a')},
B: Size(2),
},
}
fmt.Printf("slice: %v\n", slice)
fst := Shape{5, 3, 4}
retExpr, err := InferApp(slice, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n", fst, slice)
fmt.Printf("\t%v @ %v ↠ %v\n", slice, fst, retExpr)
snd := sli
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
Output: slice: { a → b → a[b] | (a[0] ≥ 2) } Applying (5, 3, 4) to { a → b → a[b] | (a[0] ≥ 2) }: { a → b → a[b] | (a[0] ≥ 2) } @ (5, 3, 4) ↠ b → (5, 3, 4)[b] Applying [0:2] to b → (5, 3, 4)[b]: b → (5, 3, 4)[b] @ [0:2] ↠ (2, 3, 4)
Example (Slice_basic) ¶
sli := Range{0, 2, 1}
last := Range{3, 4, 1}
so := SliceOf{
Slices{sli, sli, last},
Var('a'),
}
simple := Arrow{
Var('a'),
so,
}
fmt.Printf("Simple Slice: %v\n", simple)
fst := Shape{5, 3, 4}
retExpr, err := InferApp(simple, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v:\n\t%v @ %v ↠ %v\n", fst, simple, simple, fst, retExpr)
Output: Simple Slice: a → a[0:2, 0:2, 3] Applying (5, 3, 4) to a → a[0:2, 0:2, 3]: a → a[0:2, 0:2, 3] @ (5, 3, 4) ↠ (2, 2)
Example (Sum_allAxes) ¶
sum := Arrow{Var('a'), Reduce(Var('a'), Axes{0, 1})}
fmt.Printf("Sum: %v\n", sum)
fst := Shape{2, 3}
retExpr, err := InferApp(sum, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v\n", fst, sum)
fmt.Printf("\t%v @ %v → %v\n", sum, fst, retExpr)
sum1 := Arrow{Var('a'), ReductOf{Var('a'), AllAxes}}
retExpr1, err := InferApp(sum1, fst)
if err != nil {
fmt.Println(err)
}
fmt.Printf("Applying %v to %v\n", fst, sum1)
fmt.Printf("\t%v @ %v → %v", sum1, fst, retExpr1)
Output: Sum: a → /⁰/¹a Applying (2, 3) to a → /⁰/¹a a → /⁰/¹a @ (2, 3) → () Applying (2, 3) to a → /⁼a a → /⁼a @ (2, 3) → ()
Example (Trace) ¶
expr := Arrow{
Abstract{Var('a'), Var('a')},
Shape{},
}
fmt.Printf("Trace: %v\n", expr)
Output: Trace: (a, a) → ()
Example (Transpose) ¶
axes := Axes{0, 1, 3, 2}
simple := Arrow{
Var('a'),
Arrow{
axes,
TransposeOf{
axes,
Var('a'),
},
},
}
fmt.Printf("Unconstrained Transpose: %v\n", simple)
st := SubjectTo{
Eq,
UnaryOp{Dims, axes},
UnaryOp{Dims, Var('a')},
}
transpose := Compound{
Expr: simple,
SubjectTo: st,
}
fmt.Printf("Transpose: %v\n", transpose)
fst := Shape{1, 2, 3, 4}
retExpr, err := InferApp(transpose, fst)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", fst, transpose)
fmt.Printf("\t%v @ %v ↠ %v\n", transpose, fst, retExpr)
snd := axes
retExpr2, err := InferApp(retExpr, snd)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Applying %v to %v:\n", snd, retExpr)
fmt.Printf("\t%v @ %v ↠ %v\n", retExpr, snd, retExpr2)
// bad axes
bad2nd := Axes{0, 2, 1, 3} // not the original axes {0,1,3,2}
_, err = InferApp(retExpr, bad2nd)
fmt.Printf("Bad Axes causes error: %v\n", err)
// bad first input
bad1st := Shape{2, 3, 4}
_, err = InferApp(transpose, bad1st)
fmt.Printf("Bad first input causes error: %v", err)
Output: Unconstrained Transpose: a → X[0 1 3 2] → T⁽⁰ ¹ ³ ²⁾ a Transpose: { a → X[0 1 3 2] → T⁽⁰ ¹ ³ ²⁾ a | (D X[0 1 3 2] = D a) } Applying (1, 2, 3, 4) to { a → X[0 1 3 2] → T⁽⁰ ¹ ³ ²⁾ a | (D X[0 1 3 2] = D a) }: { a → X[0 1 3 2] → T⁽⁰ ¹ ³ ²⁾ a | (D X[0 1 3 2] = D a) } @ (1, 2, 3, 4) ↠ X[0 1 3 2] → (1, 2, 4, 3) Applying X[0 1 3 2] to X[0 1 3 2] → (1, 2, 4, 3): X[0 1 3 2] → (1, 2, 4, 3) @ X[0 1 3 2] ↠ (1, 2, 4, 3) Bad Axes causes error: Failed to solve [{X[0 1 3 2] → (1, 2, 4, 3) = X[0 2 1 3] → a}] | a: Unification Fail. X[0 1 3 2] ~ X[0 2 1 3] cannot proceed Bad first input causes error: SubjectTo (D X[0 1 3 2] = D (2, 3, 4)) resolved to false. Cannot continue
Example (Transpose_NoOp) ¶
axes := Axes{0, 1, 2, 3} // when the axes are monotonic, there is NoOp.
transpose := Arrow{
Var('a'),
TransposeOf{
axes,
Var('a'),
},
}
fst := Shape{1, 2, 3, 4}
retExpr, err := InferApp(transpose, fst)
if err != nil {
fmt.Printf("Error %v\n", err)
}
fmt.Printf("Applying %v to %v\n", fst, transpose)
fmt.Printf("\t%v @ %v ↠ %v", transpose, fst, retExpr)
Output: Applying (1, 2, 3, 4) to a → T⁽⁰ ¹ ² ³⁾ a a → T⁽⁰ ¹ ² ³⁾ a @ (1, 2, 3, 4) ↠ (1, 2, 3, 4)
Example (UnsafePermute) ¶
pattern := []int{2, 1, 3, 4, 0}
x1 := []int{1, 2, 3, 4, 5}
x2 := []int{5, 4, 3, 2, 1}
fmt.Printf("Before:\nx1: %v\nx2: %v\n", x1, x2)
err := UnsafePermute(pattern, x1, x2)
if err != nil {
fmt.Println(err)
}
fmt.Printf("After:\nx1: %v\nx2: %v\n\n", x1, x2)
// when patterns are monotonic and increasing, it is noop
pattern = []int{0, 1, 2, 3, 4}
err = UnsafePermute(pattern, x1, x2)
if _, ok := err.(NoOpError); ok {
fmt.Printf("NoOp with %v:\nx1: %v\nx2: %v\n\n", pattern, x1, x2)
}
// special cases for 2 dimensions
x1 = x1[:2]
x2 = x2[:2]
fmt.Printf("Before:\nx1: %v\nx2: %v\n", x1, x2)
pattern = []int{1, 0} // the only valid pattern with 2 dimensions
if err := UnsafePermute(pattern, x1, x2); err != nil {
fmt.Println(err)
}
fmt.Printf("After:\nx1: %v\nx2: %v\n\n", x1, x2)
// Bad patterns
// invalid axis
pattern = []int{2, 1}
err = UnsafePermute(pattern, x1, x2)
fmt.Printf("Invalid axis in pattern %v: %v\n", pattern, err)
// repeated axes
pattern = []int{1, 1}
err = UnsafePermute(pattern, x1, x2)
fmt.Printf("Repeated axes in pattern %v: %v\n", pattern, err)
// dimension mismatches
pattern = []int{1}
err = UnsafePermute(pattern, x1, x2)
fmt.Printf("Pattern %v has a smaller dimension than xs: %v\n", pattern, err)
Output: Before: x1: [1 2 3 4 5] x2: [5 4 3 2 1] After: x1: [3 2 4 5 1] x2: [3 4 2 1 5] NoOp with [0 1 2 3 4]: x1: [3 2 4 5 1] x2: [3 4 2 1 5] Before: x1: [3 2] x2: [3 4] After: x1: [2 3] x2: [4 3] Invalid axis in pattern [2 1]: Invalid axis 2 for ndarray with 2 dimensions. Repeated axes in pattern [1 1]: repeated axis 1 in permutation pattern. Pattern [1] has a smaller dimension than xs: Dimension mismatch. Expected 2. Got 1 instead.
Index ¶
- func AreBroadcastable(a, b Shape) (err error)
- func CheckSlice(s Slice, size int) error
- func IsMonotonicInts(a []int) (monotonic bool, incr1 bool)
- func SliceDetails(s Slice, size int) (start, end, step int, err error)
- func UnsafePermute(pattern []int, xs ...[]int) (err error)
- func Verify(any interface{}) error
- type Abstract
- func (a Abstract) Clone() Abstract
- func (a Abstract) Concat(axis Axis, others ...Shapelike) (newShape Shapelike, err error)
- func (a Abstract) Cons(other Conser) (retVal Conser)
- func (a Abstract) DimSize(dim int) (Sizelike, error)
- func (a Abstract) Dims() int
- func (s Abstract) Format(st fmt.State, r rune)
- func (a Abstract) Repeat(axis Axis, repeats ...int) (retVal Shapelike, finalRepeats []int, size int, err error)
- func (a Abstract) S(slices ...Slice) (newShape Shapelike, err error)
- func (a Abstract) T(axes ...Axis) (newShape Shapelike, err error)
- func (a Abstract) ToShape() (s Shape, ok bool)
- func (a Abstract) TotalSize() int
- type Arrow
- type Axes
- type Axis
- type BinOp
- type BroadcastOf
- type Compound
- type ConcatOf
- type Conser
- type ConstraintsExpr
- type E2
- type Expr
- type Exprer
- type IndexOf
- type NoOpError
- type OpType
- type Operation
- type Range
- type ReductOf
- type RepeatOf
- type Shape
- func (s Shape) AsInts() []int
- func (s Shape) Clone() Shape
- func (s Shape) Concat(axis Axis, ss ...Shapelike) (retVal Shapelike, err error)
- func (s Shape) Cons(other Conser) Conser
- func (s Shape) Dim(d int) (retVal int, err error)
- func (s Shape) DimSize(d int) (retVal Sizelike, err error)
- func (s Shape) Dims() int
- func (s Shape) Eq(other Shape) bool
- func (s Shape) Format(st fmt.State, r rune)
- func (s Shape) IsColVec() bool
- func (s Shape) IsMatrix() bool
- func (s Shape) IsRowVec() bool
- func (s Shape) IsScalar() bool
- func (s Shape) IsScalarEquiv() bool
- func (s Shape) IsVector() bool
- func (s Shape) IsVectorLike() bool
- func (s Shape) Repeat(axis Axis, repeats ...int) (retVal Shapelike, finalRepeats []int, size int, err error)
- func (s Shape) S(slices ...Slice) (newShape Shapelike, err error)
- func (s Shape) Shape() Shape
- func (s Shape) T(axes ...Axis) (newShape Shapelike, err error)
- func (s Shape) TotalSize() int
- type Shapelike
- type Shaper
- type Size
- type Sizelike
- type Sizes
- type Slice
- type SliceOf
- type Slicelike
- type Slices
- type SubjectTo
- type TransposeOf
- type UnaryOp
- type Var
Examples ¶
- Package (Add)
- Package (Broadcast)
- Package (ColwiseSumMatrix)
- Package (Im2col)
- Package (Index)
- Package (Index_scalar)
- Package (Index_unidimensional)
- Package (KeepDims)
- Package (MatMul)
- Package (Package)
- Package (Ravel)
- Package (Reshape)
- Package (Slice)
- Package (Slice_basic)
- Package (Sum_allAxes)
- Package (Trace)
- Package (Transpose)
- Package (Transpose_NoOp)
- Package (UnsafePermute)
- Gen
- MakeArrow
- Shape.IsScalarEquiv
- Slice (S)
- Verify
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AreBroadcastable ¶
AreBroadcastable checks that two shapes are mutually broadcastable.
func CheckSlice ¶
CheckSlice checks a slice to see if it's sane
func IsMonotonicInts ¶
IsMonotonicInts returns true if the slice of ints is monotonically increasing. It also returns true for incr1 if every succession is a succession of 1
func SliceDetails ¶
SliceDetails is a function that takes a slice and spits out its details. The whole reason for this is to handle the nil Slice, which is this: a[:]
func UnsafePermute ¶
UnsafePermute permutes the xs according to the pattern. Each x in xs must have the same length as the pattern's length.
func Verify ¶
func Verify(any interface{}) error
Verify checks that the values of a data structure conforms to the expected shape, given in struct tags.
Example - consider the following struct:
type Foo struct {
A tensor.Tensor `shape:"(a, b)"`
B tensor.Tensor `shape:"(b, c)"`
}
At runtime, the fields A and B would be populated with a Tensor of arbitrary shape. Verify can verify that A and B have the expected patterns of shapes.
So, if A has a shape of (2, 3), B's shape cannot be (4, 5). It can be (3, 5).
Example ¶
package main
import (
"fmt"
. "gorgonia.org/shapes"
)
type T int
func (t T) Shape() Shape {
switch t {
case 0:
return Shape{5, 4, 2}
case 1:
return Shape{4, 2}
case 2:
return Shape{2, 10}
default:
return Shape{10, 10, 10, 10} // bad shape
}
}
func main() {
// the actual field type doesn't matter for now
type A struct {
A T `shape:"(a, b, c)"`
B T `shape:"(b, c)"`
}
type B struct {
A
C T `shape:"(c, d)"`
}
a1 := A{0, 1}
a2 := A{0, 100}
if err := Verify(a1); err != nil {
fmt.Printf("a1 is a correct value. No errors expected. Got %v instead\n", err)
}
err := Verify(a2)
if err == nil {
fmt.Printf("a2 is an incorrect value. Errors expected but none was returned\n")
}
}
Output:
Types ¶
type Abstract ¶
type Abstract []Sizelike
Abstract is an abstract shape
func Gen ¶
Gen creates an abstract with the provided dims. This is particularly useful for generating abstracts for higher order functions.
Example ¶
Gen is a generator for Abstracts
a := Gen(2)
fmt.Printf("Gen(2): %v\n", a)
// Gen is not a stateful generator
b := Gen(2)
fmt.Printf("Gen(2): %v\n", b)
// Gen handles a maximum of 50 characters(so far)
c := Gen(50)
fmt.Printf("Gen(50): %v\n", c)
defer func() {
if r := recover(); r != nil {
fmt.Println("Gen will panic if a `d` >= 51 is passed in.")
}
}()
Gen(51)
Output: Gen(2): (a, b) Gen(2): (a, b) Gen(50): (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, α, β, γ, δ, ε, ζ, η, θ, ι, κ, λ, μ, ν, ξ, ο, π, ρ, ς, σ, τ, υ, φ, χ, ψ) Gen will panic if a `d` >= 51 is passed in.
type Arrow ¶
type Arrow struct {
A, B Expr
}
Arrow represents a function of shapes, from A → B. Arrows are right associative.
func MakeArrow ¶
MakeArrow is a utility function for writing correct Arrow expressions.
Consider for example, matrix multiplication. It is written plainly as follows:
MatMul: (a, b) → (b, c) → (a, c)
However, note that because arrows are right associative and they're a binary operator, it actually is more correctly written like this:
MatMul: (a, b) → ((b, c) → (a, c))
This makes writing plain Arrow{} expressions a bit fraught with errors (see example). Thus, the MakeArrow function is created to help write more correct expressions.
Example ¶
MakeArrow is a utility function
matmul := MakeArrow(
Abstract{Var('a'), Var('b')},
Abstract{Var('b'), Var('c')},
Abstract{Var('a'), Var('c')},
)
fmt.Printf("Correct MatMul: %v\n", matmul)
wrong := Arrow{
Arrow{Abstract{Var('a'), Var('b')},
Abstract{Var('b'), Var('c')},
},
Abstract{Var('a'), Var('c')},
}
fmt.Printf("Wrong MatMul: %v\n", wrong)
// it doesn't mean that you should use MakeArrow mindlessly.
// Consider the higher order function Map: (a → a) → b → b
// p.s equiv Go function signature:
// func Map(f func(a int) int, b Tensor) Tensor
Map := MakeArrow(
Arrow{Var('a'), Var('a')}, // you can also use MakeArrow here
Var('b'),
Var('b'),
)
fmt.Printf("Correct Map: %v\n", Map)
wrong = MakeArrow(
Var('a'), Var('a'),
Var('b'),
Var('b'),
)
fmt.Printf("Wrong Map: %v\n", wrong)
Output: Correct MatMul: (a, b) → (b, c) → (a, c) Wrong MatMul: ((a, b) → (b, c)) → (a, c) Correct Map: (a → a) → b → b Wrong Map: a → a → b → b
type Axes ¶
type Axes []Axis
Axes represents a list of axes. Despite being a container type (i.e. an Axis is an Expr), it returns nil for Exprs(). This is because we want to treat Axes as a monolithic entity.
type Axis ¶
type Axis int
Axis represents an axis in doing shape stuff.
const (
AllAxes Axis = -65535
)
func ResolveAxis ¶
type BinOp ¶
BinOp represents a binary operation. It is only an Expr for the purposes of being a value in a shape. On the toplevel, BinOp on is meaningless. This is enforced in the `unify` function.
type BroadcastOf ¶
type BroadcastOf struct {
A, B Expr
}
BroadcastOf represents the results of mutually broadcasting A and B expr.
type Conser ¶
Conser is anything that can be used to construct another Conser. The following types are Conser:
Shape | Abstract
type ConstraintsExpr ¶
type ConstraintsExpr struct {
// contains filtered or unexported fields
}
ConstraintExpr is a tuple of a list of constraints and an expression.
func App ¶
func App(ar Expr, b Expr) ConstraintsExpr
App applys an expression to a function/Arrow expression. This function will aggressively perform alpha renaming on the expression.
Example. Given an application of the following:
((a,b) → (b, c) → (a, c)) @ (2, a)
The variables in the latter will be aggressively renamed, to become:
((a,b) → (b, c) → (a, c)) @ (2, d)
Normally this wouldn't be a concern, as you would be passing in concrete shapes, something like:
((a,b) → (b, c) → (a, c)) @ (2, 3)
which will then yield:
(3, c) → (2, c)
type Expr ¶
type Expr interface {
// contains filtered or unexported methods
}
Expr represents an expression. The following types are Expr:
Shape | Abstract | Arrow | Compound Var | Size | UnaryOp IndexOf | TransposeOf | SliceOf | RepeatOf | ConcatOf Sli | Axis | Axes
A compact BNF is as follows:
E := S | A | E → E | (E s.t. X) a | Sz | Π E | Σ E | D E I n E | T []Ax E | L : E | R Ax n E | C Ax E E : | Ax | []Ax
func Infer ¶
func Infer(ce ConstraintsExpr) (Expr, error)
type Exprer ¶
type Exprer interface {
Shape() Expr
}
Exprer is anything that can return a Shape Expr.
type IndexOf ¶
IndexOf gets the size of a given shape (expression) at the given index.
IndexOf is the symbolic version of doing s[i], where s is a Shape.
type NoOpError ¶
type NoOpError interface {
NoOp()
}
NoOpError is a useful for operations that have no op.
type Operation ¶
type Operation interface {
// contains filtered or unexported methods
}
Operation represents an operation (BinOp or UnaryOp)
type Range ¶
type Range struct {
// contains filtered or unexported fields
}
Range is a shape expression representing a slicing range. Coincidentally, Range also implements Slice.
A Range is a shape expression but it doesn't stand alone - resolving it will yield an error.
type Shape ¶
type Shape []int
Shape represents the shape of a multidimensional array.
func CalcBroadcastShape ¶
CalcBroadcastShape computes the final shape of two mutually broadcastable shapes. This function does not check that the shapes are mutually broadcastable. Use `AreBroadcastable` for that functionality.
func ScalarShape ¶
func ScalarShape() Shape
ScalarShape returns a shape that represents a scalar shape.
Usually `nil` will also be considered a scalar shape (because a `nil` of type `Shape` has a length of 0 and will return true when `.IsScalar` is called)
func (Shape) Eq ¶
Eq indicates if a shape is equal with another. There is a soft concept of equality when it comes to vectors.
If s is a column vector and other is a vanilla vector, they're considered equal if the size of the column dimension is the same as the vector size; if s is a row vector and other is a vanilla vector, they're considered equal if the size of the row dimension is the same as the vector size
func (Shape) IsMatrix ¶
IsMatrix returns true if it's a matrix. This is mostly a convenience method. RowVec and ColVecs are also considered matrices
func (Shape) IsScalarEquiv ¶
IsScalarEquiv returns true if the access pattern indicates it's a scalar-like value
Example ¶
s := Shape{1, 1, 1, 1, 1, 1}
fmt.Printf("%v is scalar equiv: %t\n", s, s.IsScalarEquiv())
s = Shape{}
fmt.Printf("%v is scalar equiv: %t\n", s, s.IsScalarEquiv())
s = Shape{2, 3}
fmt.Printf("%v is scalar equiv: %t\n", s, s.IsScalarEquiv())
s = Shape{0, 0, 0}
fmt.Printf("%v is scalar equiv: %t\n", s, s.IsScalarEquiv())
s = Shape{1, 2, 0, 3}
fmt.Printf("%v is scalar equiv: %t\n", s, s.IsScalarEquiv())
Output: (1, 1, 1, 1, 1, 1) is scalar equiv: true () is scalar equiv: true (2, 3) is scalar equiv: false (0, 0, 0) is scalar equiv: true (1, 2, 0, 3) is scalar equiv: false
func (Shape) IsVector ¶
IsVector returns whether the access pattern falls into one of three possible definitions of vectors:
vanilla vector (not a row or a col) column vector row vector
func (Shape) IsVectorLike ¶
IsVectorLike returns true when the shape looks like a vector e.g. a number that is surrounded by 1s:
(1, 1, ... 1, 10, 1, 1... 1)
func (Shape) Repeat ¶
func (s Shape) Repeat(axis Axis, repeats ...int) (retVal Shapelike, finalRepeats []int, size int, err error)
Repeat returns the expected new shape given the repetition parameters
type Shapelike ¶
type Shapelike interface {
Dims() int
TotalSize() int // needed?
DimSize(dim int) (Sizelike, error)
T(axes ...Axis) (newShape Shapelike, err error)
S(slices ...Slice) (newShape Shapelike, err error)
Repeat(axis Axis, repeats ...int) (newShape Shapelike, finalRepeats []int, size int, err error)
Concat(axis Axis, others ...Shapelike) (newShape Shapelike, err error)
}
Shapelike is anything that performs all the things you can do with a Shape. The following types provided by this library are Shapelike:
Shape | Abstract
func ShapesToShapelikes ¶
ShapesToShapelikes is a utility function that retuns a []Shapelike given a []Shape.
type Sizelike ¶
type Sizelike interface {
// contains filtered or unexported methods
}
Sizelike represents something that can go into a Abstract. The following types are Sizelike:
Size | Var | BinOp | UnaryOp
type Slice ¶
Slice represents a slicing range.
Example (S) ¶
param0 := Abstract{Var('a'), Var('b')}
param1 := Abstract{Var('a'), Var('b'), BinOp{Add, Var('a'), Var('b')}, UnaryOp{Const, Var('b')}}
expected, err := param1.S(S(1, 5), S(1, 5), S(1, 5), S(2, 5))
if err != nil {
fmt.Printf("Err %v\n", err)
return
}
expr := MakeArrow(param0, param1, expected.(Expr))
fmt.Printf("expr: %v\n", expr)
fst := Shape{10, 20}
result, err := InferApp(expr, fst)
if err != nil {
fmt.Printf("Err %v\n", err)
return
}
fmt.Printf("%v @ %v ↠ %v\n", expr, fst, result)
snd := Shape{10, 20, 30, 20}
result2, err := InferApp(result, snd)
if err != nil {
fmt.Printf("Err %v\n", err)
return
}
fmt.Printf("%v @ %v ↠ %v", result, snd, result2)
Output: expr: (a, b) → (a, b, a + b, K b) → (a[1:5], b[1:5], a + b[1:5], K b[2:5]) (a, b) → (a, b, a + b, K b) → (a[1:5], b[1:5], a + b[1:5], K b[2:5]) @ (10, 20) ↠ (10, 20, 30, 20) → (4, 4, 4, 3) (10, 20, 30, 20) → (4, 4, 4, 3) @ (10, 20, 30, 20) ↠ (4, 4, 4, 3)
type Slicelike ¶
type Slicelike interface {
// contains filtered or unexported methods
}
Slicelike is anything like a slice. The following types implement Slicelike:
Range | Var
func ToSlicelike ¶
ToSlicelike is a utility function for turning a slice into a Slicelike.
type TransposeOf ¶
TransposeOf is the symbolic version of doing s.T(axes...)
Source Files