Difference between revisions of "DIP55"

From D Wiki
Jump to: navigation, search
(Intentionally deal with the stack)
 
(One intermediate revision by the same user not shown)
Line 478: Line 478:
 
See e.g. [https://github.com/FBergemann/ASF-RBT/tree/for_delete ASF RBT] Red/Black-Tree algorithm using this programming model w/o need for a parent ptr in the node structure.   
 
See e.g. [https://github.com/FBergemann/ASF-RBT/tree/for_delete ASF RBT] Red/Black-Tree algorithm using this programming model w/o need for a parent ptr in the node structure.   
  
<span style="color:red">(However, it is incomplete. The delete operation is yet missing, but will be added pretty soon.)</span>
+
<span style="color:red">(Initial version including delete operation now available - but it has to be tested, documented, cleaned-up.)</span>
  
 
Another example is a "recursion tracker" to generate stack level information without adding and removing again recursion level information to a dedicated storage for "printout of position of recursion" in case of errors (e.g. for boost::serialization in the c++ world).
 
Another example is a "recursion tracker" to generate stack level information without adding and removing again recursion level information to a dedicated storage for "printout of position of recursion" in case of errors (e.g. for boost::serialization in the c++ world).
Line 494: Line 494:
 
How can we memorize such? <br>
 
How can we memorize such? <br>
 
Can i exessively use the stack? (stack instead of heap?) <br>
 
Can i exessively use the stack? (stack instead of heap?) <br>
Or do we need stack objects? (from the heap?)
+
Or do we need supporting "stack objects"? (from the heap?)
  
 
== Rationale ==
 
== Rationale ==

Latest revision as of 14:27, 15 June 2016

Title: Access Data Items In Ancestor Stack Frames
DIP: 55
Version: 2
Status: Draft (under construction)
Created: 2014-01-01
Last Modified: 2016-05-03
Author: Frank Bergemann
Links: Dr.Dobb's Article Access Data Items In Ancestor Stack Frames Safely

NG discussion for C++

ASF RBT Red/Black-Tree algorithm using this programming model w/o need for a parent ptr in the node structure.

Abstract

The language should support an implicit *caller pointer for functions (callee) for access to the calling function (caller).

As if functions would internally be modelled as class wrappers (functors) passing their *this ptr implicitly to a called function.

(Likely this behavior is switched on/off, auto-detected by making use of the *caller ptr in a called function yes/no.)

Rationale

callee pulls data specificially when/if required instead of caller pushs all always

This might be a performance improvement.

void f1(void)
{
   SomeType x;
   SomeType y;
   SomeType z;
   [...]
   f2();
   [...]
}

void f2(void)
{
   if (caller->x.IsValid())
   {
      use(caller->y)
   }
   else 
   {
      use(caller->z);
   }
}

public, private (protected?) caller data

Like for data members for classes, local variables of functions might be declared private, public (protected?) for access limitations

void f1(void)
{
private:
   int _x;
   int _y;
public:
   int z;
   [...]
   f2();
   [...]
}

void f2(void)
{
private: 
   int _a1 = caller->_x * 2.0; // ERROR!
   int _a2 = caller->z * 2.0;  // OK
   [...]
}

non-const for the caller, const for the callee

void f1(void)
{
private:
   int _x;
   int _y;
public:
   const int & x = _x;
   const int & y = _y;
   [...]
   f2();
   [...]
}

void f2(void)
{
private: 
   caller->x *=  2.0;        // ERROR!
   int x2 = caller->x * 2.0; // OK
   [...]
}

BTW, here the caller decides about constness for what he provides - not the callee.

public, private (protected?) local functions

Such might serve as getter or setters with similar benefits we have for accessing class data.

void f1(void)
{
private:
   SomeProtoType _x;
public:
   SomeType GetX()(void)
   {
      return SomeType(_x);
   }

   [...]
   f2();
   [...]
}

void f2(void)
{
   if (whatsoever())
   {
      DoIt(caller->GetX());
   }
}

E.g....

Lazy evaluation

Data could be prepared only by caller for callee. But it could be up to the callee to decide if it actually wants that data and for this delay its calculation.

void f1(void)
{
   SomeType x;
   SomeType y;
   SomeType z;
   [...]
   f2();
   [...]
}

void f2(void)
{
   if (caller->x.IsValid())
   {
      caller->y.ExpensivePreProcess();
      use(caller->y);
   }
   else 
   {
      caller->z.ExpensivePreProcess();
      use(caller->z);
   }
}

Multi-level

void f1(void)
{
public:
   RootData rootData;
private:
   [...]
   f2();
   [...]
}

void f2(void)
{
public:
   SomeData x;
   SomeData y;
   SomeData z;

   f3();
}

void f3(void)
{
   if (caller->x.IsValid())
   {
      use(caller->caller->rootData, caller->y)
   }
   else 
   {
      use(caller->caller->rootData, caller->z)
   }
}

plus a *callscope ptr?

caller->caller->x has a flaw: We need to know about the call hierarchy (levels - is it #1 level up or #2 levels up?).

Can't we have something like callscope->x which check for the closest x in ancestor stack frames?

This would be compatible with existing definitions for shadowing:

void funcA(...)
{
   int x = 1;

   funcB(x); // x is #1
}

void funcB(...)
{
   // funcB body
}


void funcA(...)
{
   int x = 1;

   {
      int x = 2;
      funcB(x); // x is #2
   }
}

void funcB(...)
{
   // funcB body
}

unrolled:

void funcA(...)
{
   int x = 1;

   {
      int x = 2;
      {
         // funcB body // x is #2
      }
   }
}

The latter (unrolled) reveals that this CR moves functions a bit closer to local scopes. Because the access to "surrounding data" is similar.

Functionally a current stack image having *caller / *callscope ptr is equivalent with nested scopes.

Cons

caller has to adhere to callee's naming

For passing data as function arguments, the function can choose any name w/o dependency to the caller. The caller just provides the values (but has to follow a sequence).

However, when the called function tries to use some caller->x, it expects the caller to provide some 'x'.

On the other side: if using named parameters, the caller also has be aware of the callee's naming conventions.

But for this the caller still can decide for the function call invocation which value to pass as 'x => someVal'. But does not have to set a variable (pointer, reference), which does this.

Description

Dependency and Hierarchy

Function A is calling function B.

Usually A has more domain knowledge. And B is a less informed service for A.

But can't B have more limited, but more precise information about a certain issue?

Could that be a reason, to turn B from a stupid service into an user (or even instructor) for A?

It's not good or bad design to let B directly manipulate A.

There are some cases, where this is applicable. E.g.:

1. traversing a tree structure invoking functions along the paths', evaluating detailed information way down to the leaves, but consolidating results into a shared root data structure.

2. building up a stack by recursions to calculate a result, finally save the result at the root position.

Problem How should the compiler know where to store at root for #x dynamic recursive invocations when we try to update callscope->x?

Answer The data objects to access exist. All we need is a dynamic type-specific list of pointers for public data. It's actually vtable-alike for data (names).

For public local functions along the call stack it's even more like a vtable.

Usage

STILL TEMPLATE CONTENT ONLY HERE

This section has been adapted for MediaWiki.

To start a new DIP you can go to Edit link and copy the source of this DIP, then go to DIP index and add a new item in the list. The DIP number should be one more than the last DIP in the index (for example, if the DIP1 is the last DIP, your DIP should be DIP2). The link in the index should have the form: [[DIPx]], Title, Status, resume. Where x is the DIP number, title is the DIP title and resume is a short description about the DIP.

Save the DIP index page and click on the new red link. Now you are editing the new DIP you just created, now paste the copied source text from this template and replace all the you need.

Remember to update the metadata at the start of the DIP, and keep it as a Draft at the beginning. When your DIP is done, you should announce it in the News Group for discussion, with a subject like this: new DIPx: title (where one more time x is the DIP number and title is the DIP title).

You should always put you DIPs in the Public Domain (or a similarly permissive license but use Public Domain unless you're very sure of what you're doing).

Recommendations

STILL TEMPLATE CONTENT ONLY HERE

When writing a DIP, try not to express your opinion. DIPs should provide facts and be as objective as possible. Even when that's pretty hard, you can make the DIP look more objective by not using, for example, "I prefer XXX because YYY". If YYY is an objective advantage, write that in a more objective way, like "XXX can be a better option because YYY". Try to leave non-technical personal preferences aside; "XXX can be a better option because the syntax is nicer" is not good enough even when you don't say "I prefer".

Try not to include half-baked ideas. If you are not sure about something, leave it outside the DIP and write it on the NG announcement instead for further discussion. The idea can be added to the DIP in the future when it is in a better shape.

Abstract

What's good for classes is good for functions

This CR enables features used for classes (structural) to functions/procedures (procedural).

Bypassing data

As it shares a context (data) along a call hierarchy it can be considered a "better version of global variables" - because it is limited to the execution scope (call hierarchy).

How many times you've been bothered to pass some value along a call hierarchy to reach a target function?

Now you can tunnel it.

void FuncA(...)
{
   SomeType transactionId;

   FuncB(...); // NOT including transactionId
}

void FuncB(...)
{
   // not using FuncA's transactionId;
   FuncC(...); 
}

void FuncC(...)
{
   Log(callscope->transactionId, "my message");
}

But don't stress this option - don't end up in a BLOB stack.

For the example above: you need some logging function - even don't want to know requirement to use transactionId for logging?

void FuncA(...)
{
   SomeType transactionId;

   void Log(...)
   {
     writeln(transactionId):
     foreach (arg; _arguments)
     {
	[...]
     }
   }

   void FuncB(...); // NOT including transactionId
}

void FuncB(...)
{
   // not using FuncA's transactionId;
   FuncC(...); 
}

void FuncC(...)
{
   callscope->Log("my message");
}

Closure

sorry for c++ here

void MyFunction(int x);

void FuncA(void)
{
   std::vector<int> myvector;
   myvector.push_back(10);
   myvector.push_back(20);
   myvector.push_back(30);

   {
      int x = 1;
      int y = 2;
      std::for_each (myvector.begin(), myvector.end(), MyFunction);
   }
}

void MyFunction(int x)
{
   // do whatever you like using...
   caller->x
   caller->y
}

std::for_each uses the function argument interface.

But the user can define a context for the *caller interface.

Compositions via the stack

Inheritance is used to model basic features in base classes and to specialize or to add extension in derived classes.

This is done by design before/at compile time.

Turning functions into some class-alike for this CR provides inheritance-alike options along the stack.

An initial function FuncA(...) can hold a base definition (data, nested functions). And invoking a next FuncB(...) can add extensions.

At FuncX(...) some desired context is reached.

Note: such shall not replace class design, it's just a different tool.

In contrast to a structural class, using a stack of functions is not durable, but rather temporary (for now). But usable for a singleton-alike work-horse (processor).

But in contrast to classes, such context can be composed dynamically (at runtime). And it can be composed limited to the current needs. E.g. a base functionality can be completed with an import interface at one time, and later the import interface can be dropped and an export interface can be added.

Video Inheritance is the base class of Evil might address the same (or a similar) issue (i am not sure).

who's client, who's server?

(1) Function A invokes function B using B's function arguments.

(2) Function B uses caller->x, i.e. x of A.

Both are interfaces.

(1) is the "normal" API interface we use every day.

(2) is a kind of callback.

Considering

o) A being modelled as a class wrapper for a function and

o) B defining what is uses from A

...A has to inherit from a callback user interface of B.

So we have a mutual client/server relationship.

Intentionally deal with the stack

It offers a toolbox to make better use of a stack.

It adds a stack-machine user interface for the programmer (usable for compilers?).

E.g. for traversing trees the stack can be better incorporated into the algorithm implementation. A parent/child relationship is supported by a caller/called model.

See e.g. ASF RBT Red/Black-Tree algorithm using this programming model w/o need for a parent ptr in the node structure.

(Initial version including delete operation now available - but it has to be tested, documented, cleaned-up.)

Another example is a "recursion tracker" to generate stack level information without adding and removing again recursion level information to a dedicated storage for "printout of position of recursion" in case of errors (e.g. for boost::serialization in the c++ world).

(Another demo will be provided for that.)

A bridge between object oriented programming and functional programming

(more dynamic objects)
Imagine, you have a function, that holds data members.
This function can be extended stack-wise by calling other functions.
By this it can temporary grow, then shrink and grow again in a different direction (you can't do with classes).
But we want an unlimited number of instances of such new kind of objects.
How can we model those with functions?
Presume setup-data are given to functions, driving their members and other functions they call.
How can we memorize such?
Can i exessively use the stack? (stack instead of heap?)
Or do we need supporting "stack objects"? (from the heap?)

Rationale

STILL TEMPLATE CONTENT ONLY HERE

Rationale should be complete. When the DIP tries to solve a problem, try to describe that problem as detailed as possible. If you have links to the NG describing the problem more deeply, used them. All the background information is welcome.

NG Announcement

STILL TEMPLATE CONTENT ONLY HERE

When posting the DIP announcement to the NG, please copy the abstract, so people can easily know what is it about and follow the link if they are interested.

Copyright

This document has been placed in the Public Domain.