Кіріспе
Бағдарламалау тілінің мүмкіндігі Компьютерлік ғылымда, егер бағдарламалау тілі функцияларды бірінші сыныптық объектілер ретінде қарастырса, онда ол бірінші сыныптық функцияларды қолдайды делінеді. Бұл тіл функцияларды басқа функцияларға аргументтер ретінде жіберуге, оларды басқа функциялардың нәтижесі ретінде қайтаруға және оларды айнымалыларға тағайындауға немесе дерек құрылымдарында сақтауға мүмкіндік береді дегенді білдіреді. Кейбір бағдарламалау тілі теорияшылары анонимді функцияларды (функциялық литералдарды) қолдауды да талап етеді. Бірінші сыныптық функцияларды қолдайтын тілдерде функциялардың аттары ешқандай арнайы мәртебеге ие болмайды; олар функция типі бар қарапайым айнымалылар сияқты қарастырылады. Бұл термин 1960 жылдардың ортасында Кристофер Стречи «функциялар – бірінші сыныптық объектілер» контекстінде қолданған. Бірінші сыныптық функциялар функционалдық бағдарламалау стилі үшін қажетті жағдай, онда жоғары ретті функцияларды пайдалану стандартты тәжірибе болып табылады. Жоғары ретті функциялардың қарапайым мысалы – `map` функциясы, ол функцияны және тізімді аргументтер ретінде қабылдайды және тізімнің әрбір элементіне функцияны қолдану арқылы құрылған жаңа тізімді қайтарады. Тіл `map` функциясын қолдау үшін функцияны аргумент ретінде жіберуге мүмкіндік беруі керек. Функцияларды аргументтер ретінде жіберу немесе оларды нәтиже ретінде қайтаруда, әсіресе ішкі және анонимді функцияларда пайда болатын жергілікті емес айнымалылардың болуында, белгілі бір орындалу қиындықтары туындайды. Тарихи тұрғыдан алғанда, бұлар `funarg` проблемалары деп аталды, бұл атау «функция аргументі» деген сөздерден шыққан. Ертедегі императивті тілдер бұл проблемаларды нәтиже типі ретінде функцияларды қолдамау арқылы (мысалы, ALGOL 60, Pascal) немесе ішкі функцияларды және осылайша жергілікті емес айнымалыларды жою арқылы (мысалы, C) шешіп келді. Ертедегі функционалдық тіл Lisp динамикалық ауқымдау тәсілін қолданды, онда жергілікті емес айнымалылар функция анықталған жерінен емес, функция орындалатын жердегі осы айнымалының ең жақын анықтамасына сілтеме жасайды. Лексикалық ауқымдағы бірінші сыныптық функцияларға толық қолдау Scheme тілінде енгізілді және функцияларға сілтемелерді қарапайым функция көрсеткіштерінің орнына жабылу ретінде қарастыруды талап етеді.
In computer science, a programming language is said to have first class functions if it treats functions as first class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures. Some programming language theorists require support for anonymous functions (function literals) as well. In languages with first class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type. The term was coined by Christopher Strachey in the context of "functions as first class citizens" in the mid 1960s. First class functions are a necessity for the functional programming style, in which the use of higher order functions is a standard practice. A simple example of a higher ordered function is the map function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each member of the list. For a language to support map, it must support passing a function as an argument. There are certain implementation difficulties in passing functions as arguments or returning them as results, especially in the presence of non local variables introduced in nested and anonymous functions. Historically, these were termed the funarg problems, the name coming from "function argument". In early imperative languages these problems were avoided by either not supporting functions as result types (e. g. ALGOL 60, Pascal) or omitting nested functions and thus non local variables (e. g. C). The early functional language Lisp took the approach of dynamic scoping, where non local variables refer to the closest definition of that variable at the point where the function is executed, instead of where it was defined. Proper support for lexically scoped first class functions was introduced in Scheme and requires handling references to functions as closures instead of bare function pointers,
Жоғары реттік функциялар: функциялар нәтиже ретінде қайтарылады
Функцияны қайтарғанда, біз шын мәнінде оның жабылуын қайтарамыз. C мысалында, жабылуға түсірілген кез келген жергілікті айнымалылар, жабылуды құрастыратын функциядан шыққаннан кейін қолданыстан шығады. Кейіннен жабылуды пайдалануға тырысу белгісіз мінез-құлыққа алып келеді, және ықтимал түрде стекті бұзуы мүмкін. Бұл "жоғары бағытталған аргумент" проблемасы деп аталады.
Функциялардың теңдігі
Теңдік үшін көптеген мәтіндік және мәндерді сынап көре алатындықтан, бағдарламалау тілі функцияларды теңдік үшін сынап көре ала ма деген сұрақ туындайды. Көбірек тексеру кезінде бұл сұрақ қиынырақ болып көрінеді және функция теңдігінің бірнеше түрін ажырату қажет:
Extensional equality Two functions f and g are considered extensionally equal if they agree on their outputs for all inputs (∀x. f(x) = g(x)). Under this definition of equality, for example, any two implementations of a stable sorting algorithm, such as insertion sort and merge sort, would be considered equal. Deciding on extensional equality is undecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality. Intensional equality Under intensional equality, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as the program counter or a mutable global variable.) Reference equality Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaks referential transparency and is therefore not supported in pure languages, such as Haskell.
Экстенциялық теңдік. Егер екі функция f және g барлық кірістер үшін бірдей нәтиже берсе (∀x. f(x) = g(x)), онда олар экстенциялық тұрғыдан тең деп есептеледі. Теңдіктің осы анықтамасы бойынша, мысалы, тұрақты сұрыптау алгоритмінің кез келген екі іске асырылуы, мысалы, енгізу сұрыптау және біріктіру сұрыптау тең деп саналады. Экстенциялық теңдікті анықтау жалпы жағдайда шешілмейді және тіпті шекті домені бар функциялар үшін де көбінесе қиынға соғады. Осы себепті ешбір бағдарламалау тілі функциялық теңдікті экстенциялық теңдік ретінде іске асырмайды.
Extensional equality Two functions f and g are considered extensionally equal if they agree on their outputs for all inputs (∀x. f(x) = g(x)). Under this definition of equality, for example, any two implementations of a stable sorting algorithm, such as insertion sort and merge sort, would be considered equal. Deciding on extensional equality is undecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality. Intensional equality Under intensional equality, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as the program counter or a mutable global variable.) Reference equality Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaks referential transparency and is therefore not supported in pure languages, such as Haskell.
Интенциялық теңдік. Интенциялық теңдік бойынша, егер екі функция f және g бірдей "ішкі құрылымға" ие болса, онда олар тең деп есептеледі. Мұндай теңдік интерпретацияланған тілдерде функциялардың бастапқы кодын (мысалы, Interpreted Lisp 1.5-тегідей) немесе компиляцияланған тілдердегі объектілік кодты салыстыру арқылы іске асырылуы мүмкін. Интенциялық теңдік экстенциялық теңдікті білдіреді (егер функциялар детерминистік болса және жасырын кірістері болмаса, мысалы, бағдарламалық тізімдегіш немесе өзгертілетін жаһандық айнымалы).
Extensional equality Two functions f and g are considered extensionally equal if they agree on their outputs for all inputs (∀x. f(x) = g(x)). Under this definition of equality, for example, any two implementations of a stable sorting algorithm, such as insertion sort and merge sort, would be considered equal. Deciding on extensional equality is undecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality. Intensional equality Under intensional equality, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as the program counter or a mutable global variable.) Reference equality Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaks referential transparency and is therefore not supported in pure languages, such as Haskell.
Анықтамалық теңдік. Экстенциялық және интенциялық теңдікті іске асырудың қиындығын ескере отырып, функцияларды теңдік үшін тексеруді қолдайтын көптеген тілдер анықтамалық теңдікті пайдаланады. Барлық функцияларға немесе жабылуларға бірегей идентификатор (әдетте функция денесінің мекенжайы немесе жабылу) тағайындалады және теңдік идентификатордың теңдігі негізінде анықталады. Екі бөлек анықталған, бірақ басқа жағынан бірдей функция анықтамалары тең емес деп есептеледі. Анықтамалық теңдік интенциялық және экстенциялық теңдікті білдіреді. Анықтамалық теңдік анықтамалық ашықтықты бұзады, сондықтан Хаскелл сияқты таза тілдерде қолдау көрсетілмейді.
Extensional equality Two functions f and g are considered extensionally equal if they agree on their outputs for all inputs (∀x. f(x) = g(x)). Under this definition of equality, for example, any two implementations of a stable sorting algorithm, such as insertion sort and merge sort, would be considered equal. Deciding on extensional equality is undecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality. Intensional equality Under intensional equality, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as the program counter or a mutable global variable.) Reference equality Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaks referential transparency and is therefore not supported in pure languages, such as Haskell.
Тип теориясы
Тип теориясында А типіндегі мәндерді қабылдайтын және В типіндегі мәндерді қайтаратын функциялардың типі A → B немесе BA түрінде жазылуы мүмкін. Кьюри-Ховард сәйкестігінде функция типтері логикалық импликациямен байланысты; лямбда абстракциясы гипотетикалық болжамдарды түсіруге, ал функцияны қолдану modus ponens логикалық ережесіне сәйкес келеді. Бағдарламалау функцияларының қалыпты жағдайынан өзге, тип теориясы ассоциативтік массивлер және осыған ұқсас дерек құрылымдарын модельдеу үшін бірінші класс функцияларын да пайдаланады. Бағдарламалаудың категориялық теориялық тұжырымдамаларында бірінші класс функцияларының болуы жабық категория болжамымен сәйкес келеді. Мысалы, қарапайым типтелген лямбда есептеуі Картезиан жабық категорияларының ішкі тіліне сәйкес келеді.