4 ms·
The name "treeshaker" for an application delivery tool possibly originated in Lisp. The first time I've found it was in Lucid Common Lisp, a (no longer availabl
by lispm 3y ago
The name "treeshaker" for an application delivery tool possibly originated in Lisp. The first time I've found it was in Lucid Common Lisp, a (no longer available) commercial implementation of Common Lisp for UNIX. Lucid CL 4.1 in 1992 included a tool called Treeshaker. Lucid CL was one of those Lisps which have the idea of an image (see for example the "image" feature of Lisp 1 in 1960), a saved memory dump of the current heap of a running Lisp. An application then is an image plus a runtime. The image typically includes almost all code AND data from the memory, which sometimes creates the wish to create smaller images for application delivery. Lucid CL then included a tool, which before saving that image, removes all kinds of unused code and data, depending on some meaning of what „unused“ means. For example the symbol table may have variables, types, functions, etc. which are not referenced anywhere. A treeshaker tool might also get a list of things to remove. Thus in a graph of reachable Lisp data&code, the connections are pruned. Either a GC or a specialized piece of code then collects the garbage, shrinks memory (-> shakes the tree and everything which is cut loose is falling down) and dumps it as a possibly smaller image.
The treeshaker thus was not a compiler tool, but a tool to remove what was determined to be unused code of a Lisp heap. Remember, by default such a Lisp image would also contain a compiler, an interpreter and an implementation of a read-eval-print loop. Thus if we break (-> interrupt a thread which then provides a REPL) a running program into such a read-eval-print loop, we could still use all the code, which is in this heap (which was restored from an image). Thus it would make sense to remove the compiler too, and possibly the read-eval-print loop, too.
- munificent 3y agoI could be wrong, but I've heard that the term originated in Smalltalk. Smalltalk is also image-based, and tree-shaking was a way to produce a smaller image for deploying.
- lispm 3y agoReferences: Lucid Inc. used the word internally at least since 1987, mentioning a treeshaker for Lucid CL 3.0 on the VAX. "Lisp Systems in the 1990s", Layer/Richardson, 1991 https://dl.acm.org/doi/10.1145/114669.114674 https://dl.acm.org/doi/10.1145/114669.114674 From above: "In contrast, tree shaking uses the approach of eliminating --shaking out-- what is not needed in a static fashion. Programmers specify the requirements of their application and the unneeded parts of the Lisp system are removed using their detailed knowledge of the application. The disadvantages of tree shaking are that it requires programmer intervention and that a function which is shaken out cannot be easily restored." "Building Common Lisp Applications with Reasonable Performance", Boreczky/Rowe, 1993, https://dl.acm.org/doi/10.1145/1040032.174174 https://dl.acm.org/doi/10.1145/1040032.174174 "Lisp: Good News, Bad News, How to Win Big", Gabriel, (not sure from when this version is, the original article is from 1989) https://www.dreamsongs.com/Files/LispGoodNewsBadNews.pdf https://www.dreamsongs.com/Files/LispGoodNewsBadNews.pdf From Gabriel's essay: > "1.6.3 The Treeshaker > Most Lisp development systems, including Lucid’s, provide all the resources of the Lisp system by default, and this in turn leads to a style of development in which the programmer makes use of whatever tool happens to be most convenient. Because much of the basic Lisp system (or any development system built on top of the basic Lisp system) will generally be unused by a given application, it is very worthwhile to have a tool for excising these unused parts. This tool is called the Treeshaker. > Treeshaker execution occurs in three phases: walking, testing and writing. In the walking phase, the Treeshaker accumulates a set of objects that need to be included in the saved image. After making this set, the treeshaker runs a test of the application to check that all objects which are used in a typical run have been included. The writing phase then generates an executable image which will run the application. > To a first approximation, the walk phase is just a matter of computing the connected component of the Lisp image (treated as a directed graph in the obvious way) generated by the application’s toplevel function. However, because of the way that Lisp objects are generally connected this usually includes almost the entire Lisp image including the unused subsystems. Therefore the treeshaker uses several techniques to find connections between objects that do not actually need to be followed in the walk." > "The name Treeshaker is meant to be evocative of the idea of actually shaking a tree to dislodge dead branches or other trash." On the more funny side, LispWorks has a keyword to the DELIVER function :shake-shake-shake , which invokes the treeshaker during application delivery. https://www.lispworks.com/documentation/lw80/deliv/deliv-keywords-2.htm#DELIV):shake-shake-shake%20keyword https://www.lispworks.com/documentation/lw80/deliv/deliv-key...