We have been using rrdtool[1] at work, and it's been very handy for us.
Our uses of it have been getting more and more advanced, to the point
where the RPN syntax was getting in the way. So this weekend[2] I wrote a
little Lisp program that converts infix expressions into RPN. It
understands operator precedence and does some tokenising. For example, it
converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
It only took me 66 lines of code to do the whole thing. I did look at
PAIP occasionally, but mostly just for inspiration - I decided that Norvig
was really solving a different problem and that I would do my own thing.
You can find the code at http://www.abstractnonsense.com/convert.lisp.html
Feel free to use it for whatever purpose you want - it's in the public
domain. I'm happy with most of it, but READ-LINE-AS-LIST is ugly (there
*must* be a better way!) and I'm sure LOOP gurus could make
POSITION-OF-MIN a bit prettier.
Anyway, it looks like this might actually see some use in my workplace,
which is a first for Lisp.
Cheers,
Bill.
[1] http://people.ee.ethz.ch/~oetiker/webtools/rrdtool/
[2] To be precise, Sunday morning when I had a bad hangover - that's my
defense in case you think the code sucks ;-)
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
William Bland <·······@abstractnonsense.com> wrote in message news:<······························@abstractnonsense.com>...
> We have been using rrdtool[1] at work, and it's been very handy for us.
> Our uses of it have been getting more and more advanced, to the point
> where the RPN syntax was getting in the way. So this weekend[2] I wrote a
> little Lisp program that converts infix expressions into RPN. It
> understands operator precedence and does some tokenising. For example, it
> converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
Your lisp2rpn function seems to me like it's a bit too close to the
intutive way of doing it by hand, patching it as one encounters
problem cases. I'm reptty sure transforming prefix to postfix is
simply a matter of (recursively) rotating the list so that the first
element of each list, hopefully the operator, becomes the last one.
After that, one only needs to flatten the list for rpn (I see rpn as a
special case of postfix where argument count is implied, and thus
grouping unneeded). I'm not that good with FORMAT, so I'm leaving that
to someone else, although a (barely) working expression is trivial.
;;;; it'd be easy to only traverse the list once, but I doubt the
;;;; gain in efficiency is worth the loss in clarity :)
(defun lisp2rpn (list)
"transform a prefix, grouped expression to rpn.
((1 2 3) (4 5 6) (7 (8 9) 10)) =>
(5 6 4 9 8 10 7 2 3 1)"
(flatten (recursive-rotate list)))
(defun flatten (list)
"recursively flatten lists to a single level.
(1 2 (3 4 5) ((6 7))) => (1 2 3 4 5 6 7)"
(cond ((atom list) (list list))
(t (mapcan 'flatten list))))
(defun recursive-rotate (list)
"recursively rotate the list (the first element becomes last).
(1 2 3 (4 5 6) 7) => (2 3 (5 6 4) 7 1)"
(cond ((atom list) list)
(t (mapcar 'recursive-rotate (rotate-list list)))))
(defun rotate-list (list)
"rotate the list once. (0 1 2 3 ... n) => (1 2 3 ... n 0)"
(append (cdr list) (list (car list))))
CG-USER(28): (lisp2rpn '(- (+ 1 2) (/ 2 3)))
(1 2 + 2 3 / -)
As a bonus, if you ever use higher order functions, you now can (I'm
not sure the original code could do it, but I doubt you care). BTW,
this boilerplate code of recurring only on list is starting to annoy
me. The number of times i've written:
(defun foo (list)
(cond ((atom list) <do something with list>)
(t (mapca? 'foo <do something with list>)))) ;where mapca? is
usually mapcar or mapcan
seems to be quite high to me. I realise this is simple pattern
matching, but I think pattern matching still doesn't cut enough typing
:) This might be my first macro...
On Mon, 08 Nov 2004 16:30:29 -0800, Paul Khuong wrote:
> William Bland <·······@abstractnonsense.com> wrote in message news:<······························@abstractnonsense.com>...
>> We have been using rrdtool[1] at work, and it's been very handy for us.
>> Our uses of it have been getting more and more advanced, to the point
>> where the RPN syntax was getting in the way. So this weekend[2] I wrote a
>> little Lisp program that converts infix expressions into RPN. It
>> understands operator precedence and does some tokenising. For example, it
>> converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
>
> Your lisp2rpn function seems to me like it's a bit too close to the
> intutive way of doing it by hand, patching it as one encounters
> problem cases.
Sure, the reason I didn't care when I wrote it was that lisp2rpn already
did everything necessary to handle the output of infix2lisp, and so
no more generality was necessary for the purpose of the program. I do
like the implementation you posted though!
Cheers,
Bill.
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
William Bland <·······@abstractnonsense.com> writes:
> We have been using rrdtool[1] at work, and it's been very handy for
> us. Our uses of it have been getting more and more advanced, to the
> point where the RPN syntax was getting in the way.
"RPN syntax . . . getting in the way." You know, just because a
sentence is grammatically correct doesn't mean it says anything
meaningful....
Seriously, could you expand on this a bit? Perhaps I rewired my
brain by excessive use of HP calculators in college, but I prefer RPN
to infix.
Regards,
Patrick
On Tue, 09 Nov 2004 12:03:59 +0000, Patrick May wrote:
> William Bland <·······@abstractnonsense.com> writes:
>> We have been using rrdtool[1] at work, and it's been very handy for
>> us. Our uses of it have been getting more and more advanced, to the
>> point where the RPN syntax was getting in the way.
>
> "RPN syntax . . . getting in the way." You know, just because a
> sentence is grammatically correct doesn't mean it says anything
> meaningful....
Fair enough.
> Seriously, could you expand on this a bit? Perhaps I rewired my
> brain by excessive use of HP calculators in college, but I prefer RPN
> to infix.
I am agnostic on this - I barely notice a difference when I switch between
infix, prefix and RPN. I'll happily use any of the three. But I work
with people who are allergic to anything remotely unusual (which is why me
getting to use Lisp here is rather amazing). RPN syntax was getting in
*their* way.
Cheers,
Bill.
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
William Bland <·······@abstractnonsense.com> wrote in message news:<······························@abstractnonsense.com>...
> On Tue, 09 Nov 2004 12:03:59 +0000, Patrick May wrote:
>
> > William Bland <·······@abstractnonsense.com> writes:
> >> We have been using rrdtool[1] at work, and it's been very handy for
> >> us. Our uses of it have been getting more and more advanced, to the
> >> point where the RPN syntax was getting in the way.
[...]
> > Seriously, could you expand on this a bit? Perhaps I rewired my
> > brain by excessive use of HP calculators in college, but I prefer RPN
> > to infix.
>
> I am agnostic on this - I barely notice a difference when I switch between
> infix, prefix and RPN. I'll happily use any of the three. But I work
> with people who are allergic to anything remotely unusual (which is why me
> getting to use Lisp here is rather amazing). RPN syntax was getting in
> *their* way.
Mmm. Interesting. How do they deal with the precedence of unary and
binary minus? (Aaah, unary minus having lower precedence than
exponentiation. The source of so many middle school errors :)
Actually, how does your parser deal with them? I only took a quick
look at the infix2lisp part, so i'm not sure how it copes with that
problem.
·······@gmail.com (Paul Khuong) writes:
> Mmm. Interesting. How do they deal with the precedence of unary and
> binary minus? (Aaah, unary minus having lower precedence than
> exponentiation. The source of so many middle school errors :)
> Actually, how does your parser deal with them? I only took a quick
> look at the infix2lisp part, so i'm not sure how it copes with that
> problem.
I don't know who the various infix languages cope with it, but I know
how I do: add parenthesis!
((-n)^2)-1
or: -((n^2)-1)
--
__Pascal Bourguignon__
On Tue, 09 Nov 2004 18:40:24 -0800, Paul Khuong wrote:
> William Bland <·······@abstractnonsense.com> wrote in message news:<······························@abstractnonsense.com>...
>> On Tue, 09 Nov 2004 12:03:59 +0000, Patrick May wrote:
>>
>> > William Bland <·······@abstractnonsense.com> writes:
>> >> We have been using rrdtool[1] at work, and it's been very handy for
>> >> us. Our uses of it have been getting more and more advanced, to the
>> >> point where the RPN syntax was getting in the way.
> [...]
>> > Seriously, could you expand on this a bit? Perhaps I rewired my
>> > brain by excessive use of HP calculators in college, but I prefer RPN
>> > to infix.
>>
>> I am agnostic on this - I barely notice a difference when I switch between
>> infix, prefix and RPN. I'll happily use any of the three. But I work
>> with people who are allergic to anything remotely unusual (which is why me
>> getting to use Lisp here is rather amazing). RPN syntax was getting in
>> *their* way.
>
> Mmm. Interesting. How do they deal with the precedence of unary and
> binary minus?
Hehe, if I had enough time to wonder how other peoples' minds work as well
as getting my own job done, I'd be a happy man.
> Actually, how does your parser deal with them? I only took a quick
> look at the infix2lisp part, so i'm not sure how it copes with that
> problem.
Actually it didn't handle unary minus at all. It was a very quick fix
though (all of thirty seconds). I just tweaked the tokeniser so that it
breaks on an operator only if the last character was not an operator as
well, so:
"1-1" => "1 - 1"
but
"1+-1" => "1 + -1"
The fixed version is at http://www.abstractnonsense.com/convert.lisp.html
Perhaps it's a little hacky, perhaps one day I'll care enough to improve
it. For now though I have problems at work that are big enough that even
Lisp can't help :-(
Cheers,
Bill.
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
William Bland <·······@abstractnonsense.com> writes:
> We have been using rrdtool[1] at work, and it's been very handy for us.
> Our uses of it have been getting more and more advanced, to the point
> where the RPN syntax was getting in the way. So this weekend[2] I wrote a
> little Lisp program that converts infix expressions into RPN. It
> understands operator precedence and does some tokenising. For example, it
> converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
>
> It only took me 66 lines of code to do the whole thing. I did look at
> PAIP occasionally, but mostly just for inspiration - I decided that Norvig
> was really solving a different problem and that I would do my own thing.
>
I found your example interesting and posted it to e-mail list
of CS department of Bilgi University. One of the professors
(who is also giving Scheme lessons using the Purple Book and
admits that he likes Lisp) claimed that a lex/yacc based solution
that creates a table driven tokeniser and parser would be simpler
and more flexible.
He stressed that the solution being the same had the
advantage of being table driven and thus making it
easier to add rules.
To support his claim he provides the source code for
his solution:
A simle lex + simple LL(1) top down parser:
http://cs.bilgi.edu.tr/pages/courses/year_4/comp_412/Archive/2003-2004/Examples/week_7/
And a simpel YACC example:
http://cs.bilgi.edu.tr/pages/courses/year_4/comp_412/Archive/2003-2004/Examples/week_9/parse.y.txt
No, this post does not intend to start another endless language
war (we all know "language wars are moot"). I just wanted to know
people's ideas about this alternative solution. Thus I'm targeting
people who knows Lisp and C well, which solution is more powerful
and more flexible/extensible according to you and why?
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
On Wed, 10 Nov 2004 23:17:09 +0200, Emre Sevinc wrote:
> William Bland <·······@abstractnonsense.com> writes:
>
>> We have been using rrdtool[1] at work, and it's been very handy for us.
>> Our uses of it have been getting more and more advanced, to the point
>> where the RPN syntax was getting in the way. So this weekend[2] I wrote a
>> little Lisp program that converts infix expressions into RPN. It
>> understands operator precedence and does some tokenising. For example, it
>> converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
>>
>> It only took me 66 lines of code to do the whole thing. I did look at
>> PAIP occasionally, but mostly just for inspiration - I decided that Norvig
>> was really solving a different problem and that I would do my own thing.
>>
> I found your example interesting and posted it to e-mail list
> of CS department of Bilgi University. One of the professors
> (who is also giving Scheme lessons using the Purple Book and
> admits that he likes Lisp) claimed that a lex/yacc based solution
> that creates a table driven tokeniser and parser would be simpler
> and more flexible.
More than likely. I'm strange - I enjoy writing parsers by hand ;-)
Certainly for anything more complex than the problem I was solving, I
would use a real parser-generator (I use ANTLR a lot at work).
Cheers,
Bill.
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
Emre Sevinc <·····@bilgi.edu.tr> writes:
> William Bland <·······@abstractnonsense.com> writes:
>
>> We have been using rrdtool[1] at work, and it's been very handy for us.
>> Our uses of it have been getting more and more advanced, to the point
>> where the RPN syntax was getting in the way. So this weekend[2] I wrote a
>> little Lisp program that converts infix expressions into RPN. It
>> understands operator precedence and does some tokenising. For example, it
>> converts "sin(x^2)+cos(1+1/x)" into "x,2,^,sin,1,1,x,/,+,cos,+".
>>
>> It only took me 66 lines of code to do the whole thing. I did look at
>> PAIP occasionally, but mostly just for inspiration - I decided that Norvig
>> was really solving a different problem and that I would do my own thing.
>>
>
> I found your example interesting and posted it to e-mail list
> of CS department of Bilgi University. One of the professors
> (who is also giving Scheme lessons using the Purple Book and
> admits that he likes Lisp) claimed that a lex/yacc based solution
> that creates a table driven tokeniser and parser would be simpler
> and more flexible.
>
> He stressed that the solution being the same had the advantage of
> being table driven and thus making it easier to add rules.
You can do the same thing in Common Lisp with an appropriate parser
generator. You might take a look at the code at:
<http://www.gigamonkeys.com/lisp/>
I think it actually works and stuff--it's been a while since I wrote
it. math-parser.lisp in particular should be of interest because I
think it's more or less equivalent to the lex-based version your
professor wrote. It doesn't handle exponentiation or named functions
like sin and cos, though; exercise for the reader and all that.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
"Emre Sevinc" <·····@bilgi.edu.tr> wrote in message
···················@bilgi.edu.tr...
> He stressed that the solution being the same had the
> advantage of being table driven and thus making it
> easier to add rules.
Two comments.
One, his solution effectively uses two different languages.
Two, the Lisp solution is also (lightly) table driven. It's table is the
operator precedance table. The other "hidden table" is in the "infix2lisp"
routine where he can easily put special cases.
Once he has a routine in his Lisp form, the RPN form (which is the goal of
this little tool) comes "for free".
Note how in the C code, several of the symbols (defined in the YACC/LEX
file) are used several times. The PLUS symbol alone is in there 5 times.
This implies that should I want to add the ~ operator (whatever that may
be), I'd have to add that several times into several places with the code,
as well as the YACC/LEX source file.
In the Lisp example, I'd need to simply add it to the operators list.
Granted, the C code seems to be doing something different, though similar,
to the Lisp code, but even though it's table driven, it's not clear that
it's that much more flexible. In fact, I'd argue that as the table grows, it
would get yet more and more inflexible.
Regards,
Will Hartung
(·····@msoft.com)