Make

August 7, 2012

We begin with two caveats: our make doesn’t provide all the features of the real make (for instance, there are no macros), and it doesn’t really perform the associated commands (it writes them to the output, instead). So this is a toy, to show how the whole can be done, not a drop-in replacement for the real make. Here we define exec as display, so it simply writes the commands to the output; the real make would use the shell command instead of display so that the commands are actually executed.

(define (exec commands)
  (when (pair? commands)
    (display (car commands)) (newline)
    (exec (cdr commands))))

We represent the makefile by a list of triples (three-elements lists) with the target name in the car, a list of precedents in the cadr, and a list of commands in the caddr. The format of the makefile is constrained: a target is a line containing a name, a colon, and a possibly-null list of predecessors, a line beginning with a horizontal tab is a command associated with the current target, a blank line is ignored, and anything else causes an error:

(define (read-makefile makefile)
  (define (but-last str)
    (list->string (reverse (cdr (reverse (string->list str))))))
  (define (end-first-word line)
    (let ((words (string-split #\space line)))
      (if (not (positive? (length words))) #\space
        (car (reverse (string->list (car words)))))))
  (define (get-name line)
    (but-last (car (string-split #\space line))))
  (define (get-preds line)
    (cdr (string-split #\space line)))
  (with-input-from-file makefile
    (lambda ()
      (let loop ((line (read-line)) (name "") (preds (list))
                 (cmds (list)) (rules (list)))
        (cond ((eof-object? line)
                (if (null? cmds) rules
                  (cons (list name preds (reverse cmds)) rules)))
              ((char=? (end-first-word line) #\:) ; new rule
                (loop (read-line) (get-name line) (get-preds line) (list)
                  (if (zero? (string-length name)) (list)
                    (cons (list name preds (reverse cmds)) rules))))
              ((and (positive? (string-length line))
                    (char=? (string-ref line 0) #\tab)) ; command
                (loop (read-line) name preds
                  (cons (substring line 1 (string-length line)) cmds) rules))
              (else (loop (read-line) name preds cmds rules)))))))

The code is complicated because the format is strict; if you have trouble reading it (I had trouble writing it), take your time, getting each piece firmly in mind before going on to the next. The result of read-makefile on the sample makefile is:

(("print" () ("pr prog.h a.c b.c c.y"))
  ("c.c" ("c.y") ("yacc c.y" "mv y.tab.c c.c"))
  ("c.o" ("c.c") ("cc -c c.c"))
  ("b.o" ("prog.h" "b.c") ("cc -c prog.h b.c"))
  ("a.o" ("prog.h" "a.c") ("cc -c prog.h a.c"))
  ("prog" ("a.o" "b.o" "c.o") ("cc a.o b.o c.o -ly -o prog")))

We compare the ages of two files by getting from the operating system a list of files in order by modification date, newest first; on Unix systems, that can be done by the Unix command ls -t. File x is newer than file y if it precedes file y in the list. The system, file-exists? and delete-file functions are non-standard, but most Scheme implementations provide them; the code shown below works in Chez Scheme. Some Scheme implementations also provide a way to stat a file, which should be used in preference to system if it is available:

(define (newer? x y)
  (define (mktemp prefix)
    (let loop ((n 0))
      (let ((file (string-append prefix (number->string n))))
        (if (file-exists? file) (loop (+ n 1)) file))))
  (let ((tempfile (mktemp "temp")))
    (system (string-append "ls -t >" tempfile))
    (let ((p (open-input-file tempfile)))
      (define (return val)
        (close-port p) (delete-file tempfile) val)
      (let loop ((z (read-line p)))
        (cond ((eof-object? z) (return #f))
              ((string=? z x) (return #t))
              ((string=? z y) (return #f))
              (else (loop (read-line p))))))))

We’re ready now to write the recursive updater. The code is deceptively simple. An auxiliary function is used to check if the target is in the makefile, since it is called twice.

(define (make target makefile)
  (define (check target makefile)
    (if (not (or (file-exists? target) (assoc target makefile)))
      (error 'make "don't know how to make " target)))
  (check target makefile)
  (if (all? (lambda (pred) (newer? pred target)) (cadr (assoc target makefile)))
      (string-append target " is up to date")
      (let loop ((target target) (preds (cadr (assoc target makefile))))
        (if (null? preds)
            (exec (caddr (assoc target makefile)))
            (if (newer? (car preds) target)
                (loop target (cdr preds))
                (begin (loop (car preds) (cadr (assoc (car preds) makefile)))
                       (loop target (cdr preds))))))))

Here’s an example, assuming that file “makefile” contains the lines of the example and that this is the first time we run make on the target prog, and assuming that exec is changed to execute the commands instead of merely display them:

> (define makefile
    (read-makefile "makefile"))
> (make "prog" makefile)
cc -c prog.h a.c
cc -c prog.h b.c
yacc c.y
mv y.tab.c c.c
cc -c c.c
cc a.o b.o c.o -ly -o prog
> (system "touch c.y")
0
> (make "prog" makefile)
yacc c.y
mv y.tab.c c.c
cc -c c.c
cc a.o b.o c.o -ly -o prog
> (make "prog" makefile)
prog is up to date

We used string-split from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/Q5bDIyqX.

About these ads

Pages: 1 2

2 Responses to “Make”

  1. cage said

    Hello,
    As I am trying to learn common lisp i found your site very fun and useful; here is
    my attempt..

    (note: I am using tabular character as command separator)

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: