Metalinguistic Abstraction

Computer Languages, Programming, and Free Software

KPMake: A Proposed Dependency Resolution Tool

with 3 comments

One of the insane ideas I have floating around is to write yet another Make replacement. My rationale is as follows:

  • Make is simple, but not very powerful
  • Absurd macro languages and generation facilities grant enough power for “real work,” but are painful and ugly.
  • People widely use ant, probably a step down from Make if not for the incredible dedication to tool support to make it convenient for Java somewhat.

“But wait!” you say, “haven’t you ever heard of SCons or Rake, you imbecile?”

Why yes, yes I have. The nice thing about these approaches is that they recognize that most non-trivial build-systems are going to demand the power of a “real” programming language; certainly not the looseness of shell scripting nor the inflexibility of ant buildfiles. (Quote a colleague: “it’s like Lisp, without any of the advantages of Lisp!” ) The downside is they lose out on clarity. A hand-written Makefile tends to stay very simple whereas any convoluted thing can happen in a SConstruct file (the rough equivalent to Make’s “Makefile”), leaving the user doing some head scratching as to why something-or-other happened or why-or-not something built and how or why. On the plus side, the machinery of SCons also gets you things like a “clean” target for free. Another downside is agnosticism: Makefiles, thanks to their simple nature, can be easily written to control complex toolchains that do things other than compiling programs[0]. The barrier for entry in writing a builder in SCons is considerably higher than simple rules as dictated by a Makefile such as

foo : bar baz
	cat bar baz > foo

(Yes, I realize you can use automatic variables like ‘$@’ and ‘$^’, but let’s keep it less cryptic for now)

I have been working on and off on a project that uses a Makefile to orchestrate around a dozen individual tools. Not only is it robust, but after almost a year of inactivity it’s possible to read the Makefile and recall the roles of all the tiny moving parts and how they relate to one another. I then went back and wrote documentation. But now I want to improve on Make by allowing for complex behaviors while retaining succinct, declarative syntax and keeping the system easy to debug. How do I portend to do this?

KPMake, or “Knowledge Powered Make” is one possible solution. In a nutshell: I want to leverage state of the art symbolic AI techniques to solve a relatively mundane problem of dependency resolution while including modern explanation generation facilities to increase user understanding of why any particular actions were taken and to help debug these actions. I will probably use the KM knowledge base, partially because of being exposed to it at work and partially because I know it has been successfully been used in large projects such as Vulcan Inc’s ambitious Project HALO. I also happen to know it’s available as a single lisp file and has practically no set-up or portability problems. The base package for KPMake should simply be a distribution of KM, some basic models to handle basic generic dependency resolution, and macro/procedure support to make writing KPMakefiles easier. Knowledge models to build for say, particular languages (such as a gcc or a javac model) will be distributed and maintained separately and ought to have an eye towards making things even more convenient.

A neat feature that is enabled that I didn’t include in this writing to begin with is using situation calculus to allow programmers to load, save, and debug situational traces as well as perform advanced error recovery. KM supports situational reasoning and simulations that can be used to test build scripts (and write fuzz testing!) to make sure they respond in at least a reasonable way to unexpected events as well as increasing visibility of every step of the build process: right now one generally has to do a lot of manual logging to get a trace of what’s going on or, if one is lazy, set a breakpoint and only be able to view a few slices in the process. You can also have your build engineers in India and send your broken build “core dump” abroad and mostly avoid the “well it works on my machine” scenario.

[0]: I owe my appreciation of this technique to Professor Strain. Imagine a Makefile to build the program, run the tests, spit out any pictures, compile the TeX sources, and finally deliver you a postscript file to send off to the journal. I’m sure if submissions were something that had to be done often there would be a “mail” target that’d also deliver the resultant postscript to the relevant journal(s).


Written by fdr

June 27, 2007 at 9:10 pm

Posted in lisp, projects

3 Responses

Subscribe to comments with RSS.

  1. >;;; — arithmetic —
    >;;; “What is 1 + 1?”
    >KM> (1 + 1)

    Infix notation? Man, that KM is really something.

    In all seriousness, reading the annotated transcript ( ) is pretty interesting, especially the situation stuff. I’m intrigued by KPMake.


    June 28, 2007 at 12:29 pm

  2. Yes, situation calculus is one of the cooler features that KM has and may be very useful in debugging every step in the process of doing dependency resolution. Right now (as I do it, anyway) what generally happens is that someone will notice a bug by using the debugger, break (as in interrupt) the build process, fix it, and move on. It’d be nice if instead one could just dump the entire KB — which includes the situations — and then poke at it and its situations to figure things out.

    It’s also useful if you want to run a simulation, so it’s a lot easier to write a test driver for your build files which in all seriousness are getting as complicated as small to moderate sized programs.


    June 28, 2007 at 8:21 pm

  3. Not sure if it is what you want, but Jam (written by someone at Perforce) is quite a nifty make replacement with quite a lot of speed and power. I recommend everyone interested in make replacements to take a peak at it.


    August 5, 2007 at 10:46 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: