[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

functions as orbits (sequences

Taoufik Dachraoui

8/2/2015 4:15:00 PM

Hi

The macro DEFORBIT (a sequence starting with x0 is called an orbit around x0) is used to define
any function that can be expressed as a sequence.

(deforbit (foo args (initial-elements form) &key (index (gensym "N"))))

For example:

? (deforbit %fact () (((a 1)) (* a n)) :index n)
%FACT
? (funcall (%fact) 5)
120
? (deforbit %fib () (((a 0) (b 1)) (+ a b)))
%FIB
? (funcall (%fib) 10)
55
? (deforbit %iter (f x) (((a (funcall f x))) (funcall f a)))
%ITER
? (deforbit %ack () (((f (lambda (n) (1+ n)))) (%iter f 1)))
%ACK
? (funcall (funcall (%ack) 4) 1)
65533

The interesting thing is that functions defined using DEFORBIT are iterative and thus much faster
than their corresponding recursive definition (the recursive ackermann function on my computer
failed to compute (ackermann 4 1) because of stack overflow, and Fibonacci of 10000 run for ever.

The following shows how fast it is when using orbits instead of recursive functions:

? (time (funcall (%fib) 10000))
(FUNCALL (%FIB) 10000)
took 22 milliseconds (0.022 seconds) to run.
2 milliseconds (0.002 seconds, 9.09%) of which was spent in GC.
During that period, and with 2 available CPU cores,
19 milliseconds (0.019 seconds) were spent in user mode
3 milliseconds (0.003 seconds) were spent in system mode
4,457,848 bytes of memory allocated.
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875


? (time (funcall (funcall (%ack) 4) 1))
(FUNCALL (FUNCALL (%ACK) 4) 1)
took 12 milliseconds (0.012 seconds) to run.
During that period, and with 2 available CPU cores,
12 milliseconds (0.012 seconds) were spent in user mode
0 milliseconds (0.000 seconds) were spent in system mode
352 bytes of memory allocated.
65533


-Taoufik
12 Answers

William James

8/3/2015 8:55:00 AM

0

Taoufik Dachraoui wrote:

> The following shows how fast it is when using orbits instead of recursive functions:
>
> ? (time (funcall (%fib) 10000))
> (FUNCALL (%FIB) 10000)
> took 22 milliseconds (0.022 seconds) to run.
> 2 milliseconds (0.002 seconds, 9.09%) of which was spent in GC.
> During that period, and with 2 available CPU cores,
> 19 milliseconds (0.019 seconds) were spent in user mode
> 3 milliseconds (0.003 seconds) were spent in system mode

Recursion isn't slow when done correctly.

Scheme:

(define (fib n)
(let go ((a 0) (b 1) (n n))
(if (zero? n)
a
(go b (+ a b) (- n 1)))))

Running this under (interpreted) Gauche Scheme on a very old
Windows XP laptop:

gosh> (time (fib 10000))
;(time (fib 10000))
; real 0.062
; user 0.047
; sys 0.015

--
The Authoritarian Personality extends beyond the attempt to pathologize
cohesive gentile groups to pathologizing adaptive gentile behavior in general.
The principal intellectual difficulty is that behavior that is critical to
Judaism as a successful group evolutionary strategy is conceptualized as
pathological in gentiles. --- Dr. Kevin MacDonald; "The Frankfurt School of
Social Research and the Pathologization of Gentile Group Allegiances"

Taoufik Dachraoui

8/3/2015 1:09:00 PM

0

On Sunday, August 2, 2015 at 5:15:13 PM UTC+1, Taoufik Dachraoui wrote:
> Hi
>
> The macro DEFORBIT (a sequence starting with x0 is called an orbit around x0) is used to define
> any function that can be expressed as a sequence.
>
> (deforbit (foo args (initial-elements form) &key (index (gensym "N"))))
>
> For example:
>
> ? (deforbit %fact () (((a 1)) (* a n)) :index n)
> %FACT
> ? (funcall (%fact) 5)
> 120
> ? (deforbit %fib () (((a 0) (b 1)) (+ a b)))
> %FIB
> ? (funcall (%fib) 10)
> 55
> ? (deforbit %iter (f x) (((a (funcall f x))) (funcall f a)))
> %ITER
> ? (deforbit %ack () (((f (lambda (n) (1+ n)))) (%iter f 1)))
> %ACK
> ? (funcall (funcall (%ack) 4) 1)
> 65533
>
> The interesting thing is that functions defined using DEFORBIT are iterative and thus much faster
> than their corresponding recursive definition (the recursive ackermann function on my computer
> failed to compute (ackermann 4 1) because of stack overflow, and Fibonacci of 10000 run for ever.
>
> The following shows how fast it is when using orbits instead of recursive functions:
>
> ? (time (funcall (%fib) 10000))
> (FUNCALL (%FIB) 10000)
> took 22 milliseconds (0.022 seconds) to run.
> 2 milliseconds (0.002 seconds, 9.09%) of which was spent in GC.
> During that period, and with 2 available CPU cores,
> 19 milliseconds (0.019 seconds) were spent in user mode
> 3 milliseconds (0.003 seconds) were spent in system mode
> 4,457,848 bytes of memory allocated.
> 336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820653326808361593737347904838652682630408924> 630564318873545443695598274916066020998841839338646527313000888302692356736131351175792974378544137521305205043477016022647583189065278908551543661> 595829872796829875106312005754287834532155151038708182989697916131278562650331954871402142875326981879620469360978799003509623022910263681314931952> 756302278376284415403605844025721143349611800230912082870460889239623288354615057765832712525460935911282039252853934346209042452489294039017062338> 889910858410651831733604374707379085526317643257339937128719375877468974799263058370657428301616374089691784263786242128352581128205163702980893320> 999057079200643674262023897831114700540749984592503606335609338838319233867830561364353518921332797329081337326426526339897639227234078829281779535> 805709936910491754708089318410561463223382174656373212482263830921032977016480547262438423748624114530938122065649140327510866433945175121615265453> 613331113140424368548051067658434935238369596534280717687753283482343455573667197313927462736291082106792807847180353291311767789246590899386354593> 278945237776744061922403376386740040213303432974969020283281459334188268176838930720036347956231171031012919531697946076327375892535307725523759437> 884345040677155557790564504430166401194625809722167297586150269684431469520346149322911059706762432685159928347098912847067408620085871350162603120> 719031720860940812983215810772820763531866246112782455372085323653057759564300725177443150515396009051686032203491632226408852488524331580515348496> 224348482993809050704834824493274537326245677558790891871908036620580095947431500524025327097469953187707243768259074199396322659841474981936092852> 239450397071654431564213281576889080587831834049174345562705202235648464951961124602683139709750693826487066132645076650746115126775227486215986425> 307112984411826226610571635150692600298617049454250474913781151541399415506712562711971332527636319396069028956502882686083622410820505624307017949> 76171121233066073310059947366875
>
>
> ? (time (funcall (funcall (%ack) 4) 1))
> (FUNCALL (FUNCALL (%ACK) 4) 1)
> took 12 milliseconds (0.012 seconds) to run.
> During that period, and with 2 available CPU cores,
> 12 milliseconds (0.012 seconds) were spent in user mode
> 0 milliseconds (0.000 seconds) were spent in system mode
> 352 bytes of memory allocated.
> 65533
>
>
> -Taoufik

Recursive functions are slow because of the stack usage (I do not understand what do you
mean by correct use of recursion); your fib function is tail recursive and it is basically a loop,
and it is less clear then the mathematical definition of fibonacci function:
fib(n) = fib(n-2) + fib(n -1)
The orbit is very close to the mathematical definition.

You could easily write an iterative function for fib but try to do it for the ackermann funtion:

A(m,n) =
if m = 0 then n+1
elsif n = 0 then A(m-1,1)
else A(m-1,A(m,n-1))

It is far from easy to write an iterative version

-Taoufik

Pascal J. Bourguignon

8/3/2015 1:54:00 PM

0

Taoufik Dachraoui <dachraoui.taoufik@gmail.com> writes:

> You could easily write an iterative function for fib but try to do it for the ackermann funtion:
>
> A(m,n) =
> if m = 0 then n+1
> elsif n = 0 then A(m-1,1)
> else A(m-1,A(m,n-1))
>
> It is far from easy to write an iterative version

It's a trivial generalization from 1D vectors to 2D matrices.

Alternatively, you can just memoize the function, for the general
generalization to any-dimension spaces.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Kaz Kylheku

8/3/2015 3:01:00 PM

0

On 2015-08-03, Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:
> On Sunday, August 2, 2015 at 5:15:13 PM UTC+1, Taoufik Dachraoui wrote:
>> Hi
>>
>> The macro DEFORBIT (a sequence starting with x0 is called an orbit around x0) is used to define
>> any function that can be expressed as a sequence.
>>
>> (deforbit (foo args (initial-elements form) &key (index (gensym "N"))))
>>
>> For example:
>>
>> ? (deforbit %fact () (((a 1)) (* a n)) :index n)
>> %FACT
>> ? (funcall (%fact) 5)
>> 120
>> ? (deforbit %fib () (((a 0) (b 1)) (+ a b)))
>> %FIB
>> ? (funcall (%fib) 10)
>> 55
>> ? (deforbit %iter (f x) (((a (funcall f x))) (funcall f a)))
>> %ITER
>> ? (deforbit %ack () (((f (lambda (n) (1+ n)))) (%iter f 1)))
>> %ACK
>> ? (funcall (funcall (%ack) 4) 1)
>> 65533
>>
>> The interesting thing is that functions defined using DEFORBIT are iterative and thus much faster
>> than their corresponding recursive definition (the recursive ackermann function on my computer
>> failed to compute (ackermann 4 1) because of stack overflow, and Fibonacci of 10000 run for ever.
>>
>> The following shows how fast it is when using orbits instead of recursive functions:
>>
>> ? (time (funcall (%fib) 10000))
>> (FUNCALL (%FIB) 10000)
>> took 22 milliseconds (0.022 seconds) to run.
>> 2 milliseconds (0.002 seconds, 9.09%) of which was spent in GC.
>> During that period, and with 2 available CPU cores,
>> 19 milliseconds (0.019 seconds) were spent in user mode
>> 3 milliseconds (0.003 seconds) were spent in system mode
>> 4,457,848 bytes of memory allocated.
>> 336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820653326808361593737347904838652682630408924>> 630564318873545443695598274916066020998841839338646527313000888302692356736131351175792974378544137521305205043477016022647583189065278908551543661>> 595829872796829875106312005754287834532155151038708182989697916131278562650331954871402142875326981879620469360978799003509623022910263681314931952>> 756302278376284415403605844025721143349611800230912082870460889239623288354615057765832712525460935911282039252853934346209042452489294039017062338>> 889910858410651831733604374707379085526317643257339937128719375877468974799263058370657428301616374089691784263786242128352581128205163702980893320>> 999057079200643674262023897831114700540749984592503606335609338838319233867830561364353518921332797329081337326426526339897639227234078829281779535>> 805709936910491754708089318410561463223382174656373212482263830921032977016480547262438423748624114530938122065649140327510866433945175121615265453>> 613331113140424368548051067658434935238369596534280717687753283482343455573667197313927462736291082106792807847180353291311767789246590899386354593>> 278945237776744061922403376386740040213303432974969020283281459334188268176838930720036347956231171031012919531697946076327375892535307725523759437>> 884345040677155557790564504430166401194625809722167297586150269684431469520346149322911059706762432685159928347098912847067408620085871350162603120>> 719031720860940812983215810772820763531866246112782455372085323653057759564300725177443150515396009051686032203491632226408852488524331580515348496>> 224348482993809050704834824493274537326245677558790891871908036620580095947431500524025327097469953187707243768259074199396322659841474981936092852>> 239450397071654431564213281576889080587831834049174345562705202235648464951961124602683139709750693826487066132645076650746115126775227486215986425>> 307112984411826226610571635150692600298617049454250474913781151541399415506712562711971332527636319396069028956502882686083622410820505624307017949>> 76171121233066073310059947366875
>>
>>
>> ? (time (funcall (funcall (%ack) 4) 1))
>> (FUNCALL (FUNCALL (%ACK) 4) 1)
>> took 12 milliseconds (0.012 seconds) to run.
>> During that period, and with 2 available CPU cores,
>> 12 milliseconds (0.012 seconds) were spent in user mode
>> 0 milliseconds (0.000 seconds) were spent in system mode
>> 352 bytes of memory allocated.
>> 65533
>>
>>
>> -Taoufik
>
> Recursive functions are slow because of the stack usage (I do not understand what do you
> mean by correct use of recursion); your fib function is tail recursive and it is basically a loop,
> and it is less clear then the mathematical definition of fibonacci function:
> fib(n) = fib(n-2) + fib(n -1)

The above recursive version of the fib function isn't tail recursive. It makes
two calls to itself, which have to return so that it can calculate their sum.

The main problem with the above recursive fib isn't so much the stack usage, as
the overlapping subcases, which make it take exponential time. That bites
even for reasonably small values of n, where stack usage wouldn't be a concern.

Memoization will reduce the problem to merely that of linear stack usage.

If you want a tail-recurive fib, you have to express it differently from the
above. For example, like this:

(defun fib-rec (a b count)
(if (zerop count)
a
(fib-rec b (+ a b) (1- count))))

(defun fib (n)
(fib-rec 1 1 n))

(fib 0) -> 1
(fib 1) -> 1
(fib 2) -> 2
(fib 3) -> 3
(fib 4) -> 5
(fib 5) -> 8
....

> The orbit is very close to the mathematical definition.

Yes, well orbits are evidently based on seuqences which are defined by
*recurrences*. Orbits are close to the recurrences.

We know that we can calculate the elements of a recurrent sequence by
starting with some initial values and applying the recurrence; and
you've come up with a syntactic sugar for specifying the initial
conditions and recurrence in a capsule.

Here is a problem: some recurrences rely on random access into the the entire
preceding sequence, not only on the last handful of elements.
For instance, calculation of some (f n) may rely on (f (floor n 3)).

Taoufik Dachraoui

8/3/2015 3:23:00 PM

0

>It's a trivial generalization from 1D vectors to 2D matrices.

I read an article that proposes an efficient iterative algorithm for ackermann function and it is
not trivial; I would like to see how you do it.

>Alternatively, you can just memoize the function, for the general
>generalization to any-dimension spaces.

I encourage you to write a memoized ackermann function and analyze its space and time
complexity; you will see that writing an efficient iterative ackermann function
is not that easy. How much space does your memoized function use to save already
computed values?

it happens that the orbit for ackermann function has a space complexity O(1)

-Taoufik

Taoufik Dachraoui

8/3/2015 3:44:00 PM

0

>The above recursive version of the fib function isn't tail recursive. It makes
>two calls to itself, which have to return so that it can calculate their sum.

I meant the following Scheme function is tail-recursive:

>>Scheme:
>>
>>(define (fib n)
>> (let go ((a 0) (b 1) (n n))
>> (if (zero? n)
>> a
>> (go b (+ a b) (- n 1)))))

>Memoization will reduce the problem to merely that of linear stack usage.

Memoization is a good solution for fib function (the Scheme iterative function uses
a and b to store previously computed values)

>Yes, well orbits are evidently based on seuqences which are defined by
>*recurrences*. Orbits are close to the recurrences.
>
>We know that we can calculate the elements of a recurrent sequence by
>starting with some initial values and applying the recurrence; and
>you've come up with a syntactic sugar for specifying the initial
>conditions and recurrence in a capsule.

I did not pretend that I invented a new thing, I just wrote a macro to allow
me to define functions based on their recursive equations (ie factorial,
fibonacci, ackermann, ...) and the defined functions are highly space
and time efficient (see ackermann example)

So orbits allows you to define efficient functions that are very close to their
mathematical definitions

>Here is a problem: some recurrences rely on random access into the the entire
>preceding sequence, not only on the last handful of elements.
>For instance, calculation of some (f n) may rely on (f (floor n 3)).

It is clear from the signature of deforbit

-Taoufik

Kaz Kylheku

8/3/2015 5:52:00 PM

0

On 2015-08-03, Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:
>>The above recursive version of the fib function isn't tail recursive. It
>>makes two calls to itself, which have to return so that it can calculate
>>their sum.

The way in which you're following up to articles is broken. Your reply
references your own posting as the parent article, and my quotes appear without
attribution.

> I meant the following Scheme function is tail-recursive:

Yes, unfortunately what you actually *wrote* is that the straight Fibonacci
recurrence fib_k = fib_k-1 + fib_k-2 is tail recursive.

>>>Scheme:
>>>
>>>(define (fib n)
>>> (let go ((a 0) (b 1) (n n))
>>> (if (zero? n)
>>> a
>>> (go b (+ a b) (- n 1)))))

That's a nearly verbatim Scheme transliteration of the Lisp code that I wrote
in the same article you're responding to:

(defun fib-rec (a b count)
(if (zerop count)
a
(fib-rec b (+ a b) (1- count))))

(defun fib (n)
(fib-rec 1 1 n))

>>Memoization will reduce the problem to merely that of linear stack usage.
>
> Memoization is a good solution for fib function

Nobody said it was. I claimed that the straight fib recurrence, if used as a
recursive function, has a more significant resource issue than memory usage.
(And tail recursion doesn't fix it, because it doesn't apply.)

> (the Scheme iterative function uses
> a and b to store previously computed values)

So now you've taken a function that I wrote, trivially transliterated it to
Scheme, and are lecturing me about how it works? Brilliant!

> I did not pretend that I invented a new thing, I just wrote a macro to allow

More precisely, as far as the public is concerned, you wrote a Usenet article
which shows *invocations* of a macro.

As usual, the definition is nowhere to be seen.

Taoufik Dachraoui

8/3/2015 7:53:00 PM

0

TO Kaz: you are misreading the messages, you need to read the messages in the correct order

It was WJ who gave the Scheme code and I said that his function is tail recursive

My intention was not to give you the code of deforbit, but just to show the idea of having such
a macro; I think it is a valuable macro it allows you to define recursive functions close to their
mathematical definition and have an iterative code that is highly efficient (the ackermann function
is a good example).

All the rest of your speech is meaningless and beside the subject (so much mis understanding)

-Taoufik

Kaz Kylheku

8/3/2015 8:58:00 PM

0

On 2015-08-03, Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:
> TO Kaz: you are misreading the messages, you need to read the messages in the correct order
> It was WJ who gave the Scheme code and I said that his function is tail recursive

The entire confusion is caused by you:

- you're replying to yourself (the References: header in your postings refers
to your own earlier article), and
- you're inserting quoting material from other people without attribution.

I didn't see any article by WJ (killfile at work), and your follow up to
yourself makes no indication that you copied anything out of a WJ article.

(I sometimes do see WJ articles. This happens in situations when my newsreader
shows that there are some new articles, but after processing the kill file,
that drops to zero (all killed). When that happens, sometimes I peek at the
suppressed articles. At other times, no.)

Pascal J. Bourguignon

8/3/2015 10:31:00 PM

0

Taoufik Dachraoui <dachraoui.taoufik@gmail.com> writes:

>>It's a trivial generalization from 1D vectors to 2D matrices.
>
> I read an article that proposes an efficient iterative algorithm for ackermann function and it is
> not trivial; I would like to see how you do it.

Well, I didn't say "space-efficient"; the idea is to keep a 2D array of
the previously computed ackermann values.


>>Alternatively, you can just memoize the function, for the general
>>generalization to any-dimension spaces.
>
> I encourage you to write a memoized ackermann function and analyze its space and time
> complexity; you will see that writing an efficient iterative ackermann function
> is not that easy. How much space does your memoized function use to save already
> computed values?

O(n*m)


> it happens that the orbit for ackermann function has a space complexity O(1)

That's interesting.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk