# An accurate-by-construction conversion from lambda calculus to combinatory logic | Journal of Practical Programming

*by*Phil Tadros

## 1 Introduction

The correspondence between Curry’s type-free lambda calculus and Schönfinkel’s combinatory algebras is among the many oldest identified and essentially the most aesthetically pleasing information concerning the lambda calculus.Peter Selinger, The lambda calculus is algebraic, Journal of Practical Programming, 12(6), 549–566.

This paper explores the connection between the lambda calculus and combinatory logic (Schönfinkel, Reference Schönfinkel1924; Curry *et al.*, Reference Curry, Feys, Craig, Hindley and Seldin1958). The phrases of the lambda calculus are outlined by the next grammar:

[M ; ::= ; x ; mid ; M , M ; mid ; lambda x . M]

Evaluating and manipulating lambda phrases require a cautious remedy of variable binding. Combinatory logic, alternatively, is a language with out variable binding:

[T ; ::= ; x ; mid ; T , T ; mid ; mathsf{S} ; mid ; mathsf{K} ; mid ; mathsf{I}]

Right here, lambda abstractions have been changed by three *combinators*:

${textsf{S}}$

,

${textsf{Okay}}$

, and

${textsf{I}}$

. Every combinator has its personal discount behaviour, given by the next rewrite guidelines:

start{align*} mathsf{S} ; f ; g ; x & to (f ; x) ; (g ; x) mathsf{Okay} ; x ; y & to x mathsf{I} ; x & to xend{align*}

It’s not so exhausting to outline a translation from combinatory logic to lambda phrases that preserves discount behaviour. The next three lambda phrases correspond to the combinators

${textsf{S}}$

,

${textsf{Okay}}$

, and

${textsf{I,}}$

respectively.

start{align*} lambda f ; g ; x , & . , (f ; x) ; (g ; x) lambda x ; y , & . , x lambda x , & . , xend{align*}

Apparently, there’s additionally a translation within the different course, from lambda phrases to combinatory logic. The important thing ingredient on this translation scheme is named *bracket abstraction* or *combinatory abstraction*. Given a variable *x* and time period in combinatory logic *t*, we will outline the time period

$Lambda ; x ; . ; t$

by the use of the next three circumstances:

start{align*}Lambda ; x ; .; x & = mathsf{I} Lambda ; x ; . ; t & = mathsf{Okay} t quad textual content{if $textit{x}$ doesn’t happen freely in $textit{t}$} Lambda ; x ; . ; (t_1 ; t_2) & = mathsf{S} (Lambda ; x ; . ; t_1) ; (Lambda ; x ; .; t_2)finish{align*}

As its identify suggests, the time period in combinatory logic computed on this vogue simulates the discount behaviour of a lambda abstraction in combinatory logic.

These translations are usually outlined on untyped lambda phrases. On this pearl, we strive a special tack and discover easy methods to show that the interpretation from the merely typed lambda calculus to combinatory logic preserves each varieties and semantics. This isn’t a brand new outcome, however slightly than show these properties publish hoc, we guarantee the interpretation is right by building utilizing the dependently typed programming language Agda (Norell, Reference Norell2007).

## 2 Lambda calculus

To set the scene, we begin by defining an evaluator for the merely typed lambda calculus. This evaluator options in quite a few papers and introductions on programming with dependent varieties (McBride, Reference McBride2004; Norell, Reference Norell2009, Reference Norell2013; Abel, Reference Abel2016), but we embody it right here in its entirety for the sake of completeness.

### Phrases

Earlier than we outline the *phrases* of the merely typed lambda calculus, we have to resolve on easy methods to deal with variables. We start by defining the next inductive household, modelling legitimate references to a kind

${{sigma}}$

in a given context

${{Gamma}}$

:

Erasing the kind indices, we’re left with the Peano pure numbers – equivalent to the standard De Bruijn illustration of variable binding.

We are able to now outline the datatype for well-typed, well-scoped lambda phrases as follows:

Every constructor mirrors a well-recognized typing rule: purposes require the perform’s area and argument’s kind to coincide; lambda abstractions introduce a brand new variable within the context of the lambda’s physique; the

${textsf{var}}$

constructor could also be used to discuss with any variable that’s at present in scope.

## 3 Translation to combinatory logic

Earlier than we will outline the interpretation from lambda phrases to combinators, we have to repair our goal language. As a primary try, we’d strive one thing alongside the next traces, turning the grammar from the introduction into an Agda datatype:

But if we goal for our translation to be type-preserving, the very least we will do is embellish our combinators with the identical kind info as our lambda phrases:

The kinds of each the

${textsf{app}}$

and

${textsf{var}}$

constructors are the identical as we noticed for the lambda phrases. The kinds of the primitive combinators are decided by their desired discount behaviour. Observe that – as our

${textsf{Comb}}$

lacks lambdas and can’t introduce new variables – the context is now a *parameter* slightly than an *index* as we noticed for the

${textsf{Time period}}$

datatype. That is the essence of combinatory logic: a language with variables however with out binders.

But we’ll attempt to do even higher. We’ll outline a translation that preserves each the categories and *dynamic semantics* of our lambda phrases. To realize this, we index our combinators with *each* their varieties and their supposed semantics, given by a perform of kind

${textsf{Env};Gamma;to ;textsf{Val};textsf{u}}$

. This may allow us to outline a translation from a lambda time period to a time period in combinatory logic that has the identical semantics as its enter lambda time period. This yields the ultimate model of our datatype for combinatory logic:

Right here the kind of every base combinator (

${textsf{S}}$

,

${textsf{Okay}}$

, and

${textsf{I}}$

) incorporates each its kind and semantics. For instance, the

${textsf{I}}$

combinator has kind

${{sigma};Rightarrow;sigma}$

and corresponds to the lambda time period

${lambda;textsf{x};rightarrow;textsf{x}}$

. Not one of the combinators depend on the extra surroundings parameter

${textsf{env}}$

. This surroundings is used within the

${textsf{var}}$

constructor; simply as we noticed in our evaluator for lambda phrases, this surroundings shops a price for every variable. Lastly, the

${textsf{app}}$

constructor applies one combinator time period to a different. The sort info for each the

${textsf{var}}$

and

${textsf{app}}$

constructors coincides with their counterparts from the

${textsf{Time period}}$

knowledge kind; their supposed semantics could be learn off from the evaluator for lambda phrases, , that we outlined beforehand.

The important thing distinction between lambda phrases and SKI combinators is the shortage of lambdas within the latter. To deal with the *bracket abstraction* translation from the introduction, we outline the

${textsf{abs}}$

perform that maps one combinator time period to a different:

This behaviour of the

${textsf{abs}}$

perform needs to be clear from its kind: given a

${textsf{Comb}}$

time period of kind

${tau}$

utilizing variables drawn from the context

${{sigma};textsf{::};Gamma}$

, the

${textsf{abs}}$

perform returns a combinator of kind

${{sigma};Rightarrow;tau}$

utilizing variables drawn from the context

${{Gamma}}$

. Basically, any occurrences of the

${textsf{var};textsf{High}}$

are changed with the identification

${textsf{I}}$

; the brand new argument is distributed over purposes utilizing the

${textsf{S}}$

combinator; every other variables or base combinators discard this new argument by introducing a further

${textsf{Okay}}$

combinator.

With this definition in place, we will now outline our type-preserving correct-by-construction translation. That’s, we goal to outline a translation with the next kind:

Right here a lambda time period of kind

${{sigma}}$

within the context

${{Gamma}}$

is mapped to a combinator of kind

${{sigma}}$

utilizing variables drawn from the context

${{Gamma}}$

in such a manner that the analysis of

${textsf{t}}$

and semantics of the combinator are an identical, specifically . The definition of this translation is now completely easy.

To see why this code kind checks, observe that each the (dynamic) semantics of each the

${textsf{app}}$

and

${textsf{var}}$

constructors of the

${textsf{Comb}}$

datatype coincide exactly with their semantics as lambda phrases, and respectively. Lastly, if translating the physique of a lambda produces some

${textsf{Comb}}$

time period

${textsf{f}}$

, the

${textsf{abs}}$

perform produces a combinator time period with the semantics

${lambda;textsf{env};textsf{x};;textsf{f};(textsf{Cons};textsf{x};textsf{env})}$

. The similarity between the *kind* of the

${textsf{abs}}$

perform and the

${textsf{lam}}$

department of our evaluator isn’t any coincidence.

There’s a refined distinction between this translation scheme and the one introduced within the introduction. Specifically, when a variable doesn’t happen anyplace, the bracket abstraction sketched within the introduction instantly introduces a

${textsf{Okay}}$

combinator, whereas the

${textsf{abs}}$

perform will use the

${textsf{S}}$

combinator in each software – even when the variable is unused in each branches. This will result in unnecessarily giant combinatorial phrases. Moreover, the SKI-combinators will not be the one doable alternative of combinatorial foundation. Specifically, the

${textsf{S}}$

combinator *at all times* passes its third argument to the primary two – even whether it is unused in one of many branches. Can we do higher?

## 4 An optimising translation

There’s another implementation of bracket abstraction, utilizing two extra combinators

${textsf{B}}$

and

${textsf{C}}$

, that Turner (Reference Turner1979) attributes to Curry. The discount behaviour of

${textsf{B}}$

and

${textsf{C}}$

is outlined as follows:

start{align*} mathsf{B} ; f ; g ; x & to f ; (g ; x) mathsf{C} ; f ; g ; x & to (f ; x) ; gend{align*}

In distinction to the

${textsf{S}}$

combinator, the

${textsf{B}}$

combinator solely passes its third argument to its second argument. The

${textsf{C}}$

combinator, alternatively, solely passes its third argument to its first argument. This avoids unnecessarily duplicating the third argument

${textsf{x}}$

, when it is just utilized by one of many two phrases in an software. When the variable will not be used in any respect, we will introduce the

${textsf{Okay}}$

combinator as instructed by the interpretation scheme from the introduction. Because of this, normalising phrases might require fewer discount steps.

We are able to readily prolong our

${textsf{Comb}}$

datatype with new constructors for these two combinators:

When translating an software, we now want to pick out between 4 choices:

${textsf{Okay}}$

,

${textsf{B}}$

,

${textsf{C,}}$

and

${textsf{S}}$

, relying how variables are used. How can we make this alternative, whereas nonetheless guaranteeing that varieties and semantics are preserved accordingly?

The important thing perception is that the interpretation scheme, applied by the

${textsf{abs}}$

perform above, already informs us whether or not or not a variable is used: any variable prevalence or combinator that doesn’t use essentially the most lately sure variable begins with an software of the

${textsf{Okay}}$

combinator. Slightly than indiscriminately apply the

${textsf{S}}$

combinator on subterms, we will as an alternative differentiate the place variables are literally used. To this finish, we outline the next specialised perform for making use of the

${textsf{S}}$

combinator:

Not like the earlier naive translation, this definition avoids pointless occurrences of the

${textsf{Okay}}$

combinator, simplifying the ensuing definition at any time when doable. Solely the final case, when neither

${textsf{t}_{1}}$

nor

${textsf{t}_{2}}$

begin with an software of

${textsf{Okay}}$

, introduces the

${textsf{S}}$

combinator. The opposite circumstances introduce an outermost

${textsf{Okay}}$

,

${textsf{B,}}$

or

${textsf{C}}$

combinator, relying on the place the ‘sure’ variable happens.

To finish the interpretation, we have to adapt the

${textsf{abs}}$

perform: including new circumstances for

${textsf{B}}$

and

${textsf{C}}$

, and calling the

${textsf{sapp}}$

perform as an alternative of making use of

${textsf{S}}$

immediately.

The categories and remaining circumstances definitions, nevertheless, stay unchanged.

## 5 Reflection

Though the interpretation schemes are fairly easy, discovering the implementation introduced right here was not. Writing dependently typed applications on this type – folding a program’s specification into its kind – might really feel like a little bit of a parlour trick, the place the correct alternative of definitions ensures the whole building is right. But studying by way of these definitions after the very fact – like so typically with Agda applications – doesn’t inform the whole story of how they have been constructed.

Verifying the kind protected translation from lambda phrases to

${textsf{SKI}}$

combinators is a query I’ve set my college students previously. Proving this translation right requires defining an analysis perform for combinatory phrases after which proving that the interpretation is semantics preserving. Apparently, this proof requires an axiom – practical extensionality – within the case for lambdas, as we have to show two capabilities equal. But the *construction* of proof is easy sufficient: it depends completely on induction hypotheses and a property of the

${textsf{abs}}$

perform. It’s this remark that makes it doable to include the correctness proofs within the definitions themselves – the place the required property of the

${textsf{abs}}$

perform is mixed with its definition. This remark is an occasion of the *recomputation lemma* of algebraic ornaments (McBride, Reference McBride2010). Extending the interpretation scheme to make use of the

${textsf{B}}$

and

${textsf{C}}$

combinators is a bit tougher. The code accompanying this paper demonstrates easy methods to use the ‘co-De Bruijn’ illustration of variables to outline the optimising translation (McBride, Reference McBride2018). Ralf Hinze instructed defining the interpretation immediately utilizing the

${textsf{sapp}}$

perform.

Traditionally, combinatory logic arose from the need to discover a basis for arithmetic that averted the problems surrounding variable binding (Schönfinkel, Reference Schönfinkel1924; Curry *et al.*, Reference Curry, Feys, Craig, Hindley and Seldin1958). The interpretation between between lambda calculus and combinatory logic is properly documented in quite a few textbooks (see Barendregt, Reference Barendregt1984, Chapter 7; Hindley & Seldin, Reference Hindley and Seldin1986, Chapter 2; Sørensen & Urzyczyn, Reference Sørensen and Urzyczyn2006, Chapter 5.4; Mimram, Reference Mimram2020, Chapter 3.6). There’s a shut connection between combinatory logic and Hilbert-style proof programs – cognoscenti will recognise the correspondence between the primary three axiom schemes and the categories that may be assigned to the three combinators above. Since then, Turner (Reference Turner1979) has explored easy methods to compile practical applications to combinatory logic (see additionally Peyton Jones, Reference Peyton Jones1987, Chapter 16; Diller, Reference Diller1988). This concept has been prolonged additional by Hughes (Reference Hughes1982) and plenty of others, even resulting in design of customized {hardware} for effectively rewriting phrases in combinatory logic (Stoye, Reference Stoye1983, Reference Stoye1985; Scheevel, Reference Scheevel1986). The lambda phrases equivalent to the

${textsf{S}}$

and

${textsf{Okay}}$

combinators have made a latest reappearance because the operations defining the

${textsf{Reader}}$

applicative functor (McBride & Paterson, Reference McBride and Paterson2008).

As our start line, we’ve got taken the ‘conventional’ merely typed lambda calculus. Newer work by Kiselyov (Reference Kiselyov2018) exhibits how a slight modification to the typing guidelines permits for a denotational semantics as combinators immediately. Formalising this in a proof assistant, nevertheless, is left as an train for the reader.