愿你走出半生,归来仍是Java Parser
几天前,我的一个朋友给了我一个Haskell问题 Hey,MK,假设我有个BNF,并且我在Haskell中有个这个BNF的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把这些功能补完。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |