How to write a `HeldOptional` variant of `Optional` that does not evaluate its second argument?

Question

How to specify optional arguments that take functional values made me wonder: Can we come up with a variant of Optional that allows to do the following:

lhs = x_;
g[lhs~HeldOptional~RandomReal[]] := x
DownValues@g

and get

{HoldPattern[g[Optional[x_, RandomReal[]]]] :> x}

Specifically, I want HeldOptional to evaluate the left hand side like all pattern construction constructs, while leaving the right argument untouched.

The following attempt does not work:

HeldOptional~SetAttributes~HoldRest
HeldOptional[x_, y_] := Optional[x, Unevaluated@y]

This gives the DownValue

{HoldPattern[g[x_ : Unevaluated[RandomReal[]]]] :> x}

such that g[] gives Unevaluated[RandomReal[]] instead of a random real.

Answer 1

Putting together idea from question to use function with HoldRest attribute, together with idea from QuantumDot's answer to use HoldPattern we get:

ClearAll[HeldOptional]
HeldOptional~SetAttributes~HoldRest
HeldOptional[x_, y_] := HoldPattern@Optional[x, y]

HoldPattern wraps whole Optional pattern, but since function has only HoldRest attribute, its firs argument evaluates before it's passed to held pattern.

Using HeldOptional we get definitions equivalent to requested one:

ClearAll[lhs, g]
lhs = x_;
g[lhs~HeldOptional~RandomReal[]] := x
DownValues@g
(* {HoldPattern[g[HoldPattern[x_ : RandomReal[]]]] :> x} *)

and desired behavior:

g[a]
(* a *)
g[]
(* 0.408798 *)
g[]
(* 0.0652214 *)
g[]
(* 0.587329 *)

Answer 2

This works:

ClearAll[DontEvaluateInOptional];
DontEvaluateInOptional~SetAttributes~HoldAllComplete;
DontEvaluateInOptional /: (h: Except[Optional])[l___, 
   HoldPattern@DontEvaluateInOptional[b___], r___] := h[l, r, b];

HeldOptional~SetAttributes~HoldRest
HeldOptional[x_, y_] := Optional[x, DontEvaluateInOptional@y]

lhs = x_;
g[lhs~HeldOptional~RandomReal[]] := x
DownValues@g

g[3]
g[]
g[]

Out[39]= {HoldPattern[g[x_:DontEvaluateInOptional[RandomReal[]]]]:>x}

Out[40]= 3

Out[41]= 0.0769485

Out[42]= 0.674345

This is a bit superior to the Unevaluated method I suggested first because it is stripped in more cases, but it cannot insert the default value into HoldAllComplete symbols:

ClearAll[f,g];
f~SetAttributes~HoldAllComplete
g[x_~HeldOptional~RandomReal[]] := f[x]
g[3]
g[]

Out[46]= f[3]

Out[47]= f[DontEvaluateInOptional[RandomReal[]]]