愿你走出半生，归来仍是Java Parser

Java 2019-03-16

几天前，我的一个朋友给了我一个Haskell问题

Hey,MK，假设我有个BNF，并且我在Haskell中有个这个BNF的parser。
现在，我想给这个BNF改一行，有没有办法不用动这个BNF parser的代码（因为是其他人写的），而是对这parser进行扩展呢？

这问题挺有趣的，也不算难。

这问题说是extensibility problem，其实有两个地方需要扩展。

0：Parser需要用open recursion之类的方法扩展

1：Parse出来的ADT也需要可扩展性

后半个需求见多了，Final Tagless，DTALC，Tree that grow，Recursion scheme style fix。。。于是放下不表，我们来处理前一个。

前半个。。Haskell's Overlooked Object System就搞过，当然他们有点heavy weight，打算随手弄一个超级轻量级的：5行就够了，多一行是小莎莎。

Ready？

data Object x = MkObject (x -> x)

1。Inheritance is not subtyping式的Object=recursive type。为了简易性（反正也不需要多高的扩展性）就不model真。recursive type，而只有recursive dependency。

use :: Object x -> use (MkObject x) = let res = x res in res

2。3。最典型的tying the knot。其实就是fix了。

我们想想，这个x是什么variant的呢？covariant还是contravariant？

 inherit :: (a -> b) -> (b -> a) -> Object a -> inherit ab ba (MkObject aa) = MkObject (ab . aa . ba)

既然是invariant，那fmap contramap都用不上，但invariant依然能有map：两边一起传进来就行了。4。5。

这就是一个prototype based oo system了。

接下来讲怎么用哈：

test = MkObject $ \self -> (2,fst self + fst self)

这弄了个两个field的object，第零个field初始值为2（可能因为继承被override），第一个field为第零个field的值*2（不一定是3，如果任何field被override这个值都能改）。use test应该是(2,4)。

inheritTest = inherit (\(l,r) -> ((l + 1,r + 2),r + 1)) fst test

这里继承了上面的Object，override了l(l + 1是super + 1），r被override到super + 2，加了个新的field，值是r+1。use inheritTest应该是((3,8),7)。记着传进来的参数不是self而是super就很好理解了。

好，open recursion搞好了，剩下的就是标准的final tagless了，体力活，没啥意思

    lit :: Int ->   plus :: repr -> repr -> 
    var :: String -> 
 type WholeParser repr = type LitParser repr = type PlusParser repr = 
  intP = read <$> 
  stringP = 
 type OriginalParser repr = originalParser :: AST repr => originalParser = MkObject $ \(~(_,p)) ->   litP = lit <$>   plusP = between ( '(') ( ')') ( {l <- p; spaces;  '+'; spaces; r <- p;    wholeP = litP <|>  
 type VarParser repr = extendedParser :: (AST repr,Var repr) => extendedParser =      extend ~((litP,wholeP) =       varP = var <$>       (varP,((litP,varP <|> 
    lit =   plus x y = "(" ++ x ++ " " ++ "+" ++ " " ++ y ++ ")"
 
    var x = x

大功告成。

代码在

Q：封装呢？

A：Abstract Type is Existential Type

Q：这是prototype based的，class怎么办？

A：A Theory Of Object里面讲过怎么用prototype来做class

Q：多继承呢？

A：给定Object a，Object b，可以组合出Object (a,b)，要菱形继承自己手动再inherit一下就好

Q：Subtyping?

A：Typeclass。

如果大家感兴趣，请评论下，我可以再写个blog把这些功能补完。

归来仍是Java Parser 愿你走出半生

ArrayList源码分析

ArrayList简介：ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增...

java多线程与并发（基础篇）

一、进程与线程进程：是代码在数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位。线程...

LinkedList 的实现原理

本文为博客园作者所写： 一寸HUI，个人博客地址：https://www.cnblogs.com/zsql/ 简单的一个类...

java之面向对象详解

#############java面向对象详解#############1、面向对象基本概念2、类与对象3、类和对象的定义格式4、...

java之异常详解

一、什么是异常? 异常就是有异于常态，和正常情况不一样，有错误出错。在java中，阻止当前方法或作用域...

Java集合框架

Collection接口 Collection接口 Collection接口 Collection是最基本的集合接口，一个Collection代表一组...

愿你走出半生，归来仍是Java Parser

相关文章