On 10 Jul, 15:26, Mark Tarver <··········@ukonline.co.uk> wrote:
> On 10 Jul, 15:20, Mark Tarver <··········@ukonline.co.uk> wrote:
>
>
>
>
>
> > On 10 Jul, 13:15, Dan Bensen <··········@cyberspace.net> wrote:
>
> > > Mark Tarver wrote:
> > > > The Solutions
> > > > **************************************
> > > > Language: Lisp
> > > > Author: Andre Thieme
> > > > Author: Nathan Froyd
> > > > Author: Pascal Constanza
>
> > > I submitted another solution last week:http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/e6...
>
> > > (defmacro defop (func op ident zero-case)
> > > (let ((e1 (gensym "E1"))
> > > (e2 (gensym "E2")))
> > > `(defun ,func (,e1 ,e2)
> > > ,(delete :no-case
> > > `(case ,e1
> > > ,zero-case
> > > (,ident ,e2)
> > > (t ,(delete :no-case
> > > `(case ,e2
> > > ,zero-case
> > > (,ident ,e1)
> > > (t (if (atom ,e2) (list ,e1 ,op ,e2)
> > > (case (cadr ,e2)
> > > (,op (,func (,func ,e1 (car ,e2)) (caddr ,e2)))
> > > (t (list ,e1 ,op ,e2)))))))))))))
>
> > > (defop expr+ '+ 0 :no-case)
> > > (defop expr* '* 1 ( 0 0 ))
>
> > > (defun simplify (expr)
> > > (if (atom expr)
> > > expr
> > > (let ((e1 (simplify (car expr)))
> > > (e2 (simplify (caddr expr))))
> > > (case (cadr expr)
> > > ('+ (expr+ e1 e2))
> > > ('* (expr* e1 e2))))))
>
> > > --
> > > Danwww.prairienet.org/~dsb/
>
> > Equal with Pascal I should say
>
> > Revised Results are
>
> > SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
> > |
> > -------------------------------------------------
> > |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> > *******************************************************************
> > time 0.9s 0.625s 0.49s 1.59s 0.09s 0.93s ?
>
> > Mark
> > loc 15 15 42 23 27 26 15- Hide quoted text -
>
> > - Show quoted text -
>
> Sorry Dan,
>
> I missed the decimal place - its 0.093 not 0.93s. Of course.
>
> Comes from not getting enough sleep!
>
> Mark
>
> SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
> |
> -------------------------------------------------
> |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> *******************************************************************
> time 0.9s 0.625s 0.49s 1.59s 0.09s 0.093s ?
> loc 15 15 42 23 27 26 15- Hide quoted text -
>
> - Show quoted text -
Actually - a faster version in Qi of equal length to the original is
(define simplify
[Op A B] -> (s Op (simplify A) (simplify B))
A -> A)
(define s
+ M N -> (+ M N) where (and (number? M) (number? N))
+ 0 F -> F
+ F 0 -> F
+ A [+ B C] -> [+ [+ A B] C]
* M N -> (* M N) where (and (number? M) (number? N))
* 0 F -> 0
* F 0 -> 0
* F 1 -> F
* 1 F -> F
* A [* B C] -> [* [* A B] C]
Op A B -> [Op A B])
we then get
SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
|
-------------------------------------------------
|Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
*******************************************************************
time 0.56s 0.38s 0.49s 1.59s 0.09s 0.093s ?
loc 15 15 42 23 27 26 15
From: Marcus Breiing
Subject: Re: Jon Harrop rewrite benchmark; Qi, Lisp and OCaml
Date:
Message-ID: <f70pgh$jpp$1@chessie.cirr.com>
Mark Tarver <··········@ukonline.co.uk> writes:
>
> SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
> |
> -------------------------------------------------
> |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> *******************************************************************
> time 0.9s 0.625s 0.49s 1.59s 0.09s 0.093s ?
> loc 15 15 42 23 27 26 15
I tried to reproduce your (non-Qi) results, but got some significant
differences. I think your timings for "Pascal" and "Dan" may be off by
large factors due to wrong inputs.
"Pascal" doesn't take a prefix-sexp expression, but one made up of
structs. A correct invocation for the challenge problem should look
like this.
(simplify-pascal
(make-mul :x 'x
:y (make-add :x (make-add :x (make-mul :x 12 :y 0)
:y (make-add :x 23 :y 8))
:y 'y)))
"Dan" takes infix-sexp input, and should be invoked like this:
(simplify-dan '(x * (((12 * 0) + (23 + 8)) + y)))
BTW, "Dan" returns (X * ((23 + 8) + Y)), seemingly missing out on a
simplification.
With these inputs, on a slightly slower machine and using CMU 19c, I
get:
Nathan 0.96
Andre 1.25
Pascal 3.41
Dan 1.19
I don't have Qi installed. My own (unpublished) pattern matcher gives
results virtually indistinguishable from "Nathan". It was explicitly
written to avoid redundant tests, which probably explains the
similarity. It looks like this:
(defun simplify (exp)
(labels ((s+ (x y)
(mcase (values x y)
((values (the number _) (the number _)) (+ x y))
((values 0 _) y)
((values _ 0) x)
((values _ `(+ ,a ,b)) (s+ (s+ x a) b))
((values _ _) `(+ ,x ,y))))
(s* (x y)
(mcase (values x y)
((values (the number _) (the number _)) (* x y))
((values 0 _) 0)
((values _ 0) 0)
((values 1 _) y)
((values _ 1) x)
((values _ `(* ,a ,b)) (s* (s* x a) b))
((values _ _) `(* ,x ,y)))))
(mcase exp
(`(+ ,x ,y) (s+ (simplify x) (simplify y)))
(`(* ,x ,y) (s* (simplify x) (simplify y)))
(_ exp))))
--
Marcus Breiing
(Cologne, Germany)
On 10 Jul, 21:16, Marcus Breiing <······@2007w27.mail.breiing.com>
wrote:
> Mark Tarver <··········@ukonline.co.uk> writes:
>
> > SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
> > |
> > -------------------------------------------------
> > |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> > *******************************************************************
> > time 0.9s 0.625s 0.49s 1.59s 0.09s 0.093s ?
> > loc 15 15 42 23 27 26 15
>
> I tried to reproduce your (non-Qi) results, but got some significant
> differences. I think your timings for "Pascal" and "Dan" may be off by
> large factors due to wrong inputs.
>
> "Pascal" doesn't take a prefix-sexp expression, but one made up of
> structs. A correct invocation for the challenge problem should look
> like this.
>
> (simplify-pascal
> (make-mul :x 'x
> :y (make-add :x (make-add :x (make-mul :x 12 :y 0)
> :y (make-add :x 23 :y 8))
> :y 'y)))
>
> "Dan" takes infix-sexp input, and should be invoked like this:
>
> (simplify-dan '(x * (((12 * 0) + (23 + 8)) + y)))
>
> BTW, "Dan" returns (X * ((23 + 8) + Y)), seemingly missing out on a
> simplification.
>
> With these inputs, on a slightly slower machine and using CMU 19c, I
> get:
>
> Nathan 0.96
> Andre 1.25
> Pascal 3.41
> Dan 1.19
>
> I don't have Qi installed. My own (unpublished) pattern matcher gives
> results virtually indistinguishable from "Nathan". It was explicitly
> written to avoid redundant tests, which probably explains the
> similarity. It looks like this:
>
> (defun simplify (exp)
> (labels ((s+ (x y)
> (mcase (values x y)
> ((values (the number _) (the number _)) (+ x y))
> ((values 0 _) y)
> ((values _ 0) x)
> ((values _ `(+ ,a ,b)) (s+ (s+ x a) b))
> ((values _ _) `(+ ,x ,y))))
> (s* (x y)
> (mcase (values x y)
> ((values (the number _) (the number _)) (* x y))
> ((values 0 _) 0)
> ((values _ 0) 0)
> ((values 1 _) y)
> ((values _ 1) x)
> ((values _ `(* ,a ,b)) (s* (s* x a) b))
> ((values _ _) `(* ,x ,y)))))
> (mcase exp
> (`(+ ,x ,y) (s+ (simplify x) (simplify y)))
> (`(* ,x ,y) (s* (simplify x) (simplify y)))
> (_ exp))))
>
> --
> Marcus Breiing
> (Cologne, Germany)
Yes, you're right! I pasted the same test into his file that
I had used on Nathan and Andre. Thanks for that, Marcus.
Dan is adhering to the terms of the original spec in using infix.
I'll ask him to fix his bug if he would so I can get a fair timing.
Ok, see if we can get this right.
I've run this again using the proper inputs; on my machine we get.
SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
|
-------------------------------------------------
|Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
*******************************************************************
time 0.56s 0.38s 0.49s 1.59s 0.95s 0.47s ?
loc 15 15 42 23 27 26 15
Hum - the unreleased Turbo-E is top* ;) Well its not a fix - honest!
Mark
* Its top until perhaps O'Caml does its stuff.
Mark Tarver <··········@ukonline.co.uk> writes:
> |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> *******************************************************************
> time 0.56s 0.38s 0.49s 1.59s 0.95s 0.53s ?
> loc 15 15 42 23 27 26 15
>
> One camel to go.
Can someone code a GHC version?
From: Ben Bacarisse
Subject: Re: Jon Harrop rewrite benchmark; Qi, Lisp and OCaml
Date:
Message-ID: <877ip4vy8b.fsf@bsb.me.uk>
Paul Rubin <·············@NOSPAM.invalid> writes:
> Mark Tarver <··········@ukonline.co.uk> writes:
>> |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
>> *******************************************************************
>> time 0.56s 0.38s 0.49s 1.59s 0.95s 0.53s ?
>> loc 15 15 42 23 27 26 15
>>
>> One camel to go.
>
> Can someone code a GHC version?
Too late? BTW I am a Haskell novice, so the implementation is basic.
I can't compile any of the other versions so I can only report that is
takes about 0.40s on my laptop (Intel(R) Pentium(R) M processor
2.00GHz, GHC 6.6).
{- CODE START -}
data Expression
= I Integer
| S String
| Add Expression Expression
| Mul Expression Expression
deriving Show
simplify :: Expression -> Expression
simplify e =
case e of
(Add a b) -> simp (Add (simplify a) (simplify b))
(Mul a b) -> simp (Mul (simplify a) (simplify b))
e -> e
where
simp :: Expression -> Expression
simp (Add (I x) (I y)) = I (x + y)
simp (Add (I 0) e) = e
simp (Add e (I 0)) = e
simp (Mul (I x) (I y)) = I (x * y)
simp (Mul (I 0) _) = I 0
simp (Mul _ (I 0)) = I 0
simp (Mul (I 1) e) = e
simp (Mul e (I 1)) = e
simp (Mul a (Mul b c)) = (Mul (Mul a b) c)
simp (Add a (Add b c)) = (Add (Add a b) c)
simp e = e
-- [* x [+ [+ [* 12 0] [+ 23 8]] y]].
test = (Mul (S "x") (Add (Add (Mul (I 12) (I 0)) (Add (I 23) (I 8))) (S "y")))
main :: IO ()
main = putStrLn $ show $ last $ map simplify (replicate (10^7) test)
{- CODE END -}
Obviously, a compiler could optimise that repetition away, but GHC
leaves it (at least the execution time scales with the number in the
replicate call!).
--
Ben.
Does Qi stick in declarations similar to the embedded declarations in
the lisp examples for the underlying lisp compiler? I dunno
if it has much effect on this particular code, but that "(declare
(optimise (speed 3)))" can make a difference in some lisps for some
applications.
On 11 Jul, 01:13, David Golden <············@oceanfree.net> wrote:
> Does Qi stick in declarations similar to the embedded declarations in
> the lisp examples for the underlying lisp compiler? I dunno
> if it has much effect on this particular code, but that "(declare
> (optimise (speed 3)))" can make a difference in some lisps for some
> applications.
Qi does put in type declarations based on its type inferencing. You
can associate a Qi type with a Lisp type too. But here there's not
much of that going on - the type checker is off.
All the code being run save Dan's had (optimize (speed 3)) in it.
Qi runs under this default setting. But now you mentioned it I put
this into Dan's code and ran it again. It made no discernable
difference.
Mark
Mark Tarver wrote:
> All the code being run save Dan's had (optimize (speed 3)) in it.
> Qi runs under this default setting. But now you mentioned it I put
> this into Dan's code and ran it again. It made no discernable
> difference.
You mean you added it to simplify? I put it into the last version of
apply? (? = +|*). Maybe try taking it out of the definition in defop.
That's what does most of the work.
--
Dan
www.prairienet.org/~dsb/
Mark Tarver wrote:
>
> Qi does put in type declarations based on its type inferencing. You
> can associate a Qi type with a Lisp type too. But here there's not
> much of that going on - the type checker is off.
>
And do you get faster results with the type checker on?
(given that SBCL may need some declarations for its own
checking and inferencing).
On 11 Jul, 13:11, David Golden <············@oceanfree.net> wrote:
> Mark Tarver wrote:
>
> > Qi does put in type declarations based on its type inferencing. You
> > can associate a Qi type with a Lisp type too. But here there's not
> > much of that going on - the type checker is off.
>
> And do you get faster results with the type checker on?
> (given that SBCL may need some declarations for its own
> checking and inferencing).
Probably not; there's not much to optimise type theory wise in this
program.
Mark
From: Dimiter "malkia" Stanev
Subject: Re: Jon Harrop rewrite benchmark; Qi, Lisp and OCaml
Date:
Message-ID: <46969AA7.8080504@mac.com>
Under lispworks, I found out that (optimize (speed 3)) is not enough,
I'm using (optimize (speed 3) (safety 0) (debug 0) (space 0)
(compilation-speed 0)). Off course all this could be declaim'd
and in case of fixnums only arithmetic, I'm also doing this:
(optimize #+lispworks (fixnum-safety 0))
if it's float point only:
(optimize #+lispworks (float 0))
Probably the other implementations would have similiar options.
I've found that having (debug) set to anything above 0, would create
additional code (disassemblin'g it).
Then again, I needed that just for some really tight decompression code,
just to get feel of lispworks optimizer. It's not the smartest compiler,
but still gives good results.
Mark Tarver wrote:
> On 11 Jul, 01:13, David Golden <············@oceanfree.net> wrote:
>> Does Qi stick in declarations similar to the embedded declarations in
>> the lisp examples for the underlying lisp compiler? I dunno
>> if it has much effect on this particular code, but that "(declare
>> (optimise (speed 3)))" can make a difference in some lisps for some
>> applications.
>
> Qi does put in type declarations based on its type inferencing. You
> can associate a Qi type with a Lisp type too. But here there's not
> much of that going on - the type checker is off.
>
> All the code being run save Dan's had (optimize (speed 3)) in it.
> Qi runs under this default setting. But now you mentioned it I put
> this into Dan's code and ran it again. It made no discernable
> difference.
>
> Mark
>
On 10 Jul, 21:16, Marcus Breiing <······@2007w27.mail.breiing.com>
wrote:
> Mark Tarver <··········@ukonline.co.uk> writes:
>
> > SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
> > |
> > -------------------------------------------------
> > |Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
> > *******************************************************************
> > time 0.9s 0.625s 0.49s 1.59s 0.09s 0.093s ?
> > loc 15 15 42 23 27 26 15
>
> I tried to reproduce your (non-Qi) results, but got some significant
> differences. I think your timings for "Pascal" and "Dan" may be off by
> large factors due to wrong inputs.
>
> "Pascal" doesn't take a prefix-sexp expression, but one made up of
> structs. A correct invocation for the challenge problem should look
> like this.
>
> (simplify-pascal
> (make-mul :x 'x
> :y (make-add :x (make-add :x (make-mul :x 12 :y 0)
> :y (make-add :x 23 :y 8))
> :y 'y)))
>
> "Dan" takes infix-sexp input, and should be invoked like this:
>
> (simplify-dan '(x * (((12 * 0) + (23 + 8)) + y)))
>
> BTW, "Dan" returns (X * ((23 + 8) + Y)), seemingly missing out on a
> simplification.
>
> With these inputs, on a slightly slower machine and using CMU 19c, I
> get:
>
> Nathan 0.96
> Andre 1.25
> Pascal 3.41
> Dan 1.19
>
> I don't have Qi installed. My own (unpublished) pattern matcher gives
> results virtually indistinguishable from "Nathan". It was explicitly
> written to avoid redundant tests, which probably explains the
> similarity. It looks like this:
>
> (defun simplify (exp)
> (labels ((s+ (x y)
> (mcase (values x y)
> ((values (the number _) (the number _)) (+ x y))
> ((values 0 _) y)
> ((values _ 0) x)
> ((values _ `(+ ,a ,b)) (s+ (s+ x a) b))
> ((values _ _) `(+ ,x ,y))))
> (s* (x y)
> (mcase (values x y)
> ((values (the number _) (the number _)) (* x y))
> ((values 0 _) 0)
> ((values _ 0) 0)
> ((values 1 _) y)
> ((values _ 1) x)
> ((values _ `(* ,a ,b)) (s* (s* x a) b))
> ((values _ _) `(* ,x ,y)))))
> (mcase exp
> (`(+ ,x ,y) (s+ (simplify x) (simplify y)))
> (`(* ,x ,y) (s* (simplify x) (simplify y)))
> (_ exp))))
>
> --
> Marcus Breiing
> (Cologne, Germany)
Yes, you're right! I pasted the same test into his file that
I had used on Nathan and Andre. Thanks for that, Marcus.
Dan is adhering to the terms of the original spec in using infix.
I'll ask him to fix his bug if he would so I can get a fair timing.
Ok, see if we can get this right.
I've run this again using the proper inputs; on my machine we get.
SBCL 1.0 Windows, 2.6GHz, 500Mb RAM
|
-------------------------------------------------
|Qi 8.0 Qi Turbo-E Nathan Andre Pascal Dan | Jon
*******************************************************************
time 0.56s 0.38s 0.49s 1.59s 0.95s 0.47s ?
loc 15 15 42 23 27 26 15
Hum - the unreleased Turbo-E is top* ;) Well its not a fix - honest!
Mark
* Its top until perhaps O'Caml does its stuff.
From: Marcus Breiing
Subject: Re: Jon Harrop rewrite benchmark; Qi, Lisp and OCaml
Date:
Message-ID: <f70q7f$jpp$2@chessie.cirr.com>
Marcus Breiing <······@2007w27.mail.breiing.com> writes:
>
> Nathan 0.96
> Andre 1.25
> Pascal 3.41
> Dan 1.19
Above runs have "Pascal" at a disadvantage by creating its input on
each invocation, whereas the others are fed (read-time) constants.
Correcting that, I get
Nathan 0.96
Andre 1.25
Pascal 2.05
Dan 1.19
--
Marcus Breiing
(Cologne, Germany)
Mark Tarver <··········@ukonline.co.uk> writes:
> This test was conducted to determine the relative efficiency of hand-
> coded Lisp, OCaml, Qi 8.0 and Qi Turbo-E using the benchmark challenge
> provided by Jon Harrop.
> The problem is to simplify symbolic expressions by applying the
> following rewrite rules from the leaves up:
> 1*f -> f
> f*1 -> f
> The Solutions
> --------------------
>
> Language: Qi
> Author: Mark Tarver
> Length: 13 lines
>
> (define simplify
> [Op A B] -> (s [Op (simplify A) (simplify B)])
> A -> A)
>
> (define s
> [+ M N] -> (+ M N) where (and (number? M) (number? N))
> [+ 0 F] -> F
> [+ F 0] -> F
> [+ A [+ B C]] -> [+ [+ A B] C]
> [* M N] -> (* M N) where (and (number? M) (number? N))
> [* 0 F] -> 0
> [* F 0] -> 0
> [* A [* B C]] -> [[A * B] * C]
> A -> A)
>
I think you are missing
[* 1 F] -> F
and its commutative friend.
I doubt it will change the timings, but I know you will want
the code to be correct.
Alan Crowe
Edinburgh
Scotland
On 10 Jul, 12:58, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> Mark Tarver <··········@ukonline.co.uk> writes:
> > This test was conducted to determine the relative efficiency of hand-
> > coded Lisp, OCaml, Qi 8.0 and Qi Turbo-E using the benchmark challenge
> > provided by Jon Harrop.
> > The problem is to simplify symbolic expressions by applying the
> > following rewrite rules from the leaves up:
> > 1*f -> f
> > f*1 -> f
> > The Solutions
> > --------------------
>
> > Language: Qi
> > Author: Mark Tarver
> > Length: 13 lines
>
> > (define simplify
> > [Op A B] -> (s [Op (simplify A) (simplify B)])
> > A -> A)
>
> > (define s
> > [+ M N] -> (+ M N) where (and (number? M) (number? N))
> > [+ 0 F] -> F
> > [+ F 0] -> F
> > [+ A [+ B C]] -> [+ [+ A B] C]
> > [* M N] -> (* M N) where (and (number? M) (number? N))
> > [* 0 F] -> 0
> > [* F 0] -> 0
> > [* A [* B C]] -> [[A * B] * C]
> > A -> A)
>
> I think you are missing
>
> [* 1 F] -> F
>
> and its commutative friend.
>
> I doubt it will change the timings, but I know you will want
> the code to be correct.
>
> Alan Crowe
> Edinburgh
> Scotland- Hide quoted text -
>
> - Show quoted text -
Yes indeed. I missed those cases. In which case the code is
(define simplify
[Op A B] -> (s [Op (simplify A) (simplify B)])
A -> A)
(define s
[+ M N] -> (+ M N) where (and (number? M) (number? N))
[+ 0 F] -> F
[+ F 0] -> F
[+ A [+ B C]] -> [+ [+ A B] C]
[* M N] -> (* M N) where (and (number? M) (number? N))
[* 0 F] -> 0
[* F 0] -> 0
[* F 1] -> F
[* 1 F] -> F
[* A [* B C]] -> [* [* A B] C]
A -> A)
On 3 runs we get
(1-) (tt 1000000)
Evaluation took:
0.656 seconds of real time
0.59375 seconds of user run time
0.0625 seconds of system run time
[Run times include 0.047 seconds GC run time.]
0 calls to %EVAL
0 page faults and
119,997,552 bytes consed.
0
(2-) !!
1. (tt 1000000)
Evaluation took:
0.594 seconds of real time
0.59375 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
119,993,336 bytes consed.
0
(3-) !!
2. (tt 1000000)
Evaluation took:
0.609 seconds of real time
0.609375 seconds of user run time
0.0 seconds of system run time
[Run times include 0.031 seconds GC run time.]
0 calls to %EVAL
0 page faults and
120,001,224 bytes consed.
0
As you say, very little difference.
Mark
On 2007-07-11, ctnd <·········@googlemail.com> wrote:
> On Jul 10, 11:06 am, Mark Tarver <··········@ukonline.co.uk> wrote:
[ 304 lines snipped ]
>
> Lisp is a language separate from its _implementations_... what?
Why must you quote 304 lines to ask a one-line question?
* Larry Clapp <····················@theclapp.ddts.net> :
| On 2007-07-11, ctnd <·········@googlemail.com> wrote:
|> On Jul 10, 11:06 am, Mark Tarver <··········@ukonline.co.uk> wrote:
| [ 304 lines snipped ]
|>
|> Lisp is a language separate from its _implementations_... what?
|
| Why must you quote 304 lines to ask a one-line question?
Because he's using google groups and they design the UI to encourage him
to do that.
--
Madhu
*murmur investments in bandwidth industry* *lost time scrolling*