基於 Python 型別提示檢查不可變性

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：5

、訪客IP：18.191.5.239

姓名

林右展(You-Zhan Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

基於 Python 型別提示檢查不可變性
(Checking Immutability using Python Type Hints)

相關論文

★ 條件判斷式事件驅動程式設計之C語言擴充	★ 基于小波变换的指纹活度检测,具有聚集 LPQ 和 LBP 特征
★ 應用自動化測試於異質環境機器學習管道之 MLOps 系統	★ 設計具有可視化思維工具和程式作為單一步的輔助學習程式之棋盤式遊戲
★ TOCTOU 漏洞的靜態分析與實作	★ 用於繪製風力發電控制邏輯之特定領域語言
★ 在Java程式語言中以雙向結構表達數學公式間關聯之設計與實作	★ 支援模組化規則製作之程式碼轉換工具
★ 基於替代語意的 pandas DataFrame 靜態型別檢查器	★ 自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗
★ 以震波層析成像為應用之特定領域語言實作與分析	★ 用特徵選擇減少疲勞偵測腦電圖通道數
★ 一個應用紙本運算與數位化於程式設計學習使程序性思維可視化的機制	★ 基於抽象語法樹的陣列形狀錯誤偵測
★ 從合作學習角色分工獲得函式程式設計思維學習遞迴程式的機制	★ 基於抽象語法樹的深度複製及彈性別名之所有權系統解決 Java 表示暴露問題

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2028-7-27以後開放)

摘要(中)

程式語言在不可變性的支援對程式開發流程相當有幫助，特別是對指令式的物件導向程式語言來說。
透過不可變性限制物件的狀態，不僅能更容易理解程式的執行流程，若使用適當，更能減少程式開發過程中尋找與去除程式錯誤的時間。
對於不可變性支援程度較低的程式語言，過去有許多研究在該語言的型別或注釋系統上加入新的型別或注釋，藉此標記變數、函式、類別等結構的不可變性。
Python 雖已支援部分不可變類別的建立方式與不可變型別提示的使用，但仍存在一些使用上的不容易。

因此本研究在 Python 中加入一個新的型別提示 Frozen。
透過將 Frozen 標記在變數、參數、屬性等名稱上，便可以使用靜態檢查工具來檢測這些變數是否被用於修改其對應的物件。
這樣做可以提升程式的正確性、加速錯誤的排除，從而使程式開發流程更加順暢。

摘要(英)

Language supports for immutability in programming languages can benefit the software development process,
especially in imperative object-oriented programming languages.
By enforcing immutability and restricting the modification of objects′ states,
it becomes easier to understand the program′s execution flow.
When used appropriately, immutability can also reduce the time spent on finding and fixing program errors.
For programming languages with limited support for immutability,
there has been research in the past on introducing new types or annotations within the language′s type or annotation system.
These additions aim to mark the immutability of variables, functions, classes, and other structures.
Although Python already supports the creation of immutable classes and the type hints of partial immutable types,
there are still some challenges in practice that make it less straightforward.

Therefore, this research introduces a new type hint in Python called "Frozen."
By applying the "Frozen" to variables, parameters, attributes, and other identifiers, static analysis tools can be used to detect
if these variables are used to modify their corresponding objects.
This approach makes the software development process smoother.

關鍵字(中)

★ 不可變性
★ 型別提示
★ 靜態分析
★ Python

關鍵字(英)

★ Immutability
★ Type Hints
★ Static Analysis
★ Python

論文目次

一、緒論 1
1.1 物件導向與物件的使用 ................. 1
1.2 對於物件的意外變更 ................... 2
1.3 Python 的型別系統 .................... 3
1.4 Python 的型別提示 .................... 5
1.5 其他語言的型別注釋 ................... 7
1.6 論文架構 ............................. 8

二、動機 9
2.1 Python 當前提供不可變性的方法 ........ 9
2.2 既存方法的缺點 ....................... 12

三、提案 15
3.1 語法 ................................. 15
3.2 語意與使用範例 ....................... 17

四、實作 19
4.1 實作概觀 ............................. 19
4.2 抽象語法樹分析 ....................... 21

五、評估 27
5.1 彌補 Python 既存方法的不足 ........... 27
5.2 靜態檢查所需時間 ..................... 28
5.3 不可變性評估 ......................... 32
5.4 本提案與既存方法的比較 ............... 37

六、相關研究 40
6.1 別名問題 ............................. 40
6.2 其他語言的不可變性支援 ............... 41

七、總結 43

八、未來展望 45
8.1 別名問題 ............................. 45
8.2 支援對類別使用的裝飾詞 frozen ........ 46
8.3 支援不可變性的推論 ................... 47

參考文獻 48

參考文獻

[1] C. Böhm and G. Jacopini, “Flow diagrams, turing machines and languages with
only two formation rules,” Commun. ACM, vol. 9, no. 5, pp. 366–371, May 1966,
issn: 0001-0782. doi: 10.1145/355592.365646. [Online]. Available: https://doi.
org/10.1145/355592.365646.
[2] E. W. Dijkstra, “Letters to the editor: Go to statement considered harmful,” Com-
mun. ACM, vol. 11, no. 3, pp. 147–148, Mar. 1968, issn: 0001-0782. doi: 10.1145/
362929.362947. [Online]. Available: https://doi.org/10.1145/362929.362947.
[3] A. Goldberg and D. Robson, Smalltalk-80: the language and its implementation.
Addison-Wesley Longman Publishing Co., Inc., 1983.
[4] O.-J. Dahl, “The roots of object orientation: The simula language,” Software Pio-
neers: Contributions to Software Engineering, pp. 78–90, 2002.
[5] C. A. R. Hoare, “Record handling,” ALGOL Bull., no. 21, pp. 39–69, Nov. 1965,
issn: 0084-6198.
[6] J. Hughes, “Why functional programming matters,” The computer journal, vol. 32,
no. 2, pp. 98–107, 1989.
[7] S. Artzi, J. Quinonez, A. Kieżun, and M. D. Ernst, “Parameter reference immutabil-
ity: Formal definition, inference tool, and comparison,” Automated Software Engi-
neering, vol. 16, no. 1, pp. 145–192, Mar. 2009.
[8] M. Coblenz, J. Sunshine, J. Aldrich, B. Myers, S. Weber, and F. Shull, “Explor-
ing language support for immutability,” in Proceedings of the 38th International
Conference on Software Engineering, ser. ICSE ’16, Austin, Texas: Association for
Computing Machinery, 2016, pp. 736–747, isbn: 9781450339001. doi: 10.1145/
2884781 . 2884798. [Online]. Available: https : / / doi . org / 10 . 1145 / 2884781 .
2884798.
[9] J. Eyolfson and P. Lam, “How c++ developers use immutability declarations: An
empirical study,” in 2019 IEEE/ACM 41st International Conference on Software
Engineering (ICSE), 2019, pp. 362–372. doi: 10.1109/ICSE.2019.00050.
[10] S. Meyers, Effective C++: 55 specific ways to improve your programs and designs.
Pearson Education, 2005.
[11] M. S. Tschantz and M. D. Ernst, “Javari: Adding reference immutability to java,”
SIGPLAN Not., vol. 40, no. 10, pp. 211–230, Oct. 2005, issn: 0362-1340. doi:
10.1145/1103845.1094828. [Online]. Available: https://doi.org/10.1145/
1103845.1094828.
[12] W. Huang, A. Milanova, W. Dietl, and M. D. Ernst, “Reim amp; reiminfer: Check-
ing and inference of reference immutability and method purity,” SIGPLAN Not.,
vol. 47, no. 10, pp. 879–896, Oct. 2012, issn: 0362-1340. doi: 10.1145/2398857.
2384680. [Online]. Available: https://doi.org/10.1145/2398857.2384680.
[13] Y. Zibin, A. Potanin, M. Ali, S. Artzi, A. Kie|un, and M. D. Ernst, “Object and
reference immutability using java generics,” in Proceedings of the the 6th Joint
Meeting of the European Software Engineering Conference and the ACM SIG-
SOFT Symposium on The Foundations of Software Engineering, ser. ESEC-FSE
’07, Dubrovnik, Croatia: Association for Computing Machinery, 2007, pp. 75–84,
isbn: 9781595938114. doi: 10.1145/1287624.1287637. [Online]. Available: https:
//doi.org/10.1145/1287624.1287637.
[14] Y. Zibin, A. Potanin, P. Li, M. Ali, and M. D. Ernst, “Ownership and immutability
in generic java,” SIGPLAN Not., vol. 45, no. 10, pp. 598–617, Oct. 2010, issn: 0362-
1340. doi: 10.1145/1932682.1869509. [Online]. Available: https://doi.org/10.
1145/1932682.1869509.
[15] J. Boyland, J. Noble, and W. Retert, “Capabilities for sharing,” in ECOOP 2001
— Object-Oriented Programming, J. L. Knudsen, Ed., Berlin, Heidelberg: Springer
Berlin Heidelberg, 2001, pp. 2–27, isbn: 978-3-540-45337-6.
[16] M. Coblenz, W. Nelson, J. Aldrich, B. Myers, and J. Sunshine, “Glacier: Transitive
class immutability for java,” in 2017 IEEE/ACM 39th International Conference on
Software Engineering (ICSE), May 2017, pp. 496–506. doi: 10.1109/ICSE.2017.
52.
[17] “Built-in types - python 3.11.4.” (), [Online]. Available: https://docs.python.
org/3/library/stdtypes.html (visited on 06/10/2022).
[18] A. Takikawa, T. S. Strickland, C. Dimoulas, S. Tobin-Hochstadt, and M. Felleisen,
“Gradual typing for first-class classes,” SIGPLAN Not., vol. 47, no. 10, pp. 793–810,
Oct. 2012, issn: 0362-1340. doi: 10.1145/2398857.2384674. [Online]. Available:
https://doi.org/10.1145/2398857.2384674.
[19] G. van Rossum, J. Lehtosalo, and Ł. Langa. “Pep 484 –type hints.” (Sep. 2014),
[Online]. Available: https://peps.python.org/pep-0484/ (visited on 05/26/2023).
[20] J. Siek and W. Taha, “Gradual typing for objects,” in ECOOP 2007 – Object-
Oriented Programming, E. Ernst, Ed., Berlin, Heidelberg: Springer Berlin Heidel-
berg, 2007, pp. 2–27, isbn: 978-3-540-73589-2.
[21] “Mypy: Static typing for python.” (), [Online]. Available: https : / / www . mypy -
lang.org/ (visited on 05/31/2022).
[22] “Pyright.” (), [Online]. Available: https : / / github . com / microsoft / pyright
(visited on 05/31/2022).
[23] M. M. Vitousek, A. M. Kent, J. G. Siek, and J. Baker, “Design and evaluation of
gradual typing for python,” in Proceedings of the 10th ACM Symposium on Dynamic
Languages, ser. DLS ’14, Portland, Oregon, USA: Association for Computing Ma-
chinery, 2014, pp. 45–56, isbn: 9781450332118. doi: 10.1145/2661088.2661101.
[Online]. Available: https://doi.org/10.1145/2661088.2661101.
[24] M. M. Vitousek, C. Swords, and J. G. Siek, “Big types in little runtime: Open-
world soundness and collaborative blame for gradual type systems,” in Proceedings
of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages,
ser. POPL ’17, Paris, France: Association for Computing Machinery, 2017, pp. 762–
774, isbn: 9781450346603. doi: 10.1145/3009837.3009849. [Online]. Available:
https://doi.org/10.1145/3009837.3009849.
[25] M. J. Sullivan and I. Levkivsky. “Pep 591 –adding a final qualifier to typing.”
(Mar. 2019), [Online]. Available: https://peps.python.org/pep-0591/ (visited
on 05/29/2023).
[26] A. Chaudhuri, P. Vekris, S. Goldman, M. Roch, and G. Levi, “Fast and precise
type checking for javascript,” Proc. ACM Program. Lang., vol. 1, no. OOPSLA,
Oct. 2017. doi: 10.1145/3133872. [Online]. Available: https://doi.org/10.
1145/3133872.
[27] S. Tobin-Hochstadt and M. Felleisen, “The design and implementation of typed
scheme,” in Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Sympo-
sium on Principles of Programming Languages, ser. POPL ’08, San Francisco,
California, USA: Association for Computing Machinery, 2008, pp. 395–406, isbn:
9781595936899. doi: 10.1145/1328438.1328486. [Online]. Available: https://
doi.org/10.1145/1328438.1328486.
[28] B. Greenman, C. Dimoulas, and M. Felleisen, “Typed–untyped interactions: A
comparative analysis,” ACM Trans. Program. Lang. Syst., vol. 45, no. 1, Mar.
2023, issn: 0164-0925. doi: 10.1145/3579833. [Online]. Available: https://doi.
org/10.1145/3579833.
[29] “Dataclasses —data classes.” (), [Online]. Available: https://docs.python.org/
3/library/dataclasses.html (visited on 06/08/2022).
[30] “Glossary —python 3.11.4.” (), [Online]. Available: https://docs.python.org/
3/glossary.html#term-decorator (visited on 06/08/2022).
[31] “Built-in exceptions —python 3.11.4 documentation.” (), [Online]. Available: https:
//docs.python.org/3/library/exceptions.html (visited on 07/05/2022).
[32] E. V. Smith. “Pep 557 –data classes.” (Jun. 2017), [Online]. Available: https :
//peps.python.org/pep-0557/ (visited on 05/26/2023).
[33] “Flake8: Your tool for style guide enforcement.” (), [Online]. Available: https :
//flake8.pycqa.org/en/latest/ (visited on 06/07/2022).
[34] “References and borrowing.” (), [Online]. Available: https://pypi.org/project/
pyflakes/ (visited on 06/08/2022).
[35] “Pep 8 –style guide for python code.” (), [Online]. Available: https : / / peps .
python.org/pep-0008/ (visited on 06/08/2022).
[36] “Mccabe - code complexity checker.” (), [Online]. Available: https : / / here -
be - pythons . readthedocs . io / en / latest / python / mccabe . html (visited on
06/08/2022).
[37] “Ast-abstract syntax trees.” (), [Online]. Available: https://docs.python.org/
3/library/ast.html (visited on 06/07/2022).
[38] “The python performance benchmark suite.” (), [Online]. Available: https : / /
pyperformance.readthedocs.io/ (visited on 07/11/2022).
[39] J. Hogg, D. Lea, A. Wills, D. deChampeaux, and R. Holt, “The geneva convention
on the treatment of object aliasing,” SIGPLAN OOPS Mess., vol. 3, no. 2, pp. 11–
16, Apr. 1992, issn: 1055-6400. doi: 10.1145/130943.130947. [Online]. Available:
https://doi.org/10.1145/130943.130947.
[40] D. G. Clarke, J. M. Potter, and J. Noble, “Ownership types for flexible alias protec-
tion,” in Proceedings of the 13th ACM SIGPLAN Conference on Object-Oriented
Programming, Systems, Languages, and Applications, ser. OOPSLA ’98, Vancouver,
British Columbia, Canada: Association for Computing Machinery, 1998, pp. 48–64,
isbn: 1581130058. doi: 10 . 1145 / 286936 . 286947. [Online]. Available: https :
//doi.org/10.1145/286936.286947.
[41] T. Jim, J. G. Morrisett, D. Grossman, M. W. Hicks, J. Cheney, and Y. Wang,
“Cyclone: A safe dialect of c.,” in USENIX Annual Technical Conference, General
Track, 2002, pp. 275–288.
[42] C. Boyapati, “Safejava: A unified type system for safe programming,” Ph.D. dis-
sertation, Massachusetts Institute of Technology, 2003.
[43] A. Potanin, J. Noble, D. Clarke, and R. Biddle, “Generic ownership for generic
java,” in Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-
Oriented Programming Systems, Languages, and Applications, ser. OOPSLA ’06,
Portland, Oregon, USA: Association for Computing Machinery, 2006, pp. 311–324,
isbn: 1595933484. doi: 10.1145/1167473.1167500. [Online]. Available: https:
//doi.org/10.1145/1167473.1167500.
[44] M. Skoglund and T. Wrigstad, “A mode system for read-only references in java,”
Jan. 2001.
[45] A. Potanin, J. Östlund, Y. Zibin, and M. D. Ernst, “Immutability,” in Aliasing
in Object-Oriented Programming. Types, Analysis and Verification, D. Clarke, J.
Noble, and T. Wrigstad, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013,
pp. 233–269, isbn: 978-3-642-36946-9. doi: 10 . 1007 / 978 - 3 - 642 - 36946 - 9 _ 9.
[Online]. Available: https://doi.org/10.1007/978-3-642-36946-9_9.
[46] “References and borrowing.” (), [Online]. Available: https://doc.rust- lang.
org/book/ch04-02-references-and-borrowing.html (visited on 06/08/2022).
[47] J. Quinonez, M. S. Tschantz, and M. D. Ernst, “Inference of reference immutabil-
ity,” in ECOOP 2008 – Object-Oriented Programming, J. Vitek, Ed., Berlin, Hei-
delberg: Springer Berlin Heidelberg, 2008, pp. 616–641, isbn: 978-3-540-70592-5.
[48] T. Roth, D. Helm, M. Reif, and M. Mezini, “Cifi: Versatile analysis of class and field
immutability,” in 2021 36th IEEE/ACM International Conference on Automated
Software Engineering (ASE), 2021, pp. 979–990. doi: 10.1109/ASE51524.2021.
9678903.

指導教授

莊永裕(Yung-Yu Zhuang)

審核日期

2023-7-28

推文