Function Binding

[TypeIt]

Let's assume that there is a function that expects another function as an argument.

Func GetSortedListOfVillains (ByRef $hero, Const ByRef $sortingAlgorithmOfEvil)
    ; That will take a while, so fight with swords while riding on chairs (xkcd.com/303/).
    Local $villains = [$evilOverlord] ; should be global
    _ArrayConcatenate ($villains, VisitGhibliHills ($hero))
    _ArrayConcatenate ($villains, VisitForestOfInconvenience ($hero))
    _ArrayConcatenate ($villains, VisitHillsOfModerateEvil ($hero))
    _ArrayConcatenate ($villains, VisitMountDoom ($hero))
    $sortingAlgorithmOfEvil ($villains)
    Return $villains
EndFunc

One way to use that:

Global $Sort_Arguments
; ...
$Sort_Arguments = ["evilsort", $SORT_IGNORECASE] ; Let's assume that you're using a compiler which translates this into valid AutoIt.
GetSortedListOfVillains ($theHero, Sort)
; ...
Func Sort (ByRef $array)
    If Not IsArray ($Sort_Arguments) Then Return SetError (...)
    ; I changed this function yesterday. Use the specified sorting algorithm and silently ignore any other arguments.
    ; Bonus points for silently changing the meaning of an argument.
EndFunc

Another way:

GetSortedListOfVillains ($theHero, SpecialEvilSortUsingAUniqueVillainIdList)
; ...
Func SpecialEvilSortUsingAUniqueVillainListId (ByRef $array)
    ; this is the id of the list v
    Return Sort ("evilsort", 16372, $array)
    ; That's a magical number, but I can't pass it as an argument.
    ; And I need to create a separate function for every used combination of id and sorting algorithm.
EndFunc

The desired way with the hypothetical function "BindFunction":

GetSortedListOfVillains ($theHero, BindFunction (Sort, "evilsort"))
; ...
Func Sort (Const ByRef $sortingAlgorithm, ByRef $array)
    ; sort it
    ; Time complexity of EvilSort: O((n^2)!)
EndFunc

(The example code should highlight specific aspects of these approaches. That's the reason for the different signatures of the sort function.)

Is something like that possible? Do you think that it would be useful?

Edited July 24, 2014 by TypeIt

[Mat]

What you want would require functions to be first class objects. A lot of progress has been made in AutoIt over the last year to get some of the features other modern languages have, and first class functions is one of those features that isn't quite there yet.

It's a little bit tricky to decipher exactly what you want to do. It's possible that you could mimic it with Execute, something like:

GetSortedListOfVillains("Sort($aArray, ""evilsort"", ""ignore case"")")


Func GetSortedListOfVillains ($sortingAlgorithmOfEvil)
    ; That will take a while, so fight with swords while riding on chairs (xkcd.com/303/).
    Local $villains = ["Weese", "Dunsen", "Chiswyck", "Polliver", "Raff the Sweetling", "The Tickler", "The Hound", "Ser Gregor", "Ser Amory", "Ser Ilyn", "Ser Meryn", "King Joffrey", "Queen Cersei"]
    ApplySort($sortingAlgorithmOfEvil, $villains)
    Return $villains
EndFunc

Func ApplySort($sFunc, ByRef $aArray)

    ; An example of how to use Execute on code that has had variable names changed by Au3Stripper.
    Local $sArrName = "a"
    While IsDeclared($sArrName)
        $sArrName &= "a"
    WEnd

    Assign($sArrName, $aArray)

    Execute(StringReplace($sFunc, "$aArray", "$" & $sArrName))

    $aArray = Eval($sArrName)
EndFunc


Func Sort(ByRef $aArray, $sSortType, $iFlags)
    MsgBox(0, $sSortType, $iFlags)
Endfunc

But I'm not sure what you are looking to achieve.

[jvanegmond]

Simple and genius at the same time! I would applaud but I'm in an office full of people.

Yes, we totally need to update the Array UDF to include a function for equality comparison. That will greatly simplify the existing _ArraySort method and also increase its usefulness. Who needs $iDescending parameter? Hah.

 

Proof of concept:

expandcollapse popup

#include <Array.au3>

Local $arr[5] = [4, 2, 1, 5, 3]

__ArraySort($arr, EqualityComparisonGreaterThan)
Func EqualityComparisonGreaterThan($a, $b)
    Return $a > $b
EndFunc

_ArrayDisplay($arr)

__ArraySort($arr, EqualityComparisonLessThanOrEquals)
Func EqualityComparisonLessThanOrEquals($a, $b)
    Return $a <= $b
EndFunc

_ArrayDisplay($arr)

Local $sArr[6] = ["4", "2", "1", "5", "3", "Hue hue"]

__ArraySort($sArr, EqualityComparisonStringLessThanOrEquals)
Func EqualityComparisonStringLessThanOrEquals($a, $b)
    Return Number($a) <= Number($b)
EndFunc

_ArrayDisplay($sArr)

Func __ArraySort(ByRef $avArray, $equalityFunc, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iPivot = 0)
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If Not IsArray($avArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($avArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd = Default Then $iEnd = 0
    If $iEnd < 1 Or $iEnd > $iUBound Or $iEnd = Default Then $iEnd = $iUBound
    If $iStart < 0 Or $iStart = Default Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)

    If $iPivot = Default Then $iPivot = 0
    If $iSubItem = Default Then $iSubItem = 0

    ; Sort
    Switch UBound($avArray, $UBOUND_DIMENSIONS)
        Case 1
            ___ArrayQuickSort1D($avArray, $iStart, $iEnd, $equalityFunc)
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch

    Return 1
EndFunc   ;==>_ArraySort

Func ___ArrayQuickSort1D(ByRef $avArray, Const ByRef $iStart, Const ByRef $iEnd, $equalityFunc)
    If $iEnd <= $iStart Then Return

    Local $vTmp

    ; InsertionSort (faster for smaller segments)
    Local $vCur
    For $i = $iStart + 1 To $iEnd
        $vTmp = $avArray[$i]

        For $j = $i - 1 To $iStart Step -1
            $vCur = $avArray[$j]
            ; If $vTmp >= $vCur Then ExitLoop
            If $equalityFunc($vTmp, $vCur) Then ExitLoop
            $avArray[$j + 1] = $vCur
        Next

        $avArray[$j + 1] = $vTmp
    Next
    Return
EndFunc   ;==>__ArrayQuickSort1D

Edited July 25, 2014 by Manadar

[guinness]

Yes, we totally need to update the Array UDF to include a function for equality comparison.

We are making progress in this area with that UDF.

[TypeIt]

What you want would require functions to be first class objects. A lot of progress has been made in AutoIt over the last year to get some of the features other modern languages have, and first class functions is one of those features that isn't quite there yet.

I take first-class as being able to do more than something second-class. As far as I know, you can assign "normal" values to variables, pass them as arguments and return them. You can do the same with functions, so "normal" values should be first-class values. You can create "normal" values "on the fly", but you can't do the same with functions, so functions are second-class values. Do I have this right?

 

It's possible that you could mimic it with Execute

Is it possible without strings? I might not be able to convert it into a string representation without using global variables. Global variables are neiter a general solution nor a desirable solution.

I couldn't find a general solution that would work with the following, even if it's allowed to generate a (constant) number of additional functions for each occurrence of BindFunction and the ability to rewrite every BindFunction expression.

Func theFunction ($a, $b)
    ConsoleWrite ($a & " " & $b & @CRLF)
EndFunc

Func createTheBoundFunction ($firstArgument)
    Return BindFunction (theFunction, $firstArgument)
EndFunc

Func callIt ($f1, $f2)
    For $i = 1 To 3
        If Random () > 0.5 Then
            $f1 ($i)
        Else
            $f2 ($i)
        EndIf
    Next
EndFunc

callIt (createTheBoundFunction (1), createTheBoundFunction (2))

 

But I'm not sure what you are looking to achieve.

I think it's called "partial function application". I would like to bind the first a arguments of a function with n arguments to some values and treat the result as a function with n-a arguments, like std::bind in C++ and Array.prototype.bind in Javascript. bind​(f,a,b​)(c,d​) should be the same as f(a,b,c,d). Do you think that that would be useful (in the context of Autoit)? It appears to require language level support.

 

Yes, we totally need to update the Array UDF to include a function for equality comparison. That will greatly simplify the existing _ArraySort method and also increase its usefulness. Who needs $iDescending parameter? Hah.

Maybe the performance fanatic. It will be possible to pass the less than function as the second argument?

[jchd]

Passing a comparison function to sort is standard C for decades. Don't we do the same now? I must admit that now that I don't actually use the language for practical purpose I'm a bit off with improvements in UDFs.

[jvanegmond]

Passing a comparison function to sort is standard C for decades. Don't we do the same now? I must admit that now that I don't actually use the language for practical purpose I'm a bit off with improvements in UDFs.

No, not yet. The comparison is built into the _ArraySort function and that's what I mean. It should probably be changed.

[trancexx]

The OP talks about lambdas, anonymous functions.

Manadar's code:

#include <Array.au3>

Local $arr[5] = [4, 2, 1, 5, 3]

__ArraySort($arr, EqualityComparisonGreaterThan)
Func EqualityComparisonGreaterThan($a, $b)
    Return $a > $b
EndFunc

_ArrayDisplay($arr)

... then becomes:

#include <Array.au3>

Local $arr[5] = [4, 2, 1, 5, 3]

__ArraySort($arr, [&]($a, $b){ Return $a > $b})

_ArrayDisplay($arr)

...or once valid AutoIt:

#include <Array.au3>

Local $arr[5] = [4, 2, 1, 5, 3]

__ArraySort($arr, Func($a, $b) Return $a > $b EndFunc)

_ArrayDisplay($arr)

I would say more about that and the work done in that direction few years ago, but my censors would probably classify that as an attempt to insult Jon or whoever, so I wont. Edited July 25, 2014 by trancexx

[guinness]

Currently Min and Max index adopt passing a comparison function for want of a better word.

[TypeIt]

The OP talks about lambdas, anonymous functions.

Yes, I did. At one point. But that isn't my main concern. It is possible to implement partial function application with closures, lambdas which can access their lexical environment (and either keep it alive and require garbage collection or copy the necessary part of the environment). Lambdas would be the best possible solution, but are not the only possible solution.

Example:

Func BindFunction ($f, $a)
    Return ($b, $c) => $f ($a, $b, $c)
EndFunc

It is possible to create expressions that behave like lambdas with a function for partial function application. It's possible that it isn't really difficult to implement, but fortunately it isn't I who modifies the AutoIt source (just in case that this will get implemented and is really complex).

Example:

$a = 1
; $lambda = $b => $a + $b
$lambda = Bind (Addition, $a)
Func Addition ($a, $b)
    Return $a + $b
EndFunc

Is it possible to implement partial function application with "conventional" AutoIt, if the code in this post should work? Should it be possible to do something like that in AutoIt? Edited July 25, 2014 by TypeIt

[jvanegmond]

Yes, but it's kind of lame. It solves your issue though.

 

You "bind" a function with parameters by putting it in an array or map. Then write your own call function to extract the function and parameters from the array/map.

 

Something like this:

expandcollapse popup

Local $heroes = ["Manadar", "Mat", "trancexx"]


Sort($heroes, ExampleSort1)

Sort($heroes, Bind(ExampleSort2, 123))

; "Parameter" functions
Func ExampleSort1($aValues, $a, $b)
   
EndFunc

Func ExampleSort2($aValues, $a, $b, $optionalA)
   
EndFunc


; Implementation
Func Sort(ByRef $aValues, $fSort)
   For ...... $aValues
      $a = ...
      $b = ...
      
      Local $params[2] = [$a, $b]
      _Call($fSort, $params)
   Next
EndFunc



; Utility
Func Bind($f, $params)
   Local $aBound = [$f, $params]
   Return $aBound
EndFunc

Func _Call($aBound, $params)
   $aBound ;<-- Your function or an array containing:
   $aBound[0] ;<-- Your function
   $aBound[1] ;<-- Optional parameters
   
   ;And also
   
   $params ;<-- Actual parameters
EndFunc

Once my dev env works again I'll flesh the example out better.

Maybe there's a better way. Will have to think about it.

Edited July 25, 2014 by Manadar

[TypeIt]

You "bind" a function with parameters by putting it in an array or map. Then write your own call function to extract the function and parameters from the array/map.

I've thought of that, but unfortunately that doesn't solve the problem. I can't change the Sort function, and that function requires the compare argument to be callable, to be a function reference.

[TypeIt]

...

I tested that. The results first:

sorted array
1. normal sort: 1706.77929891972
2. sort with normal function: 3243.01820175122
3. sort with bound function: 68745.4947985765
t3 / t2: 21.1979984452305
t3 / t1: 40.2779051996281
t2 / t1: 1.90008058089516

sorted array reverse
1. normal sort: 389.053023881008
2. sort with normal function: 1909.09730231511
3. sort with bound function: 67457.9875664576
t3 / t2: 35.3350180133055
t3 / t1: 173.390215281014
t2 / t1: 4.90703627816812

random array
1. normal sort: 1060.49700717624
2. sort with normal function: 2613.1627985126
3. sort with bound function: 67304.0390386167
t3 / t2: 25.755777281433
t3 / t1: 63.4646194974426
t2 / t1: 2.46409257247279

That's a really big difference. I don't think that this is useful, if it isn't part of the language.

functional.au3

expandcollapse popup

; Somewhere between speed and flexibility with 100 supported arguments.
; The version with 100.000 arguments takes half a minute without getting anything done.
Func MakeArray ($a1 = Default, $a2 = Default, $a3 = Default, $a4 = Default, $a5 = Default, $a6 = Default, $a7 = Default, $a8 = Default, $a9 = Default, $a10 = Default, $a11 = Default, $a12 = Default, $a13 = Default, $a14 = Default, $a15 = Default, $a16 = Default, $a17 = Default, $a18 = Default, $a19 = Default, $a20 = Default, $a21 = Default, $a22 = Default, $a23 = Default, $a24 = Default, $a25 = Default, $a26 = Default, $a27 = Default, $a28 = Default, $a29 = Default, $a30 = Default, $a31 = Default, $a32 = Default, $a33 = Default, $a34 = Default, $a35 = Default, $a36 = Default, $a37 = Default, $a38 = Default, $a39 = Default, $a40 = Default, $a41 = Default, $a42 = Default, $a43 = Default, $a44 = Default, $a45 = Default, $a46 = Default, $a47 = Default, $a48 = Default, $a49 = Default, $a50 = Default, $a51 = Default, $a52 = Default, $a53 = Default, $a54 = Default, $a55 = Default, $a56 = Default, $a57 = Default, $a58 = Default, $a59 = Default, $a60 = Default, $a61 = Default, $a62 = Default, $a63 = Default, $a64 = Default, $a65 = Default, $a66 = Default, $a67 = Default, $a68 = Default, $a69 = Default, $a70 = Default, $a71 = Default, $a72 = Default, $a73 = Default, $a74 = Default, $a75 = Default, $a76 = Default, $a77 = Default, $a78 = Default, $a79 = Default, $a80 = Default, $a81 = Default, $a82 = Default, $a83 = Default, $a84 = Default, $a85 = Default, $a86 = Default, $a87 = Default, $a88 = Default, $a89 = Default, $a90 = Default, $a91 = Default, $a92 = Default, $a93 = Default, $a94 = Default, $a95 = Default, $a96 = Default, $a97 = Default, $a98 = Default, $a99 = Default, $a100 = Default)
    Local $array [@NumParams]
    For $i = 1 To @NumParams - 1
        $array [$i] = Eval ("a" & $i)
    Next
    Return $array
EndFunc

Func MakeEmptyArray ()
    Local $result = []
    Return $result
EndFunc

Func IsBoundFunction ($boundFunction)
    Return IsArray ($boundFunction) _
        And UBound ($boundFunction, 0) == 1 And UBound ($boundFunction) == 2 _
        And IsFunc ($boundFunction [0]) _
        And UBound ($boundFunction [1], 0) == 1
EndFunc

Func BindFunction ($functionOrBoundFunction, $arguments = Default)
    ; The arguments to bind to were omitted. Fix that.
    If $arguments == Default Then $arguments = MakeEmptyArray ()

    ; When there are no arguments to bind, then there is no work to do.
    ; Return the function.
    If UBound ($arguments) == 0 Then Return $functionOrBoundFunction

    If IsFunc ($functionOrBoundFunction) Then
        Local $result = [$functionOrBoundFunction, $arguments]
        Return $result

    ElseIf IsBoundFunction ($functionOrBoundFunction) Then
        Return BindBoundFunction ($functionOrBoundFunction, $arguments)

    Else
        Return SetError (1, 0, Null)
    EndIf
EndFunc

; "internal"
Func BindBoundFunction ($boundFunction, $additionalArguments)
    ; If the function already is a bound function, then the result shouldn't
    ; wrap the already bound function in another array. We copy the old
    ; argument array, resize it and append the new arguments to bind.
    Local $boundArguments = $boundFunction [1]
    Local $oldSize = UBound ($boundArguments)
    Local $sizeIncrease = UBound ($additionalArguments)
    Local $newSize = $oldSize + $sizeIncrease
    ReDim $boundArguments [$newSize]
    For $i = 0 To $sizeIncrease - 1
        $boundArguments [$oldSize + $i] = $arguments [$i]
    Next
    $boundFunction [1] = $boundArguments
    Return $boundFunction
EndFunc

Func Invoke ($functionOrBoundFunction, $additionalArguments = Default)
    ; The arguents to call with were omitted. Fix that.
    If $additionalArguments == Default Then $additionalArguments = MakeEmptyArray ()

    ; Someone might pass something that isn't an arguments array. It's the callers
    ; fault, I don't care.
    If Not IsArray ($additionalArguments) Then Return SetError (1, 0, Null)

    If IsFunc ($functionOrBoundFunction) Then
        ; We need to prepend "CallArgArray"  to the arguments to indicate that we intend
        ; to pass an argument array instead of each argument separately.
        PrependCallArgArray ($additionalArguments)
        Local $result = Call ($functionOrBoundFunction, $additionalArguments)
        Return SetError (@error, @extended, $result)

    ElseIf IsBoundFunction ($functionOrBoundFunction) Then
        Local $result = InvokeBoundFunction ($functionOrBoundFunction, $additionalArguments)
        Return SetError (@error, @extended, $result)

    Else
        Return SetError (1, 0, Null)
    EndIf
EndFunc

; "internal"
Func InvokeBoundFunction ($boundFunction, $additionalArguments)
    ; If we don't need to concatenate two arrays, then we won't do that.
    If UBound ($additionalArguments) == 0 Then
        PrependCallArgArray ($additionalArguments)
        Local $result = Call ($boundFunction [0], $additionalArguments)
        Return SetError (@error, @extended, $result)
    EndIf

    ; If we need to concatenate two arrays and prepend the "CallArgArray"
    ; argument, then we will first allocate an array with enough space for
    ; that and then copy the rest.

    Local $boundArguments = $boundFunction [1]
    Local $boundArgumentsSize = UBound ($boundArguments)
    Local $additionalArgumentsSize = UBound ($additionalArguments)

    ; Don't forget the additional "CallArgArray" argument.
    Local $argumentsSize = $boundArgumentsSize + $additionalArgumentsSize + 1
    Local $arguments [$argumentsSize] = ["CallArgArray"]

    ; Copy the bound arguments.
    For $i = 0 To $boundArgumentsSize - 1
        $arguments [$i + 1] = $boundArguments [$i]
    Next

    ; Copy the additional arguments.
    For $i = 0 To $additionalArgumentsSize - 1
        $arguments [$boundArgumentsSize + 1 + $i] = $additionalArguments [$i]
    Next

    Local $result = Call ($boundFunction [0], $arguments)
    Return SetError (@error, @extended, $result)
EndFunc

; "internal"
Func PrependCallArgArray (ByRef $arguments)
    Local $argumentsSize = UBound ($arguments)
    ReDim $arguments [$argumentsSize + 1]
    For $i = $argumentsSize To 1 Step -1
        $arguments [$i] = $arguments [$i - 1]
    Next
    $arguments [0] = "CallArgArray"
EndFunc

test.au3

expandcollapse popup

#include "functional.au3"

Func less ($a, $b)
    Return $a < $b
EndFunc

; I didn't test the correctness of this function, because
; this function doesn't need to be correct.
Func Sort1 (ByRef $array)
    Local $arrayLength = UBound ($array)
    For $i = 2 To $arrayLength - 2
        For $j = 0 To $arrayLength - $i
            If $array [$j] < $array [$j + 1] Then
                Local $copy = $array [$i]
                $array [$i] = $array [$i + 1]
                $array [$i + 1] = $copy
            EndIf
        Next
    Next
EndFunc

Func Sort2 (ByRef $array, $less = less)
    Local $arrayLength = UBound ($array)
    For $i = 2 To $arrayLength - 2
        For $j = 0 To $arrayLength - $i
            If $less ($array [$j], $array [$j + 1]) Then
                Local $copy = $array [$i]
                $array [$i] = $array [$i + 1]
                $array [$i + 1] = $copy
            EndIf
        Next
    Next
EndFunc

Func Sort3 (ByRef $array, $less = less)
    Local $arrayLength = UBound ($array)
    For $i = 2 To $arrayLength - 2
        For $j = 0 To $arrayLength - $i
            If Invoke ($less, MakeArray ($array [$j], $array [$j + 1])) Then
                Local $copy = $array [$i]
                $array [$i] = $array [$i + 1]
                $array [$i + 1] = $copy
            EndIf
        Next
    Next
EndFunc


Func createRandomArray ($arrayLength)
    Local $array [$arrayLength]
    For $i = 0 To $arrayLength - 1
        $array [$i] = Random ()
    Next
    Return $array
EndFunc

Func createSortedArray ($arrayLength)
    Local $array [$arrayLength]
    For $i = 0 To $arrayLength - 1
        $array [$i] = $i + 1
    Next
    Return $array
EndFunc

Func createSortedArrayReverse ($arrayLength)
    Local $array [$arrayLength]
    For $i = 0 To $arrayLength - 1
        $array [$i] = $arrayLength - $i
    Next
    Return $array
EndFunc

Func copyArray ($array)
    Return $array
EndFunc

Func specialLess ($bindMe, $a, $b)
    Return $a < $b
EndFunc


Func testSort1 ($array)
    Local $array1 = copyArray ($array) ; Yes, this is ncessary.
    Local $timer = TimerInit ()
    Sort1 ($array1)
    Return TimerDiff ($timer)
EndFunc

Func testSort2 ($array)
    Local $array2 = copyArray ($array)
    Local $timer = TimerInit ()
    Sort2 ($array2, less)
    Return TimerDiff ($timer)
EndFunc

Func testSort3 ($array)
    Local $array3 = copyArray ($array)
    Local $timer = TimerInit ()
    Sort3 ($array3, BindFunction (specialLess, MakeArray (1)))
    Return TimerDiff ($timer)
EndFunc

Func testSortFunctions ($array)
    Local $time1 = testSort1 ($array)
    ConsoleWrite ("1. normal sort: " & $time1 & @CRLF)
    Local $time2 = testSort2 ($array)
    ConsoleWrite ("2. sort with normal function: " & $time2 & @CRLF)
    Local $time3 = testSort3 ($array)
    ConsoleWrite ("3. sort with bound function: " & $time3 & @CRLF)

    ConsoleWrite ("t3 / t2: " & $time3 / $time2 & @CRLF) ; bound function vs. normal function
    ConsoleWrite ("t3 / t1: " & $time3 / $time1 & @CRLF)
    ConsoleWrite ("t2 / t1: " & $time2 / $time1 & @CRLF)
EndFunc

ConsoleWrite ("sorted array" & @CRLF)
testSortFunctions (createSortedArray (1000))
ConsoleWrite (@CRLF)
ConsoleWrite ("sorted array reverse" & @CRLF)
testSortFunctions (createSortedArrayReverse (1000))
ConsoleWrite (@CRLF)
ConsoleWrite ("random array" & @CRLF)
testSortFunctions (createRandomArray (1000))

Edited July 27, 2014 by TypeIt