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

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

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 collisionsYeah, 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 (

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

Konrad Hinsen

06/26/2019, 2:44 PM

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

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

06/26/2019, 6:01 PM

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

12:36 AM

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

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

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

6:33 PM

Found the answer: no https://www.wikiwand.com/en/Richardson%27s_theorem

w

wtaysom

06/27/2019, 6:43 PM

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

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

View count: 3

Join thread in Slack