Semuanya adalah Fungsi: Ulasan kuliah David Beazley dan SICP

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.

[GN⁺]

Opini Hacker News

• Kuliah SICP memiliki kepadatan informasi yang tinggi, tetapi memakan banyak waktu karena sesi tanya jawab mahasiswa dan penggunaan papan tulis. Urutan kuliahnya juga mungkin bisa disusun ulang. Secara pribadi sedang merencanakan seri video baru

  • Kuliah SICP tetap mempertahankan maksud aslinya sambil menggunakan bahasa modern seperti Python
  • Python adalah bahasa multi-paradigma dengan daya ekspresi yang sangat baik

• Diperkenalkan cara mengenkode state sebagai fungsi murni. Ada berbagai encoding fungsional murni untuk beragam data

  • Encoding bisa membingungkan, tetapi elegan dan ringkas
  • Ditunjukkan contoh implementasi monad Maybe secara fungsional di JavaScript

• Karena anchor/hash URL pada posting blog, langsung lompat ke postscript sehingga membingungkan

• Implementasi cons/car/cdr dengan lambda terasa seperti sulap saat pertama kali melihatnya. Ini menunjukkan bahwa runtime bahasa perlu mengimplementasikan kamus key/value

• David Beazley adalah figur legendaris di dunia Python, dan kuliah ini awalnya terasa mengejutkan, tetapi segera terasa sebagai kombinasi yang sempurna. Saya mendaftar untuk kuliah berikutnya

  • Ini menunjukkan bagaimana pendidikan berkelanjutan bagi software engineer akan berlangsung

• Saya menemukan konsep bahwa tipe data induktif itu diperlukan. Hanya dengan encoding Church, tidak mungkin membuktikan teorema seperti 0 != 1

  • Konten terkait telah diposting di Notion

• Artikelnya sendiri menarik, tetapi navigasi halamannya sulit. Scroll tidak berfungsi dengan tombol panah keyboard

• Ada typo pada kode di bagian "model alternatif". Harus memakai fibonacci, bukan fib. Kode di repositori GitHub sudah benar

• Ada tautan ke diskusi yang sedang berlangsung tentang buku tersebut. Saya penasaran kenapa tautannya langsung menuju diskusi di bagian bawah halaman. Saya juga penasaran apakah itu bisa digabungkan ke diskusi lain

• Tautan YouTube disediakan