How mala1180/pps-22-satify works
Project Type and Purpose
• Satify is a standalone, open-source, pure-functional SAT solver written in Scala 3.
• It provides:
• A DSL to express boolean formulas and classical problems (N-Queens, Graph Coloring, Nurse Scheduling).
• Two core algorithms: Tseitin transformation (formula → CNF) and DPLL search (CNF satisfiability).
• An MVU (Model-View-Update) architectural shell for interactive use (CLI/REPL style).
File-Structure Analysis
• Top-level: build files (build.sbt), CI/CD workflows (.github/workflows), docs (doc/), source (src/), tests (src/test/).
• src/main/scala/satify: four main packages:
• dsl: user-facing language constructs and conversions.
• model: domain types (Expression, CNF, Problems, Solver models, Errors).
• update: MVU “controller” layer broken into Parser, Converters, Solver implementations.
• view: UI components and rendering logic.
• satify/app: MVU orchestration (Architecture.scala, Main.scala).
• Resources: sample CNF files, images for the UI/logo.
• Tests mirror this structure using both unit and Cucumber-style feature tests.
Key README Insights
• Emphasis on immutability, declarative/api style, idiomatic Scala.
• Two main algorithms: Tseitin (CNF conversion) and DPLL (SAT search).
• DSL use cases and provided example problems.
1. Application Shell (satify.app.Main)
2. DSL Layer (satify.dsl)
3. Model Layer (satify.model)
4. Update Layer (satify.update)
– Parser (DimacsParser)
– Converters (TseitinTransformation)
– Solver (DPLL variants)
5. View Layer (satify.view)
6. External I/O (CLI or file inputs/outputs)
• User Input → Application Shell → DSL Layer (or → Parser for DIMACS)
• DSL Layer → Model Layer (builds Expression or Problem instances)
• Model Layer → Update Layer/Converters (generates CNF)
• Update Layer/Parser + Converters → Solver → Solution in Model Layer
• Model Layer (Solution/State) → View Layer → Console/UI Output
c. Architectural Patterns & Principles:
– MVU (Model-View-Update) in satify.app
– Functional pipelines: DSL → Model → Conversion → Solver → View
– Immutable data models (case class), pure functions (no mutable state)
– Separation of concerns by package: DSL, Domain, Controller, UI
d. Technologies & Frameworks:
– Scala 3.3.0, sbt 1.9.1, JDK 17
– Scala pattern matching for parser and converters
– Cucumber (via src/test/resources/features) for BDD tests
– No external UI framework (console-based view using Scala’s native libs)
Essential Elements
– Component labels & package names
– Notes on immutability and pure functions at the boundaries