4 ms·

Ask HN: Reversible function definitions

5 points by posterboy 9y ago

What do computer scientists call a function that allows inference of transformations between two data types from a single definition, and does any language support this and explicit calls or implicit conversions? function convert (rad_t) phi = pi/180 * (deg_t) phi rad_t alpha = convert((deg_t) 45) //explicit deg_t beta = pi/4 + alpha //implicit rad_t and deg_t might be together in a typeclass archs or sumsuch. disc.: I can't reach stackoverflow, so I'm posting here.

bjourne 9y ago
There are Python packages that do what you want (units and numericalunits), but they aren't used much presumably due to the overhead they bring. You might also be interested in Prolog which feature what is, essentially, invertible functions. E.g: convert(Deg, Rad) :- nonvar(Deg), Rad is Deg * pi / 180. convert(Deg, Rad) :- nonvar(Rad), Deg is Rad * 180 / pi. In this case, it doesn't work well because of floating point math, but it works well for functions manipulating lists. The Factor language also feature function inversion in an addon: http://docs.factorcode.org/content/article-inverse%2Cintro.html http://docs.factorcode.org/content/article-inverse%2Cintro.h... Afaik, figuring out what functions in general are invertible is an unsolved problem in computer science.
miguelrochefort 9y ago
They're call isomorphic functions. Recently, I've been thinking a lot about them and also have been looking for a language/framework that supports them. What would be very interesting is a way to inverse non-isomorphic functions and get a constrained set of possible values (i.e., the reverse of age(birth, now) would return a range of date for either birth or now). Often, the complete value is not necessary and you're only interested in some subset of it (i.e., that a person's age is greater than 18).
- zmonx 9y ago
  It is true: An isomorphic function admits an inverse function. However, what you are describing in the second paragraph is a generalization of functions: You are now reasoning in terms of relations, where a single entity can be related to one or more others. Hence, a programming language that reasons in terms of relations (not functions) seems very appropriate for your use case. Logic programming is a such a natural generalization of functional programming. For example, if you want to reason flexibly over dates and times, check out Prolog and its finite domain constraints. Michael Hendricks has implemented a great library for this, called library(julian): http://mndrix.github.io/julian/ http://mndrix.github.io/julian/ This library lets you reason in terms of ranges and other constraints to describe general relations between dates and times.
zmonx 9y ago
There is a natural generalization of functions, called relations. To benefit from relations, have a look at a logic programming language such as Prolog. In Prolog, relations are defined by predicates and constitute the basic building blocks of all Prolog programs. A predicate is indeed sometimes called "reversible" if it can also be used in a direction that seems somewhat unexpected at first. For example, the predicate length/2 can be used to both compute the length of a list and generate a list of a given length. However, a predicate should ideally not only be "reversible", but indeed completely general. This means that we should also be able to ask: Which solutions are there at all? This is a query where nothing is given, and the Prolog system must find solutions on its own. Indeed, length/2 also satisfies this criterion. We can ask for example: ?- length(Ls, L). Ls = [], L = 0 ; Ls = [_2168], L = 1 ; Ls = [_2168, _2174], L = 2 ; etc. and the Prolog system generates as many lists (and their lengths) as we want. So, calling such predicates "reversible" still does not do justice to what they actually are, namely completely general relations that work in all directions. Therefore, when programming in Prolog, do not fall into the trap of calling your predicates "reversible" or "usable in the other direction" is if there were only one such other direction. Instead, think in terms of relations between entities, and use language features that allow such general reasoning. For instance, let us consider your concrete example. Using Prolog and its CLP(R) constraints, we can very generally describe the relation between floating point numbers. CLP(R) is for example available in SICStus Prolog and also a few other systems: :- use_module(library(clpr)). pi(Pi) :- Pi is 4*atan(1). rad_deg(Rad, Deg) :- pi(Pi), { Rad = Pi / 180 * Deg }. Now the point: rad_deg/2 is a general relation and can be used in all directions. For example, it can be used to compute the first argument if only the second is known: ?- rad_deg(Alpha, 45). Alpha = 0.7853981633974483 . Conversely, it can be used to compute the second argument if only the first is known: ?- rad_deg(0.7853981633974483, Beta). Beta = 45.0 . Here is your slightly more complex example, which is also an instance of computing the second argument: ?- pi(Pi), rad_deg(Alpha0, 45), { Alpha = Pi/4 + Alpha0 }, rad_deg(Alpha, Beta). ..., Beta = 90.0 . But it does not stop there! The relation can also be used in the most general way to answer: Which solutions are there at all? ?- rad_deg(R, D). {D=57.29577951308232*R}. In this case, it provides an answer that expresses the general relation between the two arguments even though none of them are known. And it still doesn't stop there! The relation can also be used to ask: Does the relation hold between two given numbers? ?- rad_deg(0, 0). true. If the relation doesn't hold between two given floating point numbers, the system tells us: ?- rad_deg(0, 1). false. So, this is a true relation between floating point numbers, usable in all directions! Caveat: Floating point numbers are an extremely bad way to represent numbers, and I can only advice to use better representations instead. For example, Unum computing looks very promising. In Prolog, consider using rational numbers, available via CLP(Q). Declarative reasoning over integers is available via CLP(FD) constraints. All these systems let you implement general relations between numeric expressions.

5 points by posterboy 9y ago

bjourne 9y ago

There are Python packages that do what you want (units and numericalunits), but they aren't used much presumably due to the overhead they bring. You might also be interested in Prolog which feature what is, essentially, invertible functions. E.g: convert(Deg, Rad) :- nonvar(Deg), Rad is Deg * pi / 180. convert(Deg, Rad) :- nonvar(Rad), Deg is Rad * 180 / pi. In this case, it doesn't work well because of floating point math, but it works well for functions manipulating lists. The Factor language also feature function inversion in an addon: http://docs.factorcode.org/content/article-inverse%2Cintro.html http://docs.factorcode.org/content/article-inverse%2Cintro.h... Afaik, figuring out what functions in general are invertible is an unsolved problem in computer science.

miguelrochefort 9y ago

They're call isomorphic functions. Recently, I've been thinking a lot about them and also have been looking for a language/framework that supports them. What would be very interesting is a way to inverse non-isomorphic functions and get a constrained set of possible values (i.e., the reverse of age(birth, now) would return a range of date for either birth or now). Often, the complete value is not necessary and you're only interested in some subset of it (i.e., that a person's age is greater than 18).

zmonx 9y ago
It is true: An isomorphic function admits an inverse function. However, what you are describing in the second paragraph is a generalization of functions: You are now reasoning in terms of relations, where a single entity can be related to one or more others. Hence, a programming language that reasons in terms of relations (not functions) seems very appropriate for your use case. Logic programming is a such a natural generalization of functional programming. For example, if you want to reason flexibly over dates and times, check out Prolog and its finite domain constraints. Michael Hendricks has implemented a great library for this, called library(julian): http://mndrix.github.io/julian/ http://mndrix.github.io/julian/ This library lets you reason in terms of ranges and other constraints to describe general relations between dates and times.

zmonx 9y ago

There is a natural generalization of functions, called relations. To benefit from relations, have a look at a logic programming language such as Prolog. In Prolog, relations are defined by predicates and constitute the basic building blocks of all Prolog programs. A predicate is indeed sometimes called "reversible" if it can also be used in a direction that seems somewhat unexpected at first. For example, the predicate length/2 can be used to both compute the length of a list and generate a list of a given length. However, a predicate should ideally not only be "reversible", but indeed completely general. This means that we should also be able to ask: Which solutions are there at all? This is a query where nothing is given, and the Prolog system must find solutions on its own. Indeed, length/2 also satisfies this criterion. We can ask for example: ?- length(Ls, L). Ls = [], L = 0 ; Ls = [_2168], L = 1 ; Ls = [_2168, _2174], L = 2 ; etc. and the Prolog system generates as many lists (and their lengths) as we want. So, calling such predicates "reversible" still does not do justice to what they actually are, namely completely general relations that work in all directions. Therefore, when programming in Prolog, do not fall into the trap of calling your predicates "reversible" or "usable in the other direction" is if there were only one such other direction. Instead, think in terms of relations between entities, and use language features that allow such general reasoning. For instance, let us consider your concrete example. Using Prolog and its CLP(R) constraints, we can very generally describe the relation between floating point numbers. CLP(R) is for example available in SICStus Prolog and also a few other systems: :- use_module(library(clpr)). pi(Pi) :- Pi is 4*atan(1). rad_deg(Rad, Deg) :- pi(Pi), { Rad = Pi / 180 * Deg }. Now the point: rad_deg/2 is a general relation and can be used in all directions. For example, it can be used to compute the first argument if only the second is known: ?- rad_deg(Alpha, 45). Alpha = 0.7853981633974483 . Conversely, it can be used to compute the second argument if only the first is known: ?- rad_deg(0.7853981633974483, Beta). Beta = 45.0 . Here is your slightly more complex example, which is also an instance of computing the second argument: ?- pi(Pi), rad_deg(Alpha0, 45), { Alpha = Pi/4 + Alpha0 }, rad_deg(Alpha, Beta). ..., Beta = 90.0 . But it does not stop there! The relation can also be used in the most general way to answer: Which solutions are there at all? ?- rad_deg(R, D). {D=57.29577951308232*R}. In this case, it provides an answer that expresses the general relation between the two arguments even though none of them are known. And it still doesn't stop there! The relation can also be used to ask: Does the relation hold between two given numbers? ?- rad_deg(0, 0). true. If the relation doesn't hold between two given floating point numbers, the system tells us: ?- rad_deg(0, 1). false. So, this is a true relation between floating point numbers, usable in all directions! Caveat: Floating point numbers are an extremely bad way to represent numbers, and I can only advice to use better representations instead. For example, Unum computing looks very promising. In Prolog, consider using rational numbers, available via CLP(Q). Declarative reasoning over integers is available via CLP(FD) constraints. All these systems let you implement general relations between numeric expressions.