classifier.scala

classifier.scala

object SententialCalculus {
  // Here is a scala program which classifies an SC sentence.
  // It recognizes whether the sentence is an SC sentence,
  // and returns the parsed typed tree.
  // You can run this with the following command, but here's
  // an executive summary.
  //    fsc -d build classifier.scala && scala -classpath build SententialCalculus
  // Executive summary:
  // If the input is a single predicate atom, this is an atom.
  // If the input starts with a NOT, this is a negation.
  // If the input is anything surrounded by parens, then:
  //    Scan left to right on the inside, incrementing the count
  //    for each left paren, and decrementing for each right paren.
  //    When you find an operator (except NOT) where the counter is zero,
  //    that's the operator that represents the whole expression.

  sealed trait SCSentence
  case class Atom(name: String)                        extends SCSentence
  case class Negation(a: SCSentence)                   extends SCSentence
  case class Conjunction(a: SCSentence, b: SCSentence) extends SCSentence
  case class Disjunction(a: SCSentence, b: SCSentence) extends SCSentence
  case class Implication(a: SCSentence, b: SCSentence) extends SCSentence
  case class Iff(a: SCSentence, b: SCSentence)         extends SCSentence

  // Predicates and operator symbols.
  val predicates = "PQRSTUV".toList // etc
  val NOT = '¬'
  val AND = '⋀'
  val OR = '⋁'
  val EQUIV='↔'
  val IMPLY='→'

  def main(args: Array[String]) {
    // Run this on the Question 2 sentences.
    report("¬ ((P → Q) ⋁ (P ⋀ S))")
    report("(¬ (P → (Q ⋁ (P ⋀ S))))")
    report("(¬ (P → Q) ⋁ (P ⋀ S))")
    report("(((¬ P → Q) ⋁ P) ⋀ S)")
    // Run this on the Question 4 sentences.
    report("(((P⋀Q)→R)→((P→R)⋁(Q→R)))")
    report("((((P⋀Q)→R)→(P→R))⋁(Q→R))")
    report("(((((P⋀Q)→R)→(P→R))⋁Q)→R)")
    report("((¬Q⋀¬R)↔¬(¬P↔¬((Q⋁R)↔¬P)))")
  }
  
  def report(input: String) {
    // Print the sentence and it's type tree.
    val result = scparse2(input)
    println(s"$input    ${result.map(repr)}")
  }
  
  def repr(input: SCSentence): String = input match {
    // Rebuild standard string representation.
    case Atom(name: String) => name.toString
    case Negation(a) => s"$NOT${repr(a)}"
    case Conjunction(a, b) => s"(${repr(a)} $AND ${repr(b)})"
    case Disjunction(a, b) => s"(${repr(a)} $OR ${repr(b)})"
    case Implication(a, b) => s"(${repr(a)} $EQUIV ${repr(b)})"
    case Iff(a, b) => s"(${repr(a)} $IMPLY ${repr(b)})"
  }
  
  def scparse2(input: String): Option[SCSentence] = {
    // Remove spaces and convert to list for ez parsing.
    scparse(input.toList.filter(x => x != ' '))
  }
  
  def scparse(input: List[Char]): Option[SCSentence] = {
    // Check what kind of thing it is.
    input match {
      case List(p) if predicates.contains(p) =>
        Some(Atom(p.toString))
      case NOT :: tail =>
        // Validate the tail as well.
        scparse(tail).flatMap(tail => Some(Negation(tail)))
      case '(' +: mid :+ ')' => Some(Conjunction)
        // Grab the zero-depth operator, make sure it's legit,
        // and validate the tree branches recursively.
        find_depth_zero_operator(mid).flatMap{ index =>
          val (head, xtail) = mid.splitAt(index)
          val tail = xtail.tail
          (scparse(head), scparse(tail)) match {
            case (Some(head), Some(tail)) =>
              (mid(index) match {
                case `AND` => Some(Conjunction(head, tail))
                case `OR` => Some(Disjunction(head, tail))
                case `EQUIV` => Some(Iff(head, tail))
                case `IMPLY` => Some(Implication(head, tail))
                case _ => None
              })
            case _ => None
          }
        }
      case _ => None
    }
  }
  
  def find_depth_zero_operator(input: List[Char]): Option[Int] = {
    // Scan to find a non-redicate symbol (hopefully operator)
    // at depth 0.
    var depth = 0;
    for ((c, index) <- input.zipWithIndex) {
      c match {
        case '(' => depth += 1;
        case ')' => depth -= 1;
        case p if predicates.contains(p) || p == NOT =>
        case _ if (depth == 0) => return Some(index)
        case _ =>
      }
    }
    return None
  }
}

$ fsc -d build classifier.scala && scala -classpath build SententialCalculus
¬ ((P → Q) ⋁ (P ⋀ S))    Some(¬((P → Q) ⋁ (P ⋀ S)))
(¬ (P → (Q ⋁ (P ⋀ S))))    None
(¬ (P → Q) ⋁ (P ⋀ S))    Some((¬(P → Q) ⋁ (P ⋀ S)))
(((¬ P → Q) ⋁ P) ⋀ S)    Some((((¬P → Q) ⋁ P) ⋀ S))
(((P⋀Q)→R)→((P→R)⋁(Q→R)))    Some((((P ⋀ Q) → R) → ((P → R) ⋁ (Q → R))))
((((P⋀Q)→R)→(P→R))⋁(Q→R))    Some(((((P ⋀ Q) → R) → (P → R)) ⋁ (Q → R)))
(((((P⋀Q)→R)→(P→R))⋁Q)→R)    Some((((((P ⋀ Q) → R) → (P → R)) ⋁ Q) → R))
((¬Q⋀¬R)↔¬(¬P↔¬((Q⋁R)↔¬P)))    Some(((¬Q ⋀ ¬R) ↔ ¬(¬P ↔ ¬((Q ⋁ R) ↔ ¬P))))