# Where are the two missing bits from \`Int\`?

**URL:** <https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962>\
**Category:** Learn\
**Created:** [October 29, 2023, 10:44am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962 "2023-10-29T10:44:39Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![qqwy](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/qqwy/32/1983_2.png) [@qqwy](https://discourse.haskell.org/u/qqwy)\
**Post date:** [October 29, 2023, 10:44am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/1 "2023-10-29T10:44:39Z")

</div>

In the [Haskell Report](https://www.haskell.org/definition/haskell2010.pdf) we can find:

> The finite-precision integer type Int covers at least  
> the range `[−2^29 , 2^29−1]`.

Which is very curious, because on a 32-bit platform it is more common to use one bit for the sign and the other 31 bits for the number, resulting in the range `[-2^31..2^31-1]`. I am not aware of any other language that uses the 30-bit range.

Also, it is quite easy to see using the methods of the `Bounded` typeclass that in modern-day GHC programs, the actual range of `Int` is the full 32-bit resp. 64-bit range.

Which begs the question: What historic reason is there for this peculiar range? Why are there two bits ‘missing’?

* * *

Now I _think_ I have an answer. However, it is very difficult to find resources about early Haskell development or about the internals of early GHC and other (pre-GHC) Haskell compilers. If someone who has been around in the Haskell community for longer can corroborate this I would be very happy 😊 !

### 1) Laziness tagging

To work with lazy values, you need some way to disambiguate not-yet-evaluated thunks from already-evaluated results.  
A very simple way to do this, is to use one bit in each pointer as a boolean ‘is this evaluated already?’ tag. (You can do this because on essentially all hardware a pointer always has to be word-aligned which means that the last few bits end up being unused.)  
The big drawback of this approach however, is that everywhere in your code you will now need to check on this tag.

This approach was used by the ‘Lazy Abstract Machine’ (LAM), which was used in GHC before the invention of the Spineless Tagless G-machine (STG).

The STG improved on this, by instead of needing a bit in the pointer, always store a callable closure. It’s just that after evaluating a thunk for the first time, its closure will be replaced with a closure which just immediately returns the value. _(In very broad strokes)_  
This is why the STG is ‘Tagless’.

### 2) Garbage collection

The other bit might have been used by the garbage collector. In the past (again, before the STG), there was no special support for ‘fully unboxed’ values. But obviously Haskell did still have its primitive types which needed to be stored and manipulated in some way. So an `Int` would just be a value which was stored on the stack. As mentioned above, one bit might have been set if it was still a pointer to a thunk, but if it was already evaluated, it would result in a plain value being present on the stack.

This poses a problem for the garbage collector: All pointer-values on the stack need to be considered as ‘live roots’ for the starting point of the collection process. But if we are mixing pointers and plain values on the stack, we need some way for the GC to know which is which!

I expect that the other bit of `Int` was used in the past for this reason. [‘Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine’](https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf) mentions this GC technique and that the STG wants to avoid it (Section 8.1).  
_(NOTE: I have not found concrete proof so far however that in the first versions of GHC before the STG or possibly in other Haskell Compilers (Hugs? York? Nottingham? Yale? Utrecht?) this particular approach to garbage collection was actually being used.)_

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [October 29, 2023, 11:16am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/2 "2023-10-29T11:16:28Z")

</div>

Various papers about implementation matters can be found here:

[Research papers/Runtime systems - HaskellWiki](https://wiki.haskell.org/Research_papers/Runtime_systems)

---

<div class="post-metadata">

**Author:** ![AntC2](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/antc2/32/1872_2.png) [@AntC2](https://discourse.haskell.org/u/AntC2)\
**Post date:** [October 30, 2023, 9:02am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/3 "2023-10-30T09:02:21Z")

</div>

> [@qqwy](#):
>
> In the [Haskell Report](https://www.haskell.org/definition/haskell2010.pdf) we can find: …

Exactly that wording is in the v1.0 Haskell report, April 1990. At that time, not all hardwares used a word size that was some power of two.

That 1990 section goes on

> … `Float` is a floating-point type, also implementation-defined; it is desirable that this type be at least equal in range and precision to the IEEE single precision type.

So both stipulations are there to assure programmers of scientific applications Haskell’s behaviour conforms with what they’re used to in Fortran.

> [@](#):
>
> Now I _think_ I have an answer. …

None of those hypotheses make sense to me. Why would the implementation put tagging _inside_ an `Int`? Tag pointers, certainly. Make your pointers point to blocks of 4 words so the low-order two bits aren’t needed so can carry tags, OK. But the low-order two bits of an `Int` certainly can’t be abused like that. And that sort of abuse doesn’t extend to `Float`s, `Double`s or `Char`s.

Neither will that abuse be safe passing an `Int` to a FFI or returning `Int` to a caller using a Haskell function from some other language. Haskell is all about type safety.

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [October 30, 2023, 1:37pm UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/4 "2023-10-30T13:37:14Z")

</div>

It’s difficult to answer where those two bits “are”, because the Haskell language spec is just a specification, not an implementation. Clearly it was written with some kind of tagged integer representation in mind, but at least as far as GHC is concerned, these tag bits _inside `Int` representation_ are not used. I know that, for example, the Lean theorem prover _does_ use such tags to eliminate Int boxes, but GHC does not. It has other, more general means to get rid of those boxes that don’t require special casing for `Int`s.

GHC also makes use of pointer tagging, but for a different mechanism: Encoding evaluatedness (your “Laziness tagging”) using the ordinal of the data constructor (+1) inside the tag. See [pointer tagging · Wiki · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/pointer-tagging).

This pointer tagging mechanism is different to the tagging mechanism that is avoided in “tagless” STG; note that all heap objects have a uniform representation with something akin to runtime type information/virtual table that is accessed by indirection. Indirections are costly and GHC uses pointer tagging to avoid following those indirections in many cases by looking at the pointer tag.

In fact, for some heap objects GHC wants to adopt an “always tagged” invariant, in which case some entry code can be dropped altoghether/simply lead to a crash, further subverting the “tagless” point that is part of STG.

* * *

Don’t think about the meaning of the acronym STG, every part of it is just confusing and irrelevant. STG is just (one of?) the first instance of a practical useful kind of intermediate representation for functional languages that became standard. The equivalent in OCaml would be [`flambda`](https://github.com/ocaml/ocaml/blob/14d9ab10567d1a6d1d70c24b04656d9e44b3aacb/middle_end/flambda/flambda.mli#L86-L110), I think: It is in ANF (the property of a program where every non-variable argument is let-bound thus given a name) as well. Similarly, Lean has an IR called [“IR”](https://github.com/leanprover/lean4/blob/db281f60fe5317bff508bf1a3146879bea8d7cd4/src/Lean/Compiler/IR/Basic.lean#L193-L221); in ANF as well, and supporting saturated fast calls as well as unsaturated slow calls. The concepts are the same, the names are different.

Why was STG the first? I think because ANF is a necessary requirement to compile lazy programs, plus Simon identified that it’s important to have a way to handle currying/bulk applications efficiently (previous calculi only apply one arg at a time). Compilation of call-by-value languages was comparatively simple, but ultimately all optimising compilers want to cope with currying well and turning your program into ANF seems to be the only way to do so without losing your mind.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [October 30, 2023, 4:28pm UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/5 "2023-10-30T16:28:59Z")

</div>

> [@sgraf](#):
>
> Don’t think about the [original] meaning of the acronym STG, every part of it is [now] just confusing and irrelevant.

…and probably as a result, an alternative definition (from around the turn of the millennium, as I dimly recall) to search for is `Shared Term Graph machine` e.g:

`https://hsyl20.fr/home/files/papers/2022-ghc-modularity.pdf`

But most articles and papers still refer to the _“older”_ definition.

* * *

At various times there also was interest in a intermediate language for both Haskell and Standard ML:

- [Bridging the gulf: a common intermediate language for ML and Haskell](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.8673&rep=rep1&type=pdf) (1998)

- [Haskell Is Not Not ML](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.1959&rep=rep1&type=pdf) (2006)

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [October 30, 2023, 4:55pm UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/6 "2023-10-30T16:55:43Z")

</div>

> “Shared term graph”

Interesting … reinterpretation of the acronym. I’m not convinced we need the “graph” either (I don’t think that graph reduction is the most intuitive model to explain laziness, especially since [A call-by-need lambda calculus | Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages](https://dl.acm.org/doi/10.1145/199448.199507)), but don’t have a replacement to offer.

> At various times there also was interest in a intermediate language for both Haskell and Standard ML:

Both of these references are _very_ interesting, thank you!

I think that for a pure variant of ML (“Strict Haskell” with different syntax, or Purescript/Idris), in large parts this language could be just STG. Nonrec let is simply `Case`, letrec is STG’s `Let (Rec ...)`. Note that ML’s value restriction on letrec means that we never have to ask “is this let binding strict or lazy?”. Of course, the '98 paper is concerned with side-effects in SML, which warrants a more first class integration of commands. But even newer strict languages try to isolate side-effects into certain type constructors, so I’m not sure that it’s worth having a separate language-level concept.

As it happens, we were just discussing today (for a repeated time) how to equip STG with an “ABI” that allows us to have first class call-by-value functions: [#24136: Convey ABI/calling-convention between modules (even with -O0) · Issues · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/issues/24136).  
The goal is to form the bedrock for a truly levity polymorphic code generation pipeline, where you can write strict programs just as well as lazy programs, with the stretch goal of re-using inherently strict functions such as `foldl` in the 2006 paper in both flavours. Still a lot of engineering to do here.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [October 30, 2023, 10:10pm UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/7 "2023-10-30T22:10:04Z")

</div>

> [@sgraf](#):
>
> I’m not convinced we need the “graph” either […] but don’t have a replacement to offer.

Have I got a deal for you!

- for theoreticians:  
[Call-by-Need Is Clairvoyant Call-by-Value](https://www.cs.nott.ac.uk//~pszjlh/cbncbv.pdf) ([_2019_](https://www.cs.nott.ac.uk//~pszjlh/cbncbv_erratum.pdf) )

- for implementors:  
[On Inter-deriving Small-step and Big-step Semantics: A Case Study for Storeless Call-by-need Evaluation](http://www.zerny.dk/danvy-al-tcs12.pdf) (2012).

(Alas, the acronym _“STM”_ has already been taken…)

* * *

> Of course, the '98 paper is concerned with side-effects in SML, which warrants a more first class integration of commands.

Not necessarily - read section 5.1 (_First-order versus higher-order_, page 29 of 33) in [How to Declare an Imperative](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf) (1997). But failing that, there’s the evidence-passing style as used by Linear Haskell:

> [@Since Haskell has linear types so we can track resources, why can't we disable the GC like in ATS?](http://discourse.haskell.org/t/since-haskell-has-linear-types-so-we-can-track-resources-why-cant-we-disable-the-gc-like-in-ats/7951/12):
>
> No, you shouldn’t need pragmas. As the abstract says: Soundness of linear constraints is ensured by the fact that they desugar into Linear Haskell. Linear types permeate all the way into Core, so optimizations should preserve them, although I believe that is not yet checked at the moment. @romes is working on that. But any problems with that should be seen as bugs in GHC, not as problems with linear constraints. Also, the second argument of swap is not a good example because that’s just an …

* * *

> As it happens, we were just discussing today [_again!_] how to equip STG with an “ABI” that allows us to have first class call-by-value functions:

~~_That’s odd: from [Making a Fast Curry](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.6776&rep=rep1&type=pdf) (2004), I thought the STG language was already strict._~~

Edit: from that paper, I presumed an implementation of the STG language in another strict language would be a simple matter of replacing the local bindings `v = e` in each `Let`-expressions with calls to e.g. `v = halloc(e);` with the result of the `Let`-expression immediately following:

```
Let b1 = e1; ... bN = eN; in result
```

therefore being expanded to:

```
b1 = halloc(e1);
     ⋮ 
bN = halloc(eN);
{- code
    for
    result -};
```

So in that very specific sense, there’s already a strict variant of the STG language lurking in the original one - it just needs to be _“exposed”_.

Perhaps the _“strict Core”_ variant devised in [Types are Calling Conventions](https://www.researchgate.net/profile/Simon-Peyton-Jones/publication/221562931_Types_are_calling_conventions/links/0c960517e31f4ad9b5000000/Types-are-calling-conventions.pdf) (2009) could be of some use, despite it being (apparently) [superseded](https://www.researchgate.net/profile/Paul-Downen/publication/343413492_Kinds_are_calling_conventions/links/5f3aeddda6fdcccc43d0e45a/Kinds-are-calling-conventions.pdf)…

* * *

> Both of these references are _very_ interesting, thank you! […]

…getting back on-topic: were Standard ML’s `int` values also similarly limited in size back then (1990-1997)? If so, the appropriate standard reference for that language ought to have the answer to the original question.

---

<div class="post-metadata">

**Author:** ![AntC2](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/antc2/32/1872_2.png) [@AntC2](https://discourse.haskell.org/u/AntC2)\
**Post date:** [October 31, 2023, 6:53am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/8 "2023-10-31T06:53:12Z")

</div>

> [@sgraf](#):
>
> at least as far as GHC is concerned, these tag bits _inside `Int` representation_ are not used.

Neither in Hugs 2006. `Int`’s range is `[-2^31 , 2^31 - 1]` – on a Windows machine.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [October 31, 2023, 9:21am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/9 "2023-10-31T09:21:32Z")

</div>

I think Yale Haskell might have inherited some limitations around integers from Common Lisp. There’s some info about the implementation of CMU Common Lisp here:

> **[Fixnums (Design of CMU Common Lisp)](https://cmucl.org/docs/internals/html/Fixnums.html)**
>
> Fixnums (Design of CMU Common Lisp)

> 40.4 Fixnums
> 
> A fixnum has one of the following formats in 32 bits:
> 
> ```
> -------------------------------------------------------
> | 30 bit 2's complement even integer | 0 0 0 |
> -------------------------------------------------------
> 
> ```
> 
> or
> 
> ```
> -------------------------------------------------------
> | 30 bit 2's complement odd integer | 1 0 0 |
> -------------------------------------------------------
> 
> ```
> 
> Effectively, there is one tag for immediate integers, two zeros. This buys one more bit for fixnums, and now when these numbers index into simple-vectors or offset into memory, they point to word boundaries on 32-bit, byte-addressable machines. That is, no shifting need occur to use the number directly as an offset.
> 
> This format has another advantage on byte-addressable machines when fixnums are offsets into vector-like data-blocks, including structures. Even though we previously mentioned data-blocks are dual-word aligned, most indexing and slot accessing is word aligned, and so are fixnums with effectively two tag bits.
> 
> Two tags also allow better usage of special instructions on some machines that can deal with two low-tag bits but not three.
> 
> Since the two bits are zeros, we avoid having to mask them off before using the words for arithmetic, but division and multiplication require special shifting.

---

<div class="post-metadata">

**Author:** ![AntC2](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/antc2/32/1872_2.png) [@AntC2](https://discourse.haskell.org/u/AntC2)\
**Post date:** [November 1, 2023, 12:46am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/10 "2023-11-01T00:46:19Z")

</div>

> [@jaror](#):
>
> when these numbers index into simple-vectors or offset into memory,

Thanks, But, but! A type that represents “offset into memory” isn’t an (Haskell) `Int`. (That is, they might both use the same memory representation – that is, a full word – but the type system is all about the _logical_ properties of a type, not its representation.)

The “index into simple-vectors” chimes with what the Haskell report 1.0 1990 goes on to say following @qqwy’s quote:

> The range chosen [for `Int`] by an implementation must … and should be large enough to serve as array indices.

That talk of indices is no longer in the H2010 Report. And neither should it be: you can index your array by any type in `Ix`, I would have thought(?) (Class `Ix` is spec’d in the v1.0 Report.)

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [November 1, 2023, 9:08am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/11 "2023-11-01T09:08:14Z")

</div>

I’m saying the reason for those two missing bits is because the corresponding common lisp type, `fixnum`, is also missing two bits. And that in turn is because common lisp needs to retain all type information at run time. [CMU Common Lisp has 8 (3-bit) primitive types](https://cmucl.org/docs/internals/html/Tagging.html) and two of those are used for `fixnum`. The reason for choosing the specific tags `100` and `000` for `fixnum` is because that choice allows for faster array indexing.

---

<div class="post-metadata">

**Author:** ![hsyl20](https://avatars.discourse-cdn.com/v4/letter/h/b4bc9f/32.png) [@hsyl20](https://discourse.haskell.org/u/hsyl20)\
**Post date:** [November 1, 2023, 10:08am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/12 "2023-11-01T10:08:10Z")

</div>

While I’ve used it in the GHC modularity paper, I haven’t invented the different meaning for the STG acronym. Sadly I don’t remember exactly where I’ve read that STG stood for “Shared Term Graph” when talking about the language, perhaps in [http://ac.inf.elte.hu/Vol\_036\_2012/117\_36.pdf](http://ac.inf.elte.hu/Vol_036_2012/117_36.pdf) but I’m not sure.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [November 1, 2023, 11:24am UTC](https://discourse.haskell.org/t/where-are-the-two-missing-bits-from-int/7962/13 "2023-11-01T11:24:19Z")

</div>

`o_0` …er, yes: I’ve assumed that the alternate definition, while not common knowledge, was known by some to be pre-existing; post updated.

After rummaging though some of my old archives…it’s earliest appearance I can find is in GHC 0.29 - from `ghc/compiler/stgSyn/StgSyn.lhs`:

* * *

```
%
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1995
%
\section[StgSyn]{Shared term graph (STG) syntax for spineless-tagless code generation}
```

* * *

Since then, that definition just languished in obscurity and continues to do so…