
I'm feeling generous. I'll make a generic factory-like function that constructs an object for you. Whatever arguments you give me, I'll forward (foreshadowing!) to that specific object's constructor:

```cpp
template <typename T, typename Arg>
T make(Arg arg) {return T(arg); }

Box b = make<Box>(42); // returns Box(42)
```

Simple, right? I mean, this example is probably a bit contrived (why not just use the `Box` constructor itself) but you can imagine how this is a pared-down example of what something like `std::make_unique` or `emplace_back` might have to do. So let's keep digging.

What does this do?

```cpp
make<Box>(Box{});
```

Hmm, assuming `Box` has copy and move constructors, this actually triggers a copy, not a more-efficient move. Why? Well, the fact that `Arg` is named turns the temporary into an Lvalue, triggering the copy constructor. Actually, move-only types don't even compile:

```cpp
auto p = make<std::unique_ptr<int>>(std::make_unique<int>(5));
// error: call to deleted constructor of 'std::unique_ptr<int>'
//        (return T(arg);  <- tries to COPY arg, but unique_ptr has no copy ctor)
```

Why does it ultimately matter if `make` moves or copies, if the final `Box` contents are correct? Well, one of the canonical reasons to move is for performance. If we move a big `std::string` or `std::vector` that's an O(1) pointer reassignment instead of O(n) deep copy. So if our make doesn't move when it can, we're not being very performant.

Aside from optimization, there's also correctness concerns. Some types are move-only, like `std::unique_ptr`! For exclusive ownership of a managed resource it really wouldn't make sense to have copy constructors.

In essence, the `make` wrapper function here can't preserve the _value category_ of its arguments. This post will be dedicated to exploring what that means exactly, and how perfect forwarding works to help us solve this problem.
# What are L and R values?

The oversimplified way to think about this is that
- Lvalues appear on the left hand side of assignment operator `=`, meaning they represent objects that have an identifiable location in memory ("locator" values).
- Rvalues are temporaries that appear on the right hand side of assignment operator `=` and don't persist beyond that expression. So these temporaries have no name and no address ("read" values).

Given this, we know that taking the address (`&`) of an Lvalue gives you the memory address of its location, and trying to do the same of an Rvalue will make the compiler error.

Well, I lied above a little bit. I said that L and R values can sit on the left and right side of assignment, respectively, but there are some special cases:

``` cpp
const int x = 1;
x = 2;
```
Here, `x` is an lvalue -- it has a specific memory address. But it's `const`, so it actually can't sit on the LHS in the second line -- it can't be modified. The compiler will error. Remember, Lvalue-ness is a distinct concept from const-ness.

And of course, lvalues can sit on the right too, like assignment `int y = x`. 

>One other subtle (or maybe not, if you've experienced having to debug this) thing that can happen is you can set temporaries on the LHS of `=`. Here's what I mean:

``` cpp
class Box {
	public:
		int value;
		Box(int x) : value(x) {}
};

int main() {
	Box(1) = Box(2); // this compiles!!
}
```

>You can't assign primitive types (`1 = 2` would never work), but for classes the `=` call is a hidden member function call, so `Box(1).operator=(Box(2))` isn't blocked. The result is that the temporary `Box` with 1 is modified at runtime to contain `2` and then immediately destroyed at the end of the line. This is kind of a pedantic Rvalue example, but many a bug has been caused by accidentally modifying a copy instead of the real object you want! So if you're writing a class and want to prevent the ability to assign values to temporaries of your class, you use lvalue ref-qualifiers on your assignment operator:

``` cpp
class StrictBox {
	public:
	    int value;
	    StrictBox(int v) : value(v) {}
	    StrictBox& operator=(const StrictBox& other) & {
	        value = other.value;
	        return *this;
	    }
};

// StrictBox(1) = StrictBox(2) will fail to compile!
```

>STL components like `std::optional` or `std::vector` use lvalue ref-qualifiers to prevent this kind of temporary modification bug. And modern C++ (11+) allows for rvalue ref-qualifiers (`&&`) to detect when a member function is being called on a temporary that will die anyway, letting moves (instead of copies) happen and optimizing your performance. And in fact, under the hood `std::move` is just a type cast that forces a variable (lvalue) to become an rvalue again.

Anyway, the actual important caveat for our example is:

# Named Rvalue references are actually Lvalues!

Here's something to be very clear on: named rvalue references are actually lvalues! Example:

``` cpp
void foo(int& x); // lvalue overload
void foo(int&& x); // rvalue overload

void bar(int&& arg) {
	foo(arg); // uses the lvalue overload, because this rvalue reference is named so is actually an lvalue!
}
```

Names turn rvalues into lvalues, destroying the original value category. This could be annoying in some use cases... (foreshadowing)

Okay, so hopefully it is clear to you that if we want to fix our `make`, we can't just go and change the parameter types to use Lvalue ref or const ref or by value or something.

# Fixing with overloads?

Okay, what if we just write a bunch of overloads to handle all our cases? Sorta like this, but with an actual concrete `Arg`:

``` cpp
T make(Arg&  arg);        // lvalue
T make(const Arg& arg);   // const lvalue
T make(Arg&& arg);        // rvalue
```

Like sure, this technically works. But I'm not feeling generous enough to give you an overload for every combination of values and number of args you want -- that's exponential! Is there a way for me to write this function in a scalable way?

Let's take a look at forwarding/universal references, as some way to bind to anything in one parameter while also recording what type of value it bound to.

# `&&` as a Universal/Forwarding Reference

Aside from being a normal rvalue reference (and a logical operator), `&&` actually has another meaning: in templates it's a universal/forwarding reference, and you'll see it in contexts that look suspiciously like rvalue references. See here:

```cpp
void strict(int&& arg); // only accepts rvalues!

template <typename T>
void wrap(T&& arg) // forwarding reference
```
When we deduce the template type `T`, a special **forwarding deduction rule** applies, and then the above reference collapsing rules takes over, and `T&&` can bind to anything: const/non-const L/R-values. Because the compiler has to deduce the type (it's not strictly calculated beforehand), this isn't a normal rvalue reference!

>(By the way, this also means `auto&&` is a forwarding reference and triggers the reference collapsing rules, since the compiler is deducing what type the `auto` is! Using an explicit type alias like `Result ref` bypasses deduction and leaves it as a normal rvalue reference!)

The special forwarding deduction rule says that for `wrap(T&& arg)` called with an argument of type `U`:
- if the argument is an **Lvalue** then `T` deduces to `U&` which is an Lvalue reference and also cv-preserved
- if the argument is an **Rvalue** then `T` deduces to a plain `U` (no reference!)

It's special because this is the only context where deduction can produce a reference type (everywhere else, deduction would strip references and give a value type). 

# Reference Collapsing

In cases where the type is explicitly fixed (even calculated beforehand using `using` or `typedef`, and as opposed to when the compiler has to deduce the type at exact point of variable declaration), the compiler follows the below **reference collapse rules**: 

- `&` + `&` $\rightarrow$ `&`
- `&` + `&&` $\rightarrow$ `&`
- `&&` + `&` $\rightarrow$ `&`
- `&&` + `&&` $\rightarrow$ `&&`

More concretely, here are usage examples of those rules:

``` cpp
using LRef = int&; // lvalue ref type

using Result1 = LRef&; // int& & -> int&
int x = 1; 
Result1 ref = x; // valid, binds to lvalue x
// Result1 ref = 2; errors -- cannot bind int& to an rvalue (2)

using Result2 = LRef&&; // int& && -> int&
int x = 1;
Result2 ref = x; // valid, ref just is int&
// Result2 ref = 2; error -- cannot bind lval ref int& to rvalue (2)

using RRef = int&&; // rvalue ref type

using Result3 = RRef&; // int&& & -> int&
int x = 1;
Result3 ref = x; // valid, collapsed to int&
// Result3 ref = 2; error -- cannot bind lval ref int& to rvalue (2)

using Result4 = RRef&&; // int&& && -> int&&
int x = 1;
// Result4 ref = x; error -- cannot bind rval ref to lvalue (1)
Result4 ref = 2; // valid! This is a normal rvalue reference! int&& binds to temporary 2 cleanly.
```
Basically, if there's any Lvalue reference in the mix, the result collapses into a normal Lvalue reference. 

So for our `Box` example:

```cpp
Box lv; const Box clv;
make<Box>(lv);       // lvalue       → Args = Box&        → param Box&
make<Box>(Box{});    // rvalue       → Args = Box         → param Box&&
make<Box>(clv);      // const lvalue → Args = const Box&  → param const Box&
```

And our `make` so far:

```cpp
template <typename T, typename... Args>
T make(Args&&... args) {
    return T(args...);        // note: passing `args`, NOT std::forward<Args>(args)
}
```

The forwarding reference is just forwarding deduction rule + reference collapsing. The forwarding deduction rule serves to encode the value category into the type `Args` (Lvalue arg of type `Box` means `Args` is `Box&`, Rvalue arg of type `Box` means `Args` is `Box`). Then the reference collapsing is the mechanism that actually substitutes the encoded `Args` into `Args&&` and succinctly makes a correctly-binding parameter type (`Box& → Box& && → Box&` (an lvalue ref — binds the lvalue); `Box  → Box&&` (an rvalue ref — binds the temporary)). Otherwise, `Box& &&` would be a reference to a reference, which is useless and uncompilable. 

Okay, so this forwarding reference is part of the solution: we get a parameter that can now bind to anything and store the original value category in `Args` -- we've solved the unscalable overload problem, and we've eliminated the unnecessary copies at the site of the parameter binding. But still, a named `args` turns into an Lvalue no matter what `Args` is -- we still haven't dealt with the unnecessary copies at object construction. So there's still some part of the pipeline missing. We probably want some kind of flexible cast to turn the named `args` for object construction into the respective value category we got from the forwarding reference. Enter `std::forward`!

# `std::forward`

Yes, `std::forward<T>(arg)` actually is a conditional cast! If `T` comes in as an Lvalue (deduced as `U&`), then it forwards as an Lvalue (and hence invokes the copy constructor). If `T` comes in as an Rvalue (deduced as `U`), then it forwards as an Rvalue (invoking the move constructor). Contrast this with `std::move`, which you can think of as an unconditional cast that always casts to Rvalue. If you're passing along an Rvalue reference you own, you can directly `std::move` it, but if you're just passing along a forwarding reference (like in our `make` example), you're better off `std::forward`ing it!

``` cpp
template <typename T>
T&& forward(std::remove_reference_t<T>& arg) noexcept {
    return static_cast<T&&>(arg);
}

template <typename T>
std::remove_reference_t<T>&& move(T&& arg) noexcept {
	return static_cast<std::remove_reference_t<T>&&>(arg);
}
```

# Forwarding reference + `std::forward` = solved!

So putting that all together, our final magical `make` looks like this:

```cpp
template <typename T, typename... Args>
T make(Args&&... args) {
    return T(std::forward<Args>(args)...);
}

make<Box>(Box{})                            // 1 move, 0 copies
make<Box>(b)                                // 1 copy
make<unique_ptr<int>>(make_unique<int>(5))  // moves!
```

And as I alluded to in the beginning, our toy `make` is useful to understand what happens in the standard library: `std::make_unique/std::make_shared` both forward constructor args to `T`. `vector::emplace_back` forwards args to construct the element in place (without temporaries). Perfect forwarding is what allows `std::function` to function (LOL). And perfect forwarding is also related to how `std::thread` starts another thread running a callable, though it's technically a decay-copy + move... (post with common forwarding gotchas coming later...)

C++ is a language built around zero-cost abstractions and compatibility with C, which is why it's so complex, daunting to learn, and maybe even fun to dig around in. Perfect forwarding is precisely the feature that lets "generic pass-through code" be zero-overhead and behavior-preserving at the same time.
# Sources

[temp.deduct.call/3](https://eel.is/c++draft/temp.deduct.call)

[dcl.ref/6](https://eel.is/c++draft/dcl.ref#6)
[https://en.cppreference.com/w/cpp/language/reference](https://en.cppreference.com/w/cpp/language/reference)

[forward](https://eel.is/c++draft/forward)
[https://en.cppreference.com/w/cpp/utility/forward](https://en.cppreference.com/w/cpp/utility/forward)

[https://developers.redhat.com/blog/2019/04/12/understanding-when-not-to-stdmove-in-c](https://developers.redhat.com/blog/2019/04/12/understanding-when-not-to-stdmove-in-c)
[https://learn.microsoft.com/en-us/cpp/cpp/lvalues-and-rvalues-visual-cpp?view=msvc-170](https://learn.microsoft.com/en-us/cpp/cpp/lvalues-and-rvalues-visual-cpp?view=msvc-170)
[https://en.cppreference.com/cpp/language/value_category](https://en.cppreference.com/cpp/language/value_category)
[https://www.modernescpp.com/index.php/perfect-forwarding/](https://www.modernescpp.com/index.php/perfect-forwarding/)
[https://www.justsoftwaresolutions.co.uk/cplusplus/core-c++-lvalues-and-rvalues.html](https://www.justsoftwaresolutions.co.uk/cplusplus/core-c++-lvalues-and-rvalues.html)
[https://www.studyplan.dev/pro-cpp/forwarding](https://www.studyplan.dev/pro-cpp/forwarding)


Perfect Forwarding


One of the many (certainly not the main!) takeaways from [Ben Deane's CppNow 2026 talk](https://schedule.cppnow.org/session/2026/plato-magritte-sartre-carroll/) was, in the words of Lewis Carroll's White Queen, to imagine six impossible things before breakfast. In sort of that spirit, I've started poking around more to understand what kinds of defects and issues in the C++ standard have come up and what the resolutions have entailed. Below, I explain what I learned about indirection and UB, casts, and lvalue-to-rvalue conversions specifically through CWG defect report numbers 232, 453, 242, and 446, and also indirectly (ha) through 315, 2823, 2875, 342, 1102, and 86.
# 232:  Is indirection through a null pointer undefined behavior?

Previously, the standard conflicted itself about whether `*nullptr` was UB. Some sections like then-intro.execution paragraph 4 said it was, and then-dcl.ref paragraph 4 said that this UB was reason to not have "null references". However, the definition of unary `*` didn't mention it (and didn't explicitly say that if the operand is nullptr, this is UB). `typeid(*p)` even gave null dereference well-defined semantics (saying it should throw `bad_typeid`). Clearly this was an inconsistency that needed to be cleaned up.

From my understanding reading through the history of this discussion [on the CWG page](https://cplusplus.github.io/CWG/issues/232.html), this basically boiled down to an important semantic difference. Should the process of forming an lvalue from a nullptr be UB, or should only reading the value be undefined behavior? In the following example that Bill Gibbons gave, if you dereference then immediately take the address without accessing the memory, should that be UB?

>`char *p = 0;`
>`char *q = &*p;`

Or should the following pointer arithmetic idiom of dereferencing a pointer to no object be UB if the value isn't used?

>`char a[10];`
>`char *b = &a[10];   // equivalent to "char *b = &*(a+10);"`

Tom Plum agreed by saying the standard's intent was that UB should trigger at the point of lvalue-to-rvalue conversion, so forming an lvalue from a dereference without reading should be fine. But Mike Miller here then asked what it meant to have created a "null lvalue": if null lvalues are legal, then null references are also legal, because references are just named lvalues. This undermines the fundamental C++ guarantee that references must always refer to a valid object!

Obviously having inconsistencies in the standard is a pretty big issue, and even more so when it's about core behavior like dereferencing null pointers. Compilers like GCC or clang use "dereferencing implies non-null" as an optimization assumption (allowing code elimination by assuming `p != null` after any dereference). Many optimizations also depend on null references not being a thing. If the above one-past-end iterator idiom was UB, then most existing iterator/range semantics would be broken (in fact, the later "safer" ways to iterate like `std::span::end()`, `std::vector::end()`, range-for still use one-past-end pointers internally. The increased safety comes from wrapping that pointer to prevent end-users from misusing it).

In October 2004, the committee tried to resolve this by inventing a new concept: empty lvalues that refer to no object. The idea is something like:

- dereferencing null / one-past-end produces "empty lvalue"
- taking the address of empty lvalue is fine (gives back original pointer)
- lvalue-to-rvalue conversion of an empty lvalue is UB
- binding a reference to an empty lvalue is UB

This would've meant that the above two examples were legal and `typeid` kept its behavior definition. But it created too many other edge cases to deal with. Here's my attempt at summarizing what I could find:

Even though `*(a + N)` would give an empty lvalue (and thus be allowed), that's not the only kind of expression or usage that would need addressing. Would `*(a + N + 5)` or `*(a + N) = 5` be allowed? This would require a revisiting of everything in `sizeof`, `decltype`, member access, etc. to clarify empty lvalue behavior. Would `sizeof(*p)` where `p` is null also produce an empty lvalue or not? There's some line that would have to be drawn between "unevaluated" and "evaluated but produces empty lvalue". Tedious!

Similarly, what would happen to static member access through null pointers ([CWG 315](https://cplusplus.github.io/CWG/issues/315.html))? I.e. is `ap->f()` AKA `(*ap).f()` UB when `ap` is null and `f()` is static? Originally CWG said this was fine because `.f()` on a static member doesn't read from it. But this meant empty lvalues needed to propagate through member access expressions: UB would arise if `f` was non-static. This is an extremely hairy thing to add!

How would the `typeid(*null)` exception work? `typeid` would receive an empty lvalue and detect its emptiness to be able to throw `bad_typeid`. So runtime would have to be able to distinguish empty from normal lvalues, which is bad for the separation of concerns between compile- and run-time. This abstraction incoherence would just be terrible design.

`constexpr` expression evaluation would also get really annoying. The compiler would have to track whether every lvalue was empty and reject anything that did lvalue-to-rvalue conversions on them. I think this is technically doable, but just needlessly annoying and hard to deal with because of this policy.

So for the above reasons (and probably more), in November 2023 CWG scrapped this empty lvalue thing. Not only was this an extremely far-reaching resolution to adopt, but consensus was that this was an EWG-level language design problem and not a CWG-level wording fix. The discussion moved to [CWG 2823](https://cplusplus.github.io/CWG/issues/2823.html), where dereferencing an invalid pointer was specifically made UB. The side effects here were that 

- CWG 315 was retroactively flipped: static member calls through nullptrs were now UB
- `&*p` where `p` is null is also now UB, diverging from C (documented in [CWG 2875](https://cplusplus.github.io/CWG/issues/2875.html), which was accepted November 2025 and is now in DRaft Working Paper (DRWP) status for possibly C++29 or later)
- `&a[N]` for an array of size N is now UB in C++ but defined in C. This divergence is also documented in CWG 2875.

Also, though I've been saying "dereference", [CWG 342](https://cplusplus.github.io/CWG/issues/342.html) standardized the language to "indirection" over "dereference" to be more aligned with C's terminology, and actually through [CWG 1102](https://cplusplus.github.io/CWG/issues/1102.html), the standard replaced "dereferencing the null pointer" with "effect of attempting to modify a const object" as the canonical example of UB.

Wow! It's quite interesting to track the history of a defect report that pointed to an existential intent question that still has non-solidified standards ramifications 26 years later! (Indeed, I'm writing this on June 6, 2026, almost exactly 26 years after CWG 232 was submitted on June 5, 2000.)

# 453: References may only bind to valid objects

[CWG 453](https://cplusplus.github.io/CWG/issues/453.html) spent years trying to pin down a definition of "valid object" for reference binding: this defect report basically points out that the standard says "a reference shall be initialized to refer to a valid object or function" but never defines "valid object". Is `f1` a valid object if the constructor receives `f1` as a reference without full initialization? The March 2024 resolution was to replace "valid object" with specific rules:

- references can bind to objects outside their lifetime (e.g. during construction)
- binding through a type-incompatible glvalue (like `*reinterpret_cast<int*>(&char_obj))` is UB
- evaluating a reference before its initialization is UB
- specifying that the object designated by such a glvalue can also be outside its lifetime.

Had empty lvalues been adopted as from [#232](#232-is-indirection-through-a-null-pointer-undefined-behavior), binding references to empty lvalues would need to be separately addressed (this is different from "object outside its lifetime"!)

# 242: Interpretation of old-style casts

[expr.cast](https://eel.is/c++draft/expr.cast) deals with how a C-style cast `(t)(expr)` is supposed to be handled. The following interpretations are to be tried in order, and we should use the first one that applies (you can see this [implemented in clang](https://github.com/llvm/llvm-project/blob/main/clang/lib/Sema/SemaCast.cpp#L2847-L2858)):
```cpp
const_cast
static_cast
static_cast + const_cast
reinterpret_cast
reinterpret_cast + const_cast
```
(Just to review, `static_cast` is for well-defined compatible conversions, `const_cast` is for adding/removing cv qualifiers, and `reinterpret_cast` is for low-level bit-pattern reinterpretation. Their safety is roughly descending in that order, because `static_cast` is compile-time checked, `const_cast` can result in UB if used incorrectly, and `reinterpret_cast` circumvents type-safety completely. See also [this](https://stackoverflow.com/questions/332030/when-should-static-cast-dynamic-cast-const-cast-and-reinterpret-cast-be-used))

The intent here is that if we have something like this example from the defect report:
```cpp
struct A {};
struct I1 : A {};
struct I2 : A {};
struct D : I1, I2 {};
A *foo( D *p ) {
	return (A*)( p ); // ill-formed static_cast interpretation
}
```
trying to do the derived-to-base pointer conversion `(A*)(p)` should be one of the conversions that can be performed using `static_cast`. This cast is ill-formed because of ambiguity (which `A` should the pointer convert to, the one offset in `I1` or the one offset in `I2`?), and the compiler should error -- and crucially, not fall through to any of the other (more dangerous) types of casts. 

DR 242 points out that the description of `static_cast` in [expr.static.cast](https://wg21.link/expr.static.cast) implied something that didn't match the intent. Specifically, the line 

>An expression `e` can be explicitly converted to a type `T` using a `static_cast` of the form `static_cast<T>(e)` if the declaration "`T t(e);`" is well-formed, for some invented temporary variable `t`.

seems to imply that `A* t(p)` is ill-formed because of ambiguity, and therefore `(A*)(p)` is NOT one of the conversions that can be done using `static_cast`, and would fall through to `reinterpret_cast<A*>(p)` which is well-formed via [expr.reinterpret.cast](https://wg21.link/expr.reinterpret.cast#7).

The CD4 status of this DR means this wording was clarified in C++17. Along with the above example of ambiguous upcasts, the standard also revised the wording for ambiguous downcasts, virtual base downcasts, reference casts, and pointer-to-member casts. Ambiguous downcasts, reference casts, and pointer-to-member casts are can't be handled by `static_cast` for similar reasons to ambiguous upcasts. Virtual base downcasts have offsets that are looked up through vtables at runtime, so `static_cast` can't handle them at compile time.

# 446: Does an lvalue-to-rvalue conversion on the "?" operator produce a temporary?

Consider the following:

```cpp
struct B {
	int v;
	B (int v) : v(v) { }
	void inc () { ++ v; }
};
struct D : B {
	D (int v) : B(v) { }
};

B b1(42);
(0 ? B(13) : b1).inc();
assert(b1.v == 42); // should this pass?
```

What exactly does that conditional `0 ? B(13) : b1` do? Does it result in an lvalue referring to `b1` itself (which would mean `.inc()` modifies `b1`, and the assert fails), or a temporary copy (rvalue) of `b1` (where `.inc()` modifies a temporary, `b1` itself is untouched, and the assert passes)?

Well, the second operand `B(13)` is a prvalue (temporary), and the third operand `b1` is an lvalue. The standard requires the conditional expression to have a single type and value category regardless of the branch (for more funny examples of this, you should check out Jonathan Muller's CppNow 2026 lightning talk when it comes out). So since one operand is an rvalue, the overall expression must be an rvalue, and `b1` must undergo lvalue-to-rvalue conversion: the value is "read out" of `b1`. 

Yeah, that's fine and all for scalar types like `int` where an original and a copy wouldn't have any difference, but what about class types? Should the lvalue-to-rvalue conversion call the copy constructor to create a temporary? This results in e.g. address identity changes. Or should this conversion happen by "reinterpreting" the lvalue as an rvalue without copying? Then the `.inc()` would modify the original object through what is supposed to be an rvalue, which is weird because end users expect rvalues to be disposable. The distinction also mattered for e.g. taking a const reference to extend lifetime -- this would have different semantics depending on if it was acting on a copy or not.

This DR points out that the standard's wording at the time was ambiguous: it said this conversion for classes "produces the value contained in the object" but didn't explicitly mandate a copy/temporary. Consider the following test cases:

```cpp
#include <cassert>
struct B {
    int v;
    B (int v) : v(v) { }
    void inc () { ++ v; }
};
struct D : B {
    D (int v) : B(v) { }
};
int main () {
    B b1(42);
    D d1(42);
    (0 ? B(13) : b1).inc();
    assert(b1.v == 42);
    (0 ? D(13) : b1).inc();
    assert(b1.v == 42);
    (0 ? B(13) : d1).inc();
    assert(d1.v == 42);
}
```

The core idea should ideally be something like `cond ? a : b` should have one type and one value category regardless of the runtime branch. So if either branch is a temporary, the whole expression should be a temporary. Otherwise the principle that value categories should be a static property of expressions is violated. In the first case, the `B(13)` is a prvalue -> expression should be an rvalue -> `b1` should be untouched and the assert should pass. In the second case, `D(13)` converts to `B`, and the assert also passes due to same reasoning as the first case. In the third case, the `D` object gets sliced down to a `B` temporary, and then again the same value category reasoning applies and the assert should pass.

When this was posted to the Usenet clc++m group in 2003, different providers (GCC, MSVC, SUN...) showed different results on whether they copied or made a temporary. Clearly this ambiguity had resulted in diverging handling. Some compilers just reinterpreted the expression as an rvalue without copying, which was an issue for mental models of value categories, as we saw above.

In March 2004 it was decided that all `?` operators returning a class rvalue should copy the second or third operand to a temporary. This also resolved [CWG 86](https://cplusplus.github.io/CWG/issues/86.html). 



Exploring CWG Defect Reports (Part 1)


All of my friends know that I play Set at a level so beyond obsessive it almost integer overflows to mundane -- the simplicity and symmetry of the game makes for an easy way to reset the marbles in my brain, and it's a quick way to idly pass by a minute or two between subway stops. Because of the elegant (one could even say algebraic) nature of the game, it's also fun to use for combinatorics questions. Since I've been trying to get more used to Lean anyway, I decided to try proving some Set combinatorics in Lean.

Let's first look at how many distinct sets there should be from the deck of 81 cards. The Fundamental Theorem of Set says that given two cards, we can uniquely determine the third card in the set (try it!). So there are $\binom{81}{2} \cdot \frac{1}{3} = 1080$ unique sets we can create (remember we divide by 3 to correctly account for the 3 different ways to choose the first 2 cards from the 3 cards in a set).

I won't go into the rules of Set or how I chose the specific representation of cards (plenty has been written about this), but since Set cards have 4 attributes with 3 choices each, one elegant way to represent a card is as a 4-dimensional vector space over the set of integers mod 3, or $\mathbb{Z}_3^4$. 

```lean
def Card := Fin 3 × Fin 3 × Fin 3 × Fin 3
```

Then the really elegant thing is that we can test three cards form a set by seeing what the elementwise sum of the 3 vectors is. We get a set if and only if the resulting sum is the 0 vector, because three cards are a set if and only if for each of the attributes, the cards are either all the same or all different. This elegant set condition is pretty unique to the number of options per attribute and number of cards defined as making up a set (try it!). 

Remember that by our definition, Lean reads `Card` as looking like something like this: `Fin 3 × (Fin 3 × (Fin 3 × Fin 3))`, so we have to do some funny indexing to do elementwise addition. We also denote this as just a statement of truth by using `Prop`:

```lean
def isSet (c1 c2 c3 : Card) : Prop :=
  c1.1 + c2.1 + c3.1 = 0 ∧
  c1.2.1 + c2.2.1 + c3.2.1 = 0 ∧
  c1.2.2.1 + c2.2.2.1 + c3.2.2.1 = 0 ∧
  c1.2.2.2 + c2.2.2.2 + c3.2.2.2 = 0
```

Then we need to do some setup before we can tell Lean to prove there's 1080 sets in a deck. First, let's tell it what to do with a group of 3 cards. We use `Decidable` to tell Lean that it will use our `isSet Prop` to make an executable boolean program that takes as input an instance of 3 cards. Lean automatically does this via `infer_instance`, but we need to tell it to `unfold isSet` because our `Card` is defined via raw nested products. 

```lean
instance (c1 c2 c3 : Card) : Decidable (isSet c1 c2 c3) :=
  by unfold isSet; infer_instance
```

Actually, we also need to tell Lean how to decidably check for equality and how to perform addition, so we have to explicitly add in our previous definition that `Card` derives from `Fintype` and `DecidableEq`.

```lean
def Card := Fin 3 × Fin 3 × Fin 3 × Fin 3
  deriving Fintype, DecidableEq
```

From here, the basic sketch of this method is that we will tell Lean how to construct all sets from the deck, and since the Set deck is relatively small and there aren't too many sets, Lean can bash out how many sets there are and check that it's equal to what we know combinatorially.

To make our lives easier, let's define an ordering of set cards so that we can cleanly keep track of which sets we've seen before. To accomplish this, for readability (and perhaps teachability, because this is certainly not the easiest way) we can "overload" the `<` operator to do some lexicographical ordering for us:

```lean
def cardLessThanBool (c1 c2 : Card) : Bool :=
  (c1.1 < c2.1) ||
  (c1.1 == c2.1 && c1.2.1 < c2.2.1) ||
  (c1.1 == c2.1 && c1.2.1 == c2.2.1 && c1.2.2.1 < c2.2.2.1) ||
  (c1.1 == c2.1 && c1.2.1 == c2.2.1 && c1.2.2.1 == c2.2.2.1 && c1.2.2.2 < c2.2.2.2)

instance : LT Card where
  lt c1 c2 := cardLessThanBool c1 c2 = true
```

I say overload in quotes because it feels like overloading a method, but actually Lean implements this using a typeclass system. `LT` is a global typeclass defined in Lean's core library: "Any type implementing `LT` must provide a function called `lt` that takes two items and determines a proposition." So we have to make sure to return a `Prop`, not a `Bool`, which is why we return `cardLessThanBool c1 c2 = true`.

Similar to before, we also have to make sure Lean knows how to compute whether a card is less than another card. Again, `Decidable` tells Lean that we are providing an explicit algorithm to check our claim and provide a true/false. `change` here tells Lean that because we've overloaded `<` previously, we can rewrite the target goal using `cardLessThanBool` to explicitly show the boolean equality equation. Then `infer_instance` searches Lean's typeclass database, finds the core library built-in rule that says "Checking if a known boolean function outputs `true` is always decidable (you just run it)", and uses that to automatically construct the runtime validation block. 

```lean
instance (c1 c2 : Card) : Decidable (c1 < c2) :=
  by change Decidable (cardLessThanBool c1 c2 = true); infer_instance
```

Here I had to stop and think about why Lean was seemingly so smart in some areas (it knows how to infer if boolean functions are decidable!) but not in other areas (we have to use `by change` as a macro hint to... tell Lean that the overloaded lt boolean function... is... decidable??). It turns out that when Lean sees something like `(c1 < c2)`, it looks for an algorithm to compute `Decidable (c1 < c2)` by looking for `Decidable (LT.lt c1 c2)`. It doesn't automatically open up the definition of `LT.lt` to realize that the custom logic is just a simple `Bool` function. So we have to tell Lean to look under the abstract wrapper using the `by change` tactic.

That all said, we're now pretty close to being able to finish our bashy count proof. We'll use two nested loops to represent our first two cards, then use our `lt` operator to cleanly search for the third card using our previously-defined `isSet`. We use `biUnion` as a flat map for the first two cards, and `filter` for the third card's conditions. WLOG, we only have to look for a `c3` if `c1 < c2`, and we only count the set if `c2 < c3`, otherwise we just use the null set `∅`. This helps with recursion depth issues. `map` packages up the three cards so we take `c1, c2, c3` as a set.

``` lean
def allSetsProduct : Finset (Card × Card × Card) :=
  (Finset.univ : Finset Card).biUnion fun c1 =>
    (Finset.univ : Finset Card).biUnion fun c2 =>
      if c1 < c2 then
        ((Finset.univ : Finset Card).filter fun c3 => c2 < c3 ∧ isSet c1 c2 c3).map
          ⟨fun c3 => (c1, c2, c3), fun _ _ h => by injection h; rename_i h2; injection h2⟩
      else ∅
```

What's that second to last line? Well, a `Finset` contains unique items by definition. So before using `map`, we have to prove that we aren't counting duplicate entries. We use `by injection h` to prove that if two `c3` cards are identical, their output triples must be identical too. Similar to the `change` tactic above, that `injection` tactic peels back the nested layers to satisfy the safety checker.

Then we can check that Lean does indeed find 1080 sets by the following:

```lean
theorem card_sets_product : (allSetsProduct).card = 1080 := by decide
```

Actually, we also need to add something like this:

```lean
set_option maxRecDepth 1000000
set_option maxHeartbeats 1000000
```

`maxRecDepth` sets the max recursion depth, and `maxHeartbeats` sets an allowed amount of computation effort. A heartbeat roughly corresponds to 1,000 small memory allocations.

Whew! We did it! Okay, admittedly that was pretty bashy. We basically told Lean how to check set conditions for a given trio, and made it look at all the (ordered) trios to match that number to what we calculated combinatorially before. Along the way, we had to do some "casting" and some "overloading". We could optimize on this approach by modeling cards as `Fin 4 → Fin 3` and using `Pi.Lex` for ordering. This also makes addition in our `isSet` definition more elegant. But I think there's still a more combinatorial (not sure if this is more elegant code-wise though) way to prove this, which I'll explore in a follow-up post.


Using Lean to Prove 1080 Sets


# Lambdas

A lambda is an anonymous function object:

```cpp
int i = 0, j = 1;
auto func = [i, &j](bool b, float f){++j; std::cout << i << ", " << b << ", " << f << std::endl; };

func(true, 1.0f); // 0, 1, 1
```

There's 3 parts in a lambda:
- capture list `[]` of variables to be used
- arguments `()` passed in at execution time
- function logic `{}`

> Fun fact: `[](){}();` is a useless but valid expression that declares an empty lambda with 0 captured variables and 0 arguments and immediately executes it.

What do we mean by anonymous function object? Well, every lambda expression generates a unique, unnamed class at compile time. So they behave like functors, which are objects that can be called/invoked like a function because of `operator()` overload. This is an example of a zero-overhead abstraction -- you pay nothing extra for using this higher-level syntactical sugar, it compiles down to the same machine code:

```cpp
auto add = [](int x, int y) { return x + y; };                  
add(1, 2);  

struct __lambda {
    int operator()(int x, int y) const { return x + y; }
};

__lambda add; 
add(1, 2); 
```

By the way, you'll often see the word "closure" used, especially around lambdas. The closure is the actual object the compiler creates when you write a lambda. Here, the lambda `add` leads to the compiler generating something like the struct `add`. The closure is the struct instance and the closure *type* is `__lambda`.

# Captures and `mutable`

The arguments and function logic are perhaps self explanatory, but the capture list is a little interesting. The captures become data members in the unnamed class that is generated from every lambda. This means there isn't any single size for all lambdas. As you might expect, there are three ways variables can be captured:

- capture-by-value: variables are stored as copies in the closure object
- capture-by-reference: variables are stored as reference members (here there's a dangling reference risk!)
- capture-by-move: creates new data members

There's specific syntax for some common kinds of captures:

- `[&](){ i=0; j=0; }` captures all variables in use by reference
- `[=](){ k=0; }` captures all variables in use by value
- `[&, i, j](){}` captures all vars by ref except i and j by value
- `[= &i, &j](){}` captures all vars by value except i and j by ref

Now, by default `operator()` is `const`, meaning it can't modify its captured variables. Even if the variable is captured by value/move and the lambda owns a copy/moved-in object, the member variables can't be mutated. This is a safety choice. References themselves are `const` but the underlying object is of course not, so be careful as well here. In cases where you do actually intend to modify the copy (or moved-in object), you explicitly specify the `mutable` keyword:

```cpp
auto f = [x]() mutable {
	x = 20;
}
```

Needing to use `mutable` on a lambda is relatively rare in practice, but useful for things like accumulating state across calls, consuming a move-only resource (then you could only meaningfully call the lambda once), or lazy initialization like the following:

``` cpp
auto get = [cache = std::optional<Result>{}]() mutable -> Result {
	if (!cache) cache = expensive_compute();
	return *cache;
}
```

To be clear, the lambda's cache is specific to that lambda instance. This differs from a `static` cache in a named `Result` struct. 

If you find a need for `mutable` often, that could be a code smell. Consider using a named struct or class for long-lived objects. Mutable lambdas are better for short-lived, localized stateful callbacks.
# Lambda decay to function pointer, and unary trick

Lambdas that don't have captures have no state, so they can be represented as a plain function. The compiler will generate that implicit conversion operator. This is what is meant by "lambda decay to function pointer".

``` cpp
struct __lambda {
    int operator()(int a, int b) const { return a > b; }
    // compiler also generates this:
    using FnPtr = bool(*)(int, int);
    operator FnPtr() const {
        return [](int a, int b) { return a > b; }; // a static forwarder
    }                                                                               
};
```

This implicitly gets used when the context requires a function pointer, e.g.

```cpp
auto f = [](int a, int b) { return a > b; };
bool (*fp)(int, int) = f;  // conversion operator called here  
```

This is useful for compatibility with C-style function pointers. In general, decay usually automatically happens, 

``` cpp
void set_callback(void (*cb)(int));
set_callback([](int x) {});  // implicit decay, no forcing needed 
```

but there are some ambiguous cases when you'll need to force the conversion.

1. overloaded functions with ambiguity
	``` cpp
	void foo(void (*)(int));
	void foo(void (*)(double));
	foo([](int x) {});  // ERROR: which overload?  
	```
2. template type deduction (deduction doesn't trigger conversion)
	``` cpp
	template <typename T>
	void foo(T* fn); //expects a pointer
	
	foo([](int x) {}); // Error: T can't be deduced -- lambda is not a pointer
	```
3. `auto` in a pointer context
	``` cpp
	void (*fp)(int) = [](int x) {}; // implicit decay works here -- target type is known
	auto fp = [](int x) {}; // auto deduces closure type, not pointer
	```

How do you force a conversion? You could use a `static_cast`:

```cpp
auto func = static_cast<int(*)(int)> ([](int x) { return x * x; });
```

Or you could use the unary plus trick to trigger the implicit conversion operator without a verbose cast. This works because the operator `+` isn't defined for the lambda's closure type. The compiler looks for a conversion to make `+` applicable, finds the implicit conversion operator to a function pointer, applies it, and then applies unary `+` to the resulting pointer. The type of `decayed_ptr` here is `int(*)(int)`. The `*` is the pointer declarator, and sanity check! -- we use the parens for grouping, otherwise `int* (int)` of course means a function taking `int`, returning `int*`.

```cpp
auto decayed_ptr = +[](int x) { return x * x; };
```

But function pointers can't be inlined (pointer target is unknown at compile time) and require that indirect pointer call at runtime.  On the other hand, a lambda passed to e.g. `std::sort` can be fully inlined because the closure type is unique and `operator()` is statically known. 

```cpp
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
```
When we pass callables in templates, we let the compiler see through the callable and optimize. This is why std algorithms are all templated -- our `std::sort` example above instantiates with the concrete lambda type, inlines the body into the loop, and enables vectorization. We also might want to use templates to customize behavior of a class or algorithm at compile time:

``` cpp
template <typename Comparator>
class PriorityQueue {
	Comparator cmp;
	public:
		void push(int x) { /* uses cmp */ }
	};

PriorityQueue<decltype([](int a, int b) { return a > b; })> pq; 
```
In this example the comparator is baked into the type, giving us zero-runtime cost.

In some cases we can't/don't want to use templates (e.g. when you want to store the callable -- can't store a template parameter, or when you want different callables chosen at runtime -- virtual/runtime polymorphism, or across compilation boundaries where you don't want to expose implementation in headers). How can we still pass in a callable?

# Type erasure via `std::function` 

When you want the ability to store a callback as a class member, or flexibility for runtime polymorphism, or cleaner separations across API and TU boundaries, you can use `std::function`, which is basically a generalized box for callable things.

``` cpp
struct Button {
	std::function<void()> on_click;
};

Button b;
b.on_click = []() { printf("clicked\n"); };
b.on_click = []() { printf("Something else\n"); }; //reassignable at runtime
```

The class member's type must be fixed at class definition time, so you can't template it. `std::function` gives you that general type to hold any matching callable. Similarly, callbacks that vary at runtime also can't use compile-time templates and can use `std::function`. And here's an example of how to use `std::function` to compartmentalize implementation details:

``` cpp
void register_handler(std::function<void(Event)> handler); // lives in a header
```

If this was a template, the whole implementation would have to live in the header, and every TU would get its own instantiation. With `std::function`, we can stick the implementation in one `.cpp` file and keep a stable ABI -- if you ship a compiled library, callers compiled against an old version of the header should still work with a new version of the library binary without recompilation. With templates, every caller would have to recompile. 

Another example worth mentioning is when you want to store heterogeneous callables in a container. Since `std::vector` needs a single element type, and each lambda has a unique type, you can't make a vector of raw lambdas.

``` cpp
std::vector<std::function<void(int)>> callbacks;
callbacks.push_back([](int x) { printf("%d\n", x); });
callbacks.push_back([](int x) { log(x); });
```

To be clear, this fun flexibility does not come for free! Under the hood, `std::function` stores the callable either inline (small buffer optimization, for small callables) or on the heap (for larger ones), and also stores a table of function pointers telling `std::function` how to operate on the object: a function pointer that knows how to invoke the underlying, and function pointers to copy or destroy it. 

``` cpp
// std::function internally holds something like this
struct vtable {
	void (*invoke)(void* storage, args...);  // how to call it
	void (*copy)(void* dst, void* src);       // how to copy it
	void (*destroy)(void* storage);           // how to destroy it
};  
```

So when you call a `std::function`, it makes one call into `std::function::operator()`, one indirect call into `invoke_fn()`, and then calls the underlying. Because this is type erased, the compiler can't inline these calls for any optimizations, and you're always going through a layer of indirection regardless of how simple the underlying callable is.

# Small buffer/function optimization (SBO/SFO)

Heap allocation is expensive: it goes to the allocator and might cause cache misses. The allocated memory also probably lives far away in memory away from the `std::function` object. So the idea of small buffer optimization is to have a small fixed-size buffer directly inside the `std::function` object and store small callables there. Otherwise it heap allocates and `heap_ptr` points to it:

``` cpp
	// conceptually what std::function might look like internally 
	struct function {
		vtable* vt;
		union {
			void* heap_ptr;              // pointer to heap if callable is large
			char  buffer[sizeof(void*)   // inline storage if callable is small
						  * 3];        // can hold 3 pointers worth of bytes
		} storage;                                                                            
	};
```

The size of the buffer is implementation-defined, but usually something like 16-32 bytes. So for instance, a lambda capturing a few ints probably fits, but a lambda capturing a `std::vector` wouldn't. Note that SBO doesn't eliminate the vtable indirection cost! It just removes that heap allocation cost. SBO also makes the `std::function` larger. And to be clear, SBO isn't just an optimization for `std::function` and callables -- the same kind of buffer optimization is used for strings and other types as well.

# Performance tradeoffs

Let's recap when to use what for different considerations. Lambdas allow for inlining and compiler is free to perform optimizations. There's no indirection, so they're the fastest kind of callable.  Function pointers don't allow inlining, but they're faster than `std::function` due to no vtable, no heap, and no type erasure overhead.`std::function` doesn't allow for inlining or compiler optimizations, and depending on the size/storage, may come with heap allocation costs. They also incur two layers of indirection at call time. You should use `std::function` for runtime polymorphism, storage, or separation of TUs or stable ABI boundaries. But if you can, you should use lambdas + templates, especially for performance-critical code or hot loops, or for compile-time optimizations. Function pointers are useful mainly for C API compatibility.

# Sources

[https://shaharmike.com/cpp/lambdas-and-functions/#capture-by-value-vs-by-reference](https://shaharmike.com/cpp/lambdas-and-functions/#capture-by-value-vs-by-reference)

[https://www.youtube.com/watch?v=aC-aAiS5Wuc](https://www.youtube.com/watch?v=aC-aAiS5Wuc)

[https://www.youtube.com/watch?v=qmd_yxSOsAE](https://www.youtube.com/watch?v=qmd_yxSOsAE)


Lambdas and <code>std::function</code>


I've been having great fun in the Lean dependent type system, so it's high time I wrote about pattern matching!
# What is pattern matching?

Pattern matching is a mechanism for deconstructing data types by directly matching against their structure and binding components to variables. For production software, native pattern matching support in a language helps with type safety, reducing defensive checks and making illegal/not-well-defined states unreachable. For formal verification, this is how we prove propositions -- each case is a proof obligation.

By C++17 we'd gotten `std::variant`, `std::visit`, and structured bindings as an [approximation for a non-native way](https://bitbashing.io/std-visit.html#fn:2) to pattern match. 

```cpp
#include <variant>
#include <iostream>

struct Zero {};
struct Succ {
    int value;
};

using Nat = std::variant<Zero, Succ>;

template<class... Ts>
struct overloaded : Ts... {
    using Ts::operator()...;
};

template<class... Ts>
overloaded(Ts...) -> overloaded<Ts...>;

void printNat(const Nat& n) {
    std::visit(overloaded{
        [](const Zero&) {
            std::cout << "Zero\n";
        },
        [](const Succ& s) {
            std::cout << "Succ with value: " << s.value << "\n";
        }
    }, n);
}

int main() {
    Nat zero = Zero{};
    Nat succ = Succ{42};

    printNat(zero); // Output: Zero
    printNat(succ); // Output: Succ with value: 42
}
```

The `std::variant` is a discriminated union/sum type that allows runtime polymorphism without requiring inheritance or virtual functions. `std::visit` dispatches the right callable (lambda in this example) based on the active type in the `std::variant`. Since `std::visit` only takes a single callable object but we want to use different lambdas based on the different possible underlying types (`Zero`/`Succ`), we use the `overloaded` struct to combine multiple lambdas together into a single callable. This is cleverly achieved by inheriting from all the lambdas and using template parameter pack expansion `(Ts... )`, and then bringing all the `operator()` overloads together into the struct via `using Ts::operator()...;`. Then we use CTAD in `overloaded(Ts...) -> overloaded<Ts...>;` to let the compiler automatically deduce the types of the lambdas passed to `overloaded`. 

Since we wrote this without a generic fallback, exhaustiveness is enforced -- we get a (pretty gnarly) compilation error if we add in some other type to the variant without adding a corresponding case in the `std::visit`. We don't have exhaustiveness checking provided natively, and we also don't have matching on multiple fields or nested matching.

In Lean this is easier on the eyes:

``` lean
inductive Nat : Type where
  | zero : Nat
  | succ : Nat → Nat

def isZero (n : Nat) : Bool :=
  match n with
  | Nat.zero => true
  | Nat.succ _ => false
  
#eval isZero Nat.zero -- `true`
#eval isZero (Nat.succ Nat.zero) -- `false`
```

We inductively define a `Nat` type with a base case `Nat.zero` and an inductive successor case `Nat.succ`. Then `isZero` pattern matches on the structure of `Nat`. The native language support in Lean means handling of all possible cases is enforced, and values are automatically destructured and bound.

# Dependent type systems ...and match?

Actually, Lean takes it a step further by supporting full dependent types. A dependent type is a type that can depend on runtime values. 

``` lean
def BoolToType x :=
  match x with
  | true => Nat
  | false => String
  
axiom n : Nat

axiom x : BoolToType (n % 2 == 0)
```
* This convoy example is from stepchowfun's Lean tutorial series! See [Sources](#sources)

Here the type of `x` depends on whether the value of `n` is even or odd. And let's say we want to do different things with `x` depending on the different types it could be. You might try naively pattern matching:

``` lean
-- #check
--   match n % 2 == 0 with
--   | true => x + 1
--   | false => x.length
```

But this is an issue -- Lean can't infer the specific type of `x` based on what it knows about `n`. Naive pattern matching doesn't work because it doesn't do *type refinement* on the result for each case such that each branch only needs to consider the specific value corresponding to that case. You'll get compiler errors on both match cases above. Specifically, in both branches `x` still has type `BoolToType (n % 2 == 0)`, which is why we can't use it as `Nat` or `String`.

# The convoy pattern and dependent pattern matching

Instead, let's use dependent pattern matching and the convoy pattern to "lift" the runtime value into the compile time type system. We construct a function which accepts an arbitrary value of the dependent type. Then we immediately call that function on the value we have, `x`. Dependent pattern matching means when we match on a value, it causes types mentioning that value to get refined.

``` lean
#check
  (
    match n % 2 == 0 with
    | true => fun y => @id Nat y + 1
    | false => fun y => y.length
    : BoolToType (n % 2 == 0) → Nat
  ) x
```

The key here is Lean creates an equality proof in each branch. For the `true` case Lean knows `n % 2 == 0 = true`, so `BoolToType (n % 2 == 0)` reduces to `BoolToType true` . Then we can use `@id Nat` to force `y`'s `BoolToTrue` type to be reduced to `Nat` type, which is needed for *type class resolution* of which `+` operator to use (`@ id` means the identity function with implicit arguments disabled). In the `false` case, Lean knows `n % 2 == 0 = false`, and the `.length` method directly tells Lean `y` 's type should be reduced down to a `String` via *method resolution*. 

And using the equality proof to carry information learned about each case of `x` is quite neat! Indeed, that's the essence of the convoy pattern: that information is convoyed/escorted into each branch to be refined, which enables expressiveness while maintaining type safety. (To be clear, naive pattern matching does maintain type safety too, by being conservative and rejecting.)

# Why can't C++ do something like this?

Stepping back, the answer lies in the differences in how C++ and Lean are compiled, and what each language wants to achieve.

In general, C++ has a hard wall between compile and run time. Types are checked at compile time, and values are computed at runtime. Types have to be erased before runtime for performance. C++ guarantees zero-cost abstraction, which means no runtime overhead for type safety. But by definition, dependent types depend on runtime values. On the other hand, Lean doesn't mind adding compilation time -- as an interactive theorem prover, Lean wants that compile-time correctness.

# Sources

[https://lean-lang.org/theorem_proving_in_lean4/Dependent-Type-Theory/#dependent-type-theory](https://lean-lang.org/theorem_proving_in_lean4/Dependent-Type-Theory/#dependent-type-theory)

[https://lean-lang.org/functional_programming_in_lean/Programming-with-Dependent-Types/#Functional-Programming-in-Lean--Programming-with-Dependent-Types](https://lean-lang.org/functional_programming_in_lean/Programming-with-Dependent-Types/#Functional-Programming-in-Lean--Programming-with-Dependent-Types)

[https://github.com/stepchowfun/proofs/tree/main/proofs_lean/tutorial](https://github.com/stepchowfun/proofs/tree/main/proofs_lean/tutorial)



Pattern Matching


>These are my notes while going through the book [Design Patterns in Modern C++20: Reusable Approaches for Object-Oriented Software Design](https://www.oreilly.com/library/view/design-patterns-in/9781484272954/) by Dmitri Nesteruk. Since they're notes, I may have direct code examples or quotes, and may omit things that may be notable to you but aren't to me. I definitely encourage getting a copy of this book for full context!

# CRTP (Curiously Recurring Template Pattern)

Key idea: inheritor passes itself as a template argument to its base class. One reason to do this: access a typed `this` pointer in a base class implementation: Let's say every child class of `SomeBase` has a `begin()/end()` defined for iteration. Can you iterate the object in a member of `SomeBase` instead of in the child class? `SomeBase` doesn't itself provide a `begin()/end()`, so you may think no! but using CRTP, derived class can pass information about *itself* to the base class:
``` cpp
struct MyClass : SomeBase<MyClass>
{
  class iterator {
	// your iterator defined here
  }
  iterator begin() const { ... }
  iterator end() const { ... }
}
```
so inside the base class you can cast `this` to a derived class type:
``` cpp
template <typename Derived>
struct SomeBase
{
  void foo()
  {
	for (auto& item : *static_cast<Derived*>(this))
	{
	  ...
	}
  }
}
```
What happens here when calling `MyClass::foo()`: `this` pointer gets cast from `SomeBase*` to `MyClass*` , the pointer gets dereferenced and iterated on using that range-based `for` which calls the `MyClass::begin()/end()`.

# Mixin Inheritance

Key idea: a class can be defined to inherit from its own template argument, allowing hierarchical composition of types.

``` cpp
template <typename T> struct Mixin : T
{
  ...
}
```

You can make an instance of `Foo<Bar<Baz>> x;` that implements traits of all three classes without having to construct a whole new `FooBarBaz` type. This is really useful with Concepts! We can clearly and elegantly constrain the type our mixin inherits from to use base type features without having to look at compile-time errors.

# Static Polymorphism

## First, the old-fashioned way:

Ex: building an alert systems that notifies via different mediums: email, SMS, Telegram, etc. With CRTP you can implement a base `Notifier` :

``` cpp
template <typename TImpl>
class Notifier {
public:
  void AlertSMS(string_view msg)
  {
    impl().SendAlertSMS(msg);
  }
  void AlertEmail(string_view msg)
  {
    impl().SendAlertEmail(msg);
  }
private:
  TImpl& impl() { return static_cast<TImpl&>(*this); }
  friend TImpl;
};
```

`TImpl` is a template argument, so compiler will check that `AlertSMS()` and `AlertEmail()` actually exist on the object, even though we didn't tell it that `TImpl` must inherit from `Notifier`.  So we can define this:

``` cpp
template <typename TImpl>
void AlertAllChannels(Notifier<TImpl>& notifier, string_view msg)
{
  notifier.AlertEmail(msg);
  notifier.AlertSMS(msg);
}
```

And then we can make `Notifier` implementations, like a no-op for testing:

``` cpp
struct TestNotifier: public Notifier<TestNotifier>
{
  void SendAlertSMS(string_view msg){}
  void SendAlertEmail(string_view msg){}
};

TestNotifier tn;
AlertAllChannels(tn, "testing!"); // just testing!
```

But this can be annoying because
- you have to have two separate, parallel APIs e.g. `AlertSMS/SendAlertSMS`
- the impl thing feels clunky. You'd expect base alert methods to be virtual and then impl class to override.
- `Timpl`'s interface isn't explicitly enforced, we just try to call them to check at runtime and rely on compiler errors.

## Now, with Concepts:

we can alleviate those issues by introducing a concept that requires those member functions:

``` cpp
template <typename TImpl>
concept IsANotifier = requires(TImpl impl) {
  impl.AlertSMS(string_view{});
  impl.AlertEmail(string_view{});
};
```

So we don't need the base `Notifier`:

``` cpp
template <IsANotifier TImpl>
void AlertAllChannels(TImpl& impl, string_view msg)
{
  impl.AlertSMS(msg);
  impl.AlertEmail(msg);
}

struct TestNotifier
{
  void AlertSMS(string_view msg) {}
  void AlertEmail(string_view msg) {}
};
```

# Properties

A property is just a combination of a (usually private) field and a getter/setter. This isn't part of the C++ standard (and you could implement this without any special language support), but we should mention the declaration specifier `property` you can use in most compilers:

``` cpp
class Person
{
  int age_;
public:
  int get_age() const { return age_; }
  void set_age(int value) { age_ = value; }
  __declspec(property(get=get_age, put=set_age)) int age;
};
```

Here `__declspec(property())` turns the getters and setters into virtual fields, so the compiler replaces any attempts to read/write to this field.

``` cpp
Person p;
p.age = 20; // calls p.set_age(20)
```

# SOLID Design Principles

## Single Responsibility Principle (SRP)

"Each class should have only one responsibility and therefore one reason to change."

Ex: A Journal class shouldn't have to deal with persistence/file saving, it should only need to change if e.g. you need to change how journal entries are stored. (Any situation that leads us to having to do a lot of tiny changes in lots of classes is probably a code smell!)

An extreme example of an antipattern here is the God object -- a huge class that tries to handle as many concerns as possible -- terrible monolithic monstrosity!
## Open-Closed Principle (OCP)

"open for extension but closed for modification" -- You shouldn't need to go back to code you've written and tested to change it.

Ex: You have a bunch of products, and you want to be able to filter them in many ways: by color, by size, by color and size...

``` cpp
enum class Color { Red, Green, Blue };
enum class Size { Small, Medium, Large };
struct Product
{
  string name;
  Color color;
  Size size;
};
```

Let's first separate (SRP) the filter (process that takes all items and only returns some) and the specification (the predicate definition to apply to a data element).

``` cpp
template <typename T> struct Specification
{
  virtual bool is_satisfied(T* item) = 0;
};

template <typename T> struct Filter
{
  virtual vector<T*> filter(
    vector<T*> items,
    Specification<T>& spec) const = 0;
};
```

Then the filter implementation is way simpler:

``` cpp
struct BetterFilter : Filter<Product>
{
  vector<Product*> filter(
    vector<Product*> items,
    Specification<Product>& spec) override
  {
    vector<Product*> result;
    for (auto& p : items)
      if (spec.is_satisfied(p))
        result.push_back(p);
    return result;
  }
};
```

And for actual specialized filters:

``` cpp
struct ColorSpecification : Specification<Product>
{
  Color color;
  explicit ColorSpecification(const Color color) : color{color} {}
  bool is_satisfied(Product* item) override {
    return item->color == color;
  }
};

Product apple{ "Apple", Color::Green, Size::Small };
Product tree{ "Tree", Color::Green, Size::Large };
Product house{ "House", Color::Blue, Size::Large };
vector<Product*> all{ &apple, &tree, &house };
BetterFilter bf;
ColorSpecification green(Color::Green);
auto green_things = bf.filter(all, green);
for (auto& x : green_things)
  cout << x->name << " is green";
```

And for compositional conditions:

``` cpp
template <typename T> struct AndSpecification : Specification<T>
{
  Specification<T>& first;
  Specification<T>& second;
  AndSpecification(Specification<T>& first,
    Specification<T>& second)
    : first{first}, second{second} {}
  bool is_satisfied(T* item) override
  {
    return first.is_satisfied(item) && second.is_satisfied(item);
  }
};

SizeSpecification large(Size::Large);
ColorSpecification green(Color::Green);
AndSpecification<Product> green_and_large{ large, green };
auto big_green_things = bf.filter(all, green_and_big);
for (auto& x : big_green_things)
  cout << x->name << " is large and green";
// Tree is large and green
```

>Side note: C++26 reflection + concepts can further make this way less clunky!

You can also embellish:

``` cpp
template <typename T> AndSpecification<T> operator&&
  (const Specification<T>& first,
   const Specification<T>& second)
{
  return { first, second };
}

SizeSpecification large(Size::Large);
ColorSpecification green(Color::Green);
auto big_green_things = bf.filter(all, green && large);
for (auto& x : big_green_things)
  cout << x->name << " is large and green" << endl;
```
## Liskov Substitution Principle (LSP)

"If an interface takes an object of type `Parent`, it should equally take an object of type `Child` without anything breaking."

Bad example:

``` cpp
class Rectangle
{
protected:
  int width, height;
public:
  Rectangle(const int width, const int height)
    : width{width}, height{height} { }
  int get_width() const { return width; }
  virtual void set_width(const int width) { this->width = width; }
  int get_height() const { return height; }
  virtual void set_height(const int height) { this->height = height; }
  int area() const { return width * height; }
};

class Square : public Rectangle
{
public:
  Square(int size): Rectangle(size,size) {}
  void set_width(const int width) override {
    this->width = height = width;
  }
  void set_height(const int height) override {
    this->height = width = height;
  }
};
```

Seems innocent, but then this easily blows up:

``` cpp
void process(Rectangle& r)
{
  int w = r.get_width();
  r.set_height(10);
  cout << "expected area = " << (w * 10)
    << ", got " << r.area() << endl;
}

Square s{5};
process(s); // expected area = 50, got 25
```

Ahh!!! Many possible solutions: perhaps the type `Square` shouldn't even exist and we should maybe use Factories for both rectangles and squares. Or maybe detect that a `Rectangle` is in fact a `Square`. You could also throw an exception but this would violate the "principle of least surprise" -- you'd probably expect a call to `set_width` to actually do something?
## Interface Segregation Principle (ISP)

"Split up interfaces so that implementers can pick and choose depending on their needs."

Ex: instead of having an interface for your multifunction printer that prints, scans, and faxes, you should have 3 separate interfaces for each.
## Dependency Inversion Principle (DIP)

"Depending on interfaces or base classes is better than depending on concrete types."
"Abstractions should not depend on details. Details should depend on abstractions."

We can achieve this via dependency injection:

Ex. Car has an engine, but needs to write to a log.

``` cpp
struct Engine
{
  float volume = 5;
  int horse_power = 400;
  friend ostream& operator<< (ostream& os, const Engine& obj)
  {
    return os
      << "volume: " << obj.volume
      << " horse_power: " << obj.horse_power;
  } // thanks, ReSharper!
};

struct ILogger
{
  virtual ~ILogger() {}
  virtual void Log(const string& s) = 0;
};

struct ConsoleLogger : ILogger
{
  ConsoleLogger() {}
  void Log(const string& s) override
  {
    cout << "LOG: " << s.c_str() << endl;
  }
};
```

Car needs both the engine and logging component. Let's define both of the dependent components as constructor parameters:

``` cpp
struct Car
{
  unique_ptr<Engine> engine;
  shared_ptr<ILogger> logger;
  Car(unique_ptr<Engine> engine,
      const shared_ptr<ILogger>& logger)
    : engine{move(engine)},
      logger{logger}
  {
    logger->Log("making a car");
  }
  friend ostream& operator<<(ostream& os, const Car& obj)
  {
    return os << "car with engine: " << *obj.engine;
  }
};
```

Then we bind `ILogger` to `ConsoleLogger`: "any time someone asks for an `ILogger` give them a `ConsoleLogger`"

```cpp
auto injector = di::make_injector(
  di::bind<ILogger>().to<ConsoleLogger>()
);
```

And now we can create our car:

``` cpp
auto car = injector.create<shared_ptr<Car>>();
```

So we have a `shared_ptr<Car>` pointing to a fully initialized `Car`, and to change the type of logger we just have to change a single place (the `bind` call) and then everywhere there's an `ILogger` it can now be the new logger. Helps with unit testing and allows us to use stubs/noops instead of mocks!


Design Patterns in Modern C++20

CppOnline26 Quiz Hunt


# Deducing `this`

> Python fans will love this one!

C++23 introduces the **explicit object parameter**, which allows the implicit `this` pointer in member functions to be made explicit. This is colloquially known as "deducing `this`". 

## Background & Motivation

Since C++03, member functions can have cv-qualifiers (`const` or `volatile`). It's common to see overloading based on these qualifiers. And since C++11, we can overload based on reference qualifiers. But that's quite verbose and not elegant! We'd have to rewrite the same logic many times, or delegate all methods to a separate `static` helper. Oftentimes, the only difference is in the types being accessed and used -- the implementation remains the same.

Pre-C++23, to perfectly forward the object itself (e.g., in a generic accessor or wrapper function), you needed all four overloads:

``` cpp
struct MyClass {
    void foo() & { /* lvalue non-const implementation */ }
    void foo() const & { /* lvalue const implementation */ }
    void foo() && { /* rvalue non-const implementation */ }
    void foo() const && { /* rvalue const implementation */ }
};
```

We want to be able to write a single member function template that can handle all combinations of `const`, non-`const`, l-value, and r-value references for the object on which it is called. 

## Enter C++23 deducing `this`.

With C++23 `this` keyword, we can condense all the perfect forwarding overloads into one generic implementation:

``` cpp
#include <utility>

struct MyClass {
    template <typename Self>
    void foo(this Self&& self) {
        // Use std::forward to preserve the original value category and constness
        internal_implementation(std::forward<Self>(self));
    }
};
```

As another benefit, we also get a cleaner implementation of the Curiously Recurring Template Pattern (CRTP). In traditional CRTP, the base class has to "know" the derived type via a template parameter. To access derived data, we have to cast the `this` pointer, which can be confusing for complex inheritance hierarchies, or if you accidentally cast to the wrong type. 

``` cpp
template <typename Derived>
struct Base {
    void interface() {
        // Confusion: 'this' is Base*, not Derived*. 
        // You MUST cast it, or the compiler won't see Derived's methods.
        static_cast<Derived*>(this)->implementation();
    }
};

struct Derived : Base<Derived> {
    void implementation() { /* ... */ }
};
```
If you have `struct Wrong : Base<Derived>`, the `static_cast` in the base class will compile but cause undefined behavior at runtime because it casts `Base` to a sibling type instead of itself. Confusing and hard to debug!

With C++23's deduced `this`, we can shift the template from class to function level, take out the `static_cast`, and have better type safety! The compiler can deduce the exact type of the object the method was called on, ensuring `self` is always the correct type. 

```cpp
struct Base {
    template <typename Self>
    void interface(this Self&& self) {
        // No static_cast needed! 
        // 'self' is automatically deduced as the Derived type.
        self.implementation();
    }
};

struct Derived : Base {
    void implementation() { /* ... */ }
};
```

Thirdly, deducing `this` greatly simplifies recursive lambda syntax. Traditionally, a lambda's body couldn't refer to itself because the object wasn't fully defined until the expression was complete. Here were some awkward workarounds:

- using `std::function`:

    ``` cpp
    #include <functional>
    #include <iostream>

    int main() {
        // Declare the std::function object first
        std::function<int(int)> fib = [&](int n) -> int {
            if (n <= 1) {
                return n;
            }
            // 'fib' is in scope here because it was declared previously
            return fib(n - 1) + fib(n - 2);
        };

        std::cout << "Fib(10) = " << fib(10) << std::endl; // Output: 55
    }
    ```
- using a generic lambda (with `auto&&` or `const auto&` parameter) that accepts itself as an argument to its own call operator, avoiding the overhead of `std::function`.
    ``` cpp
    #include <iostream>

    int main() {
        // The outer lambda defines the interface for the caller
        auto factorial = [](int n) {
            // The inner, generic lambda performs the actual recursion
            auto fact_impl = [](int n_val, const auto& self) -> int {
                if (n_val <= 1) {
                    return 1;
                }
                // Pass 'self' explicitly in the recursive call
                return n_val * self(n_val - 1, self);
            };
            // Initial call passes the implementation to itself
            return fact_impl(n, fact_impl);
        };

        std::cout << "Factorial(5) = " << factorial(5) << std::endl; // Output: 120
    }
    ```

- or the competitive programming variant defining the self-passing behavior directly:
    ``` cpp
    #include <iostream>

    int main() {
        // A single generic lambda that takes itself as the first argument
        auto fact = [&](auto&& self, int x) -> int {
            return x <= 1 ? 1 : x * self(self, x - 1);
        };

        std::cout << "Factorial(5) = " << fact(fact, 5) << std::endl; // Output: 120
    }
    ```
- in a functional manner, a generic Y-combinator (no, not the startup incubator, though that is what YC is named after) higher-order function can be defined. The Y-combinator takes a function that accepts "itself" as its first argument and handles the recursive binding automatically. (no, I don't really know what's happening here. #TODO learn lambda calculus and explain!)
    ``` cpp
    // A simple generic Y-combinator implementation (C++14/17)
    template<class R, class... Args>
    auto Y = [](auto f) {
        auto action = [=](auto action) -> std::function<R(Args...)> {
            return [=](Args&&... args) -> R {
                // The 'f' is called with a recursive version of itself (action(action))
                return f(action(action), std::forward<Args>(args)...);
            };
        };
        return action(action);
    };

    // Usage with a factorial function "generator"
    auto fact = Y<int, int>([](auto&& self, int val) {
        if (val < 2) {
            return 1;
        }
        return val * self(val - 1);
    });

    std::cout << fact(5); // Output: 120
    ```

But now we can use the `self` parameter as an alias for the lambda object within its scope, allowing for direct recursive calls.

``` cpp
// The 'self' parameter makes the lambda object available inside its body
auto factorial = [](this const auto& self, int n) -> int {
    if (n <= 1) return 1;
    return n * self(n - 1); // Directly call 'self'
};
// Call it normally, no extra arguments needed
static_assert(factorial(5) == 120, "factorial() incorrect"); //

```

Also, deducing `this` is once again a feature that works strongly with C++26 reflection! Deduction directly provides the instance of the object, including its derived type. Reflection will then allow you to introspect that deduced type at compile-time to see its members, methods, and attributes.


## How implemented 

#TODO


## Sources (some)

[https://www.sandordargo.com/blog/2022/02/16/deducing-this-cpp23](https://www.sandordargo.com/blog/2022/02/16/deducing-this-cpp23)

[https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/](https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/)

[https://antonkw.github.io/scala/y-combinator/](https://antonkw.github.io/scala/y-combinator/)

Deducing <code>this</code> in C++23


# `if consteval`

## `const` syntax timeline:
- `const` original language
- `constexpr` C++11
- `if constexpr` C++17
- `consteval` and `constinit` C++20
- `if consteval` C++23 aka "consteval if", colloquially

## Background & Motivation

`consteval` is an "immediate" function -- every call to it _has to be executed_ during compile time. The `constexpr` keyword indicates the _possibility_ of a function being run at compile-time. If the arguments to a `constexpr` function were all compile-time constants, the compiler _could_ evaluate the `constexpr` function at compile-time, but that would only be a compiler optimization (not required by the language, except in _manifestly constant-evaluated contexts_ that demand a constant expression (e.g. array bound). Here the compiler is required to perform evaluation at compile time). 

So pre C++23, calling `constexpr` from `consteval` does work, but calling `consteval` functions from `constexpr` functions does **not** work. After all, `constexpr` could be evaluated at run time. 

> Using `std::is_constant_evaluated()` also won't work. And we don't expect it to! We use `std::is_constant_evaluated()` in a `constexpr` function to select between a compile-time-friendly implementation and a potentially-faster runtime implementation. Function parameters are not `constexpr`, and using `std::is_constant_evaluated()` within a `constexpr` function doesn't change the overall potential for runtime function execution. The compiler must still be able to generate a valid runtime version of the entire function with all code paths, so this may cause static analysis errors / fail to compile. These failures prevent the possibility of a `consteval` call ending up in runtime code.

* all code examples are currently directly from Sandor Dargo's blog! See [Sources](#sources-some).

``` cpp
consteval int bar(int i) {
    return 2*i;
}

constexpr int foo(int i) {
    if (std::is_constant_evaluated()) {
        return bar(i);
    }
    return 2*i;
}

int main() {
  [[maybe_unused]] auto a = foo(5);
}
/*
main.cpp: In function 'constexpr int foo(int)':
main.cpp:6:14: error: 'is_constant_evaluated' is not a member of 'std'
    6 |     if (std::is_constant_evaluated()) {
      |              ^~~~~~~~~~~~~~~~~~~~~
main.cpp:7:19: error: 'i' is not a constant expression
    7 |         return bar(i);
      |                ~~~^~~

*/
```

## Introducing C++23 `if consteval`!

Enter `if consteval` in C++23! Now we can call `consteval` functions from `constexpr` ones. The syntax looks exactly as we had wanted `if (std::is_constant_evaluated)` to work, but we **can** invoke `consteval` functions if the `if` condition evaluates to `true`, aka when the context is constant-evaluated, but not necessarily explicitly declared so. We continue to safely prevent `consteval` calls ending up in runtime code! (Also, you don't need any header include)

``` cpp
consteval int bar(int i) {
    return 2*i;
}

int foo(int i) {
    if consteval {
        return bar(i);
    }
    return 2*i;
}

int main() {
  [[maybe_unused]] auto a = foo(5);
}
```

## How implemented 

#TODO

## Takeaways

The benefits from unlocking "call-`consteval`-from-`constexpr`" are in line with all motivations for expanding compile-time capabilities:

- We can implement different optimizations for compile time vs. runtime. `if consteval` allows the compiler to choose between a slow but simple-to-implement `constexpr` compile-time version, or a highly optimized (maybe assembly-level) runtime version.
- We can access compile-time library features (e.g. `std::source_location::current()`) when available during constant evaluation, while providing a fallback (or simply doing nothing) at runtime.
- We can use `if consteval` to wrap compile-time assertions (`static_assert`) or other static analysis code that should only be checked during compilation.
- In certain scenarios, we can generate and populate data structures or lookup tables entirely at compile time, avoiding runtime overhead.

We should point out the difference between C++23 `if consteval` and C++17 `if constexpr`. `if constexpr` is a compile-time conditional that causes the compiler to discard branches of code at compilation based on a `constexpr`. This differs from a regular `if` statement, where both branches are compiled, and the condition is evaluated at runtime. `if constexpr` is primarily used in generic template programming and largely supplants SFINAE/manual template specialization, where different code paths may be required based on the properties of a template type (e.g., using type traits like `std::is_integral_v`). And in fact C++26 reflection in concert with `if constexpr` vastly expands our compile-time and metaprogramming toolboxes.

## Sources (some)
[https://www.sandordargo.com/blog/2022/06/01/cpp23-if-consteval](https://www.sandordargo.com/blog/2022/06/01/cpp23-if-consteval)

abelianpi

Filter by Topic

Perfect Forwarding

Exploring CWG Defect Reports (Part 1)

Using Lean to Prove 1080 Sets

Lambdas and `std::function`

Pattern Matching

Design Patterns in Modern C++20

CppOnline26 Quiz Hunt

Deducing `this` in C++23

Understanding C++23 `if consteval`