July 2004 - small-cl-src-discuss@lists.common-lisp.net

[Small-cl-src-discuss] Re: WITH*
by Dirk Gerrits 16 Jul '04

16 Jul '04

Marco Baringer <mb(a)bese.it> writes: > ;;;; Alleviate deep nesting. Suggestions for a better name are welcome. Just a little nit: this seems like an interesting idea in principle, but the example macro call you list is wider than its listed expansion. ;) I don't really have a problem with deep nesting except for its effect on line width, so the example seems unconvincing to me. Regards, Dirk Gerrits

1 0

[Small-cl-src-discuss] Re: packet.lisp, version 2
by Eric Marsden 16 Jul '04

16 Jul '04

Nifty! I played around with this a little, trying to get it to decode packets that I saved using tcpdump's "-w" option. I used the following two functions to read the pcap file. This is throwing away some information that is present in the pcap framing, such as frame number, arrival time, delta since previous packet etc. It also seems to throw away the Ethernet type: reading http://www.hw-server.com/ethernet#link_layer I discovered that there are two Ethernet formats, the old "Ethernet II" format and the IEEE 802.3 format. They aren't quite equivalent, so for Ethernet II packets GRAB-ETHERNET-HEADER is reading what it thinks is the protocol but is in fact LLC data. (defun pcap-file-frames (pathname) (let ((frames (list))) (block reading (with-open-file (raw pathname :direction :input :element-type 'octet) ;; skip over the pcap per-file header (dotimes (i 24) (read-byte raw)) (loop ;; skip over the per-frame header (dotimes (i 12) (unless (read-byte raw nil nil) (return-from reading))) ;; read the frame length (let* ((frame-length (read-uint32 raw)) (frame (make-array frame-length :element-type 'octet))) (read-sequence frame raw) (push frame frames))))) (reverse frames))) (defun decode-pcap-file (pathname) (loop :for frame :in (pcap-file-frames pathname) :collect (decode (coerce frame 'buffer)))) STRUCTURE-SYMBOL-NAMES should be written as follows to avoid problems with *PRINT-CASE*: (defun structure-symbol-names (name) "Return all the interesting symbols generated by DEFSTRUCT for NAME. Assumes a FOO type name, MAKE-FOO constructor, and FOO-P predicate to avoid excessively low-level introspection." (list* name (find-symbol (concatenate 'string (symbol-name name) "-P")) (find-symbol (concatenate 'string "MAKE-" (symbol-name name))) (structure-accessors name))) Furthermore as I mentioned to Luke on IRC, I think this would benefit from splitting out into multiple files: a README, a package file, a test file, a system-definition file etc. -- Eric Marsden <URL:http://www.laas.fr/~emarsden/>

1 0

[Small-cl-src-discuss] Re: [Small-cl-src] combinations and permutations (was: Small, occasionally handy piece of code)
by Ingvar 09 Jul '04

09 Jul '04

> "Steven E. Harris" <seharris(a)raytheon.com> writes: > > > I wrote one a while ago that may cons less because it requires use > > of vectors to represent the sequences. > > Following up to myself, if you're interested, I also have similar code > to produce permutations from a source vector, though the permutation > algorithm operates destructively in-place on the source sequence. > > It's been about six months since I was doing the analysis for this > code, but I recall some interesting interdependencies between > combinations and permutations. Unfortunately my notes are at home > right now. An interesting variation for generating the Nth permutation of a list L is: (defun excise (number args) (declare (type fixnum number)) (cond ((<= number 0) (cdr args)) (t (cons (car args) (excise (1- number) (cdr args)))))) (defun permute (list num &optional accumulator) (if (null list) (nreverse accumulator) (let* ((length (length list)) (nth (mod num length)) (remainder (rem num length))) (permute (excise nth list) remainder (cons (nth nth list) accumulator))))) * (loop for n from 0 to 5 collect (permute '(1 2 3) n)) ((1 2 3) (2 3 1) (3 1 2) (1 2 3) (2 3 1) (3 1 2)) So far, the only piece of code where I've needed to generate one of all possible permutations for a list has been in a Mandelbrot generator, where I use that for a recursive call to generate smaller and smaller squares on the screen, ignoring to recurse if and only if the sides of the square end up having the same iteration depth before heading for infinity, thus making the whole process somewhat more pleasurable to watch (I *think* that is in the Mandelbrot generator among the SB-CLX demos). //Ingvar

1 0

[Small-cl-src-discuss] combinations and permutations (was: Small, occasionally handy piece of code)
by Steven E. Harris 09 Jul '04

09 Jul '04

[I apologize for posting this article incorrectly first to the "code" list rather than the "discuss" list.] "Steven E. Harris" <seharris(a)raytheon.com> writes: > I wrote one a while ago that may cons less because it requires use > of vectors to represent the sequences. Following up to myself, if you're interested, I also have similar code to produce permutations from a source vector, though the permutation algorithm operates destructively in-place on the source sequence. It's been about six months since I was doing the analysis for this code, but I recall some interesting interdependencies between combinations and permutations. Unfortunately my notes are at home right now. For example, one can compute /how many/ permutations exist for a full draw from a set (n!), or how many permutations exist for a draw k from a set (n!/(n - k)!), but computing how many combinations exist for any draw k is dependent upon the related permutation count (P/k!).¹ However, to actually come up with the /specific/ permutations and combinations, the dependency is reversed. One can come up with combinations in any draw k independently. One can also come up with permutations for a full draw independently. But to come up with the permutations for some draw k, one must first generate the combinations of draw k, then permute each of those combinations as a full draw. The apparent independence of the full draw permutations is due to there being only one combination to permute for a full draw. Footnotes: ¹ http://www.themathpage.com/aPreCalc/permutations-combinations.htm -- Steven E. Harris :: seharris(a)raytheon.com Raytheon :: http://www.raytheon.com

1 0