Hi,
I know that for recursive subprograms, each call usually use space on the stack for its own context and local variable, and they add up, while in the iterative version you typically recycle the same variables.
However, in this case there are no locally declared variable:
FUNCTION Copy(L: IN List) RETURN List IS ((if L = null then null else Copy (NEW ListNode’(L.ALL.Word, Copy(L.ALL.Next)))));
So I’m quite curious, I assume by default the value of the formal parameter L is copied in the context of each call. But not if said parameter is of a limited/tagged type. Is it possible to force this in order to make recursive implementations more efficient ? Do some specific optimizations exist, if so are there requirements to keep in mind to benefit from them ?
Ok, so, in Ada’s original design the how of parameter-passing is an implementation-detail, with the usage being what is specified via the modes: in, out, in out. — Typically, you’re best off not caring about the details and concentrating on the subprogram-proper.
The question of “how do I force X detail to ‘make it more efficient’?” (i.e. micro-optimization) is widely used in C/C++–land and is an exercise in foolishness: a seemingly trivial change in the rest of the compiler can completely invalidate what you were relying on to “be more efficient”.
There are points where optimizing is appropriate, but this is typically in the realm of what algorithm is being used. Things like parameter-passing should typically only be investigated after (a) profiling, (b) isolating hot-spots, and (c) using a & b to see what the time-drain is — if you haven’t even profiled, you’re almost certainly looking in the wrong spot.
Now, there are methods for recursion that does alleviate stack pressure; one is the usage of an implementation-detail/-optimization of “tail-call optimization”. This is, of course, an implementation detail. The two ways that I know of for addressing this in user-code are using parameters/generic-contexts to hold the state, and trampolines. (This article goes over trampolines, and even shows Ada.)
TL;DR — Make sure that you actually need to “complexify” straightforward code before you begin ‘optimizing’.
ohhh interesting ! Thanks you !
No of course I don’t need to bother with this right now, unless I get to hammer good habits for later at a low effort cost.
I never considered that generic formal parameters were treated like globals of an anonymous package the procedure would be in. So elegant.
If you want to reinitialize the subprogram, without instantiating the generic again, you can set the formal object in out even if you don’t modify its value within the generic, for then it must be passed by reference. This is exactly the kind of method I was looking for.
Interestingly enough, the trampoline technique looks like a low level state machine where instead of using enumerations for the states, you use the subprogram access values.
So to sum up what I tried, as far as language constructs go, with generics:
→ to avoid copies for parameters that stay constant between successive recursive calls, use an in formal objects
→ to get recyclable temporary variables (as if using a library-level global), use in out generic objects.
→ Lastly, formal objects with a default, either a variable or value, can be shared between generic instances.
For the trampoline, so it solves the issue by making recursive calls not recursive ?
I think you might be getting ahead of yourself on details.
Take a step back and think in terms of types and how they’re going to be used in your codebase.
So, let’s say that you need some sort of list (since that was mentioned). But are these lists going to change frequently? If they aren’t going to be mutated much, maybe under-the-hood using an array is appropriate. If there’s going to be a lot of adding/subtracting elements, maybe under-the-hood using Ada.Containers.Indefinite_Vectors.
To put it simply, try looking from the outside first:
Generic
Type Element is private;
Package Example is
Type Element_Vector is Array(Positive range <>) of Element;
-- Limited Private + indefinite to force use of function MAKE.
Type List(<>) is limited private;
Function Make( Input : Element_Vector ) return List;
Function "-"(Object : List) return Element_Vector;
Function First(Object : List) return Element;
Function Last(Object : List) return Element;
-- Other interfacing subprograms.
Private
-- Actual implementation.
End Example;
This is, of course, a step abstracted from just directly implementing your list-of-integer (e.g.) that you’re really going to be using, but the principle is the same: look at how you’re going to use your data-type, and let that guide your implementation. Just like how you use the type-system to model your problem, allowing the actual solution to be in its own terms, rather than forcing everything into the model of the architecture-details like C/C++ encourage.
(This is to say, consider Ada’s Type Percent is range 0..100; vs C’s “just use char”; expand that idea into how you’re using the type.)
Elementary types (scalar and access types) are passed by copy, unless the mode is aliased. Tagged and limited types, and parameters with mode aliased, are passed by reference. All other types and modes are passed using an implementation-chosen mechanism.
In Ada 83, there were three parameter modes: in, in out, and out. Elementary types (scalar and access types) were always passed by copy, regardless of mode; other types used an implementation-chosen mechanism.
A generic formal object of mode in out is equivalent to a renaming of the actual object. See ARM 12.4(1.b), (7), and (10/2).
Trampolines, IIUC, are a mechanism for passing subprograms as parameters, unrelated to recursion. Tail-recursion optimization implements a tail-recursive call using iteration.
Also any composite type with a sub component that falls into those categories is passed by reference, even if the composite type itself is not otherwise by reference. Full list from the RM:
4 A type is a by-reference type if it is a descendant of one
of the following:
5 * a tagged type;
6 * a task or protected type;
7/3 * an explicitly limited record type;
8 * a composite type with a subcomponent of a by-reference type;
9 * a private type whose full type is a by-reference type.
10/5 A parameter of a by-reference type is passed by reference, as
is an explicitly aliased parameter of any type.
Yes, that was a nod toward the “efficient implementation” design-goal, but if you look at the rationale+standard, it’s obvious that the “big idea” there [WRT parameters] was in describing the “how” of the usage, not the “how” of the mechanism.
Yep, I tend to think of this as capturing/binding a [variable] context.
Generic formal in out parameters are perhaps a bit underused, IMO.
Well they’re useful for generic packages, but less so with generic subprograms. Was still when functions didn’t in out parameters but now ? Since these objects are always dynamic, I can’t see what they bring that parameters and a wrapper subprogram won’t, without the need to instanciate when changing the object.
procedure Wrapper (A: in out Integer) is
procedure Recurse return Integer is (do_something_with_A_with_recursion);
begin
Recurse;
end Wrapper;
“Reading between the lines”, it seems to me that it was to try to “micro-optimize” the efficiency part of Ada’s design-goals —Ref: Ada was designed with three overriding concerns: program reliability and maintenance, programming as a human activity, and efficiency. (83 LRM) / 2005 LRM— which actually ties into this thread rather nicely: such micro-optimizations are often less useful than they appear, and even are for a given context. Consider the move to parallelism and multi-core: with sequential/single-core machines, it is really efficient to have an accumulator, but in the context of ‘parallel’ an accumulator hoses all hope of efficiency: see this video. (Precisely because an accumulator’s particular state depends on its previous state, which forces sequentiality.)
Presuming that an elementary type is never larger than an address? In the 20th century I used compilers for 16-bit machines that allowed 32-bit integers, so that an address was smaller than than a 32-bit integer, and current GNAT for 64-bit machines allows 128-bit integers, so that an address is smaller than a 128-bit integer. And since FPUs became common in the 1990s, 64-bit floating point numbers have existed on 32-bit machines (and often 80-bit numbers on 64-bit machines). So that never really was the case.
Or is there another micro-optimization that you’re referring to?
Flip it around: the presumption that compiler makers would choose a different option than by-copy parameters [typically by-reference; though by-name is… interesting]. — Specifying the results of a construct instead of the details is how Ada’s standard typically is, but with this it’s an odd departure. (And this specification bleeds into OOP, where all tagged-types are passed by-reference, even when they could be by-copy.)