Final Tagless

A continuation for Object Algebra.     阅读全文
zjuwyd's avatar
zjuwyd 12月 16, 2018

PolarDB 数据库性能大赛总结

PolarDB 数据库性能大赛总结几个月前龙先生告诉我有这么个比赛,于是便和龙先生、虎先生一起参加了。结果不算差但还是挺遗憾的,距离前十只差 5 名,不过还是学到了很多东西,以后可能也会用上不少。 下面零零碎碎地讲一下从头开始的思路吧。     阅读全文
zjuwyd's avatar
zjuwyd 12月 10, 2018

使用 Object Algebra 改善解释器代码设计

使用 Object Algebra 改善解释器代码设计前言很久(很久)没写过文章了,这次就讲讲最近看到的 Object Algebra 相关的内容吧。 什么是 Object AlgebraObject Algebra 是一种类似于抽象工厂的设计模式。不同在于,抽象工厂提供的是具体的类型/接口而 Object Algebra 提供了泛型。通过 Object Algebra, 可以将 Expression Problem 中的定义和实现进行完全的解耦,而仅仅需要非常基础的语言 Feature。     阅读全文
zjuwyd's avatar
zjuwyd 10月 03, 2018

Windows 下的 LLVM 前端项目构建指北

Windows 下的 LLVM 前端项目构建指北前言我为什么要写这篇文章最近因为有编译原理大作业 + 很久以前就有的兴趣,选择了 LLVM IR 作为我们的编译器的中间表示。 当然,LLVM 这个项目的文档是非常良心的,名为万花镜的 Tutorial 也给了我很大的帮助,但是—— 在配环境的过程中踩过了无数个坑 这篇文章是我希望我当初在学习 LLVM 时能够看到的东西,也希望能对其他人(包括以后的我)有一定的帮助     阅读全文
zjuwyd's avatar
zjuwyd 5月 11, 2018

一个简单的 Scheme 到 C 的编译器

一个简单的 Scheme 到 C 的编译器这是一个用 JavaScript 实现的简单的编译器,能够将 scheme 的一个子集编译到可以阅读的 C 语言,其教学意义远大于实际意义。 为什么用 JavaScript懒 前面的废话从接触函数式语言(这里更准确的来说是指支持 first-class-function 的语言)开始,我就一直在思考这个问题:这些高级的抽象是如何转换到相对低级的抽象直至汇编的。在刚开始学习编程时使用的是 C 语言。C 语言的优点和缺点都在于它足够底层,C 语言和汇编的关系是明显的,是基本可以直接看出来的。但在后来接触的其它语言基本都支持更高等级的抽象,而这些抽象中最常见的一种就是 first class function。C++11 作为一个划时代的 C++ 版本,提供的诸多重要特性中的一条就是 lambda 表达式。C++ 和很多其它语言对于 lambda 的实现都是将其处理成一个匿名类,将捕获的变量作为匿名类的成员、表达式的 body 存放在匿名类的一个方法中。但我们这里不是要实现一个 C++ 到 C 的编译器,所以我们会采用其它的方法。这里我们假定读者对 scheme 的语法有一定的了解, 所以不会再对 Scheme 语言本身做太详细的介绍。     阅读全文
zjuwyd's avatar
zjuwyd 4月 03, 2018

Magic with continuation

    阅读全文
zjuwyd's avatar
zjuwyd 12月 09, 2017

在 Haskell 中的“定理证明”

在 Haskell 里的“定理证明”这篇文章讲了什么总结了 Codewars 上面的几道证明题的思想并加以延拓,如果能在看完这篇文章之前/之后解决练习中的题目可能理解会更深刻。 下面是正文 众所周知,Haskell 并没有真正意义上的 dependent type,但通过一些技巧 (利用GADT)可以“模拟”dependent type,并可以通过其证明一些定理。 利用 GADT 模拟 Dependent Type首先我们需要作为值的类型 12data Zdata S n     阅读全文
zjuwyd's avatar
zjuwyd 11月 30, 2017

究极数据结构 Finger Tree

“究极数据结构” Finger Tree前言写这篇文章的动机是什么众所周知,代数数据结构 (ADT) 的代表之一 list 的随机访问时间复杂度是 $O(n)$ ,非常的慢。可以说,除了访问/删除/插入头节点以外,几乎所有的操作都是 $O(n)$ 的。虽然说我们写 Haskell 不是在效率上面非常苛求,让它跑的跟c一样快,但每次取个 length 就要 $O(n)$ 的时间还是无法让人放心。于是我们想出了各种方法来优化它的访问时间,比如我们可以通过把 list 封装成函数来使连接的效率达到 $O(1)$ ,我们把它叫做 DList ; 或者通过 Zipper 来提高对内部元素的访问效率,我们把它叫做 list-zipper 。但在学习 Haskell 时,我们了解到它的 Seq 模组中提供了一个效率非常理想的数据结构,名字很奇特,叫做 “ Finger Tree ”,于是看了一点它的源码和最初的 paper 。网上关于 Finger Tree 的中文资料少得可怜(就像很多 Haskell 相关的东西一样),知乎上聚集了一些精通 plt 的人士经常回答这些方面的问题,这次也如往常一样给了我很大的帮助。所以我下面将会讲一点 Finger Tree 相关的知识。 这篇文章讲了什么我将会在这篇文章中提到 Finger Tree 的设计思想、Finger Tree 的实现细节、 Finger Tree 的应用等内容。 我需要看这篇文章吗你需要对数据结构有着简单的了解。如果你希望能看懂代码的话,那么需要对 Haskell 的语法和思想有着基本的了解。     阅读全文
zjuwyd's avatar
zjuwyd 10月 11, 2017

Parser Combinator

Parser Combinator前面的废话这篇文章讲了什么讲了一些基础的 Parser Combinator 的实现,和一个简单的例子。 谁需要看这篇文章对 Haskell 和 Parser 有简单但不是很深入的了解的人     阅读全文
zjuwyd's avatar
zjuwyd 9月 28, 2017

Too Simple Language Interpreter

Too Simple Language Interpreter跑起来大概长这样: 项目地址在 这里 。 UPDATE 1: 更改了循环流程控制,添加了 for 循环、 break 和 continue 。 UPDATE 2: 更改了 bnf 文法,使其支持一定的后缀表达式,例如下标访问、函数连续调用、成员访问等功能。 添加了指向函数自己的 this 指针。 添加了成员访问符 . ,可以通过其访问函数闭包内部的变量。 更改了 asn_expr 的文法,使之支持直接对闭包成员的修改和定义。 UPDATE 3: 修改了 bnf 文法,支持了数组。 数组字面量形式为 [1, 2, 3] ,可以通过下标访问 x = [1, 2, 3] , x[0] -> 1 数组支持 + 号来进行拼接。可以直接通过下标修改数组成员。 UPDATE 4: 添加了 else 语句 修改了函数调用的求值逻辑,使左值能够直接进行运算,并使成员函数得以正常工作,现在基本已经可以实现很多数据结构了。 添加了 repl 中的 load show quit 指令,分别用以运行一个文件、打印出一个作用域内所有的变量、退出。 UPDATE 5: 添加了注释,使用 $ 来标注注释的开头与结尾。 UPDATE 6: 添加了默认柯里化功能,(x, y) => x + y 和 (x) => (y) => x + y 在调用时等价 UPDATE 7: 更改了函数参数格式,单个参数可以省略括号 (x) => (y) => x + y + 1 现在可以写成 x => y => x + y + 1     阅读全文
zjuwyd's avatar
zjuwyd 9月 09, 2017