加利化

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

數學電腦科學入面,加利化粵拼gaa1 lei6 faa3,亦稱加里化;英:currying,加利化咗=curried)就係將一個多輸入值函數變做一串單輸入值函數。譬如,加利化咗一個收三個輸入值嘅函數 就會整到三個函數:

抽象啲嚟講,一個函數收兩個輸入值(一個嚟自 ,一個嚟自 )而出個喺 嘅,呢個函數加利化咗之後,佢就會變第二個函數,而呢個函數會收一個嚟自 嘅輸入值而出一個由 射到 嘅函數。加利化𪐀局部應用褦,但係兩個係唔同概念嚟嘅。

加利化理論同應用上嚟講都有用。喺啲函數程式同其他程式語言入面,佢係攞嚟自動噉處理點將啲輸入值遞落去啲函數同例外。喺理論電腦科學,加利化可以攞嚟研究點將啲多輸入值函數化為淨係收單輸入值嘅簡單模型。最一般而概念上緊密嘅應用範疇就係喺啲閉包幺半範疇,嗰度就可以將褦埋證明程式Curry-Howard對應廣泛噉應用喺好多其他嘅結構,譬如量子力學cobordisms同埋弦理論(string theory)[1]。加利化係由Gottlob Frege[2][3]引入嘅,後嚟再俾Moses Schönfinkel[3][4][5][6]發展,跟住又俾哈士𠵇·加利發展[7][8]

Uncurrying係加利化嘅對偶變換,係用嚟去函數化嘅一種方法。簡單嚟講就係將一個入一個輸入值、出一個函數 嘅函數 化成一個入 嘅輸入值 ,而 嘅輸出值就等同用完 再用 而得出嘅輸出值。噉樣嘅過程係可以重複嘅。

動機[編輯]

加利化提供咗一個途徑嚟到將一個接受幾個輸入值嘅函數應用喺啲淨係收一個輸入值嘅架構度。例如,有啲分析技巧淨係可以喺收一個輸入值嘅先至用到,但係實用嘅函數通常都會收多個一個函數。Frege呢就話揾到單輸入值呢個個案嘅答案就已經夠,因為一個收幾個輸入值嘅函數可以畀人轉換成一串單輸入值函數。呢個轉換呢而家就叫做加利化嘞[9]。全部喺數學分析或者電腦程式編寫「正常」嘅函數冚𠾴唥都係可以加利化嘅。但係,有啲範疇係唔可以加利化到嘅;最廣泛嘅可加利化範疇就係閉包幺半範疇嘞。

有啲程式語言係幾乎無時無刻都會用加利化咗嘅函數嚟達到多個輸入值;顯著嘅例子有MLHaskell,兩者都淨係會用單輸入值函數。攞一串單輸入值函數嚟代多輸入值函數呢個性質係由λ運算遺傳落嚟嘅。

加利化係𪐀局部應用褦嘅,但係兩者唔係完全一樣嘅。實際嚟講,閉包呢啲編程技巧就可以喺一個可以同個加利化咗嘅函數一齊行嘅環境入面遮住啲輸入值,嚟達到局部應用,嚟做加利化嘅一種。

例子[編輯]

假設有個收兩個實數)同出一個實數嘅函數 ,定義佢做 。加利化呢就會將化為一個函數 呢會收一個實數嘅函數 ,同埋出一個喺 嘅函數。用符號嚟講就係 ,其中嘅 係所有收一個實數出一個實數嘅函數嘅集合。跟住,再為每個實數 定義一個函數 ,然之後定義 。舉個例子,就係由 射到 嘅函數,即係 。整體嚟講,我哋可以睇到

從而令到原本嘅同埋加利化咗嘅係含有同樣嘅資訊。喺呢個情況,我哋亦都可以寫

呢個記法用喺其他嘅多輸入值函數都得。如果 係一個收三個輸入值嘅函數 嚟嘅話,噉加利化咗嘅 就會符合以下嘅公式:

歷史[編輯]

英文「Currying」呢個稱呼係由Christopher Strachey喺1967年起嘅[未記出處或冇根據],個稱呼係源於哈士𠵇·加利呢個邏輯學家嘅名。以前都有提倡過要跟Moses Schönfinkel嘅名去叫「Schönfinkelisation」。喺數學呢個範疇入面,「Currying」呢個原則係嚟自Frege喺1893年做嘅嘢。

定義[編輯]

用以下俗而簡嘅定義呢,就會容易理解加利化㗎喇,之後可以再將個定義套用喺唔同嘅領域入面。首先,喺講定義之前,我哋要定咗一啲記法先。呢個記法係講緊所有由 射到 函數。如果 係一個噉嘅函數嚟嘅話,噉我哋就可以記低 。將 攞嚟做 順序對,即係兩者嘅笛卡兒積。喺度呢, 可以係集合、類、或者其他其他款式嘅物件嚟嘅,下面會再探討。

畀一個函數

,

加利化 就會整一個新嘅函數

.

佢係會收個嚟自 嘅數值同出一個由 射去 嘅一個函數,係定義做

其中嘅 分別係嚟自

Uncurrying 就係加利化嘅相反變換,係可以用佢嘅右伴隨函數 嚟容易噉瞭解。

集合論[編輯]

集合論入面, 係攞嚟記低由集合射到集合嘅函數集合。噉加利化呢,就係由 射到 嘅函數集合 同埋由 射到由射到嘅函數集合嘅函數集合之間嘅自然對射。用符號就係

當然,正正就係呢個自然對射先至合理化咗用次方嘅記法嚟寫函數嘅組合。就好似唔同加利化嘅例子噉,上面嘅公式就形容一對伴隨函子:For每個定咗嘅集合嚟講,函子就係函子嘅左伴隨函子。

集合範疇入面,呢個物件係叫做冪對象

函數空間[編輯]

函數空間嘅理論有包泛函分析Homotopy論,主要研究拓撲空間之間嘅連續函數

集合曬所有由 射到 嘅函數而得出嘅集合呢就可以記做同叫做Hom函子。呢度呢, 就係以下嘅對射

而去加利化就係相反嘅映射。如果我哋攞緊緻開拓撲 呢個由 射到 連續函數嘅集合,而空間 局部緊緻Hausdorff嘅話,噉

就係一個同相寫像(homeomorphism)嚟嘅,話之你係咪 緊生成[10](chapter 5)[11],雖然重有其他case[12][13]

噉樣呢就會衍生咗一個推論出嚟:一個函數係連續若且唯若相應嘅加利化函數係連續。另外,平時喺呢個情況叫開「評價」嘅應用映射就會係連續嘅(注意:嚴緊嚟講,「eval」係一個喺電腦科學入面唔𪐀耕嘅概念嚟嘅)。即係如果係緊緻開而係局部緊緻Hausdorff嘅話,噉

就會係連續㗎喇[14]。呢兩個結果對要建立同倫嚟講係中心嘅,即係當 嘅單位間隔,令到 可以一係俾人視為兩個由 射到 嘅函數之間嘅同倫,一係俾人視為喺 嘅一條道路。

代數拓撲[編輯]

領域論[編輯]

Lambda運算[編輯]

類型論[編輯]

邏輯[編輯]

根據Curry-Howard對應,加利化同去加利化嘅存在係等同 呢個邏輯定理,因為多元組積類型)係對應邏輯入面嘅邏輯與(conjunction),而函數類型係對應意味(implication)。

呢個冪對象喺Heyting代數嘅範疇入面同相會寫成 呢個實質條件。分配Heyting代數係布林代數,而 就係個冪對象,所以冪對象就係實質條件[15]

範圍論[編輯]

同局部函數應用嘅[編輯]

內文:局部應用

睇埋[編輯]

[編輯]

  1. John C. Baez and Mike Stay, "Physics, Topology, Logic and Computation: A Rosetta Stone", (2009) ArXiv 0903.0340 in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.
  2. Gottlob Frege, Grundgesetze der Arithmetik I, Jena: Verlag Hermann Pohle, 1893, §36.
  3. 3.0 3.1 Willard Van Orman Quine, introduction to Moses Schönfinkel's "Bausteine der mathematischen Logik", pp. 355–357, esp. 355. Translated by Stefan Bauer-Mengelberg as "On the building blocks of mathematical logic" in Jean van Heijenoort (1967), A Source Book in Mathematical Logic, 1879–1931. Harvard University Press, pp. 355–66.
  4. Strachey, Christopher (2000). "Fundamental Concepts in Programming Languages". Higher-Order and Symbolic Computation. 13: 11–49. doi:10.1023/A:1010000313106. There is a device originated by Schönfinkel, for reducing operators with several operands to the successive application of single operand operators. Unknown parameter |s2cid= ignored (help) (Reprinted lecture notes from 1967.)
  5. Reynolds, John C. (1972). "Definitional Interpreters for Higher-Order Programming Languages". Proceedings of the ACM Annual Conference. 2 (4): 717–740. doi:10.1145/800194.805852. In the last line we have used a trick called Currying (after the logician H. Curry) to solve the problem of introducing a binary operation into a language where all functions must accept a single argument. (The referee comments that although "Currying" is tastier, "Schönfinkeling” might be more accurate.) Unknown parameter |s2cid= ignored (help)
  6. Kenneth Slonneger and Barry L. Kurtz. Formal Syntax and Semantics of Programming Languages. 1995. p. 144.
  7. Henk Barendregt, Erik Barendsen, "Introduction to Lambda Calculus", March 2000, page 8.
  8. Curry, Haskell; Feys, Robert (1958). Combinatory logic. I (第2版). Amsterdam, Netherlands: North-Holland Publishing Company.
  9. Graham Hutton. "Frequently Asked Questions for comp.lang.functional: Currying". nott.ac.uk.
  10. J.P. May, A Concise Course in Algebraic Topology, (1999) Chicago Lectures in Mathematics ISBN 0-226-51183-9
  11. Compactly generated topological space 可以喺 nLab 揾到
  12. P. I. Booth and J. Tillotson, "Monoidal closed, Cartesian closed and convenient categories of topological spaces", Pacific Journal of Mathematics, 88 (1980) pp.33-53.
  13. Convenient category of topological spaces 可以喺 nLab 揾到
  14. Joseph J. Rotman, An Introduction to Algebraic Topology (1988) Springer-Verlag ISBN 0-387-96678-1 (See Chapter 11 for proof.)
  15. Saunders Mac Lane and Ieke Moerdijk, Sheaves in Geometry and Logic (1992) Springer ISBN 0-387-97710-4 (See Chapter 1, pp.48-57)

參考[編輯]

  • Schönfinkel, Moses (1924). "Über die Bausteine der mathematischen Logik". Math. Ann. 92 (3–4): 305–316. doi:10.1007/BF01448013. Unknown parameter |s2cid= ignored (help)
  • Heim, Irene; Kratzer, Angelika (1998). Semantics in a Generative Grammar. Malden: Blackwall Publishers. ISBN 0-631-19712-5.

出面網頁[編輯]