Halo Habr.Hari ini kami menawarkan kepada Anda terjemahan dari artikel yang menyentuh topik yang bukan paling banyak dibahas: kompilasi kode dengan Python, yaitu: bekerja dengan pohon sintaksis abstrak (AST) dan kode byte. Meskipun Python adalah bahasa yang ditafsirkan, fitur-fitur seperti itu sangat penting dari sudut pandang optimasi. Kami akan membicarakannya hari ini.Pernahkah Anda bertanya-tanya bagaimana sebenarnya kompiler mengoptimalkan kode Anda sehingga bekerja lebih cepat? Ingin tahu apa itu pohon sintaksis abstrak (AST) dan untuk apa pohon itu digunakan?Artikel ulasan ini menjelaskan bagaimana kode Python dikonversi ke bentuk pohon (AST). Setelah membangun AST program Anda, Anda dapat melanjutkan untuk mencari optimasi dan transformasi kode Anda. Namun, perlu diingat bahwa mengoptimalkan program Python dengan cara yang tidak sepele sangat sulit .Kode program sebagai pohon
Bagaimana komputer memastikan bahwa ia mengevaluasi ekspresi dari kode Anda dalam urutan yang benar?Untuk melakukan ini, ia terlebih dahulu membuat ulang kode program Anda menjadi struktur pohon yang disebut AST.Ketika bekerja dengan bahasa pemrograman yang ditafsirkan (seperti Python), secara umum diterima bahwa penerjemah melewati kode Anda dan melakukan semua yang ditemuinya, tepat di tempat, tanpa mengubah kode Python menjadi kode mesin dengan cara apa pun. Namun, dalam praktiknya, skema eksekusi ini memicu banyak masalah, yang membuatnya sangat merepotkan.Ambil contoh, masalah sederhana seperti itu sebagai prioritas operator. Dalam ekspresi tampilan 3 + 4 * x , bagian tersebut pertama kali dihitung4 * x, dan hanya dengan demikian 3 dapat ditambahkan ke hasil perkalian. Mungkin Anda belajar diutamakan operator di kelas matematika dengan menggambar pohon-pohon ini di bawah ungkapan:
Python menggunakan aturan standar notasi matematika (perkalian terlebih dahulu, kemudian penambahan). Agar tidak membingungkan apa pun dengan prioritas operator, dengan Python, pada awalnya itu dibangun pohon seperti pada gambar sebelumnya. Operasi umum adalah penambahan (pada akar pohon), dan sementara sisi kiri jumlah ini adalah angka reguler, di sebelah kanan kami memiliki produk. Struktur data yang dihasilkan terlihat seperti ini:BinOp(
left = Num(3),
op = Add(),
right = BinOp(
left = Num(4),
op = Mult(),
right = Name('x')
)
)
BinOpberarti Operasi Biner (Operasi Biner) dan menunjukkan bahwa dalam operasi seperti penambahan dan perkalian - dua operan. Secara alami, Anda tidak akan mendapatkan tambahan apa pun jika bagian yang tepat dari ekspresi tidak memiliki nilai yang benar - karena itu, Anda harus terlebih dahulu menggandakan.Dalam teori kompiler dan bahasa pemrograman, pohon seperti itu disebut Pohon Sintaksis Abstrak , atau AST . AST dalam contoh di atas termasuk dua simpul BinOp, dua simpul, Numdan satu simpul Name.Ada fitur bagus di Python - kemampuan untuk langsung melihat dan menampilkan AST untuk program Python tertentu. Yang diperlukan hanyalah mengimpor modul standarast, parsing program, dan kemudian menampilkan hasilnya di layar (omong-omong, parsing adalah proses mengubah kode sumber program ke pohon AST).import ast
my_tree = ast.parse("3 + 4*x")
print(ast.dump(my_tree))
Namun, Anda akan melihat bahwa akan ada node dan bidang tambahan di AST yang dihasilkan oleh Python, dan itu akan ditampilkan pada satu baris, yang membuatnya tampak lebih rumit pada pandangan pertama daripada yang sebenarnya.Module(body=[Expr(value=BinOp(left=Num(n=3), op=Add(), right=BinOp(left=Num(n=4), op=Mult(), right=Name(id='x', ctx=Load()))))])
Mari kita membaginya menjadi node yang terpisah, seperti terakhir kali - dan buka kembali AST, sudah di atas, sebagai bagian dari keseluruhan pohon:Module(body = [
Expr(
value = BinOp(
left = Num(n=3),
op = Add(),
right = BinOp(
left = Num(n=4),
op = Mult(),
right = Name(id='x', ctx=Load())
)
)
)
])
Jelas, Python "berpikir" bahwa baris yang kami berikan untuk parsing adalah seluruh modul. Tubuh modul adalah daftar semua instruksi yang terkandung di dalamnya. Satu-satunya instruksi dalam contoh kita adalah ekspresi Expryang maknanya persis seperti yang kita bahas di atas.Catatan: simpul Namememiliki bidang tambahan ctx(disingkat "konteks"), yang memiliki nilai Load(). Jadi Python mengatakan bahwa kita menggunakan nilai yang disimpan dalam variabel x, dan tidak (kembali) mendefinisikan atau menghapus nama x. Sekarang langkah Anda, coba parsing sesuatu seperti del xatau diri Anda sendiri x = 123, dan Anda akan melihat bagaimana bidang ctxdalam node Nameberubah menjadi Del()atau Store(), masing-masing.Omong-omong: jika Anda menginstal modulastunparse, maka output AST ke layar dapat dibuat jauh lebih indah, dan bahkan mengubah AST kembali menjadi kode Python langsung.Proses kompilasi: sisanya
Setelah mengumpulkan program AST, pada prinsipnya mungkin untuk menyelesaikan seluruh program dengan melalui AST dan melakukan operasi sesuai urutan yang ditunjukkan. Namun, pendekatan ini setidaknya memiliki dua kelemahan. Pertama, AST dapat menempati jumlah memori yang relatif besar, terutama jika mengandung informasi yang berlebihan. Kedua, AST traversal mungkin membutuhkan waktu lebih lama dari yang diperlukan. Singkatnya: itu bisa dilakukan, tetapi tidak efisien.Compiler tidak memproses AST secara langsung, tetapi menyiapkan bytecode, yang kemudian dieksekusi pada mesin virtual Python. Meskipun membahas detail proses ini berada di luar cakupan artikel ini, prinsip dasarnya adalah bahwa kompiler menerjemahkan AST menjadi notasi Polandia terbalik (RPN). Alih-alih menempatkan operator+antara operan kiri dan kanan, kami meletakkannya setelah kedua operan. Pada contoh di 3 + 4*xatas, kami mendapatkan urutan 3 4 x * +(dan notasi ini sangat baik karena Anda dapat langsung melihat dari urutan: pertama Anda perlu melakukan perkalian, dan hanya kemudian penambahan). Karena masing-masing dari lima elemen dalam urutan ini pada prinsipnya dapat direpresentasikan sebagai byte tunggal, kode tersebut disebut kode byte. Python kemudian menggunakan mesin virtual yang ditumpuk untuk menjalankan kode ini secara efisien.Dengan kata lain, proses penyusunan program yang ditulis dengan Python berlangsung dalam dua tahap. Pertama, program yang diterima oleh input diuraikan, dan hasilnya adalah pohon sintaksis abstrak (AST). Compiler kemudian melewati AST dan menghasilkan bytecode. Setelah itu, interpreter Python mengeksekusi bytecode ini. Setelah melakukan optimasi, ini dapat diterapkan baik pada level AST atau pada level bytecode. Kedua opsi ini memiliki kelebihan dan kekurangannya sendiri.Akhirnya, perlu diingat bahwa meskipun AST umum dalam setiap implementasi Python, proses menerjemahkan AST ke dalam bytecode mungkin berbeda, dan dalam beberapa implementasi Python, katakanlah, JavaScript, daripada bytecode, dapat dihasilkan pada tahap perantara.Paradigma dari bahasa pemrograman lain
Tidak semua bahasa pemrograman menggunakan notasi infiks, seperti pada Python. Dua contoh yang patut dicatat dalam kasus ini adalah PostScript, di mana program ditulis langsung dalam notasi Polandia terbalik, dan Lisp, tentu saja, di mana program biasanya ditulis dalam notasi Polandia. Jadi, ekspresi kita contoh di atas, dalam Lips akan mengambil formulir berikut: (+ 3 (* 4 x)).Konversi simpul dalam AST
Memiliki program AST, bagaimana mengkonversi setiap bagian dari pohon ini? Dengan fitur bawaan Python yang nyaman.Jika kita melihat AST dan, misalnya, menemukan bahwa kedua bidang leftdan rightsimpul BinOpadalah angka (node Num), kita dapat melakukan perhitungan yang sesuai sebelumnya, dan kemudian menggantinya dengan BinOpsimpul normal Num.Tentu saja, Anda harus bertindak sangat hati-hati agar tidak mengubah perilaku program, melakukan transformasi seperti itu. Misalnya, dalam len([a(), b(), c(), d()]), jelas bahwa hasilnya adalah 4. Tapi kita tidak bisa mengganti semua ekspresi nomor 4 karena empat fungsi a, b, c, dmasih benar dipanggil.Sekali lagi, mulailah dengan optimasi sederhana. Di mana pun nama muncul dalam kode sumber program pi, gantilah dengan nilai 3.14159265. Modul Python astsudah menyediakan struktur data yang diperlukan untuk melakukan ini: kelas konverter NodeTransformeryang melewati semua AST dan memeriksa untuk setiap node apakah dapat diganti. Secara default, metode transformasi hanya mengembalikan node sumber untuk setiap node, sehingga kami mendapatkan AST yang sama dengan yang kami mulai. Tetapi kita dapat dengan mudah menimpa metode untuk node Name, katakanlah, sehingga memeriksa untuk pimelihat apakah itu, dan kemudian mengembalikan node Numbukan node dengan nama asli ... import ast
class MyOptimizer(ast.NodeTransformer):
def visit_Name(self, node: ast.Name):
if node.id == 'pi':
return ast.Num(n=3.14159265)
return node
tree = ast.parse("y = 2 * pi")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
print(ast.dump(tree))
Agar konverter / pengoptimal melewati pohon kami, perlu memanggil metode visit, yang kemudian akan mengembalikan pohon baru yang diubah.Sayangnya, tidak mungkin untuk mengkompilasi dan menjalankan AST yang dihasilkan, alasannya adalah satu detail teknis. Ini belum terlihat, tetapi (hampir) semua node di AST juga memiliki bidang linenodan col_offset. Mereka menunjukkan posisi yang tepat dari simpul tertentu dalam kode sumber. Jika Anda tidak menginstalnya dengan benar, kompiler akan bersumpah dan menolak untuk bekerja.Jadi, mari kita salin bidang yang sesuai dari node sumber Nameke node baru Num. Anda kemudian dapat mengkompilasi dan menjalankan AST yang dihasilkan:import ast
class MyOptimizer(ast.NodeTransformer):
def visit_Name(self, node: ast.Name):
if node.id == 'pi':
result = ast.Num(n=3.14159265)
result.lineno = node.lineno
result.col_offset = node.col_offset
return result
return node
tree = ast.parse("print(2 * pi)")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
code = compile(tree, "<string>", "exec")
exec(code)
Catatan: Fungsi kompilasi tidak hanya menuntut kode sumber (di mana bisa menjadi program itu sendiri, atau garis AST), tapi nama file (seperti yang kita diminta "<string>"), serta salah satu dari tiga: "exec", "eval"atau "single".Kebutuhan untuk menyalin bidang yang menggambarkan posisi node dalam kode sumber muncul cukup sering. Oleh karena itu, modul astmemiliki fungsi khusus copy_locationhanya untuk tujuan ini, dan kita dapat menulis:def visit_Name(self, node: ast.Name):
if node.id == 'pi':
result = ast.Num(n=3.14159265)
return ast.copy_location(result, node)
return node
Akhirnya, Anda dapat memperluas contoh sebelumnya sehingga benar-benar melakukan optimasi, yaitu pada node BinOp. Menurut aturan transformasi, pertama-tama kita harus mengubah / mengoptimalkan kiri, dan kemudian simpul kanan sebagai bagian dari BinOp. Jika sebagai hasilnya ternyata kedua node kiri dan kanan adalah angka, maka perhitungan dapat dilakukan tepat di tempat dan mengganti yang asli dengan BinOphasil numerik dari operasi.class MyVisitor(ast.NodeTransformer):
def visit_BinOp(self, node: ast.BinOp):
node.left = self.visit(node.left)
node.right = self.visit(node.right)
if isinstance(node.left, ast.Num) and isinstance(node.right, ast.Num):
if isinstance(node.op, ast.Add):
result = ast.Num(n = node.left.n + node.right.n)
return ast.copy_location(result, node)
elif isinstance(node.op, ast.Mult):
result = ast.Num(n = node.left.n * node.right.n)
return ast.copy_location(result, node)
return node
def visit_Name(self, node: ast.Name):
if node.id == 'pi':
result = ast.Num(n=3.14159265)
return ast.copy_location(result, node)
return node
tree = ast.parse("y = 2 * pi + 1")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
print(ast.dump(tree))
By the way, kompiler CPython sudah mengoptimalkan node BinOpseperti yang ditunjukkan di sini. Kode yang sesuai ditulis dalam C dan diberikan dalam Python / ast_opt.c . Harap perhatikan: Pengoptimal CPython lebih universal dan berfungsi tidak hanya dengan angka, seperti dalam contoh yang kami pertimbangkan, tetapi dengan berbagai jenis nilai konstan.Memeriksa Nodes di AST
Bagaimana cara memastikan bahwa transformasi yang kami lakukan benar? Pertama, Anda perlu mem-bypass AST sepenuhnya dan memeriksa keseluruhan program.Pengoptimal yang disajikan di atas tetap merupakan kesalahan serius. Apa yang terjadi jika Anda mendefinisikan kembali suatu tempat di program pi? Bayangkan saja sesuatu yang sederhana dan dapat dipahami pi = 4. Pengoptimal kami hanya akan mengganti pi di sisi kiri ekspresi dengan nilai numerik 3.14159265, dan Python kemudian akan menolak untuk mengkompilasi karena tidak dapat menetapkan apa pun ke nilai literal.Mungkin inilah perilaku yang Anda cari, menjadikan pi konstanta yang benar, yang diganti selama kompilasi dan tidak pernah dapat dipindahkan, yaitu, ia tidak bisa mendapatkan nilai yang berbeda. Namun, ini jelas melanggar semantik Python.Jadi apa yang harus dilakukan jika kita ingin tetap menggunakan semantik Python, tetapi ganti pi jika memungkinkan? Dalam hal ini, Anda harus terlebih dahulu melewati seluruh program dan memeriksa apakah nilai untuk ditugaskan di suatu tempat pi. Sampai kita memperumitnya: kita tidak akan menggunakan untuk mengganti pi jika setidaknya satu titik dalam program memiliki nilai penugasan pi.Sekarang kita menggunakan node pengunjung, mirip dengan simpul konverter yang dijelaskan di atas. Tidak seperti konverter, pengunjung tidak dimaksudkan untuk mengubah node, ia hanya melewati AST dan memeriksa node (mengunjungi mereka). Dengan demikian, metode kunjungan tidak menghasilkan apa-apa.Dalam kasus kami, kami memeriksa apakah node mengacu Nameke pidan melakukan apa pun selain memuat nilaipi(ingat bidang konteks ctx).import ast
class MyVisitor(ast.NodeVisitor):
def __init__(self):
self.modify_pi = False
def visit_FunctionDef(self, node: ast.FunctionDef):
if node.name == 'pi':
self.modify_pi = True
self.generic_visit(node)
def visit_Name(self, node: ast.Name):
if node.id == 'pi' and not isinstance(node.ctx, ast.Load):
self.modify_pi = True
program = """
def pi():
return 3.1415
print(2 * pi())
"""
tree = ast.parse(program)
my_visitor = MyVisitor()
my_visitor.visit(tree)
print("Pi modified:", my_visitor.modify_pi)
Metode generic_visit(node)ini dipanggil oleh pengunjung untuk setiap simpul yang kami tidak menyediakan metode kunjungan khusus. Dengan kata lain: tidak ada metode seperti itu visit_FunctionDefdi kelas NodeVisitoryang bisa kita panggil menggunakan super(). Mengenai definisi fungsi, kita harus memanggil pengunjung umum untuk memastikan bahwa seluruh isi fungsi juga diproses dengan benar. Jika tidak, kami dapat menyembunyikan instruksi dalam fungsi global pidan mengubah nilainya secara global pi, sehingga pengoptimal kami tidak akan melihat apa pun.Nilai Lokal dalam Python
Metode kami, yang memungkinkan kami untuk menentukan apakah programmer telah mengubah pi, ternyata agak kasar. Namun, kompilator Python bertindak sangat mirip ketika menentukan nama mana dalam lingkup fungsi yang sesuai dengan variabel lokal. Jika suatu variabel berubah di suatu tempat dalam lingkup fungsi (dan tidak secara eksplisit dibuat global, misalnya, menggunakan instruksi global), maka variabel ini dianggap lokal di seluruh cakupan fungsi.Contoh berikut akan dieksekusi dengan baik tanpa baris keempat. Tapi, meskipun x = 0baris keempat tidak pernah dieksekusi, itu masih dianggap tugasx dan karenanya, x menjadi variabel lokal pada skala seluruh fungsi, dan bahkan pada baris 3. Karena itu Python akan bersumpah bahwa variabel x pada baris ketiga belum penting.x = 1
def print_x():
print(x)
if False: x = 0
print_x()
Jika Anda tertarik pada detail cara kerja Python di sini, lihat Python / symtable.c .Kesimpulan
Dalam Python, seperti pada kebanyakan bahasa pemrograman, program tertentu tidak dijalankan langsung dari kode sumber. Bahkan, terjemahan kode sumber berlangsung dalam dua tahap: pertama, pohon sintaksis abstrak (AST) dibuat darinya, dan kemudian kode byte untuk mesin virtual yang ditumpuk. Python juga menyediakan sejumlah fitur yang sangat bagus untuk menganalisis dan bahkan mengubah AST dari program Python tertentu, setelah itu AST yang dimodifikasi dapat dikompilasi dan dieksekusi. Dengan demikian, kami dapat dengan mudah menerapkan optimasi kami sendiri.Tentu saja, saya hanya menghilangkan banyak detail di sini. Untuk memastikan bahwa optimasi Anda akan berfungsi dengan benar dalam semua kasus dan keadaan yang mungkin adalah masalah yang sangat sepele. Namun, tujuan artikel ini bukan untuk memberi tahu Anda tentang pengoptimalan yang siap digunakan dalam produksi, tetapi untuk memberikan gagasan dasar tentang bagaimana Python menganalisis kode program Anda sehingga Anda dapat mempelajari cara mengonversi dengan benar dan kemudian mengoptimalkannya.