Dizi Diliyle Düşünmek

 (github.com/razetime)
2 puan yazan GN⁺ 2024-01-15 | 1 yorum | WhatsApp'ta paylaş
  • K programlama, REPL’de denenen kodu betiğe taşıyıp büyük imperative kalıpları sürekli daha küçük ve deklaratif dizi kalıplarına indirgemeye odaklanır
  • ngn/k betikleri REPL girdisi gibi satır satır çalıştırılır; \l file.k ile kaydedilmiş veri ve işlevler REPL’e yüklenebilir
  • Wikipedia tarzı üçlü döngüyle matris çarpımını aynen taşımak; global değişkenleri, iç içe döngüleri ve değişiklikleri artırır, K’nin güçlü yanlarıyla ters düşer
  • İyileştirme süreci +/ fold, ' each, /: eachright, \: eachleft, transpozu kaldırma ve tacit dönüşüm üzerinden matmul: {x{+/x*y}\:y} biçiminden matmul: (+/*)\: biçimine kadar yoğunlaşır
  • Matris çarpımı örneği, K becerisinin kod yoğunlaştırma sürecini tekrar ederek karmaşık prosedürleri daha okunabilir dizi ifadelerine dönüştürmekte yattığını gösterir

REPL merkezli K geliştirme akışı

  • Tüm kaynak kodu GitHub’daki matmul.k dosyasında görülebilir
  • K programlama çoğunlukla REPL içinde yapılır; önceki kodun üzerinde hızlıca deneme yapmak ve iyileştirmek için elverişlidir
  • ngn/k ve rlfe birleşimi, yukarı/aşağı ok geçmişini destekleyerek daha büyük K programları geliştirmek için yeterlidir
  • İşlevleri önce REPL’de test edip sonra gerçek koda taşımak doğal bir akıştır
  • ngn/k’nin prettyprinting çıktısı her zaman geçerli K verisi döndürdüğünden, bazı değerler önceden hesaplanarak program hızlandırılabilir

K betiği yürütme modeli

  • K betikleri, REPL’e girilmiş gibi çalıştırılır
    • Her satır sırayla çalıştırılır
    • Satır noktalı virgülle bitmiyorsa dönüş değeri yazdırılır
  • Betikler, okunabilirliği artırmak için çok satırlı tanımlara izin verir
  • Kaydedilmiş veri ve işlevleri REPL’de kullanmak için \l file.k çalıştırılır
    • Dosya yürütülür
    • Dosyadaki veriler yüklenir
    • Aynı dosya birden fazla kez yüklenirse önceki verilerin üzerine yazılır
  • \ ile erişilen REPL yardımında daha fazla komut görülebilir

Dizi dillerinde kalıpları azaltma yöntemi

  • K ve dizi programlama, kalıpları sürekli basitleştirme sürecidir
  • Büyük ve yönetilmesi zor kalıpları daha küçük, daha deklaratif ve daha okunabilir biçimlere indirmenin birden fazla yolu vardır
  • İlgili tartışma Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17 içinde ayrıntılı olarak görülebilir
  • Yaygın bir başlangıç noktası, GeeksforGeeks veya Wikipedia’daki iyi bilinen algoritmaları K’ye çevirmeye çalışılan durumlardır
  • Örnekte matris çarpımı kullanılır

Imperative matris çarpımını aynen taşıyınca

  • Wikipedia’daki Matrix multiplication algorithm, i, j, k üçlü döngüsü ve sum akümülatörüyle C matrisini doldurur
  • Bunu K’ye doğrudan çevirmek A, B, n, m, p, C, i, j, k, sum gibi birçok global değerin atanmasına yol açar
  • Bu kod K’yi imperative bir dil gibi kullanır; bu da K’nin tasarımıyla pek uyuşmaz
  • Sorun üç noktaya indirgenir
    • Çok sayıda global atama vardır
    • Birkaç aşamalı iç içe döngüler kalır
    • Sık sık değişiklik yapılır

En içteki döngüden başlayarak katlayıp azaltma

  • En içteki döngü sum değerini 0’a ilklendirir ve k üzerinde dönerek A[i;k]*B[k;j] değerini biriktirir
  • İlk iyileştirme, fold olan / kullanarak toplama işlemini +/ biçimine çevirmektir
    • sum globali ortadan kalkar
    • C[i;j]::+/... biçiminde sadeleşir
  • Ardından ' each’in bir dizi döndürdüğü gerçeği kullanılırsa, C değiştirilmeden iç içe döngünün dönüş değeri doğrudan kullanılabilir
  • Bu aşamadan sonra değişiklik içermeyen yalnızca üç döngü kalır; temel değişkenler i, j, k olur

k, j, i değerlerini ortadan kaldırma süreci

  • Üç değişkenin rolleri şöyledir
    • i, A matrisinin her satırını indeksler
    • j, B matrisinin her sütununu indeksler
    • k, A matrisinin her sütununu ve B matrisinin her satırını indeksler
  • k, A matrisinin her satırını B matrisinin her sütunuyla eşleyip çarptırdığı için, ara indeksi kaldırıp doğrudan eşleştirmek mümkündür
    • Bu aşamada bir döngüye ve m değerine artık gerek kalmaz
  • j değerini kaldırmak için B matrisinin her sütununu alıp A[i] ile eşleştirmek gerekir
    • B transpoze edilir ve her öğeyi eşleştirmek için eachright /: kullanılır
  • i de aynı yöntemle kaldırılabilir
    • A matrisinin her satırını B matrisinin her sütunuyla eşleştirmek için eachleft \: kullanılır
  • Bu süreçten sonra global içermeyen şu biçim elde edilir
matmul: {x{+/x*y}/:\:+y}

Transpozu kaldırma ve nihai tacit biçim

  • + transpozu maliyetli olduğundan kaldırılabilir
  • Mevcut yöntem, x matrisinin her satırını y matrisinin her sütunuyla çarpan naif yöntemdir
  • Bunun yerine B matrisinin her satırı A matrisinin tamamıyla eşleştirilirse aynı iş örtük olarak yapılabilir
matmul: {x{+/x*y}\:y}
  • Bu işlev, Chapter 3 kuralları uygulanarak tacit biçime dönüştürülebilir
  • Nihai sonuç şöyledir
matmul: (+/*)\:

Pratikle gelişen dizi dili sezgisi

  • matmul: (+/*)\:, K’ye özgü bir matris çarpımı işlevi olarak sadeleşir
  • Yoğunlaştırma süreci başta çok aşamalı görünebilir
  • K ile pratik yaptıkça kod yoğunlaştırma daha kolay ve sezgisel bir işe dönüşür
  • Matris çarpımı, K’nin dizi desteğiyle iyi örtüşen basit bir prosedürdür
  • Sonraki bölümlerde K ile iyi örtüşmeyen algoritmalar ve bunlarla nasıl başa çıkılacağı ele alınacaktır

İlgili okumalar

1 yorum

 
GN⁺ 2024-01-15
Hacker News yorumları

  • Dizi dillerinin potansiyelini bana en ikna edici biçimde gösteren şey, Aaron Hsu’nun paralel APL derleyicisi Co-dfns geliştirme sürecini anlattığı videoydu: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
    HN’de arcfide adıyla anlam yoğunluğu hakkında da birkaç kez yazdı; APL kodunun, nasıl çalıştığını, çevre bağlamı ve bağımlılıkları neredeyse hiç yer değiştirmeden tek ekranda görebilecek şekilde tasarlandığını açıkladı: https://news.ycombinator.com/item?id=13571159
    Bakış açısı şu: Bir algoritmanın adı, algoritmanın kendisini açarak yazmanın uzunluğuna yaklaşacak kadar özlü hâle geldiğinde, kodu İngilizce ifadeler okur gibi deyim birimleri üzerinden okumaya başlarsınız; yeniden kullanılabilir soyutlamalar oluşturmaktansa ekranda görünen tüm kullanım yerlerini doğrudan değiştirmek daha hızlı olabilir.

    • Sınırlı bir bağlam penceresine sahip LLM’lerin APL ile diğer dillere göre daha iyi başa çıkıp çıkamayacağını da merak ediyorum.
    • Bence böyle uzun açıklamalar yazmak zorunda kalınması, kodun çirkin görünmesinden kaynaklanıyor. Semboller yan yana geldiğinde daha az çirkin görünecek şekilde seçilseydi, insanları dilin kötü olmadığına ikna etmek için 18 saat harcamak gerekmeyebilirdi.

  • Dizi programlamayı iyi bilmiyorsanız, başlangıç kaynağı olarak The Array Cast’i öneririm: https://www.arraycast.com/episodes/
    RSS adresi: https://www.arraycast.com/episodes?format=rss

    • İkna olmak için The Array Cast’in ilk 5 bölümü civarını dinledim ama sonunda ikna olmadım. Sunucular, dizi dillerinin kısa gösteriminin ve ASCII dışı sembollerinin alışınca sorun olmadığını ve sağladıkları avantajlar için katlanmaya değer olduğunu söylüyordu; ama bu avantajların çoğu, günümüz ana akım dillerindeki higher-order function’larla zaten alışık olduğumuz şeylerdi.
      map/filter/reduce zaten neredeyse her yerde var; ideografik bir notasyon sistemi gibi yeni bir şey öğrenmeden de kullanılabildiklerini kaçırmışlar gibi geldi.
    • Bunun sayesinde BQN’i öğrendim, ama gerçek üretim ortamında kullanıp kullanmayacağımı hâlâ bilmiyorum. Hoşuma gitse de R, NumPy, Julia gibi şeyler dışında çoğu dizi dili yabancı geliyor; APL, J, BQN’de derine inmek, ileride yardım alabileceğim insanları kendi elimle uzaklaştıracakmışım gibi hissettiriyor.

  • 70’lerde kâğıt terminallerde gerçekten üst üste baskı kullanan APL/APL2 ile karşılaşıp hemen etkilenmiştim; ama daha sonra ML ve Haskell ile fonksiyonel programlamayı öğrendikten sonra, APL’de gerçekten sevdiğim şeyin dizilerden çok fonksiyon bileşimi yeteneği olduğunu fark ettim.
    Haskell tamamen saf ve tipler genel olarak uygulandığı için bu konuda çok daha iyi; APL’den daha eğlenceli ve güçlüydü. Çok sayıda küçük ve orta ölçekli proje yaptım; LLVM Flang’in ayrıştırıcısının parser combinator ile uygulanabileceğini gösteren bir prototip de hazırladım ve her yıl Advent of Code’u toplamda birkaç yüz satır civarında çözüyorum. APL’yi seviyorsanız Haskell’i de denemeye değer.
    Şimdi APL’nin “düşünme aracı olarak notasyon” yönü, aşırı kısalığı rasyonalize eden bir söylem gibi görünüyor. Bileşimin gücünü göstermek için iyi, ama açıklığa da zarar verebilir.

    • Bu konuda sürekli aynı şeyi söylüyorum ama point-free Haskell’i belli bir düzeyde iyi kullanmaya başladıktan sonra J ve K’ye neredeyse hiç dokunmaz oldum. Functor’lar da işin içine girince fiil trenlerinden daha güçlü hâle geliyor; <=< zaten var ve fmap karşılığı olan şeyi kullanınca gerçekten çok iyi işliyor.
      |||, +++, &&&, *** de güzel; UTF-8 operatörlerini kendiniz tanımlayıp daha kısa ve güzel hâle getirebilirsiniz. Yine de gerçek işte ya da kamuya açık ciddi Haskell kodlarında dikey ekran alanına bu şekilde dost davranılması nadir, bu yüzden biraz üzücü.
    • Advent of Code kaynak bağlantısını görebilsem iyi olurdu.

  • Dizi dillerinde “N’den küçük sayılar arasında P yüklemi doğru olan tüm sayıları bulma” gibi problemlerin genel olarak nasıl ele alındığını merak ediyorum. Örneğin 1000’den küçük asal sayıları bulmak ya da z’si 1.000.000’dan küçük Pisagor üçlülerini bulmak gibi biçimler.
    Emirsel bir dilde döngü içinde yüklem denetlenir; fonksiyonel bir dilde ise özyineleme ya da tembel listeler üzerinde map/filter kullanılır. Dizi dillerinde ise genelde 1..N dizisi oluşturulup, yüklem uygulanarak bir maske dizisi çıkarıldıktan sonra bu maskeyle özgün dizinin süzüldüğünü anlıyorum.
    N 1 milyar gibi büyükse ve yüklem neredeyse hiç doğru değilse, 1..N dizisiyle maske için iki dev geçici dizi oluşturmak bellek ve kaynak açısından çok savurgan görünüyor. Dizi dilleri bu geçici dizileri sürekli oluşturduğu için yavaşlıyor mu, yoksa uygulamalar bunu tembel değerlendirme gibi yöntemlerle optimize mi ediyor merak ediyorum.

    • Evet, belleği çok israf ediyor. Yine de bellek ucuz; gerekirse hesaplama bloklar halinde bölünebilir. Gerçekte belleğin tamamen tükendiği durumlar nadirdir, ama daha düşük önbellek katmanlarında kalmak için bloklama yararlıdır.
      Skaler dillerde ise bunun tersi olarak varsayılan, bir seferde tek bir değeri işlemektir; bu da dizi dillerinin SIMD algoritmalarıyla yararlandığı potansiyel paralelliği boşa harcar. Bu da mevcut durum alışıldık olduğu için büyük bir sorun gibi görünmez; çözüm yine bloklamadır.
      Dizi dillerinin gerçekten iyi olup olmadığı probleme bağlıdır. Pratik kullanım alanlarının çoğunda performans hiç önemli değildir; k’nin itibarı da k uygulamasının kendi başına hızlı bir dil olmasından çok kdb’nin bir veritabanı olarak hızlı olmasından geliyor gibi. Yine de makineye özgü ayrıntılı optimizasyonlar yerine zarif dizi algoritmalarına odaklanmak bile şaşırtıcı derecede hız kazandırabilir: https://mlochbaum.github.io/BQN/implementation/versusc.html
    • Birkaç dolaylı yol var. Tembel değerlendirme bunlardan biri ve Kap bunu kullanıyor: https://aplwiki.com/wiki/KAP
      Bir diğer açık yöntem, tüm gövdeyi döngü kaynaştırmasıyla birleştirip geçici dizilerin oluşmasını engellemek. Daha basit bir seçenek de giriş ve çıkış dizilerini onlarca KB’lık parçalara bölerek gereksiz geçici bellek kullanımını sınırlamak; bildiğim kadarıyla bunu otomatik yapan bir dizi dili yok, ama bir gün CBQN’de denemek isterim. Kullanıcı bunu elle de yapabilir; performansı en üst düzeye çıkarmak için pratikte sık sık yapmak gerekir.
    • Sezgin büyük ölçüde doğru, ama pratikte nadir karşılaşılan bir problem. k ailesinde, örneğin ngn/k’de !10000000 gibi 0’dan on milyona kadar iota, gerçekten on milyon tamsayılık bir dizi olarak oluşturulmaz; basit bir aralık olarak ele alan tembel bir yapı vardır.
      Elbette hangi işleci kullandığına bağlı olarak sonunda böyle bir dizi oluşabilir. Ayrıca +|x gibi x’i ters çevirip ilk öğeyi alma kalıbını, doğrudan son öğeyi alma işlemine dönüştüren optimizasyonlar da vardır.
    • Dizi oluşturmanın harfi harfine gerçekleştiğini varsayıyor gibisin. Bir dizi dilinin içeride parça parça işlem yapamaması için bir neden yok. 10 milyar tamsayılık dizi istesen bile safça aynen oluşturmayabilir.
    • Birçok dizi dilinde gerçekten bu sorun var. Daha doğrusu, basit ve sezgisel yöntemin gerekenden çok daha fazla hesaplama yapma eğiliminde olması sorun.
      Elbette farklı yazarak bundan kaçınmak mümkün, ama bu çözümler daha uzun ve daha az zarif olabilir. Üzerinde çalıştığım APL lehçesi Kap, sonuç gerçekten gerekene kadar hesaplamayı erteleyerek, sezgisel biçimde kod yazarken bile atılacak sonuçların hesaplanmamasını birçok durumda ele alıyor.

  • Dizi dillerini, özellikle k’yi kullanırken en büyük farkına vardıklarım şunlar oldu. Fiiller algoritmadır; emirsel ve nesne yönelimli dillerde find, sort, group gibi ortak algoritmaları çoğu zaman kendiniz uygulamak zorunda kalırsınız.
    Fiil ya da zarf dizileri, kullandıklarım arasında en doğrudan bileşim biçimiydi; bileşim kolay ve doğaldır. Program, deyim ve ifadeler toplamı değil, algoritmaların bileşimi gibi görünmeye başlar.
    Dizilerde, map’lerde ve fonksiyonlarda tanım kümesi ve değer kümesi kavramlarını tutarlı biçimde ele almak tasarım seçimlerini basitleştirir; sağdan sola değerlendirme de kod okurken gözünüzün oradan oraya atlamasını gerektirmez.
    Veriyi koda getirmek yerine kodu veriye gönderme biçimi mümkündür ve tercih edilir. Büyük k projelerinin çoğu, yorumlar hariç tutulduğunda ağ MTU’suna, yani 1540 bayta sığar. k’nin bonusları arasında, view’ların fonksiyonel ilişkileri doğrudan uygulayabilmesi ve yorumlayıcı üzerinden sıcak kod yükleme sayesinde “sonsuza kadar” çalışan uygulamaların mümkün olması var.

  • İş görüşmelerine hazırlanmak için K dili problemleri çözmüş biri olarak kişisel, önyargılı ve sınırlı izlenimim, dilin kasıtlı olarak anlaşılması güç olduğu yönünde. Bulmacalar ve zekice çözümler için iyi bir dil.
    Ama dizi dillerini ve dizilerle düşünmeyi öğreten şeyin Python’da NumPy dizileriyle çalışma deneyimi olduğunu düşünüyorum.

    • Hangi şirketin görüşmesiydi merak ettim.

  • J’yi yaklaşık 50 saat kullanmış biri olarak bu paradigmanın açıkçası fazla tek tarafa yatkın olduğunu hissettim.
    Her problemi dizilerin iç içe geçmesi olarak düşünmenin bir düşünme aracı olarak yararlı olup olmadığını bilmiyorum. Problemi iyi yakalayan veri yapılarını özgürce oluşturabildiğinizde algoritma kısmı büyük ölçüde basitleşebilir.
    APL/J/K kullanmak için daha zeki olmak gerektiğini düşünüyorum. Daha esnek dillerde hemen mümkün olan yaklaşımlar çoğu zaman burada mümkün olmayabiliyor; problemi dönüştürmek gerekiyor ve bu süreç çok daha fazla düşünme gerektirebiliyor.

  • Bu örnek K tabanlı, ama bir başka dizi dili olarak J de var: http://jsoftware.com
    J’de dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q şeklinde yazarsanız P ile Q’nun iç çarpımı olan 10 döner.

    • Asıl dizi dili APL’dir ve iç çarpım dot←+.× olarak yazılabilir. Ama açılmış gösterim yeterince kısa bir ad kadar kısaysa, ayrıca ad vermeye gerek yoktur; üstelik adın etrafına boşluk koymanız da gerekebilir.
    • Bunun Haskell’e göre ne avantajı olduğunu hâlâ tam bilmiyorum. dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], p `dot` q şeklinde yazılabilir.
      Benim gözüme tek fark, sum ve zipWith için ad kullanılması ve lifting ya da yapı dönüşümünün “sihirli” biçimde gerçekleşmemesi gibi görünüyor.
    • KlongPy’de iç çarpım dot::{+/x*y} şeklinde yazılır. Biçim olarak P::[2 3 4], Q::[1 0 2], dot(P;Q).

  • Örneklere bakınca bunun ne anlama geldiğini anlamıyorum. Herhangi bir şekilde performansı daha mı iyi?
    Matris çarpımı sözdizimi daha kısa, ama bunun sebebi K dilinin nasıl çalıştığına dair çok fazla yerleşik bağlamı zihinde taşımak zorunda olmanız gibi görünüyor

    • Daha özlü olmasının kendisi değerli. Özellikle matematiğin giderek daha fazla kavramı daha üst düzey tanımlar içine sıkıştırma süreci olduğunu düşünürsek benzer bir durum. Daha üst düzey kavramlar ilkel öğeler haline geldiğinde daha hızlı düşünebilir ve daha karmaşık nesneler oluşturabilirsiniz
    • Performansı daha iyi olabilir. Bilgisayarlar dizileri tarama işlerinde çok hızlıdır, özellikle SIMD’den yararlanılabiliyorsa; ama mesele bundan ibaret değil
      Dizi dillerini deneyip paradigma anlaşılana kadar kurcalamaya değer. Emirsel kodun dizi tarzında daha iyi ifade edildiği durumlar sık görülür; uzun ve ufak tefek fonksiyonlar da yalnızca dizi işlemleriyle ya da başka stillerle birlikte kullanılarak büyük ölçüde basitleşebilir
    • Laf kalabalığının da bir maliyeti var; gerçekten karmaşık fonksiyonların ancak uzun anlatımlı olma ayrıcalığına sahip olduğuna inanıyorsanız anlamı kolayca görürsünüz
      Haskell’de (+) <$> Just 1 <*> Just 2 ile do x <- Just 1; y <- Just 2; Just (x + y) karşılaştırıldığında, bu karmaşıklık düzeyinde her zaman ilkini tercih ederim. İkincisi daha fazla yer kaplıyor ve sanki daha karmaşık bir şey oluyormuş gibi hissettiriyor
      Daha karmaşık bir iş olsaydı, ikinci biçimi kullanmak yerine ilk varyantın mantıklı olacağı küçük fonksiyonlara bölmek isterdim. Bu, “bazı acemiler hızlıca okuyabilir”i “acemi seviyesinin üstündekiler okuyabilir”e dönüştüren bir ödünleşimdir
      “Bazı acemiler okuyabilir”i optimizasyon hedefi yapmakta getirilerin çok hızlı azaldığını düşünüyorum; bunun yerine “acemi üstü” ya da duruma göre “orta seviye üstü” kişilerin okuyabilmesini hedeflerim

  • Her dili kullanmak için de kullanmamak için de çok neden vardır. Ama asıl mesele kısa gösterim, göreli açıklık ya da hızlı koda derlenebilme yeteneği değil; sonradan gelen programcının o kodu gerçek kullanım için değiştirip bakımını yapabilip yapamayacağıdır
    Programcılar çok sık kendi leet becerilerini göstermek isterken, arkalarından gelip o kodu devralmak zorunda kalacak zavallı insanları hesaba katmazlar. Gerçekçi olarak, birçok leet kod uzun vadede desteklenebilir bir şey elde etmek için çöpe atılmak ya da tamamen yeniden yazılmak zorunda kalır
    Bunu anlamam uzun sürdü; sonrasında başkalarının bakımını yapabileceği temiz, basit ve anlaşılır kod yazmaya çalıştım. Atılacak kodun kurumun temel altyapısı haline gelip kemikleştiği ve sonraki nesil için anlaşılmaz bir şeye dönüştüğü çok fazla durum var