#Haskell #FP #Algorithm #signal

https://lexi-lambda.github.io/blog/2020/01/19/no-dynamic-type-systems-are-not-inherently-more-open/ #programming_language #types #haskell

https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ #haskell #types #programming_language #software_design

#functional #Haskell Elm 🌝

记得之前写的文章里也有走迷宫，那个大概也不是最短路径，最短可能要每步选 minBy ，草
我都不能把 LIFO stack 和 recursion 对应起来，只知道用递归程序这样

传 history 大概是为了快一点，避免重分配 List 或者是为了能尾递归(误人子弟) 其实就相当于我的 char+String 实现方式
注意这个 #Haskell 版用的也没有 HashSet... 现在发现 let (x,y) = p in x >= (length m) or (y >= length m!!x) 大概是写反了吧 噢不这个矩阵就是 [y1, [x1,x2]] 的竖向...

#日常精神分裂 #Haskell #functional #relation 推荐不要看的胡言乱语。
A: 听见人说 Rank N Types 可以弄出 p(p==not) (: forall x. p(x)==not(x)) 的关系式
B: 不过这个你自己也不明白吧，说白就是 p(q) = not q 时 q ，正确答案 q 只有一个，但是 q=(forall x. px==notx) = True 时 p=False ， p!=not.not.not.not q ... 还有一大堆 not ，就是这里没法得到答案吧
A: 为什么有一大堆 not 呢
B: 为了保证 p=not 的定义， p(p==not) 应该里 p 的定义是不一致的，第一次是 not True 但导致 p=not.not=itself ，第二次又变成 not False 而 p=not，我们想做的是用比较形式化的方法从某一面「判断」这个东西是无解的，但它到底是等式，还是关系式，还是别的什么？
A: 那还是看看 rankn type 是什么吧。
B: 最简单的说法，对 id :: a -> a 里 a 有 Int, String 等可能，但是如果有 f :: a -> (a -> a) -> a ，f 里 a 就只能是任意一个类型，而在括号里加 forall a. 那 f g = 后面就能同时 (g 1) (g "") 了，但这只是 Rank 2 type 。 Rank 是「重评估」的意思， R0 t 是单态 R1 就是正常多态，如果要更多 Rank ， (forall c . (forall a b . a -> b) -> c) -> d 就是一个 Rank 3 。 我之前还说不可能 forall a. forall a. (a -> a) 呢（没意义 a 已经在类似上下文 绑定过了）
A: 话说 type 和程序体有什么关系啊。
B: 一个常见的误会是系统化的类型和程序是相互依存的，比如完整的程序带来了类型信息，其实除了 type inference ，程序的组织结构和类型标记是两个独立部分，类型只是限制程序 它自成体系，甚至可以说能检查程序只是它的副作用。
A: 说起来 haskell 的 a b c 到底是怎么检查的啊
B: 类型就是符号之间的关系，符号绑定了语法树的模式和其它关约束条件。 hs 里这很简单，只有一个性质—— consistence 一致性，比如有 (+) :: Int -> Int -> Int ，那 1+"1", 1+0.0 就是无效的， 1.0+1.0 也是无效的。作用域单一没有同名重载，只能约束 (t,t) -> t ，如果各处的 t 是一致的就没问题，否则就错了。 typeclass 也是类似 trait ，其实类似一个小插件，是 (Show t) 拿到实型去查对应 instance ，查到就能选择多态 找到的实现版本而已。
A: 真的不明白 RankN 和有什么关系呢，毕竟 rank 是 polymorphism ，作为 type constraint 为什么会陷入死循环呢🤔，要不谈谈 rev rev=id 吧
B: 那个就是把 0 和 iLast-0 对应吧…… 和 xs.rev()==xs.rev() 不一样，是要 xs.rev().rev()==xs ，怎么解构呢，我区分不出 foldl 和 foldr 啊，函数式分不出调用顺序 理论上不存在栈这东西呢， foldl f v xs = foldr (flip f) v (reverse xs) 啊
A: 问句题外话，为什么不能 add :: Int Int Int 啊，而且遇到 f not p 时中间也得加 $ 或 <$> 的
B: 一个是并列一个是 infix 了，编程语言可没你聪明不知道 not 不是一参数 要加括号
B: 你到底有没有见过正经的 Recursive Type 啊
A: 递归类型是什么，为什么要递归？层数有限制吗？是不是有限性？在无限序列上有限计算 算不算用了递归类型？ Py typehint 里 -> "self" 算不算？
B: 肯定不是啦…… self 是 py 作用域设计的问题，3.7 lazy 勉强解决了，和 recursive type 是无关的，这个大概和 Kotlin inference 一碰到就要 workaround 的递归返回值有关吧。
A: 当然基于 car cdr 的 apply transform 我都会，C++ template<T, ...Rest> 嘛
B: 那还真是好普通啊
B: 别灰心嘛，还是需要你们这种布道者的

A: 有时候感觉我们这些做同级翻译或者 LLVM 前端的人写的编译器本质是元编程的一种表现形式，有时候觉得完整的编译原理课又是照本宣科，除了后端都是重复，到底怎么样是好啊。
B: 我看到一个有意思的视频，一排柱子一根根升起，给你一个 i 你能不能做出动画来
A: 动画师估计挺麻烦吧。 普通人可能要求 timerup 后移 单个动画 ，但这个应该建模成 [0, 0], [1,0], [2,0], [2,1] 这样的「逐列递增表」，实际依然靠 i ，但是可以拿到过程中的所有状态。
B: 最方便的大概是直接一个乘除法吧…… 批量计算好
A: 感觉还是做到 assembler 前比较好
B: 你是说 SSA Value 和寄存器分配吧。 分配是独立的算法，但我可以告诉里不分配，完全溢出到栈上也是能实现的。只是要生命期内所有引用，局部 unified 就可以。 作为 stack ptr 参数还是 opcode reg input/out 的区别而已，如果用栈，也无所谓有几个 operand 或有几个AST前层，唯一又能统一的输入输出地址而已。

#Learn #OOP #js #design #Java #Kotlin
duangsuse:
大失败，不会写了；第一次还觉得需要 RingBuffer 或者双指针维护缓冲器那样……

其实根本没有那么麻烦， post 的时候带上 queue index ，全部完成右移视口 offset 就够了，如果没全完成右移也不行
简单设计复杂化

许久没有编程的动苏眼高手低到了这样的程度，不行，一定要写出来刚才那个的核心逻辑😡

……草，竟然真的可以用了，虽然没测试 原来 runtime.Port 真的像 channel 一样要 sender自己 onMessage 也能收到，所以要先 verify 吗

基础封装的逻辑就是封装 channel ， create server 可选， client 一定；兼容了 DOM postMessage API

假定 Function 的 que 无法共享，利用 seqNum (传输侧别名为 no) 指代响应目标，然后 que 本身利用 offsetL 压缩一下，不会一直增长
核心部分 20 行

仔细想想这个封装的确很有必要，总体 post/onMessage 请求一次 backend 是 callback(proc(msg)) ，C/S 两边都要 post,onMessage,msg,post 还难复用信道，call 了服务端处理完还要尝试按原名回调，容易重复标识符数据。

Jack Works:
来，把异常处理也加上

duangsuse:
Uncaught DOMException: The object could not be cloned.
不得不想序列化变形的办法…… 而且 JS 还是弱类型

好吧，好像需要一个完整的序列化方法，这个方法必须介入 sendMessage 数据来允许保留类型信息，如果不止要存留 Error message 的话 🌚

Jack Works:
到最后你会发现你重新发明了 JSON RPC

所以我把我的实现改造成了 JSON RPC 做成了通用的库

duangsuse:
serialize 本来就应该是框架层做的，而且它也只需要暴露 ser() deser() 两个函数而已
我们只不过应该在框架上写个十来行的小程序就够了

Jack Works:
我也是这么设计的啊， https://jack-works.github.io/async-call-rpc/async-call-rpc.asynccalloptions.html

duangsuse:
中国开发者越来越难了， github.io 都不能用了 #China #net #Freedom

以后写个软件第一关过政审第二关过苹果 Steam 的审，层层加码，服！

duangsuse:
累死了，反正能用就行
格局小了，我本来准备写 DOM 动画的，又鸽子了，再鸽就溢出了……

又到了各种 push 不上去的时间段，中国的网络环境。

Jack 那个我是真的摸不清，骨架太大了，重写人的脑力也是有限的(当然 typing 应该看得懂 就是各种 scope feature 看不懂)，知道 onConnect,disconnect 这些 API 也不好分析
不过好歹是能用一个，虽然肯定有性能开销了

Jack Works:
里面逻辑复杂但是外面接口简单啊

duangsuse:
动苏的标准是从内到外没有业务主干外的代码，如果有就作为插件嵌在骨干外…… 总之就是一句话，强调最根本最必须的算法 #statement

Jack Works:
你只要写一下怎么收发消息的逻辑，我这个框架就能 magically 跑起来

duangsuse:
所以说动苏的编程风格是函数式改 upvalue 而不是 class 属性，因为我强调算法先于架构

Jack Works:
动苏？啥玩意 = =

rxliuli:
你的中文昵称？

Jack 更喜欢在一个文件中编写多个 func，然后全部命名导出，吾辈更倾向于 class method 的形式

Jack Works:
我这个对 tree shake (webpack) 比较好🤔

duangsuse:
是的， duang 源于成龙洗发液的“头发动啊”，suse 是 Linux 发行，所以叫『动苏』😋 #life

动苏会觉得自称「我」或者「咱」(代替「我们」，我w键坏了) 有点生硬，这样就好很多

duangsuse:
这一点我还是倾向 Jack ，毕竟 Java 算是八股文式 OOP ，没有为实际编程有 toplevel func 样的优化

我可没说错话哦，面向对象的 class 本质是对函数式闭包加类型， property 即 upvalue ， method 即子程序化分段，整个对象即 send(name,args) 元方法，真正的面向对象只有「物/例」和其上的名词动词，没有文绉绉的废话甚至混乱 static。 #statement

面向对象把数据和其上操作混合定义是好事，可惜某些人就知道装B 起一大堆半通不通的专有名词，专业术语往往鬼用没得，给人们的思考造成一大堆麻烦。

要是 OOP 最初的作者能有半点实用化的觉悟，绝对不会放任 Jawa 混乱善良合理的编程习性

rxliuli:
但 Java 确实流行起来了而且基本被大规模实用了。。。虽然写起来确实感觉不太舒服，尤其是写过其他更好的语言之后

duangsuse:
所以说它才有机会被 Kotlin 吊打啊~
可惜 JavaEE 是他们自己搞出来自以为高明的八股文，很多 Kotliner 还没做好准备击败他们

CodeHz 📡:
(因为用类作为天然的命名空间分割函数的方法太好了（

duangsuse:
是的，构造器就像可覆写的一个局部变量初始化 header
然后整个类就像一个函数， constructor 提供了初始的变量混入

CodeHz 📡:
(oop 很好)就是无法自然的表达多重dispatch

duangsuse:
polymorphism 多态 不可以吗？

<就有个主次之分了，而且也不是运行时多态

运行时多态上 Sum type 可以 Visitor 啊，也挺方便的

<（有好几个参数需要动态分发的时候写起来还是挺别扭的

c 里搞 tagged union 到处 cast 就不方便吧…… 每个使用处都要检测 tag
请教下什么叫多派发啊

<大概就是这种（ https://en.wikipedia.org/wiki/Multiple_dispatch

C#是直接用动态运行时（DLR)了 #dotnet

类似 #Haskell 的 pat match 啊，那样 visitor 的确就不够了，得 trie 数据结构匹配...

非常疯狂，看起来 A.collideWith(B) 和反过来 B,A 是一样的

看起来是个非常有意思的特性，不过我感觉离算法/设计模式比 PLT 近些， visitor 单判定派发更实用一些

#fp #haskell 😒简单的问题答得太trivial/泛泛，复杂的问题无论tikv,jetbrains分部 都没几人知道，当然不知道发什么了，因为发了也没人懂

（另：hs是不在语言鄙视链顶端。有趣的是APL这种"优美"的单向数学语言都能排上号

没有简单哪来的复杂？ 我们总是喜欢掩盖或隐藏自己的过去、排斥嘲讽幼稚的东西，丢弃一些入门级太随性的理解，却没有意识到正是「基础」的层层累积到达现在的高度，它们只是融化扩张了，不是消失了。

没有人能懂的东西，就发挥这种内行专属的、孤独单一的价值吧，社会上哪哪不是如此，动画片就幼稚、宫斗剧就成熟，胜过一切的成熟是否包含幼稚呢？ 其实对不同的目的，小和大、简单和繁杂 都有用处，在它们之上，才有幼稚和成熟。

我们总是以为www就是一切、觉得这是最好最快的时代，其实有多少知识是网上搜不到的、多少技术工具明明可以更好服务于人，却各自主张，似乎是自给自足的孤岛。

我希望无论学到什么，心都是万年幼稚鬼，但口却越来越娴熟，就是这样。 😒#tech #statement

https://yfzhe.github.io/posts/2020/03/define-memo/ #fp #algorithm fib 序列

这货一般用递归或递推（伪递归）定义(f=fib)
f 0=0;f 1=1
f n=(f n-1)+(f n-2) --前两次之和

于是 f 2 = 1+0 ，f 3=f2+1 ，很明显这可以转为递推

f' 0 a _ = a --f0=0
f' n a b = f' (n-1) b (a+b)
f n=f' n 0 1

f2= f' 1 1 1

- f' 0 1 2 - 1

也即循环

f=n=>{let a=0,b=1,c=0;for(;n--;){c=a+b;a=b;b=c} return b}

如果不想浪费 f'0时的b=(a+b) ，也可以

f' 0 _b=b
f n=f' (n-1) 0 1 ; f0=0

当然即便不使用递推，memo 缓存参数也能很好优化雪崩式递归
#haskell 里也可以用 fib=0:1:zipWith(+) fib (drop 1 fib)
你可能觉得很怪，我 #Python 利用2项tee()缓冲区实现过这个 fib.py

fibs = iself(lambda fibs: chain([1,1], starmap(add, zip(fibs, drop(1,fibs)))))

函数式的动态规划 - 脚趾头的文章 - 知乎 讲了背包、子序列问题的DP
https://zhuanlan.zhihu.com/p/104238120

把我给整不会了。之前冰封每次念叨“你会 de Bur啥 Indices”，什么HOAS， 竟然是“善”用 #Haskell 实现 Lua(Upvalue,closure)早有，C语言(尽管无词法闭包) 早有了的函数参编号化/作用域闭包，而且装作不知道这回事一样？

是没有人教过他们怎么写 native 编译器吗，还 alpha conversation ，还 name shadowing 和 env-table capture ，a-自动重命名防冲突是不？先整体遍历 substitute 替换完再规约是不？文本repr 和变量实质的关系都没搞清楚，搁这学 ANTLR/PEG 呢！它们连JSON列表的',' 都没法忽略；
函数式连变量名String的语言分配都要搞“系统”！AST的阴影面，那我就用 First-order/首次 AST 和env表浅copy存储咋了，变量解析好好的为啥要动呢？Lua 的首次不仅把 free/bound 啥区分了，连寄存器都分配了，序列化也完成了；函数式是玩AST树玩疯了吧，个求值序 单步走之前最简单的值ref 还整幺蛾子，有种你和任何一门正经IR编程语言比，不要搞窝里斗

刚才我还夸函数式闭包CPS支持程续值的 interpreter approch 牛逼，现在就看到阴暗面了——env-copy，不思进取，等到想改进的时候，一大堆有的没的“专业术语”就出来了。 函数式根本不适合搞这个优化(每次写visit都得好长,还链表解构呢)，好不容易写出来。也难怪非得用术语显得牛逼，
然而并没有暖用，复杂性是多参列表处理带来的，JS完整实现要不了10行， Hs 的遍历法注定了它要给 extract instantiate 这样的树重构写些无用分支 make compiler happy——因为要纯要exhaustive穷举啊，于是你转换半天，最终还不如首次用嵌套表就分配好了函数的内外关系，而且你起一大堆“数学性”名字，也不能让代码跑得更快或更好读

或者是没写过 typeparam 或 unification 吗？类型参数的意义就是一致性、unification 的前置条件就是a=b=1的传递性，变量的语义是:第j参、上i层第j参、全局键名k ，统一个语义指代就得了，closure 就是把这些上层的Upvalue 复制保留下来，它是一个函数值的创建动作，因为函数内引用了外局部值也要存储空间

我就不服了，同样一个东西，就像lam叫抽象我们叫函数子程序，lam里叫应用，我们叫调用，lam叫bound/free我们叫局部和全局量，lam 里叫替换参数我们叫变量和存储空间，lam叫beta规约我们叫执行单步，eta规约我们叫内联，项我们叫返回值；Hs里查instance overload我们用subtype多态override；Hs 写伪递归 case/参数guard匹配我们用 forEach ；哪里有不一样，凭什么函数的就牛我们就土？他们就像拿刀背切菜， 如果不是为研究；如果自以聪明；就是蠢。 那人家刀锋你刀背，和人切得一样才你牛啊、比人切得效率才厉害啊，仅仅会几个等价 没意识到智商是搁在那的 人类极限是在那的 表达费力成品就辣鸡 只是分出了亏本精力用刀背就牛， 这叫做和plain编译器等效了？还有一大堆变形你没做呢，市面上没有多少AST形式的虚拟机！
我们把鬼都看不懂的lam 整理成了大家都实用于代码简洁复用的程序工具，而且本质就是lam，而 lam 呢？停留在纸面和扭曲符号莫名"严谨"记法里，写不出几个算法、适应不了大千世界；空洞夸张还自诩是原理，去你的原理，好像 eat(makeSoup(boiler,plate)) 任谁想不出一样，好像代码有定a=1 不letin就算副作用。整理几个重构就能叫优美，咋不说现在随便一个linter 都更能修改问题呢？

现代语言除了有替换和单步化简，还支持主语this、同名不同义、非侵入式拓展的特性，这些lam理论都描述不了，它的再生理论也说得迷迷糊糊，它有什么资格说自己是编程这个巨大集合的本源和“理论”？就因为最迷你？

而且Scheme 那套 eval(exp, env=copy) 根本就不能放编译器上用，编译时命名就消失了，变成调用栈上位置了，在解析后就已没有"a b c" 这种名字了，也就动态语言能玩 env 表浅复制当存储空间用，编译器的闭包创建哪可能把所有外层局部量，乃至全局量复制下来蛤？ 那也不比预先知道啥变量是 upvalue 更简单啊！
而且Lua 的func(){global=g+1} 编译结果，看有没有 getglobal 指令就知道是不是“闭合”函数了，比你信息量还大，你就只能知道有没有FV节点，它直接平展为列表了，这种引用统计性的分析不在话下
一大堆废话，变量就是和作用域名绑定的，从函数式和符号表看都是如此，还什么方案，这就是唯一途径；而且它也一点不 abstract ，相反更靠近汇编了；它当然很 inductive(归纳性) ，因为0年以前汇编和JVM就是 work as this way —哦，JVM是把Upvalue存在匿名子类上 也算内部field

这个 paper 就仿佛是在那个珠穆朗玛峰卖冰棒，还是在大兴安岭滑雪呢，怎么就这么飒呢，拿人东西改名还不礼貌用语，在代码里也不加致敬不给credit，直接把工业界通行的做法来了个狸猫换太子，我思量着Lua的作者93年 一个“民科”怎么可能知道函数式的这些呢，怎么就“英雄所见略同”呢 ，那JVM里 aload_0, getfield Main$0.lvar 又是干啥的呢 ，摇身一变蹭 lambda 热度，我球球您了 Lam 它是 1920s 年的老人了，别再混血了

S f g x = f x (g x); -- 值复制S(f,g(x)). a=1; f(a,a); = S(f,I,a) . jvm dup指令
K x y = x; -- 值选择. 见Church编码 (true a b)
I x = x; --S K K x = I x = x

那个红姐(thautwarm)脾气又不好，上次(木兰)听什么 Py3to2 Lambda lifting 我还挺感兴趣的，网上搜到1资料，最后看代码-不就是匿名外提为局部吗？ see(Lam)=lv.add(it.code); see(Def){...; for(lv.unnamed){stmt.unshift("k=v")} return it}
自己也说简单，那就在标题写明是兼容变换backport(lambda extract)啊，美其名曰lambda提升，我还以为是优化呢. JS也tm有var 提升呢，怎么还被人喷呢

真是受不了他们，Lam 演算由 单项Subst 函数Abst 调用Apply 甚至let这种语法糖构成，显然apply有些东西时(如 + 1 2)会直接得值,类似Java的native。函数可以引用任何绑定变量(词法域)
还把 Abstract 简写为 abs 、name 写成 n，这是数学？？绝对值和函数有毛线关系？你可以起短像f,fn,e，但语义不该含糊，更不能错位！
相比之下，王垠把 Currying 瞎起了个咖喱就好太多了，至少不是拽无意义洋文；反正对于不知道 Haskell B. Curry (一个组合数学家) 的人这个名字毫无语义

真不知道写过的人为什么会把这个当哲学，两个等价的东西，进入函数层深++ ，看见变量求个层差，就没什么好说了；亏纯函数戏多，所以我不太喜欢不实际的纯函数写法\

那段时间冰封知乎挂的都是这个 de Burj啥和HOAS+啥理论 ，我有关注他的博文，但都不是关于这些的入门级的东西；他的 slogan 还曾是“你懂(这个啥)Indices”吗？弄得我以为是高级类型系统的应用，没想到是这个代数杂交。那他是像让人知道所以问，还是不想让人知道 但害怕人不知道 所以问呢？

本文并不是讲解 Finally Tagless 的，只是讲解它和 Visitor 这种设计模式之间的对应关系的。 对于 Finally Tagless 本身的讲解和推导，可以看下面的文章。一个语文极好的人写的『一不小心发明 de Bruijn Indices, SKI 组合子和 Finally Tagless』一个语文极差的人写的『解决 HOAS 无法 look into 的问题，同时一不小心发明 SKI 组合子』

作者：老废物千里冰封

链接：https://zhuanlan.zhihu.com/p/53810286