【苏联计算机往事】R-技术

译自 R-Techonology。除非特殊声明,下文中「我」指原文作者 Oleg Kiselyov。 「R-技术(R-Technology)」是一种设计和图形化表示程序的方法,由 V.M. Glushkov 领导的基辅控制论研究所开发。该技术是自 20 世纪 50 年代末及 60 年代初,苏联弹道导弹和后来的太空火箭的航空电子软件设计中发展起来的。(有趣的是,大约二十年后,David Harel 在担任以色列飞机工业公司航空电子软件工程顾问时,发明了一种相当类似的技术--Harel 状态图。)Glushkov 研究所大量使用并推广 R-技术 :据说他们在该领域发表了 600 多篇论文(大部份是俄语的),就这一主题举办了三次全联盟会议和一次国际会议。它们甚至把 R-技术 标准化了--R-chart,ISO/IEC 8631。 20 世纪 80 年代初,我从控制论研究所研究人员出版的几本书和发表的几篇文章中了解到了 R-技术。Glushkov 研究所出版的所有东西都给人一种和 R-技术 有关的印象。我还记得当时看到了画在一张大纸上的完整 Pascal 编译器的图表(R-图表)。 R-技术 基于一种描绘程序控制流的图表。节点是程序的状态,有向边(弧)代表状态转换。弧的上下方都有文字或图形的注释,上方代表转移条件/守卫(guard),下方则描述了该弧将要执行的动作(action),弧是水平的线条。当程序处于特定状态时,我们从上到下查找对应转移条件为真的弧,并执行弧表示的操作,然后把程序状态更新为弧的目标节点。R-技术 与流程图密切相关,不过流程图中的一个节点在 R-技术 图表中是一条带有注释的弧(在 Harel 的状态图中也是如此)。我们称 R-技术 图表为 R-图表,它所描述的抽象机器/自动机则称为 R-机器 或者 R-tran(RTRAN)。 上面对 R-机器 的描述可能会令人联想到状态机。这种相似性并非偶然:Glushkov 是著名的自动机理论研究者,他第一个提出了把正则表达式转化为非确定性有限自动机的算法,还撰写了《Synthesis of Digital Automata》(该著作为他带来了列宁奖和苏联科学院院士资格)。与有限状态自动机不同的是,R-机器 转换状态的条件可以不只是对输入的测试,可以是任意复杂的。稍后可以看到一个例子:那 R-机器 名义上只有两个状态,但它还有可变状态,其动作会更新可变状态,因此实际状态的数量是无限制的。在我看来,R-机器 看起来总是像图灵机,但 R-机器「控制」实际事物,其动作不仅是读写和移动磁带。 通常把 R-技术 图表绘制成图像,因此也称该技术为可视化编程技术。不过,用(风格化的)纯文本表示图表也是可行的。我记得在某本书中看到表示 R-程序 的表格,看起来有点像 FORTRAN 或 COBOL 程序输入到打孔机上打孔的样子。表格有四列,分别是当前状态标签、转移条件、动作和目标状态标签。可以按以下方法输入 R-程序:...

February 18, 2024 · 阅卜录 · Public Domain

【译】shift/reset 编程入门 (3):理论

第二节: Spore:【译】shift/reset 编程入门 (2):应用 3 Delimited Continuation 操作符的理论基础 本节对 delimited continuation 操作符 shift/reset 的理论基础进行概述。我们使用的语言是一个从左到右求值1的 call-by-value λ 演算,并加入了多态的 let 和 shift/reset 操作符。 3.1 语法 (value)V::=x | λx.M(term)M::=V | M M | let x=M in M | Sk.M | M(pure evaluation context)F::=[ ] | F M | V F | let x=F in M(evaluation context)E::=[ ] | E M | V E | let x=E in M | E其中,shift (fun k -> M) 记作 $\mathcal{S}k....

September 26, 2022 · 知乎用户NsydZj · CC BY 4.0

【译】shift/reset 编程入门 (0)&(1):前言和概述

0 译者前言 本文译自浅井健一先生的《shift/reset プログラミング入門(Introduction to Programming with Shift and Reset)》。找了一圈之后发现整个知乎上都没人教怎么使用 delimited continuation,遂翻译。 一些说明: 虽然文中说有任意函数式编程语言的经验即可,但例子和练习题用的是一个 Caml 变体,所以想要获得最佳阅读体验还是要了解 OCaml 或其他 ML 系编程语言的基础语法。 Rust 不算。 译文同时参考日语和英语版本,两版本如有不同则以正确/易懂一方为准。 部分译者的评论或解释用〔〕标注。原文的引用和注释则尽量还原(但由于知乎的限制只能混在一起了)。 译者翻译相关文献的经验并不丰富,如有任何错漏或可改进处请务必指出。 接下来开始正文内容。 摘要 Continuation 是在各种编程语言中都普遍存在的概念。条件语句是根据条件从两个 continuation(未来)中选择一个的操作,异常则可看作是丢弃一部分 continuation 的操作。还有,尾调用(goto 语句)就是执行 continuation 的操作。尽管 continuation 是这样一个无处不在的、十分自然的概念,目前为止,显式地使用 continuation 编程仍然一直被认为是困难的。 本教程使用 delimited continuation 操作符 shift 和 reset 来演示如何显式地使用 continuation,从零开始讲解关于 continuation 的基础知识,并在过程中指导读者实现简单的协程和非确定性搜索。本教程同时也能作为 CW 2011 演讲内容的引子。 本教程需要读者熟悉 OCaml、Standard ML、Scheme 或 Haskell 等函数式编程语言,但不需要读者在阅读本文前有任何有关 continuation 的知识。教程中穿插了各种练习问题,推荐读者随读随做。 1 引言 Continuation 就是表示「之后的计算」的概念。它可以看作是异常处理的一种推广,但远比异常处理要强力。实现复杂的计算时,实现者有时会发现需要使用在通常的程序结构中难以写出的控制结构。如果能操作 continuation,则可以在不影响程序整体可读性的前提下实现它们。 想要显式地使用 continuation,一种传统的方式是对整个程序进行 CPS1变换〔continuation passing style,指把 continuation 作为参数显式传递的编程风格〕,但这样就不能保留程序的原有结构。为了在引入 continuation 的同时保持程序的正常结构,我们就需要使用 continuation 操作符。...

August 18, 2022 · 知乎用户NsydZj · CC BY 4.0

【译】shift/reset 编程入门 (2):应用

第一节: Spore:【译】shift/reset 编程入门 (0)&(1):前言和概述 2 shift/reset 编程 2.1 什么是 Continuation Continuation,简而言之就是「之后的计算」。程序的执行过程就是选出要执行的部分(称作 redex〔reducible expression,可归约表达式〕),对它求值,再使用它的结果来进行之后的计算。这里的「之后的计算」就是指 continuation。因此,continuation 是任何程序执行时都存在的基本概念。 为了展示 continuation 具体是什么,我们用 [...](称作 hole)来表示一段程序接下来要执行的部分。比如 3+521 这一算式中,如果接下来要执行的部分是 52 的话就可以写作 3+[52]1,而这时的 continuation 就是 3+[  ]1。总之,得到 [  ] 的值(52 的结果 10)之后,「给这个得到的结果加上 3 减去 1」就是整个式子当前的 continuation。从「接受 hole 的值之后用它进行计算」这方面来看,continuation 和函数是相似的。 也可以用「抛出异常时扔掉的那部分程序」来看待 continuation。例如,把上述例子中 [  ] 的部分换成 raise Abort,让它抛出异常,这时候被抛弃的部分 3+[  ]1 就是 continuation。...

August 11, 2022 · 知乎用户NsydZj · CC BY 4.0

半条命

最近观察到一些人跟事,有感而发。 假设你听说编程很厉害,有很多用,想学编程,但是编程有这么多不同的分支,有手机APP开发,有算法,有深度学习,有区块链,有编程语言。。。你该学什么好呢? 很明显,因为你基本上不懂编程,所以你无法做技术上的分析,那你只能从表面上分析:越热门火爆,越缺人的东西,越适合 - 供需关系,基础经济学嘛,人才越缺,我越好找工作,工资越高,热门的方向,发paper更多人cite,做出项目也有更多star,更多人用,谁不想被更多人需要呢? 如果这方向还比较简单,这就更好了:同等条件下,为什么要选更辛苦的工作,而不是轻轻松松攒钱? 但是如果你真这样选,那就把自己坑了。 在说原因之前,我们先来考虑一些问题。 众所周知,技术会过时,30年前学的visual foxpro到现在价值为零,而你不希望你学的东西毫无用处,那你应该去学更不会过时的技术(半衰期更长)。而什么技术半衰期更长? 更新迭代比较慢的技术。大版本号每上升一次/新框架推出一次,你就要重新学习一次新的API(比如啥tensorflow啥react),然后还要把旧的代码升级上去。 已经活了很久的技术。如果大公司推出了一个新平台,很可能过几年就打入冷宫,重新选个新欢(Objective C)。或者更惨的,这个方向直接凉凉(VR),你学的东西全部变废物,好不好玩? 很不巧的是,热门的方向正好这两点都不具备。 热门的方向,自然有各大公司卖力的去推平台推框架竞争,飙版本号,生怕落后一点点就丧失掉大蛋糕。这样迭代周期一两年一单位,你要不停翻新你会的知识,君不见tensorflow2.0一出,一推叫着我不行了,不能再学的?(如何评价 TensorFlow 2.0 版本,是否是 Google 再一次力挽狂澜?) 如果一个方向活了很久,那为什么最近才变得热门?就算我们去考虑特例,比如大环境变了,突然这个方向变得可行(GPU跟大量数据导致深度学习效果很好),那以前学的东西也变得没用了 - 因为玩法变了。90年代那些链接主义NN在现代还有什么用吗? 如果你选了个更简单的工作,那你处境更危险:本来低半衰期就导致你难以积累技术,现在再加上积累了的技术也不会带来太多竞争力,那过个五年,你不能再经常996,工资也变高了,然后跟新员工技术上拉不出差距,然后当方向慢慢变冷,竞争变激烈的时候,老板不炒你,难不成留着你过年?注意,有的工作准入门槛低,但这不等于简单 - 因为提升能力的最有效方法就是让你做刚好在能力范围外的事情。 你可能会反问‘难不成我看啥方向冷门,然后一头扎进去饿死?’ 也不是。你应该做的是去学习基本功。比如啥操作系统,算法,编程语言,体系结构这些。 这些东西都出来半世纪多了,能发掘的都发掘得差不多了,所以你能随便打开任意优质大学的公开课,然后毫无违和感的假装自己活在1990。 半世纪多的东西也不会一天突然凉凉,被打入冷宫需要重新学习。这些东西也不是一个公司能左右的 - 谁家产品这么长命? 同时,做这些基础方向,也不代表你不能做有实际impact的工作,只能去grind 1% gain,或者直接呆象牙塔,无实际应用(不一定是坏事)- 你完全可以打好基础,然后去用这些基础做各种热门应用,这样大家都需要你,但是你的半衰期则是几十年,等你的应用方向凉凉,人老珠黄了你拔吊无情,去接着做其他的应用方向,岂不美哉? 比如我表面上看上去是在做深度学习框架(TVM),其实天天都在写SML Compiler,一边在看Abstracting Abstract Machine打算实现下,另一边写的代码却被deploy到亚马逊,爽歪歪。 再举个反面例子:在这么多深度学习框架/算法中,有很多(我数出了五个,其中还有citation就快上万的教授的paper,不想点名,因为这是体制的问题,就lantern没问题)都自称对自动求导做出了创新,但是其实90年代的啥ADIFOR ADIC就已经覆盖了所有的所谓创新(其中还有这些新work由于缺乏自动求导常识做的负优化)。如果这些人肯耐着性子去看几十年前的自动求导书,从头翻到尾,也不至于闹这种笑话。 PS:我本来觉得这些道理本科生也都懂的,但是认识了好几个不好好打基础去学新潮东西的高中生,写上来希望对这种人有帮助。

October 1, 2019 · 圆角骑士魔理沙 · CC BY-SA 4.0

Some Pattern on Programming

我想说一些旧闻。更准确的说,我收集了很多旧闻,想整理一下,变成一个没那么旧的旧闻。 0:对于很多编程语言,我们真能做到‘给出编程语言X跟Y,给X一步步加功能,修改下原本的功能,最后成为Y’。我们姑且叫这做计算力吧。这方面的Work数不胜数。 对于Effect,我们有: C is a purely functional language Dijkstra Monad(被EK吐槽就是hoare monad on continuation) Lazy Functional State Thread Lambda The Ultimate Imperative Gedanken 对于Subtyping,我们有: The Essence of Algol(这也应该算Effect的,但那边挤满了) A Semantics of Multiple Inheritance 至于Type?那就更多了 Untyped Program is unityped program Gradual Typing上的work,不太清楚 Well typed program cant be blamed Type System as Macro Semantic上面有Unified Theory of Programming 编译器上面某种意义上也符合这个样子,如Lambda The Ultimate Goto,Compiling With Continuation,就是在给你说‘你看,函数,高阶函数,其实还是goto那一套。’ 当然,LTU Goto严格来说不算Compiler,各种东西都算一点,但不放这一个Compiling With Continuation好孤单( 最后,Prolog也能这样搞,Dijkstra老爷子厉害啊,一个小改动(GCL)竟然能影响到这 1:在PL以外,我们也能做到这点,有的时候还能直接unify出以前还没发现的东西 A Unifying theory of Garbage Collection - 你看看,各种GC算法都是一个路子的...

October 28, 2018 · 圆角骑士魔理沙 · CC BY-SA 4.0