progress in April

April has passed with steady progress.  Generally these last two
months have been very busy for me in other directions and my time has
been limited.  As is usual with these things, the work is more
substantial that was anticipated  at the outset.

In response to isolated queries, I don't release stuff before it is
finished.  Probably most people here would guess that!

However, despite commitments, we have a Prolog, an improved YACC and
all of of part I and nearly all of part
II of FPQi working.  Many of the code changes in Shen tended to ripple
through the source, requiring extensive editing. In particular the
accurate implementation of the Prolog cut was a definite challenge
within the current primitive instruction set and required a novel
method I call kill-and-restore.

There is still a mass of smaller detail to get right, some new
features and a fair bit of online documentation to write before my
major part is done.

Mark

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Re: progress in April

On Fri, Apr 30, 2010 at 10:44 PM, Mark Tarver <dr.mtarver@...> wrote:
> April has passed with steady progress.

exciting to hear, always looking forward to more qi/shen.

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Re: Progress to date

Re: Progress to date

FPQ Problem 2 performance issues

Why is Qi losing to Common Lisp in my nth_root solution?

So I did this as a SICP exercise (1.45) a while back:

(defun nth-root (n)
  (lambda (x)
    (fixed-point-of-transform (lambda (y)
                                (FORMAT T "~9$~%" y)
                                (/ x (expt y (1- n))))
                              (repeated #'average-damp (1+ (floor n
2)))
                              1.0)))

I took a lot of that and translated to Qi for this problem, but the
problem is the recursive iterations starts fast, but slow to a
screeching halt after roughly 7 recursive calls or so.  I tried
logging some of the function calls to help me find any bottlenecks of
which I was not aware to no avail.  (Some of the functions below look
gross because of this logging).  I'm a little lost as to how to
profile this as well.

The code in full:

(define half
  X -> (ASH X -1))

(define odd?
  X -> (= 1 (LOGAND 1 X)))

(define even?
  X -> (not (odd? X)))

(define pow
  0 _ -> 0
  _ 0 -> 1
  X P -> (pow (* X X) (half P)) where (even? P)
  X P -> (* X (pow X (- P 1))))

(define compose
  F G -> (/. x (F (G x))))

(define repeated
  Fn 1 -> Fn
  Fn N -> (compose Fn (repeated Fn (- N 1))))

(define average
  X Y -> (/ (+ X Y) 2))

(set *ad-calls* 0)
(define average-damp
  Fn -> (do (FORMAT T "ad: ~a~%" (INCF *ad-calls*))
            (/. x (average x (Fn x)))))

(set *ad-n-calls* 0)
(define average-damp-n
  N Fn -> (do (FORMAT T "adn: ~a~%" (INCF *ad-n-calls*))
              ((repeated average-damp N) Fn)))

(define abs
  X -> (- 0 X) where (< X 0)
  X -> X)

(define close-enough?
  A B Tolerance -> (< (abs (- A B)) Tolerance))

(define fixed-point
  Fn Guess Tolerance -> (fixed-point1 Fn Guess Tolerance (Fn Guess)))

(define fixed-point1
  Fn Guess Tolerance Next -> (fixed-point2 Fn Guess Tolerance Next 0))

(define fixed-point2
  Fn Guess Tolerance Next Count ->
  (do
   (FORMAT T "fp2: ~9$ ~d~%" Next Count)
   \ Added the (> Count 7) so I wouldn't get stuck w/ Qi burning up
the CPU for too long thinking too hard \
   (if (or (> Count 7) (close-enough? Guess Next Tolerance))
       Next
       (fixed-point2 Fn Next Tolerance (Fn Next) (INCF Count)))))

(define round-p
  X Places -> (let p (pow 10 Places)
                (/ (round (* X p)) p)))

(define nth_root
  N M P -> (round-p (fixed-point
                     (average-damp-n
                      (+ 1 (half M))
                      ((/. x (/. y
                                 (do (FORMAT T "/. y: ~a~%" (INCF x))
                                     (/ N (pow y (- M 1)))))) 0))
                     1
                     (/ 1 (pow 10 P)))
                     P))

(1 (nth_root 100 4 5)
adn: 1
ad: 1
ad: 2
ad: 3
/. y: 1
fp2: 13.375000000 0
/. y: 2
fp2: 11.708349000 1
/. y: 3
fp2: 10.252594000 2
/. y: 4
fp2: 8.982618000 3
/. y: 5
fp2: 7.877037500 4
/. y: 6
fp2: 6.917983000 5
/. y: 7
fp2: 6.090990000 6
/. y: 8
fp2: 5.384931600 7
/. y: 9
fp2: 4.791867000 8
/. y: 10
fp2: 4.306488000 9
430649/100000

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Re: FPQ Problem 2 performance issues

>  I'm a little lost as to how to
> profile this as well.

FPQi p 403

Mark

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe <at> googlegroups.com.
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Re: Progress to date

Re: FPQ Problem 2 performance issues

On May 4, 2:11 am, Mark Tarver <dr.mtar...@...> wrote:
> >  I'm a little lost as to how to
> > profile this as well.
>
> FPQi p 403
>
> Mark

Thanks Mark,

It looks like the arbitrary precision arithmetic is getting out of
control.  What's odd is I'm only average damping 3 times (in the case
of the 4th root === (1 + (floor(M  / 2))).  When I altered average-
damp to round its result each time it was called, everything worked
just dandy.  What's odd is this step wasn't required for my Common
Lisp solution running under SBCL, and I'm runnning Qi under SBCL.

This is where I ended up landing in my Qi code:

(define fixed-point
  Fn Guess Tolerance -> (fixed-point1 Fn Guess Tolerance (Fn Guess)))

(define fixed-point1
  Fn Guess Tolerance Next -> Next where (close-enough? Guess Next
Tolerance)
  Fn Guess Tolerance Next -> (fixed-point1 Fn Next Tolerance (Fn
Next)))

(define round-p
  X Places -> (let p (pow 10 Places)
                (/ (round (* X p)) p)))

(define nth_root
  N M P -> (round-p (fixed-point
                     (compose (/. x (round-p x P))
                              (average-damp-n
                               (+ 1 (half M))
                               (/. y (/ N (pow y (- M 1))))))
                     1
                     (/ 1 (pow 10 (+ 1 P))))
                    P))

-John Watson

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Staged Computation in Qi

I'm writing because I want to understand how expressive Qi is for
describing staged computations. For example, an elegant theoretical
system is described in the paper "An Idealized MetaML: Simpler and
More Expressive"  by Moggi, Taha, Benaissa, Sheard (see, for example,
section 3.2 which gives an interactive session). It provides operators
bracket, escape, and run which are formal analogues of back-quote,
comma, and eval in scheme along with others like box, unbox, compile,
etc....

Is Qi capable of expressing the same operational semantics? Is there a
more native Qi idiom for similar ideas?

References:
 "An Idealized MetaML: Simpler and More Expressive":
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.6938
 "Macros as Multistage Computations": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.7706

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.

Re: Staged Computation in Qi

I skimmed this paper rather quickly.  Hope this is of some use.
QUOTE
MetaML has three staging annotations: Brackets h i, Escape ~ and Run
run . An expression hei defers the computation of e; ....and run e
evaluates e to obtain a deferred expression, and
then evaluates it.
UNQUOTE
p 2.

This, or something like it, is already in Qi II

http://www.lambdassociates.org/Book/page153.htm

As regards eval, eval is in Qi, but has no type theory for it.

http://www.lambdassociates.org/Book/page131.htm

However it is possible to program Qi to typecheck eval.
eg.

Qi II 2008, Copyright (C) 2001-2008 Mark Tarver
www.lambdassociates.org
version 1.05

(0-) (tc +)
true

(1+)
(datatype metaQi

F : (A --> B);
X : A;
__________________
(eval [F X]) : B;)
metaQi : symbol

(2+) (eval [sqrt 6])
2.4494898 : number

That is a demo, you do need more sequent rules to capture the type
theory of eval.  But you see the idea.

In general Qi has implicitly 'meta' built in to it by dint of its
programmability.

Mark

On 6 May, 20:27, Marc Coram <marc.co...@...> wrote:
> I'm writing because I want to understand how expressive Qi is for
> describing staged computations. For example, an elegant theoretical
> system is described in the paper "An Idealized MetaML: Simpler and
> More Expressive"  by Moggi, Taha, Benaissa, Sheard (see, for example,
> section 3.2 which gives an interactive session). It provides operators
> bracket, escape, and run which are formal analogues of back-quote,
> comma, and eval in scheme along with others like box, unbox, compile,
> etc....
>
> Is Qi capable of expressing the same operational semantics? Is there a
> more native Qi idiom for similar ideas?
>
> References:
>  "An Idealized MetaML: Simpler and More Expressive":http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.6938
>  "Macros as Multistage Computations":http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.7706
>
> --
> You received this message because you are subscribed to the Google Groups "Qilang" group.
> To post to this group, send email to qilang@...
> To unsubscribe from this group, send email to qilang+unsubscribe <at> googlegroups.com.
> For more options, visit this group athttp://groups.google.com/group/qilang?hl=en.

--

-- 
You received this message because you are subscribed to the Google Groups "Qilang" group.
To post to this group, send email to qilang@...
To unsubscribe from this group, send email to qilang+unsubscribe <at> googlegroups.com.
For more options, visit this group at http://groups.google.com/group/qilang?hl=en.