Hoes of Tech

Conceptualization of Technology

  • Description of LZ77

    Basic Definitions

    In this article, \(D\) is used to represent an i-elements data array. \(d_0, d_1, ... , d_i\) are the elements of \(D\). Any continuous subset of \(D\) is called slices, represented by \(S(i, j)\), where \(i\) and \(j\) is the start and end position. For two slices \(S_1\) and …

    Read more...

  • Dive into Rust(1) - Iterator

    大概三个月之前,这三个月,我一直在使用Rust。回想起来,在离开Object Pascal家族之后,过去五六年里也已经尝试了很多的新语言,不管是D,还是因为谷歌的名头而开始用的Go,又或者是Nim,Crystal或者Zimbu,都没能让我真正的满意,而OOC虽然在语法上让人十分舒服,但它使用了libGC,并且对多线程和Closure的支持并不到位。其实,在改进OOC的过程中,有人提出过给OOC加入RAII,并且尝试把一部分内容分配在了栈上,不过很可惜,OOC的编译器在设计当初并没有考虑这些事情,不到几个小时这种改进就遇到了问题。

    在刚刚接触Rust的时候曾经写过一篇关于Rust的文章,里面阐述了我对Rust的第一印象——省心。把代码写出来,编译器就会指出所有的错误,在这几十天里,我明显感觉到在调试程序时莫名其妙的错误少多了——我还清楚的记得之前在OOC里因为一个Generics的bug导致ArrayList<T>里的元素过早被回收,结果就是程序有时候正常,有时候乱码,有时候Segmentation Fault,而这种问题在Rust里几乎不会出现。

    当然,Rust这么做的代价就是语法上的繁杂。Rust的语法并不算复杂,大部分关键词的意义都很明确,也没有存在歧义的设计,然而说它繁杂却不为过,一个简单的例子就是在声明一个用到了Borrow的Struct时,编译器要求必须指明所有Borrow的Lifetime,因此定义和声明中就出现了大量的Lifetime标识符 …

    Read more...

  • A First Look at Rust

    过去的一年半多,我一直沉迷与OOC,原因倒是很简单,OOC是目前为止我所能见到的最容易理解和最容易书写的语言。并且另外一个极其重要的地方是,它可以编译成C代码。编译成C代码,也就意味着优化可以交给高度发展的C语言编译器来做,听起来似乎适合十分高效的方法。

    最近几年类似的语言越来越多,从很久很久之前就存在却一直没出名的Haxe,还有最近的Nim-lang,以及采用了类似ruby语法的Crystal,甚至包括编译成C++的felix。这些语言都号称自己考虑了速度(运行速度),至少从编译成C/C++的层面上。

    可惜的是,在改进OOC编译器rock的过程中,我遇到了越来越多的问题,这些问题让喜欢速度的人泄气。一个最明显的事情是,这些语言几乎都用了GC,不论是libGC还是自己写的,并且更重要的是,很多语言特性是基于GC设计的——比如闭包,比如iterator的unwrap,在有没GC的情况下,这些东西的设计要复杂的多。在OOC里,由于Generics不是Template,更多的东西开始依存GC,在用了它一年后,当我真正开始在工作里使用的时候,这些问题开始出现,我开始打算关闭GC,但很显然这是不可能的。编译器会把一切搞不清楚的事情踢给GC。

    在这个时候 …

    Read more...

  • Closures in OOC

    上一篇Complexity Behind Closure,这次来专注于Rock是如何在C里实现Closure的。

    Block as Blocks

    首先,需要指出的是,在C里面并不是完全没有办法使用Closure。Apple的GCC Fork里就给C添加了Block,用于实现Closure:

    (Steal from the Wiki)

    #include <stdio.h>
    #include <Block.h>
    typedef int (^IntBlock)();
    
    IntBlock MakeCounter(int start, int increment) {
        __block int i = start;
    
        return Block_copy( ^ {
            int ret = i;
            i += increment;
            return ret;
        });
    
    }
    
    int main(void) {
        IntBlock …
    Read more...

  • Complexity Behind Closure

    Introduction

    今天,我在ooc-kean上看到了一个注释:

    minimum: static func ~multiple(value: This, values: ...) -> This {
        // FIXME: This creates a closure that causes a leak every time this function is called.
        values each(|v|
            if ((v as This) < value)
                value = v
        )
        value
    }
    

    minimum是Float类型的一个扩展,这里用了闭包来实现对每个值的比较。如果这些发生在GC之下,那么一切都没有问题,因为任何内存(包括闭包的)都会被GC默默的回收。但OOC-Kean并没有打开GC,这里就出现了问题 …

    Read more...

  • Introduction to The OOC Programming Language

    我想试一门新语言……但:

    • 我希望这门语言能简洁易懂 —— 排除了Perl/Rust...
    • 我不想自己管理内存 —— 排除了C/C++/Object Pascal...
    • 最好它能跟C差不多快 —— 排除了Python/Ruby...
    • 并且最好能在任何地方编译&运行 —— 排除了D
    • 我不想带着一个数百兆的运行库 —— 排除了Java
    • 我不怕Bug —— 欢迎来到OOC的世界

    Why OOC?

    • Compile to C,所有的代码都会首先编译成C,然后由clang或者gcc编译成二进制代码 这意味着,只要你有一台能运行ooc编译器的电脑,那么你的代码就可以在几乎任何有C编译器的平台上运行。

    • Class,Function overloading,Extend,Operator Overloading.... OOC拥有绝大部分你所期待的高级语言的功能。 ooc借鉴了很多语言,尝试这把这些语言里优秀(并且有趣)的元素融合到一起。

    • Easy interface to c. OOC可以直接使用C的头文件,也可以在C里简单的使用ooc的函数。

    OOC的官方网站里有更多介绍和参考资料 …

    Read more...

  • OOC, Generics and Flawed Design

    昨天在github上讨论OOC的一些特性,随后这个语言的设计者写了这篇文章。 虽然大部分都在谈ooc的编译器设计,但更多的内容在于程序设计的思想,复杂度,维护上面。我希望这篇文章能对读者有哪怕一丁点的帮助。

    原文地址:http://fasterthanlime.com/blog/2015/ooc-generics-and-flawed-designs

    ooc可能是我(注:原作者)最得意的成果,但同时,对我来说它也是让我头疼不已的“刺头”。

    一个重要的原因就是它的设计(构架)并不让人满意,并且在当下,很多东西没法简单的解决。但不要误解: 在某种意义上,所有的设计都是“糟糕”的,不论是由一个人掌管,或者有社区驱动。没有任何一个设计能被称为完美。尽管我们并没有关于“完美”的定义和度量。

    现在回到ooc上来,一些话题反复的被提起,比如interface(接口)和cover(覆盖)。这个问题的原因一部分来自与人们会简单的认为这些概念应该跟其他语言里的一样,因为它们的名字完全相同。但事实并不是这样,纵使拥有相同的名字,它们的意义也不尽相同。如果这些概念跟其他语言里的概念完全一样,那么ooc会是一个简单的C …

    Read more...

  • Build Compiler with LALR(1) Parser Generator(III)

    在经过前两章的奋战之后, 我们对于Parser终于多少有了点理解——虽然还有一些遗留问题。至少现在已经可以把一门简单的语言编译成bytecode然后解析执行了。不过就像上一章里所说的,有些时候我们还希望能够把程序编译成可执行文件,在这一篇文章里我们就来做这件事情,不用担心,并不是所有的工作都是由compiler来做的。在这里,基于前一章编译出来的ByteCode,我们首先生成汇编代码,然后通过NASM编译成elf object,最后通过ld链接成可执行文件。

    首先来熟悉下最简单的汇编程序,比如一个Hello,World可以写成下面的样子:

    global _start
    section .text
    
    _print:
        push rdx
        push rax
        push rbx
        mov edx, 1
        mov eax, 4
        mov ebx, 1
        int 0x80
        pop rbx
        pop rax
        pop rdx
        ret
    
    _start:
        mov …
    Read more...

  • Build Compiler with LALR(1) Parser Generator(II)

    在上一篇文章里, 我们通过最简单的dunnart自带例子构建了一个计算器,并且对Parser Generator的结构做了说明,不过就像结尾时所说的一样,那个计算器只能进行简单的四则运算,无法保存输出,没有变量,并不怎么让人兴奋。因此,在这篇文章的前半段,我们会对之前的代码进行小小的修改,让它支持变量,然后会尝试让他支持循环——但这个事情并不是那么容易,因此在这次的后半段,会有另外一个小例子来了解下循环的构造。

    首先,从上次已经完成的计算器程序开始,我们希望添加变量之后能够实现下面的功能:

    a = 1
    b = 2
    a+b 
    (Output -> 3)
    

    简单来说就是任何第一次使用并且以字母或者下划线开头的字符串都是变量, 并且只能通过赋值的方式来定义。 现阶段为了例子简单,我们只考虑变量是浮点数的情况。在动手折腾lexer和parser之前,先来定义一个最简单的储存器,它的主要功能是指定一个String之后,能够储存或者读取相应的值。这并不是一个很难的事情,你可以用喜欢的任何Container来实现它,比如HashedList,LinkedList,甚至是RandomAccess的Stack。在这里我选用了最简单的Associative Array(内部实现也是HashedList):

    double[string] list;
    

    在有了这个储存设备之后,就可以真正的着手来添加功能了,首先我们需要定义Identifier的Token …

    Read more...

  • Build Compiler with LALR(1) Parser Generator(I)

    其实从几年前开始就一直想着自己写个编译器, 不管是用LLVM编译成native code还是基于自己写的VM。起因不仅仅是因为写个编译器很“酷”, 它还是很多东西的基础——比如游戏引擎,Machine Learning时的配置文件(因为很多Parameters是需要动态改变的)。之前已经试过数次,但都因为各种各样的原因放弃了。几年过去,现在又萌生了这个想法,反正都要从头来, 干脆把这些都记录下来,就算再扔掉也不会从零开始。

    之前曾经用过flex+yacc,也手写过LL(1)的Parser,但我并不喜欢C语言,也不打算折腾个底朝天,因为最近一直在用D语言,恰好DLang里有LALR(1)的Parser Generator - dunnart.于是以此为基础来试一试。

    如果你不了解D语言,也不需要担心,它的语法很像C/C++,比如一个最简单的Hello,World:

    import std.stdio;
    void main(string[] args){ 
        writeln("Hello, World!"); 
        return; 
    }
    

    如果后面遇到特殊的语法 …

    Read more...