I have heard the term "tree shaker" thrown around a few posts. I
thought I understood what it meant, but now I'm not sure. Here's
what I thought: a tree shaker removes all functions and/or packages
which go unused by the particular program or package one is trying
to deliver as an executable. This results in a smaller image and
faster execution.
However, I thought most of the image was taken up by empty space
reserved for putting stuff in (data, functions, etc.). In which
case, little (relatively speaking) will be removed from the overall
size of the image.
If this made any sense, please provide, if possible, some kinda'
concise definition of what a tree shaker does. In fact, if there
are publicly available examples, let me know.
Thanks,
Pinku
--
-----
Pinku Surana Software Technology Center
······@stc.comm.mot.com Motorola, Inc
In article <······················@lmpsbbs.comm.mot.com>
······@comm.mot.com (Pinku Surana) writes:
> I have heard the term "tree shaker" thrown around a few posts. I
> thought I understood what it meant, but now I'm not sure. Here's
> what I thought: a tree shaker removes all functions and/or packages
> which go unused by the particular program or package one is trying
> to deliver as an executable. This results in a smaller image and
> faster execution.
>
> However, I thought most of the image was taken up by empty space
> reserved for putting stuff in (data, functions, etc.). In which
> case, little (relatively speaking) will be removed from the overall
> size of the image.
You're exactly right. The idea is that the potential execution flow of
a program can be represented as a tree. The main function is the root,
and it calls functions, which call other functions, etc. A treeshaker
(what the rest of the known universe calls a smart linker) is a beast
that attempts to enumerate all of the functions ever called, directly
or indirectly, by the main function, and removes the rest.
While this is a relatively straightforward process for languages such
as C, it isn't for a language like Common Lisp, which allows one to do
stuff like cons up a list at runtime and hand it to eval (in fact, most
treeshakers simply throw up their hands in despair if the find a call
to eval anywhere in the tree. All bets are off, at that point.)
As for your second point, I don't know whether most Lisp images' data
use swamps their code use, but I'm inclined to doubt it. Most decent
Lisp implementations try to give as many things an immediate
(machine-sized) representation as possible; it's not clear that `Lisp
data' is usually bloated compared to other languages' data. So it
seems as though having a successful treeshaker would still be a big win
in most Lisp environments.
> Thanks,
> Pinku
-----------------------------------------------------------------------
Paul F. Snively "Just because you're paranoid, it doesn't mean
·····@shell.portal.com that there's no one out to get you."
In article <··········@news1.svc.portal.com>
·····@shell.portal.com "Paul F. Snively" writes:
> While this is a relatively straightforward process for languages such
> as C, it isn't for a language like Common Lisp, which allows one to do
> stuff like cons up a list at runtime and hand it to eval (in fact, most
> treeshakers simply throw up their hands in despair if the find a call
> to eval anywhere in the tree. All bets are off, at that point.)
Isn't this one of the reasons why EVAL is considered to be bad style
these days? It's not only bad programming style, but it creates technical
problems like the kind you described.
One of the first Forth programs I saw was a treeshaker for Fig Forth,
used to port the Fig Forth threaded image. It wasn't a true treeshaker,
as it merely relocated the threaded code onto a new machine, but it
used similar principles. Fig Forth could have had something like EVAL
added to it, but it wouldn't have made a treeshaker impossible.
As I understand it, EVAL is a "runtime" function, assuming that you
can make such a distinction with Lisp. As you can't really do that
in Common Lisp, except by using EVAL-WHEN for your EVAL expression,
this is going to be a problem with the language dialect, rather than
with Lisp itself.
You could, in theory, design a dialect that assumes that the code will
be compiled all at once, instead of incrementally, one function at a time.
This is almost what Apple intend with Dylan, except that Dylan can do
it at the class level, when you seal off a class. Will a treeshaker
be needed for Dylan systems? Could it be easier because Dylan doesn't
use EVAL? Apple say they wanted to take the best ideas from Lisp and
Smalltalk. I guess EVAL wasn't one of them.
--
Martin Rodgers, WKBBG, London UK AKA "Cyber Surfer"
If "One likes to believe in the freedom of email", email
················@cpsr.org and tell them you oppose Clipper.
This is a shareware .signature -- please pass it on!
In article <············@wildcard.demon.co.uk> ············@wildcard.demon.co.uk (Martin Rodgers) writes:
Fig Forth could have had something like EVAL
added to it, but it wouldn't have made a treeshaker impossible.
A tree shaker essentially says, leave function FOO and everything it
calls in the core image and throw out the rest. Suppose FOO does
(eval(read))
(to put it in lisp syntax rather than forth). Now FOO could call anything.
Of course there are some cases of eval a tree shaker could handle, e.g.
(eval '(+ 1 2))
or even
(let ((foo (cond (((null a) '+)
((null b) '-)
... etc))))
(eval foo))
But what about
(let ((foo (some-arbitrary-code))
(eval foo)))
How much analysis of (some-arbitrary-code) are you going to do in
order to determine what values? The "complete" problem reduces to the
halting problem, so you can't handle all code (even ignoring
dependence on runtime input). Thus for CL the typical case os for
tree-shakers to give up if they see eval.
It is reasonable for tree shakers to give up on eval in CL because in
CL most cases where eval might be useful can be easily coded using
funcall or apply instead, and (as of CLtL II) these functions do not
present a tree-shaker with the problems that eval does. Code can be
converted into a "funcall-able" data type only by operations such that
the reference to code can normally be detected in the static program
(unless of course you use eval or equivalents). Thus, a tree shaker
can find the code to include.
As I understand it, EVAL is a "runtime" function, assuming that you
can make such a distinction with Lisp. As you can't really do that
in Common Lisp, except by using EVAL-WHEN for your EVAL expression,
this is going to be a problem with the language dialect, rather than
with Lisp itself.
I don't understand - in CL I can certainly define a function
(defun foo() (eval(read)))
--
Lou Steinberg
uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou
internet: ···@cs.rutgers.edu
--
Lou Steinberg
uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou
internet: ···@cs.rutgers.edu
In <······················@lmpsbbs.comm.mot.com> ······@comm.mot.com (Pinku Surana) writes:
>I have heard the term "tree shaker" thrown around a few posts. I
>thought I understood what it meant, but now I'm not sure.
A "tree shaker" is a kind of monkey that likes camel dung with raisins
on top... :)