How to cast an imperative loop into a readable recursive function ?

How to cast an imperative loop into a readable recursive function ?

[Katalin Sinkov]

Background :
This is strictly a style question about a solved problem. I wrote
pseudocode in {} and converted to () and it worked. The line count of
both pseudocodes was similar. regexp part was the one left as
pseudocode in both. casting was also needed of string-to-integer.

How to cast an imperative loop into a readable recursive function ?

What questions to ask to guide thinking to it ?



Here is the concrete problem.

which is to find the nth character T_n in a string with erratic index
reset and length of substring given. ie

The string is preceeded by a value of start index s and length l

(s=4,l=16)ab5csoikowlfg02c(s=39,l=23)rli3ubxvadf36ut8uguhijh(...)...###

There can be gaps and the value of n is reset and usually greater but
no need to make the assumption and the first one with the desired
index is acceptable.

### denotes the end of the sequence.

It is not guaranteed so a (message) should be echoed in the situation
of error.



I have written this as a loop and an (if test then else) inside it.
Readablility is acceptable, however, I look for a lispy recursive
style.



(let ((char_skips (- n  s) ))
  (while (not (= char_skips 0))
    (progn
      (if (<= char_skips (+ l -1) )
	  (progn
	    (forward-char char_skips)
	    (setq char_skips 0))
	(progn
	  (forward-char l)

	  (forward-search-regexp "(s=###l=###)" nil nil nil) ; put in an if
and else block to test if FAIL
	  (setq s (match-string 0))
	  (setq l (match-string 0))

	  (setq char_skips (- n s) )
	  )
	)
      )
    )
  )

Re: How to cast an imperative loop into a readable recursive function ?

[Paul Rubin]

Katalin Sinkov <lispstylist@gmail.com> writes:
> How to cast an imperative loop into a readable recursive function ?
> What questions to ask to guide thinking to it ?

The functional-programming answer is that you rarely need explicit
recursion.  You can instead usually use higher-order functions like map
and reduce, that are defined in terms of recursion.

Maybe you want to read SICP, if you haven't done so already?

> Here is the concrete problem.
> which is to find the nth character T_n in a string with erratic index
> reset and length of substring given. ie

I'm sorry, I couldn't understand the problem description.

Re: How to cast an imperative loop into a readable recursive function ?

[RG]

In article 
<ffc3587e-3cb3-41f6-9b2f-80a22d5095d1@e20g2000vbn.googlegroups.com>,
 Katalin Sinkov <lispstylist@gmail.com> wrote:

> How to cast an imperative loop into a readable recursive function ?

What is a readable function?

Ignoring that part, you can always rewrite something like:

(while condition ...)

as

(iterate loop ()
  (when condition ... (loop)))

where iterate is defined as:

(defmacro iterate (name args &rest body)
  `(labels ((,name ,(mapcar 'first args) ,@body))
     (,name ,@(mapcar 'second args))))

Is that what you meant?

rg

Re: How to cast an imperative loop into a readable recursive function ?

[Katalin Sinkov]

On Dec 2, 6:48 pm, RG <rNOSPA...@flownet.com> wrote:
> In article
> <ffc3587e-3cb3-41f6-9b2f-80a22d509...@e20g2000vbn.googlegroups.com>,
>  Katalin Sinkov <lispstyl...@gmail.com> wrote:
>
> > How to cast an imperative loop into a readable recursive function ?
>
> What is a readable function?

for a beginner like me, i was able to read those in McCarthy's paper,
beautifully written recursive functions.

> Ignoring that part, you can always rewrite something like:
>
> (while condition ...)
>
> as
>
> (iterate loop ()
>   (when condition ... (loop)))
>
> where iterate is defined as:
>
> (defmacro iterate (name args &rest body)
>   `(labels ((,name ,(mapcar 'first args) ,@body))
>      (,name ,@(mapcar 'second args))))
>
> Is that what you meant?
>

I am sorry that this is not what I have in mind.

I am thinking of how McCarthy wrote all those difficult concepts
nicely as recursive functions. He dissected a problem ingeniously to
not have to iterate.

In my case, I have a pattern that is often interrupted by a reset of
the index.

It is trivial to go to nth character in a string because the indices
are contiguous.

However, in this case, the indices are often reset, but mercifully,
although not necessary, the length of the contiguous index sequence is
also given so we dont have to look for beginning paren at every step.

Take a look at my lisp code. it can be modified simply to run it and
it runs in an emacs "ide".

Re: How to cast an imperative loop into a readable recursive function ?

[Katalin Sinkov]

On Dec 2, 7:18 pm, Paul Rubin <no.em...@nospam.invalid> wrote:
> Katalin Sinkov <lispstyl...@gmail.com> writes:
> > I am thinking of how McCarthy wrote all those difficult concepts
> > nicely as recursive functions. He dissected a problem ingeniously to
> > not have to iterate.
>
> If you like mathematical treatments, you might look for some of Richard
> Bird's papers on program refinement.

math would be an overkill and not needed. its issue of programming
style.

Re: How to cast an imperative loop into a readable recursive function ?

[Paul Rubin]

Katalin Sinkov <lispstylist@gmail.com> writes:
> what I forgot to mention was that it should be possible to view the
> subseries problem in a way that I dont have to go thru a loop but use
> recursive definitions.

The problem is still very confusing, but it sounds to me like maybe
you want something like (untested):

   (defun foo (n str)
      (let ((s ...) (l ...) (p ...)
           ;; after reading the (s=2 l=4) prefix above,
           ;; p points past the end of it
           (if (< n l) 
              (aref str (+ p n))
             (foo (- n l) (substring str (+ p l)))))))

Re: How to cast an imperative loop into a readable recursive function ?

[Paul Rubin]

Katalin Sinkov <lispstylist@gmail.com> writes:
>>       (let ((s ...) (l ...) (p ...)
>>                   ;;; s=start l=length  p=??????

I don't mean p is actually a pointer, I just mean p is the offset after
your (l=2 s=3) stuff that you matched with a regexp in your original
example.

> At some stage there will confusion and readability issue.
> What strategies are there to grapple with this issue ?

Why don't you read some of the Emacs library code?  That is basically
how I learned Lisp.  Or, CL has a real package system so you can do more
serious encapsulation.  So you could read a CL book and apply the
techniques to Emacs Lisp as best you can.

Re: How to cast an imperative loop into a readable recursive function ?

[Katalin Sinkov]

On Dec 2, 9:35 pm, "Pascal J. Bourguignon" <p...@informatimago.com>
wrote:
> Katalin Sinkov <lispstyl...@gmail.com> writes:
> > Take a look at my lisp code. it can be modified simply to run it and
> > it runs in an emacs "ide".
>
> No it does not.  
>
> First, it's lacking a parenthesis.
>
> You should get paredit.el, and activate the paredit-mode to edit lisp
> sources.  See how lisp code is indented, and let emacs and paredit
> indent it for you, and place the parentheses for you.  This will produce
> lisp code that is more readable, and you will be able to copy-and-paste
> sexps "structurally", with much less risk of losing parentheses.
>
> Then, if we add the obvious missing parenthesis, and try to evaluate
> your code:
>
>     (let ((char_skips (- n  s) ))
>       (while (not (= char_skips 0))
>         (progn
>           (if (<= char_skips (+ l -1) )
>               (progn
>                 (forward-char char_skips)
>                 (setq char_skips 0))
>               (progn
>                 (forward-char l)
>
>                 (forward-search-regexp "(s=###l=###)" nil nil nil) ; put in an if
>                 ;; and else block to test if FAIL
>                 (setq s (match-string 0))
>                 (setq l (match-string 0))
>
>                 (setq char_skips (- n s) ))))))
>
> we get the following error:
>
>     Debugger entered--Lisp error: (void-variable n)
>       (- n s)
>       (let ((char_skips ...)) (while (not ...) (progn ...)))
>       eval((let ((char_skips ...)) (while (not ...) (progn ...))))
>       eval-last-sexp-1(nil)
>       eval-last-sexp(nil)
>       call-interactively(eval-last-sexp nil nil)
>
> If you want us to help, please provide working stand alone code, with
> test data.
>
> (By the way, my emacs "23.2.1" doesn't have a forward-search-regexp
> function).

search-forward-regexp

more later tomorrow

>
> --
> __Pascal Bourguignon__                    http://www.informatimago.com/
> A bad day in () is better than a good day in {}.

Re: How to cast an imperative loop into a readable recursive function ?

[Tim Bradshaw]

On 2010-12-03 03:19:43 +0000, Katalin Sinkov said:

> your iterate is again a loop, ie a non-functional construct

Is it?  Consider this form:

(for (i 0 100)
  (print i))

This is iterative, right, I mean obviously.

Except here's the definition of FOR:

(defmacro for ((var min max) &body decls-and-forms)
  (let ((maxn (make-symbol "MAX"))
        (nextn (make-symbol "NEXT-1")))
    `(let ((,maxn ,max))
       (labels ((,nextn (,var)
                  (when (= ,var ,maxn)
                    (return-from ,nextn ,maxn))
                  (let ((,var ,var))
                    ,@decls-and-forms)
                  (,nextn (1+ ,var)))
                (next ()
                  (,nextn (1+ ,var))))
         (,nextn ,min)))))

There seems to be no iteration there, and expanding (and renaming 
gensyms to make it clearer):

(let ((max 100))
  (labels ((next-1 (i)
             (when (= i max) (return-from next-1 max))
             (let ((i i))
			 (print i))
             (next-1 (1+ i)))
           (next () (next-1 (1+ i))))
    (next-1 0)))

No iteration there.