# ASP DSL Language Specification
**Version:** 1.0.0
**Status:** Complete
**Target:** Clingo ASP Solver
## Table of Contents
1. [Overview](#overview)
2. [Design Philosophy](#design-philosophy)
3. [Lexical Structure](#lexical-structure)
4. [Grammar (EBNF)](#grammar-ebnf)
5. [Syntax Elements](#syntax-elements)
6. [Type System](#type-system)
7. [Semantics](#semantics)
8. [Validation Rules](#validation-rules)
9. [Error Handling](#error-handling)
10. [Extensions](#extensions)
## Overview
The ASP DSL (Answer Set Programming Domain-Specific Language) provides a user-friendly interface for expressing ASP programs that compile to valid Clingo syntax. Unlike translation-based DSLs, ASP DSL programs ARE valid Clingo code.
### Key Characteristics
- **Clingo-Compatible:** All output is valid Clingo syntax
- **No Translation:** Programs run directly in Clingo
- **Template-Based:** Common patterns pre-built
- **Natural Language:** Problem detection from English
- **Default Logic:** Integration with default reasoning
### Design Goals
1. Generate valid Clingo code
2. Support full ASP-Core-2 standard
3. Provide helpful error messages
4. Enable LLM generation (90%+ success)
5. Support common problem patterns
## Design Philosophy
### Principle 1: Clingo First
Every ASP DSL program must be syntactically valid Clingo code:
```asp
% This is valid ASP DSL
vertex(1..5).
1 {color(V, C) : color_option(C)} 1 :- vertex(V).
% And it's also valid Clingo
% No translation needed!
```
### Principle 2: Progressive Enhancement
```
Level 0: Raw Clingo → Pass through
Level 1: Validation → Check syntax, safety
Level 2: Templates → Pre-built patterns
Level 3: Natural Language → Problem detection
Level 4: Default Logic → ADSL extension
```
### Principle 3: Helpful by Default
- Clear error messages with examples
- Suggestions for common mistakes
- Safety checking (unsafe variables)
- Performance warnings (large groundings)
## Lexical Structure
### Comments
```asp
% Single-line comment
% Comments start with % and continue to line end
```
Multi-line comments (block comments):
```asp
%*
Multi-line comment
Can span multiple lines
*%
```
### Identifiers
**Variables:** Start with uppercase or underscore
```
Variable := [A-Z_][a-zA-Z0-9_]*
Examples: X, Y, Person, _temp, _1
```
**Constants:** Start with lowercase
```
Constant := [a-z][a-zA-Z0-9_]*
Examples: alice, vertex, color1, is_valid
```
**Anonymous Variable:**
```
_ % Matches anything, doesn't bind
```
### Literals
**Integer:**
```
Integer := [0-9]+
Examples: 42, 0, 1000
```
**String:**
```
String := '"' [^"]* '"'
Examples: "hello", "file.txt"
```
**Symbolic Constant:**
```
Symbolic := [a-z][a-zA-Z0-9_]*
Examples: red, true, alice
```
### Operators
**Arithmetic:**
```
+ - * / \ % % Basic arithmetic
** % Exponentiation
|X| % Absolute value
```
**Comparison:**
```
= != < > <= >= % Comparisons
```
**Logical (in body):**
```
, % Conjunction (AND)
; % Disjunction (OR) - in choice rules
not % Default negation
- % Classical negation (strong negation)
```
**Aggregates:**
```
#count % Count elements
#sum % Sum weights
#min % Minimum value
#max % Maximum value
```
### Punctuation
```
. % Statement terminator (required!)
:- % Rule implication
{} % Choice rule braces
[] % Grouping (aggregates)
() % Predicate arguments, grouping
| % Conditional literal separator
```
## Grammar (EBNF)
Complete ASP-Core-2 grammar in Extended Backus-Naur Form:
```ebnf
(* Program structure *)
program ::= statement*
statement ::= rule | constraint | choice | weak_constraint
| directive | comment
(* Rules *)
rule ::= head ":-" body "."
head ::= atom
| disjunction
disjunction ::= atom (";" atom)+
body ::= literal ("," literal)*
| "(" body ")"
literal ::= atom
| "not" atom
| "-" atom
| comparison
| aggregate
(* Atoms *)
atom ::= predicate
| predicate "(" terms ")"
| "-" atom
predicate ::= constant
terms ::= term ("," term)*
term ::= constant
| variable
| number
| string
| arithmetic_term
| "_"
arithmetic_term ::= term operator term
| "(" arithmetic_term ")"
| "|" term "|"
operator ::= "+" | "-" | "*" | "/" | "\" | "%" | "**"
(* Comparisons *)
comparison ::= term compare_op term
compare_op ::= "=" | "!=" | "<" | ">" | "<=" | ">="
(* Choice rules *)
choice ::= "{" choice_elements "}" bounds? ":-" body "."
| "{" choice_elements "}" bounds? "."
choice_elements ::= choice_element (";" choice_element)*
choice_element ::= atom
| atom ":" condition
condition ::= literal ("," literal)*
bounds ::= lower_bound? "{" choice_elements "}" upper_bound?
lower_bound ::= term
upper_bound ::= term
(* Constraints *)
constraint ::= ":-" body "."
weak_constraint ::= ":~" body "." "[" weight "@" priority ("," terms)? "]"
weight ::= term
priority ::= term
(* Aggregates *)
aggregate ::= agg_function "{" agg_elements "}" compare_op term
| term compare_op agg_function "{" agg_elements "}"
agg_function ::= "#count" | "#sum" | "#min" | "#max"
agg_elements ::= agg_element (";" agg_element)*
agg_element ::= terms (":" condition)?
| terms "=" term (":" condition)?
(* Directives *)
directive ::= "#show" atom_spec "."
| "#hide" atom_spec "."
| "#minimize" "{" optimize_elements "}" "."
| "#maximize" "{" optimize_elements "}" "."
| "#const" constant "=" term "."
atom_spec ::= predicate "/" number
| predicate
| "-" predicate "/" number
optimize_elements ::= optimize_element (";" optimize_element)*
optimize_element ::= weight ("@" priority)? ("," terms)? ":" condition
(* Ranges *)
range ::= term ".." term
(* Lexical *)
constant ::= [a-z][a-zA-Z0-9_]*
variable ::= [A-Z_][a-zA-Z0-9_]*
number ::= [0-9]+
string ::= '"' [^"]* '"'
comment ::= '%' [^\n]* '\n'
| '%*' .*? '*%'
```
## Syntax Elements
### 1. Facts
Basic ground atoms that are always true:
```asp
% Simple facts
person(alice).
person(bob).
% Multi-argument facts
age(alice, 30).
likes(alice, bob).
% Numeric facts
temperature(72).
count(15).
```
### 2. Rules
Conditional derivations:
```asp
% Basic rule
friend(X, Y) :- knows(X, Y), trusts(X, Y).
% Multiple conditions
can_fly(X) :- bird(X), not penguin(X), not injured(X).
% Disjunctive head
sick(X); healthy(X) :- person(X).
```
**Structure:** `head :- body.`
### 3. Choice Rules
Generate alternative possibilities:
```asp
% Unrestricted choice
{selected(X) : item(X)}.
% Bounded choice
1 {assign(X, C) : color(C)} 1 :- vertex(X).
% Choice with condition
{in_team(P) : qualified(P), available(P)} :- team(T).
% Lower bound only
2 {member(P) : candidate(P)} :- committee(C).
% Upper bound only
{winner(P) : contestant(P)} 1.
```
**Semantics:**
- `{atoms}` - Choose any subset
- `L {atoms} U` - Choose between L and U atoms
- Generates multiple answer sets
### 4. Constraints
Eliminate invalid solutions:
```asp
% Integrity constraint (hard)
:- edge(X, Y), color(X, C), color(Y, C).
% No person under 18 selected
:- selected(P), age(P, A), A < 18.
% At most one leader
:- #count{P : leader(P)} > 1.
```
**Structure:** `:- conditions.`
**Semantics:** Eliminate answer sets where conditions are true.
### 5. Weak Constraints
Soft constraints for optimization:
```asp
% Prefer fewer colors
:~ assign(V, C). [1@1, V, C]
% Minimize cost, priority 2
:~ selected(I), cost(I, C). [C@2, I]
% Multi-level optimization
:~ late(P). [10@2, P] % Priority 2: minimize lateness
:~ overtime(P). [1@1, P] % Priority 1: minimize overtime
```
**Structure:** `:~ conditions. [weight@priority, terms]`
### 6. Aggregates
Count, sum, min, max operations:
```asp
% Count constraint
:- #count{P : selected(P)} > 10.
% Sum constraint
valid :- #sum{W, I : selected(I), weight(I, W)} <= 100.
% Min/Max
cheapest(I) :- item(I), cost(I, C),
#min{P : item(J), cost(J, P)} = C.
% Aggregate in choice
2 {team(P) : person(P)} 5 :- #count{P : qualified(P)} >= 5.
```
### 7. Negation
Two types of negation:
**Default Negation (not):**
```asp
% Closed-world assumption
fly(X) :- bird(X), not penguin(X).
available(R) :- resource(R), not reserved(R).
```
**Classical Negation (-):**
```asp
% Explicit falsity
-broken(M) :- tested(M), working(M).
healthy(P) :- person(P), -sick(P).
```
### 8. Comparisons
Arithmetic and symbolic comparisons:
```asp
% Numeric comparisons
adult(P) :- person(P), age(P, A), A >= 18.
cheap(I) :- price(I, P), P < 10.
% Term equality
same_color(X, Y) :- color(X, C), color(Y, C), X != Y.
% Arithmetic
sum_is_ten(X, Y) :- X + Y = 10, X > 0, Y > 0.
```
### 9. Optimization
Minimize or maximize objectives:
```asp
% Single objective
#minimize {1, X : selected(X)}.
#maximize {P, I : item(I), profit(I, P)}.
% Multi-objective (lexicographic)
#minimize {C@2, I : item(I), cost(I, C)}. % Priority 2
#maximize {Q@1, I : item(I), quality(I, Q)}. % Priority 1
```
### 10. Ranges
Compact notation for sequences:
```asp
% Expand to multiple facts
vertex(1..5). % vertex(1). vertex(2). ... vertex(5).
% In rules
row(1..N) :- size(N).
% In choice rules
{num(R, C, 1..9)} :- cell(R, C).
```
### 11. Directives
Control solver behavior:
```asp
% Show specific predicates
#show assign/2.
#show selected/1.
% Hide auxiliary predicates
#hide reached/1.
% Define constants
#const n = 10.
#const max_cost = 100.
```
## Type System
### Term Types
ASP is untyped at the language level, but terms have implicit types:
**Integer Terms:**
```asp
age(alice, 30) % 30 is integer
count(X, Y) :- X + Y = 10.
```
**Symbolic Terms:**
```asp
color(red) % red is symbolic constant
likes(alice, bob) % alice, bob are symbols
```
**Variables:**
```asp
person(X) % X is variable (untyped)
edge(X, Y) % X, Y are variables
```
### Safety Rules
**Variable Safety:** All variables in rule head must appear in positive body literal.
❌ **Unsafe:**
```asp
path(X, Y) :- edge(Y, Z). % X not in body
reach(X) :- not blocked(X). % X only in negated literal
```
✅ **Safe:**
```asp
path(Y, Z) :- edge(Y, Z).
reach(X) :- node(X), not blocked(X).
```
**Global Variables:** Variables in aggregates must be safe.
❌ **Unsafe:**
```asp
count(N) :- #count{X : Y > 0} = N. % Y not bound
```
✅ **Safe:**
```asp
count(N) :- #count{X : item(X), weight(X, Y), Y > 0} = N.
```
### Predicate Arity
Predicates must be used consistently:
❌ **Error:**
```asp
person(alice).
person(bob, 30). % Arity mismatch: person/1 vs person/2
```
✅ **Correct:**
```asp
person(alice).
person(bob).
age(alice, 25).
age(bob, 30).
```
## Semantics
### Stable Model Semantics
ASP uses stable model (answer set) semantics:
1. **Grounding:** Replace variables with all possible ground terms
2. **Guess:** For choice rules, guess which atoms to include
3. **Check:** Verify all constraints are satisfied
4. **Stability:** Ensure model is minimal (no unfounded atoms)
### Example Semantics
**Program:**
```asp
a :- not b.
b :- not a.
```
**Stable Models:**
1. `{a}` - a is true, b is false
2. `{b}` - b is true, a is false
**Non-stable:** `{}` - Neither a nor b (not minimal)
### Choice Rule Semantics
**Program:**
```asp
item(a; b; c).
{selected(X) : item(X)}.
```
**Stable Models:** 8 total (2³)
- `{}`
- `{selected(a)}`
- `{selected(b)}`
- `{selected(c)}`
- `{selected(a), selected(b)}`
- `{selected(a), selected(c)}`
- `{selected(b), selected(c)}`
- `{selected(a), selected(b), selected(c)}`
### Optimization Semantics
**Program:**
```asp
{selected(X) : item(X)}.
cost(a, 5). cost(b, 3). cost(c, 4).
#minimize {C, X : selected(X), cost(X, C)}.
```
**All Models:** 8 models
**Optimal Models:** 1 model with total cost = 0 (nothing selected)
**Alternative:** Force selection, then minimize
## Validation Rules
### 1. Syntactic Validation
- All rules end with period (.)
- Matching parentheses/brackets/braces
- Variables start with uppercase
- Constants start with lowercase
- Operators used correctly
### 2. Safety Validation
- Head variables appear in positive body literals
- Aggregate variables are bound
- No arithmetic on unbound variables
- Comparison terms are safe
### 3. Semantic Validation
- Consistent predicate arity
- No cyclic negation through odd cycles
- Aggregates are stratified (when required)
- Optimization objectives are valid
### 4. Performance Warnings
- Warn on large domains (> 10000 elements)
- Warn on potential Cartesian products
- Suggest use of conditional literals
- Recommend domain restrictions
## Error Handling
### Error Categories
1. **Syntax Errors** - Invalid Clingo syntax
2. **Safety Errors** - Unsafe variables
3. **Semantic Errors** - Logical inconsistencies
4. **Performance Warnings** - Potential issues
### Error Message Format
```
Error: [Category]
Line X: [Code snippet]
[Indicator]
[Explanation]
Suggestion: [Fix]
Example: [Correct code]
```
### Example Errors
**Unsafe Variable:**
```
Error: Unsafe variable in rule
Line 5: path(X, Y) :- edge(Y, Z).
^
Variable X appears in head but not in body
Suggestion: Change to path(Y, Z) :- edge(Y, Z).
```
**Missing Period:**
```
Error: Syntax error
Line 3: vertex(1)
^
Missing period at end of statement
Suggestion: Add period: vertex(1).
```
**Arity Mismatch:**
```
Error: Predicate arity mismatch
Line 5: person(bob, 30)
^^^^^^^^^^^^^^^
person/1 defined at line 2, used as person/2 here
Suggestion: Use consistent arity or different predicate name
```
## Extensions
### 1. Natural Language Support
ASP DSL can interpret natural language problem descriptions:
**Input:**
```
"Color a graph with 5 vertices and edges 1-2, 2-3, 3-4, 4-5, 5-1 using 3 colors"
```
**Output:**
```asp
vertex(1..5).
edge(1,2). edge(2,3). edge(3,4). edge(4,5). edge(5,1).
color(1..3).
1 {assign(X, C) : color(C)} 1 :- vertex(X).
:- assign(X, C), assign(Y, C), edge(X, Y).
#show assign/2.
```
### 2. Template System
Pre-built patterns for common problems:
```typescript
// Graph coloring template
applyTemplate('graph_coloring', {
vertices: [1, 2, 3],
edges: [[1,2], [2,3]],
numColors: 3
})
// N-Queens template
applyTemplate('n_queens', { n: 8 })
```
### 3. Default Logic (ADSL)
Extended syntax for default reasoning:
**ADSL Syntax:**
```asp
typically flies(X) if bird(X) unless penguin(X).
```
**Compiles to ASP:**
```asp
flies(X) :- bird(X), not ab_flies(X).
ab_flies(X) :- penguin(X).
```
**General Form:**
```
typically <conclusion> if <prerequisite> unless <exception>.
```
### 4. Macro System (Future)
Define reusable patterns:
```asp
#define alldifferent(Vars) :-
Vars = [X|Rest],
not member(X, Rest),
alldifferent(Rest).
#define increasing(Vars) :-
forall i in 0..len(Vars)-2:
Vars[i] <= Vars[i+1].
```
## Best Practices
### 1. Use Meaningful Names
```asp
% Good
vertex(V) :- graph_node(V).
edge_color(E, C) :- colored_edge(E, C).
% Avoid
v(X).
ec(E, C).
```
### 2. Add Comments
```asp
% Define the graph structure
vertex(1..5).
% Edges of cycle graph
edge(1,2). edge(2,3). edge(3,4). edge(4,5). edge(5,1).
```
### 3. Use #show
```asp
% Control output - only show assignments
#show assign/2.
```
### 4. Optimize Grounding
```asp
% Bad: Cartesian product
edge(X, Y) :- vertex(X), vertex(Y), X != Y.
% Better: Use order
edge(X, Y) :- vertex(X), vertex(Y), X < Y.
% Best: Use conditional literals
{edge(X, Y) : Y > X} :- vertex(X).
```
### 5. Test Incrementally
```asp
% Start small
vertex(1..3).
% Then scale up
% vertex(1..100).
```
## Grammar Summary (BNF)
Quick reference (simplified):
```bnf
<program> ::= <statement>*
<statement> ::= <rule> | <constraint> | <choice> | <directive>
<rule> ::= <head> ":-" <body> "."
<head> ::= <atom> | <atom> (";" <atom>)+
<body> ::= <literal> ("," <literal>)*
<literal> ::= <atom> | "not" <atom> | <comparison>
<choice> ::= [<term>] "{" <elements> "}" [<term>] [":-" <body>] "."
<constraint> ::= ":-" <body> "."
<atom> ::= <predicate> ["(" <terms> ")"]
<terms> ::= <term> ("," <term>)*
<term> ::= <variable> | <constant> | <number> | <arithmetic>
```
## Conformance
ASP DSL conforms to:
- **ASP-Core-2 Standard** (complete support)
- **Clingo 5.x Syntax** (full compatibility)
- **Grounding & Solving** (via Clingo subprocess)
---
**This specification defines ASP DSL v1.0.0. All programs are valid Clingo code.**
