Hi group,
I'm interested if there's another way than using eval in this
situation: a code has to be generated (and compiled) at run-time. Say,
to solve a sparse system of equations x=Ax+b using an iterative
algorithm I might have a specific function to compute Ax+b with A, b
hard-coded inside. I mean, not having a matrix A and a vector b
explicitely. If A, b were known at compile-time, we'd use macros. But
what if A, b have to be computed at run-time? I can construct nested
lists representing a lisp function to compute Ax+b and feed it to
eval.
My question, are there other techniques for this case?
On Jul 21, 10:13 am, zoav1602 <········@gmail.com> wrote:
> Hi group,
> I'm interested if there's another way than using eval in this
> situation: a code has to be generated (and compiled) at run-time. Say,
> to solve a sparse system of equations x=Ax+b using an iterative
> algorithm I might have a specific function to compute Ax+b with A, b
> hard-coded inside. I mean, not having a matrix A and a vector b
> explicitely. If A, b were known at compile-time, we'd use macros. But
> what if A, b have to be computed at run-time? I can construct nested
> lists representing a lisp function to compute Ax+b and feed it to
> eval.
> My question, are there other techniques for this case?
You can pass the list representing the function to compile, if you
expect to call the function many times, but conceptually it's the same
as with eval. Or, if the form of the equations is known at compile
time and only the constants vary, you can use closures:
(defun make-Ax+b-function (A b)
(lambda (x) (+ (* A x) b))
If you compile make-Ax+b-function, it will produce compiled closures.
hth,
Alessio
On 21 Jul., 11:02, Alessio Stalla <·············@gmail.com> wrote:
> On Jul 21, 10:13 am, zoav1602 <········@gmail.com> wrote:
>
> > Hi group,
> > I'm interested if there's another way than using eval in this
> > situation: a code has to be generated (and compiled) at run-time. Say,
> > to solve a sparse system of equations x=Ax+b using an iterative
> > algorithm I might have a specific function to compute Ax+b with A, b
> > hard-coded inside. I mean, not having a matrix A and a vector b
> > explicitely. If A, b were known at compile-time, we'd use macros. But
> > what if A, b have to be computed at run-time? I can construct nested
> > lists representing a lisp function to compute Ax+b and feed it to
> > eval.
> > My question, are there other techniques for this case?
>
> You can pass the list representing the function to compile, if you
> expect to call the function many times, but conceptually it's the same
> as with eval. Or, if the form of the equations is known at compile
> time and only the constants vary, you can use closures:
>
> (defun make-Ax+b-function (A b)
> (lambda (x) (+ (* A x) b))
>
> If you compile make-Ax+b-function, it will produce compiled closures.
>
> hth,
> Alessio
To make it a bit clearer, Common Lisp has a function COMPILE.
http://www.lispworks.com/documentation/HyperSpec/Body/f_cmp.htm
You can generate Lisp code at runtime and cons up a LAMBDA form like
this one
(lambda (args) (do-something args))
Now you can compile above
(compile nil '(lambda (args) (do-something args)))
it will return a compiled function (if the Lisp has a compiler,
but most have).
From: John Thingstad
Subject: Re: question about functions generating functions
Date:
Message-ID: <op.uxew78lfut4oq5@pandora>
På Tue, 21 Jul 2009 11:32:25 +0200, skrev Rainer Joswig <······@lisp.de>:
> Now you can compile above
>
> (compile nil '(lambda (args) (do-something args)))
>
> it will return a compiled function (if the Lisp has a compiler,
> but most have).
>
Erm. The ANSI CL standard requires you to have a compiler. (I assume you
don't think a bytecode compiler like in CLISP is a REAL compiler or
something..)
---------------------
John Thingstad
On Jul 21, 12:10 pm, "John Thingstad" <·······@online.no> wrote:
> På Tue, 21 Jul 2009 11:32:25 +0200, skrev Rainer Joswig <······@lisp.de>:
>
> > Now you can compile above
>
> > (compile nil '(lambda (args) (do-something args)))
>
> > it will return a compiled function (if the Lisp has a compiler,
> > but most have).
>
> Erm. The ANSI CL standard requires you to have a compiler. (I assume you
> don't think a bytecode compiler like in CLISP is a REAL compiler or
> something..)
Yes but the minimal "compiler" required by ANSI CL is just a
preprocessor that expands macros and little else. So a purely
interpreted CL could exist, I think, though I don't know if one exist
(or ever existed).
From: John Thingstad
Subject: Re: question about functions generating functions
Date:
Message-ID: <op.uxeyrwequt4oq5@pandora>
På Tue, 21 Jul 2009 12:37:43 +0200, skrev Alessio Stalla
<·············@gmail.com>:
> On Jul 21, 12:10 pm, "John Thingstad" <·······@online.no> wrote:
>> På Tue, 21 Jul 2009 11:32:25 +0200, skrev Rainer Joswig
>> <······@lisp.de>:
>>
>> > Now you can compile above
>>
>> > (compile nil '(lambda (args) (do-something args)))
>>
>> > it will return a compiled function (if the Lisp has a compiler,
>> > but most have).
>>
>> Erm. The ANSI CL standard requires you to have a compiler. (I assume
>> you
>> don't think a bytecode compiler like in CLISP is a REAL compiler or
>> something..)
>
> Yes but the minimal "compiler" required by ANSI CL is just a
> preprocessor that expands macros and little else. So a purely
> interpreted CL could exist, I think, though I don't know if one exist
> (or ever existed).
Well of the 10 implementations that exist today all have compilers.. Which
is all you need to know really.
---------------------
John Thingstad
On 21 Jul., 12:10, "John Thingstad" <·······@online.no> wrote:
> På Tue, 21 Jul 2009 11:32:25 +0200, skrev Rainer Joswig <······@lisp.de>:
>
> > Now you can compile above
>
> > (compile nil '(lambda (args) (do-something args)))
>
> > it will return a compiled function (if the Lisp has a compiler,
> > but most have).
>
> Erm. The ANSI CL standard requires you to have a compiler. (I assume you
> don't think a bytecode compiler like in CLISP is a REAL compiler or
> something..)
>
> ---------------------
> John Thingstad
A standard is a standard. A CL implementation is something else. The
standard requires
a lot of things. An implementation might not always provide everything
that's in
the standard. Then it is kind of non-standard. But who cares if it
serves
a useful purpose.
In some situations (delivery, ...) there might be an interpreter, but
no compiler.
Sometimes there might not be even an interpreter AND no compiler
(delivery to static C, ...).
If I 'deliver' a LispWorks application, then COMPILE-FILE is gone at
runtime. Even
though LispWorks is ANSI CL. I could probably buy the license to be
able
to use COMPILE-FILE in an application, but that might be expensive. I
learned,
though, that LispWorks keeps COMPILE in delivered applications if I
wish (unless
I want to save the space and don't need it).
Yes, the bytecode compiler of CLISP is a 'real' compiler.
On 2009-07-21 11:10:46 +0100, "John Thingstad" <·······@online.no> said:
> Erm. The ANSI CL standard requires you to have a compiler.
No, it doesn't. Or rather, it only requires something incredibly minimal.
zoav1602 <········@gmail.com> writes:
> Hi group,
> I'm interested if there's another way than using eval in this
> situation: a code has to be generated (and compiled) at run-time. Say,
> to solve a sparse system of equations x=Ax+b using an iterative
> algorithm I might have a specific function to compute Ax+b with A, b
> hard-coded inside. I mean, not having a matrix A and a vector b
> explicitely. If A, b were known at compile-time, we'd use macros. But
> what if A, b have to be computed at run-time? I can construct nested
> lists representing a lisp function to compute Ax+b and feed it to
> eval.
> My question, are there other techniques for this case?
First, you may distinguish functions generating functions from
functions generating closures.
In the later case, only some enclosed variables change from one
closure to the other:
(defun make-line (a b)
(lambda (x) (+ (* a x) b)))
In this case, the function of the closure (the lambda) is compiled at
compilation time. Only the bindings to the closure (a and b) are made
at run-time:
(let ((l1 (make-line 2 1))
(l2 (make-line 3 -1)))
(- (funcall l1 0) (funcall l2 0))) --> 2
If the parameters are known at compilation time, you still don't need
a macro, just define your function:
(defun line-3 (x) (+ (* 4 x) 1))
(line-3 42)
or:
(let ((l3 (lambda (x) (+ (* 4 x) 1))))
(funcall l3 42))
Up to now, all the closures created by a function such as make-line
are functions belonging to a familly of functions: some parameters
change, but the computations done by the various members of the family
are the same, so there's only one same binary code for all of them.
If you want to create at run-time functions whose bodies are
different, then you will have to build a lambda form, and compile it.
For examples:
(defun generate-function (arguments operators)
(list 'lambda arguments
(loop
:for expr = (pop arguments)
:then (list (pop operators) expr (pop arguments))
:until (or (endp arguments) (endp operators))
:finally (return expr))))
(generate-function '(x y z) '(+ *)) --> (LAMBDA (X Y Z) (* (+ X Y) Z))
(let ((f (compile nil (generate-function '(x y z) '(+ *)))))
(funcall f 2 2 3)) --> 2
(defun select (list)
(let ((item (elt list (random (length list)))))
(values item (remove item list))))
(defun generate-random-expression (binops unops expr)
(if (or binops unops)
(if (< (random (+ (length binops) (length unops))) (length binops))
(multiple-value-bind (op rest) (select binops)
(list op (generate-random-expression rest unops expr)
(generate-random-expression rest unops expr)))
(multiple-value-bind (op rest) (select unops)
(list op (generate-random-expression binops rest expr))))
expr))
(defun make-random-function ()
(compile nil (list 'lambda '(x)
(list 'handler-case
(generate-random-expression
'(+ - * /)
'(identity sin cos (lambda (x) (* x x)))
'x)
'(error () 'nil)))))
C/USER[123]> (loop repeat 10 do (print (loop with f = (MAKE-RANDOM-FUNCTION) for x from 0.0 to 1.0 by 0.1 collect (funcall f x))))
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL 0.93555063 0.9221105 0.9008954 0.8735527 0.84214264 0.8089512 0.77636415 0.7469347 0.7239408)
(NIL -0.42909086 -0.42339855 -0.4137621 -0.39999276 -0.38191772 -0.3595297 -0.33330393 -0.30488178
-0.2786162)
(NIL 0.77557087 0.7183393 0.6249741 0.5018181 0.36188757 0.22444746 0.11137805 0.042945437
0.038246308)
(NIL 0.82893765 0.7857106 0.71454096 0.6172693 0.4979943 0.36557734 0.23795247 0.14812982 0.14990473)
(0.0 -0.0049022404 -0.01888715 -0.040456805 -0.06908621 -0.10699003 -0.15938868 -0.23135132
-0.3185831 -0.39741275)
(NIL 0.13519186 0.12950563 0.11877805 0.106654525 0.12809467 0.374564 1.3711334 2.3310351 0.3031953)
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL 7.454651 7.3611574 7.1774187 6.8714275 6.4215302 5.8401155 5.190185 4.5795655 4.142553)
(NIL 2.0 2.0 2.0 2.0 1.9999993 1.9999868 1.999867 1.9991348 1.9963522)
--
__Pascal Bourguignon__
zoav1602 <········@gmail.com> writes:
> Hi group,
> I'm interested if there's another way than using eval in this
> situation: a code has to be generated (and compiled) at run-time. Say,
> to solve a sparse system of equations x=Ax+b using an iterative
> algorithm I might have a specific function to compute Ax+b with A, b
> hard-coded inside. I mean, not having a matrix A and a vector b
> explicitely. If A, b were known at compile-time, we'd use macros. But
> what if A, b have to be computed at run-time? I can construct nested
> lists representing a lisp function to compute Ax+b and feed it to
> eval.
> My question, are there other techniques for this case?
Usually I would expect that only parameters of some function change
depending on the index, so you should be able to define
A(i,j)=f(i,j) b(i)=g(i) for some functions f and g.
You could then define a class like
(defclass computed-matrix ()
(f :reader entry-calculator :initarg :f))
and a reader
(defmethod mref ((A computed-matrix) i j)
(funcall (entry-calculator A) i j))
which you could define for arbitrary other matrix representations (e.g. as
2d-array).
[The difficulty gets larger, if you aim for high performance, i.e. if the
generic function access to single entries is too slow, or if you have to
cache parts of your computed matrix for efficiency reasons, or if you want
to parallelize your entry calculations. I am just working on such
techniques for finite element discretizations.]
Yours, Nicolas