Rondroarivelo Rasoahanitralisoa

Niaina Rakotosamimanana
email: niaina@pasteur.mg

David Stucki

Christophe Sola

Sébastien Gagneux

Rasolofo Voahangy

Razanamparany

Sebastien Gagneux

Voahangy Rasolofo Razanamparany

Evaluation of spoligotyping, SNPs and customised MIRU-VNTR combination for genotyping Mycobacterium tuberculosis clinical isolates in Madagascar

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

M. tuberculosis is a widespread global human pathogen whose infection causes an estimated 10.4 million cases of tuberculosis (TB) and 1.8 million deaths every year [START_REF] Razanamparany | Global tuberculosis report 2015[END_REF]. TB epidemiology and transmission chain study has traditionally been performed by molecular strain typing [START_REF] Thumamo | Molecular epidemiology and genetic diversity of Mycobacterium tuberculosis complex in the Cross River State, Nigeria[END_REF][START_REF] Rasolofo-Razanamparany | Transmission of tuberculosis in the prison of Antananarivo (Madagascar)[END_REF][START_REF] Mathema | Molecular epidemiology of tuberculosis: current insights[END_REF]. Utilizing PCR-based methods for genotyping M. tuberculosis complex (MTBC) isolates helps public health officials manage TB outbreaks through identification of MTBC population involved in outbreaks and monitoring of their transmission dynamics [START_REF] Moss | Tuberculosis in the homeless. A prospective study[END_REF][START_REF] Saavedra-Campos | Identifying areas and risk groups with localised Mycobacterium tuberculosis transmission in northern England from 2010 to 2012: spatiotemporal analysis incorporating highly discriminatory genotyping data[END_REF].

SNP-typing, spoligotyping, and MIRU-VNTR typing are three PCR-based typing method used for molecular epidemiology of MTBC strains. SNP-typing, which is based on single nucleotide changes in specific regions of MTBC genomes, is particularly useful for classifying mycobacterial isolates into the main phylogenetic lineages and sub-lineages of the MTBC depending on the number of SNPs assessed [START_REF] Comas | Genotyping of genetically monomorphic bacteria: DNA sequencing in Mycobacterium tuberculosis highlights the limitations of current methodologies[END_REF]. Spoligotyping reveals the absence or presence of unique spacer sequences located between the direct-repeat (DR) sequences of the Clustered Regularly Interspersed Short Palindromic Repeat (CRISPR) region of MTBC genomes [START_REF] Kamerbeek | Simultaneous detection and strain differentiation of Mycobacterium tuberculosis for diagnosis and epidemiology[END_REF]. This method is a membrane-based reverse-line blotting procedure, recently adapted to a highthroughput microbead-based format, whose digital results ease the exchange of data between laboratories [START_REF] Sola | Clustured regularly interspersed short palindromic repeats (CRISPR) genetic diversity studies as a mean to reconstruct the evolution of the Mycobacterium tuberculosis complex[END_REF]. However, it is limited by its discrimination power for epidemiology studies and of homoplasies in the DR region that result from convergent evolution [START_REF] Sola | Clustured regularly interspersed short palindromic repeats (CRISPR) genetic diversity studies as a mean to reconstruct the evolution of the Mycobacterium tuberculosis complex[END_REF][START_REF] Stucki | Standard Genotyping Overestimates Transmission of Mycobacterium tuberculosis among Immigrants in a Low-Incidence Country[END_REF].

MIRU-VNTR is used to type minisatellite-like loci in the MTBC genome that show polymorphism in the number of tandem repeats. A wide range of MTBC MIRU-VNTR loci that variably discriminate the MTBC populations in the main bacterial lineages have been evaluated [START_REF] Comas | Genotyping of genetically monomorphic bacteria: DNA sequencing in Mycobacterium tuberculosis highlights the limitations of current methodologies[END_REF][START_REF] Supply | Proposal for standardization of optimized mycobacterial interspersed repetitive unit-variable-number tandem repeat typing of Mycobacterium tuberculosis[END_REF]. MIRU-VNTR typing has the advantages in the ease of its execution and the generation of results in a digital format [START_REF] Streit | Finer characterization of Mycobacterium tuberculosis using spoligotyping and 15-loci MIRU-VNTRs reveals phylogeographical specificities of isolates circulating in Guyana and Suriname[END_REF][START_REF] Chaoui | Contribution of spoligotyping and MIRU-VNTRs to characterize prevalent Mycobacterium tuberculosis genotypes infecting tuberculosis patients in Morocco[END_REF][START_REF] Asante-Poku | Evaluation of customised lineage-specific sets of MIRU-VNTR loci for genotyping Mycobacterium tuberculosis complex isolates in Ghana[END_REF]. MIRU-VNTR has advantages over spoligotyping in its ability to study the diversity and clonal expansion of particular strains at a relatively high resolution, but it can be tedious, labour-intensive, and time consuming due to the large number of loci to screen, although a recently optimized duplex gel-based procedure reduces the workload [START_REF] Vasconcellos | Strain classification of Mycobacterium tuberculosis isolates in Brazil based on genotypes obtained by spoligotyping, mycobacterial interspersed repetitive unit typing and the presence of large sequence and single nucleotide polymorphism[END_REF]. Optimized 12,[START_REF] Vasconcellos | Strain classification of Mycobacterium tuberculosis isolates in Brazil based on genotypes obtained by spoligotyping, mycobacterial interspersed repetitive unit typing and the presence of large sequence and single nucleotide polymorphism[END_REF], or 24-locus MIRU-VNTR typing systems have been proposed for international standardization [START_REF] Supply | Proposal for standardization of optimized mycobacterial interspersed repetitive unit-variable-number tandem repeat typing of Mycobacterium tuberculosis[END_REF]. The 15-loci MIRU-VNTR format evaluated for MTBC molecular epidemiological studies showed that 15 and 24 MIRU-VNTR formats provided a similar level of discrimination [START_REF] Silva | Mycobacterial interspersed repetitive unit typing and mutational profile for multidrug-resistant and extensively drug-resistant tuberculosis surveillance in Portugal: a 3-year period overview[END_REF]. However, the initial selection of the loci used for MIRU-VNTR has been reported as biased towards strains of specific lineages and varies in discrimination power within these main MTBC lineages or populations [START_REF] Comas | Genotyping of genetically monomorphic bacteria: DNA sequencing in Mycobacterium tuberculosis highlights the limitations of current methodologies[END_REF][START_REF] Supply | Proposal for standardization of optimized mycobacterial interspersed repetitive unit-variable-number tandem repeat typing of Mycobacterium tuberculosis[END_REF]. Customized MIRU-VNTR loci have been proposed to improve the discrimination resolution in specific Ghanaian MTBC populations [START_REF] Asante-Poku | Evaluation of customised lineage-specific sets of MIRU-VNTR loci for genotyping Mycobacterium tuberculosis complex isolates in Ghana[END_REF]. Moreover, different studies reported that a combination of MIRU-VNTR typing and spoligotyping offers a better tool for assessment of -TB epidemiology [START_REF] Streit | Finer characterization of Mycobacterium tuberculosis using spoligotyping and 15-loci MIRU-VNTRs reveals phylogeographical specificities of isolates circulating in Guyana and Suriname[END_REF][START_REF] Chaoui | Contribution of spoligotyping and MIRU-VNTRs to characterize prevalent Mycobacterium tuberculosis genotypes infecting tuberculosis patients in Morocco[END_REF][START_REF] Lu | Genotypes of Mycobacterium tuberculosis isolates in rural China: using MIRU-VNTR and spoligotyping methods[END_REF]. The combination of both spoligotyping and MIRU-VNTR methods has been reported to provide a similar resolving power relative to the labour-intensive procedure of IS6110 restriction fragment length polymorphism (RFLP) previously used as a standard for the study of TB transmission [START_REF] Maes | 24-locus MIRU-VNTR genotyping is a useful tool to study the molecular epidemiology of tuberculosis among Warao Amerindians in Venezuela[END_REF].

The main goal of this study was to evaluate the combination of spoligotyping with a customized and reduced MIRU-VNTR loci set compared to the reference 15 loci MIRU-VNTR for four out of seven main MTBC lineages (lineage 1, 2, 3 and 4) that are present in Madagascar for an optimal classification of those MTBC strains.

Materials and methods

Clinical isolates

Clinical MTBC strains that had previously been typed by spoligotyping were selected in this study to represent the major spoligotype families in Madagascar [START_REF] Kamerbeek | Simultaneous detection and strain differentiation of Mycobacterium tuberculosis for diagnosis and epidemiology[END_REF]. Studied strains were selected from the collections of the Mycobacterial unit of the Institute Pasteur of Madagascar. Briefly, 31 strains from Lineage 2 (Beijing), 23 strains from Lineage 3 (Central Asian, CAS), 23 strains from Lineage 1 (East African Indian, EAI), and 81 from Lineage 4 (Euro-American, specifically 18 strains of Haarlem (H), 17 strains of Latino-American (LAM) and 46 strains from the T default spoligotype signature) were studied.

SNP-typing method

The major phylogenetic lineage of MTBC isolates was determined by SNP-typing using Taq-Man simplex real time PCR as previously described [START_REF] Stucki | Two new rapid SNP-typing methods for classifying Mycobacterium tuberculosis complex into the main phylogenetic lineages[END_REF]. This method is performed to screen SNPs on six genomic regions (katG463, Rv2952, Rv3221c, Rv3804c, gyrA1842 and Psts1) S1 Table . Briefly, 10 ng of DNA was added to a final volume of 12μl containing 5μl TaqMan Universal Master Mix II (Qiagen), 0.05 pmol of wild type probe labelled by FAM and mutant probe labelled by VIC, and 0.83 pmol of each reverse and forward primers for targeted regions S2 Table . The mix reaction was run in a StepOne thermocycler (Applied Biosystems) under the following conditions: 60˚C for 30 sec, 95˚C 10 minutes, 95˚C for 15 sec and 60˚C for 1 min for 40 cycles; 60˚C for 30 sec. Fluorescence intensities from the VIC and FAM channels were measured at the end of every cycle. Alleles were obtained with the StepOne software (Applied Biosystems) [START_REF] Stucki | Two new rapid SNP-typing methods for classifying Mycobacterium tuberculosis complex into the main phylogenetic lineages[END_REF].

MIRU-VNTR typing

MIRU-VNTR typing was initially performed using 15 MIRU-VNTR loci as previously described [START_REF] Supply | Proposal for standardization of optimized mycobacterial interspersed repetitive unit-variable-number tandem repeat typing of Mycobacterium tuberculosis[END_REF]. Briefly, the 15 MIRU-VNTR loci were amplified in separate PCRs with the primers described in S3 Table . Reaction volumes of 15μl contained 1.5μl of 10X Q solution, 2μl of 5 μM primer set, 2 μl (4mM) of dNTP, 0.1 μl of Taq polymerase (0.5 unit) (Eurobio), 0.75μl of DMSO (100%), 3 μl (5M) of betaïne and 3.65 μl of pure H2O. Template DNA (10ng) was added to each PCR mix. M. tuberculosis H37Rv was included in each set of reactions as a positive control and sterile distilled water as a negative non-template control. Amplification was performed in a thermocycler (Techne, Flexigene) with an initial denaturation step of 94˚C for 5 min, followed by 35 cycles of: 94˚C for 30 sec, 61˚C for 30 sec (55˚C for Mtub04, Mtub39, Qub11b, Qub4156), and 70˚C for 45 sec. Qub26 had an additional cycle of 70˚C for 1 min and 30 sec prior to the cycle of 70˚C for 45 sec. The final extension was 72˚C for 7 min. The amplified products were visualized by 2% agarose gel electrophoresis. The sizes of the amplicons were estimated by comparison with 100 bp molecular ladders [START_REF] Supply | Variable human minisatellite-like regions in the Mycobacterium tuberculosis genome[END_REF]. The allele assignment was determined by comparison with a reference allelic table as given in S4 Table . A cluster of MTBC strains was thus defined as two or more strains with identical MIRU-VNTR genotype patterns.

To search for the concordance between spoligotyping and 15 MIRU-VNTR typing, the 15 MIRU-VNTR profiles obtained from the strains tested were identified in the MIRU-VNTRplus database accessible at https://info-demo.lirmm.fr/tbminer/ [START_REF] Allix-Beguec | Evaluation and strategy for use of MIRU-VNTRplus, a multifunctional database for online analysis of genotyping data and phylogenetic identification of Mycobacterium tuberculosis complex isolates[END_REF][START_REF] Aze | Genomics and Machine Learning for Taxonomy Consensus: The Mycobacterium tuberculosis Complex Paradigm[END_REF].

Determination of MTBC spoligotype family and lineage specific MIRU-VNTR loci

Principal component analysis (PCA) based on the 15 MIRU-VNTR data from the studied clinical MTBC strains was performed to determine which group of MIRU-VNTR loci had the ability to identify a specific spoligotype family. The spoligotype family column was used as supplementary variables which had no influence on the principal components of the analysis. The correlation coefficient matrix of the selected MIRU-VNTR loci was generated based on its allele frequency data. The first two principal components (PCs) that explain most of the variation were used to plot the 15 MIRU-VNTR loci in a two-dimensional scatter plot. PCA were performed in package FactoMineR of R software (https://www.r-project.org/).

HGDI calculation and determination of minimal set of MIRU-VNTR loci

The calculation of the discriminatory power of every studied typing method was based on Simpson's index of diversity as described by Hunter and Gaston [START_REF] Hunter | Numerical index of the discriminatory ability of typing systems: an application of Simpson's index of diversity[END_REF]. This value is commonly referred to as the Hunter-Gaston discriminatory index (HGDI) and was calculated by using the Web tool http://insilico.ehu.es/minitools/discriminatory power. HGDI was used to quantify the discriminatory power of each typing method used in isolation or combination and to evaluate the allelic diversity of the different MIRU-VNTR loci. Based on their respective HGDI score, the discriminatory powers were classified as high (HGDI!0.6), moderate (0.3 HGDI 0.6) or low (HGDI 0.3) [START_REF] Supply | Variable human minisatellite-like regions in the Mycobacterium tuberculosis genome[END_REF][START_REF] Sola | Genotyping of the Mycobacterium tuberculosis complex using MIRUs: association with VNTR and spoligotyping for molecular epidemiology and evolutionary genetics[END_REF][START_REF] Cowan | Evaluation of a two-step approach for large-scale, prospective genotyping of Mycobacterium tuberculosis isolates in the United States[END_REF].

To identify a minimal set of MIRU-VNTR loci with an equal discriminatory power as the entire 15 MIRU-VNTR loci set, the loci were ranked in increasing HGDI order and all highly discriminant loci (HGDI ! 0.6) were selected; then the other MIRU-VNTR loci were added in a stepwise manner until the HGDI of the reference 15 loci MIRU-VNTR was attained [START_REF] Luo | Development of a hierarchical variable-number tandem repeat typing scheme for Mycobacterium tuberculosis in China[END_REF].

Results

Concordance and discriminatory power of the different genotyping methods

The 158 MTBC strains were divided into four major phylogenetic lineages after genotyping with the 6 SNP regions. In all, SNP-typing assigned 23 isolates into the lineage 1 (14.6%), 31 into lineage 2 (19.6%), 23 into lineage 3 (14.6%) and 81 into lineage 4 (51.3%). Concordance was observed with the classification made with spoligotyping in all strains except for in one which was classified as lineage 3 by spoligotyping but was classified into both lineage 2 and lineage 3 by SNP-typing, possibly suggesting a mixed infection with two strains of MTBC.

When comparing the genotypes obtained with spoligotyping with the 15 MIRU-VNTR typing, concordance was found between spoligotyping and 15 MIRU-VNTR typing for 148 strains (93.7%), while no concordance was found for 10 (6.3%) strains. Full concordance was found for 31 Beijing and 18 Haarlem strains. For CAS, EAI, LAM and T spoligotype family strains, concordances of 95.7%, 87%, 82.4%, 93.5% were observed, respectively. One strain that was classified in both lineage 2 and lineage 3 by the SNP-typing was classified as Beijing by MIRU-VNTR typing. Three strains classified as EAI (13%) and 3 strains classified as LAM (17.6%) by spoligotyping were classified, respectively, as LAM and Haarlem by [START_REF] Vasconcellos | Strain classification of Mycobacterium tuberculosis isolates in Brazil based on genotypes obtained by spoligotyping, mycobacterial interspersed repetitive unit typing and the presence of large sequence and single nucleotide polymorphism[END_REF]

Discriminatory power of the 15 MIRU-VNTR loci to separate the spoligotype families

To define the MIRU-VNTR loci that could be used to classify strains within the spoligotype families, the HGDI of the 15 MIRU-VNTR was calculated for every spoligotype family. According to the global HGDI calculated from the 158 studied strains, 12 MIRU-VNTR loci were designated as "highly discriminant" (HGDI !0.6) which were, in order of decreasing discriminatory power, MIRU26, Qub11b, Mtub21, ETR-A, Qub26, Mtub39, MIRU40, MIRU10, Mtub30, Qub4156, ETR-E and MIRU16; while ETR-C, Mtub04 and ETR-D were designated as "moderately discriminant" (0.3 HGDI 0.6) (Table 1).

Within the Beijing family, the loci Qub11b and MIRU16 were highly discriminant for strain classification; the loci Mtub04, MIRU26 and ETR-A were moderately discriminant and the others were poorly discriminant (Table 1). Within the CAS family, only MIRU10 had high discriminatory power, while the loci Qub4156, MIRU16, MIRU40, ETR-C, Mtub39, Qub26 and Qub11b were moderately discriminant and the other loci were poorly discriminant. The loci Qub26, Mtub39 and Qub4156 were highly discriminant for the EAI family while other loci were poorly discriminant. Other highly discriminant loci include Qub11b, MIRU10, Qub4156, MIRU40 and Qub26 for the Haarlem family, Qub26, MIRU40, Qub11b and Mtub39 for the LAM family, and Mtub39, MIRU16, Qub11b and MIRU26 for the T family (Table 1).

MIRU-VNTR loci and specificities within MTBC spoligotype families

Reduced MIRU-VNTR loci number for subtyping MTBC spoligotype families

To identify a set of loci needed to achieve optimal discrimination, the loci that showed the highest individual discriminatory power were combined with spoligotyping. The MIRU-VNTR loci were added stepwise until the combination of loci showed an HGDI equal to the HGDI of the reference 15 loci MIRU-VNTR.

For the Beijing spoligotype family, the reduction to twelve MIRU-VNTR loci (Qub11b, MIRU16, Mtub04, MIRU26, ETR-A, ETR-C, Qub26, Mtub21, Qub4156, ETR E, MIRU10 and Mtub30) showed the same level of discrimination as the 15 loci reference (Table 2). For the EAI spoligotype family, the combination of nine MIRU-VNTR loci (Qub26, Mtub39, Qub4156, ETR-A, ETR-D, ETR-E, Qub11b, Mtub21 and MIRU40) showed the same discrimination level as the 15 loci MIRU-VNTR reference. In the CAS spoligotype family, the combination of ten loci (MIRU10, Qub4156, MIRU16, MIRU40, ETR-C, Mtub39, Qub26, Qub11b, ETR-E and Mtub04) were able to identify single genotype or cluster similar to those obtained with 15 loci reference. For the Haarlem family, four loci (Qub11b, MIRU10, Qub4156 and MIRU40) achieved the same discrimination level as the 15 loci reference (HGDI = 1). For the LAM family, a combination of 3 loci (Qub26, MIRU40 and Qub11b) achieved a similar discrimination level to the 15 loci reference (HGDI = 0.963) (Table 2). Using the above HGDI calculation method, no novel combinations of MIRU-VNTR loci were equivalent in discriminatory power to the 15 MIRU-VNTR for the T family (Fig 3).

Discussion

The main goal of this study was to evaluate the combination of spoligotyping with a reduced number of MIRU-VNTR loci that would have an equivalent discriminatory power as the 15 MIRU-VNTR typing method. This combination is expected to improve on the use of MIR-U-VNTR alone in which the selected loci were reported to be biased towards lineage 4 and can lack discriminatory power for other lineages [START_REF] Comas | Genotyping of genetically monomorphic bacteria: DNA sequencing in Mycobacterium tuberculosis highlights the limitations of current methodologies[END_REF]. This is the first study to use such a combination to describe the genetic diversity of Malagasy MTBC clinical isolates.

To confirm the MTBC lineages classification obtained by spoligotyping, the related profiles were compared to those obtained by the more robust SNP-typing to make sure that the spoligotyping profiles were not prone to homoplasy. Our results showed 99% concordance between spoligotyping and SNP-typing for the 158 MTBC strains studied. The spoligotyping could be used in the first line to identify the main sublineages of the studied strains. Then, for the lineages 1, 2 and 3, sets of MIRU-VNTR loci proposed by this study could be directly screened. However, for the lineage 4, which grouped three spoligotype families, the spoligotyping must be done before screening the set of MIRU-VNTR. This may improve the discrimination power of the combined methods against the initial biased selection of the used MIRU-VNTR loci toward this MTBC lineage 4. Spoligotyping can be more laborious when added to the customized set of 3 to 11 MIRU-VNTR lineage-depending loci proposed. However, the 15-MIR-U-VNTR method alone needs from 9 to 15 PCR runs without the automatized equipment in low-resource laboratory, as some loci can be screened in duplex PCR. Moreover, it has been suggested by this study and others that combining both methods can be much more discriminant in clusterizing clinical MTBC strains [START_REF] Streit | Finer characterization of Mycobacterium tuberculosis using spoligotyping and 15-loci MIRU-VNTRs reveals phylogeographical specificities of isolates circulating in Guyana and Suriname[END_REF][START_REF] Chaoui | Contribution of spoligotyping and MIRU-VNTRs to characterize prevalent Mycobacterium tuberculosis genotypes infecting tuberculosis patients in Morocco[END_REF]. Spoligotyping and MIRU-VNTR typing have their own database and identifying strains genotype using the combination with customized loci proposed here can be performed using softwares like the MIRUVNTR-plus used in present study where customized MIRU, with or without combination with Spoligotyping can be used to subtype the strains. The unique spoligotype profile that was discordant with SNP-typing could be indicative of a mixed infection; spoligotyping classified the strain as CAS (lineage 3) while SNP-typing classified it into lineage 2 and 3. Additional genotyping of this particular strain with MIR-U-VNTR typing gave a unique Beijing profile that suggested probable homoplasy generated by the spoligotyping, possibly due to convergent evolution. Similar discordances between spoligotyping and alternative genotyping methods was described by Fenner et al., particulary in the case of "Pseudo-Beijing" strains [START_REF] Fenner | Pseudo-Beijing": evidence for convergent evolution in the direct repeat region of Mycobacterium tuberculosis[END_REF].

As previously reported in the literature, a higher discrimination power was found for the 15 MIRU-VNTR typing compared to the spoligotyping alone [START_REF] Streit | Finer characterization of Mycobacterium tuberculosis using spoligotyping and 15-loci MIRU-VNTRs reveals phylogeographical specificities of isolates circulating in Guyana and Suriname[END_REF][START_REF] Chaoui | Contribution of spoligotyping and MIRU-VNTRs to characterize prevalent Mycobacterium tuberculosis genotypes infecting tuberculosis patients in Morocco[END_REF]. A 6.3% discordance was found between the spoligotyping and MIRU-VNTR typing alone; this observation is in agreement with other studies showing differences between spoligotyping and MIRU-VNTR typing in classifying MTBC strain. This discordance could possibly be explained by the clinical isolates representing mixed infections, that is, to say, an infection with two or more different genotypes. Multiple infections implying high reinfection rates and the absence of efficient immunity conferred to the host by the initial infection were indeed frequently reported [START_REF] Warren | Patients with active tuberculosis often have different strains in the same sputum specimen[END_REF]. This discordance might also be explained by convergent evolution of the spoligotypes, however, the SNP-typing obtained lineages did not differ from the spoligotyping ones and this SNP-spoligotyping had been selected to classify the strains due to the stability of the SNPs [START_REF] Maes | 24-locus MIRU-VNTR genotyping is a useful tool to study the molecular epidemiology of tuberculosis among Warao Amerindians in Venezuela[END_REF]. This is the first study to investigate a minimal set of MIRU-VNTR loci for Malagasy spoligotype families. Similar studies trying to define a minimal set of loci to classify MTBC strains suggested a fixed set of MIRU-VNTR loci (MIRU10, MIRU16, Mtub04, Mtub21, Mtub39, ETR-B, Qub11b and Qub26) in combination with spoligotyping for epidemiological study [START_REF] Zhang | A first assessment of the genetic diversity of Mycobacterium tuberculosis complex in Cambodia[END_REF]. While these loci were found to be highly discriminate in our Malagasy strains, combinations of varied MIRU-VNTR loci individualized to each spoligotype family and based on HGDI were found to be more discriminative than a fixed set of MIRU-VNTR loci. Another study conducted to genotype MTBC population in Ghana proposed the customized Ghanaian lineage-specific set of MIRU10, MIRU40, ETR-A, Qub11b, Qub26 and Qub4156 to subtyping the lineage 4 and 5 MTBC from this country [START_REF] Asante-Poku | Evaluation of customised lineage-specific sets of MIRU-VNTR loci for genotyping Mycobacterium tuberculosis complex isolates in Ghana[END_REF]. The loci described from the Ghanaian study were comprised of sets of loci for subtyping the Malagasy spoligotypes families. This study is also consistent with a PHRANA (progressively hierarchical resolving analysis using nucleic acid) scheme as described by P. Keim on the anthrax model [START_REF] Keim | Anthrax molecular epidemiology and forensics: using the appropriate marker for different evolutionary scales[END_REF]. The proposed combination of both methods can thus be used to improve the discriminatory power to classify MTBC populations in a wider range of MTBC population in different countries. Customized specific reduced number of MIRU-VNTR loci could be proposed to subtype spoligotype families without a loss in discrimination compared to the 15 loci MIRU-VNTR. The spoligotype specific MIRU-VNTR loci identified by PCA were found in the set of loci proposed based on HGDI method. A set of MIRU-VNTR loci identified by PCA can be typed and added to the other more discriminant loci proposed by the HGDI method.

The present study revealed that, due to the strong phylogeographic structure exhibited by MTBC, the most relevant MIRU-VNTR typing schemes will likely differ depending on the specific geographical setting. For example, in Northwest Russia, MIRU26 and ETR-A were proposed for the Beijing family while, in South Africa, MIRU10, MIRU26 and MIRU39 were proposed for the same family [START_REF] Mokrousov | Analysis of the allelic diversity of the mycobacterial interspersed repetitive units in Mycobacterium tuberculosis strains of the Beijing family: practical implications and evolutionary considerations[END_REF].

Due to the fact that the original selections of the 24 loci and the derived 15 loci widely used for MIRU-VNTR were biaised toward some main lineages, the MIRU-VNTR technique may be also biased depending on the most predominant strains in the country where the method is performed. Combining the spoligotyping and MIRU-VNTR typing can avoid such a bias as this combination can be performed independently from countries or regions from where the strains were isolated.

The studied strains were representing only the major spoligotype families circulating in Madagascar. The proposed customized combination has to be evaluated in multicentric studies in settings with different MTBC strain distributions to validate its resolution and ability to discriminate MTBC in different settings. Indeed, to assess the whole typeability and variability of loci, more samples by spoligotype family should have been taken in the present study. Twenty strains by major spoligotype family were randomly selected here without taking account Share-Type (ST); then the ability of these combination of loci proposed to distinguish strains of the same ST was not evaluated. Moreover, this study was limited to 15 MIRU-VNTR; while evaluating the 24 loci would have increased the chance of having more hypervariability. This customized combination of genotyping methods should be evaluated as a first-line panel for genotyping MTBC isolates in a particular setting. It is more cost effective than the full set of 15 loci for molecular epidemiological investigation of TB transmission in those resource-limited settings.

Conclusion

The use of combined spoligotyping and customized MIRU-VNTR loci proposed in this study to subtype MTBC isolated in Madagascar offered a similar discriminatory power as the 15-loci MIRU-VNTR typing used alone. The optimal combination of genetic markers proposed in this study achieved an acceptable level of resolution for classifying MTBC strains during tuberculosis transmission surveys. This test proves to be less laborious and resource demanding than MIRU-VNTR loci alone and would be particularly useful in low-resource settings.

  MIR-U-VNTR typing. Three strains classified by spoligotyping as T were classified as Haarlem (n = 2) and EAI (n = 1) by 15 MIRU-VNTR. Within the 158 strains, 15 MIRU-VNTR typing identified 142 different genotypes. Twentyseven isolates were grouped into 12 clusters containing 2 to 3 isolates each. Moreover, 132 isolates had a unique MIRU-VNTR profile. Spoligotyping alone identified 35 genotypes, 15 of which were unique, and 20 clusters that contained 2 to 31 strains each. 15 MIRU-VNTR typing combined with either spoligotyping or SNP-typing showed the same discrimination level as 15 MIRU-VNTR typing used alone (HGDI = 0.999). Thirty-one Beijing strains that clustered by spoligotyping were divided into 29 different MIR-U-VNTR genotypes. Of these, 27 MIRU-VNTR genotypes were unique and only 4 strains were grouped into two different clusters. Twenty-three strains belonging to EAI spoligotype family were divided into 22 MIRU-VNTR genotypes, 21 of them were unique and one cluster containing 2 strains. Twenty-three strains of the CAS spoligotype family was divided into 21 different MIRU-VNTR genotypes, 19 of which were unique and 4 formed two clusters each containing 2 strains. Eighteen strains of the Haarlem spoligotype family were distributed into unique MIR-U-VNTR genotypes. Seventeen strains with LAM spoligotype profiles were divided into 13 different MIRU-VNTR genotypes, 10 of which were unique and the remaining was grouped into three clusters containing 2 to 3 strains. Forty-six strains with T spoligotype profiles were separated into 34 unique MIRU-VNTR genotypes and four clusters containing 2 to 4 strains (S1 Fig).

  Principal component analysis (PCA) based on 15 MIRU-VNTR data from the studied clinical MTBC strains revealed three major clusters of MTBC strains. The individual plot distinguished the CAS and the EAI spoligotype family that formed two distinct groups while the Beijing, Harleem, LAM and T spoligotype families were grouped into a cloud (Fig 1). According to this PCA, the combination of MIRU10, MIRU16, MIRU40, Mtub04 and Qub4156 and the combination of ETR-A, ETR-D, ETR-E, Mtub21 and Mtub39 were associated to the CAS

Fig 1 .

 1 Fig 1. A two dimensional scatter plot based on principal component analysis (PCA) based on 15 MIRU-VNTR individual alleles. MTBC strains having similarity in MIRU-VNTR allelic tend to clusters together. https://doi.org/10.1371/journal.pone.0186088.g001

Fig 2 .

 2 Fig 2. A two dimensional scatter plot based on principal component analysis (PCA) based on 15 MIRU-VNTR individual alleles. MIRU-VNTR marker having similarity in MIRU-VNTR allelic tend to clusters together. https://doi.org/10.1371/journal.pone.0186088.g002

Fig 3 .

 3 Fig 3. Schematic overview of the typing scheme developed to differentiate MTBC clinical isolates studied. SNPs: Single Nucleotide Polymorphism. The blue arrow indicated that the discrimination level increased with the number of markers typed. https://doi.org/10.1371/journal.pone.0186088.g003

Table 1 . Global HGDI and HGDI of each locus for spoligotyping family.

 1

	LOCI	global HGDI	BEIJING	CAS	EAI	H	LAM	T
	MIRU26	0,7893	0,5312	0,1630	0,0833	0,2457	0,5882	0,6690
	Qub11b	0,7759	0,6817	0,3007	0,3116	0,7415	0,7132	0,6841
	Mtub21	0,7733	0,2430	0,2391	0,3080	0,2157	0,2279	0,4530
	ETR-A	0,7629	0,4000	0,1630	0,5942	0,1111	0,5956	0,5528
	Qub26	0,7533	0,2452	0,3696	0,7029	0,6928	0,7426	0,5459
	Mtub39	0,7362	0,0641	0,4312	0,6268	0,3137	0,6176	0,7340
	MIRU 40	0,6982	0,0645	0,4397	0,3007	0,6993	0,7206	0,5424
	MIRU10	0,6943	0,1849	0,7754	0,1594	0,7386	0,4853	0,4321
	Mtub30	0,6801	0,1269	0,1630	0,2355	0,5425	0,5809	0,2915
	Qub4156	0,6455	0,2409	0,5217	0,6051	0,7059	0,4191	0,3240
	ETR-E	0,6442	0,2123	0,3007	0,4203	0,1111	0,2206	0,2218
	MIRU16	0,6266	0,6172	0,5181	0,1630	0,3660	0,5809	0,7294
	ETR-C	0,5744	0,2796	0,4312	0,1630	0,2157	0,1117	0,5575
	Mtub04	0,5732	0,5333	0,2391	0,0000	0,4926	0,5809	0,3659
	ETR-D	0,372	0,0645	0,1594	0,5471	0,0000	0,1117	0,2449

HGDI 0.3: low discriminatory power. 0.3 HGDI 0.6: moderate discriminatory power. HGDI g 0.6: high discriminatory power. https://doi.org/10.1371/journal.pone.0186088.t001

Table 2 . Discrimination power of MIRU-VNTR genetic marker combination proposed. Spoligotype family Number of strains tested (n) MIRU-VNTR loci set (s) HGDI

 2

	Beijing	31	15 MIRU-VNTR	0.996
		Qub11b, MIRU16

, Mtub04,MIRU26, ETR-A, ETR-C,Qub26,Mtub21,Qub4156,ETR E,MIRU10, Mtub30 0.996

	EAI	23	15 MIRU-VNTR	0.996
			Qub26, Mtub39,Qub4156,ETR-A, ETR-D, ETR-E,Qub11b,Mtub21,MIRU40	0.996
	CAS	23	15 MIRU-VNTR	0.991
			MIRU10,Qub4156, MIRU16,MIRU40, ETR-C, Mtub39,Qub26,Qub11b,ETR-E,Mtub04	0.991
	Haarlem	19	15 MIRU-VNTR	1
			Qub11b, MIRU10, Qub4156,MIRU40	1
	LAM	17	15 MIRU-VNTR	0,963
			Qub26, MIRU40, Qub11b	0.963
	T	45	15 MIRU-VNTR	0.988
			Mtub39, MIRU16,Qub11b, MIRU26, ETR-C, ETR-A Qub26, MIRU40, Mtub21, MIRU10, Mtub04,	0.976
			Qub4156 and Mtub30

In bold, the set of MIRU-VNTR markers combination proposed by HGDI method for each spoligotype family. https://doi.org/10.1371/journal.pone.0186088.t002

PLOS ONE | https://doi.org/10.1371/journal.pone.0186088October 20, 2017

Acknowledgments

We would like to thank Jeremy Ratcliff from the Johns-Hopkins University for helpful inputs in the manuscript.

This work was supported by Institut Pasteur de Madagascar to Rondroarivelo Rasoahanitralisoa. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

All relevant data are within the paper and its Supporting Information files.

Supporting information

Validation: Niaina Rakotosamimanana.

Writing -original draft: Rondroarivelo Rasoahanitralisoa.

Writing -review & editing: Niaina Rakotosamimanana, Sebastien Gagneux, Voahangy Rasolofo Razanamparany.


Dariusz Biernacki

Sergueï Lenglet
email: serguei.lenglet@univ-lorraine.fr

Piotr Polesiuk
email: ppolesiuk@cs.uni.wroc.pl

Proving Soundness of Extensional Normal-Form Bisimilarities 1

Keywords: lambda calculus, normal-form bisimulations, eta-expansion, congruence, bisimulation up to context, control operators

Normal-form bisimilarity is a simple, easy-to-use behavioral equivalence that relates terms in λ-calculi by decomposing their normal forms into bisimilar subterms. Besides, they allow for powerful up-to techniques, such as bisimulation up to context, which simplify bisimulation proofs even further. However, proving soundness of these relations becomes complicated in the presence of η-expansion and usually relies on adhoc proof methods which depend on the language. In this paper, we propose a more systematic proof method to show that an extensional normal-form bisimilarity along with its corresponding bisimulation up to context are sound. We illustrate our technique with the call-by-value λ-calculus, before applying it to a call-by-value λ-calculus with the delimited-control operators shift and reset. In both cases, there was previously no sound bisimulation up to context validating the η-law. Our results have been formalized in the Coq proof assistant.

Introduction

In formal languages inspired by the λ-calculus, the behavioral equivalence of choice is usually formulated as a Morris-style contextual equivalence [START_REF] Morris | Lambda Calculus Models of Programming Languages[END_REF]: two terms are equivalent if they behave the same in any context. This criterion captures quite naturally the idea that replacing a term by an equivalent one in a bigger program should not affect the behavior of the whole program. However, the quantification over contexts makes contextual equivalence hard to use in practice to prove the equivalence of two given terms. Therefore, it is common to look for easier-to-use, sound alternatives that are at least included in contextual equivalence, such as coinductively defined bisimilarities.

Different styles of bisimilarities have been defined for the λ-calculus, including applicative bisimilarity [START_REF] Abramsky | Full abstraction in the lazy lambda calculus[END_REF], normal-form bisimilarity [START_REF] Lassen | Eager normal form bisimulation[END_REF] (originally called open bisimilarity in [START_REF] Sangiorgi | The lazy lambda calculus in a concurrency scenario[END_REF]), and environmental bisimilarity [START_REF] Sangiorgi | Environmental bisimulations for higher-order languages[END_REF]. Applicative and environmental bisimilarities compare terms by applying them to function arguments, while normal-form bisimilarity reduces terms to normal forms, which are then decomposed into bisimilar subterms. As we can see, applicative and environmental bisimilarities still rely on some form of quantification over arguments, which is not the case of normal-form bisimilarity. As a drawback, the latter is usually not complete w.r.t. contextual equivalence-there exist contextually equivalent terms that are not normal-form bisimilar-while the former are. Like environmental bisimilarity, normal-form bisimilarity usually allows for up-to techniques [START_REF] Pous | Enhancements of the bisimulation proof method[END_REF], relations which simplify equivalence proofs of terms by having less requirements than regular bisimilarities. For example, bisimulation up to context allows to forget about a common context: to equate C[t] and C[s], it is enough to relate t and s with a bisimulation up to context.

In the call-by-value λ-calculus, the simplest definition of normal-form bisimilarity compares values by equating a variable only with itself, and a λ-abstraction only with a λ-abstraction such that their bodies are bisimilar. Such a definition does not respect call-by-value η-expansion, since it distinguishes x from λy.x y. A less discriminating definition instead compares values by applying them to a fresh variable, thus relating λy.v y and v for any value v such that y is not free in v: given a fresh z, (λy.v y) z reduces to v z. Such a bisimilarity, that we call extensional bisimilarity, 6relates more contextually equivalent terms, but proving its soundness as well as proving the soundness of its up-to techniques is more difficult, and usually requires ad-hoc proof methods, as we detail in the related work section (Section 2).

In [START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF], Madiot et al. propose a framework where proving the soundness of upto techniques is quite uniform and simpler. It also allows to factorize proofs, since showing that bisimulation up to context is sound directly implies that the corresponding bisimilarity is a congruence, which is the main property needed for proving its soundness. In [START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF], the method is applied to environmental bisimilarities for the plain call-by-name λ-calculus and for a call-by-value λ-calculus with references, as well as to a bisimilarity for the π-calculus. In [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF], we extend this framework to define environmental bisimilarities for a call-by-value λ-calculus with multi-prompted delimited-control operators. We propose a distinction between strong and regular up-to techniques, where regular up-to techniques cannot be used in certain bisimilarity tests, while strong ones can always be used. This distinction allows to prove sound more powerful up-to techniques, by forbidding their use in cases where it would be unsound to apply them.

So far, the method developed in [START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF][START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF] have been used in the λ-calculus only for environmental bisimilarities. In this paper, we show that the framework of [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF] can also be used to prove the soundness of extensional normal-form bisimilarities and their corresponding bisimulation up to context. We first apply it to the plain call-byvalue λ-calculus, in which an extensional normal-form bisimilarity, albeit without a corresponding bisimulation up to context, have already been proved sound [START_REF] Lassen | Eager normal form bisimulation[END_REF], to show how our framework allows to prove soundness for both proof techniques at once. We then consider a call-by-value λ-calculus with the delimited-control operators shift and reset [START_REF] Danvy | Abstracting control[END_REF], for which there has been no sound bisimulation up to context validating the η-law either, and we show that our method applies seamlessly in that setting as well. Our results have been formalized in the Coq proof assistant, thus increasing the confidence in proofs that can be quite meticulous.

The paper is organized as follows: in Section 2, we discuss the previous proofs of soundness of extensional normal-form bisimilarities. In Section 3, we present the proof method for the call-by-value λ-calculus, that we then apply to a λ-calculus with shift and reset in Section 4. We conclude in Section 5, and the Coq developments are available at http://www.ii.uni.wroc.pl/ ~ppolesiuk/apnfbisim.

Related Work

Normal-form bisimilarity has been first introduced in [START_REF] Sangiorgi | The lazy lambda calculus in a concurrency scenario[END_REF], where it was named open bisimilarity, and has then been defined for many variants of the λ-calculus, considering η-expansion [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Eager normal form bisimulation[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF][START_REF] Støvring | A complete, co-inductive syntactic theory of sequential control and state[END_REF][START_REF] Lassen | Typed normal form bisimulation[END_REF][START_REF] Lassen | Typed normal form bisimulation for parametric polymorphism[END_REF][START_REF] Biernacki | Normal form bisimulations for delimited-control operators[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF] or not [START_REF] Lassen | Bisimulation for pure untyped λµ-caluclus[END_REF][START_REF] Lassen | Normal form simulation for McCarthy's amb[END_REF]. In this section we focus on the articles treating the η-law, and in particular on the congruence and soundness proofs presented therein.

In [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF], Lassen defines several equivalences for the call-by-name λ-calculus, depending on the chosen semantics. He defines head-normal-form (hnf ) bisimulation and hnf bisimulation up to η for the semantics based on reduction to head normal form (where η-expansion applies to any term t, not only to a value as in the call-byvalue λ-calculus), and weak-head-normal-form (whnf ) bisimulation based on reduction to weak head normal form. (It does not make sense to consider a whnf bisimulation up to η, since it would be unsound, e.g., it would relate a non-terminating term Ω with a normal form λx.Ω x.) The paper also defines a bisimulation up to context for each bisimilarity.

The congruence proofs for the three bisimilarities follow from the main lemma stating that if a relation is a bisimulation, then so is its substitutive and context closure. The lemma is proved by nested induction on the definition of the closure and on the number of steps in the evaluation of terms to normal forms. It can be easily strengthened to prove the soundness of a bisimulation up to context: if a relation is a bisimulation up to context, then its substitutive and context closure is a bisimulation. The nested induction proof method has been then applied to prove congruence for a whnf bisimilarity for the call-by-name λµ-calculus [START_REF] Lassen | Bisimulation for pure untyped λµ-caluclus[END_REF] (a calculus with continuations), an extensional hnf bisimilarity for the call-by-name λcalculus with pairs [START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF], and a whnf bisimilarity for a call-by-name λ-calculus with McCarthy's ambiguous choice (amb) operator [START_REF] Lassen | Normal form simulation for McCarthy's amb[END_REF]. These papers do not define any corresponding bisimulation up to context.

Lassen uses another proof technique in [START_REF] Lassen | Eager normal form bisimulation[END_REF], where he defines an eager normal form (enf ) bisimilarity and an enf bisimilarity up to η. 7 Lassen shows that the bisimilarities correspond to Böhm trees equivalence (up to η) after a continuation-passing style (CPS) translation, and then he deduces congruence of the enf bisimilarities from the congruence of the Böhm trees equivalence. A CPS-translation based technique has also been used in [START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF] to prove congruence of the extensional bisimilarity for the call-by-name λ-calculus (also with surjective pairing), the λµ-calculus, and the Λµ-calculus. Unlike the nested induction proof method, this technique does not extend to a soundness proof of a bisimulation up to context.

In [START_REF] Lassen | Eager normal form bisimulation[END_REF], Lassen claims that "It is also possible to prove congruence of enf bisimilarity and enf bisimilarity up to η directly like the congruence proofs for other normal form bisimilarities (tree equivalences) in [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF], although the congruence proofs (...) require non-trivial changes to the relational substitutive context closure operation in op.cit. (...) Moreover, from the direct congruence proofs, we can derive bisimulation up to context proof principles like those for other normal form bisimilarities in op.cit." To our knowledge, such a proof is not published anywhere; we tried to carry out the congruence proof by following this comment, but we do not know how to conclude in the case of enf bisimilarity up to η. We discuss what the problem is at the end of the proof of Lemma 3.11.

In [START_REF] Støvring | A complete, co-inductive syntactic theory of sequential control and state[END_REF], the authors define extensional enf bisimilarities for three calculi: λµ (continuations), λρ (mutable state), and λµρ (continuations and mutable state). The congruence proof is rather convoluted and is done in two stages: first, prove congruence of a non-extensional bisimilarity using the nested induction of [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF], then extend the result to the extensional bisimilarity by a syntactic translation that takes advantage of an infinite η-expansion combinator. The paper does not mention bisimulation up to context.

In [START_REF] Lassen | Typed normal form bisimulation[END_REF][START_REF] Lassen | Typed normal form bisimulation for parametric polymorphism[END_REF], the authors define a normal-form bisimilarity for a CPS calculus called JWA equipped with a rich type system (including product, sum, recursive types, and [START_REF] Lassen | Typed normal form bisimulation for parametric polymorphism[END_REF] adds existential types). The bisimilarity respects the η-law, and the congruence proof is done in terms of game semantics notions. Again, these papers do not mention bisimulation up to context.

In [START_REF] Biernacki | Normal form bisimulations for delimited-control operators[END_REF], we define extensional enf bisimilarities and bisimulations up to context for a call-by-value λ-calculus with delimited-control operators. The (unpublished) congruence and soundness proofs follow [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF], but are incorrect: one case in the induction, that turns out to be problematic, has been forgotten. In [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF] we fix the congruence proof of the extensional bisimilarity, by doing a nested induction on a different notion of closure than in [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF]. This approach fails when proving soundness of a bisimulation up to context, and therefore bisimulation up to context does not respect the η-law in [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF].

To summarize:

-The soundness proofs for extensional hnf bisimilarities are uniformly done using a nested induction proof method [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF]. The proof can then be turned into a soundness proof for bisimulation up to context.

-The soundness proofs of extensional enf bisimilarities either follow from a CPS translation [START_REF] Lassen | Eager normal form bisimulation[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF], or other ad-hoc arguments [START_REF] Støvring | A complete, co-inductive syntactic theory of sequential control and state[END_REF][START_REF] Lassen | Typed normal form bisimulation[END_REF][START_REF] Lassen | Typed normal form bisimulation for parametric polymorphism[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF] which do not carry over to a soundness proof for a bisimulation up to context.

-The only claims about congruence of an extensional enf bisimilarity as well as soundness of the corresponding bisimulation up to context using a nested induc-tion proof are either wrong [START_REF] Biernacki | Normal form bisimulations for delimited-control operators[END_REF] or are not substantiated by a presentation of the actual proof [START_REF] Lassen | Eager normal form bisimulation[END_REF]. The reason the nested induction proof works for extensional hnf bisimilarities and not for extensional enf bisimilarities stems from the difference in the requirements on the shape of λ-abstractions the two normal forms impose: whereas the body of a λ-abstraction in hnf is also a hnf, the body of a λ-abstraction in enf is an arbitrary term.

In this paper, we consider an extensional enf bisimilarity for two calculi: the plain λcalculus and its extension with delimited continuations, and in each case we present a soundness proof of the corresponding enf bisimulation up to context from which congruence of the bisimilarity follows.

3 Call-by-value λ-calculus

In this section we introduce a new approach to normal-form bisimulations that is based on the framework we developed in [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF]. The calculus of discourse is the plain call-by-value λ-calculus.

Syntax, semantics, and normal-form bisimulations

We let x, y, z range over variables. The syntax of terms (t, s), values (v, w), and call-by-value evaluation contexts (E) is given as follows:

t, s ::= v | t s v, w ::= x | λx.t E ::= | E t | v E
v x R w x x fresh v R v w E[x] R E [x] x fresh E R ctx E E R ctx E v R v w E[x v] R o E [x w]
We can now define (extensional) normal-form bisimulation and bisimilarity, using a notion of progress.

Definition 3.1 A relation R progresses to S if t R s implies:
• if t → t , then there exists s such that s → * s and t S s ;

• if t = v, then there exists w such that s ⇓ w, and v S v w;

• if t = E[x v], then there exist E , w such that s ⇓ E [x w] and E[x v] S o E [x w];
• the converse of the above conditions on s.

A bisimulation is then defined as a relation which progresses to itself, and bisimilarity-as the union of all bisimulations. Our definition is in a small-step style, unlike in [START_REF] Lassen | Eager normal form bisimulation[END_REF], as we believe small-step is more flexible, since we can recover a big-step reasoning with bisimulation up to reduction (Section 3.3). In usual definitions [START_REF] Lassen | Eager normal form bisimulation[END_REF][START_REF] Støvring | A complete, co-inductive syntactic theory of sequential control and state[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF], the β-reduction is directly performed when a λ-abstraction is applied to a fresh variable, whereas we construct an application in order to uniformly treat all kinds of values, and hence account for η-expansion. However, with this approach a naive definition of bisimulation up to context would be unsound because it would equate any two values: if v and w are related, then v x and w x are related up to context. In our framework, we prevent this issue as explained after Definition 3.2.

We now recast the definition of normal-form bisimilarity in the framework of [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF], which is itself an extension of a work by Madiot et al. [START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF][START_REF] Madiot | Higher-Order Languages: Dualities and Bisimulation Enhancements[END_REF]. The goal is to factorize the congruence proof of the bisimilarity with the soundness proofs of the up-to techniques. The novelty in [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF] is that we distinguish between active and passive clauses, and we forbid some up-to techniques to be applied in a passive clause. Whereas this distinction does not change the notions of bisimulation or bisimilarity, it has an impact on the bisimilarity congruence proof. Definition 3.2 A relation R diacritically progresses to S, T written R S, T , if R ⊆ S, S ⊆ T , and t R s implies:

• if t → t , then there exists s such that s → * s and t T s ;

• if t = v, then there exists w such that s ⇓ w, and v S v w;

• if t = E[x v], then there exist E , w such that s ⇓ E [x w] and E[x v] T o E [x w];
• the converse of the above conditions on s.

An normal-form bisimulation is a relation R such that R R, R, and normal-form bisimilarity ≈ is the union of all normal-form bisimulations.

The difference between Definitions 3.2 and 3.1 is only in the clause for values, where we progress towards a different relation than in the other clauses of Definition 3.2. We say that the clause for values is passive, while the others are active. A bisimulation R progresses towards R in passive and active clauses, so the two definitions generate the same bisimilarity. However, we prevent some up-to techniques from being applied in a passive clause. In particular, up to context is not allowed, as explained in Section 3.3, meaning that we cannot deduce that v x and w x are related up to context just because v and w are related. In contrast, we allow any up-to techniques when we test a value in the open stuck term case, since we cannot deduce from E[x v] related to E [x w] that v y and w y are related up to context.

R def = I ∪ {(λx.x, J)} ∪ {(t, s) | (λx.x) y → * t, J y → * s, y fresh} ∪ {(y z, t) | (λx.y (J x)) z → * t, y, z fresh}
is a bisimulation. Indeed, to compare λx.x and J, we have to relate (λx.x) y and J y, but J y → * λx.y (J x). We then have to equate y z and (λx.y (J x)) z, the latter evaluating to y λx.z (J x).

To relate these open stuck terms, we have to equate and (with I), and z with λx.z (J x), but these terms are already in R. As usual, the quite lengthy definition of R can be simplified with up-to techniques (see Example 3.13). 2

Up-to techniques, general definitions

We recall here the main definitions we use from [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF]. The goal of up-to techniques is to simplify bisimulation proofs: instead of proving that a relation R is a bisimulation, we show that R respects some looser constraints which still imply bisimilarity. In our setting, we distinguish the up-to techniques which can be used in passive clauses (called strong up-to techniques), from the ones which cannot. An up-to technique (resp. strong up-to technique) is a function

f such that R R, f (R) (resp. R f (R), f (R)) implies R ⊆ ≈.
Proving that a given f is an up-to technique is difficult with this definition, so following [START_REF] Pous | Enhancements of the bisimulation proof method[END_REF][START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF], we rely on a notion of compatibility instead, which gives sufficient conditions for f to be an up-to technique.

We first define some auxiliary notions and notations. We write f ⊆ g if f (R) ⊆ g(R) for all R. We define f ∪ g argument-wise, i.e., (f ∪ g)(R) = f (R) ∪ g(R), and given a set F of functions, we also write F for the function defined as f ∈F f . We define f ω as n∈N f n . We write id for the identity function on relations, and

f for f ∪ id. A function f is monotone if R ⊆ S implies f (R) ⊆ f (S). We write P f in (R)
for the set of finite subsets of R, and we say f is continuous if it can be defined by its image on these finite subsets, i.e., if f (R) ⊆ S∈P f in (R) f (S). The up-to techniques of the present paper are defined by inference rules with a finite number of premises, so they are trivially continuous. Continuous functions are interesting because of their properties:8 Lemma 3.4 If f and g are continuous, then f • g and f ∪ g are continuous.

If f is continuous, then f is monotone, and f • f ω ⊆ f ω . Definition 3.5 A function f evolves to g, h, written f g, h, if for all R R, T , we have f (R) g(R), h(T ). A function f strongly evolves to g, h, written f s g, h, if for all R S, T , we have f (R) g(S), h(T ).

Evolution can be seen as a notion of progress for functions on relations. Note that strong evolution does not put any condition on how R progresses, while regular evolution is more restricted, as it requires a relation R such that R R, T .

Definition 3.6 A set F of continuous functions is diacritically compatible if there exists S such that S ⊆ F and

• for all f ∈ S, we have f s S ω , F ω ;

• for all f ∈ F, we have f

S ω • F • S ω , F ω .
In words, a function is in a compatible set F if it evolves towards a combination of functions in F. The (possibly empty) subset S intuitively represents the strong up-to techniques of F. Any combination of functions can be used in an active clause. In a passive one, only strong functions can be used, except in the second case, where we progress from f (R), with f not strong. In that case, it is expected to progress towards a combination that includes f ; it is safe to do so, as long as f (or in fact, any non-strong function in F) is used at most once. If S 1 and S 2 are subsets of F which verify the conditions of the definition, then S 1 ∪ S 2 also does, so there exists the largest subset of F which satisfies the conditions, written strong(F). Lemma 3.7 Let F be a diacritically compatible set.

• If R strong(F) ω (R), F ω (R), then F ω (R) is a bisimulation. • If f ∈ F, then f is an up-to technique. If f ∈ strong(F), then f is a strong up-to technique.
• For all f ∈ F, we have f (≈) ⊆ ≈.

The proof takes advantage of Lemma 3.4. In practice, proving that f is in a compatible set F is easier than proving it is an up-to technique. Besides, if we prove that a bisimulation up to context is compatible, then we get for free that ≈ is a congruence thanks to the last property of Lemma 3.7.

Up-to techniques for normal-form bisimilarity

Figure 1 presents the up-to techniques we define for the λ-calculus. Combined altogether, they define a closure as in the nested induction proof method [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF]; we use a more fine-grained approach to distinguish between strong and regular up-to techniques. As in [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF], we use the substitutive closure subst. We also rely on the closure by evaluation contexts ectx, which is less common, but already used in [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF]. The closure ectx is not the same as bisimulation up to context, since we can factor out different contexts, as long as they are related when we plug a fresh variable inside them. The technique red, used in the compatibility proofs, is the classic bisimulation up to reduction, which allows terms to reduce before being related.

Theorem 3.8 The set F def = {refl, app, lam, subst, ectx, id, red} is diacritically compatible, with strong(F) = {refl, lam, subst, id, red}.

t refl(R) t t R t s R s t s app(R) t s t R s λx.t lam(R) λx.s t R s v R v w t{v/x} subst(R) s{w/x} t R s E R ctx E E[t] ectx(R) E [s] t → * t s → * s t R s t red(R) s
Fig. 1: Up-to techniques for the λ-calculus

The complete proof of Theorem 3.8 can be found in the Coq formalization. We sketch some of the compatibility proofs to show how proofs are done in our framework, in particular the crucial case of app, where we need the distinction between active and passive tests. We compare ourselves to the proof technique of [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF], which would do an induction on the definition of the closure using Definition 3.1. We do not need an induction on the number of evaluation steps for our small-step definition, but a nested induction proof for a big-step relation would exhibit the same issues. The strong up-to techniques lam, refl, and red are easy to deal with; we detail the proof for lam. We now sketch the proof for subst. The proof method is by case analysis on the related terms, similar to what one would do in the proof by induction of [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF].

Lemma 3.10 subst s subst, (id ∪ ectx) • subst •(id ∪ subst). Proof (Sketch) Let R S,
• subst •(id ∪ subst)(T ).
If v is a variable, a similar reasoning shows that t{v/x} and s {w/x} evaluate to open stuck terms, whose contexts are related by ectx • subst •(id ∪ subst)(T ) and whose arguments are related by subst(subst(T )).

2

The proof for subst does not require the clause for values to be passive, and is thus similar to the corresponding case of an induction proof [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF]. In contrast, we need testing values to be passive when dealing with app and ectx; we present the problematic subcase in the proof below. We do not know how to make this subcase go through in a proof as in [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF].

Lemma 3.11 app app, app ∪ subst ∪ ectx ∪ (id ∪ ectx) • subst •(id ∪ subst).
Proof (Sketch) Let R R, S, and t 1 s 1 app(R) t 2 s 2 such that t 1 R t 2 and s 1 R s 2 . We proceed by case analysis on t 1 and s 1 . Most cases are straightforward; the problematic case is when t 1 is a variable x and s 1 a value w 1 . Because t 1 R t 2 and s 1 R s 2 , there exists v 2 and w 2 such that

t 2 ⇓ v 2 , s 2 ⇓ w 2 , x R v v 2 , and w 1 R v w 2 . From x R v v 2 ,
we have x y R v 2 y for a fresh y, and therefore x w 1 subst(R) v 2 w 2 . We can conclude using Lemma 3.10: there exists an open stuck term s such that

t 2 s 2 → * v 2 s 2 → * v 2 w 2 → * s and x v 2 ((id ∪ ectx) • subst •(id ∪ subst)(S)) o s .
In an induction proof with Definition 3.1, we would have in that case x y S v 2 y and w 1 S v w 2 instead of R. We do not see how to go further in the case w 1 is a λ-abstraction λx.t: we have to prove that t{w 2 /x} evaluates to an open stuck term, but we do not have any progress hypothesis about S.

2

The technique ectx exhibits a similar problematic subcase, when E = v and t = x. We obtain the following corollary that follows from Theorem 3.8 (refl, lam and app are compatible) and Lemma 3.7 (the third item). Corollary 3.12 ≈ is a congruence. This corollary, in turn, immediately implies the soundness of ≈ w.r.t. the usual contextual equivalence of the λ-calculus, where we observe termination of evaluation [START_REF] Abramsky | Full abstraction in the lazy lambda calculus[END_REF]. However, as proved in [START_REF] Lassen | Eager normal form bisimulation[END_REF], ≈ is not complete w.r.t. contextual equivalence. showing that R def = {(v, w), (v x, w x), ((λy.v x) z, (λy.w (J x)) z) | x, z fresh} ∪ R is a bisimulation up to ectx, refl, and red. Indeed, we have vx → * (λzxy.zx)vx → * λy.vx and w x → * (λzxy.z (J x)) w x → * λy.w (J x). To relate the two resulting values, we compare (λy.v x) z and (λy.w (J x)) z for a fresh z. These terms reduce to respectively v x and w (J x), which are in ectx(R ), because v y R w y for a fresh y and x R J x. Without ectx, we would have to reduce these terms further and continue the bisimulation game. Note that we use ectx after a reduction step, i.e., in an active clause. We also have (λy.v x) z red(ectx(R)) (λy.w (J x)) z, but we cannot conclude with this, as we would use ectx in the passive clause for values. 2

Delimited-control operators

In this section we turn to the call-by-value λ-calculus extended with shift and reset [START_REF] Danvy | Abstracting control[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF]. We show that the results of Section 3 seamlessly carry over to this calculus, thus demonstrating the robustness of the approach, but also improving on the previous results on extensional normal-form bisimulations for this calculus [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF].

Syntax, semantics, and normal-form bisimulations

We extend the grammar of terms and values given in Section 3 as follows:

t, s ::= . . . | t v, w ::= . . . | S where • is the control delimiter reset and S is the delimited-control operator shift. Usually, shift is presented as a binder Sx.t [START_REF] Danvy | Abstracting control[END_REF][START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF] or as a special form S t [START_REF] Filinski | Representing monads[END_REF], but here we choose a more liberal syntax treating shift as a value (as, e.g., in [START_REF] Kameyama | Axioms for control operators in the CPS hierarchy[END_REF]). This makes the calculus a little more interesting since shift becomes a subject to η-expansion just as any other value, and moreover it makes it possible to study terms such as S S. We call pure terms effect-free terms, i.e., values and terms of the form t . We distinguish a subclass of pure contexts (E) among evaluation contexts (F ):

E ::= | v E | E t F ::= | v F | F t | F
We extend the function fv to both kinds of contexts. Note that an evaluation context F is either pure or can be written F [ E ] for some F and E . Pure contexts can be captured by S, as we can see in the following rules defining the call-by-value left-to-right reduction semantics of the calculus:

F [(λx.t) v] → F [t{v/x}] F [ E[S v] ] → F [ v λx. E[x] ] with x ∈ fv(E) F [ v ] → F [v]
The first rule is the usual call-by-value β-reduction. When S is applied to a value v, it captures its surrounding pure context E up to the dynamically nearest enclosing reset, and provides its term representation λx. E[x] as an argument to v. Finally, a reset which encloses a value can be removed, since the delimited subcomputation is finished. All these reductions may occur within a metalevel context F that encodes the chosen call-by-value evaluation strategy. As in Section 3, the reduction relation → is preserved by evaluation contexts.

Example 4.1 This example illustrates the operational behavior of S as a value:

E[S S] → S λx. E[x] → (λx. E[x] ) (λx. x ) → E[λx. x ]
In particular, if E = , then the value of the initial term is λx. x , i.e., the representation of the empty context. 2

A term t either uniquely reduces to another term, or is an eager normal form: it is either a value v, an open stuck term F [x v], or a control-stuck term E[S v]. The latter cannot reduce further since it lacks a reset enclosing S. Because shift can decompose contexts, we have to change the relation R ctx as discussed in [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF]:

E[x] R E [x]
x fresh

E R ctx E E[x] R E [x] F [x] R F [x]
x fresh

F [ E ] R ctx F [ E ]
We also introduce a relation R c to handle control-stuck terms:

E R ctx E v x R w x x fresh E[S v] R c E [S w]
whereas the relation R v remains unchanged, so that it accounts for the η-law, even though the values now include S.

We can now define (extensional) normal-form bisimulation and bisimilarity for the extended calculus, again using the notion of diacritical progress. Definition 4.2 A relation R diacritically progresses to S, T written R S, T , if R ⊆ S, S ⊆ T , and t R s implies:

• if t → t , then there exists s such that s → * s and t T s ;

• if t = v, then there exists w such that s ⇓ w, and v S v w;

• if t = F [x v], then there exist F , w such that s ⇓ F [x w] and F [x v] T o F [x w]; • if t = E[S v], then there exist E , w such that s ⇓ E [S w] and E[S v] T c E [S w];
• the converse of the above conditions on s.

A normal-form bisimulation is a relation R such that R R, R, and normal-form bisimilarity ≈ is the union of all normal-form bisimulations.

Note that only the clause for values is passive, as in Definition 3.2.

Example 4.3 The terms S S and S (λk.k (λx.x)) are bisimilar since the following relation is a normal-form bisimulation:

I ∪ { (S S, S (λk.k (λx.x))), (1)
( S z , (λk.k (λx.x)) z ), ( 2
) ( z (λx. x ) , z (λx.x) ), (3)
((λx. x ) y, (λx.x) y), (4)
( y , y) }

where I is the identity relation and x, y, and z fresh variables. In (1) we compare two control-stuck terms, so to validate the bisimulation conditions, we have to compare the two empty contexts (which are in I ctx ) and the arguments of shift. Here,

t R s E R ctx E E[t] pctx(R) E [s] t R s E R ctx E E[t] pctxrst(R) E [s] t R s t, s pure F [x] R F [x] x fresh F [t] ectxpure(R) F [s]
Fig. 2: Up-to techniques specific to the λ-calculus extended with shift and reset extensionality plays an important role, as these arguments are of different kinds (S vs a λ-abstraction). We compare them by passing them a fresh variable z, thus we include the pair (2) in the bisimulation. The terms of (2) can be reduced to those in (3), where we compare open stuck terms, so we have to include (4) to compare the arguments of z. The terms in (4) can then be reduced to the ones in ( 5) which in turn reduce to identical terms. 2

Up-to techniques

The up-to techniques we consider for this calculus are the same as in Figure 1, except we replace ectx by three more fine-grained up-to techniques defined in Figure 2.

The techniques pctx, pctxrst allow to factor out related pure contexts and pure contexts with a surrounding reset. The third one (ectxpure) can be used only with pure terms, but uses a naive comparison between any evaluation contexts instead of • ctx . Indeed, a pure term cannot evaluate to a control-stuck term, so decomposing contexts with • ctx is not necessary. The usual bisimulation up to evaluation context ectx can be obtained by composing these three up-to techniques.

Lemma 4.4 If t R t and F R ctx F then F [t] (pctx ∪ (ectxpure • pctxrst))(R) F [t ].
Note that we do not define extra up-to techniques corresponding to the new constructs of the language: shift is dealt with like variables-using refl, and congruence w.r.t. reset can be deduced from pctxrst by taking the empty context. Defining a dedicated up-to technique for reset would have some merit since it could be proved strong. It is not so for pctxrst, as we can see in the next theorem:

Theorem 4.5 The set F def = {refl, app, lam, subst, pctx, pctxrst, ectxpure, id, red} is diacritically compatible, with strong(F) = {refl, lam, subst, id, red}.

The evolution proofs are as in the pure λ-calculus, by case analysis on the possible reductions that the related terms can do. The techniques app, pctx, pctxrst, and ectxpure are not strong as they exhibit the same problematic case presented in Lemma 3.11 (for app, pctx, and ectxpure) or a slight variant ( E = v and t = x for pctxrst). As in Section 3, from Theorem 4.5 and Lemma 3.7 it follows that ≈ is a congruence, and, therefore, is sound w.r.t. the contextual equivalence of [START_REF] Biernacki | Bisimulations for delimited-control operators[END_REF]; it is not complete as showed in op. cit. 2) is in red(f (R)), and for (1), we have also to relate with , thus (1) is in refl(R) ∪ red(f (R)). As a result, R is a bisimulation up to red, refl, pctxrst, and lam. 2

Conclusion

In this article we present a new approach to proving soundness of normal-form bisimilarities as well as of bisimulations up to context that allow for η-expansion.

The method we develop is based on our framework [START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF] that generalizes the work of Madiot et al. [START_REF] Madiot | Bisimulations up-to: Beyond first-order transition systems[END_REF][START_REF] Madiot | Higher-Order Languages: Dualities and Bisimulation Enhancements[END_REF] in that it allows for a special treatment of some of the clauses in the definition of bisimulation. In particular, we show soundness of an extensional bisimilarity for the call-by-value λ-calculus and of the corresponding bisimulation up to context, where it is critical that comparing values in a way that respects η-expansion is done passively, i.e., by requiring progress of a relation to itself. Following the same route, we obtained similar results for the extension of the call-by-value λ-calculus with delimited control, where the set of normal forms is richer, and we believe this provides an evidence for the robustness of the method.

To the best of our knowledge, there has been no soundness proof of extensional normal-form bisimulation up to context for any of the two calculi before.

The proof method we propose should trivially apply to the existing non-extensional whnf bisimilarities [START_REF] Lassen | Bisimulation for pure untyped λµ-caluclus[END_REF][START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Normal form simulation for McCarthy's amb[END_REF] and extensional hnf bisimilarities [START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF][START_REF] Lassen | Head normal form bisimulation for pairs and the λµ-calculus[END_REF] for the λ-calculus and its variants. Since whnf bisimilarities do not take into account ηexpansion, their testing of values would be active and all their up-to techniques would be strong, so actually Madiot's original framework is sufficient to account for them. In the case of extensional hnf bisimilarities, normal forms are generated by the grammar: h ::= λx.h | n n ::= x | n t and in order to account for η-expansion a λ-abstraction λx.h is related to a normal form n, provided h is related to n x, a freshly created normal form. Thus, in extensional enf bisimulations the relation on normal forms provides enough information to make testing of normal forms active just like in whnf bisimulations. A future work that seems a worthwhile task would be to tackle the complete enf bisimilarity for the λµρ-calculus of sequential control and state [START_REF] Støvring | A complete, co-inductive syntactic theory of sequential control and state[END_REF]. It would be interesting to investigate whether our method can be adapted to the 'relation-set' structure of bisimulations that capture the behavior of mutable references.

Example 3 . 3

 33 Let θ def = λzx.x λy.z z x y and fix(v) def = λx.θ θ v x for a given v; note that fix(v) x → * v fix(v) x. Wadsworth's infinite η-expansion combinator [3] can be defined as J def = fix(λf xy.x (f y)). Let I def = {(t, t) | t any term} be the identity bisimulation. We prove that λx.x ≈ J, by showing that

Lemma 3 . 9

 39 lam s lam ∪ red, lam ∪ red. Proof. Let R S, T ; we want to prove that lam(R) lam(S) ∪ red(S), lam(T ) ∪ red(T ). The inclusions lam(R) ⊆ lam(S) ∪ red(S) and lam(S) ∪ red(S) ⊆ lam(T ) ∪ red(T ) hold because R ⊆ S, S ⊆ T (by definition of ) and the functions are monotone. Next, let λx.t lam(R) λx.s such that t R s. The only clause to check is the one for values: we have (λx.t) x → t and (λx.s) x → s, i.e., (λx.t) x red(R) (λx.s)x, which implies (λx.t)x red(S) (λx.s)x because R ⊆ S and red is monotone.2

Example 3 . 13

 313 We can simplify the definition of R in Example 3.3 to just R def = {(λx.x, J), (y, λx.y (J x)) | y fresh} and show that R is a bisimulation up to refl and red. To illustrate how bisimulation up to context can help, we define v def = fix(λzxy.z x) and w def = fix(λzxy.z (J x)) and prove that these values are bisimilar by

Example 4 . 6

 46 With these up-to techniques, we can simplify the bisimulation of Example 4.3 to just a single pair R def = {(S S, S (λk.k (λx.x)))}. Indeed, we have λx. x lam(red(refl(R))) λx.x, and z refl(R) ctx z , so (3) is in f (R), where f def = pctxrst •(refl ∪ (lam • red • refl)). Then, (

  Normal-form bisimilarity relates terms by comparing their normal forms (if they exist). For values, a first possibility is to relate separately variables and λ-abstractions: a variable x can be equated only to x, and λx.t is bisimilar to λx.s if t is bisimilar to s. As explained in the introduction, this does not respect η-expansion: the η-respecting definition compares values by applying to a fresh variable. Given a relation R on terms, we reflect how values and open stuck terms are tested by the relations R v , R ctx , and R o , defined as follows:

An abstraction λx.t binds x in t; a variable that is not bound is called free. The set of free variables in a term t is written fv(t). We work modulo α-conversion of bound variables, and a variable is called fresh if it does not occur in the terms under consideration. Contexts are represented outside-in, and we write E[t] for plugging a term in a context. We write t{v/x} for the capture-avoiding substitution of v for x in t. We write successive λ-abstractions λx.λy.t as λxy.t.

We consider a call-by-value reduction semantics for the language

E[(λx.t) v] → E[t{v/x}]

We write → * for the reflexive and transitive closure of →, and t ⇓ s if t → * s and s cannot reduce; we say that t evaluates to s. Eager normal forms are either values or open stuck terms of the form E[x v].

  We check the different clauses by case analysis on t. If t is a value, then there exists a value s such that s ⇓ s and t R v s . But then t{v/x} and s {w/x} are also values, and then we can prove that t{v/x} subst(S) v s {w/x} holds. If t → t , then there exists s such that s → * s and t T s . Then t{v/x} → t {v/x}, s{w/x} → * s {w/x}, and t {v/x} subst(T ) s {w/x}. Finally, if t = E[y v ], then there exists s such that s ⇓ s and t T o s . If y = x, then t{v/x} and s {w/x} are open stuck terms in subst(T ) o . Otherwise, we distinguish cases based on whether v is a λ-abstraction or not. In the former case, let v = λz.t , s = E [x w ]. Then t{v/x} = E{v/x}[v v {v/x}] → E{v/x}[t {v {v/x}/z}]. From v R v w and v z → t , we know that there exists s such that w z → * s and t T s . Consequently, we have s{w/x} → * s {w/x} = E {w/x}[w w {w/x}] → * E {w/x}[s {w {w/x}/z}]. Then E{v/x}[x ] subst(T ) E{w/x}[x ] for a fresh x , but also t {v {v/x}/z} subst(subst(T )) s {w {w/x}/z}, so after plugging, we obtain terms in ectx

T , and t{v/x} subst(R) s{w/x} such that t R s and v R v w.

Lassen uses the term bisimilarity up to η[START_REF] Lassen | Bisimulation in untyped lambda calculus: Böhm trees and bisimulation up to context[END_REF] for a normal-form bisimilarity that validates the η-law, but we prefer the term extensional bisimilarity so that there is no confusion with notions referring to up-to techniques such as bisimulation up to context.

While weak head normal forms are normal forms under call-by-name evaluation, eager normal forms are normal forms under call-by-value evaluation of λ-terms.

Our formalization revealed an error in previous works[START_REF] Aristizábal | Environmental bisimulations for delimitedcontrol operators with dynamic prompt generation[END_REF][START_REF] Madiot | Higher-Order Languages: Dualities and Bisimulation Enhancements[END_REF] which use f instead of f in the last property of Lemma 3.4 (expressing idempotence of f ω )-id has to be factored in for the property to hold.

Acknowledgement

We thank the anonymous reviewers for their helpful comments on the presentation of this work.

 [START_REF] Abramsky | Full abstraction in the lazy lambda calculus[END_REF]This work was partially supported by PHC Polonium and National Science Centre, Poland, grant no. 2014/15/B/ST6/00619.