inverse function
in [Lisp]
|
From: Kyle M on 15 Feb 2010 08:56 On Feb 13, 12:27 pm, Taoufik <taou...(a)mazeboard.com> wrote: > Dear, > > Does someone know if there is any work done to generate an inverse of > any given lisp function (if possible). > > Example: > > > (defun f (x) (+ x 1)) > > (f 2) > 3 > > (funcall (inverse #'f) 3) > 2 > > (funcall (inverse #'f) (f 5)) > > 5 > > When a lisp function has conditional branchs then the inverse function > will > have a code to test both paths (eg. choice and fail constructs). > > This example is very simple and serves only to describe my needs; I > would like to use the inverse function > for complex lisp defined functions. > > Thank you for your help Easy! Just guess randomly until you get it right. (defun invert (f guess) (lambda (x) (loop for y = (funcall guess) when (= x (funcall f y)) return y))) (defun my-guess () (random 1000)) > (funcall (invert (lambda (x) (+ 1 x)) #'my-guess) 100) 99 Kyle
From: Norbert_Paul on 15 Feb 2010 09:10 A good (though not easy to use) library for solving linear equation systems is LAPACK. It originally is coded in FORTRAN. I (still) use the Java port but I even found a LISP port in the maxima source tree: http://sage.math.washington.edu/home/wstein/tmp/maxima-5.16.3.p2/src/share/lapack/ Norbert Harald Hanche-Olsen wrote: > + Taoufik <taoufik(a)mazeboard.com>: > >> Does someone know if there is any work done to generate an inverse of >> any given lisp function (if possible). > > As must be clear from the answers so far, it is impossible in general. > However, for specialized problem domains, such as linear algebra, > something likt it is not only possible but frequently desirable. For one > example, consider Knuth's metafont, which is a program to define fonts > for use in typesetting. It contains a fairly general facility for doing > linear algebra. You just give it linear equations involving a number of > variables, and once enough equations have been given to fix the value of > some variable, that variable can now be used freely. This facility is > amazingly useful when creating graphics, and it might be a fun as well > as useful exercise to implement such a library in lisp. I often miss > something like this when using other graphics packages. One thing you > wouldn't do, though, is to structure this around DEFUNs defining linear > algebra. The whole style is declarative more than imperative, and it > requires primitives to match that style. (BTW, there is a graphics > drawing program called metapost which is based on the metafont language > but which produces postscript output.) >
From: Norbert_Paul on 15 Feb 2010 09:38 I suppose that even your "(if possible)" restriction is untractable: Assume a unary function #'uninvertible, where inversion is impossible, existed and assume a predicate #'if-possible-p (where "if" stamds for "Inversion of Function"). Then do (defun mean-function (x) (if (if-possible-p #'mean-function) (uninvertable x) (identity x) ) ) So when #'if-possible-p says that #'mean-function is invertable then it is not (as it behaves identically to #'uninvertable) and vice versa (as then it behaves like the invertible function #'identity. So #'if-possible-p at least errs with #'mean-function. With a similar argument, I guess, you can demonstrate the existance of such an uninvertable function. Maybe even an uninvertable bijection exists. I didn't yet care about that. So, anyway, you must restrict yourself to an incomplete set of /explicitly declared/ invertible functions, maybe registered in a hash table. You might then also define a macro like (definvertable fun (x) <body> <inverse-body> ) Note that 'invertability depends on arity and domain of the function. A unary #'+ ( +: T -> T) is invertible, whereas a binary #'+ (or +:T^2 -> T ) is not. Also #'not is invertible if applied to {nil, T} only. #'list and #'cons are invertible, if you consider the argument list one argument and are satisfied with #'equal results. Then there may also be rules which tell what combinations of invertible functions themselves yield invertible function. For example composition of invertible functions is invertible. I strongly suppose that this set of rules also will always be incomplete. Norbert. Taoufik wrote: > Dear, > > Does someone know if there is any work done to generate an inverse of > any given lisp function (if possible). > > Example: > >> (defun f (x) (+ x 1)) >> (f 2) > 3 >> (funcall (inverse #'f) 3) > 2 >> (funcall (inverse #'f) (f 5)) > 5 > > When a lisp function has conditional branchs then the inverse function > will > have a code to test both paths (eg. choice and fail constructs). > > This example is very simple and serves only to describe my needs; I > would like to use the inverse function > for complex lisp defined functions. > > Thank you for your help
From: Norbert_Paul on 15 Feb 2010 09:53 I suppose that even your "(if possible)" restriction is untractable: Assume a unary function #'uninvertible, where inversion is impossible, existed and assume a predicate #'if-possible-p (where "if" stamds for "Inversion of Function"). Then do (defun mean-function (x) (if (if-possible-p #'mean-function) (uninvertable x) (identity x) ) ) So when #'if-possible-p says that #'mean-function is invertable then it is not (as it behaves identically to #'uninvertable) and vice versa (as then it behaves like the invertible function #'identity. So #'if-possible-p at least errs with #'mean-function. With a similar argument, I guess, you can demonstrate the existance of such an uninvertable function. So, anyway, you must restrict yourself to an incomplete set of /explicitly declared/ invertible functions, maybe registered in a hash table. You might then also define a macro like (definvertable fun (x) <body> <inverse-body> ) Note that 'invertability depends on arity and domain of the function. A unary #'+ ( +: T -> T) is invertible, whereas a binary #'+ (or +:T^2 -> T ) is not. Also #'not is invertible if applied to {nil, T} only. #'list and #'cons are invertible, if you consider the argument list one argument and are satisfied with #'equal results. Then there may also be rules which tell what combinations of invertible functions themselves yield invertible function. For example composition of invertible functions is invertible. I strongly suppose that this set of rules also will always be incomplete. Norbert. Taoufik wrote: > Dear, > > Does someone know if there is any work done to generate an inverse of > any given lisp function (if possible). > > Example: > >> (defun f (x) (+ x 1)) >> (f 2) > 3 >> (funcall (inverse #'f) 3) > 2 >> (funcall (inverse #'f) (f 5)) > 5 > > When a lisp function has conditional branchs then the inverse function > will > have a code to test both paths (eg. choice and fail constructs). > > This example is very simple and serves only to describe my needs; I > would like to use the inverse function > for complex lisp defined functions. > > Thank you for your help
From: Mark Tarver on 16 Feb 2010 08:38
On 13 Feb, 17:27, Taoufik <taou...(a)mazeboard.com> wrote: > Dear, > > Does someone know if there is any work done to generate an inverse of > any given lisp function (if possible). > > Example: > > > (defun f (x) (+ x 1)) > > (f 2) > 3 > > (funcall (inverse #'f) 3) > 2 > > (funcall (inverse #'f) (f 5)) > > 5 > > When a lisp function has conditional branchs then the inverse function > will > have a code to test both paths (eg. choice and fail constructs). > > This example is very simple and serves only to describe my needs; I > would like to use the inverse function > for complex lisp defined functions. > > Thank you for your help This kind of thing is much more tractable in Prolog where f(x) = y is represented as a dyadic predicate f(X,Y). In theory one can run this in either direction using either X or Y as the output variable. It would be possible to build a Lisp interpreter in Prolog which could be 'run backwards' as it were. In the case of many-one functions multiple values could be returned. In practice though, there are three problems with doing this even in Prolog. The first is that most Prolog programs are not pure Horn clauses but use the arithmetic engine and this is very directional. So you have to limit yourself to pure Prolog and use the successor notation for arithmetic. Second, multiple values may in certain cases be infinite. Third, even in pure Prolog there are programs that cannot be 'run backward' without engendering an infinite regress. an example of this is the naive reverse program in Prolog. Often this is a result of the incomplete search strategy of Prolog so you have to build a loop detector into your Prolog which traps some of these loops. This is called a subsumption test. It's a nice exercise to experiment with representing functional programming in logic programming and will probably teach you a lot about the limits of computing inverses. Mark |