aspi

Answer Set Programming, Interactively

This project started as an interactive shell for clingo, and is gradually morphing into an experimental programming language based on Lambda Dependency-Based Compositional Semantics (λdcs). It supports a variety of declarative programming paradigms in a cohesive manner:

• Functional programming

  fib[0]: 0.
  fib[1]: 1.
  fib[N 2..45]: fib[N-1] + fib[N-2].
  

• Relational programming

  pythag(A n2, B n2, C n2): (A**2) = ((B**2) + (C**2)).
  

• Constraint programming

  triple(A,B,C): pythag(A,B,C), ((A+B)+C) = 96?
  

  • Zebra puzzle solver
• Logic programming

  mine: block ~red ~supports.pyramid.
  in.box mine?
  

• Definite clause grammars

  #macro words[A,B]: concatenate[A, " ", B].
  sentence[s(N,V)]: words[noun_phrase.N, verb_phrase.V].
  noun_phrase[np(D,N)]: words[det D, noun N].
  verb_phrase[vp(V,N)]: words[verb V, noun_phrase.N].
  det: "a" | "the".
  noun: "bat" | "cat".
  verb: "eats".
  parse.S: sentence'.S.
  

  >>> parse."the bat eats a cat"?
  that: s(np("the","bat"),vp("eats",np("a","cat"))).
  

• Predicating type specifiers

  collatz[N even n3]: N / 2.
  collatz[N odd n3]: (3*N) + 1.
  say[N multiple.100 100..900]: concatenate[say[N/100], " hundred"].
  

• Automated planning
  • Tower of Hanoi solver
  • SHRDLU-inspired dialogue

The language is still unstable and lacking much documentation yet, but there are several example programs in this repo, e.g. solutions to Project Euler-like problems.

Syntax

λdcs can be used to write logic programs in a concise, pointfree manner. Below are a number of examples comparing how λdcs expressions translate to standard logic programs, as well as monadic functional programs.

	λdcs	ASP logic program	Haskell
Unary predicate	seattle?	what(A) :- seattle(A).	[Seattle]
Join binary to unary predicate	place_of_birth.seattle?	what(B) :- place_of_birth(B,A), seattle(A).	placeOfBirth =<< [Seattle]
Reverse operator	place_of_birth'.john?	what(B) :- place_of_birth(A,B), john(A).	inv placeOfBirth =<< [John]
Join chain	children.place_of_birth.seattle?	what(C) :- children(C,B), place_of_birth(B,A), seattle(A).	children =<< placeOfBirth =<< [Seattle]
Intersection	profession.scientist place_of_birth.seattle?	what(C) :- profession(C,A), scientist(A), place_of_birth(C,B), seattle(B).	[ x | x <- profession =<< [Scientist] , x' <- placeOfBirth =<< [Seattle] , x == x' ]
Union	oregon | washington | type.canadian_province?	what(C) :- disjunction(C). disjunction(B) :- oregon(B). disjunction(B) :- washington(B). disjunction(B) :- type(B,A), canadian_province(A).	[Oregon] <|> [Washington] <|> (type' =<< [CanadianProvince])
Negation	type.us_state ~border.california?	what(D) :- type(D,A), us_state(A), not negation(D). negation(C) :- border(C,B), california(B).	(type' =<< [USState]) \\ (border =<< [California])
Aggregation	count{type.us_state}?	what(C) :- C = #count { B : type(B,A), us_state(A) }.	[length . nub $ type' =<< [USState]]
μ abstraction	X children.influenced.X?	what(B) :- B = MuX, children(B,A), influenced(A,MuX).	[ x | x <- universe , x' <- children =<< influenced =<< [x] , x == x' ]
λ abstraction	number_of_children.X: count{children'.X}.	number_of_children(B,MuX) :- B = #count { A : children(MuX,A) }.	numberOfChildren x = [length . nub $ inv children =<< [x]]

The Haskell code above uses the following definitions:

universe :: (Bounded a, Enum a) => [a]
universe = [minBound .. maxBound]

inv :: (Bounded a, Enum a, Eq b) => (a -> [b]) -> b -> [a]
inv f y = [ x | x <- universe, y' <- f x, y == y' ]