Jump to content

The perfect recursive function


SOliver

Recommended Posts

Hi folks.

 

EDIT:

To spare confusion this is an attempt at writing the perfect recursive function, not necessarily the perfect recursive function - in fact on page two it is starting to go downhill. I would say it was a tribute but I've never known the real thing :D

/EDIT

 

So a few weeks ago I posted a thread on some of the quirks that lisp offers and a few examples of how they could be used to make very flexible functions, which are framed to Ruby's don't repeat yourself ethos. Sadly it wasn't received well (no comments).

 

Not one to be disheartened by what seems to be a fundamental lack of interest in the language itself I set myself the challenge of writing the perfect recursive function. I have posted my attempt below with some of the axioms of the method written in the comments. I'm hoping this will spark discusion but either way

 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Recursive list processor                                                                ;
;                                                                                                                ;
;Members                                                                                                ;
;    params         = list                                                                            ;
;    derivative = list  or nil                                                                          ;
;    handler      = unevaluated function name prepended          ;
;    processor  = unevaluated lisp expression                             ;
;                                                                                                                ;
;Axioms of the list processor                                                        ;
;    -The handler method is structured in such a manner that it         ;
;     accepts one parameter.                                                                ;
; -Whilst the handler method doess not necessitate          ;
;  That it accommodates for lists and atoms alike                ;
;  the return value from this method must be either            ;
;     nil or a list.The handler must be able to process        ;
;  elements output therefore it can be said that where  ;
;  a handler potential to return a list whose contents  ;
;  include any number of subsequently embeded lists,        ;
;     including any list structure containing a combination;
;     of atoms and lists, it must include processing for   ;
;     both.                                                                                                ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun recursiveListHandler( params handler processor / derivative)
 (mapcar
    '(lambda(x)
       (if(Setq derivative(handler x))
             (recursiveListHandler derivative handler processor)
             (processor x)
         )
       )
     params
   )
)

Should add that the axiom list doesn't cover the processor yet, when I get the chance I'll update it.

Edited by SOliver
Link to comment
Share on other sites

  • Replies 28
  • Created
  • Last Reply

Top Posters In This Topic

  • SOliver

    14

  • Lee Mac

    10

  • irneb

    3

  • CHLUCFENG

    1

"Hi, how are you?"

 

Also, we have not yet reached the limits of Moore's law. In reality, it's mechanics and physics that keep us electrical/computer folks from creating everything. Anything is possible in our world, we just need to overcome mechanical and mother nature.

 

Keep rockin' LISP folks!

Link to comment
Share on other sites

Hi folks.

 

So a few weeks ago I posted a thread... Sadly it wasn't received well (no comments).

 

Not one to be disheartened... I set myself the challenge of writing the perfect recursive function. I have posted my attempt below...

 

;; <-Attempt

 

Should add that the axiom list doesn't cover the processor yet, when I get the chance I'll update it.

 

In the spirit of "If a tree falls in the forest, and nobody is around to hear it, does it make a noise?"... Can something be called "perfect" if in the original post it is noted that additions are forthcoming? :lol: LoL

(^^ I jest ^^)

 

I appreciate the attempt (and the code comments) none-the-less, Soliver. I highly doubt I would offer anything better.

 

Cheers! :beer:

Link to comment
Share on other sites

In the spirit of "If a tree falls in the forest, and nobody is around to hear it, does it make a noise?"... Can something be called "perfect" if in the original post it is noted that additions are forthcoming? :lol: LoL

(^^ I jest ^^)

 

I appreciate the attempt (and the code comments) none-the-less, Soliver. I highly doubt I would offer anything better.

 

Cheers! :beer:

 

Touche' RenderMan lol. I should have clarified the reference to perfection was exclusive to the function. Thanks for the positives :)

 

My emails say that Lee Mac commented earlier

Example of usage?

but I can't seem to see it.

 

I'll upload some examples soon.

Link to comment
Share on other sites

Admittedly no the most exciting example (I will post one honest ;) ) but this simple implementation should provide an inital idea of how it works.

;Sample list
(setq sampleList '((1 11 13)
                         (55 55 66)
                           (75 ((44 102 999
                              ((1024 1280 1690)))
                                  (33 768 512)))))
;Sample handler
(defun isList(x / )
 (if(listp x)
       x
       nil
   )
)
;Sample processor
(defun isDivisibleByThree(x /)
 (if(= (rem x 3) 0)
       t
       nil
   )
)
;Method call
(recursiveListHandler sampleList isList isDivisibleByThree)

 

The method does nothing more than translate the sampleList variable in to boolean atoms which are true only when the numerical value is divisible by three (or it is 0). and returns the list.

 

I'll post an exciting one in an hour or so - hopefully.

 

Cheers

Link to comment
Share on other sites

Not worth pursuing? Dare I ask why?

 

I didn't really see the point of the function, it would seem to obfuscate code where a specifically written function in its place would retain readability and furthermore, using the mapcar structure would fail with dotted pairs excluding it from a generic application. Other than that I wasn't prepared to spend time deciphering the 'axioms' to work out how it could be used - hence why I retracted my comment.

But then maybe its just too clever in all its 'perfection' for my small mind to conceive.

Link to comment
Share on other sites

I didn't really see the point of the function, it would seem to obfuscate code where a specifically written function in its place would retain readability and furthermore, using the mapcar structure would fail with dotted pairs excluding it from a generic application. Other than that I wasn't prepared to spend time deciphering the 'axioms' to work out how it could be used - hence why I retracted my comment.

 

You appear to be taking some offense at the thread and I can't say I understand why.

 

The thread aptly states that it is an "attempt" at writing a perfect recursive function (I suppose function framework technically). I'm in no way proclaiming that this is in fact the perfect function but rather attempting to open an interesting debate for those who enjoy lisp as more than just a convenient addition to autocad.

 

I spent a lot of time weighing out the pro's and con's of writing such a method with different approaches and I personally can't see a better alternative which is another reason I hoped for the forum to dissect the code.

 

As for the axioms: I may write comments in an overtly autistic manner but I believe that having written them in a similar theme to the type of statements you'd expect from a logic class was the correct choice. That said I may just understand them because I've wrote them.

 

But then maybe its just too clever in all its 'perfection' for my small mind to conceive.

Given the profound nature of your presence on the forum I would have thought you off all people would both understand and enjoy such topics. But you may be right; a lot of programmers never understand recursion :shock:

 

As an ending note: You surely can't see this method as obfuscation? It's purpose is the opposite.

 

EDIT:

 

Lol Lee; I'll admit that you trolled me admirably here. I'm too naive to understand this...... It is too difficult to read 90 words........ Well played; until I thought of the word count I genuinely thought the comments were real.

Edited by SOliver
Link to comment
Share on other sites

OK, what I can gather from your code (not trying to troll in 90 words or less :shock:) is you're attempting to generalize the usual recursive method. And for those who "might" not understand, recursion need 2 main things to work:

 

  1. It needs to call itself again in order to form a loop or produce a result. This is what the word recursion means.
  2. It needs to check for an end condition to keep from making an endless loop.

Your code simply makes it posible to move the check and the actual calculations outside the recursive function. I think this is what Lee refers to with "obfuscating". It's not always as "readable" when your calculation happens somewhere else, and even more so if your check is also in some other place.

 

Other than that, it could save some typing, since you just need to produce 2 defuns (one for check and one for calc) which you then send together with the data to this generalized function. If it's actually less typing depends on the situation.

 

Although as Lee's also pointed out, I think this function falls a bit short of being truly general. Since it uses the mapcar function it can only work on lists. As a quick hash, though untested:

(defun recursiveListHandler1 (params handler processor / derivative)
 (if (listp params)
   (if (handler (car params))
     (cons (processor (car params)) (recursiveListHandler1 (cdr params) handler processor))
     (processor (car params))
   )
   (if (setq derivative (handler params))
     (recursiveListHandler1 derivative handler processor)
     (processor params)
   )
 )
)

Also the mapcar is actually an iterative approach - though it might be implemented recursively (but then it wouldn't fail on dotted pairs). So your function isn't "purely" recursive. And neither is (yours and mine) it not state-based, since it uses a setq. So recursive optimization starts becoming less efficient and starts eating into the stack.

 

I'm sorry if this sounds harsh, but you are in the pursuit of "perfection" aren't you? I'd just like to know which way you deem perfection to hang? :lol: Is it efficiency or elegance? They sometimes become mutually exclusive.

Link to comment
Share on other sites

No 'trolling' intended (I don't even know about trolling in 90 words and doubt I have the wit to do so) - my points were genuine, I couldn't understand the purpose of your function and believed it would only decrease code readability.

 

No, I was not offended, but I did find your thread title a little pretentious, hence my jibe at it being too clever for me - I apologise if this caused offence.

Link to comment
Share on other sites

No 'trolling' intended (I don't even know about trolling in 90 words and doubt I have the wit to do so) - my points were genuine, I couldn't understand the purpose of your function and believed it would only decrease code readability.

 

No, I was not offended, but I did find your thread title a little pretentious, hence my jibe at it being too clever for me - I apologise if this caused offence.

 

The 90 words was reference to the length of the axioms

 

Yeah the title was intentionally pretentious, as commented my previous post went unheard so I figured - against all that I stand for, that I should use the blog naming convention of sensationalism/convtraversy.

 

I wasn't entirely sure where you're post was aimed at but I have to admit you were one of the people I was hoping would be all about the subject and I was rather dissappointed that you opted out.

 

OK, what I can gather from your code (not trying to troll in 90 words or less :shock:) is you're attempting to generalize the usual recursive method. And for those who "might" not understand, recursion need 2 main things to work:

 

  1. It needs to call itself again in order to form a loop or produce a result. This is what the word recursion means.
  2. It needs to check for an end condition to keep from making an endless loop.

Your code simply makes it posible to move the check and the actual calculations outside the recursive function. I think this is what Lee refers to with "obfuscating". It's not always as "readable" when your calculation happens somewhere else, and even more so if your check is also in some other place.

 

Other than that, it could save some typing, since you just need to produce 2 defuns (one for check and one for calc) which you then send together with the data to this generalized function. If it's actually less typing depends on the situation.

 

[/Quote]Yeah the main idea was that with lisp's loose structure control there is more than likely a clever way to write a perfect skeleton function which could be used for all recursive methods alike without having to re-write the full method every time.

 

I can see why it may be considered to have legibility issues as you've noted above although I felt not having to read through what would be in effect redundant code ,if a new method were to be written for every use, would surely be beneficial - after all the code is short enough that it can be remembered easily. That said a method such as the one I originally posted would really on pay off (in individual cases) where the calling method will make two or more recursive calls.

 

Although as Lee's also pointed out, I think this function falls a bit short of being truly general. Since it uses the mapcar function it can only work on lists. As a quick hash, though untested:

 

Also the mapcar is actually an iterative approach - though it might be implemented recursively (but then it wouldn't fail on dotted pairs). So your function isn't "purely" recursive. And neither is (yours and mine) it not state-based, since it uses a setq. So recursive optimization starts becoming less efficient and starts eating into the stack.

I'll admit handling dotted lists never crossed my mind throughout the write or indeed up until it was pointed out by Lee in the thread.

 

I have a love-hate relationship with the deriviate variable. On the one hand it allows for a level of formal structure (in this case single member method for processing and handling) whilst still allowing for the handler to expand on atoms or lists. For example say you were to pass a directory path to the handler with the intention of creating a list of sub directories. But as you say that takes away from the truly recursive nature of the method, effectively making it greedy (over ambitious lol).

 

And it is becoming apparent that stack overflow is of concern when such a liberty is given to the handler method.

I'm sorry if this sounds harsh, but you are in the pursuit of "perfection" aren't you? I'd just like to know which way you deem perfection to hang? :lol: Is it efficiency or elegance? They sometimes become mutually exclusive.

Not at all this is premium quality feedback :D

 

With the derivative in place, noting the stack overflow comments, efficiency may suffer if the functions aren't well thawed and more importantly not goin' to store unhandlable amounts of data. That said I was greedy trying to implement the derivative for sake of flexibility and there are some heavy costs and potential problems that may be a result of it.

 

Were the function to be made as a pure recursive function (get rid of the greedy derivative) I feel that efficiency and elegance can be achieved in harmony. Although the flexibility would suffer.

 

In general I felt the topic to be one that the community could really get it's teeth into, exploring some of the lesser known yet powerful approaches that lisp enables a developer to undertake. After all lisp is the chuck norris of the programming language world :)

Edited by SOliver
Link to comment
Share on other sites

I wasn't entirely sure where you're post was aimed at but I have to admit you were one of the people I was hoping would be all about the subject and I was rather dissappointed that you opted out.

 

Oh, don't get me wrong - I'm definitely keen to discuss the language, it makes things interesting.

 

To quell your disappointment, this was my intial understanding of your intention: a mapcar function to process nested lists, maybe something along the lines of:

 

(defun nmapcar ( _function _list )
 (
   (lambda ( _function )
     (mapcar
       (function
         (lambda ( item )
           (if (listp item)
             (nmapcar _function item)
             (_function item)
           )
         )
       )
       _list
     )
   )
   (eval _function)
 )
)

 

For Example:

_$ (nmapcar '1+ '(1 2 (1 2 3 (4)) 5))
(2 3 (2 3 4 (5)) 6)

 

But that is probably about as generic as I would make it. The above will merely match the characteristics of a mapcar call, but process nested lists.

Link to comment
Share on other sites

Oh, don't get me wrong - I'm definitely keen to discuss the language, it makes things interesting.

 

To quell your disappointment, this was my intial understanding of your intention: a mapcar function to process nested lists, maybe something along the lines of:

 

(defun nmapcar ( _function _list )
 ;;Code from above

)

For Example:

_$ (nmapcar '1+ '(1 2 (1 2 3 (4)) 5))
(2 3 (2 3 4 (5)) 6)

But that is probably about as generic as I would make it. The above will merely match the characteristics of a mapcar call, but process nested lists.

The method sums up the (exlusive of the derivative) generalised recursion, dare I say perfectly lol. It certainly for all intensive purposes carries out the state based recursion taking a function as a param. That said the reference to the derivative is merely for note, it changes the nature of the question - might have purpose yet though lol.

 

My attempt is not to dissimilar to the above although it takes the symbol as a parameter as opposed to taking the unevaluated equivalent. To be honest this might not be a good thing, however; until tomorrow morning or so I'm arrogantly assuming that lisp passes native and global methods as pointers. I'll test it tomorrow and let you's know the results.

(defun nmapcar2 ( _function _list )
 (mapcar
   '(lambda ( item )
      (if (listp item)
        (nmapcar2 _function item)
        (_function item)
      )
    )
     _list
 )
)

Not particularly different other than the need for the eval statement has been removed. As said the only real difference is passing the symbol

(nmapcar2   1+  '(1 2 (1 2 3 (4)) 5)))
(2 3 (2 3 4 (5)) 6)

I suppose what's good about both methods is that since they still only take one parameter so the function can do any group of thing to the value in one swoop - I say this because I initially thought your method ran multiple function iteratively and ended up fuelling my compulsive nature by having a go at writing one as such before thinking "this is madness, there's no need"

 

One thing I would possibly be inclined to do is pass a validation method as well as the function. For example:

(defun nmapcar2 ( _function _validation _list )
 (mapcar
   '(lambda ( item )
      (if (_validation item)
        (nmapcar2 _function item)
        (_function item)
      )
    )
     _list
 )
)

Where the validation method takes the place of listp. In this instance the call would be.

(nmapcar2   1+ _someValidationMethod  '(1 2 (1 2 3 (4)) 5)))

I reckon this is important as it provides a method of identifying pre-structured lists, sort of in the theme of objects. Can't think of a great example but say you had a nested set of mapped blocks and subsequently embedded blockss, you may want to continue in until the entity type was other than a block. This would allow you to retain the list structure without calling the nmapcar function again. That said if you're able to make lists that are gauranteed not to *error* you're probably coding the earth using pebbles in the desert and have no need for lisp :D

 

EDIT:

 

Perhaps an overly ambitious statement to make but: With a bit of tinkering, possibly reinstating the derivative the method could be used to map all possible routes of the collatz conjecture (half or triple plus 1) from a given starting point until the stopping time. For example 16 can be derived from both 5 and 32

Edited by SOliver
Link to comment
Share on other sites

Passing a quoted symbol is standard behaviour in LISP, i.e.:

 

(mapcar '1+ '(1 2 3 4 5))

Yes, though that then requires an eval. So it's a situation of half-a-dozen of the one and six of the other (if there's a duplicated ByValue type argument passing in Lisp).
Link to comment
Share on other sites

Passing a quoted symbol is standard behaviour in LISP, i.e.:

(mapcar '1+ '(1 2 3 4 5))

It does appear to be common behaviour although the memory allocation doesn't appear to support it's use in this instance. It is standard behaviour to pass quoted lists for function calls though. In any case the only difference appears to be whether the memory is allocated to "dynamic" or "memory". One passes a string (effectively a hash table reference) the other a pointer. Pointers in most cases are smaller than their string counterpart

 

So as not to ramble without reference. In many cases your code favours (function (lambda)) as opposed to '(lambda). Function while anonymous is still a function; would this not contradict your statement?

 

That said is it not common practice to avoid the use of eval like the plague where possible?

 

Could you provide a source that states your comment, or is at least indicative of it?

 

Please forgive my somewhat pathological arrogance but I find it hard to accept language "truths" based solely on a single comment in a forum, from an exulted member or not.

 

P.S. As an end note I just want to say that this thread is going as well as I would've hoped were I an optimist.

 

Cheers,

SOliver

Link to comment
Share on other sites

The quoted list wasn't really relevant to the example, this make no difference to the function. My reason for the use of eval was to enable the function to accept a quoted functional argument, to match the behaviour of existing LISP functions.

Link to comment
Share on other sites

The quoted list wasn't really relevant to the example, this make no difference to the function. My reason for the use of eval was to enable the function to accept a quoted functional argument, to match the behaviour of existing LISP functions.

 

That's fair enough I realise I'm probably just arguing semantics with the use of the word "standard". Being overtly pedantic/curious aren't native methods written in c/c++ and therefore not entirely comparable? By that I mean that for example passing python to lisp would be handled differently from passing lisp to lisp.

(defun test1 (x )
(mem)
)
(test1 'someFunction)
(test 1 someFunction)

As far as memory goes using the above shows what I said earlier about the storage location. I'm in the process of test efficency or at least iterations/m. Obviously larger quoted strings may initally present larger memory requirements but that may be subject to this being a non-referencing example (referencing the x value that is)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...