Re: [fpc-pascal] Recursion optimization by compiler
On Sep 2010, at 20:32, José Mejuto wrote: [ some stuff about recursion - at the bottom if you want to read it ] This a misunderstanding of way recursion can be flattened into a loop. It's especially not useful because the transformed version still uses a stack, so it doesn't execute in constant space. Consider the classic factorial function: function fact ( i : integer ) : integer ; begin if i := 0 then fact := 1 else fact := i * fact ( i - 1 ) end ; with initial call fact ( some-value ) For an actual parameter value i this requires O (i) space, because you need to create stack frame to hold the current value of i for use after calculating the value factorial ( i - 1 ) and the return address of the calling routine, (which is actually the same in every stack frame except in the one created by the top-level call). You can see this by writing a top-level-call and plugging in the definition until you hit the base-case: fact ( 4 ) - 4 * fact ( 3 ) - 4 * ( 3 * fact ( 2 ) ) - 4 * ( 3 * ( 2 * fact ( 1 ) ) ) - 4 * ( 3 * ( 2 * ( 1 * fact ( 0 ) ) ) ) - 4 * ( 3 * ( 2 * ( 1 * 1 ) ) ) None of the multiplications can be done until the final call of fact, so all the values must be preserved until then. Now consider this version: function accfact ( f , i : integer ) ; begin if i = 0 then accfact := f else accfact := accfact ( f * i , i - 1 ) end ; with an initial call of accfact ( 1 , some-value ) This is the standard accumulating parameter technique. All the calculation is performed on the descent, no local variables need to be kept, and the return address can simply be the point following the top-level call. The new stackframe can overwrite the old one (or rather the new values for the actual parameters f and i can simply overwrite the old ones). If you the previous trick of plugging the definition into a top-level call you immediately get: accfact ( 1 , 4 ) - accfact ( 1 * 4 , 3 ) and we can do the multiplication before making the recursive call. This is tail recursion. For trees it's a lot trickier to write the processing routines in this kind of tail-recursive form. Suppose we have a data type tree that can be empty or hold a value (say an integer) plus two subtrees, either of which may of course be empty at any level. Without getting into the minutiae of data representation and pointer-twiddling, assume functions value, left and right to return the value and the two subtrees respectively, and isempty to check if a tree is empty. The obvious way to process all the integers in such a tree (perhaps by forming their sum) is: function sum ( t : tree ) : integer ; begin if isempty ( t ) then sum := 0 else sum := value ( t ) + sum ( left ( t ) ) + sum ( right ( t ) ) end ; For a tree with n nodes this executes in O (n) space. The accumulating parameter version is a bit less intuitive than accfact: function accsum ( s : integer ; t : tree ) : integer ; begin if isempty ( t ) then accsum : = s else accsum := accsum ( accsum ( s + value ( t ) , left ( t ) ) , right ( t ) ) end ; with top-level call accsum ( 0 , some-tree ) Here we have double recursion, which for a tree of maximum depth d it can be executed in O (d) space. For a balanced tree of n nodes, this means O(log(n)) space, which is still a huge improvement on the original version. The key to making this work invisibly is provide higher-order functions to hide the recursion. If necessary they can be hand-coded in assembler and the compiler need never do any optimisation. i.e given a type munge = function ( a , b : some-type ) : some-type we define: function mungetree ( b : some-type ; m : munge ; t : tree-containing-some-type-values ) : some-type ; begin if isempty ( t ) then mungetree : = b else mungetree := mungetree ( mungetree ( munge ( s , value ( t ) ) , left ( t ) ) , right ( t ) ) end ; and depending on what some-type is, and the actual function we supply for m (with of course an appropriate base-case value for b) we can traverse any tree in O(log(n)) space, irrespective of the type of values in the tree or the type of operation performed on them. Or we could if Pascal had a proper polymorphic type system. But it ain't, it's too old-fashioned. On 3 Sep 2010, at 20:32, fpc-pascal-requ...@lists.freepascal.org wrote: From: Jos? Mejuto joshy...@gmail.com Subject: Re: [fpc-pascal] Recursion optimization by compiler To: FPC-Pascal users discussions fpc-pascal@lists.freepascal.org Message-ID: 166212194.20100903141...@gmail.com Content-Type: text/plain; charset=ISO-8859-15 Hello FPC-Pascal, Friday, September 3, 2010, 1:12:31 PM, you wrote: BA After my previous post, TreeView and Nonrecursion, I'd tried to ask the same BA topics in stackoverflow.com BA (http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion) BA and I got something new. BA It is possible to recurse without using up the stack space. Optimizing BA compilers are able to
[fpc-pascal] ARM STM32F Processor
Is it possible to compile for this device? Can somebody help? I want to switch from Atmel (8bit) to ARM. I Also need hardware demo board, if someone has an example. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] ARM-Cortex port
Den 26-08-2010 18:20, Geoffrey Barton skrev: On 24 Aug 2010, at 21:52, Florian Klaempfl wrote: Am 24.08.2010 11:53, schrieb Geoffrey Barton: using Jonas and Jeppe's answers to my idiot questions in this forum, and Jeppe's startup code for the STM32F, I have FPC cross-compiling for the LM3S9B92, one of the TI Luminary processors. If you've any reusable startup code, we would be happy to include it in official fpc. certainly! where do you want it? Geoffrey ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal Supplying a patch on the bug tracker would probably be the best way ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] ARM STM32F Processor
Den 04-09-2010 10:50, Rainer Stratmann skrev: Is it possible to compile for this device? Yes Can somebody help? Yes I want to switch from Atmel (8bit) to ARM. I Also need hardware demo board, if someone has an example. I have a small guide here: http://j-software.dk/stm32f103.aspx I think this looks like a nice board: http://www.futurlec.com/STM32_Development_Board.shtml Both well featured and cheap :) I have this board: http://www.futurlec.com/ET-STM32_Stamp.shtml It has no features except for a serial port, but it's cheap There are still a few things missing in the rtl, before you can use interrupts, but principally most should be doable with FPC ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] ARM STM32F Processor
Am Saturday 04 September 2010 11:57:25 schrieb Jeppe Johansen: Den 04-09-2010 10:50, Rainer Stratmann skrev: Is it possible to compile for this device? Yes Can somebody help? Yes I want to switch from Atmel (8bit) to ARM. I Also need hardware demo board, if someone has an example. I have a small guide here: http://j-software.dk/stm32f103.aspx I think this looks like a nice board: http://www.futurlec.com/STM32_Development_Board.shtml Both well featured and cheap :) I have this board: http://www.futurlec.com/ET-STM32_Stamp.shtml It has no features except for a serial port, but it's cheap There are still a few things missing in the rtl, before you can use interrupts, but principally most should be doable with FPC What does that mean exactly? Is it possible to deal with interrupts? The FPC program is simply transfered to the controller by uploading with its usart interface? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] ARM STM32F Processor
Den 04-09-2010 12:37, Rainer Stratmann skrev: Am Saturday 04 September 2010 11:57:25 schrieb Jeppe Johansen: Den 04-09-2010 10:50, Rainer Stratmann skrev: Is it possible to compile for this device? Yes Can somebody help? Yes I want to switch from Atmel (8bit) to ARM. I Also need hardware demo board, if someone has an example. I have a small guide here: http://j-software.dk/stm32f103.aspx I think this looks like a nice board: http://www.futurlec.com/STM32_Development_Board.shtml Both well featured and cheap :) I have this board: http://www.futurlec.com/ET-STM32_Stamp.shtml It has no features except for a serial port, but it's cheap There are still a few things missing in the rtl, before you can use interrupts, but principally most should be doable with FPC What does that mean exactly? Is it possible to deal with interrupts? The FPC program is simply transfered to the controller by uploading with its usart interface? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal I don't know if it's directly possible to use interrupts, but I would guess it is The FPC program is compiled just like a C program. The resulting hex file is then burned to the flash, either using JTAG, or a bootloader via usart. STM32F103 comes with a bootloader from the factory ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
Am 03.09.2010 21:31, schrieb Sven Barth: On 03.09.2010 18:02, Marco van de Voort wrote: Second, does FPC understand tail recursion? Depends on version, do fpc -i |grep -i tailrec to find out more. O.o Ok... now I'm officially impressed. Well, simple to implement and useless optimization :) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
On 28.08.2010 11:57, Florian Klämpfl wrote: Am 03.09.2010 21:31, schrieb Sven Barth: On 03.09.2010 18:02, Marco van de Voort wrote: Second, does FPC understand tail recursion? Depends on version, do fpc -i |grep -i tailrec to find out more. O.o Ok... now I'm officially impressed. Well, simple to implement and useless optimization :) But it's nice to have. In the lecture Introduction of Computer Science 2 we had to learn functional programming with the programming language OCaml. There we used tail recursion a lot (and I always tried to write my functions in a tail recursive form) and it's nice to see/know that FPC can do that as well. :) Btw: is this a CPU dependent optimization? Regards, Sven ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re[2]: [fpc-pascal] Recursion optimization by compiler
Hello FPC-Pascal, Saturday, September 4, 2010, 9:07:57 AM, you wrote: RB This a misunderstanding of way recursion can be flattened RB into a loop. It's especially not useful because the transformed RB version still uses a stack, so it doesn't execute in constant RB space. I know, but as far as I know it is the only way to get exactly the same functionality whichever the recursion function works (using a stack different than the default stack). If the recursion function is not the last function it can not be optimized in such way, moreover most of that tail recursive functions are easy to be rewritten as a while end loop. Anyway I do not have any kind of degree in computer science or alike so I could be completly wrong :) -- Best regards, José ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] ARM-Cortex port
Am 26.08.2010 18:20, schrieb Geoffrey Barton: On 24 Aug 2010, at 21:52, Florian Klaempfl wrote: Am 24.08.2010 11:53, schrieb Geoffrey Barton: using Jonas and Jeppe's answers to my idiot questions in this forum, and Jeppe's startup code for the STM32F, I have FPC cross-compiling for the LM3S9B92, one of the TI Luminary processors. If you've any reusable startup code, we would be happy to include it in official fpc. certainly! where do you want it? Just email it to me or create a bug report and attach it. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
Am 04.09.2010 15:08, schrieb Sven Barth: On 28.08.2010 11:57, Florian Klämpfl wrote: Am 03.09.2010 21:31, schrieb Sven Barth: On 03.09.2010 18:02, Marco van de Voort wrote: Second, does FPC understand tail recursion? Depends on version, do fpc -i |grep -i tailrec to find out more. O.o Ok... now I'm officially impressed. Well, simple to implement and useless optimization :) But it's nice to have. In the lecture Introduction of Computer Science 2 we had to learn functional programming with the programming language OCaml. There we used tail recursion a lot (and I always tried to write my functions in a tail recursive form) and it's nice to see/know that FPC can do that as well. :) IIRC in the whole FPC source tree are two cases where this optimization is applied :) Btw: is this a CPU dependent optimization? No. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
