So Swift Then: The Curried Function Type Encoding Mystery Concluded

While currying may be a theoretically elegant technique for thinking about and solving certain problems, when it comes to using it to write software it may not be very practical

Calling N one argument functions in a row, with each function allocating a closure, is going to be an expensive undertaking in terms of speed and memory, and it is going to be a lot slower than one function call of N arguments that does not allocate any closures.

If the sequence of function calls is complete, that is, they are being used to obtain the result rather than an intermediate closure then the allocated closures are one-shot. They are going to be deallocated straight away. This cost is incurred every time the result is obtained using all N function calls.

Of course the compiler could attempt some kind of special case optimization when the curried function is called. It could attempt to turn the N function calls back into one function call of N arguments but in the general case, that is, when the curried function is not guaranteed to be in the same module as the caller it is a bit stuck, unless it wants to decompile the object code.

Alternatively it could de-curry the curried function when it compiled it which is of course what it is doing in the case of xper.plusN

It is turning this

    func plusN(n: Int)(i: Int) -> Int
    {
        return i + n
    }

into this

    func 'plusN[decurried]'(n: Int, #i: Int) -> Int
    {
        return i + n
    }

For this to work the compiler must do two additional things when the curried function xper.plusN is called.

In the the function cod

    import xper
    
    func cod(x: Int, y:Int) -> Int
    {
        return xper.plusN(x)(i:y) // ignore the 'external name' its not really there
    }

it must convert the repeated single argument function call sequence to a standard function call.

In the function saithe

    import xper
    
    func saithe(x: Int, y:Int) -> Int
    {
        let plusX = xper.plusN(x)
    
        return plusX(i:y) // ignore the 'external name' its not really there
    }

it must generate the functions necessary to make it appear that the curried function still exists.

This explains what we see when cod and saithe are compiled.

In the first case ‘plusN[decurried]’ can be called directly.

In the second case the compiler needs to generate the equivalent of this

    func 'xper.plusN'(n: Int) -> (i: Int) -> Int
    {
        return { (i : Int) in return 'plusN[decurried]'(n, i: i) }
    }

To rewrite a call to a curried function and generate the local functions if necessary, the compiler must be able to identify when a public function in a module is a curried function, but that is not what the symbol associated with the object code is for.

We can demonstrate this by compiling the function cod using the module information in

  xper.swiftmodule

associated with the curried function version of plusN, and the library

  libxper.dylib

obtained by compiling its vanilla function equivalent, in which case this happens.

    $ swiftc -I. -lxper -L. -module-name caller -emit-library call_plusN.swift
    Undefined symbols for architecture x86_64:
      "__TF4xper5plusNfSiFT1iSi_Si", referenced from:
         __TF6caller3codFTSiSi_Si in call_plusN-7db2ff.o
    ld: symbol(s) not found for architecture x86_64
    <unknown>:0: error: linker command failed with exit code 1 (use -v to see invocation)

The compiler has used the module information that identifies plusN as a curried function and compiled accordingly.

It has specified that the object code of the caller needs to be linked against the object code identified by the symbol

    __TF4xper5plusNfSiFT1iSi_Si

and left it to the linker to do whatever it is that linkers do.

In this case there is an undefined symbol for some object code so the linker goes and looks for the piece of object code for which that symbol is defined.

What it does if it finds it depends on where the object code is found.

What it does if doesn’t find it is stop.

In this case the only other object code is in

  libxper.dylib

and because the version it is has been given to link against does not contain the compiled code for the curried function it cannot find a matching defined symbol so it stops.

To match undefined and defined symbols does not require the linker to understand their format or even to be aware that they have a format.

The linker likes to match symbols and the only thing it asks is that they be unique.

If the compiler is prepared to guarantee that no two functions with the same name and the same type can exist at the same time in the same module, then encoding a function’s name and type into the symbol for that function is a guaranteed way to ensure its uniqueness.

In the case of a curried function the compiler needs to generate a symbol which can be used to identify the de-curried function which is the result of the compilation.

Like all symbols used for linking it must be unique.

Given that the compiler is treating curried functions as a special case the most straight forward solution is for it to use a distinct ‘curried function type’ encoding which reflects this to generate the symbols for them.

Hence the lower-case ‘f’.

---

Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

So Swift Then: The Curried Function Type Encoding Mystery Continued

Compiling the curried function

    public func plusN(n: Int)(i: Int) -> Int
    {
        return i + n
    }

on its own in the module xper gives us the symbol

    __TF4xper5plusNfSiFT1iSi_Si

All the examples of mangled names of vanilla functions we have seen to date have been in the format.

    "__TF" 'function name' "F" 'parameter encoding' 'return type encoding' 'suffix'?

The format of the symbol for the curried function is identical to this except that there is a lower-case ‘f’ rather than an upper case ‘F’

We have been assuming that the upper case ‘F’ immediately following the function name in the symbol for a vanilla function is the prefix for a ‘function type’.

If this is true than the lower case ‘f’ is presumably the prefix for a different kind of function type.

The obvious candidate is the ‘curried function type’ but why is it necessary to distinguish between a ‘function type’ and a ‘curried function type’ in the mangled name of the function ?

The compiler does not distinguish between a curried function and the vanilla version of the curried function at compile time but it does ensure that it is possible to identify which one was compiled to produce the object code.

This implies that a caller would have to be linked against either one or the other despite calls to both functions being identical.

Here is a function which calls plusN and then immediately calls the function that was returned

    import xper
    
    func cod(x: Int, y:Int) -> Int
    {
        return xper.plusN(x)(i:y) // ignore the 'external name' its not really there
    }

This call works whether it is the curried function or the vanilla function equivalent that is being called.

Here is a function that does the same thing as the function cod with an intermediate step just to make it clear what is going
on.

    import xper
    
    func saithe(x: Int, y:Int) -> Int
    {
        let plusX = xper.plusN(x)

        return plusX(i:y) // ignore the 'external name' its not really there
    }

This call also works whether it is the curried function or the vanilla function equivalent that is being called.

This is not surprising since they are obviously both doing the same thing, that is

• calling the function xper.plusN with the argument x

• calling the function returned from the call to xper.plusN with the argument y

In saithe the function returned from the call to xper.plusN is explicitly referenced but the only thing done with it is to call it. It does not ‘escape’ from the function at any point so the two functions are effectively identical.

If we compile the function cod on its own in the module caller linking against the module xper containing the curried function plusN we get the symbol

    __TF6caller3codFTSiSi_Si

for the function itself, and the undefined symbol

  __TF4xper5plusNfSiFT1iSi_Si

which is the symbol for the curried function xper.plusN.

If we compile the function saithe on its own in the module caller linking against the module xper containing the curried function plusN then, as before, we get the symbol

    __TF6caller6saitheFTSiSi_Si

for the function itself, the undefined symbol

  __TF4xper5plusNfSiFT1iSi_Si

which is the symbol for the curried function xper.plusN, as before, and quite unexpectedly the symbols for two local
functions.

    __TF4xper5plusNFSiFT1iSi_Si

and

    __TPA__TF4xper5plusNfSiFT1iSi_Si

Who ordered those ?

The function type encoded in the first symbol is

    (Int) -> (i: Int) -> Int

which looks strangely familiar.

The only place in the function saithe that it could be called is here.

    let plusX = xper.plusN(x)

If we assume that the compiler knows what it is doing then that must be what it is for.

The symbol for the second function

    __TPA__TF4xper5plusNfSiFT1iSi_Si

looks like the symbol for the curried function xper.plusN with the prefix

    __TPA

We have never seen anything like this before so it is a bit difficult to say what this kind of function might be for.

Continuing with the hypothesis that the compiler knows what it is doing we have to assume that it needs this function for something, and given that is has already generated a function to return a function then presumably this is the function that gets returned.

If this is true then the reading of the function type in the mangled name has to be something other than the type apparently encoded.

The function type needs to be

    (i: Int) -> Int

and that is not what is encoded according to the vanilla function type reading.

If the compiler really has had to generate a function to do this

    let plusX = xper.plusN(x)

then the implication is that the function plusN in the module xper cannot be called at that point.

It must be possible to call it since the first example works and the compiler did not need to generate any additional functions to make it work.

If the function plusN in the module xper cannot be called in saithe but it can be called in cod then we can infer both

• what its function type is not, and

• what it must be

which explains both why the generated local functions are needed and what they do.

It also confirms that the reading of ‘curried function’ types is not the same as the reading of ‘vanilla function’ types when they appear in mangled function names.

---

Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

So Swift Then: The Curried Function Type Encoding Mystery

We have a model of how function types are encoded when function names are mangled.

It works for all the vanilla functions we have looked at to date, albeit we have not looked at that many, but there are at least three other kinds of function we have not looked at.

The first kind are ‘curried’ functions.

Currying, the term originated in the lambda calculus, is the transformation of a function that takes N arguments into N functions each of one argument so that

    F(a[0], ..., a[N-1]) == f[0](a[0])(a[1]) ... (a[N-1])

For I from 0 to N – 2, function I takes argument I and returns function I + 1.

For I == N – 1, function I takes argument I and returns the result.

Its a neat trick if you can pull it off.

The usual example for N == 2 is something like this.

    func plusN(n: Int) -> (Int) -> Int
    {
        func plusI(i: Int) -> Int
        {
            return i + n
        }
    
        return plusI
    }

In Swift this can also be written like this

    func plusN(n: Int)(i: Int) -> Int
    {
        return i + n
    }

What is interesting in this context is how the function name gets mangled when the curried function syntax is used.

Compiling the first version gives us the symbol

    __TF4xper5plusNFSiFSiSi

Compiling the second version gives us the symbol

    __TF4xper5plusNfSiFT1iSi_Si

which is interesting both because the function type starts with an ‘f’ rather than an ‘F’ and because the second ‘parameter’ as written, which is actually the first parameter of the returned function has apparently acquired an external name.

    __TF4xper5plusNfSiFT1iSi_Si

It should be possible to invoke either version like this

    func plus(a: Int, b:Int) -> Int
    {
        return plusN(a)(b)
    }

This function duly compiles with the first definition but compiling it with the second definition gets you this

    $ swiftc -module-name xper  -emit-library functions.swift
    functions.swift:83:21: error: missing argument label 'i:' in call
        return plusN(a)(b)
                        ^
                        i:

The compiler does indeed believe that the second parameter has an ‘external name’.

The only clue to what is going on is the symbol.

    __TF4xper5plusNfSiFT1iSi_Si

We know that compiling the function

    func bass(e i : Int) -> Int
    {
        return i
    }

gives us the symbol

    __TF4xper4bassFT1eSi_Si

so it looks as though the compiler believes the return type of the function plusN is

a function with a single parameter with the external name ‘i’ of type Int which returns an Int

The definition of a function type given in the ‘red book’ is

    function-type → type -> type

The definition of a type is

    type →   array-type
           | dictionary-type
           | function-type
           | type-identifier
           | tuple-type
           | optional-type
           | implicitly-unwrapped-optional-type
           | protocol-composition-type
           | metatype-type

The definition of a tuple type is

    tuple-type               →   ( tuple-type-bodyopt )
    
    tuple-type-body          →   tuple-type-element-list ...opt
    
    tuple-type-element-list  →   tuple-type-element
                               | tuple-type-element , tuple-type-element-list
                            
    
    tuple-type-element       →   attributesopt inoutopt type
                               | inoutopt element-name type-annotation
                            
    element-name             →   identifier

This is all a bit misleading because you simply cannot use an arbitrary tuple type wherever you can use a type.

For example the return type of a function can be a tuple type, but it certainly cannot be the tuple type

    (inout Int)

Which is a bit disappointing really.

It would be quite an interesting feature although it is not entirely clear whether it would enable the caller to alter the value inside the called function after the called function had returned the value to them, or conversely enable the called function to alter the returned value insider the caller after it had returned the value to the caller.

Either way an opportunity missed I think.

We have already seen another return type example.

A return type cannot be a single named element tuple type.

This is covered in the Tuple Type section where it says

you can name a tuple element only when the tuple type has two or more elements

so you can’t do this either

    func cod(#i: Int) -> Int
    {
        return 0
    }
    
    func dab() -> (i: Int) -> Int
    {
        return cod
    }

except that you can.

The effect of this is to specify that the parameter of the returned function has the external name ‘i’ and the type Int although you would be hard pushed to discover that other than by trial and error.

Note that the type of the function dab

    (i: Int) -> Int

is the same text appears in the curried function version of the function plusN.

    func plusN(n: Int)(i: Int) -> Int
    {
        return i + n
    }

If you were to mistakenly transform that version into this one

    func plusN(n: Int) -> (i : Int) -> Int
    {
        return { i in  i + n }
    }

you would end up with the right behaviour but with an external name you do not want.

This is not what is happening the curried function we have been looking at it because the resulting symbol would not be the same but it is presumably something similar that occurs at some stage during the compilation.

Let’s assume the appearance of the ‘external name’ when using the curried syntax in this way is a bug and that it is going to get fixed.

That leaves the lower case ‘f’.

You cannot compile the curried and vanilla versions of plusN above together in the same file. The compiler considers one to be a redeclaration of the other.

Yet if you compile them on their own you get different symbols even if the difference is the case of a single letter.

Is the difference meaningful or is it some kind of artefact ?

---

Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

So Swift Then: Mangled Function Names And Function Types — Function Types Go Recursive

Now we have a model of how function types are encoded lets see if we can break it.

What happens if we use it on a function which returns a function.

Starting with the function

    func bass() -> ()
    {
    }

Now we have a function to return like so

    func cod() -> () -> ()
    {
        return bass
    }

Compiling cod gives us the symbol

    __TF4xper3codFT_FT_T_

giving us

    FT_FT_T_

as the function type.

Now for the model.

Starting by creating some useful objects.

    let encoder     = Encoder()
    let builder     = FunctionTypeBuilder()
    let ftVoidVoid  = builder.build()

then

    let ft6000 = builder.returnType(ftVoidVoid).build()

    println(ft6000.encode(encoder))

prints

    FT_FT_T_

We’re off to flying start.

This is a function which returns a function which returns a function

    func dab() -> () -> () -> ()
    {
        return cod
    }

and compiling it gives us the symbol

    __TF4xper3dabFT_FT_FT_T_

giving us

    FT_FT_FT_T_

as the function type.

This

    let ft6001 = builder.returnType(ft6000).build()
    
    println(ft6001.encode(encoder))

prints

    FT_FT_FT_T_

so that’s alright.

A function that takes an Int and a function as arguments

    func eel(x: Int, f: (Int) -> (Int)) -> Int
    {
        return f(x)
    }

Compiling it gives us the symbol

    __TF4xper3eelFTSiFSiSi_Si

giving us

    FTSiFSiSi_Si

as the function type.

    let ftIntInt = builder.intParam().intReturnType().build()
    let ft6002   = builder.intParam().param(ftIntInt).intReturnType().build()
    
    println(ft6002.encode(encoder))

prints

    FTSiFSiSi_Si

A function that takes a function that takes two Ints and returns a pair or Ints

    func flounder(f: (Int, Int) -> (Int, Int))
    {
    }

Compiling it gives us the symbol

    __TF4xper8flounderFFTSiSi_TSiSi_T_

giving us

    FFTSiSi_TSiSi_T_

as the function type.

    let intType  = BuiltinType.IntType
    let fnType   = builder.tupleTypeParam(intType, intType).tupleReturnType(intType, intType).build()
    let ft6003   = builder.param(fnType).build()
    
    println(ft6003.encode(encoder))

prints

    FFTSiSi_TSiSi_T_

which of course it would !

A function that takes a function which returns a function as its argument and returns the result of calling that function

    func goby(f: () -> () -> ()) -> () -> ()
    {
        return f()
    }

Pick the parentheses out of that.

The compiler having picked the parentheses out comes up with the symbol

    __TF4xper4gobyFFT_FT_T_FT_T_

which gives us the function type

    FFT_FT_T_FT_T_

and we’ll just have to trust that it knows what its doing.

    let ft6004   = builder.param(ft6000).returnType(ftVoidVoid).build()
    
    println(ft6004.encode(encoder))

prints

    FFT_FT_T_FT_T_

so if the compiler knows what its doing so does the model, and possibly vice versa.

And that’s enough of that without a dedicated test harness that can count ‘F’s and ‘T’s and stuff.

It certainly looks as though the model’s behaviour matches that of the compiler when it comes to function types as arguments and return types.

---

Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.