For some time, it was popular to experiment with VMs (virtual machines) that accepted programs represented as trees or graphs or related algebraic structures. The most famous examples are Haskell's G-Machine (standing for "graph" machine) and CAML's Categorical Abstract Machine, and there are many more. The whole topic of Intentional Programming is devoted to manipulation of programs as trees, even to the point of their surface syntax. We can see contemporary efforts to promote programs-as-trees in XML -- today's tree-syntax-of-choice -- for all kinds of VMs from query processors to rendering and simulation engines.
However, most workers have completely abandoned this approach and gone back to instruction sets as the preferred representation at the VM boundary. Java and CLR are obvious examples, but even Haskell and CAML have gone back to instructions and abandoned trees. Why? There is one big answer. The consensus -- after trying it -- is that it's the compiler's job to reduce recursion to looping, NOT the VM's job. That's the division of labor that promotes good software development by letting the VM concentrate on optimization, JITting, and efficient execution. Since trees and their relatives are an inherently recursive data structure, feeding them to the VM means that the VM needs to do the pedestrian step of boiling off recursive definitions before it can get to its real job.
Recursion is great for describing things, but lousy for executing things. Describing things is the compiler's job, and executing things is the VM's job.
Reference: “Feynman’s Lost Lecture, The Motion of Planets Around the Sun,” by David L. Goodstein and Judith R. Goodstein, W. W. Norton & Company, New York, 1996.
Richard Feynman was one of the most important physicists of all time. He had a peculiar way of taking ideas out of thin air and bringing them to bear on problems that seemed unrelated, thereby busting them wide open. He is perhaps best remembered for the path-integral formulation of relativistic quantum mechanics, which not only showed that the otherwise stupefyingly mysterious quantum mechanics is just another application of the old familiar principle of least action, but also revealed space-time symmetries that resolved conundrums about antiparticles and particles going backwards in time. Every word he ever spoke or wrote is worthy of study. I had the privilege of meeting with him several times over the years as a child, an older student, and as a professional physicist, and witnessing the magic at work.
The book referenced at the top records a wonderful demonstration by Feynman that Kepler’s laws follow from Newton’s laws plus ordinary, high-school plane geometry: no calculus required. No differential equations, no angular momentum, no constants of integration. This is Feynman at his best: reducing something seemingly big, complicated, and difficult to something small, simple, and easy. In this PDF file (http://home.comcast.net/~brianbec/Feynman.zip), I present an original reconstruction of this argument, accompanied by several documents for the application Geometry Expressions. This is a very powerful constraint-propagation and symbolic-manipulation program specialized to plane geometry. It was, in fact, that an old friend of mine, Van Warren of Warren Design Visions, brought Geometry Expressions to my attention that stimulated me to recall Feynman’s Lost Lecture and attempt this reconstruction.
My presentation is very short, on purpose, but omits no detail. To get a more lengthy presentation that delectates on every precious morsel, PLUS an audio CD recording of the man himself delivering the lost lecture, see the book referenced at the top. You won’t regret it.
Here are Kepler’s three laws, in the order that we prove them:
K1: A planet orbiting a star sweeps out equal areas in equal times
K2: The square of the period of a closed orbit is proportional to the cube of its longest axis
K3: A closed orbit is an ellipse (open orbits are parabolic or hyperbolic)
Now, here are Newton’s laws (specialized to the fixed-star assumption and numbered as we need them)
N1: A body (planet) in motion continues in straight-line motion unless acted on by a force
N2: The change in velocity of a planet over a time interval is proportional to the force applied (N1 is really a special case of N2 with force equal to zero)
N3: The force between a planet and a star acts along the line connecting them (central-force law)
N4: The force between a planet and a star is proportional to the inverse square of the distance between them (inverse-square law)
Now, get the downloads to get the rest of the story :)
Ok, it's been quite a while since I issued the challenge to write the Y combinator in VB9 CTP without using recursive types, and no one has bitten yet (actually, the challenge was originally made to me by Erik Meijer and much of what I've done comes from Mark Shields). So I am going to drop a HUGE hint and re-issue the challenge. Review my blog to see how I did the early-bound version, using a universal representation for types. Now, instead of recursively defining a type U with a branch for functions from U-to-U, (drum roll), use
exceptions to throw either integers or functions from U-to-U out of the combinators. Now, the top-level type is ... ?? That's the new puzzle, and I'm going to bring this episode to a close with that, hoping some adventurous reader will post the solution in the form of VB code, because I have some new wonders to talk about.