pure-lang-users

[pure-lang-users] Swapping Symbols and Integers

[David B. <dh...@gm...>]

Hi,

I'm new to Q/Pure, and I've searched the archives a little and the "Q
in a Nutshell" doc a lot, but maybe I missed something.  I have been
just using Q up until now (because I only just found out about Pure).
I would like rewrite an expression like:

    4 * a * 3

to this:

    12 * a

So, I thought maybe I could create a rule like this:

    A:Symbol * B:Integer = B * A;
    // and maybe some more rules for associativity/commutivity

but, like I guessed, I get an undeclared type error for Symbol and
Integer (I think the type guards have to be algebraic types, not
simple expressions).  Is there a way to achieve this in Q or Pure?

Thanks,
-David

Re: [pure-lang-users] Swapping Symbols and Integers

[Albert G. <Dr....@t-...>]

Hi David,

David Baird wrote:
> So, I thought maybe I could create a rule like this:
> 
>     A:Symbol * B:Integer = B * A;
>     // and maybe some more rules for associativity/commutivity

There's not type for symbols in either Pure or Q, and in Q the type of 
integers is named Int (section 8.2 of the manual), int and bigint in 
Pure. To check for free variable symbols, there's the isvar predicate, 
described in Section 10.8 of the manual (varp in Pure, see primitives.pure).

So something like this should do the job in Pure:

a*b::int = b*a if varp a;
x*a*b::int = x*b*a if varp a;

(In addition, you'll probably need some associativity rules to make this 
work in the general case.)

HTH,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [pure-lang-users] Swapping Symbols and Integers

[David B. <dh...@gm...>]

On Fri, Aug 8, 2008 at 3:30 AM, Albert Graef <Dr....@t-...> wrote:
> So something like this should do the job in Pure:
>
> a*b::int = b*a if varp a;
> x*a*b::int = x*b*a if varp a;
>
> (In addition, you'll probably need some associativity rules to make this
> work in the general case.)

Excellent, thanks!  I finally got your suggestion to work in Pure.
(Took awhile because I had to work around having multiple versions of
LLVM installed though so that pure-0.4 would build).

I also got it to work in Q:

    A * B:Int = B * A if isvar A;
    X * A * B:Int = X * B * A if isvar A;
    A * (B * C) = A * B * C;

Then, I can ask it to reduce an expression like:

    ==> 3 * ((A * 2) * 4)

and I get:

    24*A

-David

Re: [pure-lang-users] Swapping Symbols and Integers

[Albert G. <Dr....@t-...>]

David Baird wrote:
> Excellent, thanks!  I finally got your suggestion to work in Pure.

Great. :) Are you writing a CAS in Pure? There's already some nice stuff 
by Rob Hubbard to deal with rationals and polynomials, it only needs to 
be ported over (currently it's written in Q).

> (Took awhile because I had to work around having multiple versions of
> LLVM installed though so that pure-0.4 would build).

Yeah, I really have to get Pure 0.5 out of the door soon. I just fixed 
one showstopper, two more bugs to go.

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [pure-lang-users] Swapping Symbols and Integers

[David B. <dh...@gm...>]

On Sat, Aug 9, 2008 at 5:11 AM, Albert Graef <Dr....@t-...> wrote:
> David Baird wrote:
>> Excellent, thanks!  I finally got your suggestion to work in Pure.
>
> Great. :) Are you writing a CAS in Pure? There's already some nice stuff
> by Rob Hubbard to deal with rationals and polynomials, it only needs to
> be ported over (currently it's written in Q).

Well, not a CAS exactly but probably very related.  I'll definitely
keep checking out Q.  I originally tried cracking open the source code
to Maxima and then realized that was going to be more than just an
hour of effort (partly because I don't have enough Lisp experience
yet).  Then I discovered Q and was very impressed by the conciseness
of Q (and then discovered Pure).  What I'm kinda playing around with
is compilers and also just systems integration in general.  As far as
compilers though, I've mentally broken them down like this:

1. Parsing
2. Term rewriting for doing AST manipulation (Q seemed a good match
here).  Mostly, I was interested in taking an expression and
normalizing it to a sum-of-products format.
3. (maybe something else goes in the middle here?)
4. Optimization to try to ensure that pipelines in a CPU are kept full
or that processing latency is minimized (using Prolog, integer linear
programming, ...)
5. Writing out the results

I'm trying to use declarative tools to achieve these goals.  Also, I
don't really have much experience with compilers so I am just goofing
around really.  Some of my coworkers have also been doing great work
by using high level tools such as OCaml and Prolog.  I'm actually
kinda confused about why people insist on using C to write compilers
when there are such great higher level tools available?

I'm also investigating the possibility of implementing an expression
representation system (probably a thin layer around sexps) in Python.
The idea is that I can then layer term rewriters on top of this (this
is how I discovered Q in the first place), and also be able to provide
nearly seamless integration between Python and constrained
optimization tools (like CVXOPT, GLPK, LP_SOLVE), and probably other
tools too (like ODE solvers?).

*phew* Hope that description wasn't too long.  Sometimes I enjoy
talking too much.

-David

Re: [pure-lang-users] Swapping Symbols and Integers

[Albert G. <Dr....@t-...>]

David Baird wrote:
> Well, not a CAS exactly but probably very related.  I'll definitely
> keep checking out Q.

Note that Q will eventually be replaced by Pure, so it's a good idea to 
already check out the latter, even if it's still a bit rough around the 
edges here and there. I hope that the forthcoming 0.5 release will be 
bug-free and feature-complete enough to be useful for some real 
programming. (Thanks also to the work of other people here who already 
started porting modules from Q to Pure.)

> I originally tried cracking open the source code
> to Maxima and then realized that was going to be more than just an
> hour of effort (partly because I don't have enough Lisp experience
> yet).

LOL. Yeah, CAS's are big monsters. :)

> 2. Term rewriting for doing AST manipulation (Q seemed a good match
> here).  Mostly, I was interested in taking an expression and
> normalizing it to a sum-of-products format.

There's a software named Stratego specifically designed for that purpose 
(http://www.program-transformation.org/Stratego/). It uses some kind of 
programmed rewriting systems which look like they are quite a bit more 
complicated to program than Pure/Q. Probably worth a look, though.

> 3. (maybe something else goes in the middle here?)

Something like... code generation? :)

> 4. Optimization to try to ensure that pipelines in a CPU are kept full
> or that processing latency is minimized (using Prolog, integer linear
> programming, ...)

For items 3 and 4, LLVM (which Pure uses as its backend) is definitely 
worth a look. It's a C++ framework, though.

It would be nice to have LLVM bindings for Pure. Then we could write 
compiler backends directly in Pure, which also provides an easy path to 
make Pure self-hosting at some point.

> I'm actually
> kinda confused about why people insist on using C to write compilers
> when there are such great higher level tools available?

C/C++ is what most programmers know, and has a huge amount of libraries 
available. Also, besides the usual problems to break away from the 
imperative mindset, languages like ML, Haskell and even Lisp are often 
perceived as requiring at lot of esoteric math/cs knowledge to be able 
to use them successfully. That's not completely undeserved. I think that 
there's a need for a functional language which is as easy to use as, 
say, Python. Obviously, Pure tries to fill that niche, but we're not 
quite there yet. ;-)

> The idea is that I can then layer term rewriters on top of this (this
> is how I discovered Q in the first place), and also be able to provide
> nearly seamless integration between Python and constrained
> optimization tools (like CVXOPT, GLPK, LP_SOLVE), and probably other
> tools too (like ODE solvers?).

There are plans to add interfaces to the GNU Scientific Library and some 
other solvers to Pure, so these kinds of applications will hopefully be 
well supported in the future.

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [pure-lang-users] Swapping Symbols and Integers

[David B. <dh...@gm...>]

On Sat, Aug 9, 2008 at 2:48 PM, Albert Graef <Dr....@t-...> wrote:
>> David Baird wrote:
>> 3. (maybe something else goes in the middle here?)
>
> Something like... code generation? :)

Doh!  I thought that was somewhere around step 5 :-P  I'll have to rethink this.

Thank you for all your generous feedback.

-David

Re: [pure-lang-users] Swapping Symbols and Integers

[Albert G. <Dr....@t-...>]

David Baird wrote:
>> Something like... code generation? :)
> 
> Doh!  I thought that was somewhere around step 5 :-P  I'll have to rethink this.

Well, there's a lot of stuff that can be done on the AST, but for things 
like peephole optimization, register allocation, constant folding, 
inlining of runtime routines, tail call elimination etc. you definitely 
need to consider the target code (which most often is an abstract 
assembler-like code which then gets translated to the real native code, 
at least nowadays).

In principle, you could also design your own AST representation of the 
target and apply your optimizations to that, but some kinds of 
optimizations are pretty hairy, so why reinvent the wheel when there's 
already something as comprehensive as LLVM out there?

> Thank you for all your generous feedback.

No sweat. :) It would be cool if you could try Pure and provide some 
feedback on how well it works for your purposes.

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag