Just An Application

November 3, 2014

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.

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

Blog at WordPress.com.

%d bloggers like this: