RE: (Lisp-HUG) Identifying Calling Function...
> Question: Is there any way in standard Common Lisp to identify a calling
> function?
>
> E.g., (cons (f1 x) (f2 x))
>
> ...is there any rational way to figure out
inside f1 the fact that the next function up the food chain is cons???
At 12:12 PM 8/3/2012, Eivind Midtgård wrote:
>In LW you should be able to do it with defadvice on each function. Or you
>could perhaps use trivial-backtrace
>(http://common-lisp.net/project/trivial-backtrace/), though as Paul points
>out, the functions may not be there after the optimizer has done its job.
Greetings to the List -
I asked the question a few days ago because I am
trying to see what sort of processing
efficiencies might be realized by moving our
commercial application --- forensic fingerprint
scanning and analysis (103,000 lines of Common
Lisp) --- from a single-core embedded Pentium
processor to multi-core hardware with LW6.x.
My interest, for years now, is to try to build a
"clean" multiprocessing software programming
"paradigm" (hate that word!), that I can
understand, rather than just manually hacking in
the LW6.x threads/processes etc.
If you assume that hardware core counts will
double about every year, then 1K-core platforms
should be the norm within ten years or so, which
is the assumed product life of this commercial
software (with enhancements, of course). Thus,
ideally, the software moved to the parallel
hardware multi-core environment should
automatically speed up with no modification or
thought as the core count increases over time (at
least no worse than according to Amdahl's Law -
http://en.wikipedia.org/wiki/Amdahl%27s_law).
I first worked with multiprocessing forty years
ago on a UNIVAC mainframe and learned that it is
not easy. Fifteen years later, I worked on a
larger scale parallel machine with up to 128
processors (http://frobenius.com/spock.gif),
where I learned that building large scale general
parallel software is a nightmare and exceedingly difficult to do.
I believe that there are two primary problems:
(a) Inadequate parallelism syntax that leads to
application code being sprinkled with confusing,
ugly, and irritating control/synchronization
primitives; and (b) It is easy to spawn hordes of
processes, but not so easy to gracefully kill all
of them off once an answer (e.g., a search in a Search Space) has been found.
Transactional Memory (TM) appears promising, but
is really not my primary cup of tea: (a) I think
that it is more oriented toward protecting
processes that mostly modify small sets of
existing objects in atomic 'transactions' rather
than creating new objects or munging large
subsets; and (b) I think, especially, that it
will require special hardware to work effectively
(I/O is also problematic; how do you undo I/O
when a transaction has to be rolled back?).
I very much believe that Good Code is inherently
like Good Physics - The controlling primitives in
software code have to be "pretty" and a joy to
read to have any chance to be good/trusted to
work. If you can't easily read and understand the
code (like reading/understanding Maxwell's
Equation primitives in physics), then there is
almost no way that the code can be determined to
be "right" --- and control/synchronization
primitives sprinkled everywhere in code is
certainly not "pretty", much less understandable.
I believe that the key to parallel programming is
absolute brevity in the control syntax.
After some thought over the past several years
(in my not so abundant spare time), perhaps the
following syntax to deal with parallel processing
on multi-core hardware might be useful:
e.g.,
(defun build-tree(x n)
(cond ((zerop n) x)
(t (cons {build-tree x (1-
n)} ; Note braces... ...{} denotes a 'future'...
{build-tree x (1-
n)})))) ; Note braces... ...{} denotes a 'future'...
where the forms in braces (i.e., the {}s) are
"futures"
(http://en.wikipedia.org/wiki/Future_%28programming%29
- stolen for this from Halstead's MultiLisp circa 1980).
A future transparently spawns a process to
evaluate its form in parallel, but immediately
returns a placeholder (pointer to a "future"
object) so the original calculation can proceed
until it needs an actual value at which time it
hangs until that calculated value exists. Once
the future has been resolved with an answer, then
the pointer to the future is automatically
replaced with a pointer to the actual value and
the delayed process happily proceeds.
This on-the-fly pointer replacement is not so
easy to do in standard Common Lisp but can, I
think, be implemented with closures, threads,
messaging, and other messy things setup by the {} Read Macro.
The above example Build-Tree constructs a tree of
depth n with each leaf being x. Thus,
(build-tree 3.14 20) will construct a 20-depth tree with about a million PIs.
The above Build-Tree, with the {} forms,
automatically spawns new processes as needed that build and return sub-trees.
The primary thing that I like about the {} read
macro above is that the general form of the
parallel version of the code (above) is identical to the serial form.
Implementation of the {} read macro, at first
glance, seems simple (well, simplish) and
obvious: A Read Macro for the {} constructs a
correct form with all of the LW 6.x parallel
processing control and other mechanisms injected.
However, there is a problem (actually
several): In the above Build-Tree, pointers to
sub-trees are actually pointers to futures - and
those pointers need to automatically and
asynchronously replace themselves with pointers
to final resolved sub-trees of cons cells, once they are generated.
Another situation:
(+ {f1 x} {f2 y} {f3 z})
In Build-Tree above, cons will happily cons up
futures that will eventually be replaced with
pointed to realized values, but the + function
doesn't know about futures and absolutely
requires numeric arguments. Thus, the {} read
macro has to deal with hanging the process that
is running the function + until all of the future arguments have been resolved.
The only reasonable way that I see a solution to
all this would be for the {} read macro to know
what the calling function is (e.g., is it
something like cons that will accept literally
anything in which case let the new process run
etc - or is it something like + that requires a
particular and specific type such as a number in
which case hang the + process until the futures all resolve to numbers).
These are, of course (I think), really binding issues:
(let ((v {f x}))....)
As usual, the {f x} is a future. The binding of v
(ignoring, for the moment, the compiler) is,
perhaps, a pointer to a future, a pointer to a
resolved primitive Lisp object (e.g., 3), or a
pointer, for example, to a cons cell with two
futures embedded. At some point, asynchronously,
the binding of v will change from a future to a
realized value. So, at one moment, v -> {future}
and at another later moment, v -> 3.
I find it interesting to note (again, ignoring
the compiler) that *all* user defined functions
will immediately accept future values - it is
only Lisp primitives (e.g., +) that require
actual resolved values (is this really true???).
Refinements on the {} read macro:
(a) {} would know the core count and its
generated code would only spawn a new process at
runtime if a core was available, otherwise it
would treat at runtime the {}s as ()s and execute
serially, which would help to minimize choking
the system with spawned processes.
(b) A Throw somewhere deep inside a spawned
process that goes outside the top-level would
automatically terminate all other generated
processes. This would be a clean way to terminate
all those hordes of processes that are searching
a Search Space etc (neat idea stolen from Gabriel
and McCarthy's QLAMBDA circa 1984).
(c) Once {} has been implemented, then something
else ('atomic'?) would be added to the system to
provide some sort of higher-level object-level synchronization/protection.
(d) etc
All of the above could be implemented with access
(and knowledge!) of the Lisp compiler, etc.
However, I am trying to construct something that
will work in standard Common Lisp (I don't see how) - or with LW6.x primitives.
One messy implementation technique could be for
the {} read macro to figure out (at compile time;
run time?) the calling function (e.g., cons in
the above Build-Tree) and generate code
accordingly (thus, my original question) based on
the function: Cons would be treated in the macro
expansion differently than +. Gee, there are over
800 of those things in CL - each to be analyzed...
Of course, any Common Lisp system that supports
parallelism is living in a State Of Sin anyway
(e.g., arguments to a function are evaluated
"strictly left to right" --- and I am not sure what others).
So, question: Anyone have any thoughts as to how
to possibly implement the {} parallel processing
read macro in LW6.x Lisp without, hopefully,
messily thinking about the calling function (cons, + above)?????
Just gotta' be an un-ugly way --- something not too horribly offensive...
Regards from a Slow and Lovely Summer Day in the Rocky Mountains,
Jack Harper
Secure Outcomes Inc
Evergreen, Colorado USA
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html