What's a treeshaker?
Pinku Surana
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
pin...@stc.comm.mot.com Motorola, Inc
Paul F. Snively
pin...@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
ch...@shell.portal.com that there's no one out to get you."
Martin Rodgers
ch...@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
clipper....@cpsr.org and tell them you oppose Clipper.
This is a shareware .signature -- please pass it on!
Lou Steinberg
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: l...@cs.rutgers.edu
--
Lou Steinberg
uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou
internet: l...@cs.rutgers.edu
Martin Rodgers
l...@cs.rutgers.edu "Lou Steinberg" writes:
> 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.
This is why I'd suggest using a subset of CL. Forget about EVAL,
as it's considered to be "bad style" these days. The Forth 79 and
Forth 83 standards don't inlcude anything like EVAL, altho writing
a treeshaker is implementation dependant enough for that to be a
small inconvenience. If you can write a treeshaker, you can write
a Forth version of EVAL. Or you can ignore 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.
I'd rather just avoid using EVAL. For me, it's just something to help
a developer, perhaps for debugging macros. I don't feel I need it for
my code, esp if it was going to become a stand alone app.
> 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)))
You can - but why would you want to? If you're serious about writing
stand alone code that can compete with code written in C++, then you
don't want to use EVAL - or COMPILE, or COMPILE-FILE. These functions
are more trouble at runtime that they're worth, and they make stand
alone code impossible, surely?
Stephen J Bevan
... Forget about EVAL, as it's considered to be "bad style" these
days. The Forth 79 and Forth 83 standards don't inlcude anything
The ANS Forth standard does, it is called EVALUATE.
Tom Almy
Sometimes standards make steps backwards. I have a shareware Forth
compiler that I'm converting to ANS Forth. It doesn't implement
EVALUATE. EVALUATE in Forth has the same set of problems regarding
"EVAL" as Lisp does.
(BTW, I usually just lurk here, and it has been interesting to see basically
the same sets of language philosophy discussions here as in comp.lang.forth.
There are many similarities between the two languages!)
--
Tom Almy
tom....@tek.com
Standard Disclaimers Apply
s...@sef-pmax.slisp.cs.cmu.edu
From: cyber_...@wildcard.demon.co.uk (Martin Rodgers)
This is why I'd suggest using a subset of CL. Forget about EVAL,
as it's considered to be "bad style" these days.
You keep saying this, so I thought it would be useful to respond before
too many people swallow this statement uncritically.
Eval is not bad style in all cases. Not every program needs eval, but when
you do need it, it's a wonderful and very important thing to have around.
Most of the essential uses of Eval involve implementing some sort of
embedded interpreter for a more specialized language in Lisp.
If you have something like (eval (read)) in your program, the user could in
principle ask for anything defined as part of Common Lisp, and that's a lot
of stuff. But you could also just tell users that only a subset of CL
commands are available at runtime, and if they want hyperbolic tangent,
they are just out of luck because it has been removed.
What is bad style is to use Eval when you don't really need it. I've seen
lots of Lisp code in which Eval is used because the programmer doesn't
really understand how to use quoting or funcall/apply or macros. This is
indeed inefficient and more error-prone than using more restrictive forms.
Dylan leaves Eval out of the core langauge, not because Eval is so
expensive but because it implies that so much other stuff is around at
runtime. 95% of application programs don't need Eval, so why burden them
with this extra runtime baggage? But most Dylan implementations will
provide some sort of interpreter in the development environment and some
(perhaps limited) form of Eval as an optional runtime library for programs
that do need it.
-- Scott
===========================================================================
Scott E. Fahlman Internet: se...@cs.cmu.edu
Principal Research Scientist Phone: 412 268-2575
School of Computer Science Fax: 412 681-5739
Carnegie Mellon University Latitude: 40:26:46 N
5000 Forbes Avenue Longitude: 79:56:55 W
Pittsburgh, PA 15213
===========================================================================
Ken Bibb
>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... :)
Martin Rodgers
be...@cs.man.ac.uk "Stephen J Bevan" writes:
> ... Forget about EVAL, as it's considered to be "bad style" these
> days. The Forth 79 and Forth 83 standards don't inlcude anything
> like EVAL, ...
>
> The ANS Forth standard does, it is called EVALUATE.
That's why I didn't mention ANS Forth. I was refering to the previous
(and widely implemented) standards.
Martin Rodgers
> This is why I'd suggest using a subset of CL. Forget about EVAL,
> as it's considered to be "bad style" these days.
>
> You keep saying this, so I thought it would be useful to respond before
> too many people swallow this statement uncritically.
It has been said by many others. I merely agree with them. Most
languages have nothing like EVAL, and many programmers would sudder
at the idea. They may be wrong, but they still feel that way.
> Eval is not bad style in all cases. Not every program needs eval, but when
> you do need it, it's a wonderful and very important thing to have around.
I don't doubt that. I didn't say it doesn't have its uses. I just
said that it is considered (ok, but _some_ people) to be bad style.
> Most of the essential uses of Eval involve implementing some sort of
> embedded interpreter for a more specialized language in Lisp.
Didn't I also say that will be expensive? How to you do that and
keep the runtime overheads low? I'm guessing from the posts here
over the last two years that CL implementations generally fail in
this repsect. Why else would so many Lisp programmers complain
about it? Why do so many C programmers think all Lisp programmings
are mad?
Why not simply think of EVAL as option? Those of us who might sometimes
wish not to use are currently forced to pay a runtime price for it.
So I'm told, as I only have access to interpreted Lisps that have no
support for stand alone code.
> Dylan leaves Eval out of the core langauge, not because Eval is so
> expensive but because it implies that so much other stuff is around at
> runtime. 95% of application programs don't need Eval, so why burden them
> with this extra runtime baggage? But most Dylan implementations will
> provide some sort of interpreter in the development environment and some
> (perhaps limited) form of Eval as an optional runtime library for programs
> that do need it.
Didn't I say that? I'm sorry if I didn't make myself clearer. I was
refering to the many posts I've seen on this subject over the last
two years, and how at least a few programmers want _all_ of CL all
the time, even after delivering the code. I hope they are a minority,
coz most apps (and most users) demand much lower overheads.