Semuanya adalah Fungsi: Ulasan kuliah David Beazley dan SICP

 (ezzeriesa.notion.site)
2 poin oleh GN⁺ 2024-11-18 | 1 komentar | Bagikan ke WhatsApp

Ulasan kuliah David Beazley dan SICP: pengalaman selama 1 minggu

Saya membagikan pengalaman mengikuti kuliah SICP oleh David Beazley pada akhir 2022. Meski ada banyak materi gratis, kuliah Dave sangat efektif karena memilih topik-topik tertentu dan menjelaskannya secara mendalam.

Titik awal

Kuliah SICP menggunakan bahasa Scheme, dan di sini dijelaskan konsep dasar model substitusi dengan mengimplementasikan interpreter Scheme sederhana dalam Python.

Dasar-dasar bahasa Scheme

  • Primitive: nilai-nilai dasar (misalnya bilangan bulat)
  • Operator: operasi dasar seperti +, -, *, / menggunakan notasi prefiks
  • define: definisi variabel
> (define x 2)  
> (+ x 3) ; hasil: 5
  • if: pernyataan kondisi
  • lambda: definisi fungsi anonim
> ((lambda (x) (* x x)) 3) ; hasil: 9

Interpreter Scheme di Python

Mengimplementasikan interpreter sederhana untuk mengevaluasi kode Scheme dengan Python. Operasi dasar didefinisikan sebagai fungsi Python.

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}

Contoh:

> evaluate(("+", 2, 3)) # hasil: 5

Juga mencakup implementasi define dan lambda, serta penanganan pernyataan kondisi if.

Model substitusi (Substitution Model)

Model substitusi adalah cara sederhana untuk menafsirkan program, dengan mengevaluasinya sambil mengganti variabel dengan nilainya. Namun, model ini gagal ketika assignment disertakan.

Status (State)

Contoh yang membuat model substitusi runtuh adalah assignment. Misalnya, saat memodelkan saldo rekening bank, set! digunakan untuk memperbarui variabel.

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)

Dalam kasus ini, model substitusi tidak dapat membedakan keadaan saldo sebelum dan sesudahnya.

Model environment pun menjadi diperlukan. Variabel didefinisikan di dalam environment, dan setiap prosedur memiliki environment-nya sendiri.

Stream

Ada juga stream sebagai cara lain untuk memodelkan status. Stream dapat memodelkan nilai masa depan melalui evaluasi malas (lazy evaluation).

Loop tak berhingga dan urutan evaluasi

Perbedaan urutan evaluasi: sebagian besar bahasa menggunakan applicative-order evaluation dengan mengevaluasi argumen terlebih dahulu.

> (square (+ 1 2)) ; hasil: 9

Namun, normal-order evaluation menunda evaluasi hingga argumen benar-benar diperlukan. Karena itu, loop tak berhingga bisa dihindari.

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; pada normal-order mengembalikan 0, pada applicative-order menjadi loop tak berhingga

Lambda calculus dan bilangan Church

Melalui Church encoding, angka dapat direpresentasikan sebagai prosedur. Ini adalah konsep penting dalam pemrograman fungsional.

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))
  • zero adalah fungsi yang mengembalikan argumennya apa adanya (fungsi identity).
  • increment menerapkan pemanggilan fungsi satu kali lagi.

Contoh

> ((zero (lambda (x) (+ x 1))) 0) ; hasil: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; hasil: 1

Iterasi vs rekursi

Scheme menggunakan rekursi alih-alih for loop untuk melakukan pekerjaan berulang.

Contoh rekursi: faktorial

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))

Pemanggilan rekursif ini dapat menggunakan stack dan memakan banyak memori.

Optimisasi tail-call

Scheme mengurangi penggunaan memori melalui optimisasi tail-call. Karena itu, ia bekerja seperti proses iteratif.

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))

Penutup

Kuliah David Beazley membahas konsep-konsep utama SICP dengan memilih topik-topik tertentu lalu mengupasnya secara mendalam. Secara khusus, kuliah ini membantu memahami beragam paradigma pemrograman seperti pemrograman fungsional, lambda calculus, dan urutan evaluasi.

Kutipan Knuth

Jika Anda hanya mempelajari teori, itu berarti sudah waktunya berfokus pada sisi praktis; dan jika Anda hanya praktik, itu berarti sudah waktunya berfokus pada sisi teoretis.

Bacaan terkait

1 komentar

 
GN⁺ 2024-11-18
Pendapat Hacker News

  • Sebagai peringatan, jika Anda mendalami SICP/Lisp/Scheme, cara Anda memikirkan pemrograman bisa berubah, dan rangsangan intelektual seperti itu selalu patut disambut
    Namun jika ide-ide itu diterapkan mentah-mentah ke codebase berorientasi objek, biasanya hasilnya kontraproduktif atau memicu penolakan dari anggota tim
    Misalnya setelah Lisp, Anda mungkin tergoda mengganti semua loop for menjadi forEach, atau menjadikan semuanya rangkaian map/reduce; tetapi jika bahasanya tidak sepenuhnya merangkul pemrograman fungsional, itu bisa merusak keterbacaan dan performa sekaligus
    Pada akhirnya, mengingat bahwa memori yang dapat berubah dan CPU-lah yang memproses kode akan memberi pijakan; dan sekarang saya melihat desain berorientasi data serta “empati mekanis” yang selaras dengan realitas hardware sebagai sesuatu yang sehari-hari lebih praktis daripada konsep abstrak seperti bilangan Church

    • Saya menganggap imutabilitas lebih aman
      Semakin sedikit efek samping, semakin mudah diprediksi; dan orientasi objek sering dipakai bahkan di tempat yang cukup dengan fungsi saja
      Dalam pengembangan game, ada banyak komputasi dan kode berisiko sehingga orientasi objek cukup cocok, tetapi dalam pengembangan web, pemrograman fungsional jauh lebih alami; di SaaS, bahasa seperti Elixir memungkinkan kita menulis kode yang lebih andal, lebih sedikit bug, dan lebih mudah diuji
    • Bukankah ada juga hal seperti Common Lisp Object System
      Selain itu, hal-hal seperti forEach dan map/reduce sudah ada di koleksi Smalltalk, dan meski bukan sintaks kelas satu, juga disalin ke Object Pascal dan C++
      Karena memori dasarnya dapat berubah, bahasa-bahasa keluarga ML pun memiliki mekanisme untuk menangani mutasi saat benar-benar diperlukan
    • Satu-satunya cara CPU mengimplementasikan alur kontrol memang mirip goto, tetapi goto bahkan kurang populer daripada Lisp
      Yang lebih aneh, untuk mendapatkan performa di CPU modern, cache itu esensial, tetapi belum ada bahasa yang memperlakukan hierarki memori sebagai warga kelas satu
      Yang paling mendekati tampaknya adalah C gaya Linux yang dipenuhi garis bawah seperti lautan

  • Memberikan pengantar yang baik tentang mengenkode state dengan fungsi murni
    Sebenarnya ada jauh lebih banyak encoding fungsional murni untuk segala jenis data, seperti tree, integer, tipe sum/product, image, monad, dan sebagainya
    Encoding-nya bisa sedikit membingungkan, tetapi sekaligus elegan dan kecil
    Misalnya, jika mengimplementasikan monad Maybe secara fungsional di JavaScript, jadinya seperti ini:
    Nothing = nothing => just => nothing
    Just = v => nothing => just => just(v)
    pure = Just
    bind = mx => f => mx(mx)(f)
    evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
    console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
    console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43

    • Implementasi seperti ini dapat diturunkan dari prinsip rekursi tipe tersebut
      data Maybe a = Nothing | Just a
      foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
      Dua fungsi tingkat tinggi yang diberikan ke foldMaybe masing-masing berkorespondensi dengan Nothing dan Just
      Namun untuk sisi Nothing, bentuk ini menambahkan parameter Unit agar sedikit lebih tepat
    • Ini bisa dilihat sebagai mengubah tipe induktif menjadi tipe fungsi rekursor dari tipe tersebut
      Dalam teori tipe ini cukup keren, tetapi tidak terlalu bagus untuk pemrograman nyata
    • Secara matematis mungkin elegan, tetapi ketika disampaikan lewat bahasa yang hanya terdiri dari set karakter ASCII tanpa pengurutan atau justifikasi internal, tampilannya cukup menyakitkan
    • Singkatnya, kalkulus lambda tak bertipe bersifat Turing complete

  • Dulu saya pernah menonton kuliah SICP yang sebenarnya, yaitu rekaman MIT OCW tahun 1986
    Kuliah itu sering dipuji karena kepadatan informasinya tinggi, tetapi kenyataannya cukup banyak waktu terbuang untuk tanya jawab mahasiswa, waktu ketika pengajar mengalihkan perhatian ke upaya presentasi “multimedia” di ruang kuliah, serta bagian-bagian ketika rencana keseluruhan perkuliahan belum sepenuhnya tersusun sebelumnya sehingga tanya jawab tidak bisa dicegah secara proaktif
    Waktu untuk menulis di papan tulis juga, jika diakumulasi, cukup besar
    Tentu saja urutan materi bisa diperdebatkan dan disusun ulang sesuka hati, dan suatu saat saya juga berencana membuat sendiri seri video yang menjelaskan materi ini sesuai dengan intuisi saya
    Saya senang kuliah ini tampaknya tetap mempertahankan akarnya sambil memakai bahasa yang lebih modern seperti Python, dan menurut saya, karena Python adalah bahasa multiparadigma yang praktis, orang belum cukup mengakui daya ekspresinya melalui idiom fungsional, meskipun bukan kemurnian penuh

    • Kuliah ini mengimplementasikan Scheme dengan Python, lalu mengimplementasikan Scheme lagi dengan Scheme
      Menurut saya Python bisa, dan seharusnya, dikeluarkan dari kuliah ini
      Dukungan Python untuk pemrograman fungsional sangat lemah
      List-nya tidak berbasis cons, lambda-nya banyak batasan, pattern matching-nya buruk dan tidak berbasis ekspresi, serta namespace-nya juga aneh
      Python juga sulit disebut bahasa modern; ia masih tertahan di era 1990-an, dan karena memiliki C-API yang lumayan, sayangnya ia tumbuh dengan mengorbankan bahasa-bahasa yang lebih baik
    • Pemrograman fungsional di Python cukup lemah, dan dalam hal itu saya malah menganggap JavaScript lebih baik
      Karena tidak ada optimisasi tail call, sebagian latihan kode membutuhkan solusi yang sama sekali berbeda dari Scheme
      Jika kode yang diterjemahkan 1:1 gagal, apakah pengajar harus mengatakan kepada mahasiswa agar percaya saja karena bahasa yang dipilih membuatnya berperilaku begitu, atau haruskah semuanya dilihat sebagai masalah mengeksternalisasi stack dan diselesaikan seperti itu, saya jadi bertanya-tanya
      Memaksakan SICP ke dalam Python terlihat cukup bodoh
    • Ada juga kuliah dari ArsDigita University
      Situsnya sekarang offline, tetapi kuliahnya bisa dilihat di archive.org
      https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
      https://archive.org/details/arsdigita_01_sicp/
      Mereka menjual USB key berisi seluruh kurikulum; akan sangat bagus kalau ada yang mengunggah ISO-nya
      https://web.archive.org/web/20190222145553/aduni.org/drives/
    • Masalah Python dan sebagian besar bahasa non-Lisp adalah tidak mudah memungkinkan memperlakukan program seperti data
      Hal-hal yang bisa diekspresikan dengan sederhana di Scheme menjadi latihan yang rumit dalam bahasa lain
      Alih-alih berfokus pada konsep dasarnya, mahasiswa jadi berfokus pada detail bahasa implementasi yang dalam Scheme tidak perlu dipikirkan

  • Saat pertama kali melihat cons/car/cdr diimplementasikan dengan lambda, rasanya seperti sulap
    Namun pada akhirnya saya melihatnya sebagai demonstrasi bahwa runtime bahasa mengimplementasikan kamus key/value, dan kita bisa meminjam implementasi itu untuk membuat struktur data lain

    • Menurut saya logika destructuring Elixir jauh lebih menarik, dan versi ES6 yang dilemahkan jauh lebih praktis
      Di Elixir, kita bisa mengambil dari depan sebanyak yang kita mau
    • Yang dibutuhkan bukan kamus key/value, melainkan hanya pointer
      Closure tanpa perilaku hanyalah pointer ke variabel yang tertutup, dan closure dengan 2 pointer adalah pasangan yang memungkinkan kita memperoleh car dan cdr
      Runtime harus membuat objek yang ditunjuk tetap bisa digunakan di luar definisinya, sehingga diperlukan escape analysis, garbage collection, dan semacamnya, tetapi kamus tidak diperlukan

  • Baru-baru ini saya menemukan konsep bahwa untuk membuktikan hal seperti 0 != 1 dalam theorem proving, Church encoding saja tidak cukup dan diperlukan tipe data induktif
    Saya sudah menaruh catatan kasar terkait hal itu di sini, bersama kritik terpisah terhadap SICP: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
    Saya ingin lebih memahami batasan dari sudut pandang bahwa “semuanya hanyalah fungsi”

    • Jika ada fakta konkret lain yang bisa dimanfaatkan tentang ketaksamaan, sepertinya 0 ≠ 1 bisa dibuktikan
      Dari teorema f = g -> f x = g x, kita bisa menyimpulkan untuk membuat fakta ketaksamaan di sisi kanan, lalu mengambil kontraposisinya
      Pernyataan bahwa ketaksamaan antara bilangan Church tidak bisa dibuktikan langsung tanpa fakta lain tentang ketaksamaan tampaknya benar
      Sebaliknya, pada tipe data induktif, sistem pembuktian dapat secara rekursif menghilangkan penerapan konstruktor terluar pada dua instance konkret dari tipe induktif yang sama, lalu secara langsung “mengamati” kesamaan atau ketaksamaan
    • Dalam theorem proving diperlukan tipe Sigma dan tipe Pi, serta suatu bentuk konsep kesamaan
      Saya penasaran apakah itu bisa dicapai dengan Scott encoding atau Church encoding
    • Tautan yang diperbaiki: https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...

  • Bukunya sendiri sudah sedang didiskusikan di sini: https://news.ycombinator.com/item?id=42157558
    Saya penasaran apakah ada alasan tautannya mengarah ke diskusi di bagian bawah, bukan ke awal halaman itu
    Mungkin tulisan ini bisa digabungkan ke diskusi yang sudah ada

  • David Beazley adalah sosok yang cukup legendaris di dunia Python, dan kuliah ini awalnya tampak seperti ide yang mengejutkan, tetapi setelah dipikir sekitar 2 detik rasanya seperti kombinasi yang sempurna, jadi saya mendaftar untuk kuliah berikutnya
    Intinya, bentuk seperti ini sepertinya akan menjadi wajah pendidikan berkelanjutan untuk software engineer ke depan

    • Jika tidak membahas kompilasi di Bab 5, berarti belum membahas bagian terbaik dari SICP

  • Ada typo pada kode di bagian “the substitution model”
    ("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
    Yang didefinisikan adalah fibonacci, dan fib tidak didefinisikan, jadi dua pemanggilan fib itu jelas seharusnya fibonacci
    Kode di repositori GitHub aslinya sudah benar: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...

  • Saya pikir SICP sangat bagus
    Namun, semakin banyak saya belajar dan semakin dalam saya mempelajari matematika, saya makin mendekati kesimpulan bahwa relasi adalah konsep primitif yang lebih fundamental
    Semua fungsi dapat dinyatakan sebagai bentuk relasi yang terbatas, tetapi kebalikannya tidak berlaku tanpa menambahkan perangkat tambahan yang cukup banyak
    Database relasional dan SQL memang contoh pemrograman relasional yang paling dikenal dan sukses, tetapi menurut saya ranah ini masih sangat belum banyak dieksplorasi
    Minat saya sekarang lebih condong ke mengajarkan dasar-dasar matematika kepada anak-anak yang sangat kecil daripada desain bahasa pemrograman
    Anehnya, mengajarkan predikat seperti “besar” sebagai relasi 1-ary, dan “lebih besar dari” sebagai relasi 2-ary, jauh lebih mudah daripada mencoba menangkap konsep yang sama sebagai fungsi

  • Saya kurang suka sudut pandang “semuanya adalah fungsi” karena terlalu disederhanakan dan sering kali tidak membantu
    Misalnya, ada fungsi yang tidak muat di cache, RAM, disk, dan sebagainya; ada fungsi yang Big-O-nya meledak seperti N-way JOIN atau pencarian/pencocokan; dan ada juga fungsi dengan efek samping, termasuk yang tidak idempotent
    Hampir tidak ada orang yang memikirkan serangan side-channel terhadap fungsi
    Ada juga fungsi nondeterministik yang bergantung pada tanggal, waktu, durasi, dan sebagainya, dan fungsi bisa gagal di tengah jalan atau tidak gagal secara elegan
    Sulit juga berasumsi bahwa fungsi tidak mengonsumsi resource yang memengaruhi “fungsi” lain yang memakai pool resource bersama
    Argumen fungsi bisa berukuran atau berkompleksitas sewenang-wenang, tetapi di dunia nyata ada batasnya; lalu kita membutuhkan pointer, dan kemudian lagi membutuhkan referensi jarak jauh seperti web atau disk
    Tolong beri tahu kapan saya harus berhenti, saya masih bisa terus bicara

    • Penyederhanaan berlebihan kadang bisa sangat bagus
      Dalam kasus ini, model kalkulus lambda adalah dasar dari pendekatan “semuanya hanyalah fungsi”, dan sebagai model komputasi ia sangat sederhana sekaligus lebih mudah ditangani dan dinalar dibandingkan mesin Turing dan sejenisnya
      Karena itu, ia menjadi dasar bagi sebagian besar logika komputer dan sistem pembuktian
    • Banyak dari hal-hal itu bisa dimodelkan sebagai fungsi, dan memang cukup ditulis seperti itu
      Jika suatu fungsi membutuhkan resource, buatlah ia meminta resource tersebut; jika bergantung pada tanggal/waktu, buatlah ia bergantung pada tanggal/waktu; jika mengembalikan nilai nondeterministik, buatlah ia mengembalikan nilai nondeterministik
      Salah satu alasan pendekatan pemrograman fungsional bersinar adalah karena ia memaksa kita menangani hal-hal seperti ini secara serius
      Jika ingin menggunakan resource yang dibagi secara implisit, kita harus memodelkannya, dan “fungsi” yang bergantung pada resource bersama implisit dibedakan secara eksplisit dari fungsi sungguhan
    • Separuh dari hal-hal yang disebut fungsi di sini sebenarnya bukan fungsi, dan banyak orang di dunia pemrograman fungsional pun tidak akan menyebutnya fungsi
      Itu lebih mendekati prosedur
      Fungsi adalah prosedur, tetapi tidak semua prosedur adalah fungsi
    • Untuk tujuan teoretis, menurut saya itu satu-satunya harapan