Down With Abstractions – HackerRank Solution

In this post, we will solve Down With Abstractions HackerRank Solution. This problem (Down With Abstractions) is a part of HackerRank Functional Programming series.

Contents

Task

Lambda calculus is a model of computation based on nothing but anonymous functions. Despite being one of the simplest and most elegant such models, it is perceived as a little too complicated by some. After all, it has function abstraction and variables! Combinatory logic, developed by Schonfinkel and Curry, is an equivalent model of computation that uses nothing but function application and a very small set of pre-defined combinators. Moreover, expressions of lambda calculus can be mechanically transformed to equivalent expressions in combinatory logic using a simple algorithm. Your task is to implement this algorithm.

Combinators

We will use the following combinators for the language of resulting combinatory logic expressions:

K = (\x y. x)

K is a constant function generator. Given some x, it evaluates to a function that evaluates to x for all inputs.

S = (\x y z. ((x z) (y z)))

S is a substitution function.

Note that S and K alone form a Turing-complete model of computation. But for convenience we will use three other combinators as well.

I = (\x. x)

Identity function. Extensionally equivalent to SKK.

B = (\x y z. (x (y z)))

B is function composition, aka “dot“. Extensionally equivalent to S(KS)K.

C = (\x y z. ((x z) y))

C returns a given binary function with its two parameters flipped. Extensionally equivalent to S(S(K(S(KS)K))S)(KK).

B and C are specializations of S.

Grammar for lambda calculus expressions

We will use a variant of lambda expression syntax for our inputs. The differences from the standard notation are as follows:

  1. Lowercase lambda in lambda expressions is represented by a backslash (‘\‘).
  2. Function applications must be parenthesized.
  3. Lambda expressions must be parenthesized.
  4. Lambda expressions are extended to easily formulate functions of arbitrary arity (in fully curried form). (\x y z. ((z y) x)) is equivalent to (\x. (\y. (\z. ((z y) x))))

Variable names are represented by arbitrary non-empty sequences of Latin upper- and lowercase letters, numbers and underscores. Other tokens are ‘(‘, ‘)‘, ‘\‘ and ‘.‘. Tokens may be separated by arbitrary amount of whitespace without changing the meaning. Whitespace is required in some contexts, as described below.

EXP = VAR
EXP = '(' EXP ' ' EXP ')'
EXP = '(' '\' VARLIST '.' EXP ')'
VARLIST = VAR VARLIST0
VARLIST0 = eps
VARLIST0 = ' ' VAR VARLIST0

Abstraction elimination algorithm

Use the version with rules for SKIBC at:

http://en.wikipedia.org/wiki/Abstraction_elimination#Combinators_B.2C_C

Apply eta-reduction wherever possible:

http://en.wikipedia.org/wiki/Abstraction_elimination#.CE.B7-reduction

Eta-reduction removes unnecessary abstraction, making use of the fact that (\x. (E x)) is equivalent to E.

Free variables in lambda calculus

Performing abstraction elimination requires determining the free variables of a given expression. In lambda calculus, a variable is free in an expression if it’s not a parameter in any of the enclosing lambda expressions. The opposite of a free variable is a bound variable. For example:

(\x. (z (\y. (y x)))

In this expression, z is a free variable, while x and y are bound variables. If we consider just the following sub-expression:

(z (\y. (y x))

…then only y is a bound variable in it. Both x and z are free variables in this expression.

Input

First line contains number of test cases, 1 <= T <= 100. T lines follow. Each line contains a lambda expression. Lambda expressions in the test cases contain no free variables at the top level. This ensures that the equivalent combinatory logic expression can be written using nothing but the five combinators listed above.

Output

Output T lines with equivalent representations of given lambda expressions in SKIBC-basis combinatory logic.

Sample Input

3
(\x. x)
(\test. (\ignored_1. test))
(\x. (\y. (y (\z. (\t. ((z (\x. x)) x))))))

Sample Output

I
K
B(CI)(B(BK)(C(CII)))   

Notes

When outputting the results, consider function application to be left-associative and do not output superfluous parentheses.

There are infinitely many combinatory logic expressions that are extensionally equivalent to a given lambda expression. Moreover, the problem of determining extensional equivalence is undecidable. To pass the test cases, use the algorithm as outlined on the linked page, using all five combinators, and performing eta-conversion whenever possible.

Solution – Down With Abstractions – HackerRank Solution

Scala

import java.util.Scanner

trait Lexeme

trait PrimaryLexeme extends Lexeme

case object Backslash extends PrimaryLexeme

case object Point extends PrimaryLexeme

case object OpenRoundBracket extends PrimaryLexeme

case object CloseRoundBracket extends PrimaryLexeme

trait Body {
  def freeVariables: Set[String] = Set()
}

case class Variable(name: String) extends PrimaryLexeme with Body {
  override lazy val freeVariables: Set[String] = Set(name)
}

trait SecondaryLexeme extends Lexeme

case class Lambda(name: String, body: Body) extends SecondaryLexeme with Body {
  override lazy val freeVariables: Set[String] = body.freeVariables - name
}

case class Application(e1: Body, e2: Body) extends SecondaryLexeme with Body {
  override lazy val freeVariables: Set[String] = e1.freeVariables ++ e2.freeVariables

  override def toString: String = e2 match {
    case _: Application => s"$e1($e2)"
    case _ => s"$e1$e2"
  }
}

case object Empty extends Body

case object K extends Body

case object I extends Body

case object S extends Body

case object C extends Body

case object B extends Body

case class T(body: Body) extends SecondaryLexeme with Body {

  def transform: Body = {
    val res = body match {
      //eta-reduction (if x is not free in E)
      case Lambda(x, Application(e, Variable(y))) if x == y && isNotFree(x, e) =>
        T(e).transform

      //1
      case v: Variable =>
        v

      //2
      case Application(e1, e2) =>
        Application(T(e1).transform, T(e2).transform)

      //3. (if x is not free in E)
      case Lambda(x, e) if isNotFree(x, e) =>
        Application(K, T(e).transform)

      //4
      case Lambda(x, Variable(y)) if x == y =>
        I

      //5. (if x is free in E)
      case Lambda(x, Lambda(y, e)) if isFree(x, e) =>
        T(Lambda(x, T(Lambda(y, e)).transform)).transform

      //6. (if x is free in both E₁ and E₂)
      case Lambda(x, Application(e1, e2)) if isFree(x, e1) && isFree(x, e2) =>
        Application(Application(S, T(Lambda(x, e1)).transform), T(Lambda(x, e2)).transform)

      //7.  (if x is free in E₁ but not E₂)
      case Lambda(x, Application(e1, e2)) if isFree(x, e1) && isNotFree(x, e2) =>
        Application(Application(C, T(Lambda(x, e1)).transform), T(e2).transform)

      //8. (if x is free in E₂ but not E₁)
      case Lambda(x, Application(e1, e2)) if isNotFree(x, e1) && isFree(x, e2) =>
        Application(Application(B, T(e1).transform), T(Lambda(x, e2)).transform)

      case v =>
        v
    }

    res
  }

  private def isFree(x: String, e: Body): Boolean = e.freeVariables.contains(x)

  private def isNotFree(x: String, e: Body): Boolean = !isFree(x, e)
}

object Expression {

  def findCloseBracket(lexemes: List[Lexeme], openBracket: Lexeme, closeBracket: Lexeme): (List[Lexeme], List[Lexeme]) = {
    case class Acc(lexemes: List[Lexeme] = Nil, bracketCount: Int = 1)
    @scala.annotation.tailrec
    def inner(lexemes: List[Lexeme], acc: Acc = Acc()): (List[Lexeme], List[Lexeme]) = {
      lexemes match {
        case ([email protected]'closeBracket') :: lexemes =>
          if (acc.bracketCount == 1) (acc.lexemes.reverse, lexemes)
          else inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount - 1))
        case ([email protected]'openBracket') :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount + 1))
        case lex :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount))
        case Nil => throw new Exception("Wrong exception")
      }
    }

    inner(lexemes)
  }
}

object Solution {
  def curry(name: String, otherNames: List[String], body: Body): Lambda = otherNames match {
    case Nil => Lambda(name, body)
    case n :: ns => Lambda(name, curry(n, ns, body))
  }

  def toLambda(lexemes: List[Lexeme]): Body = lexemes match {
    case Nil => Empty

    case (v: Variable) :: Nil => v

    case (v: Variable) :: rest => Application(v, toLambda(rest))

    case OpenRoundBracket :: Backslash :: rest =>
      val (bound, tempRest) = rest.span(_ != Point)
      val (part, nextRest) = findCloseBracket(tempRest.tail)
      val names = bound.collect { case Variable(name) => name }
      val lambda = curry(names.head, names.tail, toLambda(part))

      if (nextRest.isEmpty) lambda
      else Application(lambda, toLambda(nextRest))

    case OpenRoundBracket :: (v: Variable) :: rest =>
      val (part, nextRest) = findCloseBracket(rest)

      if (part.isEmpty) v
      else {
        val app = Application(v, toLambda(part))
        if (nextRest.isEmpty) app
        else Application(app, toLambda(nextRest))
      }

    case OpenRoundBracket :: OpenRoundBracket :: rest =>
      val (part, nextRest) = findCloseBracket(OpenRoundBracket :: rest)

      if (nextRest.isEmpty) toLambda(part)
      else Application(toLambda(part), toLambda(nextRest))

    case _ => throw new Exception("Wrong expression")
  }

  def solve(s: String): Body = {
    def toLexemes: List[Lexeme] = {
      val lexemeNames = Map(
        "\\" -> Backslash,
        "." -> Point,
        "(" -> OpenRoundBracket,
        ")" -> CloseRoundBracket
      )

      def parseLexeme(index: Int, predicate: Char => Boolean): (Int, String) = {
        @scala.annotation.tailrec
        def inner(index: Int, sb: StringBuilder = new StringBuilder): (Int, String) = if (index < s.length) {
          val c = s(index)
          if (predicate(c)) inner(index + 1, sb.append(c)) else (index, sb.toString())
        } else (index, sb.toString())

        inner(index)
      }

      case class State(index: Int = 0, acc: List[Lexeme] = Nil)

      @scala.annotation.tailrec
      def inner(state: State): State = if (state.index < s.length) {
        val c = s(state.index)

        val nextState = c match {
          case d: Char if d.isLetter =>
            val (nextIndex, lexemeName) = parseLexeme(state.index, c => c.isLetterOrDigit || c == '_')
            val lexeme = lexemeNames.getOrElse(lexemeName, Variable(lexemeName))
            State(nextIndex, lexeme :: state.acc)

          case d: Char if lexemeNames.contains(d.toString) =>
            val lexeme = lexemeNames(d.toString)
            State(index = state.index + 1, lexeme :: state.acc)

          case _ => state.copy(index = state.index + 1)
        }

        inner(nextState)
      } else state

      inner(State()).acc
    }

    val lexemes = toLexemes.reverse
    val lambda = toLambda(lexemes)
    val res = T(lambda).transform
    res
  }

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val t = sc.nextInt
    sc.nextLine

    (0 until t).foreach(_ => {
      val s = sc.nextLine
      println(solve(s))
    })
  }

  private def findCloseBracket(lexemes: List[Lexeme]): (List[Lexeme], List[Lexeme]) = {
    case class Acc(lexemes: List[Lexeme] = Nil, bracketCount: Int = 1)
    @scala.annotation.tailrec
    def inner(lexemes: List[Lexeme], acc: Acc = Acc()): (List[Lexeme], List[Lexeme]) = {
      lexemes match {
        case ([email protected]) :: lexemes =>
          if (acc.bracketCount == 1) (acc.lexemes.reverse, lexemes)
          else inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount - 1))
        case ([email protected]) :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount + 1))
        case lex :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount))
        case Nil => throw new Exception("Wrong exception")
      }
    }

    inner(lexemes)
  }
}

Note: This problem (Down With Abstractions) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published.