How to cast an imperative loop into a readable recursive function ?
Katalin Sinkov
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) )
)
)
)
)
)
Paul Rubin
> 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.
RG
<ffc3587e-3cb3-41f6...@e20g2000vbn.googlegroups.com>,
Katalin Sinkov <lisps...@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
Katalin Sinkov
another smaller example
s=index
v=value
series is
s=2345789
v=abcdwxy
after 5 there is 7 because there was a reset in the form
(s=7,l=whatever)
(s=2,l=4)2345(s=7,l=whatever)
only start index of the subseries is mentioned inside parens.
hope it was clear, or i can try again
Katalin Sinkov
> 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".
Paul Rubin
> 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.
Katalin Sinkov
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.
your iterate is again a loop, ie a non-functional construct
how is any looping construct defined in terms of
car/cdr/cons/quote/atom/eq/cond/
Katalin Sinkov
math would be an overkill and not needed. its issue of programming
style.
Paul Rubin
> 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)))))))
Pascal J. Bourguignon
> 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).
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Katalin Sinkov
> Katalin Sinkov <lispstyl...@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):
it has been quite helpful. I need to give a function name to be able
to recurse.
>
> (defun foo (n str)
> (let ((s ...) (l ...) (p ...) ;;; s=start l=length p=??????
> ;; after reading the (s=2 l=4) prefix above, ;;; this is exactly what should happen
> ;; p points past the end of it ;;; and how mine worked (pseudocode)
> (if (< n l) ;;; in {} .. if ( (n-s) < l )
> (aref str (+ p n)) ;;; (aref str (- n s))
> (foo (- n l) (substring str (+ p l))))))) ;;; I dont think i need substring if
;;; I set
a pointer.
What i find very confusing is this :
right now I have lots of globals in emacs.
all the data is in a file opened in emacs.
At some stage there will confusion and readability issue.
What strategies are there to grapple with this issue ?
At the moment, it appears that I can just copy parts of the buffer
(file) into a string type variable that is temporary and is
deallocated as soon as the function exits.
what is a recommended emacs command to copy parts of buffer into a
temporary local string variable ?
I should place stars around all global variable identifiers.
Paul Rubin
>> (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.
Katalin Sinkov
wrote:
search-forward-regexp
more later tomorrow
Tim Bradshaw
> 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.
Tim Bradshaw
> (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)))))
ANyone who looked at this closely would realise the local NEXT function
does not work. here is a version without that:
(defmacro for ((var min max) &body decls-and-forms)
(let ((maxn (make-symbol "MAX"))
(nextn (make-symbol "NEXT")))
`(let ((,maxn ,max))
(labels ((,nextn (,var)
(when (= ,var ,maxn)
(return-from ,nextn ,maxn))
(let ((,var ,var))
(declare (ignorable ,var))
,@decls-and-forms)
(,nextn (1+ ,var))))
(,nextn ,min)))))
Sorry