3
$\begingroup$

First, I'm mostly experienced with Math, which I hope won't be too inconvenient.

I saw Operational Calculus on Programming Spaces by Sajovic and Vuk, which seemed very interesting to me (for a "short summary" of the paper, the Wikipedia article on Automatic Differentiation may be helpful). I had a few questions about how they defined their "memory space of the program". The relevant section is below:

We will model computer programs as maps on a vector space. If we only focus on the real valued variables (of type float or double), the state of the virtual memory can be seen as a high dimensional vector. A set of all the possible states of the program’s memory, can be modeled by a finite dimensional real vector space $\mathcal{V} \equiv \mathbb{R}^n$. We will call $\mathcal{V}$ the memory space of the program. The effect of a computer program on its memory space $\mathcal{V}$, can be described by a map $$P : \mathcal{V} \to \mathcal{V}$$ A programming space is a space of maps $\mathcal{V} \to \mathcal{V}$ that can be implemented as a program in specific programming language.

I understand how $\mathcal{V}$ should be some finite object - I don't understand why this should specifically be a vector space. One analogy that may be useful for this is the following. $C(\mathbb{R})$ denotes the set of all continuous functions $f:\mathbb{R}\to\mathbb{R}$. While continuous functions themselves aren't linear, we can define addition of continuous functions and scalar multiplication of continuous functions in a linear way by defining: $$(f+g)(x) \stackrel{def}{=} f(x) + g(x)$$ $$k\cdot f(x) \stackrel{def}{=} (kf(x))$$ Something similar to this undoubtedly works for programs on $\mathcal{V}$ - for a given state $s$, define $p_1 + p_2$ evaluated on $s$ as $p_1(s) + p_2(s)$. While this (likely) leaves us with a Banach space, I'm unsure if it's the correct interpretation.

This would give us that the sum of two programs $p_1,p_2$ applied to some state $s$ is just $p_1(s) + p_2(s)$. So, looking at a single component of $p_1(s) + p_2(s)$, we have that the action of $p_1 + p_2$, as a program, is just the sum of the individual actions of $p_1$ and $p_2$ on the initial state. This seems like an odd interpretation for me - for whatever reason it'd seem much more natural to have the way to combine programs to be function composition, but this would lead to problems like $+$ not being commutative, and scalar multiplication being harder to define.

In this paper, what's the correct interpretation of addition here? The "usual" addition seems to lead to the correct mathematical construct, but I'm having a hard time understanding what the "program sum" is supposed to model in real life.

Edit: This Reddit Post seems to have some commentary on it which may help others.

Improve this question
$\endgroup$
5
  • $\begingroup$ I know essentially nothing about this except seeing it mentioned in one or two talks. But my impression is that you essentially ignore precision and other finer details and treat a program as a black box that takes real numbers as input and outputs real numbers. So $n$ is an upper bound on the total number of input/output variables and $\mathcal{V}$ is an $n$-dimensional real vector space. $\endgroup$
    – Sasho Nikolov
    May 2, 2017 at 22:00
  • $\begingroup$ @SashoNikolov after thinking about this more, I'm closer to understanding it. My issue is that defining $p_1 + p_2$ as $(p_1 + p_2)(x) = p_1(x) + p_2(x)$ for $x\in\mathcal{V}$ would be the "standard" way to proceed mathematically, but for some reason this seems like an odd choice of how to combine programs to me (potentially due to me seeing $p_1 \circ p_2$ to be more natural, essentially just piping output to input, but this probably doesn't give the vector space structure wanted). $\endgroup$
    – Mark
    May 2, 2017 at 22:05
  • 1
    $\begingroup$ Assuming $p_1$ and $p_2$ are programs/maps, I see no contradiction here. The product of maps $p_1p_2$ is given by composition, and the sum is what you write in your comment. I.e. programs have more structure than a vector space: they form an associative algebra. $\endgroup$
    – Sasho Nikolov
    May 3, 2017 at 0:07
  • $\begingroup$ @SashoNikolov In this case, is there any nice interpretation of what $p_1 + p_2$ is? Composition has an especially nice interpretation problematically as piping things, but I'm having issues finding a suitable interpretation for $p_1 + p_2$ besides "doing two things concurrently and independently from the same initial state, and combining the results". Is this a good way of thinking about it? $\endgroup$
    – Mark
    May 3, 2017 at 0:19
  • 1
    $\begingroup$ We studied this when it came out, they construct a calculus for deep learning. It addresses the shortcomings of purely functional programming (in this frame) by introducing vector spaces and algebra, but it requires a bit different view on programs. Very general results are derived using it. You could write to the authors like we did, they replied. $\endgroup$
    – LeastSquaresWonderer
    May 4, 2017 at 12:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.