A Swirl of thoughts on Programming.
Sep. 8th, 2004 08:44 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
swestrupI had an insight a few days ago; one that I'm still processing. I'm not sure I can put it all down in words and have the results make any sort of sense, but I think I want to try and capture the ideas while they are fresh. It all has to do with programming, category theory, fractal structures, editorial assistants, and my friend ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
_sps_.
Actually,_sps_ is a good place to start. I don't want to embarass the man, but he is smart and by far the best programmer I have ever met. Now, I consider myself the second best programmer I have ever met, but I will concede that in 2 or 3 cases I can think of it depends on the metric you use to measure 'best'. Now, I know that sounds like bragging, but I think its relevant to what follows. You see, I learn best by comparing my performance to others, and trying to narrow the gap. I learn what they do that I don't, and I try to borrow or steal as many useful skills as I can, incorporating them into my own toolset.
When I first learned programming, I wanted to be better than my childhood friends. That was easy. Later, I tried to be better than my teachers. That wasn't too hard. Finally, I tried to be better than all of my coworkers. That was very difficult and took years of work, but I got there. When I met_sps_ the gap between our abilities was larger (in my view at the time) than my total skill set. I was a LONG way behind him. I have tried over the years to improve, and I have narrowed the gap, but I don't think I'll ever catch up. However, a week ago, I had an idea that has finally given me an insight into one of the skills that he has, that I never understood before.
That skill is the ability to optimize through generalization. While trying to explain this skill to me, he once said something along the lines of "You start by making the design able to solve more and more general cases, until the problem becomes so simple that its easy to write. You code that, and then your original application is just one use of a far more powerful program." I found it hard to understand how this could be possible. Up to that point I had always believed that handling more cases implied more complex code to deal with the cases, which implied more lines of code, making for a larger and often slower program. I have since been shown a number of examples of this technique in operation, and the results were always far smaller, faster and more powerful that any program I would have written to solve the same problem. The problem is, I could never figure out how one goes from a program spec to a design for a tiny, general purpose program that just happens to be able to fulfil the spec.
A few days ago, I got my first inkling of how one would go about doing that, and how one might even attempt to automate the process. I was working on a simple program to generate star systems for a role-playing game. For the first pass I wasn't thinking about efficiency or good design. I had decided to simply copy a pencil-and-paper generation system that I knew about, and worry about efficiency once I decided whether or not I liked the statistical results it produced.
As I worked, I couldn't help but notice places where I could optimize. Many subroutines performed a small data generation or display task, dependant upon certain constraints. The details in all the cases were different, but the general structure was similar. Had I been worried about efficiency or code size (rather than verifing that what I was building followed the paper rules) I would have moved more of the data into tables, and pruned the routines down to 2 or 3 varients. I might then have gone further and factored out the differences in the routines and built a code table to handle the differences. The result would have been a structure traversal routine, a node engine, and a whole bunch of data and code tables that represented the relationships I was trying to build.
Instead, I just kept adding new routines, testing them out, and idly thinking about the general shape of the structure I was building. Suddenly I noticed that the program had a rough fractal shape. That is, it was to a degree self-similar. Not only were many of the routines similar to each other, but their heirarchical relationships were echoed at various scales both in how the types related to each other, and how the routines called each other. In fact, the program as a whole had a resemblence to any one of the major leaf routines.
Now, I don't know much about category theory, but I do understand (in theory, if not in practice) how it can depict arbitrary mathematical relationships as graphs of dots and arrows. I started trying to imagine what a category-theory analysis of my current program would show. I suspected that it would be a series of similar graphs, linked by a few connections. Now, my normal optimizaton technique would amount to finding the largest subgraph that was common to the majority of graphs, factoring it out, and replacing it in each case with a link to the removed graph. I would continue doing this util the point of diminishing returns.
Instead, as I looked at this structure in my mind's eye, I had a new idea. Instead of factoring the structures, my sense of symmetry asked what would happen if I added to all the subgraphs, so that the fractal shape was exactly self similar, not just aproximately so. This would be the equivalent of adding a bunch of code, but it would look much prettier in my mind, because all of the irregularities would go away, and the result would be more balanced. As I contemplated this idea, I saw that the results had another property common to fractals -- it could be generated by a much simpler function. In essense, all of the self-similar parts (which now composed the whole structure) could be collapsed into a single meta-recursive leaf node that called itself in various ways to produce all of the needed functionality.
To my astonishment, I had seen a way (in theory) to make a much more general purpose program that would nevertheless be both smaller and simpler than the program I was writing. Now, I don't yet have the skill to convert this insight into practice, but at least now I know where to look in the transformation space for the right kind of optimization operations. Hopefully I'll improve with experimentation and practice. That said, the job of converting an existing program once I've had that sort of insight is not going to be easy. As I thought about what the task of applying this kind of optimization to an existing program would be like, I imagined it would be simpler to start from scratch. Then I had another idea.
Years ago,_sps_ and HB (another member of pooq), had discussed the idea of a programmer's assistant, a program that would understand the structure of a program and could transform it under your command, performing the sort of rewriting operations that you could give to an inexperienced underling, but which no editors would do for you. Operations like:
All of these are (relatively) simple structural modifications, but they can take many hours to perform, even if you have a good editor. What's more, they are 'mindless' to anyone who knows the language well enough, and can spot the gotchas, but are too tough to just whip up a macro to handle the changes. What's needed is something that has a general purpose parsing engine (perhaps a Universal Tomita Parser), and loadable grammars. We talked about writing such a beast, but we never did manage to figure out how to get it funded, despite the money it would save in lost programmer time.
So, now I was thinking about category theory, and optimization and the Programmer's Assistant, and I started wondering if the internal representation of a parsed program used by the assistant might not want to be the categories of category theory, or perhaps something related. If such a thing is reasonable, then one might imagine an assistant that could help in the generalization of a program, to optimize it in just this way (as well as in many others). I'm now in the arena of sheer speculation, but I have to wonder just how much such a system might be capable of.
In the meantime, I have an RPG program to finish.
_sps_. Actually,
_sps_ is a good place to start. I don't want to embarass the man, but he is smart and by far the best programmer I have ever met. Now, I consider myself the second best programmer I have ever met, but I will concede that in 2 or 3 cases I can think of it depends on the metric you use to measure 'best'. Now, I know that sounds like bragging, but I think its relevant to what follows. You see, I learn best by comparing my performance to others, and trying to narrow the gap. I learn what they do that I don't, and I try to borrow or steal as many useful skills as I can, incorporating them into my own toolset. When I first learned programming, I wanted to be better than my childhood friends. That was easy. Later, I tried to be better than my teachers. That wasn't too hard. Finally, I tried to be better than all of my coworkers. That was very difficult and took years of work, but I got there. When I met
_sps_ the gap between our abilities was larger (in my view at the time) than my total skill set. I was a LONG way behind him. I have tried over the years to improve, and I have narrowed the gap, but I don't think I'll ever catch up. However, a week ago, I had an idea that has finally given me an insight into one of the skills that he has, that I never understood before. That skill is the ability to optimize through generalization. While trying to explain this skill to me, he once said something along the lines of "You start by making the design able to solve more and more general cases, until the problem becomes so simple that its easy to write. You code that, and then your original application is just one use of a far more powerful program." I found it hard to understand how this could be possible. Up to that point I had always believed that handling more cases implied more complex code to deal with the cases, which implied more lines of code, making for a larger and often slower program. I have since been shown a number of examples of this technique in operation, and the results were always far smaller, faster and more powerful that any program I would have written to solve the same problem. The problem is, I could never figure out how one goes from a program spec to a design for a tiny, general purpose program that just happens to be able to fulfil the spec.
A few days ago, I got my first inkling of how one would go about doing that, and how one might even attempt to automate the process. I was working on a simple program to generate star systems for a role-playing game. For the first pass I wasn't thinking about efficiency or good design. I had decided to simply copy a pencil-and-paper generation system that I knew about, and worry about efficiency once I decided whether or not I liked the statistical results it produced.
As I worked, I couldn't help but notice places where I could optimize. Many subroutines performed a small data generation or display task, dependant upon certain constraints. The details in all the cases were different, but the general structure was similar. Had I been worried about efficiency or code size (rather than verifing that what I was building followed the paper rules) I would have moved more of the data into tables, and pruned the routines down to 2 or 3 varients. I might then have gone further and factored out the differences in the routines and built a code table to handle the differences. The result would have been a structure traversal routine, a node engine, and a whole bunch of data and code tables that represented the relationships I was trying to build.
Instead, I just kept adding new routines, testing them out, and idly thinking about the general shape of the structure I was building. Suddenly I noticed that the program had a rough fractal shape. That is, it was to a degree self-similar. Not only were many of the routines similar to each other, but their heirarchical relationships were echoed at various scales both in how the types related to each other, and how the routines called each other. In fact, the program as a whole had a resemblence to any one of the major leaf routines.
Now, I don't know much about category theory, but I do understand (in theory, if not in practice) how it can depict arbitrary mathematical relationships as graphs of dots and arrows. I started trying to imagine what a category-theory analysis of my current program would show. I suspected that it would be a series of similar graphs, linked by a few connections. Now, my normal optimizaton technique would amount to finding the largest subgraph that was common to the majority of graphs, factoring it out, and replacing it in each case with a link to the removed graph. I would continue doing this util the point of diminishing returns.
Instead, as I looked at this structure in my mind's eye, I had a new idea. Instead of factoring the structures, my sense of symmetry asked what would happen if I added to all the subgraphs, so that the fractal shape was exactly self similar, not just aproximately so. This would be the equivalent of adding a bunch of code, but it would look much prettier in my mind, because all of the irregularities would go away, and the result would be more balanced. As I contemplated this idea, I saw that the results had another property common to fractals -- it could be generated by a much simpler function. In essense, all of the self-similar parts (which now composed the whole structure) could be collapsed into a single meta-recursive leaf node that called itself in various ways to produce all of the needed functionality.
To my astonishment, I had seen a way (in theory) to make a much more general purpose program that would nevertheless be both smaller and simpler than the program I was writing. Now, I don't yet have the skill to convert this insight into practice, but at least now I know where to look in the transformation space for the right kind of optimization operations. Hopefully I'll improve with experimentation and practice. That said, the job of converting an existing program once I've had that sort of insight is not going to be easy. As I thought about what the task of applying this kind of optimization to an existing program would be like, I imagined it would be simpler to start from scratch. Then I had another idea.
Years ago,
_sps_ and HB (another member of pooq), had discussed the idea of a programmer's assistant, a program that would understand the structure of a program and could transform it under your command, performing the sort of rewriting operations that you could give to an inexperienced underling, but which no editors would do for you. Operations like:- Take a global variable, make it local, and pass it down into all of the routines where its needed.
- Take a variable that is used in two different ways in a single scope, and split it into two independant variables.
- Take a large unwieldy structure and split it into several smaller structures, changing all of the code so it still worked.
- Given three similar routines, parameterize their differences and write a macro that can generate them given the right parameters. Replace the routines by invocation of the macros.
- Add extra control variables and/or other constructs to eliminate a goto statement, and then simplify the resulting code.
All of these are (relatively) simple structural modifications, but they can take many hours to perform, even if you have a good editor. What's more, they are 'mindless' to anyone who knows the language well enough, and can spot the gotchas, but are too tough to just whip up a macro to handle the changes. What's needed is something that has a general purpose parsing engine (perhaps a Universal Tomita Parser), and loadable grammars. We talked about writing such a beast, but we never did manage to figure out how to get it funded, despite the money it would save in lost programmer time.
So, now I was thinking about category theory, and optimization and the Programmer's Assistant, and I started wondering if the internal representation of a parsed program used by the assistant might not want to be the categories of category theory, or perhaps something related. If such a thing is reasonable, then one might imagine an assistant that could help in the generalization of a program, to optimize it in just this way (as well as in many others). I'm now in the arena of sheer speculation, but I have to wonder just how much such a system might be capable of.
In the meantime, I have an RPG program to finish.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-09-08 09:04 pm (UTC)When Hendrik describes me as a radical nominalist, he's talking not about my philosophy but my mentation. I really do take the identity of indiscernables as a mentational primitive, and do so under all quotients; you've heard me say "I only believe in anything up to isomorphism," but perhaps this kind of software example is what it takes to make that phrase meaningful to someone other than myself. I don't discard possible collapses of concepts because they differ in 'kind', and in fact I don't devote much mental space or effort to maintaining 'kind' data at all. (You'll notice that I find the absence of higher order types and recursive function type signatures in programming languages to be obviously problematic. Metarecursion and hyperrecursion are basic design patterns. Which is why OO is fatally limited and all known diagramming techniques suck, by the way.) It doesn't matter what I'm thinking about at all, most of the effort goes into collapsing ideas together rather than teasing them apart. And then things start to look simple and 'easy' (that is: merely arbitrarily tedious to get right) and you can't understand why everyone goes around dumbing themselves by inventing distinctions where there aren't any, and you know that you're now an annoying old fart ;).
The philosophical puzzle, of course, is whether the world I inhabit, in which things just collapse together into simpler structures, is 'real' or whether it's an effect of my methodology. But I have the idea that it doesn't matter, because I only experience phonemena that fall within my computational class; everything else is 'randomness'. To get efficient software, you need to take the same perspective, but 'be' the computer: since the only things you can compute efficiently are things that can be efficiently computed, why not classify the worldin terms of what can be computed efficiently and how, and let the 'kinds' go hang?
Leibniz, Hume, Kolmogorov, Goedel, Galois, and maybe a little Darwin for fixed points, you know?
no subject
Date: 2004-09-08 09:49 pm (UTC)no subject
Date: 2004-09-09 10:26 am (UTC)Its still a worthwhile project.
no subject
Date: 2004-09-09 10:39 am (UTC)