https://github.com/duangsuse/Essay-Java8-CST-Based-Generators #GItHub

= 程序设计语言类型::常见名词 #PL #PLT

🤔 有的时候看见诸如王垠这样的人的博客都会感觉好大佬的样子呢。
什么 soundness、completeness、type checker、intersection type、product type... 满嘴是我们这些菜鸡听不懂的 dalao 词汇，一瞬瞎眼膜拜。

其实你只是不明觉厉，这些都是类似”加盐“一样半俗半释的词：比如 Product Type，它其实也没有什么特殊的，只不过说某种 type 是其他一些 type 的融合罢了，看完下面的文字你很快就会明白这些常用名词的含义

要说真正困难的东西，那当然是线性代数莫属喽，给你每个名词的解释你都不一定能弄懂。

为了帮助你们学习这些程序语言类型领域的名词，首先我们得对程序设计语言的抽象语义、解释器、类型检查等概念有个基础的认识。
本教程主要面向刚入门的萌新快速上手，不会提及某些搞基的函数式语言诸如 Scala / Haskell / Agda 的搞基类型特性，比如 Higher-ranked polymorphism, Existential types, Coinducative data types

下面是本期学习到的名词，看起来好高大上呢。

+ [for type checkers] Soundness and completeness
+ Duck/Statically typed, explicitly(implicitly) typed, weakly/strongly typed
+ Type inference / type inferer
+ Types and values
+ Type erasure [Parametric polymorphism]
+ Type constructor
+ Type conversion
+ (Homogenus) Product type
+ Sum type
+ Subtyping
+ Paramized types (Parametric polymorphism)
+ Zero size types (aka. Unit types)
+ Empty types / Bottom type
+ Traits
+ Dependent type

== 什么是类型

不得不引用某 Haskell Values/Types 理论的简易入门了。

类型是什么呢？如果讨论上下文是 C、Java、Kotlin、Dart 这类简单的语言，类型可以被视为集合，某一个位置所有可能出现的值(value)的集合（有时候也可以被说成阶，但其实还是集合方便理解）

Java 的 boolean 就是 true 或者 false

boolean 是类型，true 和 false 是值

比如，有一个函数 abstract void acceptBoolean(boolean b);

实际上是说它”接受所有“ boolean 集合里的值 — true、false

这样就给我们的操作（比如二元运算、值传递、赋值语句等）定义了一个限制 — boolean 类型的参数只能被传入 boolean 类型的东西（变量、常量...）、boolean 类型的本地变量只能被赋值为 boolean....

类型系统的本意关于模块化、安全和优化 — 安全和优化是共生的，因为 Java 是安全的语言，不能让程序因为索引越界这种弱智问题导致更坏的结果，所以 Java 要做很多检查，类型检查，无论编译时或是运行时都一样，而把运行时的开销提升到编译期显然可以使得开销更小，而利用类型系统共生的多态（polymorphism）特性，诸如子类型多态、函数重载、类型转换多态、参数化类型等，可以大大提升程序的抽象性，使得软件工程更方便易读易维护。

比如 Java 的 int 就是一些数字，从 -Integer.MAX_VALUE 数到 Integer.MAX_VALUE...
Java 的 String 虽然是一种 product type，但是也可以认为是一个集合： "a" / "ab" / "ac" / "duangsuse" ....

=== 类型架构器

类型构造器就是接受类型，返回类型的玩意

Kotlin 里的 ? 是一种类型构造器，比如：
Int? 里的 ? 接受一个 kotlin.Int 类型，返回一个 kotlin.Int? 类型（Int? 是 Int 的父类型，因为它可以是 null，或者说 Int? 是 Int 和 Nothing? 的 Union type，在类型层面上是的）

此外，Java 5 引入的 Generics 也是一种类型构造器

java.util.ArrayList<T> 接受一个 T 类型，返回一个 ArrayList<T> 类型
java.util.function.Consumer<T> 接受一个 T 类型，返回一个 Consumer<T> 类型

== first-class 是什么意思

在程序设计语言理论的上下文中，说某个概念是 ”first-class“ 的（有的人也是说”作为值“，其实也都差不多，毕竟值也基本都是 first-class）

+ 可以被作为『函数』（子程序）的参数或者返回值
+ 可以被存储到诸如本地变量这样的容器里

不然的话，就被称为非 first-class (non first class)

== 组合和类型

— Haskell
inc :: Int -> Int
inc n = n +1

这是利用 (+) 操作符和两个 Int 构建的一个计算，(+) 的类型是：

(+) :: Int -> Int -> Int

给它两个 Int，然后它会返回一个 Int — 简单的 Int 二元运算

== Type constructor

A type constructor is a feature of a typed formal language that builds new types from old ones. Basic types are considered to be built using nullary type constructors. Some type constructors take another type as an argument, e.g., the constructors for product types, function types, power types and list types. New types can be defined by recursively composing type constructors.

For example, simply typed lambda calculus can be seen as a language with a single type constructor—the function type constructor (→). Product types can generally be considered "built-in" in typed lambda calculi via currying.

搞🐔一点的东西，毕竟我也不是只 🐔（是的，🐔 是一种 🥬🐔 但是 🥬🐔 不是一种 🐔[1]），没有办法理解也自然不可能误人子弟了，我只是来做乡村怨̶妇̶基础科普... 咳咳
基本都是用 Haskell、Scala、Agda、ML 这类要命 🐸的语言写一点可能并不简单的程序时候需要了解的，不过说起来类型上面讨论的毕竟还是一个高层抽象...

只能给个链接。

+ Kinds

A kind is the type of a type constructor or, less commonly, the type of a higher-order type operator.
A kind system is essentially a simply typed lambda calculus "one level up", endowed with a primitive type, denoted ∗ and called "type", which is the kind of any data type which does not need any type parameters.

===
Abstractly, a type constructor is an n-ary type operator taking as argument zero or more types, and returning another type.
Making use of currying, n-ary type operators can be (re)written as a sequence of applications of unary type operators.
Therefore, we can view the type operators as a simply typed lambda calculus, which has only one basic type, usually denoted ∗, and pronounced "type", which is the type of all types in the underlying language, which are now called proper types in order to distinguish them from the types of the type operators in their own calculus, which are called kinds.

e.g.

Maybe :: * -> *
String :: *
Maybe String :: *
(->) :: TYPE q -> TYPE r -> *

constructed types

show :: Show a => a -> String
(/) :: Fractional a => a -> a -> a

+ Union type

Union types are types describing values that belong to either of two types. For example, in C, the signed char has a -128 to 127 range, and the unsigned char has a 0 to 255 range, so the union of these two types would have an overall "virtual" range of -128 to 255 "(-128, 128] ∪ (0, 256]" that may be used partially depending on which union member is accessed.

operations on a union type are operations that are valid on both types being unioned.

|for example, both String and Int have an toString(): String operator, so type (String ∪ Int) can have toString(): String operator valid too
|but String have an subsequence(Int, Int): CharSequence operator, which is missing from Int, implies type type (String ∪ Int) cannot have the same subsequence operator from String

|As an widely-used example in Kotlin, Any? is union type of Any! and Nothing? (Any ∪ Nothing?)

In a subclassing hierarchy, the union of a type and an ancestor type (such as its parent) is the ancestor type.

|sealed class Ast<out T> { // parent Ast

, ancestor type for Add and Lit


|  abstract fun eval(): T
|  data class Add<T : Number>(val left: Ast<T>, val right: Ast<T>): Ast<T>() { override fun eval() = (left.eval().toInt() + right.eval().toInt()) as T }
|  data class Lit(val x: Int): Ast<Int>() { override fun eval() = x }
|}

>>> Ast.Add(Ast.Lit(2), Ast.Lit(3))

Add(left=Lit(x=2), right=Lit(x=3))

>>> typealias A = Ast.Add<Int>
>>> typealias L = Ast.Lit
>>> A(L(2), L(3))
Add(left=Lit(x=2), right=Lit(x=3))
>>> A(L(2), L(3)).eval()

//=> 5

The union of sibling types is a subtype of their common ancestor (that is, all operations permitted on their common ancestor are permitted on the union type, but they may also have other valid operations in common).

|for the example above, union of sibling types (Add<T> and Lit)'s common ancestor is Ast<out T>, making Add#eval and Lit#eval avaliable.

+ Intersection type

Intersection types are types describing values that belong to both of two other given types with overlapping value sets.

For example, in most implementations of C the signed char has range -128 to 127 and the unsigned char has range 0 to 255, so the intersection type of these two types would have range 0 to 127. Such an intersection type could be safely passed into functions expecting either signed or unsigned chars, because it is compatible with both types.

Intersection types are useful for describing overloaded function's types: for example, if "int → int" is the type of functions taking an integer argument and returning an integer, and "float → float" is the type of functions taking a float argument and returning a float, then the intersection of these two types (int->int ∩ float->float) can be used to describe functions that do one or the other, based on what type of input they are given. Such a function could be passed into another function expecting an "int → int" function safely (is a parent type of both i->i; f->f); it simply would not use the "float → float" functionality.

In a subclassing hierarchy, the intersection of a type and an ancestor type (such as its parent) is the most derived type. The intersection of sibling types is empty.

e.g. (String ∩ CharSequence) is String (note that String is a subtype of CharSequence)
for the Ast<out T> example above, (Ast.Add ∩ Ast.Lit) is Ast<T> (Ast.Lit, Ast.Add is a subtype of Ast, intersection of a type and an ancestor type (Ast) is the most derived type)

+ GADT (Generalized algebraic data type)

[1]: 此梗不是梗，参考 subtyping，子类型

#linux #sysadmin #fedora 原来我现在用的发行版本已经 EOL 了... 🤪

DuangSUSE@duangsuse.moe

 OS: 

Fedora

 
 Kernel: 

x86_64 Linux 5.0.4-200.fc29.x86_64

 Uptime: 

23m

 Packages: 

4863

 Shell: 

zsh 5.6.2

 Resolution: 

1920x1080

 DE: 

KDE 5.55.0 / Plasma 5.14.5

 WM: 

KWin

 WM Theme: 

Breeze Dark

 GTK Theme: 

Windows8 [GTK2/3]

 Icon Theme: 

Adwaita

 Font: 

Abyssinica SIL Regular

 CPU: 

Intel Core i5-7500 @ 4x 3.8GHz [27.8°C]

 GPU: 

nouveaufb

 RAM: 

1799MiB / 3894MiB

手工工加粗粗... 🤪 忍不住想到锤子 🔨 的声控”工作站“

[DuangSUSE@duangsuse]~%

sudo btrfs subvolume list /

ID 257 gen 378914 top level 5 path RootFileSystem
ID 258 gen 378914 top level 5 path Home
ID 398 gen 378825 top level 257 path var/lib/portables
ID 402 gen 378825 top level 257 path var/lib/machines

[DuangSUSE@duangsuse]~%

sudo btrfs filesystem df -h /

Data, single: total=100.01GiB, used=98.40GiB
System, single: total=4.00MiB, used=16.00KiB
Metadata, single: total=3.01GiB, used=2.00GiB
GlobalReserve, single: total=210.84MiB, used=0.00B

说到电子语音，国内某些辣鸡程序员的语音合成实现基本就是个自动控制的播放器，基本不涉及语音学和信号处理内容，质量非常辣鸡... 稍微好点的也不会用机器学习算法尝试让声音『自然』一点，还是简单调音高时长 shift

#GitHub https://github.com/duangsuse/Essay-Qt-CMake_QtQuick/tree/master

新的 #Essay

https://github.com/duangsuse/MonkeyVM

炒冷饭，可能是目前为止我很少的 Rust 程序了，虽然还是两年前的...

说实在话，我觉得它不怎么样，因为那时候我真的什么都不懂，当时我也想根据一位大佬（coding 上某位写过目标为猴语言编译器的大佬，不过他没写 parser，而是直接用了 ECMAScript 语法解析库）的建议，把这玩意弄成 native 编译器（可是那时候我连内存是什么都不知道，甚至 malloc 是啥也不知道... 更别提 alloca、memmove 什么的了）

很可惜我当时是看不懂 x86 汇编的，更不理解 GNU AS 汇编器的功能，尝试自然是失败了

可见会 Rust 也未必是大佬啊！

所谓的越复杂越容易堆砌，大概就是这样，这个程序当时我堆砌了大概一个星期，9k 行代码，最后连二进制序列化的操作都有了...
可惜它到底有多么复杂的算法？我不清楚，但当时我的确是很菜。

#GitHub 炒冷饭，因为 duangsuse 私人帐号下全是黑历史和完全没有用的 repo，以后 duangsuse 会把有用的代码放

https://github.com/duangsuse-valid-projects

这里，自己帐号下之前的代码会 transfer、不属于自己而属于其他 org 的代码会直接 fork 一份。

https://github.com/duangsuse-valid-projects

导入了 62 个 repo，但是还是感觉自己没底气，大概是因为 OO 抽象写得不如别人多、Android 平台不如别人熟悉
改日我有时间了多写点 Android 应用和封装 SDK 什么的的话会好一些

本频道里的东西，比如 AlpineDepolyer Python 脚本和 RustPlayBot/PythonPlayBot 就暂时放着了（不过我给加了个频道链接，反正那些也不是什么不得了的东西）

不得不说，后来再看我的确很菜，我之前没有一个面向对象的（比如，Java 类）抽象是被正确构造的... 而放在别人那里就多很多，还用 Java 软件架构常用的结构，比如 Annotation

至少看到了所谓的应用程序设计吧，真的用了不少别人的抽象呢，所以说底气不足，大概是实践不够

就好象看到会玩魔方的别人而自卑一样，但自己不经过长时间的训练，又如何能与别人相比呢？这样的话要么然花时间学魔方矩阵操作模型和模式识别，多训练、重操作速度，不这样怎么知道自己有没有能力做到？或许还能做到更好呢？

当然现在都过去了，我现在有能力，而且只要有时间，我一定能做到比以前本质上的进步，甚至超越别人（至少在某些方面是肯定可以的，因为这些是所谓更高层次的知识，和可以通过看代码抄代码改代码得到的技能有本质性的区别，就是所谓的『理解理论和进行分析程度的能力』）

我不是只会 quick hack，而是因为没时间所以真的只能去 Quick hack

越复杂越容易堆砌，我以前有时间的时候不是没有堆砌过这种功能多一点的东西，MonkeyVM 就是一个例子，这个虚拟机连”二进制代码文件格式“都写出来了，可是这能证明我理解它了吗？它只是个复杂的玩具，看起来像是有点用处而已，实际上内部依然只是空虚没有什么意思的逻辑，这种逻辑即便多一点又能怎么样？也不能证明我比别人多了些什么特别的东西。

所以我开始写所谓简单但难于设计的程序，开始看各种工程或者理论性的书籍，开始信奉简洁优雅定义自己的逻辑，即便自己依然 可能不是真正理解也要这么做。

所以我现在听到他们说『duangsuse 什么都会』『duangsuse 大佬』（这是貌似的意思，我只是大概描述一下....）
的时候甚至会怀疑，是不是在讽刺我...

希望有一天会彻底消失，不过我知道会很慢，因为那一天我必须写过所有他们写过开源的程序才行，因为打算涉足所有（软件）领域，所以要把所有领域的人都视为竞争者呢。

我知道我有时间赶，从基本的软件架构、GUI 程序、编译原理、关系代数开始，到计算机图形学、信号处理、人工智能、电子和无线电、操作系统，是以后每天要准备开始写代码的日常呢。

那么大概就是这样吧 #GitHub 现在有 64 个，但我马上还是要写新的东西的

https://github.com/github/semantic #GitHub #PL #recommended

无聊的 C 实践中.... 话说，UNIX 系统编程不容易，说起来要顾虑的就有好多、通信、线程、同步、套接字、信号和定时器、文件系统...

糊涂啊，fread(buf, sizeof(...), count, fp) 的时候，我居然把 byte size 弄成 unsigned int 了，heap 直接爆炸，我还以为是自己分配错了...

Radare2 是最好的二进制编辑器 #bin

https://www.fileformat.info/format/bmp/egff.htm

BMP Version 4

第一个版本很好读取，只需要 unpack 就可以了（看这里）

>>> struct.unpack('<ccIIIIIIHH',bmp)
('B', 'M', 691256, 0, 54, 40, 640, 360, 1, 24)

从结果 54 （矩阵偏移量）开始：
一个 4 字节整数：Header 的字节数
一个 4 字节整数：图像宽度
一个 4 字节整数：图像高度
一个 2 字节整数：始终为 1
一个 2 字节整数：颜色数