fork download
copy 
  1. import scala.util.parsing.combinator.RegexParsers
  2.  
  3. abstract class Term
  4.  
  5. case class Var(name : String) extends Term {
  6.   override def toString = name
  7. }
  8.  
  9. case class Fun(varname : String, body : Term) extends Term {
  10.   override def toString = s"(\\$varname.$body)"
  11. }
  12.  
  13. case class App(left : Term, right : Term) extends Term {
  14.   override def toString = s"($left $right)"
  15. }
  16.  
  17. trait Semantic {
  18.   def reduce(term : Term): Option[Term]
  19. }
  20.  
  21. object NormalOrder extends Semantic {
  22.   override def reduce(term : Term): Option[Term] = term match {
  23.     case App(left, right) => reduce(left) match {
  24.       case Some(Fun(leftVarname, leftBody)) => reduce(apply(leftBody, leftVarname, right))
  25.       case _ => None
  26.     }
  27.     case _ => Some(term)
  28.   }
  29.  
  30.   def apply(body : Term, varname : String, term : Term) : Term = body match {
  31.     case Var(varname1) => if(varname1 == varname) term else Var(varname1)
  32.     case Fun(varname1, body1) => Fun(varname1, apply(body1, varname, term))
  33.     case App(left, right) => App(apply(left, varname, term), apply(right, varname, term))
  34.   }
  35. }
  36.  
  37. object LambdaParsers extends RegexParsers {
  38.   override def skipWhitespace = false
  39.  
  40.   def variable : Parser[Term] = "\\w+".r ^^ {
  41.     x => Var(x)
  42.   }
  43.  
  44.   def function : Parser[Term] = "\\(\\\\".r ~ variable ~ "\\.".r ~ term ~ "\\)".r ^^ {
  45.     case _ ~ Var(varname) ~ _ ~ body ~ _ => Fun(varname, body)
  46.   }
  47.  
  48.   def application : Parser[Term] = "\\(".r ~ term ~ "\\s".r ~ term ~ "\\)".r ^^ {
  49.     case _ ~ left ~ _ ~ right ~ _ => App(left, right)
  50.   }
  51.  
  52.   def term = function | application | variable
  53. }
  54.  
  55. object TopLevel {
  56.   def eval(expression : String) : String = {
  57.     val term = LambdaParsers.parse(LambdaParsers.term, expression).get
  58.     NormalOrder.reduce(term) match {
  59.       case Some(result) => result.toString
  60.       case None => "Something wrong!"
  61.     }
  62.   }
  63. }
  64.  
  65. object Main {
  66.   def main(args : Array[String]) = {
  67.     println(TopLevel.eval(raw"(((\x.(\y.(x y))) (\z.z)) a)"))
  68.   }
  69. }
  70.  
Success #stdin #stdout 0.37s 382080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a
https://ideone.com/C6pImg
language:
Scala (scala 2.12.8)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!