Dear Collegue,
I am a beginner in Lisp. Recently I have been doing a programming
exercise in Lisp which is to build a test-tree using a so-called ID3
algorithm in A.I. one of the smaller tasks to solve this problem is to
make "not not a" (ie. '(--a) ) equals "a"; where "a" is any atom in
Lisp. This is trivial in Maths, but to make this equivalence work in
Lisp seems very tricky to me. My main difficulty is that I don't know
how to separate '(--a) into "-", "-" and "a". once I know how to do this
the problem is straight forward.
Thanks.
--
yuanxi
Sent via Deja.com http://www.deja.com/
Before you buy.
(defun --(arg)
arg)
(equal (-- 'a) 'a) --> t
(defvar foo 'bar)
(equal (-- foo) foo) --> t
(equal (-- foo) 'bar) --> t
This doesn't do exactly what you seem to want, '(--a) equals 'a , but it doesn't make
sense (to me) to ask for quoted structures that are not equal to be equal....
but i am not familiar with your problem.
Coby
if you use a richer character set, you can use the ¬ operator (found in
ISO 8859-1, or "ISO Latin 1", also known among Microsoft victims as "the
ANSI character set"), and you can teach your Common Lisp reader to make
that a single-character operator that either returns itself or returns
the "not" operator already in the language, listifying its argument like
quote (') does.
(defun not-reader (stream char)
(list 'not (read stream nil nil t)))
(set-macro-character #\¬ #'not-reader nil)
'¬¬a
=> (not (not a))
simplifying this expression can now be done at the semantic level, which
basically entails walking over your expressions looking for not forms and
replacing the form with the cadadr of the form.
the normal evaluation rules in Common Lisp makes (not (not a)) the
canonical true boolean value, t, for any non-nil a, and nil for nil.
don't know if this answered your question, it's kind of vague.
#:Erik
If what you *really* meant to say was:
to make "(not (not a))" equal "a", where "a" is any atom in Lisp
then that is not possible, because in Lisp it simply isn't true!!
In Lisp, the "not" operator maps everything to a boolean value,
which throws away information which is significant in equality
comparisons. Repeating the "not" operator cannot undo that loss
of information, since it's gone, gone, gone...
> (equalp 123 (not (not 123)))
==> NIL
> 123
==> 123
> (not 123)
==> NIL
> (not (not 123))
==> T
>
Likewise:
> (equalp 'a (not (not 'a)))
==> NIL
> 'a
==> A
> (not 'a)
==> NIL
> (not (not 'a))
==> T
>
And further:
> (defvar a 'bcd)
==> A
> (equalp a (not (not a)))
==> NIL
> a
==> BCD
> (not a)
==> NIL
> (not (not a))
==> T
>
+---------------
| This is trivial in Maths
+---------------
Wrong. It is neither trivial nor correct. Remember, you said
``where "a" is *ANY* atom in Lisp'' [emphasis added], not just
boolean-valued expressions (boolean atoms, variables currently
holding boolean values, etc.).
Only if you restrict yourself to boolean-valued expressions does
what you're attempting make any sense.
-Rob
-----
Rob Warnock, 41L-955 rp...@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
> Dear Collegue,
>
> I am a beginner in Lisp. Recently I have been doing a programming
> exercise in Lisp which is to build a test-tree using a so-called ID3
> algorithm in A.I. one of the smaller tasks to solve this problem is to
> make "not not a" (ie. '(--a) ) equals "a"; where "a" is any atom in
> Lisp. This is trivial in Maths, but to make this equivalence work in
> Lisp seems very tricky to me. My main difficulty is that I don't know
> how to separate '(--a) into "-", "-" and "a". once I know how to do this
> the problem is straight forward.
Forgive my sarcasm here, but I see a deeper problem here.
Would you answer this question?
Do you write C code like
[A]
if(x==-1) {
ww=x*(-3*a[i]);
return sin(ww*a[i+2]);
}
or
[B]
if (x == -1)
{
ww = x * (-3 * a[i]);
return sin(ww * a[i + 2]);
}
?
The answer to this questio will tell me how to answer your question.
(BTW. Of course the Numerical Recepies vi-indented style is disgusting :) ).
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
> (BTW. Of course the Numerical Recepies vi-indented style is disgusting :) ).
You are unduly harsh on vi, as there are sufficient problems with `Numerical
Recipies in C' that are total not vi related,
;) will
Am I the only one who thinks the original poster's question has nothing to
do with Lisp's ordinary calculations, and what he's actually trying to
write is some kind of symbolic logic simplifier? He mentioned it was an AI
application. In boolean algebra, not not a is equivalent to a.
--
Barry Margolin, bar...@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
The way you would want to represent this in Lisp is as:
(not (not a))
Once you have the operators separate from the propositions and variables
in your logic, manipulating them becomes fairly simple in Lisp. It is
just a matter of choosing an appropriate representation.
So, you could then have the following code, which also has the nice
benefit of applying to arbitrary formulae, not only to atomic formulae.
(defun simplify (formula)
(cond ((atom formula) formula)
((and (eq (first formula) 'not)
(consp (second formula))
(eq (first (second formula)) 'not))
(simplify (second (second formula))))
... ;; other simplification rules go here ...
))
(simplify '(not (not (and a b)))) => (AND A B)
(simplify '(not (not (not (not (not c)))))) => (not C)
You could also create functions for moving formulae into some canonical
form such as conjunctive or disjunctive normal form, applying de
Morgan's law, etc. It is actually all fairly easy to do once you adopt
a representation of the logic in terms of Lisp-style predicates and
arguments. In fact, this is one of really early applications of Lisp.
If you really, really want to have "--a" as input syntax, you would do
well to write a parser that produces lisp-friendly structures (probably
lists) and do your manipulation in the Lisp-friendly structures.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
could "Numerical Recipes in Common Lisp" be an idea? as far as I can see
from the code in the C version, about 40% of it is directly related to
managing object types that don't fall naturally into the C domain, and it
appears that the significant reduction in object management alone would
make a Common Lisp implementation of much if not all of this interesting.
#:Erik
> David <tia...@cs.man.ac.uk> wrote:
> +---------------
> | make "not not a" (ie. '(--a) ) equals "a"; where "a" is any atom in Lisp.
> +---------------
>
> If what you *really* meant to say was:
>
> to make "(not (not a))" equal "a", where "a" is any atom in Lisp
>
> then that is not possible, because in Lisp it simply isn't true!!
Or he may have meant (- (- a)). What you say still holds, this time
because a must be a number, not an arbitrary atom.
> In Lisp, the "not" operator maps everything to a boolean value,
> which throws away information which is significant in equality
> comparisons. Repeating the "not" operator cannot undo that loss
> of information, since it's gone, gone, gone...
you've lost that information, whoa, that information.
You've lost the information, now it's gone, gone, gone...
(Apologies to the Everly Brothers (I think))
--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Rethink some Lisp features, http://world.std.com/~tob/rethink-lisp/index.html
Ah, I think I see the confusion. Are you really asking how to *parse*
the string "--a" into the abstract syntax tree '(- (- a)), or
'(my-negate (my-negate a)) or some such?
When you wrote the Lisp form '(--a) above, the ng mostly assumed that
parsing was not an issue, because in Lisp it's almost always a
non-issue. `read' gives us an abstract syntax tree, we don't
generally have to work for it.
I suggest that it's better to simply adopt a more Lisp-friendly
notation.
> (Apologies to the Everly Brothers (I think))
Righteous Brothers.
--tim
Well, numerical recipies doesn't have an exactly glowing reputation,
eg:
http://math.jpl.nasa.gov/nr/nr.html
But I'd have thought there must be sufficient people doing or
interested in doing numerical analysis in lisp to make a book viable
(like me, but only for a fairly lowbrow uni assignment).
And, oh look:
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/numrecip/0.html
(it's only an incomplete translation).
I'd guess a major stumbling block for the budding lisp-using numerical
analyst is the comparative lack of libraries; writing fast, stable and
accurate numerical code is absurdly difficult, and the existence of
such for fortran is a strong argument for using it.
It would be cool if someone did write libraries for lisp, but it's a
lot of work.
I'd have thought lisp, with it's higher order functions, symbolic
manipulation capabilities, compiler macros and such would be a great
platform for numerical analysis. Room for expansion maybe?
Cheers,
Michael
--
... but I guess there are some things that are so gross you just have
to forget, or it'll destroy something within you. perl is the first
such thing I have known. -- Erik Naggum, comp.lang.lisp
[..elided some excellent reasons why this would be a good idea...]
<rant>
On top of this, another (of the many things) that gets me about the `Numerical
Recipes in C' is the complete non-reusability of the code. For example: the same
basic QR decompostion technique is used several times in the book (see the qr
and hqr subroutines). However, no attempt is made to try and pull out common
functionality and the stylistic opaqueness coupled with the difficulties of
object management make the whole thing a nightmarish read. But then again this
may infact be what the authors intended. (sigh)
</rant>
Best Regards,
:) will
Possibly. Part of the reason that Fortran is still popular
in the world of high performance computing is that such
people care about even small differences of speed, often
because they are working on problems that take weeks or
sometimes even months to solve. Some of these folks won't
even use C in lieu of Fortran.
C/
Also popular because a very useful collection (and well tested)
of routines are readily available (see www.netlib.org)
Tunc
Exactly. ;-)
Sorry to all here, but that's why I ended up giving up on common lisp.
With netlib, I could get routines that were tested by actual numeric
analysts. I don't have time to learn all the features of numerics, so
I want tested routines. the Fortran->CL converter helped a lot, but
it was too hard to get it to talk to other things.
(And, yes, I know that I was lame. Still, though.)
--
Johann Hibschman joh...@physics.berkeley.edu
> > I'd have thought lisp, with it's higher order functions, symbolic
> > manipulation capabilities, compiler macros and such would be a great
> > platform for numerical analysis. Room for expansion maybe?
>
> Possibly. Part of the reason that Fortran is still popular
> in the world of high performance computing is that such
> people care about even small differences of speed, often
> because they are working on problems that take weeks or
> sometimes even months to solve. Some of these folks won't
> even use C in lieu of Fortran.
Yah, but I'd have thought it possible to make CL nearly as fast as
Fortran, and faster than C. It was my understanding that for highly
numerical codes C was slower than Fortran basically because the
pointer model of C prohibited the use of certain optimizations
(because you can never rule out the possibility that some other part
of the program has a pointer to the middle of your critical data
structure). Lisp doesn't share this yoke, so given a sufficiently
clever compiler, speeds in excess of C might be possible (witness
stalin in the scheme world).
Also development flexibility in important for numerical analysts too;
I mean, a computation that takes a week and a half is better than one
that takes a week and gets it wrong.
Not that I could (or would want to) claim to be a numerical analyst...
Cheers,
M.
--
please realize that the Common Lisp community is more than 40
years old. collectively, the community has already been where
every clueless newbie will be going for the next three years.
so relax, please. -- Erik Naggum, comp.lang.lisp
Anything is possible. There's a whole "High Performance Computing
for Java" movement. Go figure.
I wonder if an extra week of runtime costs more than an extra
week of developer's time? For that matter, I wonder how much
overall time can be saved by having a sufficiently shorter
developer cycle?
...
C/
Well, not knowing anything about it... nevertheless I still
wonder if you couldn't have integrated it through an external
interface?
I suppose, depending on your application, it might be more
trouble than it's worth to work in a multi-linguistic
environment?
C/
> Well, not knowing anything about it... nevertheless I still
> wonder if you couldn't have integrated it through an external
> interface?
Sure you can. Once you write wrapper routines that give you a lispy
interface to the Fortran routines needed, you get a very nice
environment for exploratory numerical programming.
On the flip side, you end up with code that relatively few people find
easy to understand. Moreover, the code as such will work only in a
single Lisp system, because you are depending on a specific foreign
function interface.
Hannu Rummukainen
> > Yah, but I'd have thought it possible to make CL nearly as fast as
> > Fortran, and faster than C.
> I wonder if an extra week of runtime costs more than an extra
> week of developer's time? For that matter, I wonder how much
> overall time can be saved by having a sufficiently shorter
> developer cycle?
Well, take this with a certain pinch of salt, because although I did
work with a supercomputer I wasn't really close to the people who made
decisions.
My overwhelming impression that I took away from working with
biologists over a summer on porting their programmes to a
supercomputer is that, indeed, a week of runtime costs vastly more
than a week of developer time. This was for a Hitachi supercomputer
(pseudo-vectorising, loop-unrolling, yadda yadda yadda), although from
a scientific point of view the idea was to identify bottlenecks and
think about ways of optimizing, rather that specifically for the
Hitachi[1]; in other words, "make people happy about using
supercomputers" rather than "make sure that people are so impressed by
the go-faster stripes on this thing".
The point being, of course, that not only is extra time being taken on
this supercomputer time when you don't have the answer, it's also time
that some other scientist can't use the supercomputer to do one of his
calculations. So there's a double loss. Also, the running costs of one
of these beasts (electricity, cooling, and so on) are quite large, and
so there is a tangible monetary cost associated with having programmes
with suboptimal speed.
The irony in all this is that the Hitachi machine that I was meant to
be working on was slow. Not terribly slow, and it did fast-Fourier
transforms relatively quickly, but it was a pain to use and it wasn't
terribly fast (it was old).
I suppose the point of this message is that there are sometimes
different priorities that are even justified in a small sense;
however, given that I may well have significant numerical and
computational parts to my PhD next year[2] I would much prefer not to
have to undergo the pain of FORTRAN again.
Christophe
[1] Though my then employers might have disagreed; fortunately, I
spent much more time at Cambridge than at Maidenhead.
[2] Assuming I pass the relevant exams.
--
(macrolet ((f (a b) `(unless (equal ,a "") (princ (aref ,a 0)) (setf ,a
(subseq ,a 1)) (,b))) (z (&rest a) `(format nil "~@{~35r~^ ~}" ,@a))) (
let ((w (z 693 29204 28104384)) (x (z 1984050605838 12977))) (labels ((
y () (f w z))(z () (f x y))) (y) (terpri))))#|Jesus College,Cambridge|#
Almost never, but occasionally. For supercomputer-type applications
the cost of runtime may be critical -- the canonical example is
forecasting the weather where runtime really matters. Also anything
where the machine is a scarce resource (because there is only one) can
cause runtime to be very expensive.
of course, it's one of the classic mistakes when arguing about
performance that this situation generalises. As you say, development
time matters much more than runtime for most developers (if they would
only realise this...), so a system that compiles really fast, like
Lisp, is a big win. Most ordinary users should almost never need to
care about performance outside games now, although a lot of programs
are written *so* badly that they may have to.
--tim
Fortran's continued popularity owes something to C's lack of a complex
type, exponentiation operator, and to the relative difficulty of passing
multi-dimensional arrays around.
Johann> Sorry to all here, but that's why I ended up giving up on common lisp.
Johann> With netlib, I could get routines that were tested by actual numeric
Johann> analysts. I don't have time to learn all the features of numerics, so
Johann> I want tested routines. the Fortran->CL converter helped a lot, but
Johann> it was too hard to get it to talk to other things.
Could you elaborate on how f2cl was "too hard to get it to talk to
other things"? I'm curious. Other than the unsupported features, the
only difficulty I've had is Fortran's practice of passing around parts
of an array where f2cl doesn't work.[1]
However, in general I agree with you. The best solution is hooking up
Fortran code via a foreign function interface. However, somethings,
just can't easily be done that way. Consider trying to hook up
Fortran Quadpack (numerical integration) where the function you want
to integrate is in Lisp. (I have converted Quadpack to Lisp via
f2cl. It works just fine.)
Well, this is rather hard in CMUCL. I've never looked into doing this
with other Lisps.
Ray
Footnotes:
[1] Things like
real x(1000)
...
call sub(x(10))
f2cl thinks this calls the routine sub with a single real
argument x(10), but sub is really expecting an array, so things
don't work. To get this to work, you have to modify the code by
hand. Alternatively, if sub was known by f2cl to take an array,
the appropriate code could be generated. This is on my
always-growing, never-shrinking TODO list.
http://cvs.sourceforge.net/cgi-bin/cvsweb.cgi/?cvsroot=matlisp
or you can visit the matlisp homepage:
http://matlisp.sourceforge.net
Regards,
Tunc
>>>>>> "Johann" == Johann Hibschman <joh...@physics.berkeley.edu> writes:
Johann> Sorry to all here, but that's why I ended up giving up on common lisp.
Johann> With netlib, I could get routines that were tested by actual numeric
Johann> analysts. I don't have time to learn all the features of numerics, so
Johann> I want tested routines. the Fortran->CL converter helped a lot, but
Johann> it was too hard to get it to talk to other things.
> Could you elaborate on how f2cl was "too hard to get it to talk to
> other things"? I'm curious. Other than the unsupported features, the
> only difficulty I've had is Fortran's practice of passing around parts
> of an array where f2cl doesn't work.[1]
To be honest, I somewhat regret opening my mouth; my reasons are
entirely subjective, and I was just feeling a bit punchy when I wrote
that. Don't expect a solid technical argument. ;-)
Basically, I like Python. The programming language, not the CMUCL
compiler. Whenever I have a numerical problem, I wrap the
speed-intensive parts up in a C library, then write the smart parts in
Python. Lawrence Livermore National Labs is supporting a nice
array-manipulation library in python, with access to some good
plotting routines. It's a nice environment to work in.
I like Common Lisp, too. It has a few features which make it very
attractive for numeric work, like the ability to pass around functions
in an intelligent manner, the ability to only declare/optimize the
parts that need declaring, and so on.
In the best of all possible worlds, I could write a shared library in
Common Lisp, doing some things which are smart, but fast, and then get
that talking to the rest of my python code. I didn't have much luck
with this; CL likes to be on top. This is what I had in the back of
my mind when I said it was too hard to get to talk to other things.
Alternatively, I could just use the CL REPL as my numeric workbench.
However, it's just not as nice as Python. I'd have to track down or
build my own string-manipulation and regexp libraries (for IO, parsing
datafiles, etc.), my own convenient array package, and probably work
up some syntax to make the whole thing usable.
I thought about it. But I ended up deciding it would take too much
work for too little gain, and stuck with Python and C. f2c is robust,
there are a few numeric libraries in C and everything knows how to
talk to C. C does the grinding, Python does the thinking; sometimes I
lose some speed because of the barrier between the two, but I'm
resigned to it.
There's also the social issue; no one else would be able to read my
code or understand it, and future generations of grad students would
probably curse the hideous Lisp application they had to use. ;-)
--
Johann Hibschman joh...@physics.berkeley.edu
> There's also the social issue; no one else would be able to read my
> code or understand it, and future generations of grad students would
> probably curse the hideous Lisp application they had to use. ;-)
Well, I can't read perl or tcl. I guess future generations will curse you when
the Python and Java fads will have faded and Lisp dialects become ubiquitous.
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
> Johann Hibschman wrote:
>> There's also the social issue; no one else would be able to read my
>> code or understand it, and future generations of grad students would
>> probably curse the hideous Lisp application they had to use. ;-)
> Well, I can't read perl or tcl. I guess future generations will
> curse you when the Python and Java fads will have faded and Lisp
> dialects become ubiquitous.
Nah, they'll just be unhappy that I didn't use Fortran77, like
everyone else in astronomy. ;-)
--
Johann Hibschman joh...@physics.berkeley.edu
(Of course, I did lose some potential efficiency converting the
Fortran to C, but not enough to matter to my application.)
--
David H. Thornley | If you want my opinion, ask.
da...@thornley.net | If you don't, flee.
http://www.thornley.net/~thornley/david/ | O-
Johann> However, it's just not as nice as Python. I'd have to track down or
Johann> build my own string-manipulation and regexp libraries (for IO, parsing
Johann> datafiles, etc.), my own convenient array package, and probably work
Johann> up some syntax to make the whole thing usable.
What string-manipulation routines are missing from Lisp? There are
regexp libraries in Lisp. I even wrote an interface for Clisp to GNU
regex many years ago, just at the same time as Bruno Haible added the
same thing to Clisp. It was quite easy.
Johann> I thought about it. But I ended up deciding it would take too much
Johann> work for too little gain, and stuck with Python and C. f2c is robust,
Johann> there are a few numeric libraries in C and everything knows how to
Johann> talk to C. C does the grinding, Python does the thinking; sometimes I
Johann> lose some speed because of the barrier between the two, but I'm
Johann> resigned to it.
Exactly what I had in mind for Matlisp (that Tunc Simsek has taken
over and immensely improved): Lisp does the other stuff, Fortran
grinds the matrices.
Johann> There's also the social issue; no one else would be able to read my
Johann> code or understand it, and future generations of grad students would
Johann> probably curse the hideous Lisp application they had to use. ;-)
Which won't prevent future generations of grad students from the
hideous Python application they have to use. :-) (No offense!)
I understand the social part. It doesn't matter how great it is if
someone else to use it and modify it and doesn't even know the
language.
Ray
>>>>>> "Johann" == Johann Hibschman <joh...@physics.berkeley.edu> writes:
Johann> However, it's just not as nice as Python. I'd have to track
Johann> down or build my own string-manipulation and regexp libraries
Johann> (for IO, parsing datafiles, etc.), my own convenient array
Johann> package, and probably work up some syntax to make the whole
Johann> thing usable.
> What string-manipulation routines are missing from Lisp? There are
> regexp libraries in Lisp. I even wrote an interface for Clisp to
> GNU regex many years ago, just at the same time as Bruno Haible
> added the same thing to Clisp. It was quite easy.
I was just thinking of basics like split, join, find, strip, etc. For
some reason, I prefer to see '"foo" + "bar"' rather than '(concatenate
'string "foo" "bar")', and 'string.join(["some", "words"])' to, well,
'(concatenate 'string "some" " " "words")'.
There's no reason I couldn't use
(string-utils:join '("some" "more" "words"))
and so on, but python is here, has a large standard library, has nice
html documentation for that library, has lisp-like doc-strings (not
quite as advanced, though), and so on.
I just find it convenient. It's all there, it's done for me. Nothing
else to download, no documentation trees to build, etc. (I somehow
find the python library docs easier to browse than the hyperspec, but
I'm not sure why; maybe the python index speaks to me more. ;-) )
I don't have any major problems with the language or syntax, I have
yet to run into a case where I felt I needed some macros, and it's
easy enough to integrate C. Python's biggest flaw, which hasn't bit
me yet, is that it is reference-counted, not truly garbage-collected,
so circular datastructures are a problem. That's being fixed, though.
In short, of course there's nothing missing from CL. If I were doing
a giant complicated industrial application, I'd probably use it
instead of Python. I've just found python to be more convenient for
the things I actually do. YMMV.
--
Johann Hibschman joh...@physics.berkeley.edu