Функция аргументтері мәселесі: стек негізіндегі жадты басқарудағы қиындықтар
Funarg problem
Функция аргументі мәселесі: программалау тілдеріндегі функцияларды бірінші класс объектілер ретінде жүзеге асырудағы қиындықтар, жабылулар (closures) және стектік жадты пайдалану.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда funarg мәселесі (функция аргументі мәселесі) – функцияларды бірінші сыныптық объектілер ретінде бағдарламалау тілінің іске асырылуында жүзеге асыру кезінде туындайтын қиындықтарды білдіреді, осылайша функциялар үшін стекке негізделген жадты бөлуді пайдалану мүмкін болады. Бұл қиындық тек қана егер ішкі функцияның коды функция анықталған ортадағы идентификаторларға тікелей (яғни, аргументтер арқылы емес) сілтеме жасаса, бірақ функция шақырылған ортада емес, ғана туындайды. Стандартты шешім – мұндай сілтемелерге тыйым салу немесе жабуларды (closures) қолдану. Funarg мәселесінің екі аздап өзгешеленетін түрі бар. Funarg жоғары мәселесі функция шақырудан функцияны қайтарудан (немесе басқа жолмен "жоғары" жіберуден) туындайды. Funarg төмен мәселесі функцияны басқа функцияға параметр ретінде беруден туындайды.
In computer science, the funarg problem (function argument problem) refers to the difficulty in implementing first class functions (functions as first class objects) in programming language implementations so as to use stack based memory allocation of the functions. The difficulty only arises if the body of a nested function refers directly (i. e., not by argument passing) to identifiers defined in the environment in which the function is defined, but not in the environment of the function call. A standard resolution is either to forbid such references or to create closures. There are two subtly different versions of the funarg problem. The upwards funarg problem arises from returning (or otherwise transmitting "upwards") a function from a function call. The downwards funarg problem arises from passing a function as a parameter to another function call.
Жоғарыға көтерілу
Функция басқа функцияны шақырғанда, шақырушы функцияның жергілікті күйі (параметрлер мен жергілікті айнымалыларды қоса) сақталуы керек, сонда шақырылған функция қайтқаннан кейін орындалу жалғасады. Көптеген компиляцияланған бағдарламаларда бұл жергілікті күй шақыру стегінде стек фреймі немесе белсендіру жазбасы деп аталатын деректер құрылымында сақталады. Бұл стек фреймі басқа функцияны шақыру алдында түртіледі немесе бөлінеді, ал шақырылған функция шақырушы функцияға қайтқанда ашылады немесе босатылады. Көтерілген funarg мәселесі шақырушы функция шақырылған/шығып кеткен функцияның күйіне функция қайтқаннан кейін сілтеме жасағанда туындайды. Сондықтан, шақырылған функцияның күй айнымалыларын қамтитын стек фреймін функция қайтқанда босатуға болмайды, өйткені бұл стекке негізделген функция шақыру парадигмасын бұзады. Көтерілген funarg мәселесін шешудің бір жолы – барлық белсендіру жазбаларын стек емес, үймеден бөлу және оларды қажет болмай қалғанда босату үшін қоқыс жинау немесе сілтемелерді санаудың қандай да бір түрін пайдалану. Үймеде белсендіру жазбаларын басқару тарихи түрде стектегіден тиімсіз деп есептелген (бірақ бұл толығымен дұрыс емес) және оның іске асыруы күрделі болып көрінеді. Типтік бағдарламалардың көпшілігі (функционалдық бағдарламалау тілдеріндегі бағдарламаларға қарағанда) көтерілген funarg-тар жасамайды, бұл олардың іске асырылуымен байланысты ықтимал қосымша шығындар туралы алаңдаушылықты арттырады. Сонымен қатар, бұл тәсіл қоқыс жинауды қолдамайтын тілдерде қиынға түседі. Кейбір тиімділікке бағытталған компиляторлар гибридтік тәсілді қолданады, онда функцияның белсендіру жазбалары, егер компилятор статикалық бағдарламалық талдау арқылы функция көтерілген funarg-тар жасамайтынын анықтаса, стекте бөлінеді. Әйтпесе, белсендіру жазбалары үймеде бөлінеді. Басқа шешім – жабылу жасалған кезде айнымалылардың мәнін жабылуға көшіру. Бұл өзгертілетін айнымалылар үшін әртүрлі мінез-құлыққа әкеледі, өйткені күй енді жабылулар арасында ортақ болмайды. Бірақ егер айнымалылар тұрақты екені белгілі болса, онда бұл тәсіл эквивалентті болады. ML тілдері осы тәсілді қолданады, өйткені осы тілдердегі айнымалылар мәндерге байланысты, яғни айнымалыларды өзгертуге болмайды. Java да анонимді сыныптарға (және Java 8-ден бастап lambda-ларға) қатысты осы тәсілді қолданады, ол тек шектеулі ауқымдағы нақты соңғы (яғни тұрақты) айнымалыларға сілтеме жасауға мүмкіндік береді. Кейбір тілдер бағдарламашыға екі мінез-құлықтың бірін нақты таңдауға мүмкіндік береді. PHP 5.3-тегі анонимді функциялар қандай айнымалыларды жабылуға қосу керектігін `use` сөйлемі арқылы көрсетуді талап етеді; егер айнымалы сілтеме арқылы тізімделген болса, ол бастапқы айнымалыға сілтеме береді; әйтпесе, ол мәнді береді. Apple's Blocks анонимді функцияларында жергілікті айнымалылар әдепкі бойынша мән бойынша түсіріледі; егер күйді жабылулар арасында немесе жабылу мен сыртқы ауқым арасында бөлісу қажет болса, айнымалы `block` модификаторымен жариялануы керек, бұл жағдайда бұл айнымалы үймеде бөлінеді.
When one function calls another during a typical program's execution, the local state of the caller (including parameters and local variables) must be preserved in order for execution to proceed after the callee returns. In most compiled programs, this local state is stored on the call stack in a data structure called a stack frame or activation record. This stack frame is pushed, or allocated, as prelude to calling another function, and is popped, or deallocated, when the other function returns to the function that did the call. The upwards funarg problem arises when the calling function refers to the called/exited function's state after that function has returned. Therefore, the stack frame containing the called function's state variables must not be deallocated when the function returns, violating the stack based function call paradigm. One solution to the upwards funarg problem is to simply allocate all activation records from the heap instead of the stack and rely on some form of garbage collection or reference counting to deallocate them when they are no longer needed. Managing activation records on the heap has historically been perceived to be less efficient than on the stack (although this is partially contradicted) and has been perceived to impose significant implementation complexity. Most functions in typical programs (less so for programs in functional programming languages) do not create upwards funargs, adding to concerns about potential overhead associated with their implementation. Furthermore, this approach is genuinely difficult in languages that do not support garbage collection. Some efficiency minded compilers employ a hybrid approach in which the activation records for a function are allocated from the stack if the compiler is able to deduce, through static program analysis, that the function creates no upwards funargs. Otherwise, the activation records are allocated from the heap. Another solution is to simply copy the value of the variables into the closure at the time the closure is created. This will cause a different behavior in the case of mutable variables, because the state will no longer be shared between closures. But if it is known that the variables are constant, then this approach will be equivalent. The ML languages take this approach, since variables in those languages are bound to values—i. e. variables cannot be changed. Java also takes this approach with respect to anonymous classes (and lambdas since Java 8), in that it only allows one to refer to variables in the enclosing scope that are effectively final (i. e. constant). Some languages allow the programmer to explicitly choose between the two behaviors. PHP 5.3's anonymous functions require one to specify which variables to include in the closure using the use clause; if the variable is listed by reference, it includes a reference to the original variable; otherwise, it passes the value. In Apple's Blocks anonymous functions, captured local variables are by default captured by value; if one wants to share the state between closures or between the closure and the outside scope, the variable must be declared with the block modifier, in which case that variable is allocated on the heap.
Төменге қарай көшу проблемасы
Төменге қарай funarg функцияның іс жүзінде орындалмаған күйін де білдіре алады. Бірақ, анықтама бойынша, төменге қарай funarg-тың болуы оны жасайтын функцияның орындалуында қамтылғандықтан, функцияның стек фреймін көбінесе стекте сақтауға болады. Дегенмен, төменге қарай funarg-тардың болуы бағдарлама күйі туралы адам мен машинаның ойлауын қиындататын жабылулар мен стек фреймдердің ағаш тәрізді құрылымын білдіреді. Төменге қарай funarg мәселесі құйрық шақыруларды және жалғастыру стилінде жазылған кодты тиімді компиляциялауды қиындатады. Мұндай ерекше жағдайларда, бағдарламашының ниеті (көбінесе) функцияның шектеулі стек кеңістігінде жұмыс істеуі болады, сондықтан "жылдам" әрекет шын мәнінде қажет емес болуы мүмкін.
A downwards funarg may also refer to a function's state when that function is not actually executing. However, because, by definition, the existence of a downwards funarg is contained in the execution of the function that creates it, the stack frame for the function can usually still be stored on the stack. Nonetheless, the existence of downwards funargs implies a tree structure of closures and stack frames that can complicate human and machine reasoning about the program state. The downwards funarg problem complicates the efficient compilation of tail calls and code written in continuation passing style. In these special cases, the intent of the programmer is (usually) that the function run in limited stack space, so the "faster" behavior may actually be undesirable.
Практикалық әсері
Тарихи тұрғыдан алғанда, жоғары қарайғы funarg проблемасы көбінесе қиынға соқты. Мысалы, Паскаль бағдарламалау тілі функцияларды аргумент ретінде беруге мүмкіндік береді, бірақ нәтиже ретінде қайтаруға жол бермейді; сондықтан Паскальдің іске асырылымдары төменгі қарайғы funarg проблемасын шешуге міндетті, бірақ жоғары қарайғысын емес. Modula 2 және Oberon бағдарламалау тілдері (Паскальдің ұрпақтары) функцияларды параметрлер ретінде де, қайтарым мәндері ретінде де қолдануға рұқсат береді, бірақ тағайындалған функция ішкі функция болмауы мүмкін. C бағдарламалау тілі тарихи тұрғыдан функция анықтамаларын іштей орналастыруға жол бермеу арқылы funarg проблемасының негізгі қиындығынан қашады; өйткені әрбір функцияның ортасы бірдей болады, тек статикалық түрде бөлінген жаһандық айнымалылар мен функцияларды қамтиды, ал функция кодына сілтеме функцияны толыққанды сипаттайды. Apple C үшін жабылу синтаксисін ұсынды және іске қосты, ол қажет болған жағдайда жабылуларды стектен үймеге динамикалық түрде жылжыту арқылы жоғары қарайғы funarg проблемасын шешеді. Java бағдарламалау тілі анонимді ішкі және жергілікті сыныптардағы ішкі функциялар қолданатын контексті соңғы деп жариялауды, ал lambda өрнектерінде қолданылатын контексті тиімді түрде соңғы болуын талап ету арқылы осы мәселені шешеді. C# және D тілдерінде функция көрсеткіші мен байланысты айнымалыларды қоршап тұратын lambda-лар (жабылулар) бар. Функционалдық тілдерде функциялар – кез келген жерге жіберілуі мүмкін бірінші сыныптық мәндер. Осылайша, Scheme немесе Standard ML іске асырылымдары жоғары және төменгі қарайғы funarg проблемаларын екеуін де шешуі керек. Бұл әдетте функция мәндерін үймеге бөлінген жабылу ретінде көрсету арқылы жүзеге асырылады, бұрын сипатталғандай. OCaml компиляторы тиімділікті арттыру үшін гибридтік әдіс қолданады (статикалық бағдарламалық талдау негізінде).
Historically, the upwards funarg problem has proven to be more difficult. For example, the Pascal programming language allows functions to be passed as arguments but not returned as results; thus implementations of Pascal are required to address the downwards funarg problem but not the upwards one. The Modula 2 and Oberon programming languages (descendants of Pascal) allow functions both as parameters and return values, but the assigned function may not be a nested function. The C programming language historically avoids the main difficulty of the funarg problem by not allowing function definitions to be nested; because the environment of every function is the same, containing just the statically allocated global variables and functions, a pointer to a function's code describes the function completely. Apple has proposed and implemented a closure syntax for C that solves the upwards funarg problem by dynamically moving closures from the stack to the heap as necessary. The Java programming language deals with it by requiring that context used by nested functions in anonymous inner and local classes be declared final, and context used by lambda expressions be effectively final. C# and D have lambdas (closures) that encapsulate a function pointer and related variables. In functional languages, functions are first class values that can be passed anywhere. Thus, implementations of Scheme or Standard ML must address both the upwards and downwards funarg problems. This is usually accomplished by representing function values as heap allocated closures, as previously described. The OCaml compiler employs a hybrid technique (based on static program analysis) to maximize efficiency.