Title
#thinking-together
i

Ivan Reese

06/26/2019, 2:36 AM
I'm really struggling with Conal's FRP ā€” building systems as compositions of continuous functions ā€” functions that take and return real (that is: infinitely precise) numbers. I'm building a visual programming language where the semantics of the language depend on the measurements of the lengths of lines. The language is live, and reflective (in that code can be self-modifying), and allows for evaluation both forward and backward in time. Determinism is very important. In this Twitter thread, I outline a problem ā€” https://twitter.com/spiralganglion/status/1143704642997506049 ā€” How can I compare the lengths of lines, deterministically, without resorting to discrete values? If I use some sort of alternative representation (eg: a function that, when evaluated, produces a value for comparison), how do I do it without running smack into the halting problem? I'd love it if folks could weigh-in on this.
w

wtaysom

06/26/2019, 4:24 AM
Provocative. Avoid halting problems (and general computational trouble) by having a good idea about how computations bottom out. If two things can influence each other, how (and how quickly) does the "vibrating" stop. Dampening and imprecision are friends.
4:25 AM
Another escape valve is to allow time to step forward while things are still converging.
4:28 AM
And there's the rule of thumb that if function isn't easy to evaluate, then some variation is certainly intractable.
4:28 AM
In short: cheat to win!
shalabh

shalabh

06/26/2019, 4:30 AM
Python's sympy might be of interest as well.
>>> 2 * sympy.sqrt(2)
2*sqrt(2)
>>> 2 * sympy.sqrt(2) == sympy.sqrt(8)
True
It appears to keep the symbolic expressions in some normal form so it can do equality checks when the same irrational is computed differently (at least in the above case)
i

Ivan Reese

06/26/2019, 4:39 AM
I should clarify: I don't know a priori how these lines will be represented. They might be bezier curves. They might be b-splines. They might ā€” though I kinda doubt this ā€” be derivatives, or some other non closed-form expression that can't be evaluated finitely. So if I'm going to represent them using constructible reals, or some other constructible representation, I would want it to be able to subject to the same sorts of manipulation as regular old numbers. And that might be impossible! If so, I'm curious to learn what the limit is. Which lattice, which ring, which semigroup, which manifold, which orbifold (throwing out mostly inappropriate math terms at this point for comedic effect).. encompasses the viable solution space? And that might be impractical! If so, how the fuck are we programmers expected to actually implement FRP for things that go beyond "I made some JPGs spin in circles" and actually approximate the complexity of a modern video game?
5:09 AM
@wtaysom Everything I'm doing should, in theory, be closed-form (and very fast to compute). Fingers crossed. But if someone extends my language to do something that needs time or help to converge, that's on them.
5:13 AM
Unless someone comes through with a real zinger of a solution to this quandary, my plan is to just embrace integers, representing time using (say) nanoseconds and space using (say) nanopixels. In theory, all the code I'm writing should be functional enough to allow me to switch to a more precise representation at any time, and possibly to switch to an alternative (eg: constructive) representation if one of them offers a broad enough algebra that it satisfies all my needs. But, then, that of course means that FRP is infeasible... which is a real kick to the stomach, hey?
w

wtaysom

06/26/2019, 5:38 AM
The way to represent time depends on what kind of interactions you have. For instance, sometimes continuous time works well between discrete collisions. And when there is nothing like a collision or a three body problem, you get nice closed forms for how a system evolves. Curves can intersect in curious ways: would linear approximation be appropriate for your task?
i

Ivan Reese

06/26/2019, 5:58 AM
sometimes continuous time works well between discrete collisions
Yeah, that's exactly what I'm planning to do ā€” if I suck and end up using discrete representations of time and space, I'll interpolate so as to recover some measure of continuity, which will be perfectly lossless when away from collision events (thanks for nothing, Nyquist!). As for linear approximations ā€” totally, yes, that's pretty much my only option for working with them in bounded time, as far as I'm aware, unless there's some fast implementation of constructible numbers Conal is withholding from us.
j

Joshua Horowitz

06/26/2019, 8:26 AM
One bit of prior art to look into is CGAL. CGAL is a computational geometry library which provides algorithms for convex hulls, boolean operations on polygons, etc. (That's an extremely large 'etc'.) CGAL can represent the output of all of its geometric constructions exactly ā€“ you can intersect circles and lines and all that without ever losing precision. (Note that I said "CAN represent". One fascinating thing about CGAL is that all of its algorithms are defined in terms of abstract "kernels", which say how to perform various primitive operations. You can plug in different kernels, which represent geometric primitives in different ways and which correspondingly have different properties. There's one kernel which says "just treat points as pairs of floats", and that kernel is absolutely not exact. But then there's other kernels which do various tricks with interval arithmetic or lazily-computed symbolic trees, and those can give you exact results.) It's a ridiculously sophisticated system! If you're dead-set on exact computation, it might be worth looking into.
w

wtaysom

06/26/2019, 9:44 AM
@Joshua Horowitz oh CGAL! Had some good times with it doing "quadratic programming" (find the shortest weighted distance subject to linear constraints). Broke it hard, now I'm wedded to Gurobi http://www.gurobi.com/.
Konrad Hinsen

Konrad Hinsen

06/26/2019, 2:44 PM
@Ivan Reese You don't say much about how your lines are defined. If it's always two Cartesian points, and if the concrete values of these points are always rational numbers (e.g. via a constraint on the inputs), then you can just compare the squares of the lengths and never need more than rational arithmetic. Computable numbers (a more common term than "constructable" in my opinion) may also be a practical solution, depending on what exactly you need to do. In general, both memory and CPU requirements are unbounded if your inputs can be arbitrary (but then that's true for rational numbers as well). But if precision requirements are modest in practice even if not in theory, there might be no problem in practice either. However, computable numbers are tricky in other respects. For example, equality is not computable (intuitively, it takes forever to compare infinitely many digits). That makes comparisons a bit of a challenge.
i

Ivan Reese

06/26/2019, 3:44 PM
Hi Konrad ā€” yep, it seems we're on the same page. ā€¢ My lines are currently defined as arbitrary degree Bezier curves computed from rational-valued Cartesian points. I believe I can do most calculations on these deterministically ā€” eg: comparing squared lengths ā€” but maybe not intersections, nor other non closed-form operations. ā€¢ These lines might eventually be specified using other formulations, like NURBS, or finite segments of plots of symbolic expressions. ā€¢ I do need to be able to order these lines by length (and the length might come as the result of an intersection or other non closed-form expression), and I need to be able to determine if lines have equal length (so that I know when to resolve the ambiguity of ordering using a deterministic tiebreaker). ā€¢ I need to be able to do this hundreds of thousands of times per second, without stutter, which probably means I can't use any approach that requires integration of intermediate values. (Integration of final values is probably fine, because I can converge those across time, as @wtaysom suggested.) ā€¢ In practice, my precision requirements are very modest ā€” but I require strict determinism. When ordering these lines by length, the ordering must be perfectly stable in all cases. When push comes to shove, I'm willing to sacrifice basically all my precision / numerical correctness in order to preserve determinism. Yes, I will multiply all intermediate values by a large constant integer factor and truncate decimals if I have to. ā€¢ But accepting any degree of imprecision / incorrectness means I'm not doing FRP. ...and... if you can't do FRP with even relative common occurrences in realtime computer graphics, like intersecting lines... then what are we to make of it?
4:01 PM
@shalabh Exploring outward from SymPy, I found http://algebrite.org and https://mathjs.org. (Yes, I'm trying to do this in JS. Kill me.) There might be something here. Being able to do all my math in an intermediate symbolic form ā€” by restricting what sorts of operations are permitted to only those that can be handled quickly and exactly ā€” might just be the perfect determinism + Reals holy grail.
4:07 PM
It'll depend on how complex those symbolic forms get as time goes by. If in practice they can regularly be collapsed down to exact integer values or simplified forms, that won't be so bad. But if I need to calculate the position of a particle on a complicated path that ends in a loop.. I can picture the symbolic form just accreting terms and growing unbounded as time progresses.
jarm

jarm

06/26/2019, 6:01 PM
@Ivan Reese maybe https://github.com/tidalcycles/Tidal could be of some inspiration https://slab.org/tmp/p63.pdf
i

Ivan Reese

06/26/2019, 11:07 PM
Finally got a straight answer about this ā€” yeowzers! https://twitter.com/conal/status/1144005285284995072
12:27 AM
@jarm Yeah, it seems Tidal stores times as rationals and not floats. That is 100% the direction I'm leaning toward ā€” using all my best tricks to avoid floats at all costs and doing everything in a way that preserves precision in intermediate values. That, of course, means not using the JS-provided trig functions, and not implementing algorithms that depend on sqrt, etc. Not impossible, but certainly not straightforward for an I just make indie games person like myself.
12:36 AM
@Joshua Horowitz That reference is fantastic. I'd never heard of this tool, but it sounds like they designed it to solve exactly the problem I'm facing. The writeup [https://www.cgal.org/exact.html] is a better articulation of my pain that I've yet been able to put together myself. I don't think their escape hatch (arbitrary precision) is appropriate for my needs ā€” I need to set tight execution time limits, and if I'm going to be cutting things off I might as well just use well-chosen finite numeric representations at all times. But I so love that they've approached the problem with this perspective:
The second and deeper problem is that numerical weapons are per se less effective in geometric computing than they are in other fields. In geometry, we don't compute numbers but structures: convex hulls, triangulations, etc. In building these structures, the underlying algorithms ask questions like "is a point to the left, to the right, or on the line through two other points?" Such questions have no answers that are "slightly off". Either you get it right, or you don't. And if you don't, the algorithm might go completely astray. Even the most fancy roundoff control techniques don't help here: it's primarily a combinatorial problem, not a numerical one.
We concentrate on the geometry (after all, that's what we do best), and the CGAL algorithms themselves don't contain any numerical security measures to keep them from going astray.
That's perfect. And I think I can do just as well by restricting my domain to things that are simple, cleanly representable, and closed-form. Fingers crossed!
d

Doug Moen

06/27/2019, 1:02 PM
That CGAL reference explains why constructive reals are not the answer. It's because you can't compare two constructive reals x and y and determine if x < y, x == y or x > y (this is equivalent to solving the halting problem). You can only get an approximate answer, that might be wrong, which isn't good enough for making CGAL-style geometric constructions.
1:33 PM
I have a related problem (geometry vs floating point numbers) in my Curv project. Curv is a 3D modelling language. If I use a boundary representation for 3D objects (like a triangle mesh, or a spline surface), then CSG operations (union, intersection, etc) become intractable, if coordinates are floating point numbers. Curv makes heavy use of trigonometric and exponential functions (sin, sqrt, etc), and I want fast updates for live programming, so it's hard to avoid floating point. My solution was to switch from an explicit, or boundary representation (where you store coordinates of points on the surface of the shape) to an implicit, or signed distance field (SDF) representation. An SDF represents a shape as a function that maps an arbitrary point P in 3-space onto the distance from that point to the closest surface on the shape. The result is positive if P is outside the shape, 0 if P is on the boundary, or negative if P is inside. With this change in representation, the CSG operations become trivial, and the numeric instabilities that CGAL warns of go away. I'm using a small piece of Conal Elliot's continuous-time FRP in Curv, and I'm interested in extending that to support a more general notion of interactive animations that are defined using FRP. I am hoping that my trick of flipping the representation of shapes (from explicit to implicit) will continue to be helpful in making FRP work in my system.
2:01 PM
In Curv, a 3D shape is a continuous function of space: it's a function f : (x,y,z) -> signed_distance. An animated shape is a continuous function of space/time: f : (x,y,z,t) -> signed_distance. In Elliot's Functional Reactive Animation paper, a Behaviour is a continuous function of time. So Curv and FRP use the same implicit representation of time, and in Curv, space and time are treated the same way. I'm hoping that this correspondence will help when I later extend Curv to support a larger subset of FRP.
d

Deklan Webster

06/27/2019, 3:14 PM
One potentially useful search would be "exact real arithmetic geometry". E.g. https://icfp18.sigplan.org/details/npfl-2018-papers/5/Exact-Real-Arithmetic-for-Geometric-Operations Although, I think that CGAL is the most practical solution (that I've seen at least)
3:14 PM
This challenge by Conal is kinda strange https://twitter.com/conal/status/1143690906454777856
3:16 PM
unless I'm missing something, it's mostly who, not what: Chaitin. Do a computation to a given accuracy with a non-computable number. Or, worse, do a computation with a non-limit-computable number
d

Doug Moen

06/27/2019, 4:31 PM
The problem with reals goes farther back, to Hilbert. There an uncountable infinity of real numbers, far more than the countable infinity of the integers or rationals. The "constructive reals" is the largest subset of the real number line for which it is even theoretically possible to represent on a computer or even on an ideal Turing machine with infinite memory.
Konrad Hinsen

Konrad Hinsen

06/27/2019, 4:52 PM
One more idea: there's a set of numbers larger than the rationals but smaller than computable numbers: the set of algebraic numbers. I have vague memories of people using this set for computations, but no details. For geometry, that might be a good fit.
w

wtaysom

06/27/2019, 4:58 PM
Yeah, I'm not so sure real numbers exist. A continuum? Sure. But individual points all along it? Not so sure.
d

Doug Moen

06/27/2019, 5:26 PM
@wtaysom if you take the position that the only real numbers that exist are the ones that, in principle, can be computed by an algorithm, then those are the constructive reals, and you are a constructive mathematician. The much larger set of nonconstructive reals have no relevance to computer science, or physics, or anything else that is "real", so it's hard to take them seriously if you aren't really deep into theoretical math. If you take them seriously, you get things like chaitins number, which is either really cool, or its a number that doesn't exist
d

Deklan Webster

06/27/2019, 5:31 PM
Konrad, I was actually just wondering earlier if there's a set which is larger than the algebraics but smaller than the computables which might have nicer properties. In any case, as Doug points out, you can take computable reals seriously and develop constructive analysis, etc. It's very interesting. Idk what set of numbers Conal wants is, but I'm fairly sure it's not the reals
w

wtaysom

06/27/2019, 6:43 PM
@Doug Moen guilty as charged. I feel that "real" numbers are just a lazy way of saying that a continuum is full of "stuff." What's less lazy? Well, showing the a countable set of points has measure zero

https://www.youtube.com/watch?v=cyW5z-M2yzwā–¾

for a start. (While we're on this tangent, I also don't believe in the Axiom of Choice for what it's worth.)
shalabh

shalabh

06/27/2019, 8:25 PM
Just sharing a naive idea that came to mind which might be useful in practice. 1. Don't track points, only track intervals. So every point is in represented as a circle, line is a band etc. - it's fuzzy. You can compute 'to the left of' correctly when there is no overlap, but in overlap cases it's not known until the system calculates some more precision. 2. Represent imprecision in the UI (e.g. orange glow instead of an intersection point). Then when the user 'zooms in' to the intersection it computes more precision (~reduce the circle radius). This exposes the imprecision to the user and outsources the halting problem. Exact points can still be represented as circles with radius=0 and the null symbolic expression. Inexact points are represented as (center, radius, symbolic_expression_to_evaluate_more_precision).
8:29 PM
(is this cgal?)
d

Doug Moen

06/27/2019, 9:38 PM
@shalabh CGAL uses simple algorithms that assume exact arithmetic. In my experience of the CGAL CSG operators, you need to tell CGAL to use rational numbers. If you tell it to use floating point numbers, then you'll get garbage output for some good inputs. Even with these simplifying assumptions, the code for CSG operations is extremely complex, and can only be written by experts.