346 views

Skip to first unread message

Oct 11, 2005, 1:05:50 AM10/11/05

to

I was wondering if there is a quick and dirty way to find the rank of

the nth smallest element in lisp. That is for example finding the 2nd

smallest element in a list.

the nth smallest element in lisp. That is for example finding the 2nd

smallest element in a list.

I tried something like this:

The idea is get the minimum, if asked for the 1st smallest stop there,

else throw away the smallest and search the new list for the new

smallest (overall second smallest) and so on until you get the nth

smallest.

The problem that I am having is not getting this number, but knowing

the nth's index (position) relative to the initial list (I will call

the index realtive to the initial list the absolute index and the index

relative to the current list the relative index).

I tried saving the position of the first min relative to the overall

list, then when I find the next min (2nd smallest) I compare this

relative index with the previous (absolute index) if the relative index

is greater or equal that the absolute index add one to the relative

index to make it into the new absolute index (note if the relative

index is smaller than the previous absolute index then the relative

index automatically becomes the new absolute index). The problem is

that this doesn't work if for example say the 4th smallest element

lands in an absolute index after the 1 and 2 smallest, but BEFORE the

third.

Any ideas?

note: getNextBest is 0 for smallest, 1 for second smallest and so on

(defun getMin (children-scores getNextBest)

(setf min 100)

(dotimes (j (+ getNextBest 1)) ; repeat for nth smallest element

(dotimes (i (list-length children))

(when (< (nth i children-scores) min)

(setf min (nth i children-scores))

(if (or (> index temp-index) (= index temp-index))

(setf index (+ i j)) ;; this doesnt work in general

)

(setf index i)

)

) ; end inner dotimes

(if (> getNextBest 0)

(setf temp-index index)

(setf children-scores (remove min children-scores))

)

) ; end outer dotimes

index

)

Oct 11, 2005, 2:01:48 AM10/11/05

to

tachyon <pma...@gmail.com> wrote:

>The problem that I am having is not getting this number, but knowing

>the nth's index (position) relative to the initial list (I will call

>the index realtive to the initial list the absolute index and the index

>relative to the current list the relative index).

I'd make a list of pairs (element . rank) from the original list,

and sort that one, keyed by element.

mkb.

Oct 11, 2005, 8:38:31 AM10/11/05

to

"tachyon" <pma...@gmail.com> writes:

> I was wondering if there is a quick and dirty way to find the rank of

> the nth smallest element in lisp. That is for example finding the 2nd

> smallest element in a list.

>

> I tried something like this:

> The idea is get the minimum, if asked for the 1st smallest stop there,

> else throw away the smallest and search the new list for the new

> smallest (overall second smallest) and so on until you get the nth

> smallest.

> The problem that I am having is not getting this number, but knowing

> the nth's index (position) relative to the initial list (I will call

> the index realtive to the initial list the absolute index and the index

> relative to the current list the relative index).

>

> I tried saving the position of the first min relative to the overall

> list, then when I find the next min (2nd smallest) I compare this

> relative index with the previous (absolute index) if the relative index

> is greater or equal that the absolute index add one to the relative

> index to make it into the new absolute index (note if the relative

> index is smaller than the previous absolute index then the relative

> index automatically becomes the new absolute index). The problem is

> that this doesn't work if for example say the 4th smallest element

> lands in an absolute index after the 1 and 2 smallest, but BEFORE the

> third.

> Any ideas?

Remember that sort is n log n, so sorting the whole list is

competitive with doing a linear scan to find the least

element when you do about log n scans.

Here we test on a list of 100000 random numbers.

Scanning 16 times to find the 16 smallest takes about the

same time as sorting the whole lot

* (time (setf *r* (nth-smallest *t* 16)))

Compiling LAMBDA NIL:

Compiling Top-Level Form:

Evaluation took:

4.72 seconds of real time

4.686091 seconds of user run time

5.2e-5 seconds of system run time

[Run times include 0.61 seconds GC run time]

0 page faults and

14389248 bytes consed.

((44513 . 2.5510788e-4) (64456 . 4.1604042e-4) (36883 . 5.161762e-4)

(70989 . 5.507469e-4) (14280 . 8.1181526e-4) (99127 . 0.0010204315)

(72454 . 0.0010955334) (22152 . 0.0014972687) (5714 . 0.0015246868)

(79641 . 0.0016987324) ...)

* (time (setf *s* (sort (add-index *t*) #'< :key #'cdr)))

Compiling LAMBDA NIL:

Compiling Top-Level Form:

Evaluation took:

4.8 seconds of real time

4.697565 seconds of user run time

0.054731 seconds of system run time

[Run times include 0.7 seconds GC run time]

0 page faults and

14112936 bytes consed.

((44513 . 2.5510788e-4) (64456 . 4.1604042e-4) (36883 . 5.161762e-4)

(70989 . 5.507469e-4) (14280 . 8.1181526e-4) (99127 . 0.0010204315)

(72454 . 0.0010955334) (22152 . 0.0014972687) (5714 . 0.0015246868)

(79641 . 0.0016987324) ...)

(defun indexed-min (list)

(reduce (lambda(smallest another)

(if (< (cdr smallest)

(cdr another))

smallest

another))

list))

(defun add-index (list)

(loop for i from 1 and x in list collect (cons i x)))

(defun nth-smallest (list n)

(let ((list (add-index list))

(smallest '()))

(dotimes (i n (reverse smallest))

(setf smallest (cons (indexed-min list)

smallest)

list (remove (caar smallest)

list

:key #'car)))))

(defvar *t*

(loop for i below 100000 collect (random 10.0)))

Alan Crowe

Edinburgh

Scotland

Oct 11, 2005, 9:26:18 AM10/11/05

to

"tachyon" <pma...@gmail.com> writes:

>I was wondering if there is a quick and dirty way to find the rank of

>the nth smallest element in lisp. That is for example finding the 2nd

>smallest element in a list.

Yes, this can be done in time proportional to the length of the list,

for any n.

Here's a simple randomized algorithm (although deterministic

algorithms also exist; look up 'median algorithm', for example

in Aho, Hopcroft and Ullman).

1. Pick a random element x from the list.

2. Traversing the list, count the number of elements <= x.

Call this m.

3. If m >= n, recursively solve the problem on the elements <= x.

4. If m < n, recursively solve the problem of finding the (m - n)th

smallest element among those that were > x.

Each recursion here reduces the size of the list by an expected

constant factor, so the expected total running time is O(length(L)).

Paul

Oct 11, 2005, 11:02:37 AM10/11/05

to

Hi

The easy way is the following (not the most efficient though)

(defun nth-rank (sequence rank)

(let* ((sseq (sort (copy-seq sequence) #'<))

(nth-rank-el (elt sseq rank))

)

(position nth-rank-el sequence :test #'equalp)))

The above uses O(N) memory (the COPY-SEQ operation) and O(N lg(N)) time.

The SORT operation. A better algorithm would use a recursive

rank-finding method (whose implementation is not trivial).

A shorter version (for the brevity fanatics around :) )

(defun nth-rank (s r)

(position (elt (sort (copy-seq s) '<) r) s :test 'equalp))

Cheers

--

Marco

Oct 11, 2005, 12:32:21 PM10/11/05

to

Thank you all for your attention, its been most helpful.

Oct 11, 2005, 4:15:46 PM10/11/05

to

I tried to implement this for kicks, I think there's a couple of bits

missing. Is this an exercise for the reader or am I missing something?

missing. Is this an exercise for the reader or am I missing something?

In general there seems to be no terminating condition.

Justin

Oct 11, 2005, 4:31:17 PM10/11/05

to

Alan Crowe wrote:

> "tachyon" <pma...@gmail.com> writes:

>

> > I was wondering if there is a quick and dirty way to find the rank of

> > the nth smallest element in lisp. That is for example finding the 2nd

> > smallest element in a list.

>

> Remember that sort is n log n, so sorting the whole list is

> competitive with doing a linear scan to find the least

> element when you do about log n scans.

Possibly competitive, but certainly slower than the optimal solution.

The key thing to realize is that #'sort is doing work in comparing and

swapping elements that have no chance to be the Nth smallest.

The typical quicksort, for instance, does a partition step to divide

the list into two portions about a pivot. After doing so, you know what

location the pivot should be in; by comparing that to the rank N you

are searching for, you can discard one of the partitions *completely*.

The sort algorithm, however, keeps working on both partitions, even the

ones that are nowhere near the rank of interest.

Look up Floyd & Rivest's SELECT algorithm for an example.

It also matters if you want to select several ranks out of the same

set, in which case you want to preserve some of the partition work that

has already been done.

For "quick and dirty", however, sort & one partial list traversal is

hard to beat.

Oct 11, 2005, 4:48:36 PM10/11/05

to

It's hard to know what you are referring to without your including

context, but I think you are referring to Paul Dietz's solution.

In particular, he is rather informally stating "count the number of

elements <= x". There is also a need to accumulate the elements in some

way so that you can use that collection (or the other "complement"

collection of elements > x) for the later recursion.

The termination condition will be when you are looking for the

smallest/largest element in a one element list.

Also, if you get to caring about performance, you should be careful

with the step "pick a random element" from the list; you want to avoid

traversing the list all the way to the end to pick a pivot; that

traversal would contribute an O(L) time in addition to the O(L) time

Dietz mentions (I think these algorithms are usually discussed in the

context of array operations, where access to elements is uniform.

Singly-linked lists require more care.) Also, of course, you want to

avoid traversing a list just to see how long it is.

Oct 11, 2005, 4:54:11 PM10/11/05

to

josephoswaldgg: "It's hard to know what you are referring to without

your including

context, but I think you are referring to Paul Dietz's solution. "

your including

context, but I think you are referring to Paul Dietz's solution. "

Sorry, I'm using google groups to reply to usenet messages and I don't

think you can quote without doing it manually. I had presumed that my

messages would show up at least in he right place in the thread ;-)

I don't care about performance, and this same issue cropped up in an

earlier post about getting the index of an item in a list...

essentially if you're doing something like

(nth n lst) then you're doing a linear traversal of the list and the

way to get around that is, as you say, to use an array not a list.

"In particular, he is rather informally stating "count the number of

elements <= x". There is also a need to accumulate the elements in some

way so that you can use that collection (or the other "complement"

collection of elements > x) for the later recursion. "

Yeah that bit I had no problem with.

Justin

Oct 11, 2005, 5:53:57 PM10/11/05

to

Ah here's what Paul was getting at I think... at least this is what I

needed to do to make the algorithm work. The missing part was handling

duplicate items correctly and using that as a terminating condition...

needed to do to make the algorithm work. The missing part was handling

duplicate items correctly and using that as a terminating condition...

(defun nth-smallest(n lst)

(let* ((len (length lst))

(x (nth (random len) lst))

(less-lst (remove-if #'(lambda(n) (>= n x)) lst))

(same-lst (remove-if #'(lambda(n) (not (eq n x))) lst))

(less-cnt (length less-lst))

(same-cnt (length same-lst)))

(format t "n ~a x ~a less ~a same ~a~%" n x less-lst same-lst)

(cond

((< n less-cnt)

(nth-smallest n less-lst))

((< n (+ less-cnt same-cnt))

(progn

(format t "done answer is ~a~%" x)

x))

(t

(nth-smallest (- n (+ less-cnt same-cnt)) (remove-if

#'(lambda(n) (<= n x)) lst))))))

(nth-smallest 3 '(3 1 4 6 4 2 1))

(nth-smallest 2 '(4 6 7 23 4 6 7 4 3))

(nth-smallest 5 '(3 1 4 6 4 2 1))

(nth-smallest 6 '(4 6 7 23 4 6 7 4 3))

Oct 11, 2005, 11:01:46 PM10/11/05

to

And in case anyone cares ...

More robust version handles empty lists and lists with less elements

than n

; find the nth smallest item in a list

(defun nth-smallest(n lst)

(if lst

(let ((len (length lst)))

(if (<= n len)

(let*

((x (nth (random len) lst))

(less-lst (remove-if #'(lambda(n) (>= n x)) lst))

(same-lst (remove-if #'(lambda(n) (not (eq n x)))

lst))

(less-cnt (length less-lst))

(same-cnt (length same-lst)))

(cond

((< n less-cnt)

(nth-smallest n less-lst))

((< n (+ less-cnt same-cnt))

x)

(t

(nth-smallest (- n (+ less-cnt same-cnt)) (remove-if

#'(lambda(n) (<= n x)) lst)))))

nil))

nil))

(nth-smallest 3 '(3 1 4 6 4 2 1))

(nth-smallest 2 '(4 6 7 23 4 6 7 4 3))

(nth-smallest 5 '(3 1 4 6 4 2 1))

(nth-smallest 6 '(4 6 7 23 4 6 7 4 3))

(nth-smallest 1 '())

(nth-smallest 2 '())

(nth-smallest 2 '(1))

(nth-smallest 2 '(5 3 1 ))

(nth-smallest 4 '(1 4 4 45 5 6 4 66))

Oct 12, 2005, 12:07:21 AM10/12/05

to

justinhj wrote:

> josephoswaldgg: "It's hard to know what you are referring to without

> your including

> context, but I think you are referring to Paul Dietz's solution. "

>

> Sorry, I'm using google groups to reply to usenet messages and I don't

> think you can quote without doing it manually. I had presumed that my

> messages would show up at least in he right place in the thread ;-)

Click the "show options" to the right of the author's name on the post.

The "Reply" command in *that* banner will quote the message. That this

is not the default is, IMO, a bug.

Oct 12, 2005, 4:52:36 AM10/12/05

to

It's a recursive algorithm. Here's a simple implementation.

(defun rank (test a s)

(count-if (lambda (x) (funcall test x a)) s))

(defun left (test a s)

(remove-if-not (lambda (x) (funcall test x a)) s))

(defun right (test a s)

(remove-if (lambda (x) (funcall test x a)) s))

(defun random-element (s)

(elt s (random (length s))))

(defun order (o s &optional (test '<=))

(let* ((a (random-element s))

(r (rank test a s)))

(cond ((= (length s) 1) (elt s 0))

((>= r o)

(order o (left test a s) test))

(t (order (- o r) (right test a s) test)))))

(defun median (s &optional (test '<=))

(order (truncate (length s) 2) s test))

Oct 12, 2005, 8:08:40 AM10/12/05

to

"justinhj" <just...@gmail.com> writes:

> And in case anyone cares ...

I'm following this thread with great interest.

I'm intrigued by the idea of Lisp as runnable pseudo-code,

so when Paul Dietz posted

1. Pick a random element x from the list.

2. Traversing the list, count the number of elements <= x.

Call this m.

3. If m >= n, recursively solve the problem on the elements <= x.

4. If m < n, recursively solve the problem of finding the (m - n)th

smallest element among those that were > x.

I wondered whether I could use this directly as the top

level function definition and then add stuff to make it

go. So I sat and I typed

;; Pseudo code

(defun nth-smallest (list n)

(let* ((pivot (pick-one list))

(analysis (analyse list pivot))) ;Traversing the list

(cond ((<= n (smaller analysis)) ;pivot was too big

;; recursively solve the problem on the elements < x

(nth-smallest (low-set analysis) n))

((<= n (+ (smaller analysis) (same analysis)))

pivot)

(t ; the high set excludes the smaller and equal sets

;; recursively solve the problem of finding the (m - n)th

;; smallest element among those that were > x.

(nth-smallest (high-set analysis)

(- n

(smaller analysis)

(same analysis)))))))

;;; I'm assuming that analyse will traverse the list

;;; and construct an analysis containing the various counts

;;; and subsets as required

;;; picking one is easy enough if we don't mind bumping into worst

;;; case behaviour on a list that is already in order

(defun pick-one (list)

(assert (not (null list)) ())

(car list))

;;; Thinking bottom up, a key concept is having a bag of things

;;; and keeping count as we put things into it

;;; The protocol is to add items with add

;;; then see how many we've got with total

;;; and the list of them with members

(defclass counted-set ()

((count :reader total

:initform 0)

(set :reader members

:initform '())))

(defmethod add ((item t)(bag counted-set))

(push item (slot-value bag 'set))

(incf (slot-value bag 'count)))

;;; Analyse must return an object, an analysis, with the protocol

;;; smaller, same, larger - counts relative to the pivot

;;; low-set, high-set - the partition relative to the pivot

;;; Lets build the analysis object on top of counted-set

;;; Then the analysis object pretty simple and defstruct is

;;; adequate

(defun analyse (list pivot)

(let ((equal (make-instance 'counted-set))

(less (make-instance 'counted-set))

(more (make-instance 'counted-set)))

(dolist (item list (make-analysis :equal equal

:less less

:more more))

(cond ((= item pivot)(add item equal))

((< item pivot)(add item less))

((> item pivot)(add item more))))))

(defstruct analysis equal less more)

(defmethod smaller ((a analysis))

(total (analysis-less a)))

(defmethod larger ((a analysis))

(total (analysis-more a)))

(defmethod same ((a analysis))

(total (analysis-equal a)))

(defmethod high-set ((a analysis))

(members (analysis-more a)))

(defmethod low-set ((a analysis))

(members (analysis-less a)))

Well, by the time I'd finished all this typing I was feeling

that my experiment had failed. Yes, I added stuff to make

the "Psuedo code" go, but I'd worn out my keyboard in the

process, and I still had to debug the code.

So I try it out and it works first time.

I find that a little spooky. I usually write `clever code'

and then have to puzzle over why it doesn't work. (I always

intend to write plain code, but once I get into it I get

carried away.)

Maybe the experiment is a success after all.

Alan Crowe

Edinburgh

Scotland

Oct 12, 2005, 8:49:43 AM10/12/05

to

Thanks!

Oct 12, 2005, 11:37:32 AM10/12/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I'm intrigued by the idea of Lisp as runnable pseudo-code,

> so when Paul Dietz posted

[long story shortened...]

> So I try it out and it works first time.

No doubt the static typing.

> Maybe the experiment is a success after all.

It'd be interesting to give the same problem to some students and have

them solve it in Java, C, or whatever the language of the day is.

Oct 12, 2005, 1:26:10 PM10/12/05

to

Joe Marshall <jmar...@alum.mit.edu> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>

> > I'm intrigued by the idea of Lisp as runnable pseudo-code,

> > so when Paul Dietz posted

> [long story shortened...]

>

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>

> > I'm intrigued by the idea of Lisp as runnable pseudo-code,

> > so when Paul Dietz posted

> [long story shortened...]

>

I'm still struggling to work out what I mean by runnable

pseudo-code. I've tried again starting with this as the

pseudo-code:

(recursive-definition-of (nth-smallest n list)

(chose pivot from list)

(learn

less-than-pivot

less-than-or-equal-pivot

items<pivot

items>pivot

from

traverse list pivot)

(if n <= less-than-pivot recurse-on n items<pivot)

(if less-than-pivot < n <= less-than-or-equal-pivot answer-is pivot)

(otherwise recurse-on (- n less-than-or-equal-pivot) items>pivot))

The challenge I set myself was to get this to run. I thought

that dealing with

less-than-pivot < n <= less-than-or-equal-pivot

was an interesting thing to do because it is not handled

entirely happily in any language that I know.

Having an infix minus instead of

(- n less-than-or-equal-pivot)

seemed less interesting.

Pseudo codes often have a point by point style of

presentation, except that the later points have access to

the results of the earlier points, so there is an implicit

nesting that I wanted to explore

> It'd be interesting to give the same problem to some

> students and have them solve it in Java, C, or whatever

> the language of the day is.

Err, with the code above, that would be a quite a serious

challenge, even if they were allowed to add {,; and } at

helpful points :-)

In Artificial Intelligence: A Modern Approach, Russel and

Norvig use a pseudo code instead of an actual language. It

makes the algorithms seem very simple. I wish that I had

some feel for whether the simplicity of the pseudo code is

because real programming languages are still quite clumsy,

or whether it is because the pseudo code is basically

cheating and sweeping complications under the carpet.

Alan Crowe

Edinburgh

Scotland

PS Here is my CL code, in case any-one wants to see how the

pseudo code can be made to run.

(defun traverse (list pivot)

(let ((less-than (count-if (lambda(x)(< x pivot)) list))

(less-than-or-equal (count-if (lambda(x)(<= x pivot)) list))

(items<pivot (remove-if (lambda(x)(>= x pivot)) list))

(items>pivot (remove-if (lambda(x)(<= x pivot)) list)))

(values less-than

less-than-or-equal

items<pivot

items>pivot)))

(defmacro recursive-definition-of (function-call &body accumulating-clauses)

(let ((function-name (car function-call)))

`(symbol-macrolet ((function-name ,(car function-call)))

(defun ,function-name ,(cdr function-call)

,(nest accumulating-clauses)))))

(defun nest (clauses)

(if (endp (cdr clauses)) ;last one

(cons (look-up (caar clauses))

(cdar clauses))

(assemble (car clauses)

(nest (cdr clauses)))))

(defun assemble (context contents)

(list (look-up (car context))

(cdr context)

contents))

(defun look-up (name)

(let ((translation (assoc name *translations*)))

(if translation (cdr translation) name)))

(defparameter *translations*

`((if . inequality-if)

(otherwise . pseudo-otherwise)))

(defmacro chose ((symbol filler form) body)

(assert (eql filler 'from))

`(let ((,symbol (random-choice ,form))) ,body))

(defun random-choice (list)

;; keep it deterministic for now to ease debugging

(car list))

(defmacro learn (learning-experience body)

(let* ((marker (position 'from learning-experience))

(symbols (subseq learning-experience 0 marker))

(form (subseq learning-experience (+ marker 1))))

`(multiple-value-bind ,symbols ,form ,body)))

(defmacro inequality-if (cond&then else)

`(if ,(extract-condition cond&then)

,(extract-then cond&then)

,else))

(defun extract-condition (code)

(cons 'and (reformat-inequality (take-odd code))))

(defun take-odd (code)

(case (second code)

((< <= = > >=) (list* (first code)

(second code)

(take-odd (cddr code))))

(t (list (car code)))))

(defun reformat-inequality (code)

(if (endp (cdr code))

nil

(cons (list (second code)

(first code)

(third code))

(reformat-inequality (cddr code)))))

(defun extract-then (code)

(case (second code)

((< <= = > >=) (extract-then (cddr code)))

(t (cdr code))))

(defmacro answer-is (form &environment env)

`(return-from ,(macroexpand 'function-name env) ,form))

(defmacro recurse-on (&environment env &rest args)

(let ((function-name (macroexpand 'function-name env)))

(cons function-name args)))

(defmacro pseudo-otherwise (&rest args)

args)

(defun spy (function form env)

(if (and (listp form)

(eql (symbol-package (car form))

(find-package "CL-USER")))

(progn

(terpri)(terpri)

(format t "Expanding ~A~%" form)

(print (funcall function form env)))

(funcall function form env)))

Spy isn't called. I set *macroexpand-hook* to #'spy to help me

debug this.

CL-USER(139): (dotimes (i 10)

(print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3 3))))

1

2

3

3

3

3

3

3

4

5

Oct 12, 2005, 4:18:51 PM10/12/05

to

Alan Crowe wrote:

> I'm still struggling to work out what I mean by runnable

> pseudo-code. I've tried again starting with this as the

> pseudo-code:

Some interesting code there

Your post seems to show that the more abstract and simple your starting

point, the more code you need under the scenes to make it work

> In Artificial Intelligence: A Modern Approach, Russel and

> Norvig use a pseudo code instead of an actual language. It

> makes the algorithms seem very simple. I wish that I had

> some feel for whether the simplicity of the pseudo code is

> because real programming languages are still quite clumsy,

> or whether it is because the pseudo code is basically

> cheating and sweeping complications under the carpet.

Good pseudocode should give you everything you need to implement the

solution. Leaving unimportant things for you to do. If the unimportant

things have to be done a certain way, then they become important.

So for example in the AI book a description of the A* search algorithm

would tell you to maintain two lists of nodes, but the actual data type

and algorithm you use would be up to you and irrelevant (apart from

performance concerns.)

Oct 12, 2005, 4:12:21 PM10/12/05

to

justinhj schrieb:

[1] ;; copy&paste into dosbox on win98, clisp 2.35, code obove

[2]> (nth-smallest 2 '(0.23 0.19 2.38 1.17))

1.17

[3]> (nth-smallest 0 '(-2 2/5 3.49 13 -4))

-4

[4]> (nth-smallest 1/2 '(0.333 0.125 0.745 -2/3 (sqrt 2) 9))

*** - >=: (SQRT 2) is not a real number

The following restarts are available:

USE-VALUE :R1 You may input a value to be used instead.

ABORT :R2 ABORT

Break 1 [5]> :r2

[6]>_

Yes. Great. :)

stefan

Oct 12, 2005, 4:30:36 PM10/12/05

to

Alan Crowe schrieb:

> (defun traverse (list pivot)

> (let ((less-than (count-if (lambda(x)(< x pivot)) list))

> (less-than-or-equal (count-if (lambda(x)(<= x pivot)) list))

...

[see posting before]

...

> (terpri)(terpri)

> (format t "Expanding ~A~%" form)

> (print (funcall function form env)))

> (funcall function form env)))

> Spy isn't called. I set *macroexpand-hook* to #'spy to help me

> debug this.

> CL-USER(139): (dotimes (i 10)

> (print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3 3))))

> 1

...

> 5

I missed 1 (one) on win98 clisp 2.35 copy&paste:

[228]> (dotimes (i 9) (print (nth-smallest (+ i 1) '(5 2 3 3 3 4 1 3 3

3))))

2

3

3

3

3

3

3

4

5

NIL

[229]>

With (dotimes (i 10) ...) I get two NIL at the end and no 1 at the

beginn.

I play around a bit, maybe I find why....

stefan

Oct 12, 2005, 8:01:35 PM10/12/05

to

lin8080 <lin...@freenet.de> writes:

> [4]> (nth-smallest 1/2 '(0.333 0.125 0.745 -2/3 (sqrt 2) 9))

>

> *** - >=: (SQRT 2) is not a real number

> The following restarts are available:

> USE-VALUE :R1 You may input a value to be used instead.

> ABORT :R2 ABORT

> Break 1 [5]> :r2

> [6]>_

>

> Yes. Great. :)

> [4]> (nth-smallest 1/2 '(0.333 0.125 0.745 -2/3 (sqrt 2) 9))

>

> *** - >=: (SQRT 2) is not a real number

> The following restarts are available:

> USE-VALUE :R1 You may input a value to be used instead.

> ABORT :R2 ABORT

> Break 1 [5]> :r2

> [6]>_

>

> Yes. Great. :)

Wbat's the problem with you?

(nth-smallest 1/2 (list 0.333 0.125 0.745 -2/3 (sqrt 2) 9))

--

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

In a World without Walls and Fences,

who needs Windows and Gates?

Oct 12, 2005, 8:43:56 PM10/12/05

to

lin8080 wrote:

> I missed 1 (one) on win98 clisp 2.35 copy&paste:

did you copy & paste the definition at the end, too?

(recursive-definition-of (nth-smallest n list)

(chose pivot from list)

(learn

less-than-pivot

less-than-or-equal-pivot

items<pivot

items>pivot

from

traverse list pivot)

(if n <= less-than-pivot recurse-on n items<pivot)

(if less-than-pivot < n <= less-than-or-equal-pivot answer-is pivot)

(otherwise recurse-on (- n less-than-or-equal-pivot) items>pivot))

Perhaps you have some buggy nth-smallest function already defined. I've

tested it with clisp 2.35 on Cygwin Windows XP and it works.

--

Frank Buß, f...@frank-buss.de

http://www.frank-buss.de, http://www.it4-systems.de

Oct 12, 2005, 9:23:19 PM10/12/05

to

Thanks Pascal

I was just about to suggest

[4]> (nth-smallest 1/2 `(0.333 0.125 0.745 -2/3 ,(sqrt 2) 9))

Although really the function could enforce an integer value of n, it's

kind of a testament to lisp that it just worked and rounded down to the

nearest integer ;-)

Justin

Oct 13, 2005, 10:59:08 AM10/13/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> The challenge I set myself was to get this to run. I thought

> that dealing with

>

> less-than-pivot < n <= less-than-or-equal-pivot

>

> was an interesting thing to do because it is not handled

> entirely happily in any language that I know.

In Icon and Python it's written just like the above

(except that you can't use "-" in identifiers).

--

__("< Marcin Kowalczyk

\__/ qrc...@knm.org.pl

^^ http://qrnik.knm.org.pl/~qrczak/

Oct 13, 2005, 11:14:35 AM10/13/05

to

"justinhj" <just...@gmail.com> writes:

> Some interesting code there

>

> Your post seems to show that the more abstract and simple your starting

> point, the more code you need under the scenes to make it work

> Some interesting code there

>

> Your post seems to show that the more abstract and simple your starting

> point, the more code you need under the scenes to make it work

Agreed, but what does it /really/ show. I wrote it in a

spirit of "lets plunge in and write some code". So I now

have a data point. I'll need some more before I start

reaching broader conclusions.

I've been checking Paul Graham's essay, Beating the

Averages. He says that the Viaweb editor was 20-25%

macros. I use nothing like as many macros in my code and I

don't see how to benefit from using more. I think I am

missing out.

My two point plan is

1)Practise macro writing technique, so that I am able to

write any macros that I think will improve my code

2)??? I'm a bit stuck here. I'm at the stage of playing with

ideas, such as `runnable pseudocode'

Alan Crowe

Edinburgh

Scotland

Oct 13, 2005, 11:24:13 AM10/13/05

to

On 10 Oct 2005 22:05:50 -0700, "tachyon" <pma...@gmail.com> wrote:

>I was wondering if there is a quick and dirty way to find the rank of

>the nth smallest element in lisp. That is for example finding the 2nd

>smallest element in a list.

You do this in Lisp the same way as in other languages: a) create

heap, b) remove first n-1 elements from the heap top.

A.L.

Oct 13, 2005, 11:58:16 AM10/13/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

I think this "runnable pseudocode" is actually a very good idea.

When I need to write a program in a domain I don't know very well, I

just start to write s-expr trying to express stuff in the domain. I'm

just "inventing" a language for the domain. Then I implement the

needed "words". At this stage, I adopted a pragmatic approach, where

I allowed changes in my domain specific s-expressions, to map them

more easily to lisp constructs (functions, methods). But it may be

worthwhile to follow a more absolute way like you do, keeping the dsl

and implementing it with macros. I've not read yours in details yet,

but perhaps the complexity you see can be managed/reduced with more

experience in this technique.

--

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

Nobody can fix the economy. Nobody can be trusted with their finger

on the button. Nobody's perfect. VOTE FOR NOBODY.

Oct 13, 2005, 12:04:09 PM10/13/05

to

I wondered about that. Retrieving the lowest item would be a log2(l) op

where l is the number of items in the data. You'd repeat that operation

n times giving

n log2(l) runtime

And in the process you'd lose your heap so you'd have to add a copy

operation to the whole heap to keep it as it was before you made the

query.

So which algorithm is better depends on the value of n.

For example with a 100 element array once n>15 its better to use the

O(l) algorithm

Oct 13, 2005, 12:08:11 PM10/13/05

to

Alan Crowe wrote:

> "justinhj" <just...@gmail.com> writes:

> My two point plan is

>

> 1)Practise macro writing technique, so that I am able to

> write any macros that I think will improve my code

>

> 2)??? I'm a bit stuck here. I'm at the stage of playing with

> ideas, such as `runnable pseudocode'

Yeah it seems like a good plan in that you're at the very least getting

macro practise, and at best it would seem to be a way to learn the

right level of abstraction to begin looking at a solution.

I'll have to try that next time I solve a problem in lisp.

Oct 13, 2005, 12:21:45 PM10/13/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I've been checking Paul Graham's essay, Beating the Averages. He

> says that the Viaweb editor was 20-25% macros. I use nothing like as

> many macros in my code and I don't see how to benefit from using

> more. I think I am missing out.

>

> My two point plan is

>

> 1)Practise macro writing technique, so that I am able to

> write any macros that I think will improve my code

>

> 2)??? I'm a bit stuck here. I'm at the stage of playing with

> ideas, such as `runnable pseudocode'

This seems related to the "put parens around the spec and make it

work" strategy. I.e. translate a specification into s-exps and then

make those s-exps the code that implement the specification. I give an

example of this in chapters 24 and 25 of _Practical Common Lisp_:

<http://www.gigamonkeys.com/book/practical-parsing-binary-files.html>

<http://www.gigamonkeys.com/book/practical-an-id3-parser.html>

Another strategy is to start from the other end. Write the ugliest

possible code that does what you want and then distill it down to it's

essence using macros. This one may take more practice since you need

to develop a fine aversion to ugliness so you know when to keep

distilling. You need to constantly be looking not just for literal

code duplication but "conceptual" duplication that you can abstract

away.

-Peter

--

Peter Seibel * pe...@gigamonkeys.com

Gigamonkeys Consulting * http://www.gigamonkeys.com/

Practical Common Lisp * http://www.gigamonkeys.com/book/

Oct 13, 2005, 12:21:54 PM10/13/05

to

Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>

> > The challenge I set myself was to get this to run. I thought

> > that dealing with

> >

> > less-than-pivot < n <= less-than-or-equal-pivot

> >

> > was an interesting thing to do because it is not handled

> > entirely happily in any language that I know.

>

> In Icon and Python it's written just like the above

> (except that you can't use "-" in identifiers).

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>

> > The challenge I set myself was to get this to run. I thought

> > that dealing with

> >

> > less-than-pivot < n <= less-than-or-equal-pivot

> >

> > was an interesting thing to do because it is not handled

> > entirely happily in any language that I know.

>

> In Icon and Python it's written just like the above

> (except that you can't use "-" in identifiers).

That is interesting. I had never even heard of Icon.

Do they short circuit? That is, does a <= b < c <= d hold

off evaluating c and d until it has checked that a is indeed

less than or equal to b?

What is `the right thing' here?

Alan Crowe

Edinburgh

Scotland

Oct 13, 2005, 1:06:33 PM10/13/05

to

On 13 Oct 2005 09:04:09 -0700, "justinhj" <just...@gmail.com> wrote:

>

>So which algorithm is better depends on the value of n.

>

This is universally true for all algorithms and languages...

A.L.

Oct 13, 2005, 1:53:19 PM10/13/05

to

Of course, but I can't see anywhere in my post that I was referring

solely to lisp.

Oct 13, 2005, 3:42:37 PM10/13/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

>> In Icon and Python it's written just like the above

>> (except that you can't use "-" in identifiers).

>

> That is interesting. I had never even heard of Icon.

>

> Do they short circuit? That is, does a <= b < c <= d hold off

> evaluating c and d until it has checked that a is indeed less than

> or equal to b?

Yes in both.

In Icon it relies on the unusual core evaluation rules of the

language, which uses backtracking where an expression can potentially

lazily generate several values, similarly to Prolog. "if" checks

whether the condition succeeds or fails, i.e. whether it produces

any values or not; it doesn't involve materialized Boolean values.

Comparison operators return their right argument if the condition

is true, and fail if it's false. This yields the intended semantics

of chained comparisons when operator calls are nested in the right

direction.

In Python comparison operators are just treated specially by the

compiler. "a <= b < c" generates the short-circuiting code which

evaluates each expression at most once, and is different from

both "(a <= b) < c" and "a <= (b < c)".

Oct 13, 2005, 4:29:04 PM10/13/05

to

Frank Buss schrieb:

> lin8080 wrote:

> > I missed 1 (one) on win98 clisp 2.35 copy&paste:

> did you copy & paste the definition at the end, too?

> (recursive-definition-of (nth-smallest n list)

...

No I did not. This stands at the beginn of the posting. I copy&paste

only after Alan Crowe PS lines.

.................

PS Here is my CL code, in case any-one wants to see how the

pseudo code can be made to run.

[code]

..................

(In my Browser it is posting-reference 11 and 8, there is no (defun

nth-smallest n list) inside (not even nth-smallest), but clisp session

has (defun nth-smallest (n lst) ...) from justinhj's code before). Mabey

this was used in the second copy&paste?

> Perhaps you have some buggy nth-smallest function already defined. I've

> tested it with clisp 2.35 on Cygwin Windows XP and it works.

I'll do this again, when I find time.

stefan

Oct 13, 2005, 5:09:33 PM10/13/05

to

lin8080 wrote:

> Frank Buss schrieb:

> No I did not. This stands at the beginn of the posting. I copy&paste

> only after Alan Crowe PS lines.

> Frank Buss schrieb:

> No I did not. This stands at the beginn of the posting. I copy&paste

> only after Alan Crowe PS lines.

> I'll do this again, when I find time.

>

> stefan

>

> stefan

Just out of interest I copied the code into a window and it gave the

correct output as in Alan's original post. I'm using CLISP 2.35

Justin

Oct 13, 2005, 5:24:29 PM10/13/05

to

Yeah I see what happened, you got my version of the code which would

give that output, since I use n=0 gives the 1st smallest, n=1 gives the

2nd etc

Oct 14, 2005, 1:28:22 AM10/14/05

to

Paul F. Dietz wrote:

> Yes, this can be done in time proportional to the length of the list,

> for any n.

> Yes, this can be done in time proportional to the length of the list,

> for any n.

I'm often perplexed by all the learned scholars who speculate about

the maximal efficiency of an algorithm. It seems to me overly

restrictive and a violation of parity not to think about the

minimally efficient solution. Years ago when Usenet existed before

the Internet, and when it was possible to read the entire volume of

postings each day, there was (I think in comp.lang.c) exploration

of "malgorithms". IIRC a malgorithm was defined as an effective

procedure to solve a problem that optimized the time required to

find a solution (where "optimize" implies "maximize") without

adding superfluous do-nothing code to the solution.

My favorite example of a malgorithm for sorting a sequence can be

expressed as:

1. randomize the order of the sequence

2. if the sequence is now ordered, return it

3. goto 1

> Here's a simple randomized algorithm (although deterministic

> algorithms also exist; look up 'median algorithm', for example

> in Aho, Hopcroft and Ullman).

Here is my solution for an effective malgorithm for the current

problem. Please note that this malgorithm is carefully coded

to do the right thing for sequences with length less than 2, and

for sequences with elements that are #'=.

Read it and weep.

(defun silver-medal (list-of-reals)

(symbol-macrolet

((list-of-reals1 (remove-duplicates list-of-reals :test #'=)))

(and (cdr list-of-reals1)

(loop as trial = (elt list-of-reals1

(random (length list-of-reals1)))

when (and (loop for x in list-of-reals1

when (< x trial)

collect pi)

(null (cdr (loop for x in list-of-reals1

when (< x trial)

collect 22/7))))

return trial)))))

Oct 14, 2005, 1:08:34 PM10/14/05

to

Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> > Do they short circuit? That is, does a <= b < c <= d hold off

> > evaluating c and d until it has checked that a is indeed less than

> > or equal to b?

>

> Yes in both.

>

> In Icon it relies on the unusual core evaluation rules of the

> language, which uses backtracking where an expression can potentially

> lazily generate several values, similarly to Prolog. "if" checks

> whether the condition succeeds or fails, i.e. whether it produces

> any values or not; it doesn't involve materialized Boolean values.

> Comparison operators return their right argument if the condition

> is true, and fail if it's false. This yields the intended semantics

> of chained comparisons when operator calls are nested in the right

> direction.

>

> In Python comparison operators are just treated specially by the

> compiler. "a <= b < c" generates the short-circuiting code which

> evaluates each expression at most once, and is different from

> both "(a <= b) < c" and "a <= (b < c)".

>

I'm going green with envy here. When I have an inequality

such as 0 <= r < n to code up I find that

(and (<= 0 r)

(< r n))

feels gross and

(< -1 r n)

is too stressful, because that kind of petty transformation

is bound to cause an off by one error one day.

I think this macro does the trick

;;;; (inequality 0 <= i < j <= n)

;;; includes short circuiting so that later terms

;;; are not evalutated if earlier ones fail

;;; includes temporary variables. Forms are

;;; evaluated zero or one times, never twice

;;; I don't check the names given for the inequalities

;;; so they can be user defined functions (of two arguments)

;;; With

#|

(defun strlen< (r s)

(< (length r)

(length s)))

|#

;;; (inequality "alan" strlen< "crowe" strlen< "edinburgh") => T

#| I want (inequality a <= b < c <= d) to

expand to

eval a

eval b

check a<=b

if ok

eval c

check b<c

if still ok

eval d

check c <= d |#

#| I think I have dreamt up a suitable pattern

The code for b < c <= d is going to have to save c in case it is needed

later

(let ((#:temp c))

and then use the value of b saved from last time

(< #:earlier-temp #:temp)

which has to be anded with the rest of the computation,

which is recursive on c <= d and needs to know the name

#:temp so that it can access the value already computed

* (macroexpand '(inequality a <= b < c <= d))

(LET ((#:G867 A))

(LET ((#:G868 B))

(AND (<= #:G867 #:G868)

(LET ((#:G869 C))

(AND (< #:G868 #:G869)

(LET ((#:G870 D))

(AND (<= #:G869 #:G870) T)))))))

|#

(defmacro inequality (&rest odd)

(labels ((order-next (odd previous)

(if (endp (cdr odd))

t

(let ((temp (gensym)))

`(let ((,temp ,(third odd)))

(and (,(second odd) ,previous ,temp)

,(order-next (cddr odd) temp)))))))

(let ((temp (gensym)))

`(let ((,temp ,(car odd)))

,(order-next odd temp)))))

Alan Crowe

Edinburgh

Scotland

Oct 14, 2005, 1:34:29 PM10/14/05

to

Alan Crowe wrote:

> * (macroexpand '(inequality a <= b < c <= d))

>

> (LET ((#:G867 A))

> (LET ((#:G868 B))

> (AND (<= #:G867 #:G868)

> (LET ((#:G869 C))

> (AND (< #:G868 #:G869)

> (LET ((#:G870 D))

> (AND (<= #:G869 #:G870) T)))))))

> * (macroexpand '(inequality a <= b < c <= d))

>

> (LET ((#:G867 A))

> (LET ((#:G868 B))

> (AND (<= #:G867 #:G868)

> (LET ((#:G869 C))

> (AND (< #:G868 #:G869)

> (LET ((#:G870 D))

> (AND (<= #:G869 #:G870) T)))))))

How about this pattern:

(LET (#:G001)

(AND (<= A (SETF #:G001 B))

(< #:G001 (SETF #:G001 C))

(<= #:G001 D)))

You just need one temporary variable to tie you over from one

inequality to the next.

Oct 14, 2005, 9:50:33 PM10/14/05

to

"Steven M. Haflich" <s...@alum.mit.edu> writes:

> Paul F. Dietz wrote:

>> Yes, this can be done in time proportional to the length of the list,

>> for any n.

>

> I'm often perplexed by all the learned scholars who speculate about

> the maximal efficiency of an algorithm. It seems to me overly

> restrictive and a violation of parity not to think about the

> minimally efficient solution.

Broder and Stolfi wrote a wonderful paper on just this problem:

``Pessimal Algorithms and Simplexity Analysis''

at

http://www.cs.uiuc.edu/class/fa05/cs473ug/resources/pessimal-algorithms.pdf

Oct 15, 2005, 4:18:28 AM10/15/05

to

Peter Seibel schrieb:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

<http://www.gigamonkeys.com/book/practical-parsing-binary-files.html>

<http://www.gigamonkeys.com/book/practical-an-id3-parser.html>

Hi;

This is too interesting to ignore. I will give you an example where this

would be more necessary than a first thought will show.

Think about an expand (describe), when you want access to available

docus, ie (show-doc 'name), (list-doc-local), (search-doc-web), ...

I actualy try something with xml parts, but this may take a while, this

is a large field :).

(with-xml-part '(

<location file="local\documents\owner\cl-impnotes\..."/>

<info type="use" value="constants"/>

<info type="use" value="COMMON-LISP"/>

<info type="export" value="+LIBRARY-NAME+"/>

<variable id="variable + LIBRARY-NAME + LIBRARY-NAMES"/>

<location file="public\documents\owner\climpnotes\*.html"/>

<info type="mod" value="constant"/>

))

Now one problem is named path-names, another is include some-lisp-code

to specify a few points, or the in/out-put between interpreter and

browser-xml-mechanics.

But I dont plan to type tonnes of xml- or slot-code there, just think

around, which could be a elegant way to get that done. Sure, there are

some tests, but its horrible to work on after some time passed.

Last point: will I have the output in a browser-window (case read-only)

or in the interpreter-window (case work-on-it), ... things like this

easily fill the brain-room and ends in confusion.

My goal is using pseudo-code with the interpreter and use the specified

output from the xml-search-results to automatically translate/ create

some useable code-pieces to work on. Starting with a simply lookup

possibility for some examples or :keywords to a function. Therefor it is

useful to get a quick access to all local/ online docs (or commented

code-examples) with one simple (show-doc 'name :key-specifics).

stefan

(pseudo-code) vs (do-what-i-mean)

Oct 15, 2005, 10:04:09 AM10/15/05

to

"Kaz Kylheku" <kkyl...@gmail.com> writes:

>> (LET ((#:G867 A))

>> (LET ((#:G868 B))

>> (AND (<= #:G867 #:G868)

>> (LET ((#:G869 C))

>> (AND (< #:G868 #:G869)

>> (LET ((#:G870 D))

>> (AND (<= #:G869 #:G870) T)))))))

>

> How about this pattern:

>

> (LET (#:G001)

> (AND (<= A (SETF #:G001 B))

> (< #:G001 (SETF #:G001 C))

> (<= #:G001 D)))

I would suppose that LET with separate variables is easier for

compilers to optimize than SETF. E.g. they will more easily infer and

make use of the fact that the type of the given variable is a fixnum,

or that it's a constant, than that it's a fixnum between this

assignment and that.

Oct 15, 2005, 10:55:44 AM10/15/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:

> > In Python comparison operators are just treated specially by the

> > compiler. "a <= b < c" generates the short-circuiting code which

> > evaluates each expression at most once, and is different from both

> > "(a <= b) < c" and "a <= (b < c)".

> I'm going green with envy here. When I have an inequality

> such as 0 <= r < n to code up I find that

> (and (<= 0 r)

> (< r n))

> feels gross and

> (< -1 r n)

> is too stressful

> Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:

> > In Python comparison operators are just treated specially by the

> > compiler. "a <= b < c" generates the short-circuiting code which

> > evaluates each expression at most once, and is different from both

> > "(a <= b) < c" and "a <= (b < c)".

> I'm going green with envy here. When I have an inequality

> such as 0 <= r < n to code up I find that

> (and (<= 0 r)

> (< r n))

> feels gross and

> (< -1 r n)

> is too stressful

In the limited case with only three numbers to compare, how does

(typep r `(integer 0 (,n))) ;Or "real", or whatever.

make you feel?

Oct 16, 2005, 5:09:26 AM10/16/05

to

Lars Brinkhoff <lars...@nocrew.org> writes:

> Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> > When I have an inequality

> > such as 0 <= r < n to code up I find that

> > (and (<= 0 r)

> > (< r n))

> > feels gross and

> > (< -1 r n)

> > is too stressful

>

> In the limited case with only three numbers to compare, how does

>

> (typep r `(integer 0 (,n))) ;Or "real", or whatever.

>

> make you feel?

The strong feelings originate in my relationship to the

source material from which I'm coding. When my program

doesn't work I check my translation. So if the source

material says (before I run TeX)

sum_{ 0<= i < j < n } f(i,j)

I would like to type in

(sum (i j)(inequality 0 <= i < j < n)

(f i j))

If it says r \member [0,n)

then

(typep r `(integer 0 (,n)))

would feel pretty good, and slightly preferable to

reformating to

(inequality 0 <= r < n )

Alan Crowe

Edinburgh

Scotland

Oct 16, 2005, 12:27:46 PM10/16/05

to

Alan Crowe wrote:

> > Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> > > When I have an inequality

> > > such as 0 <= r < n to code up I find that

> > > (and (<= 0 r)

> > > (< r n))

> > > feels gross and

> > > (< -1 r n)

> > > is too stressful

> The strong feelings originate in my relationship to the

> source material from which I'm coding. When my program

> doesn't work I check my translation. So if the source

> material says (before I run TeX)

>

> sum_{ 0<= i < j < n } f(i,j)

>

> I would like to type in

>

> (sum (i j)(inequality 0 <= i < j < n)

> (f i j))

That's a *quite* different set of semantics from the Python example

that was originally stated. Depending on the mathematician and/or

formula, such an inequality could represent a set of integers, a

sequence (possibly infinite) of integers, or, in your particular case,

a set of ordered pairs of integers.

Your "sum" will have to be one hell of a macro to make sense out of

general inequality forms slurped out of TeX files. Good luck with that.

Oct 16, 2005, 1:14:45 PM10/16/05

to

Lars Brinkhoff wrote:

> In the limited case with only three numbers to compare, how does

>

> (typep r `(integer 0 (,n))) ;Or "real", or whatever.

>

> make you feel?

It doesn't make me feel good at all, since I suspect all existing

Lisp implementations will do this by consing up the type at run

time, then calling the general-case TYPEP function, which would

parse this type term. This will have horrible performance.

It seems to me that Lisp is missing types (except for classes)

as first class objects; these would be useful here.

Paul

Oct 17, 2005, 2:06:45 AM10/17/05

to

"Paul F. Dietz" <di...@dls.net> writes:

> Lars Brinkhoff wrote:

>

>> In the limited case with only three numbers to compare, how does

>> (typep r `(integer 0 (,n))) ;Or "real", or whatever.

>> make you feel?

>

> It doesn't make me feel good at all, since I suspect all existing

> Lisp implementations will do this by consing up the type at run

> time, then calling the general-case TYPEP function, which would

> parse this type term. This will have horrible performance.

Well, except for the fact that our compiler-macro for typep doesn't

handle the backquote expression as I would have expected, we at

least come close - this in Allegro CL 7.0:

CL-USER(1): (compile (defun foo (x) (typep x '(integer 0 (10)))))

FOO

NIL

NIL

CL-USER(2): (disassemble 'foo)

;; disassembly of #<Function FOO>

;; formals: X

;; code start: #x10684a9c:

0: 83 f9 01 cmpl ecx,$1

3: 74 02 jz 7

5: cd 61 int $97 ; SYS::TRAP-ARGERR

7: 80 7f cb 00 cmpb [edi-53],$0 ; SYS::C_INTERRUPT-PENDING

11: 74 02 jz 15

13: cd 64 int $100 ; SYS::TRAP-SIGNAL-HIT

15: a8 03 testb al,$3

17: 74 07 jz 26

19: 8b c7 movl eax,edi

21: f8 clc

22: 8b 75 fc movl esi,[ebp-4]

25: c3 ret

26: 83 f8 00 cmpl eax,$0

29: 7c f4 jl 19

31: 83 f8 24 cmpl eax,$36

34: 8b c7 movl eax,edi

36: 7f 03 jnle 41

38: 8d 47 c2 leal eax,[edi-62] ; T

41: f8 clc

42: eb ea jmp 22

CL-USER(3): (foo 9)

T

CL-USER(4): (foo 10)

NIL

CL-USER(5): (foo 9.0)

NIL

CL-USER(6): (foo 'a)

NIL

CL-USER(7):

Note that there is no call in this function; all of the checks are

being done based on a breakdown of the type itself.

I'll have to look into fixing the compiler-macro to allow the

backquoted expression - as long as the final form is a constant

there should be no trouble expanding this. It should also be easy

enough to rewrite a non-constant integer range into a test, although

the testing would be slightly less efficient, because you wouldn't

know if n were a fixnum, nor would you know that the

whole test could be elided and nil returned if n were negative.

Thanks.

> It seems to me that Lisp is missing types (except for classes)

> as first class objects; these would be useful here.

Mostly what is missing is the ability to normalize them. However,

they don't necessarily need to be first-class - they could just

be a subset of (or symbol list class) that has a way to manipulate

them as types.

--

Duane Rettig du...@franz.com Franz Inc. http://www.franz.com/

555 12th St., Suite 1450 http://www.555citycenter.com/

Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182

Nov 20, 2005, 3:01:24 PM11/20/05

to

Joe Marshall wrote:

[Alan Crowe:]

>> So I try it out and it works first time.

>

> No doubt the static typing.

>

>> Maybe the experiment is a success after all.

>

> It'd be interesting to give the same problem to some students and have

> them solve it in Java, C, or whatever the language of the day is.

I tried the experiment in Python (my second-favourite language

after Common Lisp, and arguably one of the "languages of the day"),

producing (as with Alan, on the basis of Paul's pseudocode)

def nth_smallest(items, n):

if len(items) < n: raise "illegal spec"

if len(items) == 1: return items[0]

x = choose_randomly(items)

smaller, equal, larger = split(items, x)

if n < len(smaller): return nth_smallest(smaller, n)

else: n -= len(smaller)

if n < len(equal): return x

else: n -= len(equal)

return nth_smallest(larger, n)

def choose_randomly(items):

return items[random.randint(0,len(items)-1)]

def split(items, pivot):

return [x for x in items if x<pivot], \

[x for x in items if x==pivot], \

[x for x in items if x>pivot]

which also worked first time. (Although there was a little bug

in my trivial test harness.) Elapsed time: a couple of minutes.

So Lisp isn't unique in this respect. I think Ruby or even Perl

would have been a similar story, modulo some reference-related

pain in Perl.

C, C++ or Java would have been a different story altogether.

--

Gareth McCaughan

.sig under construc

Nov 20, 2005, 3:33:44 PM11/20/05

to

I wrote:

> I tried the experiment in Python (my second-favourite language

> after Common Lisp, and arguably one of the "languages of the day"),

> producing (as with Alan, on the basis of Paul's pseudocode)

[etc]

... not noticing that this thread has been quiescent for over

a month. I've been reading c.l.l rather sporadically. Ahem.

Nov 21, 2005, 11:37:41 AM11/21/05

to

Gareth McCaughan <Gareth.M...@pobox.com> writes:

> I wrote:

>

> > I tried the experiment in Python (my second-favourite language

> > after Common Lisp, and arguably one of the "languages of the day"),

> > producing (as with Alan, on the basis of Paul's pseudocode)

> [etc]

>

> ... not noticing that this thread has been quiescent for over

> a month. I've been reading c.l.l rather sporadically. Ahem.

Well it is an interesting thread, and I was thinking of

sticking another post on it myself.

The post I consider most worth discussing has ID

861x2q4...@cawtech.freeserve.co.uk

and is accessible at

http://groups.google.co.uk/group/comp.lang.lisp/msg/a827235ce7466a92?hl=en

I think the question it is discussing is this

Suppose I write down my algorithm in a way that I like

and think is especially clear, but then realise that it

is not written in any particular programming language?

What happens if I get very stiff necked about this and

insist that that is the /right/ way of expressing the

algorithm. Rather than change my text to suit a

particular language, I want to change the language to

encompass the text.

One thing that happens is that it triggers lots of pointless

busy work, fitting the syntax of a well thought out language

to the needs of a jotting specific to an algorithm.

Nevertheless, I feel that this touches on something very

deep. What is a programming language? It seems in practise

that a programming language is the boundary document between

human work and automation. Humans write the program and then

the compiler, the assembler, the linker, and the loader

finish the job.

Horizontal motion of that boundary, to one language or

another seems less interesting than vertical motion of that

boundary, such as making a specification or a pseudo-code

algorithm runnable.

Alan Crowe

Edinburgh

Scotland

Nov 21, 2005, 1:41:05 PM11/21/05

to

Alan Crowe <al...@cawtech.freeserve.co.uk> writes:

> I think the question it is discussing is this

>

> Suppose I write down my algorithm in a way that I like

> and think is especially clear, but then realise that it

> is not written in any particular programming language?

> What happens if I get very stiff necked about this and

> insist that that is the /right/ way of expressing the

> algorithm. Rather than change my text to suit a

> particular language, I want to change the language to

> encompass the text.

>

> One thing that happens is that it triggers lots of pointless

> busy work, fitting the syntax of a well thought out language

> to the needs of a jotting specific to an algorithm.

I think you have that completely backwards. Seeing the algorithm for

the code is often difficult, and often the way the algorithm is

written is very well thought out, not just jotted down. Maintaining

the notation of the algorithm, but in an s-expression form, can be the

easiest way to make the algorithm clear, and the code clearly an

implementation of the algorithm. The work of building Lisp up to the

point of being able to run the pseudo-code is about the same as the

work of implementing it in a funnier-looking way.

--

/|_ .-----------------------.

,' .\ / | Free Mumia Abu-Jamal! |

,--' _,' | Abolish the racist |

/ / | death penalty! |

( -. | `-----------------------'

| ) |

(`-. '--.)

`. )----'

Reply all

Reply to author

Forward

0 new messages