Rationale Behind C++ Commandments (4) – Method Signature System

Function signature system, which allows users to use the same function name in different functions as long as they differ in the combination of

  • input arguments types
  • const modifiers counts as a different input argument type
  • object const-ness (whether it’s const-method or not) – this only make sense with classes

and C++ will figure out what to call by matching the call with the available combinations (signatures).

C does not allow the same function name to be used in different places, so under the hood, it’s done through name mangling (generating a unique ‘under-the-hood’ function name based on the signature). This mechanism has a lot of implications that a professional programmer should observe:

  • since C does not mangle its names in the object code, they’ll need to be wrapped around with extern “C” block in a C++ program so C++ won’t pervert (mangle) their function names with input arguments.
  • [24] parameter defaulting might be ambiguous with another function that does not have the said parameter (the compiler will cry about it)
  • [26] access controls/levels must play no part in resolving signatures because access level must not change the meaning of a program!

C++ resolve function overloading using signatures within its local namespace. Function overloading works for both

  • free functions (free functions are at the root namespace), as well as
  • classes (the name of the class itself is the namespace)

 9 total views,  1 views today

Rationale Behind C++ Commandments (3) – Classes came from emulating POD data types through struct and namespaces

In structured programming (like C and C++), the building abstractions is program (functions) and data (variables).

Under the hood, especially in von-Neumann architecture’s perspective, functions and variables are both just data (a stream of numbers) that can be moved and manipulated the same way just like data. It’s all up to how the program designer and the hardware choose to give meaning to the bit stream.


Namespaces

In C, we can only scope our variables 3 ways: global, static (stays within same file/translation unit) and local. Sharing variables across functions in different translation units can only be done through

  • globals (pollutes namespace and it’s difficult to keep track of who is doing what to the variables and the state at any time)
  • passing (the more solid way that gives tighter control and clearer data flow, but managing how to pass many variables in many places is messy, even with struct syntax)

Bundling program with data gives a new way to tightly control the scope of variables: you can specify a group functions allowed to share the same set of variables in the bundle WITHOUT PASSING arguments.

The toolchain modified to recognize the user-defined scope boundaries which bundles program and data into packages, thus reducing root namespace pollution. The is implemented as namespace keyword in C++

Organizing with namespaces is basically justifying the mentality of using globals (in place of passing variables around intended functions) except it’s in a more controlled manner to keep the damages at bay. The same nasty things with gloabls can still appear if we didn’t design the namespace boundaries tightly so certain functions have access to variables that’s not intended for it.

Therefore, namespaces works nearly identical to a super-simple purely static class (see below) except you lose inheritance and access modifiers in classes in exchange for allowing anonymous namespaces.

Basically namespaces + structs + inheritance + encapsulation (access modifiers) = classes


Classes

Classes extends the idea of namespaces by allowing objects (each assigned their own storage space for the variables following the same variable layout) to be instantiated, so they behave like POD (Plain Old Data) in C. We should observe that when overloading operators

  • [15] allow (a=b)=c chaining by returning *this for operator=
  • [21] disallow rvalue assignment (a+b)=c by returning const object

In the most primitive form (no dynamic binding and types, aka virtuals and RTTI), function (method) info is not stored within instantiated objects as the compiler will sort out what classes/namespace they belong to. So it screams struct in C!

C struct is what makes (instantiates) objects from classes!

Note that C structs do not allow ‘static fields’ because static members is solely a construct of namespaces idea in C++! C++ has chosen to expand structs to be synonymous to classes that defaults to private access (if not specified) so code written as C structs behaves as expected in C++.

 9 total views

‘Static classes’ are unlike instantiable (object-bearing) classes in many ways

Technically there’s no static class in C, but a class with all members and functions declared static.

Static classes are like namespaces in many ways. Because no object is constructed (it’s just holding a bunch of variables and functions in the free space), a lot of features and syntax with regular classes do not make sense with static classes.

Because no objects are instantiated

  • No constructors or destructors (no objects to make/destroy)
  • No operator overloading (you need an instantiation to pass arguments to operator methods)
  • No overriding because there are no objects for you to upcast
    (nor there’s an object to store the vtable from the virtual keyword)!

Static members and methods are treated as free objects scoped by namespaces

  • Like C, static members variables live in .bss (not explicitly initialized ones will be zero-initialized) or .data (initialized) sections, not on stack/heap!
    Exception: static const int is internally seen as enum, which the compiler uses it to plug values in the code instead of allocating space for it.
  • Therefore the syntax is pretty much like free static/global variables
  • No constructor to build member variables within the class definition, so they must be defined OUTSIDE the class definition at the top level (just like static/globals), with a SRO (scope resolution operator).
  • Static methods acts like (and function overloads the same way as) free functions.
    That’s why we often use static methods for helpers.

Namespaces has no access modifiers (public/protected/private/friend), but in return only namespaces can be unnamed/anonymous (which behaves as private)!

Namespaces cannot be inherited, but static classes can!

  • Inherited members ARE REFERENCES to the parent!
    There’s no extra copies of underlying data if that member is successfully inherited (not shadowed)!
  • Members (function or variables) can only be shadowed in the child (never overridden since it’s not an object), which creates a NEW stack variable and hid the reference to the parent member

Static class’s inheritance behavior is the same across static classes object-bearing classes! It’s actually more explicit with static members as you’ll need two declarations outside the classes if you shadow.

I am pointing this out to show that inheriting static classes IS NOT cloning namespaces! Static classes behaves as if it’s just ONE CHILD object created on the .bss/.data section (the section for static variables).

This means unlike object-bearing classes, the static class Parent cannot exist on its own if its children are defined!

C++ rules are almost always sensible and coherent; but when combined, sometimes the implications could be surprising on the first sight! When we try to extrapolate expected behaviors in C++, very often we have to think not in terms of the convenient syntax, but the implications of its ground rules (a lot of them stems from C)!

 19 total views,  1 views today

Rationale Behind C++ Commandments (2) – Philosophy of C

Everything is seen as a bitstream

  • pointers are just integers to memory locations
    – [25] integer and pointers might be indistinguishable in signature resolution
  • code (CPU instructions) and addresses are treated the same way as a stream of data
    – concept of function pointers leads to lambda (functors)
    – classes came from structs containing data and function pointers (combined with namespaces)!
  • unchecked type declarations: the compiler trusts your interpretations of data
    – leads to run-time features such as overriding (virtual methods)
  • handles (pointers and references) has unrestricted power
    – [29] can const_cast it away if the handle is exposed (bad idea)

Performance-first design choice

  • do not pay performance penalty for features not used
    – static compilation and binding by default
    – unchecked type declarations (see above)
  • static compilation: the compiler tries to know everything at compile time
  • static binding by default (cheapest)
    – pay extra to use virtual methods (overriding)
    – [38] default parameter values are statically bound and not stored in vtable (i.e. overridden child method’s default values are ignored and parent’s default values are used ONLY WHEN called through up-casts)
  • inline is at the mercy of the optimizer (which can choose to emit an object if decided inlining is counter-productive). Mechanism that forces a function pointer to exist (pointing the function, virtual functions creates the pointer in vtable)

Toolchain

  1. preprocessor (parser & macros)
  2. compiler (create object files per translation unit, which is .c file in C)
    – access control (encapsulation) extends the old trick of emulating private in C++ through macros by marking functions as static (local within translation unit) in C.
  3. linker (combine object files and adjust the addresses)

Templates behaves like a combination of macros (copy-and-paste with parameters) except it’s spread across the toolchain like inline optimizations:

  • Code bloat (one copy per type combination)
  • Can only live in the header files (it’s a template, not realized code, so no object is emitted like a .cpp file)

Parsing (language design)

  • most vexing parse [Effective STL Item 6]: if something can be interpreted as a function declaration, it will be interpreted as a function declaration

Plain Old Data Types (C++ classes tried to emulate in their operator overloading behavior)

  • [15] allow (a=b)=c chaining by returning *this for operator=
  • [21] disallow rvalue assignment (a+b)=c by returning const object

 7 total views

Rationale Behind C++ Commandments (1) – Introduction

If you’ve programmed in (or studied) C++ long enough, like you have read Scott Meyers’s Effective C++, which is a book organized in, jokingly, commandments like ‘thou shall make destructors virtual’. There’s a lot of stuff to remember.

I’ve found an approach to make the ideas stick: by understanding the rationale behind these commandments through the lens of ‘What would you do if you were to make C++ (features) out of C?

C++ is not a language designed from scratch. A lot of quirks and oddities in C++ came straight from the philosophy and the language features naturally available in C. With the right jargons (concepts), you will find a lot of the seemingly counter-intuitive behavior ‘it ought to be like this because of (insert design choice here)‘.

This is what we are going to explore in the “Rational Behind C++ Commandments” (RBCC) blog post series which came from my notes when I was going through Scott Meyer’s book. Once you get the ideas, you should be able to come up with the rules in Effective C on your own (so you don’t have to blindly remember them).

 10 total views,  1 views today

Dart Language: late binding in lambda (no capture syntax)

Dart’s documentation at the time of writing (2021-10-27) is not as detailed as I hoped for so I don’t know if the Lambda (anonymous function) is late-binding or early-binding.

For those who don’t know what late/early-binding is:

Bindingearlylate
Expressionclosed (closure)open (not a closure)
Self-containedyesno
Free symbols
(relevant variables
in outer workspace)
bound/captured at creation
(no free symbols)
left untouched until evaluated/executed
(has free symbols)
Snapshotduring creationduring execution

Late-binding is almost a always a gotcha as it’s not natural. Makes great Python interview problems since the combination of ‘everything is a reference‘ and ‘reference to unnamed objects‘ spells trouble with lazy evaluation.

I’d say unlike MATLAB, which has a more mature thinking that is not willing to trade a slow-but-right program for a fast-but-wrong program, Python tries to squeeze all the new cool conceptual gadgets without worrying about how to avoid certain toxic combinations.

I wrote a small program to find out Dart’s lambda is late-bound just like Python:

void main()
{
  int y=3;
    var f = (int x) => y+x;	
    // can also write it as 
    // f(int x) => y+x;
  y=1000;	

  print( f(10) );
}
The result showed 1010, which means Dart use open lambdas (late-binding)

LanguageBinding rules for lambda (anonymous functions)
DartLate binding
Need partial application (discussed below) to enforce early binding.
PythonLate binding.
Can capture (bind early) by endowing running (free) variables (symbols) with defaults based on workspace variables
C++11Early binding (no access to caller workspace variables not captured within the lambda)
MATLABEarly binding (universal snapshot, like [=] capture with C++11 lambdas)

I tried to see if there’s a ‘capture’ syntax in Dart like in C+11 but I couldn’t find any.

I also tried to see if I can endow a free symbol with a default (using an outer workspace variable) in Dart, but the answer is no because unlike Python, default value expressions are required to be constexpr (literals or variables that cannot change during runtime) in Dart.

So far the only way to do early binding is with Partial Application (currying is different: it’s doing partial application of multiple variables by breaking it into a cascade of function compositions when you partially substitute one free variable/symbol at a time):

  1. Add an extra outer function layer (I call it the capture/binder wrapper) putting all free variables you want to bind as input arguments (which shadows the variables names outside the lambda expression if you chose not to rename the parameter variables to avoid conceptual confusion),
  2. then immediately EVALUATE the wrapper with the with the outer workspace variables (free variables) to capture them into the functor (closed lambda, or simply closure) which binder wrapper spits out.

Note I used a different style of lambda syntax in the partial application code example below

void main()
{
  var y=3;
    f(int x) => y+x;
	
    // Partial Application
    g(int w) => (int x) => w+x;	
    // Meat: EVALUATING g() AT y saves the content of y in h()
    var h = g(y);
	
  y=1000;	

  // y is free in f 
  print( f(10) );	

  // y is not involved in g until now (y=1000)	
  print( g(y)(10) );		

  // y is bounded for h when it was still y=3
  print( h(10) );
}

Only h() captures y when it’s still 3. The snapshot won’t happen if you cascade it with other lambda (since the y remains free as they show up in the lambda expression).

You MUST evaluate it at y at the instance you want y captured. In other words, you can defer capturing y until later points in your code, though most likely you’d want to do it right after the lambda expression was declared.


As a side note, I could have used ‘y’ instead of ‘w’ as parameter in the partial application statement

g(int y) => (int x) => y + x

but the ‘y‘ inside g() has shadowed (no longer refers to) the ‘y‘ in the outer workspace!

What makes it confusing here is that quite a few authors think it’s helpful (mnemonics-wise) to use the free variable (outer scope) name you are going to inject into the dummy (argument) as the name of the dummy! This gives the false impression of the variable being free while it’s bounded (through feeding it as a parameter in the wrapper/outer function)!

Scoping rules is a nasty source of confusion in understanding lambda calculus so I decide to give it a different name ‘w‘. I’m generally dismissive of shadowing under any circumstances, to the extent that I find Python’s @ syntactic sugar for decorators shadowing the underlying function which could have been reused somewhere. See my rants here.

Notational ambiguity, even if resolvable, is NOT helpful at all here especially when there are so many level of abstractions squeezed into so few symbols! People jumping into learning the subject quickly for the first time should not have unnecessarily keep track of the obscure scoping rules in their head to resolve the ambiguities!

 12 total views

Reading Lambda Calculus

Complex expressions in lambda calculus notation here is hard to parse in the head correctly until the day I started using Dart Language and noticed the connection between => lambda notation and C-style function layout. Here’s what I learned:

  • The expressions are right-associative because the right-most expression is the deepest nested function
  • Function application (feeding values to the arguments) always starts from left-to-right because you can only gain entry to a nest of functions starting from the outermost level, peeling it layer by later like an onion. So if applying arg to statement is denoted by (statement arg), the order of input would be (((statement arg1) arg2) arg3)
  • Names showing up on the parameter list of the nearest layer sticks to it (local to the function) and excludes everybody else (variable shadowing): this means the same name have absolutely no bearing as a free variable or being a free variable anywhere, so you can (and should) replace it with a unique name.

Here’s the calculus syntax in the book:

This example is the function application used above


Here’s where reusing the variable x in multiple places to mean different things gets confusing as hell, and the author (as well as the nomenclature) do not emphasize the equivalence to variable shadowing rules:

This can be rewritten as having

  • \lambda w . w^2
  • \lambda z . (z+1)
  • \lambda f . \lambda g . \lambda x.(f (g x) )

Upon application,

((\lambda f . \lambda g . \lambda x.(f \quad (g  \quad x) ) \qquad \lambda w . w^2) \qquad \lambda z . (z+1))

\implies (\lambda g . \lambda x.(\lambda w . w^2 \qquad (g \quad x) ) \qquad \lambda z . (z+1))

\implies \lambda x.(\lambda w . w^2 \qquad (\lambda z . (z+1) \quad x) )

which clearly reads for an input of x, it’ll be incremented first then squared. Resolving further:

\implies \lambda x.(\lambda w . w^2 \quad (x+1) )

\implies \lambda x.(x+1)^2

Fucking evils of variable shadowing! Not only it makes the code hard to read and reason, it also make the mathematics hard to follow!

 16 total views

Using Dart’s C-style syntax to make chain of lambda functions concrete

Start with an example lambda calculus expression f\equiv\lambda x.(y+x). It is:

  • [programming view] a function with x as an input argument and it uses y from the outer workspace (called a free-variable). f(var x) { return y+x; }
  • [mathematical view] can also be written as f(x) = y+x where y is seen as a fixed/snapshotted value relative to the expression.
g(int y) => (int x) => y + x

Lambda calculus is right-associative

g(int y) => ( (int x) => y + x )

Unrolling in C-style it will give better insights to the relationships between layers

g(int y) {
  return (int x) { return y + x; };
}

Note that (int x) { return y + x; } is a functor. To emphasize this, the same code can be rewritten by assigning the name f to it and returning f:

g(int y) {
  f(int x) { return y + x; };
  return f;
}

Use the C++11 style syntax so that it doesn’t look like nested function implementation body instead of a functor nested inside a function:

g(int y) {
  var f = (int x) { return y + x; };
  return f;
}

Note that conceptually what we are doing with the wrapper cascade is indeed nested functions. However, in the wrapper, we spit out a functor (which did most of the partial work) so the user can endow/evaluating it with the last piece of needed info/input:

g(int y) {
  f(int x) { 
   return y + x;
  };
  return f;
}

More commonly as seen in Dart docs, this formatting shows a (binder/capturing) wrapper function returning its own nested function:

g(int y) {
  return (int x) { 
           return y + x;
         };
}

 20 total views

Styles for (Lambda) anonymous function (named or unnamed) in Dart Language

Official Dart docs is sometimes too simple to provide ultimate answers for various language questions. I discoverd an alternative syntax for named lambda here and here. In Dart,

(args) => expr

is the shorthand for

(args) { 
  return expr 
}

So the Lambda-style (C++11) names variable by assigning it to a messy functor type (inferred with var in Dart and auto in C++11):

var f = (args) => expr

Which can also be rewritten using C-style function pointer-like declaration except

  1. the body expr is included (which is not allowed in C),
  2. return must be explicit in curly braces block.
  3. arrow notation => takes whatever the expr evaluates to (which can be null for statements like print)
  4. it’s simply the function name f in Dart instead of pointer (*f) in C
[optional return type] f(args) { 
  return expr;
}

which can be simplified with the arrow operator

[optional return type] f(args) => { expr }

 11 total views

MATLAB repeating arrays (elementwise array replication, interleaved ‘repmat’)

Since MATLAB R2015b, there’s a new feature called repelem(V, dim1, dim2, ...) which repeats each element by dimX times over dimension X. If N (dim1) is scalar, each V is uniformly repeated by N times. If N is a vector, it has to be the same length as V and each element of N says how many times the corresponding element in V is repeated.

Here are some historical ways of doing it (as mentioned in MATLAB array manipulation tips)

The scalar case (repeat uniformly) can be emulated by a Kronecker product multiplying everything with 1 (self):

kron(V, ones(N,1))
Just replace all the elements b with 1 so we are left with elements of A repeating the way we wanted

Kron method is conceptually smart but it has unnecessary arithmetic (multiply by 1). Nonetheless this method is reasonable fast until TMW finally developed a built-in function for it that outperforms all the tricks people have accumulated over decades.

The vector case (each element is repeated a different number of times according to vector N) is basically decoding Run-Length Encoding (RLE), aka counts to placements, which you can download maturely written programs on MATLAB File Exchange (FEX). There are a bunch of cumsum/diff/accumarray/reshape tricks but at the end of the day, they are RLE decoding in vectorized forms.


There’s a name for almost each recurring problem that we can think of in MALTAB. Before jumping in and implementing your for loop, ask around and try to find the right keyword/terms to describe your problem! >99.9% of the time your problem is not new!

The most odd-ball MATLAB algorithm scenario I’ve ever came across that requires original thought is the ‘Jenga Matrix‘ (I coined the name) while I was working at Stanford University Medical School as a research assistant for MADIT-CRT.

MATLAB’s OOP was not mature at that time, so dataset() objects didn’t surface. The reason for the ‘Jenga Matrix’ was to create ‘sparse cells’ which uses a sparse matrix with non-zero indices mapping to a cell vector so I can make a table (that’s approximately the guts of heterogenous data structure).

As I remove elements of the ‘sparse cell matrix’, I didn’t want holes in it to accumulate so I’ll have to periodically compact the underlying cell vector and shift the indices to reflect the indices after compacting. Normally if you have to mess with these kind of ingenious indexing algorithms, you are working on some generic abstractions/tools rather than the business logic itself.

There’s no ultimate correct way to implement something in MATLAB, but there are tons of bad ways that is strictly worse under all circumstances! Being smart with these little toy (Cody) problems like array manipulation do not really show practical proficiency in MATLAB. Anybody can spend a day or two to solve a genuinely new algorithm puzzle or just ask around in the forums if you run into it once in a blue moon. Who cares if you can do it 5 times faster if it’s just <1% of the development time?

Most of your time should be spent on using MATLAB to succinctly and intuitively describe your business logic (which requires exploring and understanding your project requirements deeply), and hide the boring background work with generic abstractions (e.g. RDBMS and RLE)! People should be able to read your function and variable names and form a clear picture of what your codebase is trying to achieve instead of stumbling over smart-ass idioms that’s not immediately obvious (which should buried in the lowest level of generic tool functions if you had to develop it in-house).

Even a mathematician in Linear Algebra using MATLAB for 40 years doesn’t mean he’s good at MATLAB! The real MATLAB skills are keeping up with MATLAB has to offer for a variety of scenarios relevant to the task at hand (or know enough abstract concepts like functional programming, OOP, database, etc, to be able to find out the right tools quickly), which is a hell lot of knowledge considering MATLAB covered most common scenario imaginable (the vast majority of MATLAB users aren’t aware of the full offerings and used MATLAB the wrong/hard way)!

 13 total views