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] What do these errors mean?
Following a clean compile (Under XCode) I get: _main, referenced from: start in crt1.10.6.o [ several dozen similar messages relating to user-defined routines snipped ] fpc_shortstr_to_shortstr, referenced from: [ snip ] ld: symbol(s) not found collect2: ld returned 1 exit status Presumably these are linker messages. Where do I go from here? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Re: fpc-pascal Digest, Vol 72, Issue 35
On 12 Jun 2010, at 11:00, Michael Van Canneyt wrote:
TestFunction := ActualParameter ( ) ; { compiles and runs o.k. }
[MVC:] The addition of () actually calls the function.
TestFunction := ActualParameter ; { gives incompatible type error,
but ... }
[MVC:] Here you try to assign the ActualParameter (a function pointer) to the
result (an integer). This of course gives a type error.
TestFunction := NamedFunction ; { ... compiles and runs o.k. }
[MVC:] This is simply a regular function call.
Sorry, but this simply wrong. The LRG (page 95) does not require an actual
parameter list for a syntactically correct function call.
The call should be excecuted except in one case (LRG page 96) ... the compiler
will not execute the function call ... when assigning a value to a procedural
type variable. This is clearly not such a case.
Roger Bailey
P.S. The LRG has a minor error on page 121: out parameter appears twice as an
alternative for parameter declararion
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Re: Bug?
Sorry, I committed the cardinal sin of getting the subject line wrong.
Corrected now :-)
On 14 Jun 2010, at 18:07, Michael Van Canneyt wrote:
On Mon, 14 Jun 2010, Roger Bailey wrote:
On 12 Jun 2010, at 11:00, Michael Van Canneyt wrote:
TestFunction := ActualParameter ( ) ; { compiles and runs o.k. }
[MVC:] The addition of () actually calls the function.
TestFunction := ActualParameter ; { gives incompatible type error,
but ... }
[MVC:] Here you try to assign the ActualParameter (a function pointer) to
the
result (an integer). This of course gives a type error.
TestFunction := NamedFunction ; { ... compiles and runs o.k. }
[MVC:] This is simply a regular function call.
Sorry, but this simply wrong. The LRG (page 95) does not require an actual
parameter list for a syntactically correct function call.
[MVC:] What is simply wrong ? My explanation or the behaviour of the compiler
?
Sorry. I guess your explanation states what the compiler is doing, so in that
sense your reply isn't simply wrong. However, the program fragment
TestFunction := ActualParameter is a syntactically correct function call as
as defined by the LRG, so the statement Here you try to assign the
ActualParameter (a function pointer) to the result (an integer) is wrong. In
fact I now notice you you give an almost identical example in the LRG (page 96)
Type
FuncType = Function: Integer;
Var A : Integer;
Function AddOne : Integer;
begin
A := A+1;
AddOne := A;
end;
Var F : FuncType;
N : Integer;
begin
A := 0;
F := AddOne; { Assign AddOne to F, Don’t call AddOne}
N := AddOne; { N := 1 !!}
end.
It's clear from this that the meaning of Addone depends on the context, here
the type of the variable on LHS of the assigment. On this basis I think that
the error message I received is either a compiler bug, or FPC implements a
slightly perverse dialect of Pascal (so the LRG is wrong).
Hope this helps,
Roger Bailey___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Bug?
Can someone explain this?
program WhatsGoingOnHere ;
type
FunctionType = function : INTEGER ;
function NamedFunction : INTEGER ;
begin
NamedFunction := 12345 ;
end ;
function TestFunction ( ActualParameter : FunctionType ) : INTEGER ;
begin
TestFunction := ActualParameter ( ) ; { compiles and runs o.k. }
TestFunction := ActualParameter ; { gives incompatible type error,
but ... }
TestFunction := NamedFunction ; { ... compiles and runs o.k. }
end ;
begin
WRITELN ( TestFunction ( NamedFunction ) ) ;
end .
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Re: fpc-pascal Digest, Vol 71, Issue 69
OK, I give up. How do you handle standard input and output files in FPC? When I write something like: nextcharacter := input^ I get error: 1: Illegal qualifier. Does FPC not support this standard Pascal feature? The documentation is extremely unhelpful in this area. The LRG just says The default Input, Output and StdErr file types are defined in the system unit, and the system unit describes a record structure that doesn't seem to contain a field that might be a file buffer. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Re: ISO Standard Pascal I/O
Me: ... nextcharacter := input^ ... Does FPC not support this standard Pascal feature? Jonas: No, it does not. FPC mainly supports Borland-style Pascal dialects, and they are not ISO Standard/Extended Pascal compliant. I can live with that, but it would save newcomers a lot of trouble if the documentation were a bit more upfront about what FPC is not. Just saying it implements some, or most of the features of dialect X is a recipe for frustration. PS: please use a descriptive mail subject in the future. Sorry, netiquette got obscured by red mist :-) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] One small step for Pascalkind ...
... one big step for me. Dear FP Seers -- I'm struggling to port a heap of software written in Think Pascal to Mac OS X, and I'm finding the learning curve for Unix and Xcode extremely steep, with huge quantities of impenetrable documentation for both. I'm sorry to say that some of the FPC documentation errs in this direction too. Is this an appropriate forum for stupid beginners' questions? My immediate problems relate to Xcode, which doesn't really seem know about FPC. Perhaps there's someone on the list I could ask privately so as not to drive you all crazy with elementary questions (I'm on other technical lists, so I know how irritating this can be)? Thanks Roger Bailey___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
