[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: How to switch to regular Scheme

On 1/24/06, Amandeep Singh <varoadster@xxxxxxxxx> wrote:
Thanks for the great explanation. I really appreciate the way you explained all the steps thoroughly.

But for the procedure, I meant to keep it as an iterative function for the hanoi solution. I already know how to do the recursive one but I was searching for the way to do it iteratively. With the help of SRFI, I think I was able to do it iteratively but I'm not sure how to translate it to the regular scheme code without it being recursive.

Thanks once again

On 1/24/06, Sebastian Egner < sebastian.egner@xxxxxxxxxxx> wrote:

> I realized i made this unclear. I'm trying to translate this
> procedure into the plain Scheme code. In other words, I'm trying to
> make it work in Scheme as if SRFI never existed.

Right. In plain Scheme you would write recursive procedures,
i.e. procedures that call themselves (directly in this case)
in order to reduce the problem to a smaller problem of the
same kind. Two-power could look like this:

(define (two-power n)
  (if (even? n)
      (+ 1 (two-power (quotient n 2)))

A potentially substantial improvement with recursive
procedures in Scheme is to reformulate them into 'tail
recursive form,' meaning the last thing in (a branch of)
a procedure is the recursive call. In Scheme this is
often done by 'named LET' (look into the R5RS standard):

(define (two-power n)
  (let loop ((n n) (k 0))
    (if (even? n)
        (loop (quotient n 2) (+ k 1))

As you can see, the recursive call to the procedure LOOP
is the last thing happening. This way the computer does
not have to keep track of all the not-yet-finished calls
and can already reuse the resources (in this example it
doesn't matter a bit, but in larger programs it does).

For the other procedure you could use the 'DO' construct
(look it up in the Scheme R5RS standard):

(define (hanoi m)
  (do ((n (- (expt 2 m) 1) (- n 1))
       (h '() (cons (+ (two-power-2 n) 1) h)))
    ((zero? n) h)))

Note that the loop counts n *down* because the list is
best constructed from back to front.

The reason you have problems defining MAX-EC etc. as
procedures is that this is impossible. MAX-EC etc.
shuffle around expressions before they are evaluated,
and in Scheme it is defined that arguments of a procedure
are evaluated before the procedure is applied. For this
reason, MAX-EC etc. are implemented as 'macros.' This
is an advanced feature of Scheme.

If you are brave-hearted, you can switch PLT to show
the actual expansion of you program with macros: Use
Language > Choose Language > PLT > Expander, and Run
your program. But keep in mind that this shows part
of the inner workings of PLT, which is a powerful
machine and can be complicated.


> On 1/23/06, Amandeep Singh <varoadster@xxxxxxxxx> wrote:
> I want the plain Scheme code without using max-ec, and list-ec. I
> tried to define list-ec and max-ec as assisting procedures but it
> was hard for me to figure out.
> I want a simple way to translate this into the plain Scheme code
> without using any of the SRFI syntax (eg: max-ec, list-ec, i)
> Thank you.


> On 1/23/06, Sebastian Egner < sebastian.egner@xxxxxxxxxxx> wrote:
> > I have this code:
> >
> > (require (lib "42.ss" "srfi"))
> >
> > (define (two-power n)
> >    (max-ec (:while (: i n)
> >                    (zero? (remainder n (expt 2 i))))
> >            i))
> >
> > (define (hanoi m)
> >    (list-ec (: n 1 (expt 2 m))
> >             (+ (two-power n) 1)))
> >
> > [...]
> > if anyone can rewrite this procedure without the SRFI syntax, it
> > will be very helpful. I want to see how it would look without the
> > simple one line but instead seeing the entire procedure instead of
> > just max-ec and list-ec.
> Do you want to know the plain Scheme code into which you program
> is being translated by SRFI-42, or do you want to know how one
> would program these procedures in Scheme without SRFI-42?
> Sebastian.