Mireille Fares

Catherine Pelachaud

Nicolas Obin

TRANSTYLER: MULTIMODAL BEHAVIORAL STYLE TRANSFER FOR FACIAL AND BODY GESTURES GENERATION

This paper addresses the challenge of transferring the behavior expressivity style of a virtual agent to another one while preserving behaviors shape as they carry communicative meaning. Behavior expressivity style is viewed here as the qualitative properties of behaviors. We propose TranSTYLer, a multimodal transformer-based model that synthesizes the multimodal behaviors of a source speaker with the style of a target speaker. We assume that behavior expressivity style is encoded across various modalities of communication, including text, speech, body gestures, and facial expressions. The model employs a style-content disentanglement schema to ensure that the transferred style does not interfere with the meaning conveyed by the source's behaviors. Our approach eliminates the need for style labels and allows the generalization to styles that have not been seen during the training phase. We train our model on the PATS corpus, which we extended to include dialog acts and 2D facial landmarks. Objective and subjective evaluations show that our model outperforms state-ofthe-art models in style transfer for both seen and unseen styles during training. To tackle the issues of style and content leakage that may arise, we propose a methodology to assess the degree to which behavior and gestures associated with the target style are successfully transferred, while ensuring the preservation of the ones related to the source content.

Introduction

Human communication is a complex phenomenon that involves various modes of expression beyond speech production. It is inherently multimodal, as it relies on the interplay of verbal and non-verbal signals to convey semantic and pragmatic content and facilitate the communication process [Knapp et al.(2013), Argyle(2013), [START_REF] Feyereisen | [END_REF], [START_REF][END_REF]]. Human behavior expressivity style refers to the unique and characteristic pattern of behavior exhibited by an individual in various social and communicative contexts [Knapp et al.(2013)]. It is not a fixed attribute of the speaker but rather is constantly adjusted, accomplished, and co-created with the audience [Mendoza-Denton(1999)]. It involves the way an individual communicates verbally and non-verbally, including verbal skills, body language, gestures, and self-expression. Variability in speakers' gesturing is influenced by ) and Mel spectrogram (X source speech ) -and conditioned on a target speaker's style vector h style generated from the target's multimodal input data -Mel spectrogram (X target speech ), 2D facial landmarks (X target f ace ), 2D poses (X target pose ), and dialog tags (X target tags ). The network is composed of: (1) a style encoder that encodes the target's multimodal data and generates the style vector h style , (2) a content encoder that encodes the source's speech content and generates the content vector h content , and (3) a discriminator Dis used during training time to disentangle h content and h style . A generator G is used to generate body Z pose and facial Z f ace gestures. factors such as their personality traits [McCrae and Costa Jr(1997)], verbal skills [START_REF] Hostetter | [END_REF]], age [Alibali et al.(2009), [START_REF] Feyereisen | [END_REF]], and culture [Kita(2009)]. The topic and context of the conversation, speaker's role, and relationship with the interlocutor also play a role [Hostetter and Potthoff(2012)]. For example, extroverts tend to use larger spatial gestures [Hostetter and Potthoff(2012)]. Behavior expressivity style can vary between formal and spontaneous speech. In formal settings, a controlled and structured speaking style is used, with formal language and restrained gestures to convey professionalism and respect. In contrast, in spontaneous speech, individuals adopt a more relaxed communication style with informal gestures. In this paper, we propose a novel machine learning approach to synthesize facial and upper-body gestures driven by prosodic features and text in the style of different speakers including those unseen during training. We view behavior expressivity style as a pervasive factor during speech, influencing the expressiveness of communicative behaviors, while speech content is conveyed through a combination of multimodal behaviors and text. We propose TranSTYLer a transformer-based model that can synthesize facial and body gestures of a source speaker in the style of any target speaker, while ensuring that the transferred style does not interfere with the meaning conveyed by the source gestures. Our approach incorporates a disentanglement scheme that separates content and style, enabling us to directly infer the style representation even for speakers who were not part of the training process, without requiring additional training or fine-tuning. Our system comprises two main components. Firstly, we have a speaker style encoder network, which learns to generate a fixed-dimensional embedding that represents the style of a target speaker. This embedding is derived from the target speaker's multimodal data (facial and body gestures, audio, and text). Secondly, we employ a synthesis network that synthesizes gestures based on the content provided by the input modalities (text and audio) of a source speaker. This synthesis process is conditioned on the target speaker style embedding, ensuring that the generated gestures exhibit the target style characteristics. We also introduce a new methodology to measure the transferred style and the preservation of gestures that convey meaning. We evaluate the performance of TranSTYLer in terms of style transfer and content preservation. Objective and subjective evaluations confirm the quality of our approach, outperforming two state-ofthe-art models.This paper is organized as follows. We start by providing a review of the existing behavior expressivity style modeling approaches, discussing their limitations. We then explain our contributions and the architecture we propose. Finally, we present objective and subjective evaluations and discuss the results.

Related Works

Gesture style modeling and control have gained significance in proposing expressive behaviors for virtual agents that can be adjusted and tailored to specific audiences or interlocutors. A first model to generate communicative behaviors with different styles was proposed by Neff et al.[Neff et al.(2008)]. The authors developed a system that generates full body gesture animation based on text, mimicking the style of a specific performer. They focused mainly on hand movements. In recent years, [START_REF][END_REF]] proposed a generative model that synthesizes speech-driven gesticulation while exerting control over the output style, such as gesture level and speed. Karras et al. [Karras et al.(2017)] created a model that generates 3D facial animation from audio to capture the style of a single actor. Similarly, [START_REF] Cudeiro | [END_REF]] developed a model, called VOCA, that synthesizes 3D facial animation driven by speech signal, allowing for a wide range of speaking styles to be realistically animated, even in languages other than English. On the other hand, Ginosar et al. [Ginosar et al.(2019a)] proposed an approach for generating gestures using models trained on individual speakers. Yoon et al [START_REF] Yoon | [END_REF]] developed a method to generate gestures that matched a speaker's style by using their speaker identity. Their approach involved processing the input audio and text with separate audio and text encoders and using the speaker identity to select a style embedding from a learned space. These features were then fed to a gesture generator to produce a sequence of poses that matched the content and rhythm of the speech. On the other hand, Ghorbani et al. [Ghorbani et al.(2022a), Ghorbani et al.(2022b)] proposed a framework that improved on high-level style portrayal by using exemplar motion sequences to demonstrate the intended stylistic expression of gesture motion. Their method could extract style parameters in a zero-shot manner, only requiring a single example motion and was able to generalize to example motions (and therefore styles) not seen during training. The works just mentioned have focused on generating behaviors from one modality, either facial expressions, head movements or gestures. However, they have not considered multimodal data when modeling style or synthesizing gestures. Additionally, their generative models were only trained on single-speaker data. Recently, Ahuja et al. [START_REF] Ahuja | [END_REF]] have attempted to model and transfer style from a multi-speaker database. They proposed Mix-StAGE, a speech-driven approach that trains a model using data from multiple speakers while learning a unique style embedding for each speaker. Their neural architecture uses a content and style encoder to extract content and style information from pose. A style embedding matrix is used to represent the style associated with each specific speaker in the training set. Their approach presents several limitations. First, behavior expressivity style is only encoded by means of upper-body motion, ignoring the other possible modes of style expression, such as text, speech, and facial expresions. Second, speakers are associated with a unique speaker identity "ID", considered as style labels, which hinder their ability to generalize to new speakers. Later on, Ahuja et al. [START_REF] Ahuja | [END_REF]] presented a few-shot style transfer strategy based on neural domain adaptation to transfer style with only a few examples, considering the shift in cross-modal grounding between the source speaker and the target style. However, this approach still requires to have at least 2 minutes of the style to be transferred. Fares et. al [START_REF] Fares | [END_REF], [START_REF] Fares | [END_REF]] proposed an approach to synthesize upper body gestures of a source speaker in the style of any target speaker. The authors do not consider faces in their model. Their approach can be applied to speakers whose style behaviors have been learned or not during the training phase. Overall, the recent models proposed to capture behavior expressivity style have several limitations: they do not exploit multimodal data [Ye et al.(2022), Neff et al.(2008), Alexanderson et al.(2020), Karras et al.(2017), [START_REF] Cudeiro | [END_REF], Ginosar et al.(2019a), [START_REF] Ginosar | [END_REF], [START_REF] Fares | [END_REF]]; their generative models are trained on single speaker data; style is associated with speaker "IDs", which limits their ability to generalize to new speakers without additional training [START_REF] Cudeiro | [END_REF], Karras et al.(2017), Ginosar et al.(2019a)]; they require additional training to model unseen target speaker style [START_REF] Ahuja | [END_REF]]. In addition, they lack a methodology to evaluate properly the behavior expressivity style transfer. In particular, during the style transfer from a target style to a source content, the resulting behavior should ideally preserve the gesture related to the source content (e.g., idiomatic gestures) while modifying its expression accordingly to the target style. Practically, it is a common pitfall in style transfer to observe leakage between the source content and the target style, i.e. partially preserving the source style or transferring the target content.

Our contributions

To address the limitations, we introduce TranSTYLer a transformer-based model for the generating facial and body gestures of a source speaker in the style of a target speaker, while preserving the intended meaning of the source gestures. Our contributions are: 1. To the best of our knowledge, TranSTYLer is the first behavior expressivity style transfer approach that jointly synthesizes 2D upper-body gestures and 2D facial landmarks of source speakers, in the style of any target speakers, and without requiring additional training, making our approach zero-shot.

2. We propose a novel methodology for assessing behavior expressivity style transfer for generating communicative behaviors for virtual agents. Our methodology measures content preservation and style transfer and gives insights about potential leakages between style and content information. 3. We have extended the PATS corpus, by including 2D Facial Landmarks and Dialog Tags.

TranSTYler

We present TranSTYler, a novel approach for modelling behavior expressivity style in virtual agents.TranSTYler is a multimodal style transfer approach for generating 2D facial and pose synthesis corresponding to the content of a source speaker and in the style of a target speaker. During inference, an embedding style vector can be directly inferred from any target speaker's multimodal data -text, speech, poses, 2D facial landmarks -by simple projection into TranSTYler's embedding style space (similar to the one used in [Jia et al.(2018)] and [START_REF] Fares | [END_REF]]). Our approach allows for style transfer from any unseen speakers, without requiring further training or fine-tuning of our trained model. This means that our method is not restricted to the styles of the speakers in the training dataset.

TranSTYler is trained on PATS corpus [START_REF] Ahuja | [END_REF]] which we extended to include additional facial and text features.

Problem Positioning

The goal is to learn to generate facial and upper-body gestures based on the source speaker's content information and conditioned on the style information of the target speaker. A transformer-based generator is used to generate facial and body gestures from content and style information. An adversarial component in the form of a fader network [START_REF] Lample | [END_REF]] is used for disentangling style and content from the multimodal data. At inference time, it is discarded, and the model can generate different versions of facial and body gestures when fed with different style vectors. Gesture styles for the same input speech can be directly controlled by switching the value of style vector or by calculating it from a target speaker's multimodal data fed as input to the style encoder. Our approach is based on the following hypotheses:

• Our primary hypothesis is that behavior involves the modulation of communicative gestures associated with content, through the specific gestures associated with an individual. We propose to disentangle this information and encode it in a differentiated manner.

• Behavior expressivity style is encoded across text semantics, dialog tags, speech, face and pose and varies little or not over time. The reason we consider dialog tags is to capture further semantic information. Moreover, studies on communicative gestures have shown the link between the meaning carried by dialog acts and the one carried by gestures ([Calbris(2011), Cienki(2005)]). • Speech content is encoded across the verbal and nonverbal modalities. That is, the meaning of what is being said is conveyed by the text and by the nonverbal communicative behaviors.

To implement theses assumptions, we propose an architecture for encoding and disentangling the source speaker's content and the target speaker's style information from multiple modalities. Style and content information are entangled in each utterance produced by a speaker. On one side, a content encoder E content is used to encode a content matrix from the source's text and speech signal; on the other hand, a style encoder E style is used to encode a style vector from the text, acoustic features, dialog tags, facial and body gestures data of the target. A fader loss ( [START_REF] Lample | [END_REF]]) is introduced to effectively disentangle content and style encodings. The network processes source and target input data at the segment level, where each segment S consists of 64 frames. For each segment S, the network takes as input:

1. The source speaker's audio and text semantics represented by the Mel spectrogram (X source speech ) and Bert embeddings (X source text ). 2. The target speaker's facial gestures, body gestures, audio, text and dialog tags represented by 2D facial landmarks (X target f ace ), 2D poses (X target body ), Mel spectrogram (X target speech ), Bert embeddings (X target text ), and dialog tags (X target tags ).

For each S, the output of the network is the generation of behaviors that correspond to the content of the source speaker with the style of the target speaker, namely:

1. Facial gestures ( Z f ace ) represented by 2D facial landmarks.

2. The corresponding upper-body gestures represented by 2D poses ( Z body ).

Neural Formulation

The . A self-attention mechanism is then applied on the resulting vector. The multi-head attention layer has N h equals to 4 attention heads, and an embedding size d att equals to d att = d model + 768. The output of the attention layer is the vector h content , a content representation of the source speaker's speech, which can be written as follows:

h content = sa E content speech (X source speech ), X source text
(1) where: sa(.) denotes self-attention.

Style Encoder. We consider that behavior expressivity style is encoded in a speaker's multimodal behavior. As illustrated in Figure 1 The input features are encoded using a one-hot encoding scheme. The output is a sparse array containing binary values representing the presence or the absence of each tag in the segment S. X target speech is encoded by E style speech , which is the pre-trained AST. The output vector is concatenated with X text and a self attention mechanism is applied on the resulting vector. This attention layer has N h equals to 4 attention heads and an embedding size equals to d att . Finally, the output vector is concatenated with the other encoded modalities. The resulting vector h style is the output speaker style embedding that serves to condition the network with the speaker style. The final style embedding h style can therefore be written as follows:

h style = sa X target text , E style speech (X target speech ) , E style pose (X target pose ), E style f ace (X target f ace ), E style tags (X target tags ) (2)
where: sa(.) denotes self-attention.

Generator. For decoding Z pose , and Z face , the sequence h content and the vector h style are concatenated (by repeating the h style vector for each segment of the sequence), and passed through a Dense layer of size d model . We then give the resulting vector as input to two Transformer Decoders. Each Transformer Decoder is composed of N dec = 1 decoding layer, with N h = 2 attention heads, and an embedding size equal to d model . The resulting output vectors are sequences of 2D facial landmarks and 2D-poses which corresponds to:

Z pose = G pose (h content , h style ) Z f ace = G f ace (h content , h style ) (3)
where G f ace and G pose are the transformer decoders corresponding to face and pose modalities. The generator loss can therefore be written as:

L gen rec (E content , E style , G) = E Zpose ||Z pose -G pose (h content , h style )|| 2 +E Z f ace ||Z f ace -G f ace (h content , h style )|| 2 (4)
Adversarial Component. Our approach of disentangling style from content relies on the fader network disentangling approach ( [START_REF] Lample | [END_REF]]), where a fader loss is introduced to effectively separate h style and h content . The latent space of h content is constrained to be independent of h style embeddings. Concretely, it means that the distribution over h content of the latent representations should not contain the style information. We formulate this discriminator Dis as a regression on the conditional variable h style . Dis learns to predict h style from h content , as:

h style = Dis(h content ) (5)
While optimizing the discriminator, the discriminator loss L dis must be as low as possible, such as:

L dis (Dis) = E h style ||h style -Dis(h content )|| 2 (6)
In turn, while optimizing the generator loss including the fader loss L gen adv , the discriminator must not be able to predict correctly h style from h content conducting to a high discriminator error and thus a low fader loss. The adversarial loss can be written as:

L gen adv (E content , E style ) = E h style ||1 -(h style -Dis(h content ))|| 2 (7)
The style prediction error is preliminary normalized within 0 and 1 range. The total G loss can therefore be written as follows:

L gen total (E content , E style , G) = L gen rec (E content , E style , G)+ λL gen adv (E content , E style , G) (8)
where λ is the adversarial weight that starts off at 0 and is linearly incremented by 0.01 after each training step.

The discriminator Dis and the generator G are then optimized alternatively as described in [START_REF] Lample | [END_REF]].

All TranSTYler hyperparameters were chosen empirically and are listed in the implementation details section of the appendix.

5 Experimental Evaluations It has 251 hours of data, with 84, 000 intervals and a mean duration equal to 10.7 seconds per interval. The standard deviation is 13.5 seconds per interval. An interval corresponds to an utterance consisting of 64 timesteps. We have extended PATS to include 2D facial landmarks,and dialog tags, More specifically, we extracted 70 2D facial landmarks for all PATS speakers using OpenPose [START_REF] Cao | [END_REF]] and aligned with PATS's features. Dialog acts correspond to the communicative functions expressed by the spoken text [START_REF] Bunt | [END_REF]]. We used the tool "DialogTag" [bha ([n. d.])] to extract 38 dialog tags from PATS utterances. We refer the readers to the supplementary materials for the complete list of dialog tags.

TranSTYler Training and Testing. We trained our network using PATS 2.0. Although fingers are included in PATS, we have chosen not to model finger data in our work. The quality of the extracted fingers data is very noisy and lacks accuracy. Instead, we focus on modeling and predicting the 2D joints of the upper body and arms, using 11 joints to represent these areas. We also model 15 facial landmarks, which are illustrated in our Appendix. We use less keypoints than those originally extracted to have less input parameters and fasten the training phase. We took out some keypoints from the face contour and 2 keypoints on each eyebrow, and we used only 2 keypoints for the eyelids. In total, we model 11 body and arm joints, and 15 facial landmarks. An utterance is associated to one or more dialog acts. We consider all the 38 different tags that are listed in our appendix. Our testing comprises two conditions: Seen Speaker and Unseen Speaker. The Seen Speaker condition evaluates how accurately our model can perform style transfer when presented with target speakers seen during training. In contrast, the Unseen Speaker condition evaluates our model's ability to perform zero-shot style transfer when presented with target speakers that were not seen during training. We carefully selected both seen and unseen speakers from PATS to cover a range of stylistic behaviors in terms of lexical diversity and spatial extent which is the amplitude of body movements. The PATS database already defines the train, validation, and test sets for each speaker. We train our model on 16 PATS speakers. To test the Seen Speaker condition, we use the test sets of the 16 PATS speakers as our test set. For the Unseen Speaker condition, we select 6 other speakers and use their test sets for our experiments. Each training batch has BS = 24 pairs of word embeddings, Mel spectrogram, dialog acts, and their corresponding sequence of (x, y) joints of the skeleton of the upper-body pose and 2D facial landmarks. We use Adam optimizer with β 1 = 0.95, β 2 = 0.999, and a Cyclical Learning Rate (CLR) scheduler to render the learning balanced. The initial learning rate Lr init of the CLR is equal to 1e -7, the end learning rate Lr e is equal to 0.1, and the step size St size is equal to 196. We train the network for N it equals to 78, 400 iterations. All features values are normalized so that the dataset mean and standard deviation are 0 and 0.5, respectively. All hyperparameters used for training are summarized in our appendix.

Objective Evaluation

We objectively measure the performance of TranSTYler in terms of two key aspects: style transfer accuracy and content preservation.Moreover, to measure the degree of similarity of the generated facial and body gestures with the source and target styles, we computed the distance between our model's predictions and each of the source and target styles. Additionally, we assess and compare the unique dynamic movement patterns of the source, target, and prediction by measuring their velocity, acceleration, and jerk. This allows us to quantify and analyze the specific characteristics of their movement dynamics.

Metrics. We have followed the recommendations put forth by Fu et al. [Fu et al.(2018)] in order to evaluate the characteristics of style transfer in our study. We employed their proposed evaluation metrics, Transfer Strength Accuracy and Content Preservation, to assess the performance of TranSTYler. These metrics measure quantitatively the accuracy of style transfer and the extent to which content is preserved during the process.

Transfer Strength Accuracy. Transfer Strength is a metric that assesses the degree with which the style is transferred.

As proposed by Fu et al. [Fu et al.(2018)], this metric is implemented using a classifier C. We consider that behavior expressivity style is defined as follows:

Behavior expressivity style = Source (positive) output ≤ 0.5 Target (negative) output > 0.5 (9)

Transfer Strength Accuracy is defined as follows:

Transfer Strength Accuracy = N right N total × 100 (10)
where N right is the number of correct cases which are transferred from target to source style, and N total is the number of test set data. We developed C as a neural network consisting of three LSTM layers and a dense output layer, with the complete architecture shown in the appendix. The network's hyperparameters were chosen empirically and are also listed in the appendix. To train C, we used the train sets of the speakers included in the train sets of both the Seen and U nseen conditions, as defined in the PATS Corpus. Specifically, we trained C using a batch size of 256 and Adam optimizer, and a Binary Cross Entropy loss over 15, 000 epochs. After training, C achieved an accuracy of 96%.

Content Preservation. Content Preservation is a metric that reflects the preservation of source content, that is, in this work, the meaning conveyed by the nonverbal communicative behaviors, in predictions. It is defined as the cosine distance between predictions Z gestures and initial source gestures (X source ), as follows:

Cosine Distance = 1 - X ⊺ source • Z gestures ∥X source ∥∥ Z gestures ∥ (11)
Minkowski distance. We also measure the Minkowski distance between the upper-body gestures and facial expressions produced by our model, and the ones of the source and target speakers. We additionally experimented with alternative distance metrics, including cityblock, Chi2 distance, Euclidean distance, and cosine distance. However, we found that all these metrics yielded identical results, leading us to retain only the Minkowski distance. More specifically, for both conditions, Seen and Unseen, we define two sets of distances: (1) Dist.(TranSTYler, Source) which is the average distance between TranSTYler's predictions and the source's 2D facial landmarks and body joint; and (2) Dist.(TranSTYler, Target) which is the average distance between TranSTYler's predictions and the target data.

Velocity, Acceleration, Jerk. We evaluate the velocity, acceleration, and jerk of the source, target, and prediction to quantify and compare their distinct dynamic movement patterns. This analysis enables us to determine whether the prediction aligns more closely with the behavior expressivity style of the source or of the target. Velocity provides insights into the overall speed and rhythm of the movement, while acceleration measures the rate of change in motion velocity. Jerk indicates the smoothness of motion transitions over time. By examining these metrics, we can gain valuable information about the characteristics of the movement dynamics and utilize it to assess the degree to which the predicted animation captures the behavior expressivity style of the source or target.

Human Perceptual Studies

Following previous research [START_REF] Ahuja | [END_REF], [START_REF] Ahuja | [END_REF]], we contribute to the definition of a comprehensive methodology to assess behavior expressivity style transfer. We focus on differentiating between behaviors associated with the linguistic content of speech (i.e communicative gestures), and the unique style exhibited by a speaker. The desired outcome is to preserve the gestures form associated with the source content while adjusting their expressivity to match the target style. The proposed methodology is defined as follows:

• To assess behavioral expressivity style transfer, we evaluate the resemblance of our model's predictions to the target style. • To assess content preservation, we study the coherence of gestures by assessing their coordination with speech content and the synchronization with speech rhythm.

We conduct three studies and compare the perception of stimuli generated by our model and by the two baselines Mix-Stage and DiffGAN.

Study 1. The first study aims to assess the behavior expressivity style produced by our model w.r.t the behavior expressivity style of the seen or unseen target speakers. We additionally compare our model to Mix-Stage [START_REF] Ahuja | [END_REF]], which we consider our first baseline. We present 75 stimuli of 2D stick animation (like the 2D sticks in Fig. 2) to evaluate our model's predictions with seen target styles (condition 1, 30 stimuli), our model's predictions with unseen target styles (condition 2, 30 stimuli), and the baseline Mix-StAGE (condition 3, 15 stimuli). Each stimulus consists of a triplet of 2D animations composed of: (1) a 2D animation of the source speaker, (2) a 2D animation of the target speaker, and (3) a 2D animation of TranSTYler's prediction after performing the behavioral style transfer. Participants rate on a 5-point Likert scale the overall resemblance, resemblance of the left and right arms gesturing, body orientation, head orientation, gesture amplitude, gesture frequency, and gesture velocity of the target style animation with respect to the source style animation and our predictions' animation. The rating scale ranges from 1 (reference is very similar to A) to 5 (reference is very similar to B).

Study 2. We conduct a second study to investigate the coherence of the generated facial and body gestures. Previous research has focused on evaluating the appropriateness of generated gestures [START_REF] Kucherenko | [END_REF]]. In this work, we place greater emphasis on evaluating the coherence of gestures by assessing their coordination with speech content and synchronization with speech rhythm. By doing so, we aim to subjectively evaluate the extent to which content is preserved after performing behavioral style transfer. We evaluate the coherence of facial and body gestures in relation to speech content and rhythm. We present 90 stimuli of 2D stick animations, comprising 30 stimuli of TranSTYler's stylized predictions (condition 1), 30 stimuli of TranSTYler's predictions where we change the original audio with the audio from other speakers (condition 2), and 30 stimuli of the source style ground truth (condition 3). Condition 2 is included as an error and control condition. On a 5-point Likert scale, participants rate the synchronization of gestures with speech rhythm, the overall coherence of behavior, the coordination of the agent's gestures with speech content, and the human-likeness of the animations.

Study 3. A third study is conducted to compare the similarity of our model's predictions to the target style, as well as to those generated by our second baseline, DiffGAN [START_REF] Ahuja | [END_REF]]. We present 15 stimuli, each comprising a triplet of 2D animations corresponding to the same source-target behavioral style transfer. The first animation is generated by TranSTYler (condition 1). The second animation represents the reference, and it is target speakers' ground truth. The third animation is generated by DiffGAN (condition 2). For each stimulus, we ask participants to identify which video between condition 1 and condition 2 has the same behavior expressivity style as the reference video based on the arm gesture's extent, frequency, timing, and position of the body in relation to speech. We recruited 150 participants through the online crowd-sourcing website Prolific for our evaluation studies. Participants were selected based on their fluency in English. Attention checks were included at the beginning and middle of each study to filter out inattentive participants. Prior to each study, participants received training to introduce them to the 2D facial landmarks and upper-body skeleton and to familiarize them with 2D stick animations. 6 Results and Discussion

Objective Evaluation

Objective evaluation results are presented in Table 1 for both Seen and Unseen conditions. In the Seen condition, TranSTYler achieves a style transfer strength accuracy of 93.282%, indicating a high level of accuracy in transferring the style from the target speakers to the source speakers. For the Unseen condition, the accuracy is still high at 85.195%, although slightly lower than the accuracy for the Seen condition. This was expected since TranSTYler had not seen the target speakers during training. Nonetheless, the model demonstrated the ability to generalize the style to new, unseen speakers. In both the Seen and Unseen conditions, our model is able to preserve a high percentage of the source speakers' content, with 95.842% and 90.723% content preservation, respectively. The distance between our model's predictions and the source speakers' gestures -Dist.(TranSTYler, Source) -is higher than the one between our model's predictions and the target speakers' gestures -Dist.(TranSTYler, Target). These results confirm that the behavior expressivity style is successfully transferred from target to source speakers for both conditions. These results are further illustrated in Figures 3 and4 that illustrate the facial and body motion of a same source speaker (Ellen) as well as different target speakers that were either seen or unseen during training, alongside TranSTYler's predictions after performing style transfer. Figure 2 illustrates the motion of a source speaker Oliver, a target (seen) speaker Conan, and that of TranSTYler's predictions at the frame level. The source speaker Oliver gestures mainly with his right hand while Conan makes ample arm movements as shown toward the end of his sentence. The predicted animation displays the communicative gestures of Oliver (similar vertical movement of the arm) and the amplitude extent of Conan toward the end of the sentence. To explore the relationships and patterns between the content and style vectors generated by our model, a 2D T-SNE analysis was conducted. This analysis projects the vectors onto a two-dimensional space, where their proximity indicated similarity. The TSNE plots in Figure 5 showcase the content embeddings (h content ) and style embeddings (h style ) after disentangling the style-content information. By examining the distribution of features in the content and style space, it was observed that content and style were effectively separated. The style space exhibited clustering of features belonging to the same speaker, suggesting discernible patterns. However, in the content space, features from all speakers were mixed together without clear patterns or clusters. These results demonstrate the success of our disentangling approach in effectively separating style-content information. We additionally computed the velocity, acceleration, and jerk of TranSTYler's predictions, source style, and target style for source-target style transfers where the target is either Seen or Unseen. The results for style transfers performed on four source-target pairs, with two Seen targets (Angelica and Lec_hist) and two Unseen targets (Almaram and Minhaj) indicate that, for both Seen and Unseen targets, TranSTYler's velocity is closer to the target than to the source. Regarding the acceleration metric, we observed similar results for all style transfers except for the transfer from source Bee to the unseen target Minhaj, where the predictions' acceleration is closer to the source style. However, for the same Bee -Minhaj style transfer, our predictions' jerkness is closer to the target than the source style. For the style transfer Lec_law -angelica, TranSTYler produces a velocity that is close to the target style and far from the source style, an acceleration that is in between the source and target style, and a jerkness closer to the source style. Overall, these findings show that TranSTYler effectively transfers the behavior expressivity style from the target to the source speakers, as evidenced by the high style transfer accuracy, content preservation, and the observed patterns in velocity, acceleration, and jerk metrics.

Subjective Evaluation

Figure 6 (a) shows the mean scores obtained for all factors for all conditions (Mix-StAGE, Seen and Unseen); the higher the mean score, the closer the condition is w.r.t the target style. For all factors, our model obtained the mean scores higher than those of the baseline. For all factors, Mix-StAGE received lower scores than the Seen condition and higher scores than the Unseen condition. This may be due to the fact that speakers are visible during training in the Mix-StAGE condition, whereas TranSTYler is unseen in the Unseen condition. We conducted post-hoc paired t-tests for each factor between the three conditions and found significant differences (p < 0.007) between Mix-StAGE and Seen, and Unseen and Seen for all factors. We found significant results for Mix-StAGE and Unseen for all factors except 'body orientation'. Our prediction model in both Seen and Unseen conditions outperforms the baseline for all factors. The Seen condition also surpasses the Unseen one. Our prediction model in both Seen and Unseen conditions outperforms the baseline for all factors. The Seen condition also surpasses the Unseen one. The goal of Study 2 is to assess the preservation of the speech content during the style transfer. It evaluates the coherence of gestures by examining their coordination with speech content and synchronization with speech rhythm. Results of Study 2 are presented in Figure 6(b). We conducted paired t-tests for each factor between the following conditions: TranSTYler and Error, TranSTYler and Ground Truth, and Ground Truth and Error. The results showed significant differences (p < 0.001) between each pair of conditions for all factors. TranSTYler achieved scores that are significantly (p < 0.001) very similar to the ground truth scores. In contrast, the control condition, error, obtained a significantly (p < 0.001) lower mean score than the scores obtained by our model. Thus the gestures computed by our model maintained adequacy with the speech content as predicted gestures are highly similar to those in the original video. However, we are aware that further study ought to be conducted on measuring more precisely the semantic and pragmatic information conveyed by the predicted behaviors. The third study aimed to compare our model, TranSTYler, with a second baseline, DiffGAN [START_REF] Ahuja | [END_REF]], and results are shown in Figure 6 (c). Participants were asked to identify which animation, between condition 1 (TranSTYler) and condition 2 (DiffGAN), had the most similar behavior expressivity style as the reference video (target style) based on the arm gesture's extent, frequency, timing, and position of the body in relation to speech. A post-hoc binomial test was also conducted, and significant results were found for both conditions (p < 0.001). Thus, overall, our model generates animations that significantly capture better the behavior expressivity style of the target speaker than does DiffGAN.

Conclusion

We present TranSTYLer for synthesizing body and facial gestures of source speakers in the style of target speakers, without additional training. We propose a novel methodology for evaluating behavior expressivity style transfer, measuring content preservation and style transfer while identifying potential leakages between style and content information. Furthermore, we expand the PATS corpus by including 2D Facial Landmarks and Dialog Tags.

Figure 1 :

 1 Figure 1: Overview of TranSTYler, an approach driven by the content of a source speaker's speech -text semantics (X source text

5. 1

 1 Material and Model setups PATS 2.0 Corpus. The PATS Corpus[START_REF] Ahuja | [END_REF],Ginosar et al.(2019a)] originally includes 2D upper-body joints keypoints, aligned with the given speech, Mel spectrogram and Bert embeddings, of 25 speakers, categorized as follows: 15 talk show hosts, 5 lecturers, 3 YouTubers, and 2 televangelists. Each speaker has his/her own communicative style, and lexical and gesture diversity.

Figure 2 :

 2 Figure 2: Behavioral expressivity style transfer from target speaker Oliver to source speaker Conan. Fingers are not generated by our model but extracted from OpenPose. They are displayed for sake of visualisation.

Figure 3 :

 3 Figure 3: Visualization of facial motion of source, seen or unseen target and TranSTYLer's predictions.

Figure 4 :

 4 Figure 4: Visualization of upper-body motion of source, seen or unseen target and TranSTYLer's predictions.

Figure 5 :

 5 Figure 5: Left: T-SNE visualization of the style embeddings on the test sets of 5 speakers. Right: T-SNE visualization of the content embeddings on the same test sets.

Figure 6 :

 6 Figure6: Results of perceptual human study 1 (a), study 2 (b), and study 3 (c). Significant differences between pairs of all conditions for the same factor are marked with ( * ). If there are significant results between only two pairs of conditions for the same factor, ( * ) is used.

  network has an embedding size d model equals to 64.Content Encoder. E content encodes the source speaker's speech content information from the variables X source

	and X source speech corresponding to each S. X source text	text is represented by BERT embeddings of dimension 768. X source speech is
	encoded using E content speech , a pre-trained Mel Spectrogram Transformer (AST) base384 model ([Gong et al.(2021)]), and then concatenated with X source text

  , E style encodes the behavior expressivity style information from the target speaker's variables X target speech , X target text , X target pose , X target f ace , and X target tags ; which are encoded by E style speech , E style text , E style pose , E style f ace , and E style tags respectively. E style pose and E style f ace are composed of N lay equals to 3 layers of LSTMs with a hidden-size equal to d model . E style tags is a One Hot Encoder that considers the 38 dialog tags as categorical features.

Table 1 :

 1 Objective evaluation results: transfer strength accuracy, content preservation, and minkowski distances for Seen and Unseen conditions.

	Condition	Transfer Strength Accuracy (%)	Content Preservation (%)	Dist. w.r.t. Source	Dist. w.r.t. Target
	Seen	93.282	95.842	83.189	75.882
	Unseen	85.195	90.723	80.284	73.934


Petar Vukmirović
email: petar.vukmirovic2@gmail.com

Jasmin Blanchette
email: j.c.blanchette@vu.nl

Stephan Schulz
email: stephan.schulz@dhbw-stuttgart.de

Extending a High-Performance Prover to Higher-Order Logic

Most users of proof assistants want more proof automation. Some proof assistants discharge goals by translating them to first-order logic and invoking an efficient prover on them, but much is lost in translation. Instead, we propose to extend first-order provers with native support for higher-order features. Building on our extension of E to λ-free higher-order logic, we extend E to full higher-order logic. The result is the strongest prover on benchmarks exported from a proof assistant.

Introduction

In the last few decades, proof assistants have become indispensable tools for developing trustworthy formal proofs. They are used both in academia to verify mathematical theories [START_REF] Hales | A formal proof of the Kepler conjecture[END_REF] and in industry to verify the correctness of hardware [START_REF] Kern | Formal verification in hardware design: A survey[END_REF] and software [START_REF] Gu | CertiKOS: An extensible architecture for building certified concurrent OS kernels[END_REF][START_REF] Klein | seL4: Formal verification of an operating-system kernel[END_REF][START_REF] Leroy | Formal verification of a realistic compiler[END_REF]. However, due to the lack of strong built-in proof automation, proving seemingly simple goals can be a tedious manual task. To mitigate this, many proof assistants include a subsystem such as CoqHammer, HOL(y)Hammer, or Sledgehammer [START_REF] Blanchette | Hammering towards QED[END_REF] that translates higher-order goals to first-order logic and passes them to efficient first-order automatic provers. If a first-order prover succeeds, the proof is reconstructed and the goal is closed.

Unfortunately, the translation of higher-order constructs is clumsy and leads to poor performance on goals that require higher-order reasoning. Using native higher-order provers such as Satallax [START_REF] Brown | Satallax: An automatic higher-order prover[END_REF] as backends is not always a good solution because they are much less efficient than their first-order counterparts [START_REF] Sultana | LEO-II and Satallax on the Sledgehammer test bench[END_REF]. To bridge this gap, in 2016 we proposed to develop a new generation of higherorder provers that extend the arguably most successful first-order calculus, superposition, to higher-order logic, starting from a position of strength.

Our research has focused on three milestones: supporting λ-free higher-order logic, adding λ-terms, and adding first-class Boolean terms. In 2019, we extended the state-of-the-art first-order prover E [START_REF] Schulz | Faster, higher, stronger: E 2.3[END_REF] with a λ-free superposition calculus [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF], obtaining a version of E called Ehoh, as a stepping stone towards full higher-order logic. Together with Bentkamp, Tourret, and Waldmann, we have since developed calculi, called λ-superposition, corresponding to the other two milestones [START_REF] Bentkamp | Superposition for full higher-order logic[END_REF][START_REF] Bentkamp | Superposition with lambdas[END_REF] and implemented them in the experimental superposition prover Zipperposition [START_REF] Cruanes | Extending Superposition with Integer Arithmetic, Structural Induction, and Beyond[END_REF]. This OCaml prover is not nearly as efficient as E. Nevertheless, it has won the higher-order division of the CASC prover competition [START_REF] Sutcliffe | The 10th IJCAR automated theorem proving system competition-CASC-J10[END_REF] in 2020, 2021, and 2022, ending nearly a decade of Satallax domination.

We now fulfill a four-year-old promise: We present the extension of Ehoh to full higher-order logic (Sect. 2) based on incomplete variants of λ-superposition. We call this prover λE. In λE's implementation, we used the extensive experience with Zipperposition to choose a set of effective rules that could easily be retrofitted into an originally first-order prover. Another guiding principle was gracefulness: Our changes should not impact the strong first-order performance of E and Ehoh.

One of the main challenges we faced was retrofitting λ-terms in Ehoh's term representation (Sect. 3). Furthermore, Ehoh's inference engine assumes that inferences compute a most general unifier. We implemented a higher-order unification procedure [START_REF] Vukmirović | Efficient full higher-order unification[END_REF] that can return multiple unifiers (Sect. 4) and integrated it in the inference engine. Finally, we extended and adapted the superposition rule, resulting in an incomplete, pragmatic variant of λ-superposition (Sect. 5).

We evaluated λE on a selection of proof assistants benchmarks as well as all higher-order theorems in the TPTP library [START_REF] Sutcliffe | The TPTP problem library and associated infrastructure-from CNF to TH0, TPTP v6.4.0[END_REF] (Sect. 6). λE outperformed all other higher-order provers on the proof assistant benchmarks; on the TPTP benchmarks, it ended up second only to the cooperative version of Zipperposition, which employs Ehoh as a backend. An arguably fairer comparison without the backend puts λE in first place for both benchmark suites. We also compared the performance of λE with E on first-order problems and found that no overhead has been introduced by the extension to higher-order logic.

λE is part of the E prover's development repository and will be part of E 3.0. It can be enabled by passing the option --enable-ho to the configure script. E and λE's source code is freely available online. 1

Logic

Our target logic is monomorphic classical higher-order logic with Hilbert choice.

The following text is partly based on Vukmirović et al. [START_REF] Vukmirović | Making higher-order superposition work[END_REF]Sect. 2].

Terms s, t, u, v are inductively defined as free variables F, X, . . ., bound variables x, y, z, . . . , constants f, g, a, b, . . . , applications s t, and λ-abstractions λx. s. Bound variables may be loose (e.g., y in λx. y a) [START_REF] Nipkow | Functional unification of higher-order patterns[END_REF].

We let s t n stand for s t 1 . . . t n and λx n . s for λx 1 . . . . λx n . s. Every β-normal term can be written as λx m . s t n , where s is not an application; we call s the head of the term. If s is a free variable, we call the term flex ; otherwise, the term is rigid. A term of type o, where o is the distinguished Boolean type, is called a formula. A term whose type is of the form

τ 1 → • • • → τ n → o is called a predicate.
Logical symbols are part of the signature and may thus occur within terms. We write them in bold:

⊥ ⊥ ⊥, ⊤ ⊤ ⊤, ¬ ¬ ¬, ∧ ∧ ∧, ∨ ∨ ∨, → → →, ↔ ↔ ↔, ∀ ∀ ∀, ∃ ∃ ∃, ≈ ≈ ≈.
On top of the terms, we define some clausal structure. This structure is needed by λ-superposition. A literal l is an equation s ≈ t or a disequation s ̸ ≈ t. A clause is a finite multiset of literals, interpreted and written disjunctively:

l 1 ∨ • • • ∨ l n .
3 Terms E is designed around perfect term sharing [START_REF] Löchner | An evaluation of shared rewriting[END_REF], a principle that we kept in Ehoh and λE: Any two structurally identical terms are guaranteed to be the same object in memory. This is achieved through term cells, which represent individual terms. Each cell has (among other fields) (1) f_code, an integer corresponding to the symbol at the head of the term (negative if the head is a free variable, positive otherwise); (2) num_args, corresponding to the number of arguments applied to the head; and (3) args, an array of size num_args of pointers to argument terms. We use the notation f(s 1 , . . . , s n ) to denote a cell whose f_code corresponds to f, num_args equals n, and args points to the cells for s 1 , . . . s n .

Like Leo-III [START_REF] Steen | Extensional paramodulation for higher-order logic and its effective implementation leo-iii[END_REF]Sect. 4.8], Ehoh represents λ-free higher-order terms using a flattened, spine notation [START_REF] Cervesato | A linear spine calculus[END_REF]. Thus, the terms f, f a, and f a b are represented by the cells f, f(a), and f(a, b). To ensure that free variables are perfectly shared, Ehoh treats applied free variables differently: Arguments are not applied directly to a free variable, but using a distinguished symbol @ of variable arity. For example, the term X a b is represented by the cell @(X, a, b). This ensures that two different occurrences of the free variable X correspond to the same object, which makes substitutions more efficient [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF].

Representation of λ λ λ-Terms. To support full higher-order logic, Ehoh's λ-free cell data structure must be extended to support the λ binder. We use the locally nameless representation [START_REF] Charguéraud | The locally nameless representation[END_REF]: De Bruijn indices represent (possibly loose) bound variables, whereas we keep the current representation for free variables.

Extending the term representation of Ehoh with a new term kind involves intricate manipulation of the cell data structure. De Bruijn indices must be represented like other cells with either a negative or a positive f_code, but the code must clearly identify that the cell is a De Bruijn index.

Apart from during β-reduction, De Bruijn indices mostly behave like constants. Therefore, we choose to represent De Bruijn indices using positive f_codes: The De Bruijn index i will have f_code i. To ensure that De Bruijn indices are not mistaken for function symbols, we use the cell's properties bitfield, which holds precomputed properties. We introduce the property IsDBVar to denote that the cell represents a De Bruijn index. De Bruijn indices are systematically created through a dedicated function that sets the IsDBVar property. When given the same De Bruijn index and type, this function always returns the same object. Finally, we guard all the functions and macros that manipulate function codes to check if the property IsDBVar is set. To ensure perfect sharing of De Bruijn indices, arguments to De Bruijn indices are applied like for free variables, using @.

Extending cells to support λ-abstraction is easier. Each λ-abstraction has the distinguished function code LAM as the head symbol and two arguments: (1) a De Bruijn index 0 of the type of the abstracted variable; (2) the body of the λ-abstraction. Consider the term λx. λy. f x x, where both x and y have the type ι. This term is represented as λ λ f 1 1 in locally nameless representation, where bold numbers represent De Bruijn indices. In λE, the same term is represented by the cell LAM(0, LAM(0, f(1, 1))), where all De Bruijn variables have type ι.

The first argument of LAM is redundant, since it can be deduced from the type of the λ-abstraction. However, basic λ-term manipulation operations often require access to this term. We store it explicitly to avoid creating it repeatedly.

Efficient β β β-Reduction. Terms are stored in βη-reduced form. As these two reductions are performed very often, they ought to be efficient. Ehoh performs β-reduction by reducing the leftmost outermost β-redex first. To represent βredexes, E uses the @ symbol. Thus, the term (λx. λy. (x y)) f a is represented by @(LAM(0, LAM(0, @(1, 0))), f, a). Another option would have been to add arguments applied to λ-terms directly to the λ representation (as in LAM(0, LAM(0, @(1, 0)), f, a)), but this would break the invariant that LAM has two arguments. Furthermore, replacing free variables with λ-abstractions (e.g., replacing X with λx. x in @(X, a)) would require additional normalization.

A term can be β-reduced as follows: When a cell @(LAM(0, s), t) is encountered, the field binding (normally used to record the substitution for a free variable) of the cell 0 is set to t. Then s is traversed to instantiate every loose occurrence of 0 in s with binding, whose loose De Bruijn indices are shifted by the number of λ binders above the occurrence of 0 in s [START_REF] Kamareddine | Reviewing the classical and the de Bruijn notation for λ-calculus and pure type systems[END_REF]. Next, this procedure is applied to the resulting term and its subterms, in leftmost outermost fashion.

λE's β-normalization works in this way, but it features a few optimizations. First, given a term of the form (λx n . s) t n , λE, like Leo-III [START_REF] Steen | There is no best \beta -normalization strategy for higher-order reasoners[END_REF], replaces the bound variables x i with t i in parallel. Avoiding the construction of intermediate terms reduces the number of recursive function calls and calls to the cell allocator.

Second, in line with the gracefulness principle, we want λE to incur little (or no) overhead on first-order problems and to excel on higher-order problems with a large first-order component. If β-reduction is implemented naively, finding a βredex involves traversing the entire term. On purely first-order terms, β-reduction is then a waste of time. To avoid this, we use Ehoh's perfectly shared terms and their properties field. We introduce the property HasBetaReducibleSubterm, which is set if a cell is β-reducible. Whenever a new cell that contains a βreducible term as a direct subterm is shared, the property is set. Setting of the property is inductively continued when further superterms are shared. For example, in the term t = f a (g((λx. x) a)), the cells for (λx. x) a, g ((λx. x) a), and t itself have the property HasBetaReducibleSubterm set. When it needs to find β-reducible subterms, λE will visit only the cells with this property set. This further means that on first-order subterms, a single bit masking operation is enough to determine that no subterm should be visited.

Along similar lines, we introduce a property HasDBSubterm that caches whether the cell contains a De Bruijn subterm. This makes instantiating De Bruijn indices during β-normalization faster, since only the subterms that contain De Bruijn indices must be visited. Similarly, some other operations such as shifting De Bruijn indices or determining whether a term is closed (i.e., it contains no loose bound variables) can be sped up or even avoided if the term is first-order.

Efficient η η η-Reduction. The term λx. s x is η-reduced to s whenever x does not occur unbound in s. Observing that a term cannot be η-reduced if it contains no λ-abstractions, we introduce a property HasLambda that notes the presence of λ's in a term. Only terms with λ's are visited during η-reduction. λE performs parallel η-reduction: It recognizes terms of the form λx m . s x m such that none of the x i occurs unbound in s. If done naively, reducing terms of this kind requires up to m traversals of s to check if each x i occurs in s. In λE, exactly one traversal of s is required. More precisely, when η-reducing a cell LAM(0, s), λE considers all λ binders in s as well. In general, the cell will be of the form LAM(0, . . . , LAM(0, t) . . .), where t is not a λ-abstraction, and l is the number of LAM symbols above t. Then λE breaks the body t down into a decomposition u (n -1) . . . 1 0 where u is not of the form . . . n; such a decomposition is unique. If n = 0, the cell is not η-reducible. Otherwise, u is traversed to determine the minimal index j of a loose De Bruijn index, taking j = ∞ if no such index exists. λE can then remove the k = min{j, l, n} rightmost outermost λ binders in LAM(0, . . . , LAM(0, t) . . .) and replace t by the variant of u (n -1) . . . (k + 1) k obtained by shifting the loose De Bruijn indices down by k.

To illustrate this convoluted De Bruijn arithmetic, we consider the term λx. λy. λz. f x x y z. This term is represented by the cell LAM(0, LAM(0, LAM(0, f(2, 2, 1, 0)))). λE splits f(2, 2, 1, 0) into two parts: u = f 2 and the arguments 2, 1, 0. Since the minimal index in u is 2, we can omit the De Bruijn indices 1 and 0 and their λ binders, yielding the η-reduced cell LAM(0, f(0, 0)).

Parallel η-reduction both speeds up η-reduction and avoids creating intermediate terms. For finding the minimal loose De Bruijn index, optimizations such as the HasDBSubterm property are used.

Representation of Boolean Terms. E and Ehoh represent Boolean terms using cells whose f_codes are reserved for logical symbols. Quantified formulas are represented by cells in which the first argument is the quantified variable and the second one is the body of the quantified formula. For example, the term ∀ ∀ ∀x. p x corresponds to the cell ∀ ∀ ∀(X, p(X)), where X is a free variable. This representation is convenient for parsing and clausification, which is what E and Ehoh use it for, but in full higher-order logic, it is problematic during proof search: Booleans can occur as subterms in clauses, as in q(X) ∨ p(∀ ∀ ∀(X, r(X))), and instantiating X in the first literal should not affect X in the second literal.

To avoid this issue, in λE we use λ binders to represent quantified formulas, as is customary in higher-order logic [1, §51]. Thus, ∀ ∀ ∀x. s is represented by ∀ ∀ ∀ (λx. s). Quantifiers are then unary symbols that do not directly bind the variables. Since λE represents bound variables using De Bruijn indices, this solves all α-conversion issues. However, this solution is incompatible with thousands of decades-old lines of clausification code that assumes E's representation of quantifiers. Therefore, λE converts quantified formulas only after clausification, for Boolean terms that occur in a higher-order context (e.g., as argument to a function symbol).

New Term Orders. The λ-superposition calculus is parameterized by a term order that is used to break symmetries in the search space. We implemented the versions of the Knuth-Bendix order (KBO) and lexicographic path order (LPO) for higher-order terms described by Bentkamp et al. [START_REF] Bentkamp | Superposition for full higher-order logic[END_REF]. These orders encode λ-terms as first-order terms and then invoke the standard KBO or LPO. For efficiency, we implemented separate KBO and LPO functions that compute the order directly, intertwining the encoding and the order computation.

Ehoh cells contain a binding field that can be used to store the substitution for a free variable. Substitutions can then be applied by following the binding pointers, replacing each free variable with its instance. Thus, when Ehoh needs to perform a KBO or LPO comparison of an instantiated term, it needs only follow the binding pointers. In full higher-order logic, however, instantiating a variable can trigger a chain of βη-reductions, changing the shape of the term dramatically. To prevent this, λE computes the βη-reduced instances of the terms before comparing them using KBO or LPO. which case the unifier can be read via the iterator's subst field. Otherwise, no more unifiers can be found, and the iterator is no longer valid. The function's pseudocode is given below, including two auxiliary functions: ForwardIter begins by backtracking if the previous attempt was successful (i.e., all constraints were solved). If it finds a state from which it can continue, it takes term pairs from constraints until there are no more constraints or it is determined that no unifier exists. The terms are normalized by instantiating the head variable with its binding and reducing the potential top-level β-redex that might appear. This instantiation and reduction process is repeated until there are no more top-level β-redexes and the head is not a variable bound to some term. Then the term with shorter λ prefix is expanded (only on the top level) so that both λ prefixes have the same length. Finally, the λ prefix is ignored, and we focus only on the body. In this way, we avoid fully substituting and normalizing terms and perform just enough operations to determine the next step of the procedure.

function NormalizeHead(t) is if t.head = @ ∧ t.
If either term of the constraint is flex, we first invoke oracles to solve the constraint. λE implements the most efficient oracles implemented in Zipperposition: fixpoint and pattern [START_REF] Vukmirović | Efficient full higher-order unification[END_REF]Sect. 6]. An oracle can return three results: (1) there is an MGU for the pair (Unifiable), which is recorded in subst, and the next pair in constraints is tried; (2) no MGU exists for the pair (NotUnifiable), which causes the iterator to backtrack; (3) if the pairs do not belong to the subclass that oracle can solve (NotInFragment), we generate possible variable bindings-that is, we guess the approximate form of the solution.

λE has a dedicated module that generates bindings (NextBinding). This module is given the current constraint and the values of branch_iter and steps, and it either returns the next binding and the new values of branch_iter and steps or reports that all different variable bindings are exhausted. The bindings that λE's unification procedure creates are imitation, Huet-style projection, identification, and elimination (one argument at a time) [START_REF] Vukmirović | Efficient full higher-order unification[END_REF]Sect. 3]. A limit on the total number of applied binding rules can be set, as well as a limit on the number of individual rule applications. The binding module checks whether limits are reached using the iterator's steps field.

Computing bindings is the only point in the procedure where the search tree branches and different possibilities are explored. Thus, when λE follows the branch indicated by the binding module, it records the state to which it needs to return should the followed branch be backtracked. The state consists of the values of constraints, steps, and subst before the branch is followed and the value of branch_iter that points past the followed branch. The values of branch_iter are either BindBegin, which denotes that no binding was created, intermediate values that NextBinding uses to remember how far through bindings it is, and BindEnd, which indicates that all bindings are exhausted.

If all bindings are exhausted, the procedure checks whether the pair is flex-flex and both sides have the same head. If so, the pair is decomposed and constraints are derived from the pair's arguments; otherwise, the iterator backtracks. If the pair is rigid-rigid, for unification to succeed, the heads of both sides must be the same. Unification then continues with new constraints derived from the arguments. Otherwise, the iterator must be backtracked.

Matching. In E, the matching algorithm is mostly used inside simplification rules such as demodulation and subsumption [START_REF] Schulz | E-a brainiac theorem prover[END_REF]. As these rules must be efficiently performed, using a complex matching algorithm is not viable. Instead, we provide a matching algorithm for the pattern class of terms [START_REF] Nipkow | Functional unification of higher-order patterns[END_REF] to complement Ehoh's λ-free higher-order matching algorithm [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF]Sect. 4]. A term is a pattern if each of its free variables either has no arguments (as in first-order logic) or is applied to distinct De Bruijn indices.

To help determine whether to use the pattern or λ-free algorithm, we introduce a cached property HasNonPatternVar, which is set for terms of the form X s n where n > 0 and either there exists some s i that is not a De Bruijn index or there exist indices i < j such that s i = s j is a De Bruijn index. This property is propagated to the superterms when they are perfectly shared. This allows later checks if a term belongs to the pattern class to be performed in constant time.

We modify the λ-free higher-order matching algorithm to treat λ prefixes as above in the unification procedure-by bringing the prefixes to the same length and ignoring them afterwards. This ensures that the algorithm will never try to match a free variable with a λ-abstraction, making sure that β-redexes never appear. We also modify the algorithm to ensure that free variables are never bound to terms that have loose bound variables. This algorithm cannot find many complex matching substitutions (matchers), but it can efficiently determine whether two terms are variable renamings of each other or whether a simple matcher can be used, as in the case of (X (λx. x) b, f (λx. x) b), where X → f is usually the desired matcher. If this algorithm does not find a matcher and both terms are patterns, pattern matching is tried.

Indexing. E, like other modern theorem provers, efficiently retrieves unifiable or matchable pairs of terms using indexing data structures. To find terms unifiable with a query term or instances of a query term, it uses fingerprint indexing [START_REF] Schulz | Fingerprint indexing for paramodulation and rewriting[END_REF]. Vukmirović et al. extended this data structure to support full higher-order terms in Zipperposition [START_REF] Vukmirović | Efficient full higher-order unification[END_REF]Sect. 6]. We use the same approach in λE, and we extend feature vector indices [START_REF] Schulz | Simple and efficient clause subsumption with feature vector indexing[END_REF] in the same way.

E uses perfect discrimination trees [START_REF] Mccune | Experiments with discrimination-tree indexing and path indexing for term retrieval[END_REF] to find generalizations of the query term (i.e., terms of which the query term is an instance). This data structure is a trie that indexes terms by representing them in a serialized, flattened form. The left branch from the root in Figure 1 shows how the first-order terms f a X Fig. 1. First-order, λ-free higher-order, and higher-order pattern terms in a perfect discrimination tree and f a a are stored. In Ehoh, this data structure is extended to support partial application and applied variables [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF].

In λE, we extend this structure to support λ-abstractions and the higher-order pattern matching algorithm. To this end, we change the way in which terms are serialized. First, we require that all terms are fully η-expanded (except for arguments of variables applied in patterns). Then, when the term is serialized, we use a single node for applied variable terms X s n , instead of a node for X followed by nodes for the arguments s n . We serialize the λ-abstraction λx. s using a dedicated node LAM τ , where τ is the type of x, followed by the serialization of s. Other than these changes, serialization remains as in Ehoh, following the gracefulness principle. Figure 1 shows how g (X a b) c and h (λx. λy. X y x) are serialized. Since the terms are stored in serialized form, it is hard to manipulate λ prefixes of stored terms during matching. Performing η-expansion when serializing terms ensures that matchable terms have λ prefixes of the same length.

We have dedicated separate nodes for applied variables because access to arguments of applied variables is necessary for the pattern matching algorithm. Even though arguments can be obtained by querying the arity n of the variable and taking the next n arguments in the serialization, this is both inefficient and inelegant. As for De Bruijn indices, we treat them the same as function symbols.

Following the notation from the extension of perfect discrimination trees to λ-free higher-order logic [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF], we now describe how enumeration of generalizations is performed. To traverse the tree, λE begins at the root node and maintains two stacks: term_stack and term_proc, where term_stack contains the subterms of the query term that have to be matched, and term_proc contains processed terms that are used to backtrack to previous states. Initially, term_stack contains the query term, the current matching substitution σ is empty, and the successor node is chosen among the child nodes as follows:

A. If the node is labeled with a symbol ξ (where ξ is either a De Bruijn index or a constant) and the top item t of term_stack is of the form ξ t n , replace t by n new items t 1 , . . . , t n , and push t onto term_proc.

B. If the node is labeled with a symbol LAM τ and the top item t of term_stack is of the form λx. s and the type of x is τ , replace t by s, and push t onto term_proc. C. If the node is labeled with a possibly applied variable X s n (where n ≥ 0), and the top item of term_stack is t, the matching algorithm described above is run on X s n and t. The algorithm takes into account σ built so far and extends it if necessary. If the algorithm succeeds, pop t from term_stack, push it onto term_proc, and save the original value of σ in the node.

Backtracking works in the opposite direction: If the current node is labeled with a De Bruijn index or function symbol node of arity n, pop n terms from term_stack and move the top of term_proc to term_stack. If the node is labeled with LAM τ , pop the top of term_stack and move the top of term_proc to term_stack. Finally, if the node is labeled with a possibly applied variable, move the top of the term_proc to term_stack and restore the value of σ.

As an example of how finding a generalization works, when looking for generalizations of g (f a b) c in the tree of Figure 1, the following states of stacks and substitutions emerge, from left to right:

ϵ g g.(X a b) g.(X a b).c term_stack [g (f a b) c] [f a b, c] [c] [] term_proc [] [g (f a b) c] [f a b, g (f a b) c] [c, f a b, g (f a b) c] σ ∅ ∅ {X → f} {X → f} 5

Preprocessing, Calculus, and Extensions

Ehoh's simple λ-free higher-order calculus performed well on Sledgehammer problems and formed a promising stepping stone to full higher-order logic [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF]. When implementing support for full higher-order logic, we were guided by efficiency and gracefulness with respect to Ehoh's calculus rather than completeness. Whereas Zipperposition provides both complete and incomplete modes, λE only offers incomplete modes.

Preprocessing. Our experience with Zipperposition showed the importance of flexibility in preprocessing the higher-order problems [START_REF] Vukmirović | Making higher-order superposition work[END_REF]. Therefore, we implemented a flexible preprocessing module in λE.

To maintain compatibility with Ehoh, λE can optionally transform all λabstractions into named functions. This process is called λ-lifting [START_REF] Hughes | Super combinators: A new implementation method for applicative languages[END_REF]. λE also removes all occurrences of Boolean subterms (other than ⊥ ⊥ ⊥, ⊤ ⊤ ⊤, and free variables) in higher-order contexts using a FOOL-like transformation [START_REF] Kotelnikov | A clausal normal form translation for FOOL[END_REF]. For example, the formula

f(p ∧ ∧ ∧ q) ≈ ≈ ≈ a becomes (p ∧ ∧ ∧ q → → → f(⊤ ⊤ ⊤) ≈ ≈ ≈ a) ∧ ∧ ∧ (¬ ¬ ¬ (p ∧ ∧ ∧ q) → → → f(⊥ ⊥ ⊥) ≈ ≈ ≈ a).
Many TPTP problems use the definition role to identify the definitions of symbols. λE can treat definition axioms as rewrite rules, and replace all occurrences of defined symbols during preprocessing. Furthermore, during SInE [START_REF] Hoder | Sine qua non for large theory reasoning[END_REF] axiom selection, it can always include the defined symbol in the trigger relation.

Calculus. λE implements the same superposition calculus as Ehoh with three important changes. First, wherever Ehoh requires the MGU of terms, λE enumerates unifiers from a finite subset of the CSU, as explained in Sect. 4. Second, λE uses versions of the KBO and LPO orders designed for λ-terms.

The third difference is more subtle. One of the main features of Ehoh is prefix optimization [42, Sect. 1]: a method that, given a demodulator s ≈ t, makes it possible to replace both applied and unapplied occurrences of s by t by traversing only the first-order subterms of a rewritable term. In a λ-free setting, this optimization is useful, but in the presence of βη-normalization, the shapes of terms can change drastically, making it much harder to track prefixes of terms. This is why we disable the prefix optimization in λE. To compensate for losing this optimization, we introduce the argument congruence rule AC in λE and enable positive and negative functional extensionality (PE and NE) by default:

s ≈ t ∨ C AC s X ≈ t X ∨ C s ̸ ≈ t ∨ C NE s (sk X) ̸ ≈ t (sk X) ∨ C s X ≈ t X ∨ C PE s ≈ t ∨ C
AC and NE assume that s and t are of function type. In NE, X denotes all the free variables occurring in s and t, and sk is a fresh Skolem symbol of the appropriate type. PE has a side condition that X may not occur in s, t, or C.

Saturation. E's saturation procedure assumes that each attempt to perform an inference will either result in a single clause or fail due to one of the inference side conditions. Unification procedures that produce multiple substitutions break this invariant, and the saturation procedure needed to be adjusted.

For Zipperposition, Vukmirović et al. developed a variant of the saturation procedure that interleaves computing unifiers and scheduling inferences to be performed [START_REF] Vukmirović | Making higher-order superposition work[END_REF]. Since completeness was not a design goal for λE, we did not implement this version of the saturation procedure. Instead, in places where previously a single unifier was expected, λE consumes all elements of the iterator used for enumerating a unifier, converting them into clauses.

Reasoning about Formulas. Even though most of the Boolean structure is removed during preprocessing, formulas can reappear at the top level of clauses during saturation. For example, after instantiating X with λx. λy. x∧ ∧ ∧y, the clause X p q ∨ a ≈ b becomes (p ∧ ∧ ∧ q) ∨ a ≈ b. λE converts every clause of the form φ ∨ C, where φ has a logic symbol as its head, or it is a (dis)equation between two formulas different than ⊤ ⊤ ⊤, to an explicitly quantified formula. Then, the clausification algorithm is invoked on the formula to restore the clausal structure. Zipperposition features more dynamic clausification modes, but for simplicity we decided not to implement them in λE.

The λ-superposition calculus for full higher-order logic [START_REF] Bentkamp | Superposition for full higher-order logic[END_REF] includes many rules that act on Boolean subterms, which are necessary for completeness. Other than Boolean simplification rules, which use simple tautologies such as p ∧ ∧ ∧ ⊤ ⊤ ⊤ ↔ ↔ ↔ p to simplify terms, we have implemented none of the Boolean rules of this calculus in λE. First, we have observed that complicated rules such as FluidBoolHoist and FluidLoobHoist are hardly ever useful in practice and usually only contribute to an uncontrolled increase in the proof state size. Second, simpler rules such as BoolHoist can usually be simulated by pragmatic rules that perform Boolean extensionality reasoning, described below.

To make up for excluding Boolean rules, we use an incomplete, but more easily controllable and intuitive rule, called primitive instantiation. This rule instantiates free predicate variables with approximations of formulas that are ground instances of this variable. We use the approximations described by Vukmirović and Nummelin [START_REF] Vukmirović | Boolean reasoning in a higher-order superposition prover[END_REF]Sect. 3.3].

λE's handling of the Hilbert choice operator is inspired by Leo-III's [START_REF] Steen | Extensional higher-order paramodulation in Leo-III[END_REF]. λE recognizes clauses of the form ¬ P X ∨ P (f P ), which essentially denote that f is a choice symbol. Then, when subterm f s is found during saturation, s is used to instantiate the choice axiom for f. Similarly, Leibniz equality [START_REF] Vukmirović | Boolean reasoning in a higher-order superposition prover[END_REF] is eliminated by recognizing clauses of the form ¬ P a ∨ P b ∨ C. These clauses are then instantiated with P → λx. x ≈ a and P → λx. x ̸ ≈ b, which results in a ≈ b ∨ C.

Finally, λE treats induction axioms specially. Like Zipperposition [START_REF] Vukmirović | Making higher-order superposition work[END_REF]Sect. 4], it abstracts literals from the goal clauses and instantiates induction axioms with these abstractions. Since Zipperposition supports dynamic calculus-level clausification, induction axioms are instantiated during saturation, when the axioms are processed. In λE, this instantiation is performed immediately after clausification. After λE has collected all the abstractions, it traverses the clauses and instantiates those that have applied variable of the same type as the abstraction.

Extensionality. λE takes a pragmatic approach to reasoning about functional and Boolean extensionality: It uses abstracting rules [START_REF] Bentkamp | Superposition with lambdas[END_REF] which simulate basic superposition calculus rules but do not require unifiability of the partner terms in the inference. More precisely, assume a core inference needs to be performed between two β-reduced terms u and v, such that they can be represented as u = C[s 1 , . . . , s n ] and v = C[t 1 , . . . , t n ], where C is the most general "green" [START_REF] Bentkamp | Superposition with lambdas[END_REF] common context of u and v, not all of s i and t j are free variables, and for at least one i, s i ̸ = t i , s i and t i are not possibly applied free variables, and they are of Boolean or function type. Then, the conclusion is formed by taking the conclusion D of the core inference rule (which would be created if s and t are unifiable) and adding literals s

1 ̸ ≈ t 1 ∨ • • • ∨ s n ̸ ≈ t n .
These rules are particularly useful because λE has no rules that dynamically process Booleans in FOOL-like fashion, such as BoolHoist. For example, given the clauses f (p∧ ∧ ∧q) ≈ a and g (f p) ̸ ≈ b, the abstracting version of the superposition rule would result in g a ̸ ≈ b ∨ (p ∧ ∧ ∧ q) ̸ ≈ p. In this way, the Boolean structure bubbles up to the top level and is further processed by clausification. We noticed that this alleviates the need for the other Boolean rules in practice.

Evaluation

We now try to answer two questions about λE: How does λE compare against other higher-order provers (including Ehoh)? Does λE introduce any overhead compared with Ehoh? To answer these questions, we ran provers on problems from the TPTP library [START_REF] Sutcliffe | The TPTP problem library and associated infrastructure-from CNF to TH0, TPTP v6.4.0[END_REF] and on benchmarks generated by Sledgehammer (SH) [START_REF] Paulson | Three years of experience with Sledgehammer, a practical link between automatic and interactive theorem provers[END_REF]. The experiments were carried out on StarExec Miami [START_REF] Stump | StarExec: A cross-community infrastructure for logic solving[END_REF] nodes equipped with Intel Xeon E5-2620 v4 CPU clocked at 2.10 GHz. For the TPTP part, we used the CASC 20212 time limits: 120 s wall-clock and 960 s CPU. For SH benchmarks and to answer the other question, we used Sledgehammer's default time limit: 30 s wall-clock and CPU. The raw evaluation data is available online. 3Comparison with Other Provers. To answer the first question, we let λE compete with the top contenders in the higher-order division of CASC 2021: cvc5 0.0.7 [START_REF] Barbosa | cvc5: A versatile and industrialstrength SMT solver[END_REF], Ehoh 2.7 [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF], Leo-III 1.6.6 [START_REF] Steen | Extensional higher-order paramodulation in Leo-III[END_REF], Vampire 4.6 [START_REF] Bhayat | A combinator-based superposition calculus for higher-order logic[END_REF], and Zipperposition 2.1 [START_REF] Vukmirović | Making higher-order superposition work[END_REF]. We also included Satallax 3.5 [START_REF] Brown | Satallax: An automatic higher-order prover[END_REF]. We used all 2899 higher-order theorems in TPTP 7.5.0 as well as 5000 SH higher-order benchmarks originating from the Seventeen benchmark suite [START_REF] Desharnais | Seventeen provers under the hammer[END_REF]. On SH benchmarks, cvc5, Ehoh, λE, Vampire, and Zipperposition were run using custom schedules provided by their developers, optimized for single-core usage and low timeouts. Otherwise, we used the corresponding CASC configurations.

Although it internally does not support λ-abstractions, Ehoh 2.7 can parse full higher-order logic using λ-lifting. We included two versions of Zipperposition: coop uses Ehoh 2.7 as a backend to finish proof attempts, whereas uncoop does not. Both Ehoh and λE were run in the automatic scheduling mode. Compared with Ehoh, λE features a redesigned module for automatic scheduling, it can exploit multiple CPU cores, and its heuristics have been more extensively trained on higher-order problems.

The results are shown in Figure 2. λE dramatically improves E's higher-order reasoning capabilities compared with Ehoh. It solves 20% more TPTP benchmarks and 7% more SH benchmarks. The reason for the higher preformance increase for TPTP is likely that TPTP benchmarks tend to require more higher-order reasoning than SH benchmarks, which often have a large first-order component and for which Ehoh was already very successful.

λE was envisioned as an efficient backend to proof assistants. As such, it excels on SH benchmarks, outperforming the competition. On TPTP, it outperforms all higher-order provers other than Zipperposition-coop. If Zipperposition's Ehoh backend is disabled, λE outperforms Zipperposition by a wide margin. This comparison is arguably fairer; after all, λE does not use an older version of Zipperposition as a backend. These results suggest that λE already implements most of the necessary features for a high-performance higher-order prover but could benefit from the kind of fine-tuning that Zipperposition underwent in the last four years.

Remarkably, the raw evaluation data reveals thats λE solves 181 SH problems and 24 TPTP problems that Zipperposition-coop does not. The lower number of uniquely solved TPTP problems is likely because Zipperposition was heavily optimized on the TPTP. Comparison with the First-Order E. Both Ehoh and λE can be compiled in a mode that disables most of the higher-order reasoning. This mode is designed for users that are interested only in E's first-order capabilities and care a lot about performance. To answer the second evaluation question, about assessing overhead of λE, we chose all the 1138 unique problems used at CASC from 2019 to 2021 in the first-order theorem division and ran Ehoh and λE both in this first-order (FO) mode and in higher-order (HO) mode.

We fixed a single configuration of options, because Ehoh's and λE's automatic scheduling methods could select different configurations and we would not be measuring the overhead but the quality of the chosen configurations. We chose the boa configuration [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF]Sect. 7], which is the configuration most often used by E 2.2 in its automatic scheduling mode. The results are shown in Figure 3.

Counterintuitively, the higher-order versions of both provers outperform the first-order counterparts. However, the difference is so small that it can be attributed to the changes to memory layout that affect the order in which clauses are chosen. Similar effects are visible when comparing the first-order versions.

CASC Results. λE also took part in CASC 2022. In the TPTP higher-order division, λE finished second, after Zipperposition, as expected. In the Sledgehammer division, λE tied with Ehoh for first place, a disappointment. The likely explanation is that λE used a wrong configuration in this division, as we found out afterwards. We expect better performance at CASC 2023.

Discussion and Related Work

On the trajectory to λE, we developed, together with colleagues, three superposition calculi: for λ-free higher-order logic [START_REF] Bentkamp | Superposition for lambda-free higher-order logic[END_REF], for a higher-order logic with λ-abstraction but no Booleans [START_REF] Bentkamp | Superposition with lambdas[END_REF], and for full higher-order logic [START_REF] Bentkamp | Superposition with lambdas[END_REF]. These milestones allowed us to carefully estimate how the increased reasoning capabilities of each calculus influence its performance.

Extending first-order provers with higher-order reasoning capabilities has been attempted by other researchers as well. Barbosa et al. extended the SMT solvers CVC4 (now cvc5) and veriT to higher-order logic in an incomplete way [START_REF] Barbosa | Extending SMT solvers to higher-order logic[END_REF]. Bhayat and Reger first extended Vampire to higher-order logic using combinatory unification [START_REF] Bhayat | A combinator-based superposition calculus for higher-order logic[END_REF], an incomplete approach, before they designed and implemented a complete higher-order superposition calculus based on SKBCI combinators [START_REF] Bhayat | Restricted combinatory unification[END_REF]. The advantage is that combinators can be supported as a thin layer on top of λ-free terms. This calculus is also implemented in Zipperposition. However, in informal experiments, we found that λ-superposition performs substantially better, corroborating the CASC results, so we decided to make a more profound change to Ehoh and implement λ-superposition.

Possibly the only actively maintained higher-order provers built from the bottom up as higher-order provers are Leo-III [START_REF] Steen | Extensional higher-order paramodulation in Leo-III[END_REF] and Satallax's [START_REF] Brown | Satallax: An automatic higher-order prover[END_REF] successor Lash [START_REF] Brown | Lash 1.0 (system description)[END_REF]. A further overview of other traditional higher-order provers and the calculi they are based on can be found in the paper about Ehoh [42, Sect. 9].

Conclusion

In 2019, the reviewers of our Ehoh paper [START_REF] Vukmirović | Extending a brainiac prover to lambda-free higher-order logic[END_REF] were skeptical that extending Ehoh with support for full higher-order logic would be feasible. One of them wrote:

A potential criticism could be that this step from E to Ehoh is just extending FOL by those aspects of HOL that are easily in reach with rather straightforward extensions (none of the extensions is indeed very complicated), and that the difficult challenges of fully supporting HOL have yet to be confronted.

We ended up addressing the theoretical "difficult challenges" in other work with colleagues. In this paper, we faced the practical challenges pertaining to the extension of Ehoh's data structures and algorithms to support full higherorder logic and demonstrated that such an extension is possible. Our evaluation shows that this extension makes λE the best higher-order prover on benchmarks coming from interactive theorem proving practice, which was our goal. λE lags slightly behind Zipperposition on TPTP problems. One reason might be that Zipperposition does not assume a clausal structure and can perform subtle formula-level inferences. It would be useful to implement the same features in λE. We have also only started tuning λE's heuristics on higher-order problems.

  BindEnd then push pair (lhs,rhs) back to iter .constraints push quadruple (iter .constraints, n_branch_iter , iter .steps, iter .subst) onto iter .bt_state extend iter .subst with n_binding iter .steps ← n_steps iter .branch_iter ← BindBegin else if lhs.head = rhs.head then create constraint pairs of arguments of lhs and rhs and push them to iter .constraints iter .branch_iter ← BindBegin else if lhs.head = rhs.head then create constraint pairs of arguments of lhs and rhs and push them to iter .constraints else forward ← BacktrackIter(iter ) return forward

	args[0].is_lambda() then
	reduce the top-level β-redex in t
	return NormalizeHead(t)
	else if t.head .is_var () ∧ t.head .binding ̸ = Nil then
	t.head ← t.head .binding
	return NormalizeHead(t)
	else
	return t

function BacktrackIter(iter ) is if iter .bt_state.empty() then clear all fields in iter return False else pop (constraints, branch_iter , steps, subst) from iter .bt_state set the corresponding fields of iter return True function ForwardIter(iter ) is forward ← ¬ iter .constraints.empty() ∨ BacktrackIter(iter ) while forward ∧ ¬ iter .constraints.empty() do (lhs, rhs) ← pop pair from iter .constraints lhs ← NormalizeHead(lhs) rhs ← NormalizeHead(rhs) normalize and discard the λ prefixes of lhs and rhs if ¬lhs.head .is_var () ∧ rhs.head .is_var () then swap lhs and rhs if lhs.head .is_var () then oracle_res ← Fixpoint(lhs, rhs, iter .subst) if oracle_res = NotInFragment then oracle_res ← Pattern(lhs, rhs, iter .subst) if oracle_res = NotUnifiable then forward ← BacktrackIter(iter) else if oracle_res = NotInFragment then n_steps, n_branch_iter , n_binding ← NextBinding(lhs, rhs, iter .steps, iter .branch_iter ) if n_branch_iter ̸ =

https://github.com/eprover/eprover.git

Unification, Matching, and Term IndexingStandard superposition crucially depends on the concept of a most general unifier (MGU). In higher-order logic, the concept is replaced by that of a complete set of unifiers (CSU), which may be infinite. Vukmirović et al.[START_REF] Vukmirović | Efficient full higher-order unification[END_REF] designed an efficient procedure to enumerate a CSU for a term pair. It is implemented in Zipperposition, together with some extensions to term indexing. In λE, we further improve the performance of this procedure by implementing a terminating, incomplete variant. We also introduce a new indexing data structure.The Unification Procedure. The unification procedure works by maintaining a list of unification pairs to be solved. After choosing a pair, it first normalizes it by β-reducing and instantiating the heads of both terms in the pair. Then, if either head is a variable, it computes an appropriate binding for this variable, thereby approximating the solution.Unlike in first-order and λ-free higher-order unification, in the full higher-order case there may be many bindings that lead to a solution. To reduce this mostly blind guessing of bindings, the procedure features support for oracles[START_REF] Vukmirović | Efficient full higher-order unification[END_REF]. These are procedures that solve the unification problem for a subclass of higher-order terms on which unification is decidable and, for λE, unary. Oracles help increase performance, avoid nontermination, and avoid redundant bindings.Vukmirović et al. described their procedure as a transition system. In λE, the procedure is implemented nonrecursively, and the unifiers are enumerated using an iterator object that encapsulates the state of the unifier search. The iterator consists of five fields: (1) constraints, which holds the unification constraints;(2) bt_state, a stack that contains information necessary to backtrack to a previous state; (3) branch_iter, which stores how far we are in exploring different possibilities from the current search node; (4) steps, which remembers how many different unification bindings (such as imitation, projection, and identification) are applied; and (5) subst, a stack storing the variables bound so far.The iterator is initialized to hold the original problem in constraints, and all other fields are initially empty. The unifiers are retrieved one by one by calling the function ForwardIter. It returns True if the iterator made progress, in

http://www.tptp.org/CASC/28/

https://doi.org/10.5281/zenodo.6389849

Acknowledgment. Ahmed Bhayat and Martin Suda provided Vampire configurations optimized for Sledgehammer. Andrew Reynolds did the same for cvc5. Jannis Limperg helped us debug the submission artifact. Simon Cruanes, Wan Fokkink, Mark Summerfield, and the anonymous reviewers suggested several textual improvements. We thank them all. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 713999, Matryoshka). Vukmirović and Blanchette have received funding from the Netherlands Organization for Scientific Research (NWO) under the Vidi program (project No. 016.Vidi.189.037, Lean Forward).