This paper introduces Deputy, a dependently typed language designed for practical programming. Deputy integrates dependent types into a Lisp-like language, aiming to balance the power of dependent types with the flexibility and practicality of dynamic languages. It achieves this through a novel combination of features: gradual typing, allowing seamless mixing of typed and untyped code; a hybrid type checker employing both static and dynamic checks; and a focus on intensional type equality, allowing for type-level computation and manipulation. This approach makes dependent types more accessible for everyday tasks by allowing programmers to incrementally add type annotations and leverage dynamic checking when full static verification is impractical or undesirable, ultimately bridging the gap between the theoretical power of dependent types and their use in real-world software development.
Jonathan Protzenko announced the release of Evercrypt 1.0 for Python, providing a high-assurance cryptography library with over 15,000 lines of formally verified code. This release leverages the HACL* cryptographic library, which has been mathematically proven correct, and makes it readily available for Python developers through a simple and performant interface. Evercrypt aims to bring robust, verified cryptographic primitives to a wider audience, improving security and trustworthiness for applications that depend on strong cryptography. It offers a drop-in replacement for existing libraries, significantly enhancing the security guarantees without requiring extensive code changes.
Hacker News users discussed the implications of having 15,000 lines of verified cryptography in Python, focusing on the trade-offs between verification and performance. Some expressed skepticism about the practical benefits of formal verification for cryptographic libraries, citing the difficulty of verifying real-world usage and the potential performance overhead. Others emphasized the importance of correctness in cryptography, arguing that verification offers valuable guarantees despite its limitations. The performance costs were debated, with some suggesting that the overhead might be acceptable or even negligible in certain scenarios. Several commenters also discussed the challenges of formal verification in general, including the expertise required and the limitations of existing tools. The choice of Python was also questioned, with some suggesting that a language like OCaml might be more suitable for this type of project.
Clean is a new domain-specific language (DSL) built in Lean 4 for formally verifying zero-knowledge circuits. It aims to bridge the gap between circuit development and formal verification by offering a high-level, functional programming style for defining circuits, along with automated proofs of correctness within Lean's powerful theorem prover. Clean compiles to the intermediate representation used by the Circom zk-SNARK toolkit, enabling practical deployment of verified circuits. This approach allows developers to write circuits in a clear, maintainable way, and rigorously prove that these circuits correctly implement the desired logic, enhancing security and trust in zero-knowledge applications. The DSL includes features like higher-order functions and algebraic data types, enabling more expressive and composable circuit design than existing tools.
Several Hacker News commenters praise Clean's innovative approach to verifying zero-knowledge circuits, appreciating its use of Lean4 for formal proofs and its potential to improve the security and reliability of ZK systems. Some express excitement about Lean4's dependent types and metaprogramming capabilities, and how they might benefit the project. Others raise practical concerns, questioning the performance implications of using a theorem prover for this purpose, and the potential difficulty of debugging generated circuits. One commenter questions the comparison to other frameworks like Noir and Arkworks, requesting clarification on the specific advantages of Clean. Another points out the relative nascency of formal verification in the ZK space, emphasizing the need for further development and exploration. A few users also inquire about the tooling and developer experience, wondering about the availability of IDE support and debugging tools for Clean.
Inko is a programming language designed for building reliable and efficient concurrent software. It features a static type system with algebraic data types and pattern matching, aiding in catching errors at compile time. Inko's concurrency model leverages actors and message passing to avoid shared memory and the associated complexities of mutexes and locks. This actor-based approach, coupled with automatic memory management via garbage collection, aims to simplify the development of concurrent programs and reduce the risk of data races and other concurrency bugs. Furthermore, Inko prioritizes performance and offers efficient compilation to native code. The language seeks to provide a practical and robust solution for modern concurrent programming challenges.
Hacker News users discussed Inko's features, drawing comparisons to Rust and Pony. Several commenters expressed interest in the actor model and ownership/borrowing system for concurrency. Some questioned Inko's practicality and adoption potential given the existing competition, while others were curious about its performance characteristics and real-world applications. The garbage collection aspect was a point of contention, with some viewing it as a drawback for performance-critical applications. A few users also mentioned their previous experiences with the language, highlighting both positive and negative aspects. There was general curiosity about the language's maturity and the size of its community.
The seL4 microkernel is a highly secure and reliable operating system foundation, formally verified to guarantee functional correctness and security properties. This verification proves that the implementation adheres to its specification, encompassing properties like data integrity and control-flow integrity. Designed for high-performance and real-time embedded systems, seL4's small size and minimal interface facilitate formal analysis and predictable resource usage. Its strong isolation mechanisms enable the construction of robust systems where different components with varying levels of trust can coexist securely, preventing failures in one component from affecting others. The kernel's open-source nature and liberal licensing promote transparency and wider adoption, fostering further research and development in secure systems.
Hacker News users discussed the seL4 microkernel, focusing on its formal verification and practical applications. Some questioned the real-world impact of the verification, highlighting the potential for vulnerabilities outside the kernel's scope, such as in device drivers or user-space applications. Others praised the project's rigor and considered it a significant achievement in system software. Several comments mentioned the challenges of using microkernels effectively, including the performance overhead of inter-process communication (IPC). Some users also pointed out the limited adoption of microkernels in general, despite their theoretical advantages. There was also interest in seL4's use in specific applications like autonomous vehicles and aerospace.
Deduce is a proof checker designed specifically for educational settings. It aims to bridge the gap between informal mathematical reasoning and formal proof construction by providing a simple, accessible interface and a focused set of logical connectives. Its primary goal is to teach the core concepts of formal logic and proof techniques without overwhelming users with complex syntax or advanced features. The system supports natural deduction style proofs and offers immediate feedback, guiding students through the process of building valid arguments step-by-step. Deduce prioritizes clarity and ease of use to make learning formal logic more engaging and less daunting.
Hacker News users discussed the educational value of the Deduce proof checker. Several commenters appreciated its simplicity and accessibility compared to other systems like Coq, finding its focus on propositional and first-order logic suitable for introductory logic courses. Some suggested potential improvements, such as adding support for natural deduction and incorporating a more interactive tutorial. Others debated the pedagogical merits of different proof styles and the balance between automated assistance and requiring students to fill in proof steps themselves. The overall sentiment was positive, with many seeing Deduce as a promising tool for teaching logic.
Verification-first development (VFD) prioritizes writing formal specifications and proofs before writing implementation code. This approach, while seemingly counterintuitive, aims to clarify requirements and design upfront, leading to more robust and correct software. By starting with a rigorous specification, developers gain a deeper understanding of the problem and potential edge cases. Subsequently, the code becomes a mere exercise in fulfilling the already-proven specification, akin to filling in the blanks. While potentially requiring more upfront investment, VFD ultimately reduces debugging time and leads to higher quality code by catching errors early in the development process, before they become costly to fix.
Hacker News users discussed the practicality and benefits of verification-first development (VFD). Some commenters questioned its applicability beyond simple examples, expressing skepticism about its effectiveness in complex, real-world projects. Others highlighted potential drawbacks like the added time investment for writing specifications and the difficulty of verifying emergent behavior. However, several users defended VFD, arguing that the upfront effort pays off through reduced debugging time and improved code quality, particularly when dealing with complex logic. Some suggested integrating VFD gradually, starting with critical components, while others mentioned tools and languages specifically designed to support this approach, like TLA+ and Idris. A key point of discussion revolved around finding the right balance between formal verification and traditional testing.
Niri is a new programming language designed for building distributed systems. It aims to simplify concurrent and parallel programming by introducing the concept of "isolated objects" which communicate via explicit message passing, eliminating shared mutable state and thus avoiding data races and other concurrency bugs. This approach, coupled with automatic memory management and a focus on performance, makes Niri suitable for developing robust and efficient distributed applications, potentially replacing complex actor models or other concurrency paradigms. The language is still under development, but shows promise for streamlining the creation of complex distributed systems.
Hacker News users discussed Niri's potential, focusing on its novel approach to UI design. Several commenters expressed excitement about the demo, praising its speed and the innovative concept of manipulating data directly within the interface. Concerns were raised about the practicality of text-based interaction for complex tasks and the potential learning curve. Some questioned the long-term viability of relying solely on a keyboard-driven interface, while others saw it as a powerful tool for experienced users. The discussion also touched upon comparisons to other tools like spreadsheets and the potential benefits for specific use cases like data analysis and programming. Some users expressed skepticism, finding the current implementation limited and wanting to see more concrete examples of its capabilities.
The paper "Constant-time coding will soon become infeasible" argues that maintaining constant-time implementations for cryptographic algorithms is becoming increasingly challenging due to evolving hardware and software environments. The authors demonstrate that seemingly innocuous compiler optimizations and speculative execution can introduce timing variability, even in carefully crafted constant-time code. These issues are exacerbated by the complexity of modern processors and the difficulty of fully understanding their intricate behaviors. Consequently, the paper concludes that guaranteeing constant-time execution across different architectures and compiler versions is nearing impossibility, potentially jeopardizing the security of cryptographic implementations relying on this property to prevent timing attacks. They suggest exploring alternative mitigation strategies, such as masking and blinding, as more robust defenses against side-channel vulnerabilities.
HN commenters discuss the implications of the research paper, which suggests constant-time programming will become increasingly difficult due to hardware optimizations like speculative execution. Several express concern about the future of cryptography and security-sensitive code, as these rely heavily on constant-time implementations to prevent side-channel attacks. Some doubt the practicality of the attack described, citing existing mitigations and the complexity of exploiting microarchitectural side channels. Others propose software-based defenses, such as using interpreter-based languages, formal verification, or inserting random delays. The feasibility and cost of deploying these mitigations are also debated, with some arguing that the burden will fall disproportionately on developers. There's also skepticism about the paper's claims of "infeasibility," with commenters suggesting that constant-time coding will become more challenging but not impossible.
This paper details the formal verification of a garbage collector for a substantial subset of OCaml, including higher-order functions, algebraic data types, and mutable references. The collector, implemented and verified using the Coq proof assistant, employs a hybrid approach combining mark-and-sweep with Cheney's copying algorithm for improved performance. A key achievement is the proof of correctness showing that the garbage collector preserves the semantics of the original OCaml program, ensuring no unintended behavior alterations due to memory management. This verification increases confidence in the collector's reliability and serves as a significant step towards a fully verified implementation of OCaml.
Hacker News users discuss a mechanically verified garbage collector for OCaml, focusing on the practical implications of such verification. Several commenters express skepticism about the real-world performance impact, questioning whether the verification translates to noticeable improvements in speed or reliability for average users. Some highlight the trade-offs between provable correctness and potential performance limitations. Others note the significance of the work for critical systems where guaranteed safety and predictable behavior are paramount, even at the cost of some performance. The discussion also touches on the complexity of garbage collection and the challenges in achieving both efficiency and correctness. Some commenters raise concerns about the applicability of the specific approach to other languages or garbage collection algorithms.
AdaCore has announced the winners of its "Ada/SPARK Crate of the Year 2024" competition. The gold award went to Libadalang-TV, a library providing a tree view for Libadalang, simplifying Ada and SPARK code analysis. Silver was awarded to Ada-Scintilla, a binding for the Scintilla editing component, enhancing Ada and SPARK development environments. Finally, Florist, a tool for static analysis of formal verification results, took home the bronze. These crates demonstrate community contributions to improving the Ada and SPARK ecosystem, providing valuable tools for development, analysis, and verification.
Hacker News users discussed the winning Ada/SPARK crates, expressing interest in Creatif's accessibility features for blind programmers and praising its maintainers' dedication. Some questioned the term "crate" in the Ada context, suggesting "package" or "library" as more fitting. A few comments highlighted Ada's strengths in safety-critical systems, contrasting its niche status with the broader popularity of Rust, while also acknowledging Rust's growing presence in similar domains. One commenter pondered the reasons behind Ada's limited adoption despite its technical merits.
This paper explores the potential of Large Language Models (LLMs) as tools for mathematicians. It examines how LLMs can assist with tasks like generating conjectures, finding proofs, simplifying expressions, and translating between mathematical formalisms. While acknowledging current limitations such as occasional inaccuracies and a lack of deep mathematical understanding, the authors demonstrate LLMs' usefulness in exploring mathematical ideas, automating tedious tasks, and providing educational support. They argue that future development focusing on formal reasoning and symbolic computation could significantly enhance LLMs' capabilities, ultimately leading to a more symbiotic relationship between mathematicians and AI. The paper also discusses the ethical implications of using LLMs in mathematics, including concerns about plagiarism and the potential displacement of human mathematicians.
Hacker News users discussed the potential for LLMs to assist mathematicians, but also expressed skepticism. Some commenters highlighted LLMs' current weaknesses in formal logic and rigorous proof construction, suggesting they're more useful for brainstorming or generating initial ideas than for producing finalized proofs. Others pointed out the importance of human intuition and creativity in mathematics, which LLMs currently lack. The discussion also touched upon the potential for LLMs to democratize access to mathematical knowledge and the possibility of future advancements enabling more sophisticated mathematical reasoning by AI. There was some debate about the specific examples provided in the paper, with some users questioning their significance. Overall, the sentiment was cautiously optimistic, acknowledging the potential but emphasizing the limitations of current LLMs in the field of mathematics.
This article dissects the structure of a formal mathematical proof, illustrating it with a simple example about even and odd numbers. It emphasizes the distinction between informal proofs aimed at human understanding and formal proofs designed for automated verification. Formal proofs meticulously lay out every logical step, referencing specific axioms and inference rules within a chosen formal system. This detailed approach, while tedious for humans, enables computer-assisted verification and eliminates ambiguity, ensuring absolute rigor. The article highlights the importance of choosing appropriate axioms and the role of proof assistants in constructing and checking these complex formal structures, ultimately increasing confidence in mathematical results.
HN commenters discuss the accessibility of formal proof systems, particularly referencing Lean. Some express excitement about the potential of formal proofs to revolutionize mathematics, while others are more skeptical, citing the steep learning curve and questioning the practical benefits for most mathematicians. Several commenters debate the role of intuition versus rigor in mathematical practice, with some arguing that formalization can enhance understanding and others suggesting it might stifle creativity. The feasibility of formalizing existing mathematical knowledge is also discussed, with varying opinions on the timescale and resources required for such a project. Some users highlight the potential of AI in assisting with formalization efforts, while others remain cautious about its current capabilities. The overall tone is one of cautious optimism, acknowledging the challenges but also recognizing the potential transformative power of formal proof systems.
This paper introduces Crusade, a formally verified translation from a subset of C to safe Rust. Crusade targets a memory-safe dialect of C, excluding features like arbitrary pointer arithmetic and casts. It leverages the Coq proof assistant to formally verify the translation's correctness, ensuring that the generated Rust code behaves identically to the original C, modulo non-determinism inherent in C. This rigorous approach aims to facilitate safe integration of legacy C code into Rust projects without sacrificing confidence in memory safety, a critical aspect of modern systems programming. The translation handles a substantial subset of C, including structs, unions, and functions, and demonstrates its practical applicability by successfully converting real-world C libraries.
HN commenters discuss the challenges and nuances of formally verifying the C to Rust transpiler, Cracked. Some express skepticism about the practicality of fully verifying such a complex tool, citing the potential for errors in the formal proofs themselves and the inherent difficulty of capturing all undefined C behavior. Others question the performance impact of the generated Rust code. However, many commend the project's ambition and see it as a significant step towards safer systems programming. The discussion also touches upon the trade-offs between a fully verified transpiler and a more pragmatic approach focusing on common C patterns, with some suggesting that prioritizing practical safety improvements could be more beneficial in the short term. There's also interest in the project's handling of concurrency and the potential for integrating Cracked with existing Rust tooling.
Summary of Comments ( 1 )
https://news.ycombinator.com/item?id=44041515
Hacker News users discuss the paper "The Lisp in the Cellar: Dependent Types That Live Upstairs," focusing on the practicality and implications of its approach to dependent types. Some express skepticism about the claimed performance benefits and question the trade-offs made for compile-time checking. Others praise the novelty of the approach, comparing it favorably to other dependently-typed languages like Idris and highlighting the potential for more efficient and reliable software. A key point of discussion revolves around the use of a "cellar" for runtime values and an "upstairs" for compile-time values, with users debating the elegance and effectiveness of this separation. There's also interest in the language's metaprogramming capabilities and its potential for broader adoption within the functional programming community. Several commenters express a desire to experiment with the language and see further development.
The Hacker News post titled "The Lisp in the Cellar: Dependent Types That Live Upstairs [pdf]" links to a PDF describing a programming language called Deputy. The discussion in the comments section is relatively brief, with a focus on the practicality and implications of the presented ideas.
One commenter expresses skepticism about the overall benefit of dependent types, questioning if the added complexity is worth the effort and if the advantages primarily apply to specific niches like formal verification. They seem to imply that for general-purpose programming, the trade-offs might not be favorable.
Another commenter points out a perceived similarity between Deputy's approach and the concept of gradual typing. They suggest that Deputy seems to be striving for a system where dependent types can be introduced incrementally, allowing developers to choose where and when to apply the stricter typing discipline.
A third comment delves into the technical details of Deputy's type system, highlighting its use of elaboration and normalization. They specifically mention that values are normalized during elaboration, comparing this approach to how Agda, another dependently typed language, handles type checking. They also raise a question about the implementation of large eliminations, a technical aspect related to how dependent types are handled in practice.
Finally, someone notes the irony in the paper's title, "The Lisp in the Cellar: Dependent Types That Live Upstairs," by pointing out that historically, Lisp has often been associated with more academic or advanced programming concepts, while dependent types are now being brought into that same realm. This comment focuses on the shifting perceptions and adoption of these programming paradigms.
While there are other comments, they are largely short expressions of interest, questions about specific technical details, or requests for clarification. The comments summarized above represent the most substantial points of discussion and offer insights into the community's reaction to the Deputy language and its features.