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

0 Members and 1 Guest are viewing this topic.

Grrr1337

  • Swamp Rat
  • Posts: 812
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)
  )
)
vevo.bg

roy_043

  • Water Moccasin
  • Posts: 1895
  • 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.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
Re: Recursive function on the fly
« Reply #2 on: January 10, 2018, 07:14:48 AM »
Try a tail-recursive syntax.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Grrr1337

  • Swamp Rat
  • Posts: 812
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)
  )
)
vevo.bg

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
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.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

VovKa

  • Water Moccasin
  • Posts: 1626
  • 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: 17750
  • Have thousands of dwgs to process? Contact me.
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
Engineering Technologist • CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

roy_043

  • Water Moccasin
  • Posts: 1895
  • 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: 1895
  • 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: 12905
  • 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.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
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
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Lee Mac

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

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
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).
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Lee Mac

  • Seagull
  • Posts: 12905
  • 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.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
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.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org