# Yellow Post-Asymptotic-Giant-Branch Stars as Standard Candles. I.
Calibration of the Luminosity Function in Galactic Globular Clusters

Robin Ciardullo Department of Astronomy & Astrophysics, The Pennsylvania State
University, University Park, PA 16802, USA  Institute for Gravitation and the
Cosmos, The Pennsylvania State University, University Park, PA 16802, USA
Howard E. Bond Department of Astronomy & Astrophysics, The Pennsylvania State
University, University Park, PA 16802, USA  Space Telescope Science Institute,
3700 San Martin Dr., Baltimore, MD 21218, USA  Brian D. Davis Department of
Astronomy & Astrophysics, The Pennsylvania State University, University Park,
PA 16802, USA  Michael H. Siegel Department of Astronomy & Astrophysics, The
Pennsylvania State University, University Park, PA 16802, USA

(Accepted April 12, 2022)

###### Abstract

We use results of a survey for low-surface-gravity stars in Galactic (and LMC)
globular clusters to show that “yellow” post-asymptotic-giant-branch (yPAGB)
stars are likely to be excellent extragalactic standard candles, capable of
producing distances to early-type galaxies that are accurate to a few percent.
We show that the mean bolometric magnitude of the 10 known yPAGB stars in
globular clusters is $\langle M_{\rm bol}\rangle=-3.38\pm 0.03$, a value that
is $\sim$0.2 mag brighter than that predicted from the latest post-horizontal-
branch evolutionary tracks. More importantly, we show that the observed
dispersion in the distribution is only 0.10 mag, i.e., smaller than the
scatter for individual Cepheids. We describe the physics that can produce such
a small dispersion, and show that, if one restricts surveys to the color range
$0.0\lesssim(B-V)_{0}\lesssim 0.5$, then samples of non-variable yPAGB stars
can be identified quite easily with a minimum of contamination. The bright
absolute $V$ magnitudes of these stars ($\langle M_{V}\rangle=-3.37$) make
them, by far, the visually brightest objects in old stellar populations and
ideal Population II standard candles for measurements out to $\sim$10 Mpc with
current instrumentation. A Hubble Space Telescope survey in the halos of
galaxies in the M81 and Sculptor groups could therefore serve as an effective
cross-check on both the Cepheid and TRGB distance scales.

stars: AGB and post-AGB — globular clusters: general — galaxies: distances and
redshifts

††journal: ApJ

##  1 Introduction

Our understanding of cosmology has come a long way in the past quarter
century. In the mid-1980’s, the cosmic distance scale was uncertain to a
factor of two, and astronomers struggled to reconcile measurements of the
Hubble constant, the ages of globular clusters (GCs), and the matter density
of the universe (e.g., van den Bergh, 1990; Huchra, 1992). Now, $H_{0}$ is
known to much better than 10% (e.g., Freedman et al., 2001; Bennett et al.,
2013; Riess et al., 2016; Planck Collaboration et al., 2020), dark matter has
been modeled with precision (e.g., Springel et al., 2005; Klypin et al., 2011;
Vogelsberger et al., 2014), and the problem of GC ages has been resolved
through the discovery of dark energy (e.g., Schmidt et al., 1998; Perlmutter
et al., 1999).

Nevertheless, there are inconsistencies, and the most disconcerting arguably
involve our knowledge of the extragalactic distance scale and the expansion of
the universe. The physical scale of the baryonic acoustic oscillations, as
measured by the WMAP and Planck spacecraft, is determined by simple physics
and the expansion rate (i.e., the Hubble parameter) of the early universe. If
dark energy is the manifestation of a cosmological constant, the early-
universe Hubble parameter can be tied directly to the present-day value of
$H_{0}$; this relation, plus the curvature of the universe, implies a local
value of $H_{0}=67.37\pm 0.54$ km s-1 Mpc-1 (Planck Collaboration et al.,
2020). However, determinations of $H_{0}$ based on Type Ia supernovae (SNe
Ia), as calibrated by the Cepheid period-luminosity relation, yield
significantly larger values, with two recent measurements giving
$H_{0}=73.2\pm 1.3$ and $73.04\pm 1.04\rm\,{\>\rm km\>s^{-1}}\,Mpc^{-1}$
(Riess et al., 2021a, b). Similarly, the tip-of-the-red-giant-branch (TRGB)
calibration of SNe Ia luminosities yields only marginal agreement with the
microwave background, $H_{0}=69.6\pm 0.8\,\rm(statistical)\pm
1.9\,(systematic)\,{\>\rm km\>s^{-1}}\,Mpc^{-1}$ (Freedman et al., 2020),
while measurements from megamasers (Pesce et al., 2020) and gravitationally
lensed quasars (Wong et al., 2020) also support these higher values. Either
there is a systematic problem with the local scale of the universe, or the
cosmological-constant interpretation of dark energy is incorrect and “new
physics” is needed to understand the expansion history of the universe (see,
e.g., Di Valentino et al., 2021).

One way to improve upon the current situation is to find additional
calibrators for the intrinsic brightnesses of SNe Ia. At first glance, there
is no shortage of candidates, as the distance ladders presented by Ciardullo
(2012) and de Grijs (2013) list over a dozen different methods that might
serve to cross-check measurements of the local Hubble expansion. However, to
be competitive with the Cepheid and TRGB techniques, a standard candle must
ideally (1) have a strong theoretical basis, (2) be well-calibrated via
measurements within the Milky Way and Large Magellanic Cloud, (3) be capable
of reaching the nearest well-mixed clusters for the calibration of the
surface-brightness-fluctuation method (Blakeslee et al., 2021), as well as
Type Ia supernovae, and (4) have a small ($\lesssim$10%) dispersion in their
predicted luminosities. These conditions present problems for most of the
well-known distance methods.

Here we present an exploratory calibration of an extragalactic standard candle
that shows promise for satisfying these criteria: the intermediate-temperature
(yellow) post-asymptotic-giant-branch (hereafter yPAGB) stars of old stellar
populations. In §2, we review the reasons why these stars should make
excellent Population II distance indicators, and in §3, we test our conjecture
using the $V$-band magnitudes and colors of low-surface-gravity stars in
Galactic GCs. In §4 and §5, we describe the best way to use yPAGB stars as
standard candles and show that the observed scatter in their $V$-band
magnitudes is better than that for Cepheids at a fixed period. In §6, we
discuss the effect that stellar population has on the number of yPAGB stars in
a galaxy and argue that a population’s far-UV minus $V$-band color is the best
predictor for the success of a yPAGB survey. Finally, in §7, we compare the
efficiency of yPAGB surveys to those for Cepheids and the TRGB and discuss the
utility of this new technique for the calibration of SNe Ia luminosities.

##  2 Theoretical Post-Horizontal-Branch Evolution

The post-horizontal-branch (post-HB) evolution of low-mass stars is
illustrated in the observational color-magnitude diagram (CMD) in Figure 1.
Here we plot the CMD (visual absolute magnitude, $M_{V}$, versus reddening-
corrected $B-V$ color) for members of a typical GC, M79. The data are from
Davis et al. (2022, hereafter D22), and field interlopers have been removed as
described in that paper. Superposed are theoretical post-HB evolutionary
tracks111We thank Marcelo Miller Bertolami for sending us detailed tables of
these tracks with a finer time resolution than given in the Moehler et al.
(2019) paper. from a recent paper by Moehler et al. (2019). These tracks have
been converted from luminosity and effective temperature to the observational
quantities using the online PARSEC YBC web
tool222http://stev.oapd.inaf.it/YBC/ (Chen et al., 2019). For clarity, the
tracks have been smoothed by omitting rapid excursions produced by helium
shell flashes during late evolutionary stages, as discussed in more detail in
D22.

Following the ignition of core helium burning at the tip of the RGB, a star
moves to the zero-age horizontal branch (ZAHB), with its initial position
determined by its envelope mass: objects with larger envelope masses reside on
the red end of the ZAHB, while those with lower-mass envelopes inhabit the
blue end of the sequence. When core helium is exhausted, the star brightens
due to the release of gravitational potential energy from the core and nuclear
energy from the hydrogen-burning shell. During this thick shell-burning phase,
the star moves redward in the CMD to the base of the asymptotic giant branch
(AGB), and then rapidly increases in luminosity. Eventually the star’s helium
shell burning becomes unstable, and the envelope gets eaten away, both by mass
being deposited onto the core and by material being lost in a superwind. The
process continues until the envelope mass is reduced to
$\sim\\!0.005\,M_{\odot}$, at which point the star begins its blueward
traversal of the CMD and becomes a post-AGB star. Note that, as the figure
shows, M79 contains two bright members that lie on post-AGB tracks, as
discussed by Bond et al. (2016) and D22.

Figure 1: Color-magnitude diagram showing four post-red-giant evolutionary
tracks with metallicity $\rm[M/H]=-1.5$. The tracks are from Moehler et al.
(2019), and are for stars that arrive on the zero-age horizontal branch with
masses of 0.55, 0.60, 0.65, and $0.75\,M_{\odot}$. The thick black line traces
the zero-age horizontal branch. Luminosity and effective temperature have been
converted to visual absolute magnitude and $B-V$ color as described in the
text. Underlying the tracks is the color-magnitude diagram of the globular
cluster M79 (Davis et al., 2022). The tracks illustrate how stars evolve off
the zero-age horizontal branch to the base of the AGB, and then eventually to
the post-AGB phase. Note that M79 contains two stars that lie on post-AGB
tracks. Post-AGB evolution for an individual stars is at a nearly constant
bolometric luminosity, which depends on the star’s core mass. The brightening
in $M_{V}$ along the post-AGB tracks is due to the decreasing bolometric
correction as the temperature increases. The approximate location of the
Cepheid and RV Tauri instability strip is indicated by the dashed lines.

As Figure 1 illustrates, post-AGB stars reach their visually brightest
magnitudes in the yPAGB stage, just to the blue of the Cepheid instability
strip. The suggestion that these stars should have a narrow luminosity
function, and thus could be useful as standard candles, was first laid out by
Bond (1997a, b), and we elaborate the arguments here. The bolometric
luminosity of a PAGB star on its final traversal of the CMD depends almost
exclusively on its core mass (Paczyński, 1970; Vassiliadis & Wood, 1994;
Bloecker, 1995; Miller Bertolami, 2016), and this core mass, in turn, is
related to the star’s original main-sequence mass via the initial-final mass
relation (IFMR; e.g., Cummings et al., 2018; El-Badry et al., 2018). As the
existence of the second-parameter problem for Milky Way GCs demonstrates,
there is a scatter in the final masses for a given initial mass: clusters that
have similar ages and metallicities can have very different HB morphologies,
and therefore different post-RGB masses (e.g., Sandage & Wildey, 1967; Torelli
et al., 2019). Moreover, stars that undergo enhanced mass loss, due to binary
interactions, rapid rotation, or simply stochastic processes during normal
stellar evolution, may prematurely abort their AGB evolution, and create post-
early asymptotic giant branch (PEAGB) objects with a wide range of
luminosities. However, unless the dispersion in the IFMR is so wide as to wipe
out any systematic in the final white dwarf mass distribution, the overall
relationship should hold: the older the stellar population, the lower the mean
mass of its HB star envelopes, the lower the mean final mass of the
population’s stars, and the fainter the mean magnitude of these stars on their
final traversal of the color-magnitude diagram. Since the age of the universe
is finite, this means that there should be a low-luminosity edge to the
distribution of PAGB luminosities which is defined by the IFMR of a galaxy’s
oldest stars.

At the same time, there are two selection effects which should impose a soft
upper limit to the luminosities of Population II PAGB stars. Both effects stem
from the strong inverse correlation between the luminosity of a PAGB star and
its rate of evolution across the HR diagram (see, for example, Paczyński,
1970; Vassiliadis & Wood, 1994; Miller Bertolami, 2016). The first is the
observational bias against detecting rapidly evolving stars: the more luminous
the star, the less time it spends in the PAGB phase, and the lower the
likelihood of its detection. In a Population II system, this correlation,
coupled with the slow evolution of the main-sequence turnoff and the shallow
slope of the low-mass end of the IFMR (e.g., El-Badry et al., 2018; Cummings
et al., 2018), should produce an observed PAGB luminosity function that is
biased toward low-luminosity objects.

Amplifying this effect is a related systematic associated with circumstellar
extinction. Low-mass PAGB stars, such as BD+39∘ 4926 (Gezer et al., 2015),
BD+14∘ 3071 (Bond, 2020), and the yPAGB star in M79 (Bond et al., 2016) have
been shown to have little to no circumstellar material. This is likely because
their evolutionary timescale across the HR diagram is slow enough to allow
dust produced on the AGB to disperse into space. Conversely, in higher-
luminosity, faster-evolving objects, the AGB ejecta are still in the vicinity
of the star, even after the star has become hot enough to ionize its
surroundings (e.g., Herrmann & Ciardullo, 2009; Davis et al., 2018). The dust
associated with the circumstellar ejecta attenuates the stellar emission and
again causes the luminosity distribution of observed PAGB stars to skew
towards lower values.

As a result of the combination of these effects, most of the PAGB stars of an
old stellar populations should lie in a narrow band at the high-luminosity end
of the HR diagram, some four magnitudes above the locus of HB stars.

##  3 Observational Tests

A straightforward test of the utility of yPAGB stars as standard candles is to
examine the luminosity function of such stars in Galactic GCs. This is now
quite feasible: by combining Gaia proper motions and parallaxes from Early
Data Release 3 (EDR3; Gaia Collaboration et al., 2021), with a photometric
technique for identifying luminous stars with low surface gravities (Bond,
2005), it is relatively easy to identify PAGB star candidates and determine
the likelihood of their cluster membership. D22 did exactly this, using Gaia
EDR3 astrometry, $uBVI$ photometry, and Gaussian-mixture modeling to identify
a sample of 438 above-horizontal-branch (AHB) objects that are highly probable
members of 104 Milky Way and LMC GCs. Among these stars, D22 identified 13
luminous objects as being PAGB star candidates.

To use these data, we first identified the known variable stars in the D22
sample, and replaced their single-epoch photometry with the stars’ intensity-
weighted mean magnitudes from Clement et al. (2001) and the references given
in Table 1. We then took the photometric measurements of the stars, updated
their estimated distances to the Gaia+HST+literature values given by Baumgardt
& Vasiliev (2021), and with two exceptions, applied the foreground extinction
estimates summarized by Harris (2010).333The extinction of M19 is spatially
variable. Following Bond et al. (2021), we estimated the reddenings of its
individual PAGB and AHB stars using the high-resolution dust maps of Alonso-
García et al. (2012) and Johnson et al. (2017). The result is the CMD shown in
Figure 2. Also plotted in the figure is the expected location of $\log
L/L_{\odot}=3.25$ stars (with $M=0.56\,M_{\odot}$ and [Fe/H] = $-1.5$) derived
using the PARSEC web-tool for the calculation of bolometric corrections (Chen
et al., 2019).

Figure 2 shows several interesting features. The first is the color
distribution of the PAGB stars. Within the range $0.0<(B-V)_{0}<1.0$, D22
identified 10 stars brighter than $M_{V}=-3.0$. Nine of these stars are within
or blueward of the instability strip, and the one star redward of the
instability strip is an RV Tau or semi-regular variable whose mean $(B-V)_{0}$
color is very poorly determined (Clement et al., 2001; Wehlau & Butterworth,
1990; Jayasinghe et al., 2020). This distribution is as expected. As detailed
by Bond (2005), the $uBVI$ photometric system is quite sensitive to surface
gravity in the color range $0.0<V-I<0.9$, but the sensitivity to $\log g$
falls off rapidly for bluer objects, and tails off gradually towards the red.
For luminous stars, these $V-I$ limits are equivalent to the color range
$0.0<B-V<0.7$ (Worthey & Lee, 2011), and this is precisely where the D22 post-
AGB candidates are located. Although the D22 sample also includes objects as
red as $(B-V)_{0}=1.0$, only one of our post-AGB stars is located redward of
the instability strip.

Also, as expected, the magnitude separation between the PAGB stars and other
AHB objects increases with effective temperature until $(B-V)_{0}\simeq 0$.
This is a consequence of the evolutionary paths that stars take when leaving
the ZAHB. Figure 1 illustrates that in the red, post-HB stars can attain
luminosities that approach the AGB limit, making it difficult to distinguish
between stars on their way to the AGB tip and post-AGB objects. But blueward
of the instability strip, the evolutionary paths of post-HB stars do not come
within a magnitude of the PAGB locus (until the stars become so hot that the
bulk of their emission is in the UV). This suggests that the only possible
contaminants in a PAGB survey (aside from foreground interlopers) are rapidly
evolving stars undergoing thermal pulses near their surface, PEAGB stars
evolved from objects at the extreme blue end of the HB, and various products
of binary evolution. As Figure 2 demonstrates such objects must be extremely
rare. The D22 study included 104 of the oldest clusters in the Milky Way and
LMC, and encompassed more than $\sim$$1.5\times 10^{7}L_{\odot}$ of $V$-band
light. Yet in the survey, there are no stars with colors between
$0.0<(B-V)_{0}<0.5$ that are within $\sim$0.7 mag of the PAGB track.

Figure 2: Color-magnitude diagram of the brightest low-surface-gravity stars
identified in the Davis et al. (2022) survey of Galactic and LMC globular
clusters. Fill circles show non-variable stars and have typical errors (based
on uncertainties in photometry, distance, and reddening) of $\sim 0.03$ mag in
both $M_{V}$ and $(B-V)_{0}$. Large triangles represent mean $M_{V}$ values
for RV Tauri and W Virginis variables and have slightly larger uncertainties,
$\lesssim 0.05$ mag. The small triangles denote single-phase measurements of
variable stars. The suspected RV Tau variable with $M_{V}\simeq-3.3$ and
$(B-V)_{0}\simeq 0.9$ has a well-measured light curve in $V$ but no reliable
$B$-band photometry. The curve shows the expected location of stars with a
constant bolometric luminosity of $\log L/L_{\odot}=3.25$. The approximate
location of the instability strip is marked with dashed lines. Points are
color-coded by the horizontal-branch morphology index of their host clusters
(see text), as indicated by the color bar (Lee et al., 1994; Borkova &
Marsakov, 2000; Catelan, 2009); grey points identify stars in clusters without
a well-measured HBR value. The lack of PAGB stars from systems with red
horizontal branches confirms the strong dependence of PAGB lifetime upon
stellar mass. The histogram on the right side of the figure represents the
magnitude distribution for stars in the color range $0\leq(B-V)_{0}\leq 0.5$.

Perhaps the most interesting feature of Figure 2 concerns its implications for
the origins of PAGB stars and their rate of stellar evolution. The GCs of the
Milky Way and the LMC extend over $\sim$2.5 dex in metallicity (Harris, 2010).
Yet as detailed in Table 1, the metallicities of the clusters that contain
PAGB stars brighter than $M_{V}=-3.0$ are relatively homogeneous, varying by
less than a factor of $\sim$3\. Moreover, these 10 PAGB stars belong to only
seven GCs, as three of the systems possess two of these intermediate-
temperature, low-surface-gravity objects.

At first glance, these statistics seem peculiar, especially since, given a
population of 10 A-, F-, or G-type PAGB stars, the binomial probability of 3
clusters out of 104 having two or more objects is less than 1%. However, the
compilation by Harris (2010) shows that those eight clusters are among the
most luminous GCs in the Milky Way, and contain $\sim$15% of the GC system’s
total $V$-band light. Similarly, almost $\sim$40% of the total luminosity
emitted by Milky Way GCs comes from clusters with
$-1.29\leq\textrm{[Fe/H]}\leq-1.74$. So it should not be too surprising to
find that PAGB stars are often found in these large, moderately metal-poor
systems.

The most telling statistic, however, comes from the structure of the parent
clusters’ HBs. We can quantify HB morphology using the index proposed by Lee
et al. (1994)

${\rm HBR}=\frac{B-R}{B+R+V}\,,$ (1)

where $B$, $R$, and $V$ represent the numbers of HB stars blueward, redward,
and inside the instability strip, respectively. While imperfect (see the
discussion by Torelli et al., 2019), this index has been measured for most
Milky Way and Magellanic Cloud GCs, allowing us to quickly identify clusters
with predominantly red (HBR $<0$) and blue (HBR $>0$) HBs. Based on the
compilations of HBR values given by Lee et al. (1994), Borkova & Marsakov
(2000), and Catelan (2009), slightly more than a third of the $V$-band
luminosity of the Milky Way GC system comes from to clusters with red HBs. Yet
every one of the PAGB stars identified by D22 and in earlier studies belong to
clusters with blue HBs.

The most natural way to explain this property is through the evolutionary
timescale: because red HB stars have more massive envelopes, they presumably
create objects with higher PAGB masses, and therefore shorter PAGB
evolutionary times. The fact that we see no yPAGB stars in systems with red
HBs is direct confirmation of the strong inverse relation between stellar mass
and PAGB lifetime and/or the shallow slope of the low-mass end of the IFMR. It
also supports our argument for a soft upper limit to the luminosities of
Population II PAGB stars.

Conversely, stars with small envelope masses produce relatively long-lived
PAGB stars, and these objects occupy a distinct band in the color-magnitude
diagram. While extreme-HB stars could evolve into objects that fill the void
between the HB and PAGB regions of CMD (Moehler et al., 2019), such objects
are not present in the D22 data set. PEAGB stars must spend very little (if
any) time in the “yellow” region of the HR diagram, either because of a rapid
evolutionary timescale or an extreme dependence of post-HB luminosity on
stellar mass.

Table 1: Yellow and Red PAGB Stars StaraaV: variable star from the list of Clement et al. (2001); ZNG: Zinn et al. (1972) | $\alpha\rm(J2000)$ | $\delta\rm(J2000)$ | [Fe/H]bbHost cluster metallicity and reddening from Harris (2010), except the reddening for NGC 5986 is from Alves et al. (2001), and the reddening for M19 ZNG 4 is from Bond et al. (2021) |  $E(B-V)$bbHost cluster metallicity and reddening from Harris (2010), except the reddening for NGC 5986 is from Alves et al. (2001), and the reddening for M19 ZNG 4 is from Bond et al. (2021) |  $(m-M)_{0}$ccHost cluster distance from Baumgardt & Vasiliev (2021) | $(B-V)_{0}$ |  $M_{V}$ddThe uncertainties on $M_{V}$ include the distance errors given by Baumgardt & Vasiliev (2021), an estimate of the uncertainty in $E(B-V)$, and errors in the photometry. For variable stars, the latter number is that associated with the star’s intensity-weighted mean magnitude. | Photometry Reference
---|---|---|---|---|---|---|---|---
M79 PAGB | 05:24:10.36 |  $-$24:29:20.7 | $-1.60$ | 0.01 | 15.58 | 0.27 | $-3.41\pm 0.04$ | Bond et al. (2016)
$\omega$ Cen V1 | 13:26:05.17 |  $-$47:23:42.5 | $-1.53$ | 0.12 | 13.67 | 0.55 | $-3.21\pm 0.04$ | Braga et al. (2020)
$\omega$ Cen HD 116745 | 13:26:26.32 |  $-$47:16:27.3 | $-1.53$ | 0.12 | 13.67 | 0.24 | $-3.22\pm 0.02$ | Davis et al. (2022)
M5 V84 | 15:18:36.14 | +02:04:16.4 | $-1.29$ | 0.03 | 14.37 | 0.66 | $-3.04\pm 0.04$ | Rabidoux et al. (2010)
M5 V42 | 15:18:24.78 | +02:02:53.2 | $-1.29$ | 0.03 | 14.37 | 0.60 | $-3.27\pm 0.03$ | Rabidoux et al. (2010)
NGC 5986 PAGB 1 | 15:46:03.36 |  $-$37:46:44.2 | $-1.59$ | 0.29 | 15.14 | 0.02 | $-3.47\pm 0.04$ | Davis et al. (2022)
NGC 5986 PAGB 2 | 15:46:04.94 |  $-$37:47:02.4 | $-1.59$ | 0.29 | 15.14 | 0.28 | $-3.37\pm 0.04$ | Davis et al. (2022)
M19 ZNG 4 | 17:02:35.18 |  $-$26:15:23.1 | $-1.74$ | 0.34 | 14.84 | 0.48 | $-3.39\pm 0.05$ | Bond et al. (2021)
M28 V17 | 18:24:35.84 |  $-$24:53:15.9 | $-1.32$ | 0.40 | 13.65 | 0.90eeThe mean $(B-V)$ color of this object is poorly known | $-3.31\pm 0.05$ | Jayasinghe et al. (2020)
M2 V11 | 21:33:32.41 |  $-$00:49:05.8 | $-1.65$ | 0.06 | 15.34 | 0.50 | $-3.42\pm 0.05$ | Demers (1969)

##  4 Using PAGB Stars as Standard Candles

When first formed, all ZAHB stars have an initial core mass of
$\sim$$0.48\,M_{\odot}$ (e.g., Sweigart & Gross, 1978); the stars’ final core
masses depend of the masses of their envelopes. The more mass in the envelope,
the more mass is accumulated onto the core during the AGB phase, and the
brighter the star becomes. Clusters with red HB stars should therefore produce
very luminous (but short-lived) post-AGB stars, while systems with blue HBs
should create relatively long-lived post-AGB objects at or near the low-
luminosity limit for the class.

As Figure 2 illustrates, the 10 PAGB stars identified by D22 are all from
systems with very blue HBs and all have very similar bolometric luminosities.
If we ignore M28-V17, whose location on the CMD is poorly known due to a lack
of coverage in the $B$-band, then the stars’ scatter about the $\log L=3.25$
line is just 0.04 in $\log L$ (or 0.10 in magnitude). This consistency
supports the hypothesis that PAGB stars are excellent standard candles for
Population II systems. If the PAGB stars of other galaxies follow the same
luminosity distribution as those in Milky Way GCs, then their distances can be
measured to $\sim$2% using just a handful of objects.

Of course, Figure 2 also illustrates a major difficulty with the use of these
stars: five of the PAGB candidates shown in the figure are RV Tau variables.
These stars, which have amplitudes of more than 1 mag and periods ranging from
one to two months (Clement et al.,
2001)444http://www.astro.utoronto.ca/~cclement/cat/listngc.html, help define
the PAGB evolutionary path across the HR diagram, since their intensity-
weighted mean magnitudes are known from photometric monitoring (see the
references in Table 1). However, because of their variability, the utility of
these objects for extragalactic distance measurements is limited, as any
determination of their mean magnitudes would require at least a dozen
observations spaced over a minimum of three or four months.

The usefulness of red PAGB stars is also problematic, as the separation
between true PAGB objects and stars still on their way to the AGB is
relatively small. In addition, as the detailed stellar-evolution sequences of
Moehler et al. (2019) demonstrate, helium-shell thermal pulses on the AGB
often produce small excursions in this part of the CMD that can further
confuse the issue.

On the other hand, the A- and F-type PAGB stars located blueward of the
instability strip are ideal targets for study. In addition to the very small
scatter in their bolometric luminosities, these objects offer a number of
practical advantages for extragalactic astronomy.

The first is that yPAGB stars are the visually brightest objects in Population
II systems, and easily stand out amidst their surroundings. In bolometric
terms, yPAGBs are just as luminous as stars near the tip of the AGB, but while
AGB stars emit the bulk of the radiation in the red and infrared, yPAGB
objects have their peak emission in the optical. As a result, in the $V$-band,
yPAGB stars are a full magnitude brighter than the most luminous AGB objects,
and $\sim$2 mag brighter than stars at the tip of the RGB. At bluer
wavelengths, the contrast between the PAGB and AGB is even greater (see, e.g.,
the $u$-band image of M19 in Figure 2 of Bond et al., 2021).

A second advantage of yPAGB stars is that they are relatively unaffected by
dust, both foreground and circumstellar. As Population II objects, yPAGBs are
generally not associated with regions of high interstellar reddening, and even
in late-type galaxies, these objects should exist far away from places where
internal extinction is important. Moreover, as pointed out in §2, by the time
a low-luminosity PAGB reaches a temperature of $T_{\rm eff}\simeq 6000$ K,
virtually all of the mass lost by the star during the AGB should have
dispersed into space. Circumstellar extinction should therefore not affect our
estimates of the objects’ luminosities.

Perhaps most importantly, yPAGB stars with colors between
$0.0\lesssim(B-V)_{0}\lesssim 0.5$ are easy to detect. As detailed above,
these objects occupy a unique position in the HR diagram, roughly four
magnitudes above the HB. In addition, due to their extremely high luminosities
and therefore low surface gravities, yPAGB stars have Balmer jumps that are up
to $\sim$50% larger that those of higher-gravity objects of the same effective
temperature (Bond, 2005). As a result, it is relatively simple to identify
yPAGB stars by comparing photometry through a filter located just shortward of
the Balmer break to measurements longward of the feature. Systematics due to
possible reddening or metallicity effects can then be minimized through the
use of a color-difference index, such as $c_{2}=(u-B)-(B-V)$ (Bond 2005, D22).

If we compute the mean $V$-band luminosity of the 10 stars in Table 1 using
the bolometric corrections derived from the PARSEC database (Chen et al.,
2019), then in the color range between $0.0\leq(B-V)_{0}\leq 0.5$, PAGB stars
should have a mean absolute magnitude of $\langle M_{V}\rangle=-3.37\pm 0.03$,
where the uncertainty represents the standard deviation of the mean.
Alternatively, if we take an empirical approach and use the mean $V$-band
magnitude of all the nonvariable GC stars with colors $0.0\leq(B-V)_{0}\leq
0.5$ and absolute magnitudes brighter than $M_{V}\simeq-2.7$ is then $\langle
M_{V}\rangle=-3.37\pm 0.05$. Both of these estimates depend only on the
distances to the GCs (which, at present, are based on the Gaia+HST+literature
estimates of Baumgardt & Vasiliev, 2021) and the foreground reddening values
of Harris (2010). As the Gaia distances to the clusters improve, so will our
knowledge of the $V$ magnitudes of these stars.

We do note that over the color range $0.0\lesssim(B-V)_{0}\lesssim 0.5$, the
bolometric correction applicable to yPAGB stars changes by $\sim$0.1 mag.
Thus, to reduce the scatter in the stars’ absolute $V$ magnitudes, one could
apply a color-dependent bolometric correction to each star. However, while
such corrections are straightforward, they are likely not necessary. Just as
the color dependence of Cepheid periods is rendered moot by averaging over an
ensemble of objects distributed throughout the instability strip (Jacoby et
al., 1992), so is the color dependence of yPAGB magnitudes. As long as the
sample of objects numbers more than $\sim$10, this additional step would not
significantly improve the accuracy of the technique.

##  5 Confirmation from Gaia EDR3

To further illustrate the potential of yPAGB stars as standard candles, we can
use photometric data from Gaia EDR3555We obtained the Gaia EDR3 data from the
Strasbourg Astronomical Data Center, at https://vizier.cds.unistra.fr/viz-
bin/VizieR for the four GCs that contain nonvariable yPAGB objects. Figure 3
displays the combined Gaia CMD for M79, $\omega$ Cen, NGC 5986, and M19,
plotting absolute $G$ magnitude versus dereddened $G_{\rm BP}-G_{\rm RP}$
color. To select cluster members for this figure, we chose all stars lying
within $6^{\prime}$ of the cluster centers ($15^{\prime}$ for $\omega$ Cen),
and eliminated most field interlopers by requiring the proper motions to lie
within $\pm$$1.5\rm\,mas\,yr^{-1}$ of the mean cluster value in both
coordinates ($\pm$$2.5\rm\,mas\,yr^{-1}$ for $\omega$ Cen), and have
parallaxes within $\pm$0.5 mas of the cluster mean.

Figure 3: Color-magnitude diagram for the combined membership of the four
Milky Way globular clusters that contain nonvariable yellow PAGB stars. The
data are derived from Gaia EDR3 photometry, and are color-coded as indicated
in the legend. Field stars have been removed from the diagram based on proper
motions and parallaxes, and the magnitudes and colors are corrected for
distance and reddening, as described in the text. Filled circles mark the five
yellow PAGB stars, color-coded according to cluster membership; the open
circle is the RV Tau variable V1 in $\omega$ Cen. The figure illustrates the
extremely narrow range of absolute magnitudes for the nonvariable yPAGB
objects, and the large gap between them and the next brightest stars in the
clusters.

To correct the data for extinction, we adopted the $E(B-V)$ values listed in
Table 1. Based on calculations given in the PARSEC online CMD
tool666http://stev.oapd.inaf.it/cmd (Pastorelli et al., 2019), we assumed
extinction coefficients of $A_{G}=2.5924\,E(B-V)$ and $E(BP-
RP)=1.3918\,E(B-V)$.777These coefficients were calculated for the SED of a G2
V star. They are reasonable for the yPAGB stars, but will have systematic
offsets for very blue and very red objects. As in Table 1, the absolute
distances for the clusters were taken from the recent compilation888Available
online at https://people.smp.uq.edu.au/HolgerBaumgardt/globular/ of Baumgardt
& Vasiliev (2021).

In the figure, we plot the yPAGB stars in these four clusters as large filled
circles; also included in the figure as an open circle is the RV Tau variable
V1 in $\omega$ Cen. The figure supports the discussion in the previous two
sections. Specifically, (1) the five nonvariable yPAGB stars have a very
narrow luminosity function999Note, in particular, that the two yPAGB stars in
NGC 5986 (which are at the same distance and suffer the same extinction) have
$G$ magnitudes that differ by only 0.016 mag. (rms scatter 0.09 mag; mean
absolute magnitude $M_{G}=-3.37\pm 0.04$); and (2) there is a gap of more than
1 mag between these objects and the nearest AHB stars. Since the blue end of
the ZAHB is well populated in all four clusters, it is safe to conclude that
these stars define the low-luminosity end of the yPAGB stars’ luminosity
function.

##  6 Specific Frequency of Yellow PAGB stars

When planning extragalactic surveys, it is helpful to know how many targets
one might reasonably expect to find in a single observation. Though this
number is difficult to calculate in general, there are ways to estimate the
likelihood of a successful yPAGB survey.

From the “fuel-consumption theorem,” the number of stars in any post-main
sequence phase of evolution, $N$, is

$N=L_{\rm pop}\,B(t)\,\tau$ (2)

where $L_{\rm pop}$ is the bolometric luminosity of the stellar population
being surveyed, $B(t)$ is the bolometric-luminosity-specific stellar-
evolutionary flux, and $\tau$ is the mean lifetime of the evolutionary phase
being investigated (Renzini & Buzzoni, 1986; Buzzoni et al., 2006). For all
populations older than $\sim$3 Gyr, $B\simeq 1.8\times 10^{-11}$ stars
yr${}^{-1}~{}L_{\odot}^{-1}$, and the applicable bolometric correction is
roughly $-0.85$ (Buzzoni et al., 2006). Thus, the production rate of PAGB
stars per unit $V$-band luminosity can be estimated readily from the
integrated brightness of a target population. The total yPAGB star population
then only depends on the lifetime of the stage.

Unfortunately, for a mixed stellar population, the lifetime of PAGB stars is
ill-defined, as the evolutionary timescale for these objects is a steep
function of their core mass. For a population mix similar to that of the Milky
Way GCs, we can estimate $\tau$ directly. Based on the GC luminosities given
by Harris (2010) and Pessev et al. (2008), the D22 uBVI survey included
$\sim$$1.5\times 10^{7}L_{\odot}$ of $V$-band GC light. Since the survey
detected five nonvariable yPAGB stars, Equation (2) implies that the mean
lifetime of these objects is of order $\sim$9000 yr, with a $1\,\sigma$
confidence interval extending from 5100 to 15,000 yr (Gehrels, 1986). This is
consistent with the value one would infer from the $M=0.55\,M_{\odot}$, [Fe/H]
$=-1.5$ evolutionary track of Miller Bertolami (2016), shown in Figure 1.

Of course, as discussed in §3, all of the PAGB stars found by D22 come from
clusters with blue HBs; the higher-mass PAGB objects produced in red-HB
clusters presumably have much shorter evolutionary times and are therefore
less common. So the actual lifetime of the yPAGB stars plotted in Figure 1
must be greater than that estimated above. Thus a proper estimation for the
number of yPAGB stars expected in a galaxy must consider the mix of stellar
populations and HB morphologies present in the target population. Such data
will not generally be available for extragalactic investigations.

However, there is one observable that should be a good predictor for the
number of PAGB stars present in an early-type system: the stellar population’s
UV upturn. Traditional stellar population models predict that Population II
systems should have very little flux in the far UV. However, satellites such
as OAO-2 (Code & Welch, 1982) and IUE (e.g., Oke et al., 1981; Burstein et
al., 1988) demonstrated that this is not the case: the spectral-energy
distributions of elliptical galaxies and spiral bulges often increase
shortward of $\sim$2500 Å (e.g., Greggio & Renzini, 1999; O’Connell, 1999).
The two most plausible sources of this light are extreme HB stars and hot PAGB
objects (O’Connell, 1999; Yi, 2008), and, as D22 and Figure 2 demonstrate, the
former population generates the latter. Thus we should expect the number of
yPAGB stars to correlate strongly with a system’s UV upturn. This means that
in systems such as M32 and NGC 147 which have very weak UV excesses and
relatively few blue HB stars (Brown et al., 2000; Geha et al., 2015), we
should expect yPAGB stars to be relatively rare. Conversely, in a galaxy such
as NGC 185, which has a significant blue HB population (Geha et al., 2015), we
should see many more yPAGB objects per unit stellar luminosity. We should also
expect the number density of yPAGB stars in the halo of M31 to follow that of
the blue HB stars measured by Williams et al. (2015).

##  7 Discussion

If the PAGB luminosity limit is really as constant as the data suggest, then
yPAGB stars are competitive with the very best extragalactic standard candles.
Cepheid variables are generally considered to be the gold standard for
calibrating the luminosities of SNe Ia, but their observation is relatively
expensive, as at least a dozen visits are required to accurately determine
their periods. Moreover, optical observations of a single Cepheid variable can
only yield a distance accurate to $\sim$10% (Riess et al., 2019); it is only
by measuring large numbers of Cepheids in a single galaxy that this
uncertainty can be beaten down. Thus, the technique works best in large late-
type systems with high star-formation rates, large numbers of Cepheid
variables—and, unfortunately, significant interstellar extinction.

Alternatively, the TRGB method can produce an accurate distance to a
Population II system in a single visit. However, care must be taken to avoid
the systematic effects introduced by image crowding (Freedman, 2021), and the
fading of the $I$-band RGB tip with metallicity (e.g., Beaton et al., 2018).
The technique is therefore best suited for small galaxies with exclusively
metal-poor populations.

In contrast, crowding should not be a major issue for yPAGB stars, since in
the $V$-band, these objects are $\sim$2 mag brighter than the TRGB and (due to
their smaller bolometric correction) one magnitude brighter than the most
luminous AGB stars. Moreover, we expect that the low-luminosity locus of yPAGB
stars will be rather insensitive to galactic metallicity. Based on the data in
hand, we cannot say for certain how much the PAGB luminosity limit will change
with metal abundance, as the sample of GCs hosting PAGB stars only spans the
range $-1.74\lesssim\textrm{[Fe/H]}\lesssim-1.29$ (Table 1). However, since
the luminosity limit is produced by a galaxy’s oldest stars, it is likely that
the range of metallicity for the lowest-luminosity yPAGB objects in other
galaxies will also be limited. So we may not see much of a change in $\langle
M_{V}\rangle$, even in environments such as the halos of large spiral
galaxies.

The efficient detection of yPAGB stars in other galaxies does require
observations through a $u$-band filter whose bandpass is almost entirely
blueward of the Balmer break. The F336W filter of the WFC3/UVIS camera of the
Hubble Space Telescope satisfies this criterion, and the instrument is
efficient enough to reach the yPAGB stars of the M81 and Sculptor groups in as
little as four spacecraft orbits. Thus the method can provide an independent
cross-check of the TRGB method in systems that are inaccessible to Cepheids.
Moreover, with longer exposures, WFC3 F336W detections can be extended outward
to $\sim$10 Mpc, enabling the direct calibration of several SNe Ia.

Our understanding of the luminosities of yPAGB stars is still in its earliest
stages. To confirm their utility as standard candles, additional observations
in the various populations of the Local Group are needed. But based on the
results from the Milky Way’s GCs, such additional studies are warranted, as
the objects may provide a simple and direct link between direct trigonometric
parallaxes from Gaia and the luminosities of SNe Ia.

This research has made use of the VizieR catalogue access tool, CDS,
Strasbourg, France (DOI : 10.26093/cds/vizier). The original description of
the VizieR service was published in 2000, A&AS 143, 23. This work has made use
of data from the European Space Agency (ESA) mission Gaia
(https://www.cosmos.esa.int/gaia), processed by the Gaia Data Processing and
Analysis Consortium (DPAC,
https://www.cosmos.esa.int/web/gaia/dpac/consortium). Funding for the DPAC has
been provided by national institutions, in particular the institutions
participating in the Gaia Multilateral Agreement. The Institute for
Gravitation and the Cosmos is supported by the Eberly College of Science and
the Office of the Senior Vice President for Research at the Pennsylvania State
University. This research has made use of the NASA/IPAC Infrared Science
Archive, which is funded by the National Aeronautics and Space Administration
and operated by the California Institute of Technology.

## References

  * Alonso-García et al. (2012) Alonso-García, J., Mateo, M., Sen, B., et al. 2012, AJ, 143, 70, doi: 10.1088/0004-6256/143/3/70
  * Alves et al. (2001) Alves, D. R., Bond, H. E., & Onken, C. 2001, AJ, 121, 318, doi: 10.1086/318030
  * Baumgardt & Vasiliev (2021) Baumgardt, H., & Vasiliev, E. 2021, MNRAS, 505, 5957, doi: 10.1093/mnras/stab1474
  * Beaton et al. (2018) Beaton, R. L., Bono, G., Braga, V. F., et al. 2018, Space Sci. Rev., 214, 113, doi: 10.1007/s11214-018-0542-1
  * Bennett et al. (2013) Bennett, C. L., Larson, D., Weiland, J. L., et al. 2013, ApJS, 208, 20, doi: 10.1088/0067-0049/208/2/20
  * Blakeslee et al. (2021) Blakeslee, J. P., Jensen, J. B., Ma, C.-P., Milne, P. A., & Greene, J. E. 2021, ApJ, 911, 65, doi: 10.3847/1538-4357/abe86a
  * Bloecker (1995) Bloecker, T. 1995, A&A, 299, 755
  * Bond (1997a) Bond, H. E. 1997a, in The Extragalactic Distance Scale, ed. M. Livio, M. Donahue, & N. Panagia, 224.  https://arxiv.org/abs/astro-ph/9702008
  * Bond (1997b) Bond, H. E. 1997b, in Planetary Nebulae, ed. H. J. Habing & H. J. G. L. M. Lamers, Vol. 180, 460
  * Bond (2005) Bond, H. E. 2005, AJ, 129, 2914, doi: 10.1086/430052
  * Bond (2020) —. 2020, AJ, 160, 274, doi: 10.3847/1538-3881/abc177
  * Bond et al. (2016) Bond, H. E., Ciardullo, R., & Siegel, M. H. 2016, AJ, 151, 40, doi: 10.3847/0004-6256/151/2/40
  * Bond et al. (2021) Bond, H. E., Davis, B. D., Siegel, M. H., & Ciardullo, R. 2021, AJ, 161, 125, doi: 10.3847/1538-3881/abdbb3
  * Borkova & Marsakov (2000) Borkova, T. V., & Marsakov, V. A. 2000, Astronomy Reports, 44, 665, doi: 10.1134/1.1312963
  * Braga et al. (2020) Braga, V. F., Bono, G., Fiorentino, G., et al. 2020, A&A, 644, A95, doi: 10.1051/0004-6361/202039145
  * Brown et al. (2000) Brown, T. M., Bowers, C. W., Kimble, R. A., Sweigart, A. V., & Ferguson, H. C. 2000, ApJ, 532, 308, doi: 10.1086/308566
  * Burstein et al. (1988) Burstein, D., Bertola, F., Buson, L. M., Faber, S. M., & Lauer, T. R. 1988, ApJ, 328, 440, doi: 10.1086/166304
  * Buzzoni et al. (2006) Buzzoni, A., Arnaboldi, M., & Corradi, R. L. M. 2006, MNRAS, 368, 877, doi: 10.1111/j.1365-2966.2006.10163.x
  * Catelan (2009) Catelan, M. 2009, Ap&SS, 320, 261, doi: 10.1007/s10509-009-9987-8
  * Chen et al. (2019) Chen, Y., Girardi, L., Fu, X., et al. 2019, A&A, 632, A105, doi: 10.1051/0004-6361/201936612
  * Ciardullo (2012) Ciardullo, R. 2012, Ap&SS, 341, 151, doi: 10.1007/s10509-012-1061-2
  * Clement et al. (2001) Clement, C. M., Muzzin, A., Dufton, Q., et al. 2001, AJ, 122, 2587, doi: 10.1086/323719
  * Code & Welch (1982) Code, A. D., & Welch, G. A. 1982, ApJ, 256, 1, doi: 10.1086/159880
  * Cummings et al. (2018) Cummings, J. D., Kalirai, J. S., Tremblay, P. E., Ramirez-Ruiz, E., & Choi, J. 2018, ApJ, 866, 21, doi: 10.3847/1538-4357/aadfd6
  * Davis et al. (2022) Davis, B. D., Bond, H. E., Siegel, M. H., & Ciardullo, R. 2022, ApJ, 926, 99, doi: 10.3847/1538-4357/ac4224
  * Davis et al. (2018) Davis, B. D., Ciardullo, R., Jacoby, G. H., Feldmeier, J. J., & Indahl, B. L. 2018, ApJ, 863, 189, doi: 10.3847/1538-4357/aad3c4
  * de Grijs (2013) de Grijs, R. 2013, in IAU Symposium, Vol. 289, Advancing the Physics of Cosmic Distances, ed. R. de Grijs, 351–360, doi: 10.1017/S1743921312021709
  * Demers (1969) Demers, S. 1969, AJ, 74, 925, doi: 10.1086/110883
  * Di Valentino et al. (2021) Di Valentino, E., Anchordoqui, L. A., Akarsu, Ö., et al. 2021, Astroparticle Physics, 131, 102605, doi: 10.1016/j.astropartphys.2021.102605
  * El-Badry et al. (2018) El-Badry, K., Rix, H.-W., & Weisz, D. R. 2018, ApJ, 860, L17, doi: 10.3847/2041-8213/aaca9c
  * Freedman (2021) Freedman, W. L. 2021, ApJ, 919, 16, doi: 10.3847/1538-4357/ac0e95
  * Freedman et al. (2001) Freedman, W. L., Madore, B. F., Gibson, B. K., et al. 2001, ApJ, 553, 47, doi: 10.1086/320638
  * Freedman et al. (2020) Freedman, W. L., Madore, B. F., Hoyt, T., et al. 2020, ApJ, 891, 57, doi: 10.3847/1538-4357/ab7339
  * Gaia Collaboration et al. (2021) Gaia Collaboration, Brown, A. G. A., Vallenari, A., et al. 2021, A&A, 649, A1, doi: 10.1051/0004-6361/202039657
  * Geha et al. (2015) Geha, M., Weisz, D., Grocholski, A., et al. 2015, ApJ, 811, 114, doi: 10.1088/0004-637X/811/2/114
  * Gehrels (1986) Gehrels, N. 1986, ApJ, 303, 336, doi: 10.1086/164079
  * Gezer et al. (2015) Gezer, I., Van Winckel, H., Bozkurt, Z., et al. 2015, MNRAS, 453, 133, doi: 10.1093/mnras/stv1627
  * Greggio & Renzini (1999) Greggio, L., & Renzini, A. 1999, Mem. Soc. Astron. Italiana, 70, 691.  https://arxiv.org/abs/astro-ph/9811131
  * Harris (2010) Harris, W. E. 2010, arXiv e-prints, arXiv:1012.3224.  https://arxiv.org/abs/1012.3224
  * Herrmann & Ciardullo (2009) Herrmann, K. A., & Ciardullo, R. 2009, ApJ, 703, 894, doi: 10.1088/0004-637X/703/1/894
  * Huchra (1992) Huchra, J. P. 1992, Science, 256, 321, doi: 10.1126/science.256.5055.321
  * Jacoby et al. (1992) Jacoby, G. H., Branch, D., Ciardullo, R., et al. 1992, PASP, 104, 599, doi: 10.1086/133035
  * Jayasinghe et al. (2020) Jayasinghe, T., Stanek, K. Z., Kochanek, C. S., et al. 2020, MNRAS, 491, 13, doi: 10.1093/mnras/stz2711
  * Johnson et al. (2017) Johnson, C. I., Caldwell, N., Rich, R. M., et al. 2017, ApJ, 836, 168, doi: 10.3847/1538-4357/836/2/168
  * Klypin et al. (2011) Klypin, A. A., Trujillo-Gomez, S., & Primack, J. 2011, ApJ, 740, 102, doi: 10.1088/0004-637X/740/2/102
  * Lee et al. (1994) Lee, Y.-W., Demarque, P., & Zinn, R. 1994, ApJ, 423, 248, doi: 10.1086/173803
  * Miller Bertolami (2016) Miller Bertolami, M. M. 2016, A&A, 588, A25, doi: 10.1051/0004-6361/201526577
  * Moehler et al. (2019) Moehler, S., Landsman, W. B., Lanz, T., & Miller Bertolami, M. M. 2019, A&A, 627, A34, doi: 10.1051/0004-6361/201935694
  * O’Connell (1999) O’Connell, R. W. 1999, ARA&A, 37, 603, doi: 10.1146/annurev.astro.37.1.603
  * Oke et al. (1981) Oke, J. B., Bertola, F., & Capaccioli, M. 1981, ApJ, 243, 453, doi: 10.1086/158612
  * Paczyński (1970) Paczyński, B. 1970, Acta Astron., 20, 47
  * Pastorelli et al. (2019) Pastorelli, G., Marigo, P., Girardi, L., et al. 2019, MNRAS, 485, 5666, doi: 10.1093/mnras/stz725
  * Perlmutter et al. (1999) Perlmutter, S., Aldering, G., Goldhaber, G., et al. 1999, ApJ, 517, 565, doi: 10.1086/307221
  * Pesce et al. (2020) Pesce, D. W., Braatz, J. A., Reid, M. J., et al. 2020, ApJ, 891, L1, doi: 10.3847/2041-8213/ab75f0
  * Pessev et al. (2008) Pessev, P. M., Goudfrooij, P., Puzia, T. H., & Chandar, R. 2008, MNRAS, 385, 1535, doi: 10.1111/j.1365-2966.2008.12935.x
  * Planck Collaboration et al. (2020) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020, A&A, 641, A6, doi: 10.1051/0004-6361/201833910
  * Rabidoux et al. (2010) Rabidoux, K., Smith, H. A., Pritzl, B. J., et al. 2010, AJ, 139, 2300, doi: 10.1088/0004-6256/139/6/2300
  * Renzini & Buzzoni (1986) Renzini, A., & Buzzoni, A. 1986, Astrophysics and Space Science Library, Vol. 122, Global properties of stellar populations and the spectral evolution of galaxies., ed. C. Chiosi & A. Renzini, 195–231, doi: 10.1007/978-94-009-4598-2_19
  * Riess et al. (2021a) Riess, A. G., Casertano, S., Yuan, W., et al. 2021a, ApJ, 908, L6, doi: 10.3847/2041-8213/abdbaf
  * Riess et al. (2019) Riess, A. G., Casertano, S., Yuan, W., Macri, L. M., & Scolnic, D. 2019, ApJ, 876, 85, doi: 10.3847/1538-4357/ab1422
  * Riess et al. (2016) Riess, A. G., Macri, L. M., Hoffmann, S. L., et al. 2016, ApJ, 826, 56, doi: 10.3847/0004-637X/826/1/56
  * Riess et al. (2021b) Riess, A. G., Yuan, W., Macri, L. M., et al. 2021b, arXiv e-prints, arXiv:2112.04510.  https://arxiv.org/abs/2112.04510
  * Sandage & Wildey (1967) Sandage, A., & Wildey, R. 1967, ApJ, 150, 469, doi: 10.1086/149350
  * Schmidt et al. (1998) Schmidt, B. P., Suntzeff, N. B., Phillips, M. M., et al. 1998, ApJ, 507, 46, doi: 10.1086/306308
  * Springel et al. (2005) Springel, V., White, S. D. M., Jenkins, A., et al. 2005, Nature, 435, 629, doi: 10.1038/nature03597
  * Sweigart & Gross (1978) Sweigart, A. V., & Gross, P. G. 1978, ApJS, 36, 405, doi: 10.1086/190506
  * Torelli et al. (2019) Torelli, M., Iannicola, G., Stetson, P. B., et al. 2019, A&A, 629, A53, doi: 10.1051/0004-6361/201935995
  * van den Bergh (1990) van den Bergh, S. 1990, JRASC, 84, 275
  * Vassiliadis & Wood (1994) Vassiliadis, E., & Wood, P. R. 1994, ApJS, 92, 125, doi: 10.1086/191962
  * Vogelsberger et al. (2014) Vogelsberger, M., Genel, S., Springel, V., et al. 2014, MNRAS, 444, 1518, doi: 10.1093/mnras/stu1536
  * Wehlau & Butterworth (1990) Wehlau, A., & Butterworth, S. 1990, AJ, 100, 686, doi: 10.1086/115551
  * Williams et al. (2015) Williams, B. F., Dalcanton, J. J., Bell, E. F., et al. 2015, ApJ, 802, 49, doi: 10.1088/0004-637X/802/1/49
  * Wong et al. (2020) Wong, K. C., Suyu, S. H., Chen, G. C. F., et al. 2020, MNRAS, 498, 1420, doi: 10.1093/mnras/stz3094
  * Worthey & Lee (2011) Worthey, G., & Lee, H.-c. 2011, ApJS, 193, 1, doi: 10.1088/0067-0049/193/1/1
  * Yi (2008) Yi, S. K. 2008, in Astronomical Society of the Pacific Conference Series, Vol. 392, Hot Subdwarf Stars and Related Objects, ed. U. Heber, C. S. Jeffery, & R. Napiwotzki, 3.  https://arxiv.org/abs/0808.0254
  * Zinn et al. (1972) Zinn, R. J., Newell, E. B., & Gibson, J. B. 1972, A&A, 18, 390


##  1  Semantics

This section defines the semantics of .

(Expression Semantics)

$\inferrule{\Lambda(\mathit{x}\xspace)=\mathit{v}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x}\xspace)\Downarrow\mathit{v}\xspace{}}$

$\inferrule{\Lambda(\mathit{x_{label}}\xspace)=\mathit{v}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{label}}\xspace)\Downarrow\mathit{v}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{r}\xspace{}\\\
\Lambda(\mathit{r}\xspace\mathit{.}\xspace\mathtt{txt}\xspace)=\mathit{v}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{.}\xspace\mathtt{txt}\xspace)\Downarrow\mathit{v}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{r}\xspace{}\\\
\mathit{r}\xspace\mathit{.}\xspace\mathtt{txt}\xspace\notin\Lambda}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{.}\xspace\mathtt{txt}\xspace)\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\forall\mathit{i}\xspace,\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{i})\Downarrow\mathit{v}\xspace_{i}{}\\\
\Lambda\mathit{(}\mathit{x_{func}}\xspace\mathit{)}\xspace=\\{\overline{\mathit{x}\xspace_{i}},{\mathit{e}\xspace}\\}\\\
\Lambda[\forall\mathit{i}\xspace,\mathit{x}\xspace_{i}\mapsto\mathit{v}\xspace_{i}]\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{\tilde{v}}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{func}}\xspace\
(\overline{\mathit{e}\xspace_{i}}))\Downarrow\mathit{\tilde{v}}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{v}\xspace_{1}{}\\\
\mathit{\tilde{v}}\xspace_{2}=\mathit{unop}\xspace\
\mathit{v}\xspace_{1}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{unop}\xspace\
\mathit{e}\xspace)\Downarrow\mathit{\tilde{v}}\xspace_{2}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{v}\xspace_{1}{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{v}\xspace_{2}{}\\\
\mathit{\tilde{v}}\xspace_{3}=\mathit{v}\xspace_{1}\ \mathit{binop}\xspace\
\mathit{v}\xspace_{2}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1}\
\mathit{binop}\xspace\
\mathit{e}\xspace_{2})\Downarrow\mathit{\tilde{v}}\xspace_{3}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{0b}\mathit{C}\xspace{}\\\
\mathit{C}\xspace=\mathit{b}\xspace_{0}\ldots\mathit{b}\xspace_{\mathit{C}\xspace_{i}}\ldots\mathit{b}\xspace_{\mathit{n}}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{[}\mathit{C}\xspace_{i}\mathit{]}\xspace)\Downarrow\mathit{b}\xspace_{\mathit{C}\xspace_{i}}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{0b}\mathit{C}\xspace{}\\\
\mathit{C}\xspace=\mathit{b}\xspace_{0}\ldots\mathit{b}\xspace_{\mathit{C}\xspace_{i}}\ldots\mathit{b}\xspace_{\mathit{C}\xspace_{j}}\ldots\mathit{b}\xspace_{\mathit{n}}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{[}{\mathit{C}\xspace_{i}}\mathit{,}\
\xspace{\mathit{C}\xspace_{j}}\mathit{]}\xspace)\Downarrow\mathit{b}\xspace_{\mathit{C}\xspace_{i}}\ldots\mathit{b}\xspace_{\mathit{C}\xspace_{j}}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{[}\\_\mathit{]}\xspace)\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace\mathit{[}{\\_}\mathit{,}\
\xspace{\\_}\mathit{]}\xspace)\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{v}\xspace_{1}{}\\\
\Lambda[\mathit{x}\xspace\mapsto\mathit{v}\xspace_{1}]\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{\tilde{v}}\xspace_{2}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{let}\thinspace\mathit{x}\xspace\
\mathit{:}\
\tau\xspace_{\mathit{base}}=\mathit{e}\xspace_{1}\thinspace\texttt{in}\thinspace\mathit{e}\xspace_{2})\Downarrow\mathit{\tilde{v}}\xspace_{2}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{true}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{t})\Downarrow\mathit{\tilde{v}}\xspace_{t}{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{if}\thinspace\mathit{e}\xspace\thinspace\texttt{then}\thinspace\mathit{e}\xspace_{t}\thinspace\texttt{else}\thinspace\\_)\Downarrow\mathit{\tilde{v}}\xspace_{t}{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{false}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{f})\Downarrow\mathit{\tilde{v}}\xspace_{f}{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{if}\thinspace\mathit{e}\xspace\thinspace\texttt{then}\thinspace\\_\thinspace\texttt{else}\thinspace\mathit{e}\xspace_{f})\Downarrow\mathit{\tilde{v}}\xspace_{f}{}}$

Environment. The execution environment $\Lambda$ maps variables $\mathit{x}$to
values $\mathit{v}$. However, we take advantage of/abuse the polymorphism and
dynamic typing of paper rules to also store the following in the same
environment:

  * •

$\mathit{x_{label}}$(label names) map to values; specifically each label maps
to a pointer that points to the base (offset 0) of the region associated with
the label.

  * •

$\mathit{x_{func}}$(function names) map to pairs
$\\{\overline{\mathit{x}\xspace_{i}},{\mathit{e}\xspace}\\}$, which give the
list of argument names and the body for functions.

  * •

$\mathit{x_{proc}}$(procedure names) map to pairs
$\\{\overline{\mathit{x}\xspace_{i}},{\mathit{S}\xspace}\\}$, which give the
list of argument names and the body for procedures.

  * •

$\mathit{x_{op}}$(operation/instruction names) map to triples
$\\{\overline{\mathit{x}\xspace_{i}},\mathit{e}\xspace,{\mathit{S}\xspace}\\}$,
which give the list of argument names, the expression for the text form, and
the body for operations.

  * •

$\mathit{r}\xspace\mathit{.}\xspace\mathtt{txt}\xspace$ (the form for the text
version of a register) maps to a value.

Since identifiers are not allowed to overlap in well-typed programs, and
register identities are not strings at all, this usage creates no conflicts.

Note that $\mathit{x_{mem}}$, $\mathit{x_{\tau}}$, and
$\mathit{{x}_{module}}$do not appear in $\Lambda$ as these require no
translation at runtime.

Machine state. In addition to the execution environment we also need a
representation of machine state. We define two stores, one for registers and
one for memory. The register store $\rho$ maps registers $\mathit{r}$to values
$\mathit{v}$. The memory store $\sigma$ is more complicated: it maps pairs
$\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace$ (that is, pointer literals) to
pairs $(\mathit{v}\xspace,\mathit{C}\xspace_{l})$, where $\mathit{v}$is the
value stored at that location and $\mathit{C}\xspace_{l}$ is the bit width.

The bit widths of memory regions are invariant, both across the region (this
is the only way they can be declared) and also over time. They are used to
check the access widths appearing in fetch and store operations. Also note
that new entries cannot be created in either the register store or the memory
store, as real hardware does not permit such actions. The values stored in
registers and memory regions are restricted by the typing rules to bitvectors
(whether constants or pointers) of the appropriate width.

Notice that stepping through the declarations does _not_ initialize the
machine state. We want to reason about executions over ranges of possible
starting machine states; so instead we provide a judgment that uses the typing
environments to restricts the stores to forms consistent with the
declarations. This is discussed further below.

(More Expression Semantics)

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{r}\xspace{}\\\
\rho(\mathit{r}\xspace)=\mathit{v}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\>^{*}\mathit{e}\xspace)\Downarrow\mathit{v}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
\sigma(\mathit{x_{mem}}\xspace,\mathit{C}\xspace)=(\mathit{v}\xspace,\mathit{C}\xspace_{l})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{fetch}\xspace(\mathit{e}\xspace,\mathit{C}\xspace_{l}))\Downarrow\mathit{v}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
\sigma(\mathit{x_{mem}}\xspace,\mathit{C}\xspace)=(\\_,\mathit{C}\xspace_{m})\\\
\mathit{C}\xspace_{m}\neq\mathit{C}\xspace_{l}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{fetch}\xspace(\mathit{e}\xspace,\mathit{C}\xspace_{l}))\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace\notin\sigma}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{fetch}\xspace(\mathit{e}\xspace,\mathit{C}\xspace_{l}))\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{0b}\mathit{C}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{fetch}\xspace(\mathit{e}\xspace,\mathit{C}\xspace_{l}))\Downarrow\mathtt{fail}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{C}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{e}\xspace\mathit{)}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}}$

$\inferrule{\Lambda(\mathit{x_{label}}\xspace)=\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace
0\mathit{)}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{label}}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace 0\mathit{)}\xspace{}}$

$\inferrule{\forall\mathit{i}\xspace\in(1\ldots\mathit{k}\xspace),\
\Lambda(\mathit{x}\xspace_{i})=\mathit{r}\xspace_{i}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{\\{}\mathit{x}\xspace_{1},\ldots,\mathit{x}\xspace_{k}\mathit{\\}}\xspace)\Downarrow\mathit{\\{}\mathit{r}\xspace_{1},\ldots,\mathit{r}\xspace_{k}\mathit{\\}}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{\\{}\mathit{r}\xspace_{1},\ldots,\mathit{r}\xspace_{\mathit{C}\xspace}\mathit{\\}}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\|{\mathit{e}\xspace}\|\xspace)\Downarrow\mathit{C}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{r}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{\\{}\mathit{r}\xspace_{1},\ldots,\mathit{r}\xspace_{k}\mathit{\\}}\xspace{}\\\
\exists\mathit{i}\xspace\in(1\ldots\mathit{k}\xspace),\mathit{r}\xspace_{\mathit{i}\xspace}=\mathit{r}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1}\thinspace{\in}\mathit{e}\xspace_{2})\Downarrow\mathtt{true}\xspace{}}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{r}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{\\{}\mathit{r}\xspace_{1},\ldots,\mathit{r}\xspace_{k}\mathit{\\}}\xspace{}\\\
\forall\mathit{i}\xspace\in(1\ldots\mathit{k}\xspace),\mathit{r}\xspace_{\mathit{i}\xspace}\neq\mathit{r}\xspace}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1}\thinspace{\in}\mathit{e}\xspace_{2})\Downarrow\mathtt{false}\xspace{}}$

Expressions. We describe expressions with a big-step operational semantics.
The form of an expression semantic judgment is:
$\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{v}\xspace{}$,
which means that given the environment $\Lambda$ and the machine state
$\rho,\sigma\xspace$, the expression $\mathit{e}$evaluates to the value
$\mathit{v}$. Expressions may refer to the machine state, but not modify it.

Expressions can fail; in addition to the explicit failure cases seen, some of
the operators and built-in functions can fail. For example, as mentioned
earlier, attempting bitvector arithmetic other than addition and subtraction
on pointers will fail. Furthermore, division by zero fails.

Note that we currently do not statically check (in the typing rules) that the
$\mathit{.}\xspace\mathtt{txt}\xspace$ form is present for every register, or
that it is defined for registers on which it is used. Thus we have an explicit
failure rule for when no matching declaration has been seen. We also have
failure rules for bad fetch operations: if the length annotation is wrong, if
the pointer is not in the machine state (this covers both unaligned accesses
and out of bounds accesses), or if the value used is not a pointer. Similarly,
we have failure rules for when bit indexing/slicing a pointer. (We do not,
conversely, need explicit failure checks or rules for the bit indexes in the
bit extraction/slicing constructs as they are statically checked.)

Also note that we include in the semantics the obvious failure propagation
rules for when subexpressions fail. We do not show these explicitly as they
are not particularly interesting or informative.

(Statement Semantics)

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace_{1})\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathtt{skip}\xspace)\\\
\Lambda\vdash\xspace(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace_{2})\Downarrow(\rho^{\prime\prime},\sigma^{\prime\prime}\xspace,\mathit{S}\xspace_{2}^{\prime})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace_{1}\mathit{;}\xspace\
\mathit{S}\xspace_{2})\Downarrow(\rho^{\prime\prime},\sigma^{\prime\prime}\xspace,\mathit{S}\xspace_{2}^{\prime})}$

$\inferrule{\forall\mathit{i}\xspace,\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{i})\Downarrow\mathit{v}\xspace_{i}{}\\\
\Lambda\mathit{(}\mathit{x_{proc}}\xspace\mathit{)}\xspace=\\{\overline{\mathit{x}\xspace_{i}},\mathit{S}\xspace\\}\\\
\Lambda[\forall\mathit{i}\xspace,\mathit{x}\xspace_{i}\mapsto\mathit{v}\xspace_{i}]\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace^{\prime})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{proc}}\xspace\
(\overline{\mathit{e}\xspace_{i}}))\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace^{\prime})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{v}\xspace{}\\\
\Lambda[\mathit{x}\xspace\mapsto\mathit{v}\xspace]\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace^{\prime})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{let}\thinspace\mathit{x}\xspace\
\mathit{:}\
\tau\xspace_{\mathit{base}}=\mathit{e}\xspace\thinspace\texttt{in}\thinspace\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace^{\prime})}$

$\inferrule{\forall\mathit{i}\xspace\in(\mathit{C}\xspace_{1},\mathit{C}\xspace_{1}+1,\
\ldots,\mathit{C}\xspace_{2}),\\\
\Lambda[\mathit{x}\xspace\mapsto\mathit{i}\xspace]\vdash\xspace(\rho_{i},\sigma_{i}\xspace,\mathit{S}\xspace)\Downarrow(\rho_{i+1},\sigma_{i+1}\xspace,\mathtt{skip}\xspace)}{\Lambda\vdash\xspace(\rho_{\\\
tC_{1}},\sigma_{\mathit{C}\xspace_{1}}\xspace,\texttt{for}\thinspace\mathit{x}\xspace\in(\mathit{C}\xspace_{1}\ldots\mathit{C}\xspace_{2})\
\texttt{do}\thinspace\mathit{S}\xspace)\Downarrow(\rho_{\mathit{C}\xspace_{2}+1},\sigma_{\mathit{C}\xspace_{2}+1}\xspace,\mathtt{skip}\xspace)}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{true}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho_{t},\sigma_{t}\xspace,\mathit{S}\xspace_{t})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{if}\thinspace\mathit{e}\xspace\thinspace\texttt{then}\thinspace\mathit{S}\xspace\thinspace\texttt{else}\thinspace\\_)\Downarrow(\rho_{t},\sigma_{t}\xspace,\mathit{S}\xspace_{t})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{false}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho_{f},\sigma_{f}\xspace,\mathit{S}\xspace_{f})}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\texttt{if}\thinspace\mathit{e}\xspace\thinspace\texttt{then}\thinspace\\_\thinspace\texttt{else}\thinspace\mathit{S}\xspace)\Downarrow(\rho_{f},\sigma_{f}\xspace,\mathit{S}\xspace_{f})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{r}\xspace{}\\\
\mathit{r}\xspace\in\rho\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{v}\xspace{}\\\
\rho^{\prime}=\rho[\mathit{r}\xspace\mapsto\mathit{v}\xspace]}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1}\thinspace\mathit{:}\xspace=\mathit{e}\xspace_{2})\Downarrow(\rho^{\prime},\sigma,\mathtt{skip}\xspace)}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
\sigma(\mathit{x_{mem}}\xspace,\mathit{C}\xspace)=(\\_,\mathit{C}\xspace_{l})\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{2})\Downarrow\mathit{v}\xspace{}\\\
\sigma^{\prime}=\sigma[{\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace}\mapsto(\mathit{v}\xspace,\mathit{C}\xspace_{l})]}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{store}\xspace(\mathit{e}\xspace_{1},\mathit{C}\xspace_{l})\leftarrow\mathit{e}\xspace_{2})\Downarrow(\rho,\sigma^{\prime},\mathtt{skip}\xspace)}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
\sigma(\mathit{x_{mem}}\xspace,\mathit{C}\xspace)=(\\_,\mathit{C}\xspace_{m})\\\
\mathit{C}\xspace_{m}\neq\mathit{C}\xspace_{l}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{store}\xspace(\mathit{e}\xspace_{1},\mathit{C}\xspace_{l})\leftarrow\mathit{e}\xspace_{2})\Downarrow(\rho,\sigma,\mathtt{crash})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace{}\\\
{\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace}\notin\sigma}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{store}\xspace(\mathit{e}\xspace_{1},\mathit{C}\xspace_{l})\leftarrow\mathit{e}\xspace_{2})\Downarrow(\rho,\sigma,\mathtt{crash})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{1})\Downarrow\mathtt{0b}\mathit{C}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{store}\xspace(\mathit{e}\xspace_{1},\mathit{C}\xspace_{l})\leftarrow\mathit{e}\xspace_{2})\Downarrow(\rho,\sigma,\mathtt{crash})}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{true}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{assert}\xspace(\mathit{e}\xspace))\Downarrow(\rho,\sigma\xspace,\mathtt{skip}\xspace)}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathtt{false}\xspace{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathtt{assert}\xspace(\mathit{e}\xspace))\Downarrow(\rho,\sigma\xspace,\mathtt{crash})}$

Statements. Unlike expressions, statements can change machine state. Thus, the
form of a machine state semantics judgment (also large step) is
$\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{S}\xspace^{\prime})$.
This means that the statement $\mathit{S}$evaluates to the irreducible
statement $\mathit{S}$’ (which must be either $\mathtt{skip}$or
$\mathtt{crash}$) and in the course of doing so changes the machine state from
$\rho,\sigma$to $\rho^{\prime},\sigma^{\prime}$.

As with expressions, statements can fail. Explicit failure rules are shown for
bad stores (corresponding to the cases for bad fetches) and for a failed
assertions. We also similarly include, but do not show, the obvious failure
propagation rules for cases where sub-statements, or expressions within
statements, fail.

(Declaration Semantics)

$\inferrule{~{}}{\Lambda,(\rho,\sigma)\vdash\epsilon\rhd\xspace\Lambda}$

$\inferrule{\Lambda,(\rho,\sigma)\vdash\mathit{decl}\xspace\rhd\xspace\Lambda^{\prime}\\\
\Lambda^{\prime},(\rho,\sigma)\vdash\mathit{decls}\xspace\rhd\xspace\Lambda^{\prime\prime}}{\Lambda,(\rho,\sigma)\vdash\mathit{decl}\xspace\mathit{;}\xspace\
\mathit{decls}\xspace\rhd\xspace\Lambda^{\prime\prime}}$

$\inferrule{~{}}{\Lambda,(\rho,\sigma)\vdash\mathtt{type}\xspace\
\mathit{x_{\tau}}\xspace=\tau\xspace_{\mathit{base}}\rhd\xspace\Lambda}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{v}\xspace{}}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\
\mathit{x}\xspace\ \mathit{:}\xspace\
\tau\xspace_{\mathit{base}}=\mathit{e}\xspace\rhd\xspace\Lambda[\mathit{x}\xspace\mapsto\mathit{v}\xspace]}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x}\xspace)\Downarrow\mathit{r}\xspace{}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace)\Downarrow\mathit{v}\xspace{}}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\
\mathit{x}\xspace\mathit{.}\xspace\mathtt{txt}\xspace=e\rhd\xspace\Lambda[\mathit{r}\xspace\mathit{.}\xspace\mathtt{txt}\xspace\mapsto\mathit{v}\xspace]}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x_{func}}\xspace\mapsto\\{\overline{\mathit{x}\xspace_{i}},\mathit{e}\xspace\\}]}{\Lambda,(\rho,\sigma)\vdash\mathtt{def}\xspace\
\mathit{x_{func}}\xspace\ \overline{\mathit{x}\xspace_{i}\ \mathit{:}\xspace\
\tau\xspace_{{\mathit{base}}_{i}}}\rightarrow\tau\xspace_{\mathit{base}}\xspace=\mathit{e}\xspace\rhd\xspace\Lambda^{\prime}}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x_{proc}}\xspace\mapsto\\{\overline{\mathit{x}\xspace_{i}},\mathit{S}\xspace\\}]}{\Lambda,(\rho,\sigma)\vdash\mathtt{proc}\xspace\
\mathit{x_{proc}}\xspace\ \overline{\mathit{x}\xspace_{i}\ \mathit{:}\xspace\
\tau\xspace_{{\mathit{base}}_{i}}}\rightarrow()\xspace=\mathit{S}\xspace\rhd\xspace\Lambda^{\prime}}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x}\xspace\mapsto\mathit{r}\xspace]\\\
\mathit{r}\xspace\
\mathrm{fresh}}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\mathtt{state}\xspace\
\mathit{x}\xspace\ \mathit{:}\xspace\
\tau\xspace_{\mathit{reg}}\rhd\xspace\Lambda^{\prime}}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x}\xspace\mapsto\mathit{r}\xspace]\\\
\mathit{r}\xspace\
\mathrm{fresh}}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\mathtt{state}\xspace\
\mathtt{control}\xspace\ \mathit{x}\xspace\ \mathit{:}\xspace\
\tau\xspace_{\mathit{reg}}\rhd\xspace\Lambda^{\prime}}$

$\inferrule{~{}}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\mathtt{state}\xspace\
\mathit{x_{mem}}\xspace\ \mathit{:}\xspace\
\tau\xspace_{\mathit{mem}}\rhd\xspace\Lambda}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x_{label}}\xspace\mapsto\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace 0\mathit{)}\xspace]\\\
}{\Lambda,(\rho,\sigma)\vdash\mathtt{let}\xspace\mathtt{state}\xspace\
\mathit{x_{mem}}\xspace\ \mathit{:}\xspace\ \tau\xspace_{\mathit{mem}}\
\mathtt{with}\xspace\ \mathit{x_{label}}\xspace\rhd\xspace\Lambda^{\prime}}$

$\inferrule{~{}}{\Lambda,(\rho,\sigma)\vdash\epsilon\rhd\xspace\Lambda}$

$\inferrule{\Lambda,(\rho,\sigma)\vdash\mathit{defop}\xspace\rhd\xspace\Lambda^{\prime}\\\
\Lambda^{\prime},(\rho,\sigma)\vdash\mathit{defops}\xspace\rhd\xspace\Lambda^{\prime\prime}}{\Lambda,(\rho,\sigma)\vdash\mathit{defop}\xspace\mathit{;}\xspace\
\mathit{defops}\xspace\rhd\xspace\Lambda^{\prime}}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x_{op}}\xspace\mapsto\\{[~{}],\mathit{e}\xspace,S\\}]}{\Lambda,(\rho,\sigma)\vdash\mathtt{defop}\xspace\
\mathit{x_{op}}\xspace\
\mathit{\\{}\mathtt{txt}\xspace=\mathit{e}\xspace\mathit{,}\
\xspace\mathtt{sem}\xspace=\mathit{S}\xspace\mathit{\\}}\xspace\rhd\xspace\Lambda^{\prime}}$

$\inferrule{\Lambda^{\prime}=\Lambda[\mathit{x_{op}}\xspace\mapsto\\{\overline{x_{i}},\mathit{e}\xspace,S\\}]}{\Lambda,(\rho,\sigma)\vdash\mathtt{defop}\xspace\
\mathit{x_{op}}\xspace\ \overline{\mathit{x}\xspace_{i}\ \mathit{:}\xspace\
\tau\xspace_{{\mathit{base}}_{i}}}\
\mathit{\\{}\mathtt{txt}\xspace=\mathit{e}\xspace\mathit{,}\
\xspace\mathtt{sem}\xspace=\mathit{S}\xspace\mathit{\\}}\xspace\rhd\xspace\Lambda^{\prime}}$

Declarations. The semantics for declarations have judgments of the form
$\Lambda,(\rho,\sigma)\vdash\mathit{decl}\xspace\rhd\xspace\Lambda^{\prime}$.
This means that the given declaration updates $\Lambda$ as shown.

As stated above, we do not _initialize_ the machine state while handling
declarations; this instead allows us to work with arbitrary (or universally
quantified) machine states afterwards. However, because the let-binding
declaration evaluates an expression, it potentially needs _access_ to a
machine state. Consequently we write the rules so they accept a machine state
as input, but do not update it. In the case of machine descriptions, where
there is no machine state, we pass empty environments; let declarations in
machine descriptions are not allowed to reference machine state. In the case
of the additional declarations that accompany a specification, we pass in the
initial machine state; this allows values from the initial machine state to be
globally bound so they can be referred to in the postcondition.

We give first the rules for a list of declarations (which chain in the obvious
way), then the rules for the various declarations, then the rules for a list
of operation definitions (which chain in the same way) and a rule for a single
operation definition.

Note that several of the declarations do not update $\Lambda$, and nothing is
placed in $\Lambda$ for memory regions. (And for registers, only the mapping
of the identifier to its underlying register $\mathit{r}$is entered; nothing
for $\mathit{r}$is inserted.)

(Machine Semantics)

$\inferrule{\Lambda_{\mathit{builtin}},(\\{\\},\\{\\})\vdash\mathit{decls}\xspace\rhd\xspace\Lambda\\\
\Lambda\vdash\mathit{defops}\xspace\rhd\xspace\Lambda^{\prime}}{\vdash\mathit{decls}\xspace\mathit{;}\xspace\
\mathit{defops}\xspace\rhd\xspace\Lambda^{\prime}}$

Machines. Like with the typing rules, the semantics rule for a whole machine
description bakes in the initial environment and gives a judgment of the form
$\vdash\mathit{machine}\xspace\rhd\xspace\Lambda^{\prime}$.

We also include a comparable form that includes additional declarations, as it
will be used below.

Programs. Instructions update the machine state, and we chose to represent
programs as lists of instructions (rather than having dummy instruction forms
for skip and sequence) so the form of the judgments is slightly different:
$\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{inst}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime}\xspace)$
means that the instruction executes and updates the machine state
$\rho,\sigma$to $\rho^{\prime},\sigma^{\prime}$. The judgments for lists of
programs has the same form.

There are two versions of the judgment for instructions because instructions
with no arguments are declared as taking unit, but invoked with empty operands
(not with unit) to correspond to the way assembly languages normally work.

We include a final judgment of the form
$\mathit{machine}\xspace\vdash\xspace(\rho,\sigma\xspace,\mathit{program}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime})$
that puts the machine on the left-hand side of the turnstile. It means that
under a given machine the program maps $\rho,\sigma$to
$\rho^{\prime},\sigma^{\prime}$.

There is a limitation in the way we have formulated programs and the rules for
programs, which is that there is no easy way to represent failure. (Failure in
this might represent triggering an exception and stopping execution, which we
do not model, or invoking “unpredictable” or “undefined” behavior in the
processor and transitioning to an arbitrary unknown machine state.)

The intended behavior is that a program that fails during execution (that is,
the body of one of its instructions steps to $\mathtt{crash}$) enters a state
where no postcondition can evaluate to $\mathtt{true}$. We have decided for
the moment that working this explicitly into the formalism would result in a
lot of complication and obscuration without providing any useful information.

(Program Semantics)

$\inferrule{\Lambda(\mathit{x_{op}}\xspace)=\\{[~{}],\\_,S)\\}\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathtt{skip}\xspace)}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{op}}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime}\xspace)}$

$\inferrule{\forall\mathit{i}\xspace,\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{e}\xspace_{i})\Downarrow\mathit{v}\xspace_{i}{}\\\
\Lambda(\mathit{x_{op}}\xspace)=\\{\overline{\mathit{x}\xspace_{i}},\\_,S\\}\\\
\Lambda^{\prime}=\Lambda[\forall
i,\mathit{x}\xspace_{i}\mapsto\mathit{v}\xspace_{i}]\\\
\Lambda^{\prime}\vdash\xspace(\rho,\sigma\xspace,\mathit{S}\xspace)\Downarrow(\rho^{\prime},\sigma^{\prime}\xspace,\mathtt{skip}\xspace)}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{op}}\xspace\
\overline{\mathit{e}\xspace_{i}})\rightarrow(\rho^{\prime},\sigma^{\prime}\xspace)}$

$\inferrule{~{}}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\epsilon)\rightarrow(\rho,\sigma\xspace)}$

$\inferrule{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{inst}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime}\xspace)\\\
\Lambda\vdash\xspace(\rho^{\prime},\sigma^{\prime}\xspace,\mathit{insts}\xspace)\rightarrow(\rho^{\prime\prime},\sigma^{\prime\prime}\xspace)}{\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{inst}\xspace\mathit{;}\xspace\
\mathit{insts}\xspace)\rightarrow(\rho^{\prime\prime},\sigma^{\prime\prime}\xspace)}$

$\inferrule{\vdash\mathit{machine}\xspace\rhd\xspace\Lambda\\\
\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{program}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime})}{\mathit{machine}\xspace\vdash\xspace(\rho,\sigma\xspace,\mathit{program}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime})}$

(Spec Semantics)

$\inferrule{\forall\mathit{i}\xspace,\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{x_{{\mathit{reg}}_{i}}}\xspace)\Downarrow\mathit{r}\xspace_{i}{}\\\
\forall\mathit{r}\xspace\notin\\{\overline{\mathit{r}\xspace_{i}}\\},\rho(\mathit{r}\xspace)=\rho^{\prime}(\mathit{r}\xspace)}{\Lambda,\rho,\rho^{\prime}\vdash\mathtt{reg\text{-}modify}\xspace\
\mathit{:}\xspace\ \overline{\mathit{x_{{\mathit{reg}}_{i}}}\xspace}}$

$\inferrule{\forall\mathit{i}\xspace,\Lambda\vdash\xspace(\rho,\sigma\xspace,\mathit{(}\mathit{x_{mem}}_{i}\xspace\mathit{,}\
\xspace\mathit{e}\xspace_{i}\mathit{)}\xspace)\Downarrow\mathit{(}\mathit{x_{mem}}_{i}\xspace\mathit{,}\
\xspace\mathit{C}\xspace_{i}\mathit{)}\xspace{}\\\
\forall\mathit{x_{mem}}\xspace,\mathit{C}\xspace,\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace\notin\\{\overline{\mathit{(}\mathit{x_{mem}}_{i}\xspace\mathit{,}\
\xspace\mathit{C}\xspace_{i}\mathit{)}\xspace}\\},\\\
\sigma(\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace)=\sigma^{\prime}(\mathit{(}\mathit{x_{mem}}\xspace\mathit{,}\
\xspace\mathit{C}\xspace\mathit{)}\xspace)}{\Lambda,\sigma,\sigma^{\prime}\vdash\mathtt{mem\text{-}modify}\xspace\
\mathit{:}\xspace\ \overline{\mathit{(}\mathit{x_{mem}}_{i}\xspace\mathit{,}\
\xspace\mathit{e}\xspace_{i}\mathit{)}\xspace}}$

$\inferrule{\vdash\mathit{machine}\xspace\mathit{;}\xspace\
\mathit{decls}\xspace\rhd\xspace\Delta,\Gamma\\\
\vdash\mathit{machine}\xspace\rhd\xspace\Lambda\\\ \forall\rho,\sigma\xspace,\
\left(\Delta,\Gamma,\Lambda\vdash\rho,\sigma\xspace\right)\implies\\\
\Lambda,(\rho,\sigma)\vdash\mathit{decls}\xspace\rhd\xspace\Lambda^{\prime}\implies\\\
\Lambda^{\prime}\vdash\xspace(\rho,\sigma\xspace,\mathit{pre}\xspace)\Downarrow\mathtt{true}\xspace{}\implies\\\
\forall\rho^{\prime},\sigma^{\prime},\left(\Lambda^{\prime}\vdash\xspace(\rho,\sigma,\mathit{program}\xspace)\rightarrow(\rho^{\prime},\sigma^{\prime})\right)\implies\\\
(\Lambda^{\prime}\vdash\xspace(\rho^{\prime},\sigma^{\prime},\mathit{post}\xspace)\Downarrow\mathtt{true}\xspace{}\
\wedge\\\
\Lambda^{\prime},\rho,\rho^{\prime}\vdash\mathit{frame}\xspace\wedge\
\Lambda^{\prime},\sigma,\sigma^{\prime}\vdash\mathit{frame}\xspace)}{\mathit{machine}\xspace,(\mathit{decls}\xspace\mathit{;}\xspace\
\mathit{frame}\xspace\mathit{;}\xspace\ \mathit{pre}\xspace\mathit{;}\xspace\
\mathit{post}\xspace)\vdash\mathit{program}\xspace}$

Specifications. For specifications we need three judgments: the first two
state what the $\mathtt{reg\text{-}modify}$and
$\mathtt{mem\text{-}modify}$clauses mean, respectively (they are properties on
initial and final register and memory states), and the last one says what it
means for a program to satisfy a specification.

Note that the $\mathtt{reg\text{-}modify}$and $\mathtt{mem\text{-}modify}$rule
as shown is slightly misleading, because the register and pointer list
actually written in the input file is implicitly augmented with all registers
and pointers mentioned in the postcondition before it gets to this point.

(Machine State Validity)
$\inferrule{\left(\forall\mathit{x}\xspace,\
\Delta,\Gamma\vdash\mathit{x}\xspace\ \mathit{:}\xspace\ \mathit{C}\xspace\
\mathtt{reg}\xspace\wedge\Lambda(\mathit{x}\xspace)=\mathit{r}\xspace\right)\Leftrightarrow\\\
\left(\exists\mathit{v}\xspace,\
\rho(\mathit{r}\xspace)=\mathit{v}\xspace\wedge\Delta,\Gamma\vdash\mathit{v}\xspace\
\mathit{:}\xspace\ \mathit{C}\xspace\
\mathtt{bit}\xspace\right)}{\Delta,\Gamma,\Lambda\vdash\rho}$

$\inferrule{\forall\mathit{x_{mem}}\xspace,\
\Delta,\Gamma\vdash\mathit{x_{mem}}\xspace\ \mathit{:}\xspace\
\mathit{C}\xspace_{1}\ \mathtt{bit}\xspace\ \mathit{C}\xspace_{2}\
\mathtt{len}\xspace\ \mathit{C}\xspace_{3}\ \texttt{ref}\Leftrightarrow\\\
(\forall\mathit{i}\xspace\in\\{0,\mathit{C}\xspace_{1}/8,\dots,(\mathit{C}\xspace_{2}-1)*\mathit{C}\xspace_{1}/8\\},\\\
\exists\mathit{v}\xspace,\
\sigma(\mathit{x_{mem}}\xspace,\mathit{i}\xspace)=(\mathit{v}\xspace,\mathit{C}\xspace_{1})\wedge\Delta,\Gamma\vdash\mathit{v}\xspace\
\mathit{:}\xspace\ \mathit{C}\xspace_{1}\
\mathtt{bit}\xspace)}{\Delta,\Gamma\vdash\sigma}$

$\inferrule{\Delta,\Gamma,\Lambda\vdash\rho\\\
\Delta,\Gamma\vdash\sigma}{\Delta,\Gamma,\Lambda\vdash\rho,\sigma\xspace}$

Machine state validity. As discussed above we do not initialize the machine
state while processing declarations. Instead we treat the starting machine
state as an input (e.g. in the final judgment about programs) or quantify it
universally (as in the specification judgment). In order to do this we must,
however, have a predicate to reject machine states that do not match the
machine description.

The validity judgment has the form $\Delta,\Gamma,\Lambda\vdash\rho$, and
correspondingly for $\sigma$ (except without $\Lambda$) and then for
$\rho,\sigma\xspace$ (both stores at once). It means that the given stores
match the given environments.

We will use this with the typing environments that come from both the machine
description and the additional declarations arising from a specification.
(Recall that memory regions are normally defined by specifications and not by
machines.)

In the case of registers we need access to $\Lambda$ in order to handle the
names of registers. We do _not_ use the $\Lambda$ generated from the
additional declarations in a specification; this avoids circularity. We can
get away with this because specifications are not allowed to define new
registers.

For memory regions we need to enumerate the valid offsets for the region (note
the literal 8 that hardwires 8-bit bytes) and check the cell width.