(define fibonacci
  (lambda (nth)
  ; 不会写了...
  ))

#cs #pl #scheme Y 组合子版本的 Fibonacci（其实只是我懒得输入 (fibonacci n 1 2) 然后从 《The Little Schemer》儿童书上抄写的模式 XD
至于为什么用 Y Combinator 实现递归是因为我不想多定义一个符号了（

(define fibonacci                           
  (lambda (n a b)                          
    (cond                                 
      ((= 0 n) a + b)
      (else (fibonacci (- n 1) b (+ a b))))))

(define fibo (lambda (n) (fibonacci n 1 2)))

或者，也可以使用匿名函数版本 这个我没有抄模式...

(define fibonacci
  ((lambda (fibonacci-def)
    (lambda (n)
      (cond
        ((= n 0) 0)
        (else (fibonacci-def fibonacci-def (- n 1) 0 1))))) ; 我把这里能访问到的 fibonacci-def 传给了真正的子程序
  (lambda (l nth a b) ; 第一项是这个 lambda 自身
    (cond
      ((= nth 0) (+ a b))
      (else (l l (- nth 1) b (+ a b)))))))

; 这是真的演算 lambda
(lambda (nth a b)
  (cond
    ((= nth 0) (+ a b))
    (else (fibonacci-def (- n 1)))))

#learn #functional #scheme #cs #pl

https://www.cnblogs.com/JacZhu/p/9729587.html 阅读者 duangsuse 做的总结 以下

-Infinity: 以下可能不是标准的 C# 代码，如果不容易理解全换乘伪代码
0. 笔者一直以为 LINQ 是专门用来对不同数据源进行查询的工具
1. C# 3.0 的 LINQ 可以做 Parser Combinator
2. 我也好需要 Parser Combinator 编写技能啊

3. 任何实现了 Select，SelectMany 等方法的类型，都是支持类似于 from x in y select x.z 这样的 LINQ 语法的
4. 如果我们为 Task 类型实现了上面提到的两个方法，那么我们就可以不借助 async/await 来对 Task 进行操作

taskA = Task.FromResult(12)
taskB = Task.FromResult(12)

resultA = await taskA
resultB = await taskB

result = resultA + resultB // 12 + 12

resultLINQ = 
  from a in taskA // a = await taskA
  from b in taskB // b = await taskB
  select a + b // 简不简洁？

5. 我们来为 Task 类型添加 LINQ 语法

首先我们要定义一个 Select 拓展方法，用来实现通过一个 Func<TValue, TResult> 将 Task<TValue> 转换成 Task<TResult> 的功能。

static async Task<TR>
  Select<TV,TR>
    (this Task<TV> task, Func<TV, TR> selector)
{
    var value = await task;    // 取出 task 中的值
    return selector(value);    // 使用 selector 对取出的值进行变换
}

static async Task<TaskResultType>
  Select<TaskSelf, TaskResultType>
    (Task<TaskSelf> self, Function<TaskSelf, TaskResultType> selector)
      { return selector(await self) }

taskA = Task.FromResult(12)
result = from a in taskA select a * a;
// taskA.Select(a => (a * a))
// `a => a * a' 就是 Select 中 selector /* (a => a * a) */ (await self) 被调用的那个 selector

6. 然后是 SelectMany 函数

class Task
  async SelectMany<ThisType, SelectorType, ResultType>
     (self, selector: Function<ThisType, Task<SelectorType>>,
       projector: Function<ThisType, SelectorType, ResultType>): Task<ResultType>

{
  var value = await self;
  return projector(value, await selector(value));
}

7. 这个 SelectMany 实现的功能就是，通过一个 Func<TValue, Task<TResult>> 将 Task<TValue> 转换成 Task<TResult>
8. 如果看不懂上面的解释的话，不要灰心，因为我也看不懂

9. taskA.SelectMany(a => taskB, (a, b) => (a * b))
10. from a in taskA from b in taskB select a * b
11. 后面还有一点我也看不懂，只看懂了一句话，就是 "SelectMany 可以被看作为把两层 Task 转换成单层 Task"

12. 可以看到，当出现了两个 Task 之后，LINQ 就会使用 SelectMany 来代替 Select
13. 想为什么 LINQ 不像之前那样，用两个 Select 分别处理两个 Task 呢
14. 因为我们所写的第二个 Select 其实就是 SelectMany，结果比 LINQ 还多调用了两次 Select

15. 后面的看不懂

细心的你可能已经发现了，不管是 LINQ to Task 还是 LINQ to Result，我们都使用了某种特殊的类型（如：Task，Result）对值进行了包装，然后编写了特定的拓展方法 —— SelectMany，为这种类型定义了一个重要的基本操作。在函数式编程的里面，我们把这种特殊的类型统称为“Monad”，所谓“Monad”，不过是自函子范畴上的半幺群而已

#scheme #recommended #translate

#tool #recommended #scheme
https://www.biwascheme.org/test/tracer.html

#PL #code #guide #daily #scheme

关于 Lice lice-lang/lice 解释器的分析

我们只看解释器实现，不看测试和文档什么的，目标为理解官方 Lice 解释器实现和汲取精华、以及提出充分利用 Kotlin 特性的建议

org/lice/api/scripting/*

javax.script 的 API 接口

我们可以看到，LiceScriptEngineFactory 类提供以下信息

LanguageVersion EngineVersion Extensions MimeTypes LanguageName Names EngineName

ScriptEngine()
OutputStatement(toDisplayString)
Program(statementsCode)

MethodCallSyntax(obj: String, mid: String, vararg args: String)

Parameter(paramString)
"javax.script.engine_version", "javax.script.language_version"
"javax.script.engine", "javax.script.language", "javax.script.name"

而 LiceScriptEngine 做这些

class LiceScriptEngine : JavaxScriptEngine
  private var context: LiceContext = LiceContext()
  getContext()
  setContext(context)
    setContextIfIsLiceContext()

  getFactory()

  eval(scriptString, context) = eval(script, context.bindings)
  eval(script: String) = eval(script, context.bindings)

  eval(reader: Reader) = eval(reader.readText(), context.bindings)
  eval(reader: Reader, n: Bindings) = eval(reader.readText(), n)
  eval(reader: Reader, context: ScriptContext)

  eval(script: String, n: Bindings)

  get(key: String?): Any? = context.bindings[key]
  put(key: String, value: Any?)

  createBindings() = SymbolList()
  getBindings(scope: Int) = context.bindings
  setBindings(bindings: Bindings?, scope: Int)

并且 LiceContext 做这些

bindings: SymbolList
reader: Reader
writer: Writer
errorWriter: Writer

getAttribute(name: String)
getAttribute(name: String, scope: Int)
setAttribute(name: String, value: Any?)
setAttribute(name: String, value: Any?, scope: Int)
removeAttribute(name: String) = bindings.removeVariable(name)
removeAttribute(name: String, scope: Int)

getScopes(): MutableList<Int>
getAttributesScope(name: String?): Int

getBindings(scope: Int)
setBindings(bindings: Bindings, scope: Int)

然后是 org/lice/core/*

AbstractBindings

variables: MutableMap<String, Any?>
provideFunctionWithMeta(name: String, node: ProvidedFuncWithMeta)
provideFunction
defineFunction
getVariable
defineVariable
isVariableDefined
removeVariable

containsValue
clear
putAll(from: Map<out String, Any>)
containsKey
get
put
isEmpty
remove
var size = fun ...
entries: MutableSet<LiceEntry>
keys
values

#guide #project #scheme https://t.me/dsuses/2493 "Lime 升级的 HeapParser 解释"

#math #cs #pl #scheme #lisp #haskell 计算模型们

如果觉得这个例子不好的话，刚才看这篇博文（教你们拿 Racket，一个 Scheme 实现写基于 Lambda Calculus 的解释器的）的时候突然发现这个例子非常不错（实际上，很多 #Haskell 入门教程都会拿这个做例子）

(define tree-sum
  (lambda (exp)
    (match exp                         ; 对输入exp进行模式匹配
      [(? number? x) x]                ; exp是一个数x吗？如果是，那么返回这个数x
      [`(,e1 ,e2)                      ; exp是一个含有两棵子树的中间节点吗？
       (let ([v1 (tree-sum e1)]        ; 递归调用tree-sum自己，对左子树e1求值
             [v2 (tree-sum e2)])       ; 递归调用tree-sum自己，对右子树e2求值
         (+ v1 v2))])))                ; 返回左右子树结果v1和v2的和

(tree-sum '(1 2))
;; => 3
(tree-sum '(1 (2 3)))
;; => 6
(tree-sum '((1 2) 3))
;; => 6

如果用 Haskell 写几乎一样的程序呢？

首先我们的 Haskell 的确是静态强类型（statically strong typed, type inference supported）的语言，所以类似 Scheme 那样直接拿链表抽象一切就免了（

data BinaryTree a = Leaf a | PrimNode a a | CompNode (BinaryTree a) (BinaryTree a)
t1 = PrimNode 1 2
t2 = CompNode (Leaf 1) (PrimNode 2 3)
t3 = CompNode (PrimNode 1 2) (Leaf 3)
t4 = CompNode (PrimNode 1 2) (PrimNode 3 4)

treeSum :: BinaryTree Int -> Int
treeSum (Leaf n) = n
treeSum (PrimNode a b) = a + b
treeSum (CompNode l r) = treeSum l + treeSum r

main 
  = (foldl f v) $ (println . treeSum) <$> [t1, t2, t3, t4]
    where      
      println x = print x               
      f = (>>)
      v = putStr ""

（为了方便起见，大家可以看到 Haskell 的版本里那个 data 其实不是『等价』Racket 里我们所预期的表结构的）

当然，如果我们写『完全等价』的呢？

t1 = [1, 2]
t2 = [1, [2, 3]]
t3 = [[1, 2], 3]
t4 = [[1, 2], [3, 4]]

treeSum' :: [Int] -> Int
然后就写不出等价的来...

<del>
treeSum' :: [Int] -> Int
treeSum' xs
| length xs == 1 = head xs
| (x : xs) = x + treeSum' xs
| otherwise = treeSum' (head xs) + treeSum' (head (tail xs))

因为这个逻辑实在有点复杂，貌似简单一点的 Haskell Cons 模式匹配弄不了，只好使用 Guard Pattern（
</del>

『好的程序应该反映出它所处理的数据结构』
这话不是我说的，看完上面的小学生水平 Haskell/Racket 代码后，大家应该理解了这句话吧。

如果有喜欢 #Scheme 的同学，必须记得看完 The Little Schemer（轮子哥管它叫『儿童书』）先再出去『吓人』（悄悄告诉你们... 我就是还没看完所以连 #FP 的 QQ 群都不敢进... hhhh 🤔

#life #dev duangsuse 落实 10:30 准时睡觉『政策』。 🐱

考虑到健康原因（不让自己的努力白费），每晚 10:30(h:m) 必须立即睡觉

== duangsuse::Echo 参考 #Telegram hashtags

duangsuse::Echo 常年利用 hastags 标记消息所含知识领域，并且，这也会为未来 Echo 频道进行简单准确的数据统计带来可能（不然，我也有其他手段，比如 NLP、统计预测）

以下是新的标签实例（不区分大小写、不能保证消息只含这些标签）：

== 消息平台部分
#Telegram #zhihu #Github #so #Coolapk #book #wiki

== 注释部分
#life #China #School #Statement #lib #recommended #low #fix
#project #blog #share #Learn #paper
#dev #tech #art #meetUp #conference
#Moha #Haha
#gnu
#Microsoft #Mozilla #WeChat #QQ #Weibo #Tencent #Baidu #Ali #Qihoo
#tools #code

== 程序设计语言部分
#Kotlin #Java #JavaScript #JavaScript_ES6 #TypeScript
#Rust #Go #Swift #Dart #Crystal
#Ruby #Python #Perl #Tcl #Lua #PHP
#C #D #Cplusplus #CSharp #Objc
#Pascal #Fortran #Delphi #Ada #Basic #VisualBasic
#Scheme #Haskell #Scala #Clojure
#TeX #Graphviz
#Octave #Matlab
#Shell
（有些写出来是为了鼓励我去写，其实不一定真的写过）

== 软件平台部分
#Android #Windows #Win32 #MacOS #Java #Java_JVM #CLR #Qt #GTK #Tk #WxWidgets
#CSS #XML #JSON #KDE #Postgres #dotnet

== 软件技术领域部分

#backend #sysadmin #frontend #sysadmin_net

#OI #CS #IT #Informatics

#stat #ann #ann_dnn #machl
#math #math_linearAlgebra #math_discrete
#se #se_dia #se_ci #se_ee
#comm #net #www #web #http #html #mail #wireless
#circuit #embedded #os #db #db_relAlgebra #SQL
#bin #encoding #encoding_audio #encoding_image #encoding_video #encoding_text
#hpc #parallelism #distributed #simd #gpgpu #crypto
#pl #pl_plt #ce_vee #ce #ce_optimize #fp_monad #fp_proof #fp #oop #oop_arch #sp #parser
#algorithm #struct #lists #maps #sets
#security #security_lowlevel
#signalProc #nlp #phonetic
#cg #cg_dip #cg_3d #cg_2d #cg_lowlevel
#gui #gui_animation #gui_layouts #cli #visualization

#Haskell #Scheme #Scala #FP 支持一下其他内容维护发表一些文章分享，不过好像不是他的吧...

https://epsil.github.io/gll/#continuation-passing-style-section

#FP #scheme #parser 想了解 continuation-passing-style （没有 return 如何编程？）的大佬们可以看看这人的文章，我觉得相当好。实用性，王垠那几十行代码不就是 CPS 优化吗。

照例个人观点：
0. 上文定义了 success/failure 的 union ，以及 (successed val rest) failure ，还有添加回调的 (bind p f)，基本是 (match (p s) [(success v rest) (+ v 1)] [failure failure]) 这么用的。
实现的解析器不支持流，支持 substring 。传递方式是 backtrace (比如 (string "abc") 在 (seq) 里成功则 (cons "abc" (cont "")) 失败就只是 failure 单值，所以要利用 memo 函数)

1. PKT 是不需要这种“优化”的（顶多比过程式慢 50倍的纯函数式框架要用），因为我们的 Seq 明白一解析器失败不考虑后面就 return notParsed ，不需要玩 p1(p2(p3 { })) 这种耗栈的游戏。Kotlin 不支持 CPS 优化，编程也不是智商测试。

2. CPS 也是有一定价值的，虽然它会损失一定性能，但能够拿到调用者的句柄（比如在有 Decide 的模式里，就可以后继操作遍历所有分支了，或者进行异步回调"thunk"函数）。和非 CPS 一样可作为 suspend fun 协程

3. 即便这篇文章相对易懂 #Lisp #Racket ，我不建议大家认真用 Racket ，原因是括号的表现力不够

比如文中 (let (result (apply op args)) (entry (mcons args result)) (set! alist (mcons entry alist)) (m=map)一大堆括号，有没有注意到 (let (a v) expr) 只是为可读性而加的，量定义可以内联…… 只是表达 alist = args to op(args) : alist 甚至 alist[args] = result 的意思呢（这例还是SICP里的呢，多余命名量本身就可能意味着语言性能缺失😢，比如『文言文』里甲乙丙丁一大堆OK么）…… 函数式那么多年修成正果了，开始从“无副作用”往“看起来像过程式”靠，草生(*￣m￣)

4. 从解决实际问题而言我觉得 ParserKt 更贴近，但这个文章所创建的解析组合子用更少的代码定义了更广义的实现方法，非常有意思（最后也用左递归和 regex 创建了计算器，缓存和穷举最长匹配问题如此有意思以至于我开始可惜PKT不用处理它了😳），而且也易懂的讲解了 CPS/trampoline 以及“穷举所有可能结果”的正统函数式思路 #Learn

刚才说完这个我突然想到关于这个 CPS(continuation-passing-style) 的一点不对…… #functional
看起来要么然之前在那篇文章上看的说法是错的，要么然 CPS 是一个类 longjmp() 的控制流概念，不是函数式概念

刚才说的 listE("item", ) = <items>$=<item> op($)</items> 是这样定义的(#Python 的压行技巧，不过之前说的 walrud operator 发现根本不能用)：

def listE(tag, op, xs): e = E(tag+"s" if tag[-1]!='y' else tag[:-1]+"ies"); [lets(E(tag), lambda ee: op(ee,x), e.append) for x in xs]; return e

如果

lets(E(tag), lambda ee: op(ee,x), e.append)

是 cps call-site ，那交给 callee 调用前的 continuation 应该是从 lets() 的头部(？)
程序可组合性的关键点在于，op “返回”后要能覆盖 x 才能算够用，但此例 op 也得能覆盖（而且要实现仅改 gavTo(e,coord) 的“单至多项展开”，这还远远不够吧）
如果不知道 return-side 的 type (接收什么变量)，就是说这种 cps 式编程，必须显式定义回转方类型，或类型不安全(形式参数列表意义--)
看来只有 yield/resume continuation 是好的（

不对啊， CPS 哪里来的 forEach 😂？看来我还不够了解真正纯的函数式……

#lisp . #scheme #plt #parsing 🤔👍
看来我以前还是想多了，简单的方法也可以带来巨大的变化（指用缩进）
define fib(n)
if {n < 1}
n
(+ (fib {n - 1}) (fib {n - 2})

#日常精神分裂 #parsing #JS #scheme
A: 之前说好了要写的 s-expr 解析器，看来是写不了了？还打算复用 JSON.parse 的，以及支持缩进布局，那样就会很有价值吧
B: 之前还打算支持 {;} 可选缩排的，发现和 data notation 侧冲突了，看来是眼高手低😂
A: 其实关键在于易实现性吧，你想用尽量少的代码和低层API实现给应用用的解释器，无论解析结果怎么用？
B: 对了，子序列法比流递归下降法代码量少吗？
A: 无论从什么角度看，加上对 JSON 子语言解析器的复用都不会更省啊……
S表达式是由 Atom/List 两种元素组成的嵌套表，或者说 值/调用参组 的树形列表，一般首项为函数值， 尾余为参数；是三十行以内能实现带调用和 (let 的 动态作用域版。

譬如在解析 () 里的 a b c 单项中，我们实际在读 SList 即 toplevel 的 Expr list ，假设 a 是另一个 () 则：
流递归下降从 ( 后再解析 SList ，它主动完结后刚好在 ) 闭处
无论是靠返回结束索引号的非规范递归下降还是 StringView substr 返回消耗/片段的皆此

子序列在 ( 处直接 findPairedIndex ，这个算法只需处理 "\"" 字符串然后取闭包含子串递归解析，不过这个扫码过程是没有缓存但只需计数开括号的，相对外部()会多数很多遍。

我可以觉得，不用流不等待「不知何处结束」的子串解析结果再检查闭括号较易理解，但是它实际做了无用功，调用栈还是那么高。

B: 就没有什么又易懂又简单的方法去递归下降吗？子序列真的有那么无用吗？
A: 我打算用 function 值把流建模成 s(0)==length, s(1)=="a", s(-1)(1)=="b" 这个样子，还算轻易。
JSON 静态变作流解析有方法，递进长度子串+检查异常pos取头 足矣，全长仍错时即无解析

递归下降如果不显式 substr 而是交 (共享/复制&同步) StrView 的话 #parser 的确对新手不好理解，但套路不复杂。

子序列的话我考虑了一下，如果我们采用复杂点的 visitor 去边解析边执行（自然也可存下再执行）是能实现 if 里兼容一侧语法错误的，显得很 Javascriptic 🌝

B: 很神奇，具体怎么做呢
A: 存参成树允许再遍历的 visitor 就不说，可以给部分递归 () 的 case 变成 ()=>readList(s.substr(findPairedIndex(s,))) 闭包，然后参数求值(反正这语赋值处只有实参组) 时支持惰性求值的程序里兼容下先解析。

其实我并不喜欢边解析边执行，只是有时候（比如 %s fmtstr 等）工作就是很死板所以无所谓了，况且这分块惰性解析涉及函数调用求值序的问题，那就是扯到函数抽象、词法作用域里的闭包 #ce #plt ，不简洁不能体现对灵活的嵌套处理过程的即时利用