binders.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 358 行 · 第 1/2 页

    def onLeft {}
  }

  
  trait BindingSensitive {
    // would like to specify this as one method:
    // def alpha_==[t <: NameElement](other: BoundElement[t]): Boolean
    // def alpha_==[bt <: binderType, st <: elementT](other: UnderBinder[bt, st]): Boolean 
  }

  /** A `BoundElement' is bound in a certain scope `scope', which keeps track of the actual element that 
   * `el' stands for.                                                               
   *
   * A `BoundElement' is represented textually by its bound element, followed by its scope's `id'.
   * For example: `x@1' represents the variable `x' that is bound in the scope with `id' `1'.
   *
   * @invar scope.binds(el)
   */
  case class BoundElement[boundElement <: NameElement](el: boundElement, scope: Scope[boundElement]) extends NameElement with Proxy with BindingSensitive { 
    /** Returns the element this `BoundElement' stands for. 
     * The `Proxy' trait ensures `equals', `hashCode' and `toString' are forwarded to 
     * the result of this method.
     */
    def self: Element = scope.getElementFor(el)
    
    def name = self.asInstanceOf[NameElement].name // TODO: this is only safe when substituted to a NameElement, which certainly isn't required -- I want dynamic inheritance! :)

    // decorate element's representation with the id of the scope it's bound in
    override def toString: String =  super.toString+"@"+scope.id
    
    def alpha_==[t <: NameElement](other: BoundElement[t]): Boolean = scope.indexFor(el) == other.scope.indexFor(other.el)
  }  
  
  /** A variable that escaped its scope (i.e., a free variable) -- we don't deal very well with these yet
   */
  class UnboundElement[N <: NameElement](private val el: N) extends NameElement {
    def name = el.name+"@??"
  }
  
  // this is useless, as Element is a supertype of BoundElement --> the coercion will never be inferred
  // if we knew a more specific type for the element that the bound element represents, this could make sense
  // implicit def BoundElementProxy[t <: NameElement](e: BoundElement[t]): Element = e.self
                                                                     
  /** Represents an element with variables that are bound in a certain scope. 
   */
  class UnderBinder[binderType  <: NameElement, elementT <% Mappable[elementT]](val scope: Scope[binderType], private[Binders] val element: elementT) extends Element with BindingSensitive {
    override def toString: String = "(" + scope.toString + ") in { "+element.toString+" }"
      
    /** Alpha-equivalence -- TODO
     * Returns true if the `element' of the `other' `UnderBinder' is equal to this `element' up to alpha-conversion.
     *
     * That is, regular equality is used for all elements but `BoundElement's: such an element is 
     * equal to a `BoundElement' in `other' if their binders are equal. Binders are equal if they
     * are at the same index in their respective scope. 
     *
     * Example: UnderBinder([x, y]!1, x@1) alpha_== UnderBinder([a, b]!2, a@2)
     *          ! (UnderBinder([x, y]!1, y@1) alpha_== UnderBinder([a, b]!2, a@2))
     */
    /*def alpha_==[bt <: binderType, st <: elementT](other: UnderBinder[bt, st]): Boolean = {
       var result = true
       
       // TODO: generic zip or gmap2
       element.gmap2(other.element, new Mapper2 {
         def apply[s  <% Mappable[s], t  <% Mappable[t]](x :{s, t}): {s, t} = x match {
           case {be1: BoundElement[_], be2: BoundElement[_]} => result == result && be1.alpha_==(be2) // monadic gmap (cheating using state directly)
           case {ub1: UnderBinder[_, _], ub2: UnderBinder[_, _]} => result == result && be1.alpha_==(be2)        
           case {a, b} => result == result && a.equals(b)
         }; x
       })
    }*/
    
    def cloneElementWithSubst(subst: scala.collection.immutable.Map[NameElement, NameElement]) = element.gmap(new Mapper { def apply[t <% Mappable[t]](x :t): t = x match{
      case substable: NameElement if subst.contains(substable) => subst.get(substable).asInstanceOf[t] // TODO: wrong... substitution is not (necessarily) the identity function	
         //Console.println("substed: "+substable+"-> "+subst.get(substable)+")");
      case x => x // Console.println("subst: "+x+"(keys: "+subst.keys+")");x
    }})
    
    // TODO
    def cloneElementNoBoundElements = element.gmap(new Mapper { def apply[t <% Mappable[t]](x :t): t = x match{ 
      case BoundElement(el, _) => new UnboundElement(el).asInstanceOf[t] // TODO: precision stuff
      case x => x
    }})

    def extract: elementT = cloneElementNoBoundElements
    def extract(subst: scala.collection.immutable.Map[NameElement, NameElement]): elementT = cloneElementWithSubst(subst)
    
    /** Get a string representation of element, normally we don't allow direct access to element, but just getting a string representation is ok*/
    def elementToString: String = element.toString
  }
  
  //SYB type class instances
  implicit def UnderBinderIsMappable[bt <: NameElement <% Mappable[bt], st <% Mappable[st]](ub: UnderBinder[bt, st]): Mappable[UnderBinder[bt, st]] = 
    new Mappable[UnderBinder[bt, st]] {
      def gmap(f: Mapper): UnderBinder[bt, st] = UnderBinder(f(ub.scope), f(ub.element))
    }  
  
  implicit def ScopeIsMappable[bt <: NameElement <% Mappable[bt]](scope: Scope[bt]): Mappable[Scope[bt]] = 
    new Mappable[Scope[bt]] {
      def gmap(f: Mapper): Scope[bt] = { val newScope = new Scope[bt]()
        for(val b <- scope) newScope.addBinder(f(b))
        newScope
      }
    }  
  
  implicit def NameElementIsMappable(self: NameElement): Mappable[NameElement] = new Mappable[NameElement] {
    def gmap(f: Mapper): NameElement = self match {
      case BoundElement(el, scope) => BoundElement(f(el), f(scope))
      case _ => UserNameElementIsMappable(self).gmap(f)
    }
  }
  
  def UserNameElementIsMappable[t <: NameElement](self: t): Mappable[t]  

  object UnderBinder {
    def apply[binderType <: NameElement, elementT <% Mappable[elementT]](scope: Scope[binderType], element: elementT) = new UnderBinder(scope, element) 
    def unit[bt <: NameElement, elementT <% Mappable[elementT]](x: elementT) = UnderBinder(new Scope[bt](), x)
  }
  
  /** If a list of `UnderBinder's all have the same scope, they can be turned in to an UnderBinder 
   * containing a list of the elements in the original `UnderBinder'.
   *
   * The name `sequence' comes from the fact that this method's type is equal to the type of monadic sequence.
   *
   * @pre !orig.isEmpty implies orig.forall(ub => ub.scope eq orig(0).scope)
   * 
   */
  def sequence[bt <: NameElement, st <% Mappable[st]](orig: List[UnderBinder[bt, st]]): UnderBinder[bt, List[st]] = 
    if(orig.isEmpty) UnderBinder.unit(Nil) 
    else UnderBinder(orig(0).scope, orig.map(_.element))

  // couldn't come up with a better name...
  def unsequence[bt <: NameElement, st <% Mappable[st]](orig: UnderBinder[bt, List[st]]): List[UnderBinder[bt, st]] = 
    orig.element.map(sc => UnderBinder(orig.scope, sc))

  /** An environment that maps a `NameElement' to the scope in which it is bound.
   * This can be used to model scoping during parsing.
   *
   * (This class is similar to Burak's ECOOP paper on pattern matching, except that we use `=='
   *  instead of `eq', thus types can't be unified in general)
   *
   * TODO: more documentation
   */
  abstract class BinderEnv {
    def apply[A <: NameElement](v: A): Option[Scope[A]]
    def extend[a <: NameElement](v : a, x : Scope[a]) = new BinderEnv { 
      def apply[b <: NameElement](w : b): Option[Scope[b]] =  
        if(w == v) Some(x.asInstanceOf[Scope[b]]) 
        else BinderEnv.this.apply(w) 
    }
  }

  object EmptyBinderEnv extends BinderEnv {
    def apply[A <: NameElement](v: A): Option[Scope[A]] = None
  }

  /** Returns a given result, but executes the supplied closure before returning.
   * (The effect of this closure does not influence the returned value.)
   *
   * TODO: move this to some utility object higher in the scala hierarchy?
   *
   * @param result the result to be returned
   * @param block  code to be executed, purely for its side-effects
   */
  trait ReturnAndDo[T]{
    def andDo(block: => Unit): T
  } // gotta love Smalltalk syntax :-)

  def return_[T](result: T): ReturnAndDo[T] =
    new ReturnAndDo[T] {
      val r = result
      def andDo(block: => Unit): T = {block; r}
    }

  private object _Binder {
    private var currentId = 0
    private[Binders] def genId = return_(currentId) andDo {currentId=currentId+1}
  }
}