request comments: simple c program builder in lisp

Hello,

I am fairly new to Lisp and am trying to write a simple build tool for
C
files in order to learn lisp. I am not really interested in any
advanced
features for the build system yet as the main intent is to learn Lisp.

I am hoping that some of the lisp experts here can comment on the
style
of the program below and possibly give suggestions / pointers to what
may
be the "lispy" way of doing things.

I thought it may be best to send this across for comments before I
walk
too far down the wrong path and this becomes a 'code bomb'

Thanks very much.
Parth

Here is a sample interaction of what I have so far (I use clisp):

[1]> (load "packages.lisp")
; loading system definition from /usr/s
.............. snip ..................
; registering #<SYSTEM MD5 #x206F9E56> as MD5
T
[2]> (load "clsi.lisp")
T
[3]> (in-package :clsi)
#<PACKAGE CLSI>
CLSI[4]> (setf *p* (program "test" '("a.c" "b.c" "c.d")))
(:NAME "test" EPS
((:NAME "a.o" EPS ((:NAME "a.c" EPS NIL :TYPE CFILE)) :TYPE
OFILE)
(:NAME "b.o" EPS ((:NAME "b.c" EPS NIL :TYPE CFILE)) :TYPE
OFILE)
(:NAME "c.d" EPS NIL :TYPE NIL))
:TYPE EXE)
CLSI[5]> (build *p*)
[build] a.c: gcc -o a.o a.c
[build] a.o: nothing to do: a.o
[build] b.c: gcc -o b.o b.c
[build] b.o: nothing to do: b.o
[build] c.d: nothing to do: c.d
[build] test: gcc -o test a.o b.o c.d
NIL
CLSI[6]>

Source Code Listing
===================
; clsi.lisp (sorry for the somewhat long listing :P)

(defpackage #:clsi
(:use :common-lisp :fad pcre :md5)
(:export #:search-replace-last-re
#:search-replace-re
#:concat-string-from-list
#:checksum
#:make-file))

(in-package #:clsi)

;; ===============
;; Utility Methods
;; ===============

(defun concat-strings-from-list (l)
"take all strings in the list and concatenate them
adding a space in between.
e.g.: ('aa' 'bb' 'cc') => 'aa bb cc'"
(reduce #'(lambda (x y) (concatenate 'string x " " y))
l))

(defun find-last-subst-pos-re (sub str)
"returns position of last sub-string.
e.g.: 'xx' 'abcxxyy' => 3"
(let ((m (all-matches sub str)))
(first (last (butlast m)))))

(defun search-replace-re (old new str &key (start 0))
"replace old with new in str. old and new are regular
expressions"
(concatenate 'string ; need to use concat as regex-
replace
(subseq str 0 start) ; drops begining when start is not
0
(regex-replace old str new :start start)))

(defun search-replace-last-re (old new str)
"replace the last occurance of old with new in str.
used to change file extension in strings.
e.g.: '\.c' '\.o' 'test.c' => 'test.o'"
(let ((pos (find-last-subst-pos-re old str)))
(when (numberp pos)
(search-replace-re old new str :start pos))))

(defun checksum (pathname)
(md5sum-file (pathname-as-file pathname)))


;;; ================================
;;; File Extension and Type Handling
;;; ================================

(defun extention-p (ext name)
"return if name ends in ext. used to check file extension"
(let ((ext-len (length ext)))
(equal ext (subseq name (- (length name) ext-len)))))

(defun filetype-p (name type)
"check if file is of a 'type'"
(cond ((equal type 'cfile) (extention-p ".c" name))
((equal type 'ofile) (extention-p ".o" name))
((equal type 'hfile) (extention-p ".h" name))
(t nil)))

(defun filetype? (name)
"return the 'type' of file based on extension"
(cond ((extention-p ".c" name) 'cfile)
((extention-p ".o" name) 'ofile)
((extention-p ".h" name) 'hfile)
(t nil)))

;;; ===================
;;; File Representation
;;; ===================

(defun make-file (&key name (deps nil) (type nil))
(list :name name :deps deps :type (filetype? name)))

(defun make-file-list (names)
(mapcar #'(lambda (x) (get-intermediate-file (make-file :name x)))
names))

(defun get-intermediate-file (file)
"takes a file and generates a plist for the possible intermediate
file once this is processed. For example, for a test.c plist
it will create a test.o plist. When there is no intermediate file,
input is returned"
(let ((name (getf file :name))
(type (getf file :type)))
(cond ((equal type 'cfile) (make-file
:name (search-replace-last-re "\.c"
"\.o" name)
:deps (list file)
:type 'ofile))
(t file))))

; Usage:
; (setf *p* (program "test" '("a.c" "b.c" "c.d")))
; (build *p*)

(defun program (target sources)
"top level program creation function. returns a tree that represents
files and their dependencies leading to the toplevel program."
(let ((target-file (make-file :name target)))
(setf (getf target-file :deps) (make-file-list sources))
(setf (getf target-file :type) 'exe)
target-file))

(defun build (program)
(let ((deps (getf program :deps))
(name (getf program :name))
(type (getf program :type)))
(cond ((null deps) (format t "[build] ~A: " name)
(build-file program))
(t (mapcar #'build deps)
(format t "[build] ~A: " name)
(build-file program)))))

; "test.c" => "test.o"
(defun cfile->ofile (name)
(search-replace-last-re "\.c" "\.o" name))

; deps-(<file0>, <file1>, <file2>) => ("depname0" "depname1"
"depname2")
(defun get-dep-names (file)
(let ((deps (getf file :deps)))
(mapcar #'(lambda (x) (getf x :name)) deps)))

(defun build-file (file)
"print the string needed to build the file based on file type"
(let ((type (getf file :type))
(name (getf file :name))
(deps (getf file :deps)))
(cond ((equal type 'cfile)
(format t "~A~%" (concat-strings-from-list
(list "gcc -o" (cfile->ofile name)
name))))
((equal type 'ofile)
(format t "nothing to do: ~A~%" name))
((equal type 'exe)
(format t "~A~%" (concatenate 'string
"gcc -o "
name " "
(concat-strings-from-list
(get-dep-names file)))))
(t (format t "nothing to do: ~A~%" name)))))

Hello Parth,

some suggestions:

> (defun concat-strings-from-list (l)
> "take all strings in the list and concatenate them
> adding a space in between.
> e.g.: ('aa' 'bb' 'cc') => 'aa bb cc'"
> (reduce #'(lambda (x y) (concatenate 'string x " " y))
> l))

LIST->STR. Separator should be adjustable via key.

You don't need the #' here.

> (defun find-last-subst-pos-re (sub str)
LAST-SUBSTR-POS

> (defun search-replace-re (old new str &key (start 0))

REPLACE-RE


> (defun search-replace-last-re (old new str)

REPLACE-LAST-RE


> (let ((pos (find-last-subst-pos-re old str)))
> (when (numberp pos)

Haven't looked closely at this function; maybe

(when pos
...)

would suffice?


> (defun extention-p (ext name)

HAS-EXTENSION. EXTENSION-P would by an unary function that
checks whether its one arg is an extension.


> "return if name ends in ext. used to check file extension"
> (let ((ext-len (length ext)))
> (equal ext (subseq name (- (length name) ext-len)))))

The LET is gratuitous here, just use LENGTH directly.


> (defun filetype-p (name type)

FILE-OF-TYPE


> "check if file is of a 'type'"
> (cond ((equal type 'cfile) (extention-p ".c" name))
> ((equal type 'ofile) (extention-p ".o" name))
> ((equal type 'hfile) (extention-p ".h" name))
> (t nil)))

Use EQ to compare symbols.
Rewrite the COND with the help of CASE.


> (defun filetype? (name)

TYPE-OF-FILE, FILE-TYPE, FILE-TYPE-OF

Don't use the suffix ? on anything but Boolean functions.


> "return the 'type' of file based on extension"
> (cond ((extention-p ".c" name) 'cfile)
> ((extention-p ".o" name) 'ofile)
> ((extention-p ".h" name) 'hfile)
> (t nil)))

Don't do this.

Create an ALIST of extensions and symbols:

(defparameter *extension-map* '((".c" . CFILE) (".o" . OFILE)
(".h" . HFILE)))

or better yet

(defparameter *extension-map* '((".c" . SOURCE) (".o" . OBJECT)
(".h" . HEADER)))


(defun fextension->symbol (ext)
(assoc ext *extension-map* :test #'equal)) ; or EQUALP depending on
the file system...


> (defun make-file (&key name (deps nil) (type nil))
> (list :name name :deps deps :type (filetype? name)))

NAME is mandatory here, move it out of the key section.


> (cond ((equal type 'cfile) (make-file

Use EQ


> (let ((target-file (make-file :name target)))
> (setf (getf target-file :deps) (make-file-list sources))
> (setf (getf target-file :type) 'exe)
> target-file))

Whatcha doing here?


> (defun build (program)
> (let ((deps (getf program :deps))
> (name (getf program :name))
> (type (getf program :type)))

Uh, might be worth defining a struct with accessors for PROGRAM.


> (cond ((null deps) (format t "[build] ~A: " name)
> (build-file program))
> (t (mapcar #'build deps)
> (format t "[build] ~A: " name)
> (build-file program)))))

Use IF for binary branches.


> ; "test.c" => "test.o"
> (defun cfile->ofile (name)
> (search-replace-last-re "\.c" "\.o" name))

Define a function to change the extension and abstract the
stuff more:

(defun SOURCE-NAME->OBJECT-NAME ...)


> (defun get-dep-names (file)
> (let ((deps (getf file :deps)))
> (mapcar #'(lambda (x) (getf x :name)) deps)))

Just use DEPS inline.


> (defun build-file (file)
> "print the string needed to build the file based on file type"

I suppose this is a simulator, then...


> (let ((type (getf file :type))
> (name (getf file :name))
> (deps (getf file :deps)))

Again, use accessors.


> (format t "~A~%" (concat-strings-from-list
> (list "gcc -o" (cfile->ofile name)
> name))))
> ((equal type 'ofile)
> (format t "nothing to do: ~A~%" name))
> ((equal type 'exe)
> (format t "~A~%" (concatenate 'string
> "gcc -o "
> name " "
> (concat-strings-from-list
> (get-dep-names file)))))
> (t (format t "nothing to do: ~A~%" name)))))

Another ALIST mapping file types to actions would be appropriate.

You can also drag out the FORMAT call:

(apply #'format t "~A~%"
(cond ...))

HTH,

Leslie

* "Leslie P. Polzer" <6b367c6e-87a0-4c7d-bfda-424814ef7004@k37g2000hsf.googlegroups.com> :
Wrote on Sat, 14 Jun 2008 07:55:13 -0700 (PDT):

I think you can ignore most of Leslie P. Polzer's style advice safely as
his personal style preference.
--
Madhu

parth.malwankar@gmail.com writes:
> ;;; ===================
> ;;; File Representation
> ;;; ===================

Good.


> (defun make-file (&key name (deps nil) (type nil))
> (list :name name :deps deps :type (filetype? name)))

So far, so good.


> (defun program (target sources)
> "top level program creation function. returns a tree that represents
> files and their dependencies leading to the toplevel program."
> (let ((target-file (make-file :name target)))
> (setf (getf target-file :deps) (make-file-list sources))
> (setf (getf target-file :type) 'exe)

Why do you commit to this representation? Are you sure this data
structure is the most adapted?


It would be better of you introduced some abstraction here.

One easy way to do so is to use DEFSTRUCT.

(defstruct file name deps type)

will provide you with a constructor make-file, accessors file-name,
file-deps, file-type, and other niceties.

If you want to keep the data as lists:
(defstruct (file (:type list)) name deps type)
If you prefer vectors:
(defstruct (file (:type vector)) name deps type)

But structures are ok, since they have a print-readably
representation:
#S(FILE :NAME "test.c" EPS (#S(FILE :NAME "test.h" EPS NIL :TYPE C-HEADER)) :TYPE C-SOURCE)

If you need to do some special processing in the constructor, or in
the copier, or the printer you can also define it:
(defstruct (file (:constructor %make-file)) ...)
(defun make-file (&key name deps type)
(%make-file :name name :deps deps :type (or type (filetype? name))))





But now, since the rest of your program will be using these functional
abstractions: make-file, file-name, file-deps, file-type, ..., it will
be independant of your representation choices.





If you need to use CLOS objects instead of lists, you will only
replace the defstruct form by:

(defclass file ()
((name :accessor file-name :initarg :name :type string)
(deps :accessor file-deps :initarg :deps :initform '() :type list)
(type :accessor file-type :initarg :initform '())))
(defmethod initialize-instance :after ((self file) &rest initargs &key &allow-other-keys)
(setf (file-type self) (or (file-type self) (filetype? (file-name self))))
self)

and done.


--
__Pascal Bourguignon__ http://www.informatimago.com/

COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.

Den Sat, 14 Jun 2008 20:48:30 +0530 skrev Madhu:

> * "Leslie P. Polzer"
> <6b367c6e-87a0-4c7d-bfda-424814ef7004@k37g2000hsf.googlegroups.com> :
> Wrote on Sat, 14 Jun 2008 07:55:13 -0700 (PDT):
>
> I think you can ignore most of Leslie P. Polzer's style advice safely as
> his personal style preference.

On the contrary, most of his remarks are spot on, very little is what I'd
consider "personal style preference".

Cheers,
Maciej

Maciej Katafiasz wrote:
> Den Sat, 14 Jun 2008 20:48:30 +0530 skrev Madhu:
>
>> * "Leslie P. Polzer"
>> <6b367c6e-87a0-4c7d-bfda-424814ef7004@k37g2000hsf.googlegroups.com> :
>> Wrote on Sat, 14 Jun 2008 07:55:13 -0700 (PDT):
>>
>> I think you can ignore most of Leslie P. Polzer's style advice safely as
>> his personal style preference.
>
> On the contrary, most of his remarks are spot on, very little is what I'd
> consider "personal style preference".
>
> Cheers,
> Maciej


Well there are some not-unary predicates defined in the common lisp
library. Like typep, slot-boundp ...

Also all caps symbols are ugly.

On the other hand, using a-lists as decision tables is very lispy.

But i would use clos objects and generic functions for type dispatching,
specially in this case where speed is really not important at all.

(defclass file ()
(...))

(defclass c-file (file)
(..))

(defclass object-file (file)
(..))

(defun build-file (file)
(format nil "..." (build-file-action file)

(defmethod build-file-action ((file c-file))
...)

(defmethod build-file-action ((file object-file))
...)

this way you can extend it for ... err ... resource files, without
touching your existing functions ever again.

the concat-strings-from-list function has horrible complexity it's like
O(n!) or something. I would leave the strings in their list, then write
to a stream. use with-output-to-string. Write an interleave function to
add all these spaces in between. You'll be able to use it again some day !

Sacha

> Also all caps symbols are ugly.

It's good that you mention this. I just put the symbols uppercase
to make them stand-out in text. There was no intention on my
part to suggest actually writing your CL code that way...

Leslie

* Maciej Katafiasz <g30trr$e1c$1@news.net.uni-c.dk> :
Wrote on Sat, 14 Jun 2008 17:07:07 +0000 (UTC):
|> I think you can ignore most of Leslie P. Polzer's style advice safely as
|> his personal style preference.
|
| On the contrary, most of his remarks are spot on, very little is what I'd
| consider "personal style preference".

I hope the OP can recognize that all the points touched on are matters
of taste, and is also competenet enough to distinguish advocacy for bad
taste from more useful coding guidelines if any show up on this thread.

--
Madhu

On Jun 15, 12:10 am, Sacha <n...@address.spam> wrote:
> Maciej Katafiasz wrote:
> > Den Sat, 14 Jun 2008 20:48:30 +0530 skrev Madhu:
>
> >> * "Leslie P. Polzer"
> >> <6b367c6e-87a0-4c7d-bfda-424814ef7...@k37g2000hsf.googlegroups.com> :
> >> Wrote on Sat, 14 Jun 2008 07:55:13 -0700 (PDT):
>
> >> I think you can ignore most of Leslie P. Polzer's style advice safely as
> >> his personal style preference.
>
> > On the contrary, most of his remarks are spot on, very little is what I'd
> > consider "personal style preference".
>
> > Cheers,
> > Maciej
>
> Well there are some not-unary predicates defined in the common lisp
> library. Like typep, slot-boundp ...
>
> Also all caps symbols are ugly.
>
> On the other hand, using a-lists as decision tables is very lispy.
>
> But i would use clos objects and generic functions for type dispatching,
> specially in this case where speed is really not important at all.
>
> (defclass file ()
> (...))
>
> (defclass c-file (file)
> (..))
>
> (defclass object-file (file)
> (..))
>
> (defun build-file (file)
> (format nil "..." (build-file-action file)
>
> (defmethod build-file-action ((file c-file))
> ...)
>
> (defmethod build-file-action ((file object-file))
> ...)
>
> this way you can extend it for ... err ... resource files, without
> touching your existing functions ever again.
>
> the concat-strings-from-list function has horrible complexity it's like
> O(n!) or something. I would leave the strings in their list, then write
> to a stream. use with-output-to-string. Write an interleave function to
> add all these spaces in between. You'll be able to use it again some day !
>
> Sacha

Thanks Leslie / Pascal / Sacha. The comments were very insightful
and helpful.

For now I have upgraded to using structs. As Sasha suggested
I would probably upgrade to classes as I add this app evolves some
more.

For the 'build-file' function which was quite ugly, I tried to
do the cleanup using an alist returning a lambda based on filetype.

Here is what I came up with. Is my implementation of this clean enough
or can something be done better (code below) ?

Thanks.
Parth


(defmacro concat-str (&rest args)
`(concatenate 'string ,@args))


(defparameter *build-cmd-map*
(list
(cons 'cfile
(lambda (f)
(concat-str "gcc -o " (cfile->ofile (unit-name f))
" " (unit-name f))))
(cons 'ofile
(lambda (f)
(concat-str"nothing to do: " (unit-name f))))
(cons 'exe
(lambda (f) (concat-str "gcc -o " (unit-name f) " "
(list->str (get-dep-names
f)))))))

(defun file->build-cmd (f)
"return the 'type' of file based on extension"
(rest (assoc (unit-type f) *build-cmd-map* :test #'equal)))

(defun build-file (file)
"print the string needed to build the file based on file type"
(funcall #'format t "~A~%"
(funcall (file->build-cmd file) file)))

>
> (defmacro concat-str (&rest args)
> `(concatenate 'string ,@args))
>

You don't need a macro for this :

(defun concat-string (&rest args)
(apply #'concatenate args))

But :

;CL-USER 12 > CALL-ARGUMENTS-LIMIT
;2047

So on my lisp implementation, your macro (my function as well) would
break for lists with over 2047 items. besides we're not quite sure on
the performance implications of such a big parameter list.

So :

(defun list->stream (list stream)
(loop for item in list
do (princ item stream)))

;pretty much the same thing, but for list of lists
(defun tree->stream (tree stream)
(loop for item in tree
if (listp item) do (tree->stream item stream)
else do (princ item stream)))

(defun interleave (list separator)
(loop for first = t then nil
for item in list
unless first collect separator
collect item))

;CL-USER 1 > (interleave '(1 2 3) #\space)
;(1 #\Space 2 #\Space 3)
; common lisp is fun, i can mix characters with numbers !
; I'm not a native english speaker, maybe intersperse would be better as
a name ?

;CL-USER 2 > (tree->stream (interleave `(1 ,(interleave '("two" three)
#\space) #\z) #\space) *standard-output*)
;1 two THREE z

;literals are way easier to read
(defparameter *build-commands*
'((c-file . build-c-file)
(object-file . build-object-file)
(exe-file . build-exe-file)))

;make it easier to change stuff
(defvar *compiler-options* '("-o"))
(defvar *compiler-name* "gcc")

;we're using lisp here, so let's work with lists !
(defun build-c-file (file)
`(,*compiler-name* ,@*compiler-options* ,(c-file->object-file
(unit-name file)) ,(unit-name file)))

(defun build-object-file (file)
`(";nothing to do for" ,(unit-name file)))

(defun build-exe-file (file)
`(,*compiler-name* ,@*compiler-options* ,(unit-name file)
,@(get-dependency-names)))

;no need to use the 'equal test as we're working with symbols
(defun file->build-file-function (file)
(cdr (assoc (unit-type file) *build-commands*)))

;still working with lists
(defun file->command (file)
(interleave (funcall (file->build-file-function file) file)
#\space)))

;still working with lists, notice how it makes this very readable
(defun files->command-list (files)
(interleave (mapcar #'file->command files)
#\newline))

now we print to a stream ... so it could be standard-output, a
string-stream (with-output-to-string) for testing, or a file, which i
guess is what you eventually want to do.

(defun files->stream (files &optional (stream *standard-output*))
(tree->stream (files->command-list files) stream))

Ok i got a little bit carried away ...

This whole thing is totally untested
We're using small functions all along as these are easier to test,
compose and understand. Doc strings are missing, which is pretty bad !

There are many ways to do things using common lisp, I like to work with
lists when generating text.

Sacha