Author Topic: Recursive function on the fly  (Read 1211 times)

0 Members and 1 Guest are viewing this topic.

Grrr1337

  • Swamp Rat
  • Posts: 710
Recursive function on the fly
« on: January 09, 2018, 06:58:59 PM »
Hi guys, just wanted to leave this here - you might find it interesting:
Code - Auto/Visual Lisp: [Select]
  1. _$ (
  2.   (setq groupby3
  3.     (lambda (L / r)
  4.       (repeat 3 (and L (setq r (cons (car L) r))) (setq L (cdr L)) r)
  5.       (if L (cons (reverse r) (groupby3 L)) (progn (setq groupby3 nil) (list (reverse r))))
  6.     )
  7.   )
  8.   '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
  9. )
  10. ((0 1 2) (3 4 5) (6 7 8) (9 10 11) (12 13 14) (15 16))
  11. _$ groupby3
  12. nil

:)
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)

roy_043

  • Water Moccasin
  • Posts: 1736
  • BricsCAD 18
Re: Recursive function on the fly
« Reply #1 on: January 10, 2018, 04:23:43 AM »
Two minor improvements:
Code - Auto/Visual Lisp: [Select]
  1. (
  2.   (setq groupby3
  3.     (lambda (L / r)
  4.       (repeat 3 (and L (setq r (cons (car L) r)) (setq L (cdr L))))
  5.       (if L (cons (reverse r) (groupby3 L)) (progn (setq groupby3 nil) (list (reverse r))))
  6.     )
  7.   )
  8.   '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
  9. )

Maybe this coding style is just too confusing? :evil:

Note that because of all the setq's and the use of recursion the code will not be particularly fast.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9285
Re: Recursive function on the fly
« Reply #2 on: January 10, 2018, 07:14:48 AM »
Try a tail-recursive syntax.
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

Grrr1337

  • Swamp Rat
  • Posts: 710
Re: Recursive function on the fly
« Reply #3 on: January 10, 2018, 09:22:46 AM »
Maybe this coding style is just too confusing? :evil:

Yes - it looks confusing,
But I think if a proper comment description is written about the recursive function (about its inputs/return, aswell note that it localises itself) then it won't be required to understand it, just use it.
Sorry I didn't include any - my point was to share the overall technique, since it looks interesting.

Note that because of all the setq's and the use of recursion the code will not be particularly fast.

Thanks for mentioning, however any recursive routine could be implemented (the one I used was just to demonstrate something practical for that technique).


Try a tail-recursive syntax.

Not sure if this is tail-recursion (but its getting more confusing) :

Code - Auto/Visual Lisp: [Select]
  1. _$ (
  2.   (setq
  3.     from_right
  4.     (lambda ( L )
  5.       (if (print (setq L (reverse (cdr (reverse L))))) (from_left L) (setq from_right nil from_left nil))
  6.     )
  7.     from_left
  8.     (lambda ( L )
  9.       (if (print (setq L (cdr L))) (from_right L) (setq from_left nil from_right nil))
  10.     )
  11.   )
  12.   '(1 2 3 4 5 6 7 8 9)
  13. )
  14.  
  15. (2 3 4 5 6 7 8 9)
  16. (2 3 4 5 6 7 8)
  17. (3 4 5 6 7 8)
  18. (3 4 5 6 7)
  19. (4 5 6 7)
  20. (4 5 6)
  21. (5 6)
  22. (5)
  23. nil nil
  24. _$ from_right
  25. nil
  26. _$ from_left
  27. nil
  28.  

BTW I'm a dummy at understanding recursions - just good enough to write the linear ones.
So please share your findings to build-up opinions about this.

One additional thing from me:
For that technique, the recursive function must be error-proof, since it won't be able to undefine itself when error occurs.



Should "recursive annonymous function" be a more appropriate name?  :tongue2:
« Last Edit: January 10, 2018, 09:26:39 AM by Grrr1337 »
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9285
Re: Recursive function on the fly
« Reply #4 on: January 10, 2018, 09:46:32 AM »
See the examples on the wikipedia page for an example of a tail-recursive function.
[ https://en.wikipedia.org/wiki/Tail_call#Example_programs ]

> Should "recursive annonymous function" be a more appropriate name?  :tongue2:
No, because it is named. You are just employing syntactic sugaring techniques. I posted a snip of a conversation I was having with MP which covers this topic, for you once (did you not read it?).
MP, sorry for posting something you wrote out of context but I had the snip in my files and no link. Also, you explain things...gooder.

If you feel as though you're a `dummy at these things', you really should read a good solid book on programing. Structure and Interpretation of Computer Programs is what I started with.
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

VovKa

  • Swamp Rat
  • Posts: 1174
  • Ukraine
Re: Recursive function on the fly
« Reply #5 on: January 10, 2018, 10:22:02 AM »
Should "recursive annonymous function" be a more appropriate name?  :tongue2:
compare
Code: [Select]
(setq from_right 1 from_left 2)
((setq from_right (lambda (L)
    (if (print (setq L (reverse (cdr (reverse L)))))
      (from_left L)
      (setq from_right nil
    from_left nil
      )
    )
  )
       from_left  (lambda (L)
    (if (print (setq L (cdr L)))
      (from_right L)
      (setq from_left nil
    from_right nil
      )
    )
  )
 )
  '(1 2 3 4 5 6 7 8 9)
)
(print from_right)
(print from_left)
with
Code: [Select]
(setq from_right 1 from_left 2)
((lambda (L from_right from_left) (from_left L))
  '(1 2 3 4 5 6 7 8 9)
  (lambda (L)
    (if (print (setq L (reverse (cdr (reverse L)))))
      (from_left L)
    )
  )
  (lambda (L)
    (if (print (setq L (cdr L)))
      (from_right L)
    )
  )
)
(print from_right)
(print from_left)

MP

  • Seagull
  • Posts: 17496
Re: Recursive function on the fly
« Reply #6 on: January 10, 2018, 10:25:46 AM »
Should "syntax masturbation" be a more appropriate name?

fixed
\|// Set goal. Experiment tirelessly until
|Oo| practice has become expertise.  Loop.
|- | LinkedIn | Dropbox

roy_043

  • Water Moccasin
  • Posts: 1736
  • BricsCAD 18
Re: Recursive function on the fly
« Reply #7 on: January 10, 2018, 11:26:55 AM »
Maybe this coding style is just too confusing? :evil:
Yes - it looks confusing
My point actually is that by condensing the code to fit on a limited number of lines you are confusing yourself, let alone the readers of your code. Just look at your (repeat ...) expression.

roy_043

  • Water Moccasin
  • Posts: 1736
  • BricsCAD 18
Re: Recursive function on the fly
« Reply #8 on: January 10, 2018, 02:21:36 PM »
Does AutoLisp support tail recursion? Using the example from the Wiki link I would say that BricsCAD Lisp does not.

Lee Mac

  • Seagull
  • Posts: 12295
  • London, England
Re: Recursive function on the fly
« Reply #9 on: January 10, 2018, 03:31:50 PM »
Example using tail recursion:
Code - Auto/Visual Lisp: [Select]
  1. (   (lambda ( rec lst ) (rec lst nil))
  2.     (lambda ( lst acc )
  3.         (if lst
  4.             (rec (cdddr lst) (cons (mapcar '(lambda ( a b ) a) lst '(0 1 2)) acc))
  5.             (reverse acc)
  6.         )
  7.     )
  8.    '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
  9. )
Code - Auto/Visual Lisp: [Select]
  1. ((0 1 2) (3 4 5) (6 7 8) (9 10 11) (12 13 14) (15 16))

AFAIK, tail recursion isn't optimised in AutoLISP as it is in other languages.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9285
Re: Recursive function on the fly
« Reply #10 on: January 10, 2018, 03:55:14 PM »
No it's not (from what I remember).   

Code: [Select]
(defun factorial (n)
 (if (= n 1)
    1
    (* n (factorial (- n 1)))))

Command: (factorial 5)
Entering (FACTORIAL 5)
  Entering (FACTORIAL 4)
    Entering (FACTORIAL 3)
      Entering (FACTORIAL 2)
        Entering (FACTORIAL 1)
        Result:  1
      Result:  2
    Result:  6
  Result:  24
Result:  120
120



(defun factorial (n)
  (fact-iter 1 n))
(defun fact-iter (product n)
  (if (< n 2)
      product
      (fact-iter (* product n)
                 (- n 1))))
Command: (factorial 5)
Entering (FACTORIAL 5)
  Entering (FACT-ITER 1 5)
    Entering (FACT-ITER 5 4)
      Entering (FACT-ITER 20 3)
        Entering (FACT-ITER 60 2)
          Entering (FACT-ITER 120 1)
          Result:  120
        Result:  120
      Result:  120
    Result:  120
  Result:  120
Result:  120
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

Lee Mac

  • Seagull
  • Posts: 12295
  • London, England
Re: Recursive function on the fly
« Reply #11 on: January 10, 2018, 04:38:46 PM »

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9285
Re: Recursive function on the fly
« Reply #12 on: January 10, 2018, 04:43:52 PM »
No it's not (from what I remember).

Why?
Why isn't it optimized? ...*shrug* I don't have any more knowledge of the inside workings of the interpreter than you do (any more then observations).
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

Lee Mac

  • Seagull
  • Posts: 12295
  • London, England
Re: Recursive function on the fly
« Reply #13 on: January 10, 2018, 04:45:03 PM »
No it's not (from what I remember).

Why?
Why isn't it optimized? ...*shrug* I don't have any more knowledge of the inside workings of the interpreter than you do (any more then observations).

Apologies, I misunderstood your response - I thought you were disputing the tail-recursiveness of the function, as opposed to agreeing with the lack of optimisation.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9285
Re: Recursive function on the fly
« Reply #14 on: January 10, 2018, 04:50:25 PM »
Ah. No problem.

I didn't look at your code; I trust your judgement as to its operation. ...I only made the suggestion to use a tail-recursive format for an exercise and a bit of a lesson into recursion 101. And, to eventually drive home the point about iterative functions and proper algorithm design.
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--