inverse function [Lisp]

Prev: Lisp and ncurses
Next: new version of emacs's command frequency report

From: Taoufik on 13 Feb 2010 12:27

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: Tim Bradshaw on 13 Feb 2010 12:40

On 2010-02-13 17:27:43 +0000, Taoufik said:

> Does someone know if there is any work done to generate an inverse of
> any given lisp function (if possible).

Inverses only exist for functions which are 1-1 (is this an injection?
I think it is). So many functions do not have them. Even for those
that do, computing the inverse based on the definition is probably
intractable in general.

From: Pascal J. Bourguignon on 13 Feb 2010 13:58

From: Nicolas Neuss on 14 Feb 2010 05:24

Taoufik <taoufik(a)mazeboard.com> writes:

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

When I suggested you on the OpenMCL mailing list to go to comp.lang.lisp
with this question it was not that I thought you were answered
inappropriate there. In fact, the same people answering you there would
have answered you probably here as well. It was because I think that it
is worthwile and amusing to think also about such things and
comp.lang.lisp is a broader audience.

Nice answers have been given what you could do with such a function, Ron
Garret showing that you could decrypt RSA, Robert Goldman mentioned that
you would have solved the halting problem, Pascal Bourguignon showed
that the answer could easily be an infinite set, rather obviously it
could also solve every problem of number theory (e.g. for Fermat's last
problem set f(a,b,c,n)=c^n-a^n-b^n and ask for those (a,b,c,n) in
f^{-1}(0)=0 where
n>2.)

I liked Tobias Rittweiler's answer best. Below is my variation of it
which satisfies the requirements you pose above (although it is probably
not what you want:-) with only slightly modified syntax.

Nicolas

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun memoize-one-argument-function (funsym)
(let ((unmemoized (symbol-function funsym)))
(symbol-macrolet ((table (get funsym :memoization-table)))
(setf table ())
(setf (symbol-function funsym)
(lambda (x)
(let ((entry (assoc x table)))
(if entry
(cdr entry)
(cdar (pushnew (cons x (funcall unmemoized x))
table)))))))))

(defun inverse (funsym)
(lambda (y)
(let ((entries (remove-if-not (lambda (entry)
(eql (cdr entry) y))
(get funsym :memoization-table))))
(cond
((null entries) (error "Sorry - not yet defined"))
((= (length entries) 1) (caar entries))
(t (mapcar #'car entries))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun f (x) (1+ x))

;; this line has to be inserted
(memoize-one-argument-function 'f)

;; and inverse has to be called with 'f instead of #'f
(f 2)
(funcall (inverse 'f) 3)
(funcall (inverse 'f) (f 5))

From: Harald Hanche-Olsen on 14 Feb 2010 09:34

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

--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell

| Next | Last
Pages: 1 2 3 4 5 6 7 8 9 10
Prev: Lisp and ncurses
Next: new version of emacs's command frequency report