Nắm bắt sức mạnh của các phương pháp chính thức trong hành trình viết mã của tôi: Cách tôi trở thành nhà truyền giáo Dafny

blog 1Tin tứcDevelopersEnterpriseBlockchain ExplainedEvents and ConferencePressBản tin

Theo dõi bản tin của chúng tôi.

Địa chỉ email

Chúng tôi tôn trọng quyền riêng tư của bạn

Trang chủBlogDevelopers

Nắm bắt sức mạnh của các phương pháp chính thức trong hành trình viết mã của tôi: Cách tôi trở thành nhà truyền giáo Dafny

bởi ConsenSys Ngày 22 tháng 12 năm 2020Đăng vào ngày 22 tháng 12 năm 2020

Ảnh chụp màn hình 2020 12 15 lúc 6 giờ 46 32 giờ chiều 1

Bởi Joanne Fuller

Tôi muốn bắt đầu bằng cách nói rằng tôi đang viết bài đăng trên blog này với hy vọng rằng những người khác có thể trải nghiệm khoảnh khắc hiển linh mà tôi đã có khi học Dafny như một phần của chuyến khám phá của tôi vào phương pháp chính thức. Hơn nữa, tôi hy vọng rằng bài đăng này sẽ hoạt động như một chất xúc tác để những người khác coi các phương pháp chính thức là một kỹ năng quan trọng và cần thiết trong kho vũ khí của bất kỳ ai viết mã. Là một phần của Nhóm xác minh tự động trong R&D tại ConsenSys, Tôi đang sử dụng Dafny trong quá trình xác minh chính thức thông số kỹ thuật Ethereum 2 Giai đoạn 0 và tôi muốn chia sẻ lý do tại sao tôi thấy nó hữu ích.

Nền tảng của tôi

Tôi nên nói rõ rằng tôi không phải là một nhà phát triển phần mềm, mà đúng hơn là tôi coi mình là một lập trình viên toán học với một số kiến ​​thức về phát triển phần mềm. Lần đầu tiên tôi học viết chương trình như một phần trong lớp toán của mình trong năm cuối trung học và có lẽ tôi nên đề cập rằng mặc dù tôi khá thích sử dụng máy tính vào thời điểm đó, nhưng viễn cảnh học cách lập trình khiến tôi sợ hãi đến mức suýt chút nữa. bỏ lớp toán cụ thể đó. Sau khi quyết định đối mặt với nỗi sợ thất bại (liên quan đến việc học lập trình và có khả năng làm hỏng kết quả của tôi trong lớp học này), tôi đã tiếp tục trải nghiệm khoảnh khắc hiển nhiên đầu tiên của mình trong bối cảnh lập trình. Tôi vẫn còn nhớ rất rõ khi ngồi trong lớp và nhận ra rằng viết một chương trình để giải một bài toán không phải là một quá trình kỳ diệu và bí ẩn, nó gần giống như viết ra cách tôi sẽ giải quyết một vấn đề trong đầu. Không có nhìn lại sau đó! 

Lập trình là một khía cạnh quan trọng của mọi thứ mà tôi đã làm kể từ đó. Tiến sĩ về mật mã của tôi chủ yếu dựa vào khả năng phát triển các thuật toán và sau đó lập trình các triển khai tối ưu. Các chương trình của tôi được viết để thử nghiệm và mặc dù tôi không thực hiện điều mà bây giờ chúng ta gọi là thử nghiệm chính thức, tôi sẽ kiểm tra một cách không chính thức các giới hạn và các trường hợp thử nghiệm bằng cách sử dụng suy luận logic về đầu ra dự kiến. Tôi cũng đã làm việc trong nhiều năm với tư cách là một nhà nghiên cứu học thuật trong lĩnh vực tài chính và kinh tế. Một lần nữa, điều này bao gồm các chương trình viết và một lần nữa tôi sử dụng các kỹ thuật của riêng mình để kiểm tra một cách không chính thức và lý luận về tính đúng đắn của chúng. 

Công bằng mà nói, mặc dù tôi đánh giá cao thực tế rằng việc kiểm tra sẽ luôn không hoàn thiện theo nghĩa là không thể kiểm tra mọi trường hợp; rằng tôi tự tin một cách hợp lý rằng cách tư duy toán học của tôi khá tốt khi nó được kiểm tra không chính thức một cách nghiêm ngặt. Vì vậy, tôi chắc chắn đã không đánh giá được đầy đủ sự khác biệt giữa thử nghiệm và chứng minh tính đúng đắn, cũng như hậu quả của việc đó! Trong suốt sự nghiệp của mình trước khi gia nhập ConsenSys, tôi đã hài lòng dựa vào các kỹ thuật không chính thức của riêng mình để xác định điều tôi nghĩ là đúng thông qua thử nghiệm. 

Do đó, lý lịch của tôi là một phần của câu chuyện, vì bản thân tôi cũng hơi ngạc nhiên vì đã không khám phá ra các phương pháp chính thức sớm hơn. Tôi coi mình là một nhà toán học; Tôi yêu toán học, thuật toán và logic. Bây giờ có vẻ điên rồ khi chỉ dựa vào thử nghiệm không đầy đủ, nhưng cũng có vẻ điên rồ đối với bất kỳ ai lập trình không ít nhất có một số đánh giá cao về những gì các phương pháp chính thức có thể cung cấp và hậu quả tiềm ẩn của việc bỏ lỡ một lỗi do nhiều cách mà chương trình máy tính hòa nhập vào cuộc sống của chúng ta. Các phương pháp chính thức cho phép chúng tôi vượt xa thử nghiệm, để chứng minh rằng một chương trình là chính xác so với một đặc tả bao gồm các điều kiện trước và sau. 

Một ví dụ Dafny đầu tiên

Như một ví dụ đơn giản, hãy xem xét phép chia số nguyên của một số bị chia không âm n cho một ước số dương d; 


n / d

hiển thị bên dưới:

Mặc dù trong một ngôn ngữ lập trình đã nhập, chúng ta có thể hạn chế phần nào các tham số đầu vào, nhưng điều đó không phải lúc nào cũng đủ. Trong ví dụ này, đặc điểm kỹ thuật của n và d là số tự nhiên có nghĩa là cả hai đầu vào phải là số nguyên không âm nhưng nó không cung cấp hạn chế của d là số nguyên dương. Việc sử dụng một điều kiện trước theo cách của câu lệnh yêu cầu cung cấp một hạn chế như vậy và có nghĩa là phương thức này chỉ có thể được gọi nếu d > 0. Do đó, nếu bất kỳ phần nào khác của chương trình khiến div được gọi mà không thỏa mãn điều kiện trước đó, thì chương trình sẽ không xác minh. Sau đó, câu lệnh đảm bảo cung cấp điều kiện đăng và cung cấp đặc điểm kỹ thuật chính thức về những gì đầu ra phương thức phải đáp ứng.

Ví dụ này được viết bằng Dafny: “Một trình xác minh ngôn ngữ và chương trình cho tính đúng đắn của chức năng” và đưa tôi đến điểm tiếp theo của tôi, đó là lý do tại sao tôi lại là một fan hâm mộ của Dafny. Tôi nghĩ công bằng mà nói, đối với nhiều lập trình viên, ý nghĩ sử dụng “các phương pháp chính thức” để xác minh tính đúng đắn của chương trình có phần đáng sợ và thường bị cho là “quá” khó. Cho dù điều này là do thiếu tiếp xúc với các kỹ thuật, thiếu đánh giá cao các lợi ích, hoặc thậm chí thiếu đào tạo trong lĩnh vực này; bất kể lý do là gì, tôi tin rằng Dafny có khả năng cho phép bất kỳ lập trình viên nào nhanh chóng đạt được thành công trong việc áp dụng các phương pháp chính thức trong công việc của họ. Nhìn vào đoạn mã trên, tôi mong rằng bất kỳ ai có một số kiến ​​thức lập trình đều có thể đọc được đoạn mã Dafny này; Dafny là một ngôn ngữ thân thiện với lập trình viên. Khi bạn đã học được một chút về Dafny, bạn sẽ rất dễ dàng bắt đầu thử nghiệm và sau đó về cơ bản sẽ học được khi bạn tiếp tục. Và nếu bạn quan tâm đến việc học Dafny, một nơi tuyệt vời để bắt đầu là loạt bài hướng dẫn của Microsoft. Trang web cũng bao gồm một trình chỉnh sửa trực tuyến, vì vậy rất dễ dàng để thử các ví dụ hướng dẫn. Các Kênh YouTube của Góc xác minh là một nguồn tài liệu tham khảo hữu ích khác.

Khoảnh khắc hiển linh của tôi

Cuối cùng, tôi muốn chia sẻ khoảnh khắc hiển nhiên của mình kể từ khi tôi học Dafny. Tôi chắc chắn đã nghe những câu chuyện về những đoạn mã ngắn và đơn giản, từ các công ty lớn có uy tín, có những lỗi bị bỏ sót và cuối cùng tốn kém hàng triệu đô la; nhưng tôi nghĩ chỉ khi bạn tự nhận ra rằng việc vô tình tạo ra một lỗi trong một chức năng đơn giản sẽ trở nên dễ dàng như thế nào! Khoảnh khắc khi bạn tự nói với chính mình “Ồ, thật dễ mắc phải sai lầm đó!”

Khoảnh khắc của tôi đến khi xem một trong những Video về Góc xác minh

Trong hướng dẫn này, Rustan Leino thực hiện một phương thức SumMax nhận hai số nguyên, x và y và trả về tổng và max, s và m tương ứng. Ví dụ này tương đối đơn giản và mã Dafny được hiển thị bên dưới.

Các đầu vào x và y được chỉ định dưới dạng số nguyên thông qua việc nhập và không cần điều kiện tiên quyết nào khác. Ba điều kiện đăng cung cấp kiểm tra xem đầu ra có thực sự đáp ứng các thông số kỹ thuật hay không, cụ thể là s bằng x + y và m bằng x hoặc y và m không vượt quá x và y. Phương thức SumMaxBackwards sau đó được trình bày dưới dạng một bài tập và đây là lúc nó trở nên thú vị hơn. Đặc điểm kỹ thuật là đảo ngược của SumMax, tức là đã cho tổng và tối đa trả về các số nguyên x và y. Ok, vì vậy lần thử đầu tiên có thể với cùng các điều kiện sau; khi các mối quan hệ giữa đầu vào và đầu ra vẫn được duy trì. Nếu chúng ta cho x là giá trị lớn nhất thì một bit nhanh của đại số cho chúng ta biết rằng y phải bằng tổng trừ đi giá trị lớn nhất. Đưa cái này vào trình chỉnh sửa trực tuyến sẽ mang lại những điều sau.

Ảnh chụp màn hình 2020 12 15 lúc 6 giờ 38 37 giờ chiều 1 Ảnh chụp màn hình 2020 12 16 lúc 5 giờ 35 22 giờ tối

Nó không xác minh. Vậy điều gì đã xảy ra? Chúng tôi được biết rằng điều kiện sau không giữ và cụ thể là điều kiện sau ở dòng 3 (đảm bảo x<= m && y <= m) có thể không giữ. Xem xét kỹ hơn, chúng tôi thấy rằng điều kiện bài đăng này chỉ định rằng x <= m và y <= m. Vâng, chúng ta biết rằng x nhỏ hơn hoặc bằng m khi chúng ta đặt x bằng m, vì vậy điều này có nghĩa là y <= m phần không xác minh. Làm thế nào điều này có thể xảy ra? Đại số của chúng tôi cho chúng tôi biết rằng y: = s – m. Giả sử s là 5 và m là 3, khi đó y = 5 – 3 = 2 đảm bảo y <= m; nhưng giả sử chúng ta gọi phương thức này với s bằng 5 và m bằng 1. Không có gì ngăn chúng ta gọi phương thức với các tham số đầu vào này nhưng làm như vậy sẽ gây ra sự cố là y = 5 – 1 = 4 và sau đó là y > m. Về cơ bản những gì chúng ta đang thấy ở đây là mặc dù tham số đầu vào có nghĩa là tối đa của hai số nguyên tạo ra tổng s, không có gì ngăn cản chúng tôi cố gắng gọi phương thức với đầu vào không hợp lệ. Trừ khi một điều kiện tiên quyết được đưa vào để hạn chế đầu vào của s và m đối với các số nguyên hợp lệ sẽ dẫn đến kết quả đầu ra x và y đáp ứng đặc điểm kỹ thuật, khi đó phương pháp của chúng tôi có thể tạo ra kết quả không chính xác. Chúng ta cần mối quan hệ nào giữa s và m để cung cấp các đầu vào hợp lệ? Đại số hơn một chút cho chúng ta thấy rằng s <= m * 2 để có một nghiệm hợp lệ của x và y. Nếu chúng tôi thêm điều này làm điều kiện tiên quyết, Dafny hiện có thể xác minh mã như hình dưới đây. 

Ảnh chụp màn hình 2020 12 15 lúc 6 giờ 46 32 giờ chiều 1 Ảnh chụp màn hình 2020 12 16 lúc 5 giờ 37 phút chiều

Đây là ví dụ mà tôi có thể thấy việc đưa một lỗi vào mã dễ dàng như thế nào. Chỉ vì chúng ta gọi các tham số đầu vào là ‘s’ cho tổng và ‘m’ cho tối đa, không có nghĩa là phương thức sẽ được gọi một cách thích hợp và chẳng hạn như một phần của một số chương trình lớn hơn, có thể có nhiều hậu quả không mong muốn xảy ra sau đó loại lỗi. Tôi hy vọng nó hữu ích cho bất kỳ ai khác đang tìm hiểu về Dafny hoặc các phương pháp chính thức nói chung.

Tôi đang làm gì bây giờ

Điều đó đưa tôi đến cuối bài viết của tôi. Nếu bạn muốn xem những gì tôi hiện đang làm việc với Dafny thì hãy xem phần này GitHub repo. Tôi là thành viên của Nhóm xác minh tự động trong R&D tại ConsenSys và chúng tôi đang sử dụng Dafny trong việc xác minh chính thức thông số kỹ thuật Ethereum 2 Giai đoạn 0. Việc sử dụng các phương pháp chính thức trong không gian blockchain là một lĩnh vực nghiên cứu mới thú vị đã được ConsenSys chấp nhận và tôi sẽ khuyến khích bất kỳ ai quan tâm đến việc tìm hiểu thêm về Eth 2.0 hãy xem các tài nguyên có sẵn trong kho dự án của chúng tôi.

Bản tin Đăng ký nhận bản tin của chúng tôi để biết tin tức Ethereum mới nhất, các giải pháp doanh nghiệp, tài nguyên dành cho nhà phát triển và hơn thế nữa.

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