Just An Application

October 31, 2014

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-typetype -> 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-bodytuple-type-element-list ...opt
    
    tuple-type-element-listtuple-type-element
                               | tuple-type-element , tuple-type-element-list
                            
    
    tuple-type-elementattributesopt inoutopt type
                               | inoutopt element-name type-annotation
                            
    element-nameidentifier

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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: