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.

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.

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 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?

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?

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.

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.

@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/.

@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.

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?

@Ivan Reese maybe https://github.com/tidalcycles/Tidal could be of some inspiration https://slab.org/tmp/p63.pdf

Finally got a straight answer about this — yeowzers! https://twitter.com/conal/status/1144005285284995072

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.

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)

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.

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.

Yeah, I'm not so sure real numbers exist. A continuum? Sure. But individual points all along it? Not so sure.

@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

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

@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 for a start. (While we're on this tangent, I also don't believe in the Axiom of Choice for what it's worth.)

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).

@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.