<p>Fixpoint of type addition or type multiplication is no big deal. You just need to store data in heap. Haskell does this well for lists for example:</p>
<pre><code>data [a] = [] | a : [a]
</code></pre>
<p>Yet Haskell also permits fixpoint of type exponentiation. I'll take the following example:</p>
<pre><code>newtype FixPower = FixPower {appFixPower :: FixPower -&gt; Bool}
</code></pre>
<p>Some examples of values of this type include:</p>
<pre><code>example1 = FixPower (\_ -&gt; False)
exmaple2 = FixPower (\_ -&gt; True)
example3 = FixPower (`appFixPower` example1)
example4 = FixPower (`appFixPower` example4)
example5 = FixPower (not . `appFixPower` example5)
example6 = FixPower (join appFixPower)
</code></pre>
<p>I cannot even grasp how these values are stored in hardware. I don't see how to imitate this type in (relatively) low-level languages such as C. Does this involve some unsafe casting of function pointers? Or is there some other way?</p>

<implementation><types><functions>
How is fixpoint of type exponentiation implemented?
CC BY-SA 4.0
2023-05-23T02:56:55.787Z
Just because C has no spelling for it doesn’t mean it can’t exist. Function pointers are all the same in the hardware.
Bbrk24
CC BY-SA 4.0
2023-05-23T12:21:35.773Z
OP posted a similar question on StackOverflow 2 years ago, if that's interesting to anyone: https://stackoverflow.com/q/68735804
pxeger
<p>In GHC Haskell:</p>
<ul>
<li><code>FixPower</code> has kind <code>Type</code></li>
<li><code>Type</code> is a synonym of <code>TYPE LiftedRep</code></li>
<li><code>LiftedRep</code> is a synonym of <code>'BoxedRep 'Lifted</code></li>
<li><code>BoxedRep</code> indicates that this object is represented by a pointer</li>
<li><code>Lifted</code> indicates that the pointer may be a lazy computation, not just a value</li>
<li><code>(-&gt;)</code> is a synonym of <code>FUN</code></li>
<li><code>FUN</code> has kind <code>forall r1 r2. TYPE r1 -&gt; TYPE r2 -&gt; Type</code></li>
<li>In this case, <code>r1</code> and <code>r2</code> are both instantiated to <code>LiftedRep</code> as well</li>
</ul>
<p>Therefore, <code>FixPower</code> is a closure thunk pointer, whose underlying function pointer takes a pointer of the same description, and returns a <code>Bool</code> thunk pointer.</p>
<p>If we ignore laziness and closures, and just focus on the essence of the function itself, a translation to C is surprisingly direct:</p>
<pre><code>typedef struct FixPower {
  bool (*app)(struct FixPower);
} FixPower;
</code></pre>
<pre><code>// FixPower (const False)
bool const_false(FixPower fp) { return false; }
FixPower example_false = (FixPower){ .app = &amp;const_false };
</code></pre>
<pre><code>// FixPower (const True)
bool const_true(FixPower fp) { return true; }
FixPower example_true = { const_true };
</code></pre>
<pre><code>int main(int argc, char **argv) {
  bool result = example_true.app(example_false);
  printf(&quot;%s\n&quot;, result ? &quot;true&quot; : &quot;false&quot;);
  return 0;
}
</code></pre>
<blockquote>
<p>Does this involve some unsafe casting of function pointers?</p>
</blockquote>
<p>No, you do need a <code>struct</code> in order to be able to express a self-referential type definition in C, just as you need a <code>newtype</code> in Haskell. But C has no problem with it, as long as the type is finite in size—which is so, if the self-reference goes through an indirection, as in a more familiar case like a linked list:</p>
<pre><code>struct Node {
  int value;
  struct Node *next;
};
</code></pre>
<p>In <code>FixPower</code>, the pointer just happens to be a <em>function</em> pointer, rather than a <em>data</em> pointer. Note that we can pass <code>struct FixPower</code> <em>by value</em> to the function call, since it’s just a function pointer, which has a fixed and finite size. This is really the essence of representation-hiding: <code>sizeof(T *)</code> is independent of <code>sizeof(T)</code>.</p>
<p>Another way of thinking of this type, and <a href="https://doisinkidney.com/posts/2021-03-14-hyperfunctions.html" rel="noreferrer">hyperfunctions</a> more generally, is as a chain of cooperatively scheduled coroutines, navigating over a tree of possible computations.</p>
<p>A <code>FixPower</code> value represents a label for a computation, which is passed a “next routine” label by its caller. It can <em>return</em> a result back up the tree to its caller—in this case just a <code>Bool</code>, but in general it could be any value. Before the routine returns, it has the chance to <em>yield</em> down the tree to the next routine, as many times as it likes. And each time it yields, it’s allowed to decide which routine will be “next” for that subtree.</p>

CC BY-SA 4.0
2023-05-23T18:34:15.083Z
2023-05-23T19:18:45.897Z
2023-05-23T19:18:45.897Z
Jon Purdy
# How is fixpoint of type exponentiation implemented?
Posted by: username_0 on 2023-05-23
Fixpoint of type addition or type multiplication is no big deal. You just need to store data in heap. Haskell does this well for lists for example:
data [a] = [] | a : [a]

Yet Haskell also permits fixpoint of type exponentiation. I'll take the following example:
newtype FixPower = FixPower {appFixPower :: FixPower -> Bool}

Some examples of values of this type include:
example1 = FixPower (\_ -> False)
exmaple2 = FixPower (\_ -> True)
example3 = FixPower (`appFixPower` example1)
example4 = FixPower (`appFixPower` example4)
example5 = FixPower (not . `appFixPower` example5)
example6 = FixPower (join appFixPower)

I cannot even grasp how these values are stored in hardware. I don't see how to imitate this type in (relatively) low-level languages such as C. Does this involve some unsafe casting of function pointers? Or is there some other way?
**Tags:** implementation types functions
> **Comments:**
> **username_1**: Just because C has no spelling for it doesn’t mean it can’t exist. Function pointers are all the same in the hardware.  
> **username_2**: OP posted a similar question on StackOverflow 2 years ago, if that's interesting to anyone: https://stackoverflow.com/q/68735804  
---
## 1 answers
### Answer by username_3 on 2023-05-23. Score: 7 | Accepted answer
In GHC Haskell:

FixPower has kind Type
Type is a synonym of TYPE LiftedRep
LiftedRep is a synonym of 'BoxedRep 'Lifted
BoxedRep indicates that this object is represented by a pointer
Lifted indicates that the pointer may be a lazy computation, not just a value
(->) is a synonym of FUN
FUN has kind forall r1 r2. TYPE r1 -> TYPE r2 -> Type
In this case, r1 and r2 are both instantiated to LiftedRep as well

Therefore, FixPower is a closure thunk pointer, whose underlying function pointer takes a pointer of the same description, and returns a Bool thunk pointer.
If we ignore laziness and closures, and just focus on the essence of the function itself, a translation to C is surprisingly direct:
typedef struct FixPower {
  bool (*app)(struct FixPower);
} FixPower;

// FixPower (const False)
bool const_false(FixPower fp) { return false; }
FixPower example_false = (FixPower){ .app = &const_false };

// FixPower (const True)
bool const_true(FixPower fp) { return true; }
FixPower example_true = { const_true };

int main(int argc, char **argv) {
  bool result = example_true.app(example_false);
  printf("%s\n", result ? "true" : "false");
  return 0;
}


Does this involve some unsafe casting of function pointers?

No, you do need a struct in order to be able to express a self-referential type definition in C, just as you need a newtype in Haskell. But C has no problem with it, as long as the type is finite in size—which is so, if the self-reference goes through an indirection, as in a more familiar case like a linked list:
struct Node {
  int value;
  struct Node *next;
};

In FixPower, the pointer just happens to be a function pointer, rather than a data pointer. Note that we can pass struct FixPower by value to the function call, since it’s just a function pointer, which has a fixed and finite size. This is really the essence of representation-hiding: sizeof(T *) is independent of sizeof(T).
Another way of thinking of this type, and hyperfunctions more generally, is as a chain of cooperatively scheduled coroutines, navigating over a tree of possible computations.
A FixPower value represents a label for a computation, which is passed a “next routine” label by its caller. It can return a result back up the tree to its caller—in this case just a Bool, but in general it could be any value. Before the routine returns, it has the chance to yield down the tree to the next routine, as many times as it likes. And each time it yields, it’s allowed to decide which routine will be “next” for that subtree.
---
