Kodlama Yolculuğumda Biçimsel Yöntemlerin Gücünü Kucaklamak: Nasıl Dafny Evangelist Oldum

blog 1HaberlerGeliştiricilerEnterpriseBlockchain AçıklamasıEtkinlikler ve KonferanslarBasınBültenler

Haber bültenimize abone ol.

E

Senin gizliliğine saygı duyuyoruz

Ana SayfaBlogGeliştiriciler

Kodlama Yolculuğumda Biçimsel Yöntemlerin Gücünü Kucaklamak: Nasıl Dafny Evangelist Oldum

by ConsenSysAralık 22, 2020Yayınlanan Aralık 22, 2020

Ekran Görüntüsü 2020 12 15, 6 46 32 pm 1

Joanne Fuller tarafından

Başkalarının öğrenirken yaşadığım aydınlanma anını deneyimleyebilmesi umuduyla bu blog gönderisini yazdığımı söyleyerek başlamak istiyorum. Dafny keşfimin bir parçası olarak resmi yöntemler. Ayrıca, bu yazının, kod yazan herkesin cephaneliğinde biçimsel yöntemleri kritik ve gerekli bir beceri olarak görmeleri için başkalarına bir katalizör görevi görmesini umuyorum. Bir parçası olarak R içinde Otomatik Doğrulama Ekibi&ConsenSys şirketinde D, Ethereum 2 Phase 0 spesifikasyonunun resmi doğrulamasında Dafny kullanıyorum ve neden yararlı bulduğumu paylaşmak istiyorum.

Arkaplanım

Bir yazılım geliştiricisi olmadığımı açıkça belirtmeliyim, bunun yerine kendimi biraz yazılım geliştirme bilgisine sahip bir matematik programcısı olarak görüyorum. Program yazmayı ilk olarak lisenin son yılında matematik dersimin bir parçası olarak öğrendim ve muhtemelen şunu söylemeliyim ki, o sırada bilgisayar kullanmayı çok sevmeme rağmen, nasıl programlanacağını öğrenme olasılığı beni neredeyse korkuttu. o belirli matematik dersini bıraktı. Başarısızlık korkumla yüzleşmeye karar verdikten sonra (programlamayı öğrenmek ve bu sınıftaki sonucumu potansiyel olarak mahvetmekle ilgili olarak), programlama bağlamında ilk epifani anımı deneyimlemeye devam ettim. Sınıfta oturduğumu ve bir matematik problemini çözmek için bir program yazmanın sihirli ve gizemli bir süreç olmadığının farkına vardığımda, neredeyse kafamdaki bir problemi nasıl çözeceğimi yazmak gibiydi. Bundan sonra geriye bakmak yoktu! 

Programlama, o zamandan beri yaptığım her şeyin önemli bir yönü oldu. Kriptografi alanındaki doktoram, büyük ölçüde algoritmalar geliştirme ve ardından en uygun uygulamaları programlama becerisine dayanıyordu. Programlarım deney için yazılmıştı ve şimdi resmi test olarak adlandıracağımız şeyi üstlenmemiş olsam da, amaçlanan çıktı hakkında mantıksal akıl yürütme kullanarak sınırları ve vakaları gayri resmi olarak kontrol ederdim. Finans ve ekonomi alanında uzun yıllar akademik araştırma sorumlusu olarak çalıştım. Yine bu program yazma programlarını içeriyordu ve yine kendi tekniklerimi gayri resmi olarak test etmek ve doğruluklarını anlamak için kullandım.. 

Her vakayı test etmenin imkansız olduğu anlamında testin her zaman eksik olacağı gerçeğini takdir etsem de; gayri resmi olarak titiz bir şekilde test etme söz konusu olduğunda matematiksel düşünme tarzımın oldukça iyi olduğuna makul ölçüde güveniyordum. Bu nedenle, test etmek ve doğruluğu kanıtlamak arasındaki farkı ve bunun sonuçlarını kesinlikle tam olarak anlamadım! ConsenSys’e katılmadan önceki kariyerim boyunca, test yoluyla doğru olduğunu düşündüğüm şeyi belirlemek için kendi gayri resmi tekniklerime güvenmekten memnundum. 

Bu nedenle geçmişim hikayenin bir parçası, çünkü kendimi daha önce resmi yöntemleri keşfetmediğime biraz şaşırdım. Kendimi bir matematikçi olarak görüyorum; Matematiği, algoritmaları ve mantığı seviyorum. Şimdi sadece tamamlanmamış testlere güvenmek çılgınca görünüyor, ancak program yapan herkesin en azından resmi yöntemlerin neler sunabileceğini ve bilgisayar programlarının birçok yolu göz önüne alındığında bir hatayı kaçırmanın olası sonuçlarını takdir etmemesi çılgınca görünüyor. hayatımıza entegre. Biçimsel yöntemler, bir programın ön ve son koşulları içeren bir spesifikasyona göre doğru olduğunu kanıtlamak için testin ötesine geçmemize izin verir.. 

İlk Dafny örneği

Basit bir örnek olarak, negatif olmayan temettü n’nin pozitif bölen d’ye tamsayı bölünmesini düşünün; 


n / g

aşağıda gösterilen:

Yazılmış bir programlama dilinde giriş parametrelerini bir şekilde kısıtlayabilsek de, bu her zaman yeterli değildir. Bu örnekte, n ve d’nin doğal sayılar olarak belirtilmesi, her iki girdinin de negatif olmayan tamsayı olması gerektiği anlamına gelir, ancak bu, d’nin pozitif bir tam sayı olması sınırlamasını sağlamaz. Required ifadesi aracılığıyla bir ön koşulun kullanılması, böyle bir kısıtlama sağlar ve bu yöntemin yalnızca d > 0. Bu nedenle, programın başka herhangi bir parçası böylesi bir ön koşul sağlanmadan div çağrılmasına neden olursa, program doğrulanmayacaktır. Sağlar ifadesi daha sonra son koşulu sağlar ve yöntem çıktısının neyi karşılaması gerektiğine dair resmi bir özellik sağlar..

Bu örnek Dafny kullanılarak yazılmıştır: “İşlevsel doğruluk için bir dil ve program doğrulayıcı” ve beni bir sonraki noktama getiriyor, bu yüzden Dafny’nin bu kadar hayranıyım. Pek çok programcı için programın doğruluğunu onaylamak için “biçimsel yöntemler” kullanma düşüncesi biraz korkutucu ve genellikle “çok” zor olarak algılanıyor. Bunun nedeni tekniklere maruz kalmama, faydaların takdir edilmemesi veya hatta bu alandaki eğitim eksikliğinden kaynaklanıp kaynaklanmadığı; Sebepler ne olursa olsun, Dafny’nin herhangi bir programcının işlerinde resmi yöntemleri uygulamada hızlı bir şekilde başarıya ulaşmasına izin verme yeteneğine sahip olduğuna inanıyorum. Yukarıdaki kod parçacığına baktığımda, programlama bilgisine sahip herkesin bu Dafny kodunu okuyabilmesini beklerdim; Dafny, tam anlamıyla programcı dostu bir dildir. Biraz Dafny öğrendikten sonra, denemeye başlamak ve daha sonra temelde ilerledikçe öğrenmek çok kolaydır. Dafny’yi öğrenmekle ilgileniyorsanız, başlamak için harika bir yer eğitim serisi Microsoft tarafından. Site ayrıca bir çevrimiçi düzenleyici içerir, bu nedenle eğitim örneklerini denemek çok kolaydır. Doğrulama Köşesi YouTube kanalı başka bir faydalı referans kaynağıdır.

Benim aydınlanma anım

Sonunda Dafny’yi öğrenirken aldığım epifan anımı paylaşmak istedim. Kesinlikle büyük saygın şirketlerden kısa ve basit kod parçaları hakkında, gözden kaçan ve nihayetinde milyonlarca dolara mal olan hatalara sahip hikayeler duydum; ama bence basit bir işlevde istemeden bir hata yaratmanın ne kadar kolay olduğunu kendi kendinize anladığınızda her şeyin mantıklı olduğunu düşünüyorum! Kendinize “Ah, bu hatayı yapmak çok kolay olurdu!” Dediğiniz an.

Birini izlerken anım geldi Doğrulama Köşesi videoları

Bu eğitimde Rustan Leino, x ve y olmak üzere iki tamsayı alan ve sırasıyla toplamı ve max’ı, s ve m’yi döndüren bir SumMax yönteminden geçer. Bu örnek nispeten basittir ve Dafny kodu aşağıda gösterilmiştir.

X ve y girişleri yazarak tamsayı olarak belirtilir ve başka hiçbir ön koşul gerekmez. Üç post koşulu, çıktının gerçekten spesifikasyonları karşılayıp karşılamadığını, yani s’nin x + y’ye eşit olduğunu ve m’nin x veya y’ye eşit olduğunu ve m’nin x ve y’yi aşmadığını kontrol eder. SumMaxBackwards yöntemi daha sonra bir alıştırma olarak sunulur ve burada daha ilginç hale gelir. Belirtim, SumMax’ın tersidir, yani toplam ve maksimum verildiğinde x ve y tam sayılarını döndürür. Tamam, yani ilk deneme aynı koşullara sahip olabilir; girdiler ve çıktılar arasındaki ilişkiler hala geçerli olduğundan. Eğer x’in maksimum olmasına izin verirsek, hızlı bir cebir bize y’nin toplam eksi maksimuma eşit olması gerektiğini söyler. Bunu çevrimiçi düzenleyiciye koymak aşağıdakileri verir.

Ekran Görüntüsü 2020 12 15, 6 38 37 pm 1 Ekran Görüntüsü 2020 12 16, 5 35 22 pm

Doğrulamıyor. Öyleyse ne ters gitti? Bir son koşulun geçerli olmadığı ve özellikle 3. satırdaki son koşulun geçerli olmadığı söylendi (x<= m && y <= m) tutmayabilir. Daha yakından baktığımızda, bu post koşulunun x <= m ve y <= m. X’i m’ye eşit olarak ayarladığımızda, x’in m’den küçük veya m’ye eşit olduğunu biliyoruz, yani bu, y’nin <= m kısmı doğrulanmıyor. Bu nasıl olabilir? Cebirimiz bize y: = s – m olduğunu söyledi. Diyelim ki s 5 ve m 3, o zaman y = 5 – 3 = 2, bu da y’yi sağlar <= m; ancak bu yöntemi s eşittir 5 ve m 1’e eşit olarak adlandırdığımızı varsayalım. Hiçbir şey bizi bu girdi parametreleriyle yöntemi çağırmaktan alıkoymayacaktır, ancak bunu yapmak y = 5 – 1 = 4 ve sonra y gibi bir soruna yol açacaktır. > m. Temel olarak burada gördüğümüz şey, girdi parametresinin toplamı s oluşturan maksimum iki tam sayı olması anlamına gelse de, yöntemi geçerli olmayan bir girdi ile çağırmaya çalışmamızı engelleyecek hiçbir şey olmamasıdır. S ve m’nin girişlerini, spesifikasyonu karşılayan x ve y çıktılarıyla sonuçlanacak geçerli tamsayılarla sınırlamak için bir ön koşul dahil edilmedikçe, yöntemimiz yanlış sonuçlar üretebilir. Geçerli girdiler sağlamak için s ve m arasında nasıl bir ilişkiye ihtiyacımız var? Biraz daha cebir bize şunu gösteriyor: <= m * 2 x ve y’nin geçerli bir çözümü olması için. Bunu bir ön koşul olarak eklersek, Dafny artık kodu aşağıda gösterildiği gibi doğrulayabilir.. 

Ekran Görüntüsü 2020 12 15, 6 46 32 pm 1 Ekran Görüntüsü 2020 12 16, 5 37 39 pm

Bu, koda bir hata eklemenin ne kadar kolay olduğunu görebildiğim örnekti. Girdi parametrelerini toplam için ‘s’ ve maksimum için ‘m’ olarak adlandırmamız, yöntemin uygun şekilde çağrılacağı anlamına gelmez ve bu nedenle daha büyük bir programın bir parçası olarak, bundan kaynaklanan birçok istenmeyen sonuç olabilir. böcek türü. Umarım Dafny’yi veya daha genel olarak resmi yöntemleri öğrenen herkes için yararlıdır..

Şimdi ne üzerinde çalışıyorum

Bu beni görevimin sonuna getiriyor. Şu anda Dafny ile ne üzerinde çalıştığımı görmek isterseniz, o zaman şuna bakın GitHub deposu. R içinde Otomatik Doğrulama Ekibinin bir parçasıyım&ConsenSys’de D ve biz Dafny’yi Ethereum 2 Phase 0 spesifikasyonunun resmi doğrulamasında kullanıyoruz. Blockchain alanında resmi yöntemlerin kullanılması, ConsenSys tarafından benimsenen heyecan verici yeni bir araştırma alanıdır ve Eth 2.0 hakkında daha fazla bilgi edinmek isteyen herkesi proje depomuzda bulunan kaynaklara bakmaya teşvik ederim..

En son Ethereum haberleri, kurumsal çözümler, geliştirici kaynakları ve daha fazlası için haber bültenimize abone olun.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map