Román Mozuelos
email: roman.mozuelos@unican.es

Mar Martínez Yolanda Lechuga
email: yolanda.lechuga@unican.es

Salvador Bracho
email: salvador.bracho@unican.es

Test based on Built-In Current Sensors for Mixed-Signal Circuits

Keywords: Dynamic current test, Built-in current sensor, Design for test, Mixed-signal circuit

This paper presents a test methodology for mixed-signal circuits. The test approach uses a built-in sensor to analyze the dynamic current supply of the circuit under test. This current sensor emphasizes the highest harmonics of the dynamic current of the circuit under test when the current to voltage conversion is done. The goodness of the test method is analyzed first by means of a fault simulation and afterwards through the experimental data obtained from several benchmark circuits.

Introduction

The increase of mixed signal applications, with integrated circuits containing both analog and digital sections, motivates the development of design-for-test approaches for testing analog macros embedded in digital systems. The success of supply current monitoring (I DD ) in digital CMOS integrated circuits has prompted researches to investigate the feasibility of I DD as a testing methodology for analog modules [START_REF] Robson | In Current Monitoring Technique for Testing Embedded Analogue Functions in Mixed-Signal ICs[END_REF].

A survey of I DD test methodologies, both quiescent and transient, can be found in [START_REF] Sabade | In I DDX -Based Test Methods: A Survey[END_REF]. All of them require precise measurements to be effective. Traditionally the current measurement is performed externally to the chip. However, to enhance the precision and to increase the sampling rate may require the use of suitable built-in current sensor circuits (BICS) to measure the current inside the chip [START_REF] Alorda | In A two-level Power-Grid Model for Transient Current Testing Evaluation[END_REF].

The design of these BICS relies on the voltage drop across a resistance, induced by the dynamic supply current, in order to generate the fault signal. This current is captured in the sensor directly [START_REF] Maidon | In 3.3V CMOS Built-In Current Sensor[END_REF] or through current mirrors [START_REF] Stopjaková | In On-Chip Transient Current Monitor for Testing of Low-Voltage CMOS IC[END_REF]. Sometimes, the charge accumulated in a capacitor is used to detect the shape of the dynamic current of the circuits with faults [START_REF] Segura | In Experimental Analysis of Transient Current Testing Based on Charge Observation[END_REF].

The paper is organised as follows. Section 2 highlights the contribution to technological innovation. Section 3 presents the I DDX test method. Section 4 analyses the efficiency of the test method by means of a fault evaluation. Section 5 shows measured data from the benchmark circuits. Finally, the discussion and the conclusions are presented.

Contribution to Technological Innovation

This work proposes a new test method based on the analysis of the circuit dynamic current (I DDX ), both quiescent and transient, for the verification of digital, analog and mixed-signal circuits. The structural test method aims to reduce the test time and the complexity of the measurement equipment commonly used in mixed-signal tests.

Dynamic Current Test Method

In order to process accurately the information contained in the dynamic current that goes across the circuit under test (CUT), the measurement is performed by a built-in current sensor circuit (BICS) integrated within the CUT. Thus, it minimizes the distortion effect of the capacitances and inductances associated with the input/output pads, the circuit package and the elements of the printed circuit board.

The BICS output provides a sequence of digital pulses whose width reflects the amplitude and duration of the dynamic current. Defective circuits are exposed comparing the BICS output waveform of the CUT with the expected one for the faultfree circuit.

The test setup, besides providing the CUT stimulus, requires a digital signature analyzer to process the BICS output. This low cost equipment can be as simple as an integrator, a counter or a memory.

Built-In Current Sensor

In the mixed signal circuit, the current across the digital logic is sampled in series by a BICS placed in the power supply path between the CUT ground (Virtual_GND) and the chip pin (GND) (figure 1). The sampling element is a MOSFET transistor because it is able to accept large current transients without introducing a significant voltage drop and, at the same time, it is sensitive to the small quiescent currents [START_REF] Mozuelos | In Built-in Current Sensor in Mixed Circuit Test Based on Dynamic Power Supply Consumption[END_REF]. However, this measurement strategy would degrade the performance of the analog blocks due to the reduction of their effective voltage supply. Therefore, in this case, the current is replicated by placing additional branches to the current mirrors of the circuits, taking advantage of the widely use of these basic build blocks in analog design [START_REF] Mozuelos | In Built-In Sensor Based on the Time Variation of the Transient Current Supply in Analogue Circuits[END_REF].

In both cases, the sampled current is converted to voltage, then amplified and finally digitalized by a window comparator made of CMOS digital gates.

Under faulty conditions, the normal values of the analog circuit current may be increased, decreased or more generally distorted. Some of these faults do not produce a significant change in the quiescent current. However, they can affect the relationship of the harmonic components of the current waveform, causing a change in the slope of transient of the dynamic supply current [START_REF] Lechuga | In Built-in Dynamic Current Sensor for Hard to Detect Faults in Mixed Signal ICs[END_REF].

So, we have designed a novel built-in current sensor circuit with the goal to emphasize the high-frequency components of the current when the current to voltage conversion is done. It uses the principle that a capacitor placed at the output port of a gyrator behaves like an inductance at the input port. A prototype, without the window comparator, has been fabricated with the Austria MicroSystem (AMS) 0.6 µm technology to characterise the frequency response of the circuit. The chip photograph can be seen in figure 2b.

Figure 3 displays the experimental measurements of the circuit tranresistance (v OUT vs. i IN ). The left graph shows a good agreement among the theoretical calculus using the small signal model of the circuit, the layout simulation with the AMS 0.6µm technological transistor models and the data measured from a fabricated chip.

The circuit behaviour emulates an inductance with one series and one parallel stray resistor, where the BICS sensitivity to the high frequency components of the current can be appreciated in the abrupt change of the circuit output voltage (lower graph of figure 3b) when a current pulse is injected at the BICS input (upper graph of figure 3b). The quiescent change of the voltage, after the current stabilization, is smaller and it is given by the low frequency impedance of the circuit. The BICS design is quite sensitive to process spread attributable to the transistor implementation of the capacitor.

Fault Evaluation

A fault simulation has been carried out to check the efficiency of the test method. The process consists on the analysis of CUT behaviour when we include the electrical abstraction of a fabrication defect (known as fault) and the comparison of the circuit performance with expect for the fault-free one.

Defects in the integrated circuit materials commonly give rise to catastrophic faults [START_REF] Segura | CMOS Electronics: How it Works, How it Fails[END_REF]. In this work, we have considered short circuits between the transistor terminals, gate oxide shorts (GOS) and large deviations of the passive components (figure 4). The fault model includes soft opens due to cracks in the interconnection lines, where there is still a small current flow due to the quantum phenomenon of the tunnel effect. Hard opens, especially the open gate defect, due to the complete disconnection of the line strongly depends on the technology and physical topology of the circuit and are more difficult to model in an initial stage of the circuit analysis [START_REF] Arumí | In Experimental Characterization of CMOS Interconnect Open Defects[END_REF].

The I DDX test method uses the width of the digital pulses that appear at the sensor output for each transition of the CUT inputs to expose the defective circuits. In order to get an estimation of the goodness of the proposed test approach, the fault coverage obtained through the BICS output is compared with other more traditional structural tests. They are the quiescent current (I DDQ test) and the DC voltage at the circuit outputs.

The threshold detection limit can be established through a Montecarlo simulation taking into account the process spread, or by means of the comparison with the measures taken from a well-known good circuit (golden device). These limits include a 100ns resolution in the pulse width of the BICS digital output, a 5µA variation in the I DDQ of the CMOS logic, a change in the logic state of the digital outputs, and a 10mV deviation for the expected voltage at the analog block output.

Several benchmark circuits, both digital and analog, have been designed and fabricated to carry out the test evaluation. The digital module includes combinational logic cells and sequential memory registers. The BICS is placed between the CUT ground and the ground package pin [START_REF] Olbrich | In Design-for-Test (DfT) Study in a Current Mode DAC[END_REF].

The analog block is an operational amplifier in a voltage follower configuration. The current through the differential stage of the operational amplifiers is sampled by a new transistor added to the current mirror. As these circuits are usually connected in feedback configurations, the sampled current is sensitive not only to the differential stage and the bias network but also to the output stage.

Experimental Measurements

The test method has been experimentally validated through the design and fabrication of the benchmark circuits with the implementation of the BICS.

Figure 6 shows a measure of the BICS that analyzes the current through the digital logic. The sensor generates pulses proportional to the CUT dynamic current when a transition happens at the circuit inputs or at the clock signal. Three faults have been integrated within the manufactured operational amplifier (figure 7). All the faults have a parametric behaviour as they are implemented by an NMOS transistor (W=1µm, L=80µm) whose ON resistance is over 250 KΩ. The faults emulate a mismatch on the current mirror transistors of the differential stage (F1), an oxide pinhole in the compensation capacitor (F2) and a deviation in the current provided by the bias network (F3). An analog multiplexer selects each time a fault. The operational amplifier is configured as voltage follower in this experiment. The input and the output voltages are displayed on the upper part of figure 8 graphs for the fault-free and two faulty conditions. The BICS waveforms are displayed on the lower part of figure 8 graphs. Although the three faults produce small variations on the DC levels at the operational amplifier output, almost negligible in F3, all of them induce a large change in the pulse width of the BICS, consequently they are easily detectable with the proposed test method [START_REF] Mozuelos | In Experimental Evaluation of a Built-in Current Sensor for Analog Circuits[END_REF].

The same measured values for gain, offset voltage and slew-rate in two versions of the operational amplifier, one alone and the other with the BICS, allows appreciating the minimal influence of the sensor in the CUT performance. The influence of the process spread in the BICS behaviour can be notice in table 1. It shows the Montecarlo simulation of the fabricated circuit. The large standard deviation of the BICS pulse width has to be taken into account to set the boundary limits for the pass/fail flag. To obtain these values it may be necessary to know precisely the fabrication parameters or to use a golden device as reference. In spite of this dispersion, the BICS output allows a clear discrimination between the fault-free circuit and the defective ones.

Discussion of Results

The proposed I DDX test method provides a better fault coverage figure than the one obtained from a more traditional structural DC tests used as reference. Although, sometimes it is still necessary to characterize the functional performance of the mixed signal circuits before shipment due to customer or manufacturer necessities, the reduced test time and lower requirements of the test equipment makes this structural I DDX test suitable for its application at the wafer level allowing an easy discrimination of the chips before their inclusion in the system package.

Conclusions and Further Work

This work proposes a new test method for mixed-signal circuits based on the analysis of the circuit dynamic current (I DDX ), both quiescent and transient.

The structural test uses a built-in current sensor to sample the dynamic current through selected branches of the CUT. The BICS was designed to prioritise the information obtained from the highest frequency components of the current.

The future development of this work should study the correlation between the BICS output and the functional performance of the CUT to relate the structural fault detection of the proposed I DDX test with the test process yield.

The test method can be extended to a full BIST structure. To achieve this, the output signal processing must be included within the chip. It will be also necessary to allow the user to set the threshold limit that classifies the circuit as defective and to standardize the communication between the BICS and the test system.

Fig. 1 .

 1 Fig. 1. BICS to analyse the dynamic current through the digital logic.

Fig. 2 .

 2 Fig. 2. Proposed Built-In current sensor (a) Scheme and (b) die photograph.The circuit relies on the inverted back-to-back connection of active devices to implement the basic gyrator behaviour. The transconductance sources are done with two transistors, an NMOS (M0) and a PMOS (M1), connected as it is shown in figure2a. Transistors M2 bias M0 and M1 in the saturation region. The capacitor (C) is achieved by means of the gate capacitance of another NMOS transistor[START_REF] Lechuga | In Built-in Sensor based on Current Supply High-Frequency Behaviour[END_REF].A prototype, without the window comparator, has been fabricated with the Austria MicroSystem (AMS) 0.6 µm technology to characterise the frequency response of the circuit. The chip photograph can be seen in figure2b.Figure3displays the experimental measurements of the circuit tranresistance (v OUT vs. i IN ). The left graph shows a good agreement among the theoretical calculus using the small signal model of the circuit, the layout simulation with the AMS 0.6µm technological transistor models and the data measured from a fabricated chip.The circuit behaviour emulates an inductance with one series and one parallel stray resistor, where the BICS sensitivity to the high frequency components of the current can be appreciated in the abrupt change of the circuit output voltage (lower graph of figure3b) when a current pulse is injected at the BICS input (upper graph of figure3b). The quiescent change of the voltage, after the current stabilization, is smaller and it is given by the low frequency impedance of the circuit.

Fig. 3 .

 3 Fig. 3. BICS tranimpedance measure: (a) frequency and (b) transient responses.

Fig. 4 .

 4 Fig. 4. Catastrophic transistor fault model.

Fig. 5 .

 5 Fig. 5. Fault coverage of the digital logic and the operational amplifier.

Figure 5

 5 Figure 5 shows the fault coverage obtained in the test evaluation. The detected faults are classified according to their type (shorts, opens, GOS and passive components) and the detection methodology applied. Our dynamic current test approach is shown in the left hand columns (I DDX ) and the reference structural tests in the right ones. Quiescent current (I DDQ ) and voltage test (Voltage) for the digital logic together with the operational amplifier DC output voltage (Op. Amp. DC output). It can be appreciated a larger fault coverage from the I DDX method. The reason is that some faults are detected through the change in the duration of the transient current in spite of not modifying the quiescent current or the DC voltage of the CUT (I DDQ or DC Voltage) [8][9].

Fig. 6 .

 6 Fig. 6. Digital logic and BICS (a) chip photograph and (b) measured waveforms.

Fig. 7 .

 7 Fig. 7. Operational amplifier with injected faults (a) schematic and (b) chip photograph.

Fig. 8 .

 8 Fig. 8. Measured waveforms of the CUT and BICS output.

Table 1 .

 1 Montecarlo simulation of the pulse width of the BICS output.

	BICS Output	Typical value	Mean value	Standard deviation
	Fault free	2.67 us	3.28 us	1.46 us
	F1	18.85 us	15.86 us	5.82 us
	F2	13.29 us	12.58 us	2.61 us
	F3	19.84 us	19.66 us	0.81 us

Acknowledgments. This work was funded by the Project TEC2007-65588/MIC and by the Franco-Spanish Integrated Action "Integrated test of high-speed operation data converters" (2007)(2008).


Yolanda Lechuga
email: yolanda.lechuga@unican.es

Mar Martínez Roman Mozuelos
email: roman.mozuelos@unican.es

Salvador Bracho
email: salvador.bracho@unican.es

Structural DfT Strategy for High-Speed ADCs

Keywords: Folding and interpolated A/D converters, Design-for-Test, Circuit simulation, Behavioral modeling, Simulink environment

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

Introduction

Nowadays, the analogue-to-digital converter is a common block in mixed-mode circuits. Embedded ADCs are used in a wide range of applications such as satellite receivers, new generation DVD players, interfaces with storage elements such as computer hard-disks, or the emerging ultra-wide band radio technology. These converters demand high performance to be suitable for the digital telecommunication market, which requires low linearity errors, high speed and low power consumption (battery-powered devices). Low-power performance leads to explore other suitable architectures featuring low-to-moderate resolution in addition to the flash ADC topology. Folding and interpolating techniques are proposed [START_REF] Pan | Signal folding in A/D converters[END_REF][START_REF] Nauta | A 70-MS/s 110-mW 8-bit CMOS folding and interpolation A/D converter[END_REF][START_REF] Venes | An 80-MHz, 80-mW, 8-b CMOS folding A/D converter with distributed track-and-hold preprocessing[END_REF] as this type of ADC has the advantage of small number of comparators and chip area while the operating speed is the same that of the flash type.

To better explore the design options, and to preliminary evaluate any test approach, it is advisable to perform an analysis at the system behavioural level before starting at transistor level [START_REF] Maloberti | Behavioral modeling and simulation of data converters[END_REF]. Behavioural simulators work much faster and it is possible to use the electrical design parameters (gain, bandwidth, offset, parasitic elements) for building the behavioural model; in order to estimate the effects of the injected faults on the specifications of the data converter. In that sense, a system implementation on the MATLAB/SIMULINK environment provides a significant number of advantages.

Traditionally, ADCs are characterized through a specification test, based on a parameter characterization that requires expensive instruments to accurately measure analog signals [START_REF] Huertas | Test and Design-for-Testability in Mixed-Signal Integrated Circuits[END_REF]. To overcome problems related to functional testing, different BIST (Built-in Self Test) techniques have been proposed. They use internally generated or analyzed signals to translate on-chip the methods used in the functional tests [START_REF] Arabi | BIST for D/A and A/D converters[END_REF][START_REF] Frisch | HABIST: histogram-based analog built in self test[END_REF][START_REF] Azais | Implementation of a Linear Histogram BIST for ADCs. Design Automation and Test in Europe[END_REF][START_REF] Huertas | Oscillation-Based Test in Mixed-Signal Circuits[END_REF].

The use of structural fault-model testing has been recognized as a promising alternative or addition to specification testing [START_REF] Zjajo | A quasi-static approach for detection and simulation of parametric faults in analog and mixed-signal circuits[END_REF]. Some Design-for-Test (DfT) techniques do not attempt to extract the ADC performances to identify the defective circuits, but use a fault model to describe the electrical faulty behavior of a real defect. Therefore the effectiveness of the test technique can be estimated by analyzing the fault coverage figure.

This paper is organized as follows: Section II summarizes the original contributions of this work. Section III briefly describes the architecture of the folded and interpolated ADC used as benchmark circuit, as well as the electrical parameters chosen to build its behavioural model. Section IV presents the proposed structural design-for-test method. Section V describes the fault evaluation performed to check the test goodness on the behavioural model, and also on a transistor level implementation of the ADC. The paper finishes in Section VI with the conclusions.

Contribution to Technological Innovation

This work proposes a structural DfT method that monitors some internal test points to extract information about the ADC behaviour. The voltage deviation among these test points is the parameter chosen to infer the presence of a defect in the CUT.

We take advantage of a behavioral description of both the folded and interpolated converter and the design-for-test approach to allow a fast evaluation of the influence of the circuit parameter deviations on the DfT fault coverage and to establish a relationship with the converter performances.

A CAT platform has been used for fault injection and simulation [START_REF] Bounceur | CAT platform for analogue and mixedsignal test evaluation and optimization[END_REF], in order to set the optimum threshold voltage that results in maximum fault coverage. The paper is going to be focused in the fault evaluation process of the DfT approach, including a detailed description of the circuit modules necessaries to implement it.

Folded and Interpolated A/D Converter and Behavioral Model

The folded and interpolated (FI) A/D converter architecture divides the codification process in two steps performed in parallel: a coarse encoder for the most significant bits and a fine subsystem for the least significant bits [START_REF] Pan | Signal folding in A/D converters[END_REF][START_REF] Nauta | A 70-MS/s 110-mW 8-bit CMOS folding and interpolation A/D converter[END_REF][START_REF] Venes | An 80-MHz, 80-mW, 8-b CMOS folding A/D converter with distributed track-and-hold preprocessing[END_REF]. It uses an analog preprocessing in the form of a "folding amplifier" (FB) to significantly reduce the number of comparators required to the fine subsystem with regard to a flash ADC.

The block diagram of a 6-bit folded A/D converter implementation is shown in Fig. 1. This circuit uses a resistive reference ladder to obtain 20 voltage references to feed the preamplifier array. A preamplifier block, senses the difference between the differential input signal (Vip, Vin) and a differential threshold (Vrp, Vrn) to produce a differential signal that later drives the folder blocks. The folded A/D converter uses a distributed implementation of the track-and-hold (S&H) function to ease the synchronization between the coarse and fine bits.

The most popular method of producing folding signals involves the use of coupled differential pairs in the folder circuit. A folding degree of 4 was chosen for our application. An interpolation network, usually made of a string of equal resistors, produces additional folding signals without requiring additional folder blocks allowing the reduction of the ADC complexity and power consumption. It also performs an averaging that reduces the offset requirements of the comparators [START_REF] Venes | An 80-MHz, 80-mW, 8-b CMOS folding A/D converter with distributed track-and-hold preprocessing[END_REF].

The analog coarse preprocessing circuit generates analog versions of the two MSBs. Both are generated by means of combination of the output signals of the S&H stages, so folding is not only used in the fine converter but also in the coarse one.

The differential outputs of the interpolation network and the coarse preprocessing block are digitalized by a set of 18 comparators. Then, the decoder uses the cyclic thermometric code provided by the 16 comparators of the fine converter and the 2 bits of the comparators of the coarse block to encode the 6-bit output and to obtain the overflow and underflow signals.

The converter behavior has been modeled by using the MATLAB/SIMULINK environment. The model allows the inclusion of the main sources of distortion in the converter blocks as a set of parameters to take into account the current-voltage relationship between the circuit inputs and outputs.

Table 1 summarizes the MATLAB/SIMULINK models of the converter blocks with their main high level parameters.

DfT Approach

The proposed method is based on a structural test that provides a digital go/nogo output to be used as interface with a low cost ATE. To diminish the process parameter spread, instead of analyzing the voltage values of the converter internal nodes, we are going to focus on the relative variations that appear among them. The voltage difference between [ ]

) 1 ( ) ( 1 + - = ∆ i V i V V SH SH and [ ] ) 2 ( ) 1 ( 2 + - + = ∆ i V i V V SH SH
is computed by means of a differential difference amplifier (DDA) whose transference function implements [START_REF] Pan | Signal folding in A/D converters[END_REF].

( ) ( ) [ ] ) 2 ( ) 1 ( ) 1 ( ) ( + - + - + - ⋅ = ∆ i V i V i V i V A V SH SH SH SH VDDA out (1)
Where out V ∆ is the output of the DDA, VDDA A is the DDA voltage gain, and

) (i V SH
are the output voltages, either positive or negative, of the S&H block number "i".

In order to simplify the DfT, the circuit is designed to give zero volts at the DDA output for the fault-free ADC. Thus, any deviation at the DDA output above a voltage limit would indicate the presence of a fault in the ADC. This threshold voltage has to be chosen to accommodate the measurement resolution, noise, temperature and process variations. The comparison of the DDA output with the threshold voltage is done by two differential pair comparators (DPC), to detect both positive and negative increments on out V ∆ . The DDA output only will be zero volts if the transfer function of the three preamplifiers connected to the S&H modules is linear. As it happens for a limited range of the ADC input voltage, the DfT uses two additional comparators to discriminate the opportunity window where the DDA has to be evaluated.

The proposed method uses a five signal test bus to connect to the DfT the three signals sampled by the DDA plus the two additional signals needed by the comparators to establish the sampling window (Fig. 2). The digital logic control propagates a start pulse using an own test clock. First, it connects the positive outputs of the S&H number 1, 2 and 3 (V SHP1 -V SHP2 -V SHP3 ) and wait for the window comparators, connected to the positive and negative outputs of the S&H numbers 1 and 2 (V SHP1 -V SHN1 and V SHP2 -V SHN2 ), to detect an ADC input voltage that corresponds with the linear range of preamplifiers 1-3. Then, the control circuit allows the DDA output processing by the DPC to detect the presence of a defect in the ADC. If the differential pair comparators are both zero the control circuit provides another test clock pulse to start the second measurement, and the process is repeated until all the S&H modules are evaluated.

After the S&H outputs, the DfT analyses the 16 differential outputs of the interpolated network. Finally, the DfT is connected to the outputs of the coarse preprocessing blocks. In this module, the positive and negative outputs of each amplifier are connected to two DDA inputs; meanwhile, the third input is tied to a reference voltage.

Test Evaluation Results

The fault evaluation method consists on injecting faults in one of the modules analyzed by the DfT, meanwhile the remaining ones are considered fault-free. First, the positive outputs of the modules and then the negative ones are processed to obtain the digital outputs of the differential pair comparators DPC(>) & DPC(<) (Fig. 2).

Fault simulation analysis has been done with a fast ramp and a sinewave input stimulus comprising, both of them, the limits of the ADC full scale. The sinewave input is used for computing the main specifications of the ADC by traditional functional test routines. For the DfT evaluation (fast ramp as input stimulus) only a few codes have been computed during each input transition. One important advantage of this input vector is that it has no linearity requirements, so it could be easily generated on-chip, to convert the DfT implementation into a full BIST structure.

Behavioral Model

The fault coverage results from the proposed structural DfT are compared to a functional test based in the estimation of the SINAD degradation. Table 2 summarises this fault coverage comparison. The table shows the deviation in each parameter that induces a degradation of three dBs at the converter SINAD and the deviation of the parameter that provokes a voltage at the differential difference amplifier of 100 mV. Some parameters that do not induce a high enough change in the ADC SINAD or in the DfT voltage are labelled by "----" in Table 2.

Table 2. Fault detection on the ADC building blocks of the behavioral model.

ADC Block Model Parameter SINAD DfT

Reference Ladder

∆RREF > 35 % > 20 % Preamplifier ∆RL > 20 % > 5 % ∆βn ---- ---- ∆IBIAS ---- > 20 % BW in f ⋅ < 5 in f ⋅ < 7 Sample & Hold Aperture Time > 5 % of TCLK > 10 % of TCLK Jitter > 2 % of TCLK > 1 % of TCLK Folder Block ∆RL > 5 % > 5 % ∆βn ---- ---- ∆IBIAS > 15 % > 55 % BW in f ⋅ < 7 in f ⋅ < 3 Interpolated Network ∆RINTERP ---- > 300 % Coarse Preprocessing ∆RL > 75 % > 10 % ∆βn ---- > 200 % ∆IBIAS > 250 % > 10 %
The SINAD measurement and the DfT circuit detect some faults easily. For instance, deviations of the nominal value of one resistor of the reference ladder and the interpolating network, deviations in the load resistor of the preamplifiers and folder blocks, the reduction of the bandwidth of one of the folder blocks, or jitter in the sample and hold modules. The other two parameters used in the preamplifier behavioural description, transistor β n and differential pair bias current, I Bias , have a relatively small influence on the converter SINAD because they induce a very small change in the zero crossings of the preamplifier outputs. The DfT can detect deviations on the differential bias current, but not in the transistor β n because the DfT evaluation is restricted to the CUT linear region.

Table 2 also shows that the DfT tolerance to the aperture time is worse than the SINAD limit, due to all S&H switches being affected by aperture time in the same way, effect that the DfT circuit can not detect easily.

Transistor Level Implementation

A transistor level implementation of the FI ADC has been developed using the UMC 0.13µm technology. We have injected catastrophic faults into two critical blocks of this circuit (preamplifiers and folder blocks) to evaluate the optimum threshold limit for the DfT that permits to obtain a fault coverage higher than 99%.

The following catastrophic fault model has been used: Three short faults have been included for each transistor. They interconnect the drain, source and gate terminals with different resistance values. The open source and drain faults are placed in series with the two transistor terminals. As far as the open gate faults is concerned, the fault model used forces the transistor to be open, although floating gate voltage would depend on coupling capacitances with adjacent lines, that influence the electrical behaviour of the defective line [START_REF] Arumí | Experimental Characterization of CMOS Interconnect Open Defects[END_REF]. Since data from the layout are needed to evaluate coupling capacitances, the simulations of open gate faults are planned to be repeated as future work, once circuit layout is finished.

For fault injection and simulation, we have used the Computer-Aided-Test (CAT) platform [START_REF] Bounceur | CAT platform for analogue and mixedsignal test evaluation and optimization[END_REF], integrated in the Cadence Design Framework Environment. It has been developed for the evaluation of test techniques for mixed-signal and RF circuits, and it includes tools for fault simulation, test generation and test optimization.

For the preamplifiers, a total amount of 1,160 catastrophic faults have been simulated (20 times 58 faults per preamplifier), and all of them can be detected by the DfT using a threshold voltage of 100 mV. As far as the open faults is concerned, open drain faults in the differential pair transistors with DC input are more difficult to be detected for the corner preamplifiers (Preamp1 and Preamp20, Fig. 1). In these cases the DfT can detect open faults with an equivalent resistance higher than 40kΩ, whereas, for the rest of open drain and source faults, a threshold voltage of 100 mV is enough to detect faults with an equivalent resistance higher than 10kΩ.

For the folder blocks, 496 catastrophic faults have been simulated (4 times 124 faults per folder block). In this case, all the short and open faults injected in the middle folder blocks (FB2 and FB3, Fig. 1) can be detected using a threshold voltage of 100 mV. For the corner folder blocks (FB1 and FB4, Fig. 1), four DS shorts, four open drain faults, four open source faults and two open gate faults cannot be detected. For these undetectable faults DDA outputs are very close to the 100 mV threshold voltage, thus, probably they could be detected by increasing DDA gain.

In summary, we have obtained an overall fault coverage of 99.15% using a threshold voltage of 100mV. And this fault coverage could even be enhanced, if needed, for the analysis of other ADC blocks, by simply modifying the DDA gain.

Conclusions and Further Work

This paper presents a DfT approach for folding and interpolated ADCs. It analyses internal ADC nodes to compare relative deviations among them and, thus, the defects on the CUT can be detected.

A behavioral modeling of the ADC and the DfT has been done in MATLAB/SIMULINK to facilitate the analysis of the proposed test approach.

The detection threshold level to be used by the DfT to considerer a circuit defective is established by means a fault simulation using a CAT platform.

The proposed approach is intended for embedded modules, it also lowers the test time as only a few ADC samples are necessary for the DfT. However as a structural test, it does not provide information about the ADC performances.

As future work, we plan to check the ability of the DfT to detect simulated GOS (Gate Oxide Shorts) and parametric faults in all the ADC blocks, as well as experimentally on a prototype, where it will be necessary to establish the DfT circuit impact on the ADC performance. Finally, it is interesting to study how to complement this test strategy with other methods based on digital or supply current measurements, in order to increase fault coverage by including faults inside the comparators.

Fig. 1 .

 1 Fig. 1. Block diagram of the folded A/D converter.

Fig. 2 .

 2 Fig. 2. Simplified scheme of the proposed Design-for-Test structure.

Table 1 .

 1 High-level parameters for the FI ADC blocks.

	ADC Block	Parameter
	Reference Ladder	Nominal resistance value, Sigma variance
	Preamplifier	Transistor transconductance, Bias current
		Load resistor, Bandwidth
	Sample and Hold	Gain, Offset, Sampling capacitor
		Switch transistor areas, Jitter
		KT/C Noise, Switch transistor conductances
	Folder Block	Transistor transconductance, Bias current
		Load resistor, Bandwidth
	Interpolate Network	Nominal resistance value, Sigma variance
	Coarse ADC	Transistor transconductance, Bias current
		Load resistor, Bandwidth
	Comparator	Offset voltage, Hysteresis
	Digital encoder	Redundancy

Acknowledgments. This work was funded by the Project TEC2007-65588/MIC and by the Franco-Spanish Integrated Action "Integrated test of high-speed operation data converters" (2007)(2008).


Philippe Mahey

Henrique L Luna

come

Decomposition and informational decentralization for the computation of economic equilibrium


Gabriel Scherer
email: gabriel.scherer@gmail.com

Search for Program Structure

Keywords: 1998 ACM Subject Classification F.3.3.4 Type structure, F.4.1.2 Lambda calculus and related systems, F.4.1.8 Proof theory programs proofs focusing canonicity Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23 1

The community of programming language research loves the Curry-Howard correspondence between proofs and programs. Cut-elimination as computation, theorems for free, call/cc as excluded middle, dependently typed languages as proof assistants, etc.

Yet we have, for all these years, missed an obvious observation: "the structure of programs corresponds to the structure of proof search". For pure programs and intuitionistic logic, more is known about the latter than the former. We think we know what programs are, but logicians know better!

To motivate the study of proof search for program structure, we retrace recent research on applying focusing to study the canonical structure of simply-typed λ-terms. We then motivate the open problem of extending canonical forms to support richer type systems, such as polymorphism, by discussing a few enticing applications of more canonical program representations.

Introduction

Canonical representations for arithmetic expressions in one variable

To introduce the idea of canonical representation of programs, let us start with an example in a simpler domain, simple arithmetic expressions over one fixed variable x. Suppose we are interested in the meaning of expressions, where the meaning of a is taken to be the evaluation function that takes in input the value of the variable x and returns the value of a with this parameter choice. You may think of inputs and outputs as natural numbers -or elements of a given ring.

Our presentation of expressions above has some nice properties, in particular it makes it obvious that the set of expressions is closed over addition and multiplication; it is easy to compose expressions from smaller expressions. But it also admits pairs of expressions that are syntactically distinct but have the same meaning, such as 2 + 2 and 4, or (a + b) × c and a × c + b × c. We call these pairs redundancies.

There exists another common representation of these expressions: by applying simplification rules that preserve meaning, we can turn such expression a into a polynomial such as, for example, 2x 3 + 4x -1, which can be described formally as either 0 or a non-empty sum 0 k d c k x k of monomials of the form c k x k with c k ∈ Z and c d = 0, for a natural number d called the degree of the polynomial.

We see our arithmetic expressions and the polynomials as two different representations of the same sort of objects -their meanings as evaluation functions. Polynomials, as a © Gabriel Scherer; licensed under Creative Commons License CC-BY 42nd Conference on Very Important Topics (CVIT 2016). Editors: John Q. Open and Joan R. Acces; Article No. 23; Leibniz International Proceedings in Informatics Schloss Dagstuhl -Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

Search for Program Structure syntactic representation, have less redundancies than our expressions: 2 + 2 and 4 are distinct expressions, but they are represented by the same polynomial 4x 0 . When a representation has less redundancies than another, we say that it is more canonical. In fact, one can easily show that polynomials have no redundancies at all: if two polynomials are syntactically distinct, they have distinct meanings. When a representation has this property, we say that it is canonical.

A more canonical representation has more structure: its definition encodes more of the meaning of the objects being represented. A canonical representation is very rigid, a lot of information about the object is apparent in its syntax, which often makes it easier to operate on it. For example, it is non-obvious whether an arithmetic expression a is constant (for all values of x), while this question can be easily decided for polynomials -it is constant when it is 0 or its degree is 0. In general, polynomials are much more convenient to manipulate for virtually any application, and they are the ubiquitous choice of representation when studying these objects.

Canonical representations of simply-typed λ-terms and its applications.

In this article, we discuss the design and use-cases of canonical representations of programs expressed in typed λ-calculi, which are more complex than arithmetical expression: finding a good notion of canonical representation can already be challenging.

Because canonical representations reveal so much, in their structure, of the meaning or identity of the programs, we should expect them to play a central role in answering many questions about programs. However, until recently theoretical difficulties hampered such practical applications.

In Section 2 (Theory), we present a recent brand of work that brought a much better understanding of canonical forms in the simply-typed case, inspired by ideas from logic and proof theory, in particular focusing and saturation. This inspiration is an instance of the Curry-Howard correspondence between proofs and programs that is different in nature from the its previous use-cases that are familiar to functional programmers, and closer to some formal approaches to logic programming. We then discuss why extending these representations outside the simply-typed systems -to type systems with polymorphism, closer to realistic programming languages or proof assistants -is difficult and interesting future work.

In Section 3 (Practice), we discuss potential applications of canonical representations of typed programs.

Full abstraction, discussed in Section 3.1. Full abstraction, as a formal property of a translation from a source to a target language, requires that the translation preserves the equivalence between source programs. We discuss how having canonical representations on the source gives surprisingly strong full abstraction results; rather than a practical application, this gives new ways to think about full abstraction results and their consequences, by giving a new family of fully-abstract translations that behave in a fairly different ways from those obtained through more typical proof techniques. Equivalence checking, discussed in Section 3.2. Being able to mechanically check for equivalence opens the door to many interesting practical applications, such as automatically verifying that a "refactoring" change indeed preserved the meaning of the program as intended -a somewhat tedious task that human reviewers currently have to performand solving some ambiguity situations or conflicts arising from a "diamond inheritance" situation. Because we know that for general programming language the question of equivalence fatally becomes undecidable, we must be careful to consider applications where "time out" is an acceptable answer.

Program synthesis, studied in Section 3.3. Type-directed program synthesis algorithms try to enumerate all expressions of a certain type until they find one that satisfies certain user-provided conditions, such as input-output pairs or unit tests. More canonical representations eliminate redundancies -two syntactically distinct expressions of the same program behavior -so using them would seem very beneficial for program synthesis, by reducing the search space of program expressions to search. In fact, as we will show, existing work on program synthesis used some simplifications presented as heuristics, that are all instances of the simplifications leading to focusing-based more canonical representations.

On the other hand, canonical representations may also require additional book-keeping, and to a certain point decrease raw efficiency of term enumeration. We propose studying these situations where de-normalization is desirable, starting from canonical representations, rather than studying partial heuristics starting from naive program representations.

Theory

Functional and logic programming

We have lived for too long in a world where logical justifications for programming language research were separated in two disconnected areas: Functional programming, whose computational behavior is given by term reduction, corresponding in logic to cut-elimination or in general elimination of detours in proofs.

Logic programming, whose computational behavior is given by proof search.

It is natural for functional programmers to think about complete proofs that correspond to the program terms they are familiar with. They study relations between proofs or between programs, typically by a reduction relation that expresses computation, and an equivalence relation that expresses indistinguishability.

Curry-Howard then transfers intuition back and forth between program-formers with a computational interpretation and proof -formers with an interpretation as a reasoning principle. Some success stories include relating control operators to classical reasoning principles [START_REF] Griffin | A formulae-as-type notion of control[END_REF], functional-reactive or event-driven programming to linear temporal logic [START_REF] Jeffrey | LTL Types FRP: Linear-time Temporal Logic Propositions as Types, Proofs as Functional Reactive Programs[END_REF][START_REF] Paykin | The Essence of Event-Driven Programming[END_REF], session types to linear logic propositions [START_REF] Caires | Session Types as Intuitionistic Linear Propositions[END_REF], and building proof assistants with convenient computational principles out of advanced dependent type theories (Agda, Coq, LF, PRL...).

Logic programming considers partial proofs -derivations with some unfilled subgoals left to prove -to describe the state of a computation that evolves by proof search [START_REF] Miller | Uniform proofs as a foundation for logic programming[END_REF], either stopping when a complete proof is reached or enumeration all possible completions. Proposition-formers embed certain search principles that give rise to new computational behavior, possibly bound to the choice of well-designed search strategies. Besides proving a rich generalization of Prolog that is pleasing to proof theorists and type theorists alike, success stories include using linear logic to specify concurrent and distributed systems [START_REF] López | Monadic concurrent linear logic programming[END_REF][START_REF] Schack-Nielsen | Celf -A Logical Framework for Deductive and Concurrent Systems (System Description)[END_REF] or to study interactive fiction gameplays and interactive storytelling [START_REF] Martens | Ceptre: A Language for Modeling Generative Interactive Systems[END_REF].

We encourage functional programmers to start caring about proof search as well. When logicians propose a new strategy for proof search in a given logic, it avoids traversing redundant derivations of the same proof. In terms of programming, it removes redundant C V I T 2 0 1 6

23:4

Search for Program Structure expressions of the same program. This lets functional programmers better understand the structure and identity of programs, by suggesting more canonical representations.

Identity in logic and programming

We make a careful distinction between a program, that is a specific behavior that the user has in mind when she implements it in a programming language, and its expression as a specific term in a given system of representation -defined by a syntax, typing rules, etc. A program can have arbitrarily many expressions; we say that two expressions are equivalent if they represent the same program. For example, refactoring is the process of moving from one expression of a program to another, that is judged more amenable to further modification.

In comparison to the arithmetic expressions of Section 1.1, programs (program behaviors) correspond to evaluation functions, and expressions correspond to terms, either in the syntax of simple arithmetic expressions -one choice of representation -or as polynomials -another choice.

Definition 1 (Canonicity). A representation T is more canonical than a representation S if they represent the same programs, and there is a mapping : T → S such that the equivalence classes of T (the maximal sets of expressions of the same program) are mapped by to subsets of the equivalence classes of S. For example, β-normal λ-terms are more canonical than arbitrary λ-terms. A representation T is canonical if each equivalence class is a singleton -all equivalent representations are syntactically equal. For example, if you take a reasonable definition λ-calculus with integers, and restrict yourself to closed terms of type integer, then β-normal forms are canonical.

For programmers there is usually an extremely clear definition of the behavior of an expression, and therefore of what it means for two expressions to be equivalent. It may depend on what they decided to observe -they may, for example, ignore or pay attention to time and memory consumption -but is non-controversial as soon as the observable are agreed upon.

Logicians also make a distinctions between the expression of a formal proof and the mathematical proof it represents, and may consider that two derivations, two formal proofs are "morally the same". But how to define this distinction is not at all obvious: ordinary users of proofs do not consider their behavior, they are merely satisfied that they exist at all and could not care less about their formal identity.

How to explain, then, the following state of affairs? The identity of proofs has been studied for a long time by logicians, who proposed many different means of representing a mathematical proof, meant to better capture its identity, to strive at canonicity: natural deduction, sequent calculus, hypersequents / deep inference, focused sequents, tableaux, connection matrices, proof nets, etc. On the other hand, λ-terms reign as the ubiquitous representations of functional programs and, besides normalization of closed programs, the question of choosing alternative means of expression is rarely considered.

Remark. We propose a tentative explanation -an excuse: canonicity is bad for programming. The choice of a highly non-canonical representation of programs allows programmers rich means of expressions of the same program. Two distinct expressions of the same program may correspond to stylistic difference, or an expression of intent in the way the program being worked on will evolve over time. Non-canonicity may be essential for flexibility, clarity and modularity. This is similar to the fact that human mathematicians do, in fact, use products P × Q of arbitrary polynomials P, Q when it is what they want to express, despite this not within the grammar of polynomials themselves -the product is only a simple arithmetic G. Scherer

23:5

expression, which is simpler to produce. Yet, just as polynomials, if we want to write tools to consume programs, better understanding canonical representations can be essential.

Focusing for canonicity of simply-typed effectful λ-calculus

Focusing is based on the logical notion of invertibility. An inference rule is invertible when applying it during proof search cannot get you stuck: its premises are provable if and only if its conclusion is provable. Consider the logical rules corresponding to construction of functions, pairs and sums:

Γ, A B Γ A → B Γ A 1 Γ A 2 Γ A 1 × A 2 Γ A i Γ A 1 + A 2 i ∈ {1, 2}
The rule for functions and pairs are invertible, but the rule for sum is not: using it means making a choice, and it is possible to get into a dead-end -if you try to prove A 1 but only A 2 was provable. On the side of destructors, the opposite is true: deciding to apply a function may get you in a dead-end if you don't know how to build an argument for it, while eliminating a sum merely considers two possible outcomes, losing no information. Focusing, originally introduced for linear logic in [START_REF] Andreoli | Logic Programming with Focusing Proofs in Linear Logic[END_REF], is a series of conditions on proofs: some proofs are valid focused proofs, and other are not. First, if invertible rules can never get you in a dead-end, you can make them mandatory: focusing forces them to be applied eagerly, as much as possible. Second, once you can only apply non-invertible rules, the user has to select a formula (of the context or the goal), and focused imposes that apply non-invertible rules be applied to it as long as possible. For example, if the goal is (X 1 + X 2 ) + (Y 1 + Y 2 ), focusing demands not only that they make a (non-invertible) choice for the head sum connective, but also choose between one of the X i (or Y i ) by doing a nested sum introduction. As another example, if a function variable f : X → Y → Z is in the context, selecting it means that one has to pass all arguments at once, passing both a X and a Y argument -stopping after applying X to work on another formula would be an invalid focused proof. Intuitively, using this function is only useful to get the final result Z, so it is always possible to either never apply it (if Z is not needed), or delay the application of X until Y is also available. [START_REF] Zeilberger | On the unity of duality[END_REF] proposed to consider focused proofs as a syntax for a programming language, guided by the observation that focusing could justify the dual semantic restrictions on polymorphism in effectful call-by-value and call-by-name languages -this work explains the value restriction for strict intersection types and the context restriction for lazy union types appearing in [START_REF] Dunfield | Tridirectional Typechecking[END_REF], and the explanation was extended to second-order universal and existential polymorphism in [START_REF] Munch-Maccagnoni | Focalisation and Classical Realisability[END_REF].

The idea of invertibility is one way to understand why adding sums make equivalence harder. We say that a type connective is positive if its right introduction rule is non-invertible, and negative otherwise: (→, ×, 1) are negatives, and (+, 0) are positive. It is easy to decide equivalence of the simply-typed λ-calculus with only connectives of one polarity: we previously remarked that it is easy to define canonical forms in the negative fragment STLC(→, ×, 1), but it is equally easy in the positive fragment STLC(+,0). It is only when both polarities are mixed that things become difficult.

A key result of Zeilberger (2009, Separation Theorem, 4.3.14) is that a focusing-based presentation of the simply-typed λ-calculus is canonical in the effectful setting where we assume that function calls may perform side-effects -at least using the specific reduction strategy studied in CBPV (Levy 1999). Two syntactically distinct effectful focused program expressions are observationally distinct -the canonicity proof relies on two distinct error C V I T 2 0 1 6

23:6

Search for Program Structure effects, to distinguish evaluation order, and an integer counter to detect repeated evaluation. The fact that any λ-term can be given a focused form comes from a completeness theorem, the analogous of completeness of focusing as a subset of logical proofs. However, this syntax is not canonical anymore if we consider the stronger equivalences of pure functional programming, where duplicated or discarded computations cannot be observed.

Let us write P , Q for positive types, types that start with a positive head connective, and N , M for negative types, that start with a negative head connective. In a λ-term in focused form with types of both polarities -see a complete description in Scherer (2016, Chapter 10) -a non-invertible phases can be of two forms which we shall now define. It can start with a positive neutral (p : P ), which is a sequence of non-invertible constructors of the form σ i for positive types, they commit to a sequence of risky choice to build the value to return. Or it can start with a negative neutral n[y : N ], that performs a series of function applications n p or pair projections π i n to a variable y : N from the context. Such a negative neutral term, if it is of the type of an atomic goal (n : X), is returned unchanged. If it is of some positive type P , it is bound to a variable name to be decomposed decomposed by the following invertible phase: let (x : P ) = n[y : N ] in . . .. One way to think of these two choices is that positive neutrals (p : P ) build a part of the output value, while negative neutrals n[y : N ] observe a part of the input environment.

Saturation for local canonicity of simply-typed pure λ-calculus

Focusing enforces a form of backward search structure on canonical program representations: the invertible structure of terms is purely determined by the types of the goal and the context. To obtain canonical forms for pure terms, [START_REF] Scherer | Which simple types have a unique inhabitant?[END_REF] had to use intuitions from proof search again, by forcing the non-invertible part of terms to have the structure of a forward search: at the end of each invertible phase, try to saturate the context by making as much observations let (x : P ) = n[y : N ] in . . . as possible, returning a value (x : P ) only when introducing new observations does not teach us anything new. We call terms that follow this discipline saturated terms -for a more detailed explanation of saturation, see Scherer (2016, Chapter 11).

There is no redundancy among saturated terms, but the completeness theorem is weaker than for focusing alone. To have the saturation process terminate, one has to fix in advance a finite set of possible observations for each context. For any such choice, only finitely many λ-terms can be given a saturated normal form -and conversely, for any finite set of λ-terms there exists a saturation strategy that allows to represent them as saturated normal form. This is enough for practical applications -testing whether a type has a unique inhabitant, testing whether two terms are equivalent (two is finitely many) -but still a technical limitation.

Practice

These results on the simply-typed λ-calculus are very encouraging, but they do not provide canonical forms in presence of parametric polymorphism, which gives even stronger equational principles. In other words, canonical forms for practically used programming languages are still out of reach. We argue that building them would give us a much better understanding of what our programs are, and open the door for important applications. 1. Easy ways to build fully abstract translations. 2. Program synthesis.

G. Scherer

23:7

3. Equivalence procedures.

Full abstraction

A translation from one program representation to another, a compiler for example, is said to be fully abstract 1 if two programs are observationally equivalent if and only if their translations are observationally equivalent.

Full abstraction is a strong property that gives a lot of information of a compilation process: it tells us that any equational reasoning at the source level remain valid at the target level. One can think of it as a usability property (knowing the source language is enough) or a security property (the compiler protects programs from being separated by attacks at the target level)

As a result of its strength, it is a difficult property to establish : many translations that we intuitively believe are fully-abstract have only been proved so very recently, or are not known to be. For example, fully-abstract translations from the simply-typed λ-calculus to the untyped λ-calculus or from the simply-typed λ-calculus (with recursive types) to System F were only established in 2016 [START_REF] Devriese | Fully abstract compilation by approximate back-translation[END_REF][START_REF] New | Fully Abstract Compilation via Universal Embedding[END_REF], and type-erasing fully-abstract translations from System F are an open problem. Yet we can, with apparent ease, provide you with very strong results.

Theorem 2 (Full abstraction for free!). Take any finite subset S of the pure simply-typed λ-calculus with functions, pairs, sums and units. Take any system T in which any λ-term can be embedded: the untyped λ-calculus, System F, impure System F with references and call/cc, the Calculus of Constructions... There is a fully-abstract translation from S to T .

Proof. For any pure λ-term e in S, let us define s its canonical form as defined in [START_REF] Scherer | Which types have a unique inhabitant?[END_REF], seen as a λ-term. We assumed that the λ-calculus embeds into T . We translate s into the embedding of s .

By definition of canonicity, if two terms s, t are observationally equivalent, then s and t are syntactically equal, and in particular their embedding in T is the same program. In other words, this translation is fully abstract. This result is a bit puzzling 2 . For example, we are not requiring the type A → B of pure functions in the pure simply-typed λ-calculus to be translated in T into a type of pure functions: the embedding into ML with non-termination and references, for example, would return a term at the type of ML impure functions. Yet the translation is fully-abstract.

Full-abstraction proofs are delicate because they are often built on the ability to backtranslate contexts of the target language into the source language -completely or approximately. The proof technique established in Devriese, Patrignani, and Piessens ( 2016) might be able to back-translate contexts of the calculus of (inductive) construction, but it sounds like a daunting amount of work. Instead, we paid the cost of coming up with canonical representations in the first place; once you have them for your source language, you get fully-abstract translations for free! 1 Full abstraction was originally introduced as a quality criterion for denotational semantics instead of syntactic program translation. We mention this is Section 4.2 (Game semantics). 2 Note that it is not an immediate consequence of strong normalization for the simply-typed λ-calculus, otherwise it would extend to System F as well.

C V I T 2 0 1 6

23:8

Search for Program Structure

Equivalence procedures

Canonical representations also give procedures to decide equivalence for a programming language: to check whether two representations are equivalent, one can check whether their canonical forms are syntactically equal. Conversely, it is often -but not always -the case that equivalence procedures can be read back as a way to describe canonical forms for a language.

We know surprisingly little about deciding program equivalence. Equivalence in presence of non-empty sum types has remained an advanced, somewhat active research topic since it was proved decidable in [START_REF] Ghani | Beta-Eta Equality for Coproducts[END_REF], and equivalence in presence of the empty type (zero-ary sums) was decided only recently (Scherer 2017). We know that observational equivalence for System F is undecidable, but while the (equally undecidable) problem of type inference has been actively studied since at least [START_REF] Pfenning | Partial polymorphic type inference and higher-order unification[END_REF], we know of no research on equivalence algorithms for polymorphic calculi. 3 Similarly, an impressive amount of effort has been invested in automatically checking that an implementation respects a specification (despite the undecidability barriers), but almost none went into automatic checking of implementation equivalence -as if this question jumped straight from automata to process calculi, without ever touching functional programs.

We hope that studying proof search and canonical representations in presence of polymorphism will stimulate work on semi-decidable equivalence algorithms for powerful type systems. The applications of equivalence procedures are everywhere, and we will mention some of them: 1. Robust equivalence checking opens the door to automatic verification of refactoring code transformations. Refactoring edits are typically designed to be easily reviewable by human programmers, so they should be within reach of an equivalence algorithm, even if it is very incomplete. Note that this very quickly involves the tricky equivalence of sums: moving a condition test earlier or later in a program is an instance of β-expansion on booleans (a sum type). 2. ML module systems have generative and applicative functors, the later being characterized by the fact that two independent applications of the same functor to the same parameter return compatible modules. This means that two independent libraries that made the same instantiation choice are compatible, instead of having to be modified to depend on a common functor applications. However, equality of module parameters, "static equivalence", is implemented in a very syntactic and restrictive way, essentially requiring that both independent libraries refer to a shared definition of the parameter. To liberate independent libraries, we should let each define their parameter, and check that they are equivalent.

The question of equivalence is also underlying the problem of coherence of implicit

elaboration mechanisms such as type-classes and implicits. To remain predictable, language designs try to guarantee that each implicit elaboration problem has a unique solution across the user code -either by imposing somewhat ad-hoc priority/ordering restrictions or by imposing non-modular conditions, such as imposing all implicit instances to be declared at the toplevel. If we had reliable equivalence checking, we could for example allow local declarations under the condition that local instances remain coherent with outer instances -checking equivalence for all pairs of elaboration chains for the same G. Scherer

23:9

instance -or automatically determine which global instances need to be locally disabled to preserve coherence. 4. In general equivalence checking is the proper design tool to handle "diamond inheritance" situations. If a declaration inherits from two classes exporting the same method definition, existing languages either impose an arbitrary choice, or fail, or require a renaming; renaming is correct, but cumbersome in the common case where both definitions are equivalent -sometimes in non-trivial ways. This is common for example when modeling mathematical hierarchies: a finite monoid is both a monoid and a finite set, which both exports (non-conflicting) definitions of a carrier set.

Program synthesis

In [START_REF] Scherer | Which simple types have a unique inhabitant?[END_REF] we used canonical forms for the simply-typed λ-calculus to answer the following question: when it is the case that a given type has a unique inhabitant modulo program equivalence? This unicity situation is a perfect opportunity for program synthesis, as the code that programmer would have in mind is completely determined by the type information flowing from the context. We presented some interesting examples (unique inhabitants at non-trivial types of lens operators), but of course unicity rarely happens in common programs today, only in highly polymorphic library functions, or code written with rich dependent types [START_REF] Scherer | Mining opportunities for unique inhabitants in dependent programs[END_REF]).

More practical-minded work on type-directed program synthesis, such as the recent works of [START_REF] Osera | Type-and-Example-Directed Program Synthesis[END_REF], [START_REF] Frankle | Exampledirected synthesis: a type-theoretic interpretation[END_REF], and [START_REF] Polikarpova | Program synthesis from polymorphic refinement types[END_REF], proceeds by enumerating arbitrary many programs at a given type, looking for one that satisfies a user-provided specification -expressed as a set of input-output examples, or a refinement type. Even if the specifications can be woven inside the search procedure to reduce the search space, there is still a combinatorial explosion in the number of synthesized AST nodes that makes scaling to rich programs extremely challenging.

By reducing the redundancy among the programs of a given size, canonical forms provide order-of-magnitude 4 reduction in search space. In fact, many of the experimentally-motivated space reduction heuristics proposed in [START_REF] Osera | Type-and-Example-Directed Program Synthesis[END_REF] are subsumed by focusing.

We propose three ways in which the study of canonical forms could interact and enrich future research on type-directed functional program synthesis: 1. We believe that instead of starting from a λ-term enumeration and carving out to reduce the search space, synthesis algorithms could be usefully expressed as directly from the search procedure for canonical forms -if they are known for the type system at handor the most-canonical representation known. 2. On the other hand, sometimes strong canonicity imposes some bookkeeping that can actually degrade search performance -Frankle, [START_REF] Frankle | Exampledirected synthesis: a type-theoretic interpretation[END_REF] reports that sometimes they willingly avoid η-expansion to reduce term size. Syntactic descriptions of "weakly" focused programs that do not impose full deep inversion has been proposed (Munch-Maccagnoni 2013), but we need to build empirical and theoretical understanding of when and why de-canonicalization is useful for synthesis. 3. Finally, synthesis algorithms today mix techniques that are easily explained by the proof search-inspired point of view we promote in the present article, and others, such as the predicate interpolation used in [START_REF] Polikarpova | Program synthesis from polymorphic refinement types[END_REF], that are not 4 The order-of-magnitude claim comes from [START_REF] Frankle | Exampledirected synthesis: a type-theoretic interpretation[END_REF].

C V I T 2 0 1 6

23:10

Search for Program Structure justified in these terms. It would be interesting to find justifications for them in purely logical terms -as logicians have historically have been able to do for various aspects of logic programming, such as forward vs. backward-search [START_REF] Chaudhuri | A Logical Characterization of Forward and Backward Chaining in the Inverse Method[END_REF] or magic sets [START_REF] Chaudhuri | Magically Constraining the Inverse Method Using Dynamic Polarity Assignment[END_REF].

4 Advanced topics

Full abstraction seen differently

In Theorem 2 (Full abstraction for free!) we demonstrated that knowing a canonical representation for a source language lets us build fully-abstract translation to many different target languages with almost no assumption of those targets.

To be clear, we do not currently expect this approach to scale to the realistic languages we are interested to get fully-abstract compilers and translations for, because of the decidability barrier for canonical representations. Getting a more canonical representation is useful for the applications mentioned so far, but this approach to full abstraction requires fully canonical representations, and may therefore remain restricted to idealized languages. Nonetheless, in the rest of this section, we explore what we can learn about full abstraction from this extreme setting.

This full-abstraction argument is interesting because it gives a concrete example of the general idea that full-abstraction results from a source to a target language need not be built on back-translation techniques. Most of the known full-abstraction results rely on the ability to back-translate some parts of target terms and contexts -for example those whose type is the translation, in the target type system, of a source type -to the point where practitioners would sometimes conflate full-abstraction with the ability to back-translate. We demonstrate that knowing more about the source equivalence lets you work less on the relation between the source and target languages.

Full abstraction is also often seen as a security property, and considering our proof technique in this light is interesting. If we consider distinguishing two terms as an "attack", the statement of full abstraction says that the translation protects the source terms of any additional distinguishing power (attacks) in the target language; this may be achieved by having the compiler insert some sort of "protective wrapper" around the translated terms, to disable the more low-level (malicious?) features of the target language -see [START_REF] Fournet | Fully Abstract Compilation to JavaScript[END_REF] for example.

In our canonicity-based full abstraction result, there is no protective layer (neither static or dynamic) around the terms. Instead of disabling the observation features of the target language, we make sure that each source term will behave as all others equivalent terms under any additional observation from the target.

For example, consider the type (X → Y ) → X → Y → Y in the pure simply-typed λcalculus and its two inhabitants λf x y. f x and λf x y. y. To get a fully-abstract translation into a target calculus with side-effects such as input-output, one would typically wrap the two terms into a protective barrier that prevents using side-effects to tell if the f argument is used or not -in this example, the two terms are not equivalent, so they will remain distinguishable, but the protective barrier would be used in any case. This protection could be static, using a type of pure functions in the target language to forbid effects in f , or dynamic, using some kind of IO mocking/reification to block external observers from seeing writes. In our translation, no such protection is used; instead, saturation transforms both terms, in the source language (before translation), into terms of the form λf x y. let y = f x in . . ., where the . . . are y for the first program and y for the second. No protective wrapping is necessary anymore: bad f -observing side-effects will make the same observation on both normal forms.

Finally, one may wonder about the efficiency impact of the normalization into a canonical form -in particular the saturation. At the source type (X → Y ) → X → Y → Y in the example above, we turned λf x y. y into λf x y. let y = f x in y, introducing an apparently useless computation. In the general case, many such observations of the context may be introduced by saturation -how much depends on the finite set of terms that delimits the observable horizon. However, notice that this price needs only be paid if the function type X → Y is translated into a type of impure functions in the target. If it is translated to a pure function type, then the unused binding let y = f x can be removed after embedding in the target language. In general, saturation may introduce many additional observations, but only the ones that are required for full abstraction to hold need to be preserved; simple type-directed target simplification strategies may be able to convert back to target programs much closer to what non-canonicity-based fully-abstract compiler would produce.

Game semantics

Some readers may wonder about a relation between canonicity of syntactic representations that we propose to discover using focusing, and the full abstraction property of some denotational semantics obtained through game semantics. The comparison is as follows.

Game semantics provide a way to describe programs as games or, more precisely, strategies (as mathematical objects in a denotational semantics, but they could be given a concrete syntax), that allow to express an extremely broad scope of computational behaviors. In particular, two distinct such objects are distinct behaviors (there is no redundancy), but in general a lot of those objects do not correspond to interpretations any program of the language you are starting with: they may exhibit various kind of non-determinism, state, demand sensitivity, all sorts of weird things. Then you progressively carve out subsets of those objects that have nice behavioral properties (for example, innocent strategies), ruling out the strangest behaviors. If you do this enough, you can manage to remove all the non-standard stuff, and the remaining objects are exactly the programs of your language: you have a fully-abstract model.

The path to canonical forms goes in the opposite direction. We start with a syntax that, obviously, contains only expressions of the programs of our language, but a lot of these expressions may describe the same behavior. Then we carve out redundant expressions by proposing more and more canonical representations. If we do this enough, we can manage to remove all the redundancy, and the remaining expressions are exactly the programs of our language: we have a canonical representation.

In the best case, a language is so well-understood that both processes have reached completion: we have canonical representations and fully abstract denotations of it that are in one-to-one correspondence. This has been worked out for propositional linear logic in [START_REF] Laurent | Syntax vs. Semantics: a polarized approach[END_REF].

Conclusion

Syntax is a powerful tool to study and manipulate program behavior, and we emphasize the problem of finding more canonical syntactic representations of our program, that have less redundancy and are thus closer to a canonical description of their behavior. We claim that this research programme can take heavy inspiration from proof-theoretic results and methods to study the structure of proof search, extending a new arm of the C V I T 2 0 1 6

23:12

Search for Program Structure

Curry-Howard correspondence.

Recent results have already been obtained for simply-typed systems, giving precise descriptions of normal forms for both effectful and pure λ-calculi. The extension to parametric polymorphism, and other advanced type systems (dependent types...) is an open problem that you should consider working on! Powerful type systems, with their stronger equational reasoning principles, should not only make programming more expressive and safer, they should make it easier. We need better programming tools for that to happen, and hopefully more canonical representations are one way to make this happen. seemed to require inversion principles based on pattern-matching to be built into the typing rules. It took a few more steps to get to focusing. Here's a followup mail I wrote to Robert Harper on June 1 2006: I think I understand what you were getting at earlier -would you find it more acceptable to speak of call-by-value vs call-by-name connectives? Or maybe strict vs lazy connectives? Part of what this work is about is that we have to treat (for example) strict product and lazy product as different logical connectives, with different introduction and elimination rules. You can pattern-match against values of "strict type", and pattern-match against *covalues* of "lazy type". If you are familiar with the idea of focusing, strict (aka "positive") connectives are synchronous on the right and asynchronous on the left, whereas lazy (aka "negative") connectives are synchronous on the left and asynchronous on the right.

[...] It may not be necessary to segregate distinct "call-by-value" and "call-by-name" type systems as I did in the version of the paper you have, and instead just take their union as a system mixing strict and lazy connectives -I haven't worked that out.

  expression a, b ::= n ∈ N | a + b | a -b | a × b | x

One notable exception is the work of[START_REF] Bernardy | Testing Polymorphic Properties[END_REF] on polymorphic testing, which is secretly about program equivalence.

Acknowledgments

Amal Ahmed led an extremely stimulating discussion on the nature and limitation of the full abstraction results provided by factorization through canonical forms in Theorem 2, which we tried to summarize in Section 4.1 (Full abstraction seen differently). Thanks also to Guillaume Munch-Maccagnoni and Frédéric Bour for their comments.

This research was supported in part by the National Science Foundation (grant CCF-1422133).

A

Appendix: Noam's history of focusing Noam Zeilberger's work contains, expressed very clearly, the result that focusing gives a canonical term language for effectful programs - Zeilberger (2009, Separation Theorem, 4.3.14). Interestingly, this aspect is not emphasized in the general work, not is the connection to logic programming (despite the direct connection to Frank Pfenning's work), and the formulation in terms of a Curry-Howard correspondence between term canonicity and proof search is not to be found in his thesis -it seems to be a contribution of the present article. We tried to guess how Noam Zeilberger ended up working with focusing and its applications to functional programming problems. We assumed that familiarity with focusing came first from the literature on logic programming, and applications to the simply-typed λ-calculus came only later. We asked him, and it turns out we were completely wrong. Most of his reply, lightly edited, is quoted below:

The original reason I started thinking about evaluation order and patternmatching was actually to understand intersection and union types. I was intrigued by the paper on "Tridirectional typechecking" by Joshua Dunfield and Frank [START_REF] Dunfield | Tridirectional Typechecking[END_REF], where they showed that the union-elimination rule requires an "evaluation context restriction" in the presence of effects, dual to the value restriction on intersection-introduction which Rowan Davies and Frank had found was necessary for CBV+effects ("Intersection types and computational effects", [START_REF] Davies | Intersection types and computational effects[END_REF]. I was not completely satisfied with the treatment of subtyping in these papers, though. Rowan and Frank's paper explained that the subtyping distributivity law

from classical intersection type systems is unsound for CBV+effects, while Joshua and Frank's paper showed that the dual rule for unions

is unsound for CBN+effects (they didn't mention this explicitly, but it can be deduced from their examples showing the necessity of an evaluation context restriction on union-elimination). The solution in both papers was to simply drop these principles (1) and ( 2), but it's a fact that (1) is sound for CBN even in the presence of effects, while (2) is sound for CBV+effects. What I noticed (which really is kind of folklore) was that it's possible to reduce these questions of subtyping to typing by taking an "identity coercion" interpretation of subtyping. For example, it is possible to "derive" principle (1) by typing the eta-expansion of a function variable:

The point is that the corresponding typing derivation goes away if we place a value restriction on intersection-introduction, because the subexpression f(x) is not a value. My hypothesis was that it should derive all of the subtyping laws which are sound for a given evaluation order by typing the appropriate identity coercion, but this places constraints on the design of the type system, that the typing rules be "sufficiently complete". In particular, subtyping rules such as