【PL理论深化】(13) 变量与环境:文法结构 | 真假表达式:isZero E | let 表达式叠放 | 定义的规则 | 条件语句的使用

💬 写在前面:从现在开始,让我们正式设计和实现编程语言。首先,让我们扩展在之前定义的整数表达式语言,以便可以使用变量和条件表达式。

目录

0x00 文法结构

0x01 真假表达式:isZero E

0x02 let 表达式叠放

0x03 定义的规则

0x04 条件语句的使用


0x00 文法结构

扩展后的语言的文法结构如下,在整数表达式语言中增加了四种文法:

在程序中,可以在任意可以出现表达式的位置使用变量 x (随机变量)

let x = E_1 in E_2 是一个声明变量 x 的表达式。

它先将 E_1 的值赋给 x,然后计算 E_2 的值。在此期间,变量 x 的有效范围是 E_2

if E_1 then E_2 else E_3  是一个条件表达式,其计算方式如下。

.

此后,我们约定符号 \top 表示 true,符号 \bot 表示 false。

首先计算表达式 E_1,其结果必须是 \perp 或 \top

  • 如果 E_1 的值是 \top,则计算 E_2
  • 如果 E_1 的值是 \bot,则计算 E_1

0x01 真假表达式:isZero E

为了使用条件表达式,需要创建产生 真/假 的表达式,因此我们添加了语法:

\textrm{iszero}\,\, E

它计算表达式 E 的值,如果值为 0,则计算为 \top,否则为 \bot

由于它类似于 OCaml 的语法,可以很容易感受到可以编写哪些程序,举几个例子:

下面是一个程序,首先变量 x:= 1,然后计算 x+2 的值,结果是 3

let x = 1 in x + 2

0x02 let 表达式叠放

在 let 表达式的 E_2 位置上可以放置另一个 let 表达式

let x = 1
in let y = 2
  in x + y

表达式 x+y 中,x 和 y 分别代表 1 和 2,因此程序的计算结果是 3。

.

也可以在 let 表达式的 E_1 位置上放置另一个 let 表达式,如下所示。

let x = let y = 2
        in y + 1
in x + 3

表达式 let y = 2 in y + 1 的值为 3,将其命名为 x 后,计算表达式 x+3 的结果为 6。

在计算表达式 x+3 时,请注意变量 y 不可用。

变量 y 的作用范围仅限于表达式 y+1,因此在其他地方无法使用。

因此,下面的程序在语法上没有问题,但在执行时会出现问题。

let x = let y = 2
        in y + 1
in x + y

0x03 定义的规则

可以多次使用相同的名称进行定义,如下所示。

let x = 1
in let y = 2
    in let x = 3
        in x + y

在最后一行计算 x+y 时,x 表示最后定义的值 3,因此 x+y 的值是 5。

重新定义具有相同名称的变量并不会改变先前变量的值。

使用 let 定义变量并不是修改现有变量的值,而是创建一个新名称,在其作用域内具有意义。

例如下面的程序:

let x = 1
in let y = let x = 2
           in x + x
    in x + y

上述程序计算的结果是 5。第一行定义变量 x:= 1,第二行定义的 x:= 2

因此第三行的 x+x 的值是 4,因此变量 y 的值为 4。

在最后一行的表达式 x+y 中,变量 x 指的是第一行定义的 x,因此 x+y 的值为 5。

0x04 条件语句的使用

条件语句的使用如下所示。这是一个计算整数 1 的程序。

let x = 1
in let y = 2
    in if iszero (x - 1) then y - 1 else y + 1

.

现在,由于程序不仅可以计算整数,还可以计算真 / 假值,因此存在一些由于类型不匹配而无法执行的程序,即存在 类型错误 (type error) 的程序。例如,看下面的程序。

let x = 1
in let y = iszero x
    in x + y

加法是针对两个整数定义的操作,但由于 y\in \left \langle bool \right \rangle,因此在计算 x+y 时会发生类型错误。

由于我们的语言目前没有静态类型系统,所以无法在执行前发现这类类型错误。

如果在运行过程中发生类型错误,程序将会因此而非正常终止。

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.9.14
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限,本文有错误和不准确之处在所难免,
              本人也很想知道这些错误,恳望读者批评指正!

📜 参考资料 

- R. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015.

- T. Cormen《算法导论》(第三版),麻省理工学院出版社,2009年。

- T. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018.

- J. Kleinberg&E. Tardos, Algorithm Design, Addison Wesley, 2005.

- R. Sedgewick&K. Wayne,《算法》(第四版),Addison-Wesley,2011

- S. Dasgupta,《算法》,McGraw-Hill教育出版社,2006。

- S. Baase&A. Van Gelder, Computer Algorithms: 设计与分析简介》,Addison Wesley,2000。

- E. Horowitz,《C语言中的数据结构基础》,计算机科学出版社,1993

- S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.

- A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974.

- M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997.

- A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003. - A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.

- E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.

- R. Sedgewick, Algorithms in C: 第1-4部分(第三版),Addison-Wesley,1998

- R. Sedgewick,《C语言中的算法》。第5部分(第3版),Addison-Wesley,2002

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/760666.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Leetcode 78 数组子集

题目描述: 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的 子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums [1,2,3] 输出&#xff1…

Python-数据分析组合可视化实例图【附完整源码】

数据分析组合可视化实例图 开篇:应女朋友的要求,于是写下了这篇详细的数据可视化代码及完整注释 一:柱状图、折线图横向组合网格布局 本段代码使用了pyecharts库来创建一个包含多个图表(柱状图、折线图)和网格布局的…

服装分销的系统架构

背景 服装的分销规则:组织结构由总公司代理商专卖店构成。总公司全权负责销售业务,并决定给代理商的份额;代理商再给货到专卖店,整个组织机构呈现树状结构;上级机构对下级机构拥有控制权,主要控制其销售的服…

利用谷歌云serverless代码托管服务Cloud Functions构建Gemini Pro API

谷歌在2024年4月发布了全新一代的多模态模型Gemini 1.5 Pro,Gemini 1.5 Pro不仅能够生成创意文本和代码,还能理解、总结上传的图片、视频和音频内容,并且支持高达100万tokens的上下文。在多个基准测试中表现优异,性能超越了ChatGP…

MySQL高阶:事务和并发

事务和并发 1. 事务创建事务 2. 并发和锁定并发问题 3. 事务隔离等级3.1 读取未提交隔离级别3.2 读取已提交隔离级别3.3 重复读取隔离级别3.4 序列化隔离级别 4. 死锁 1. 事务 事务(trasaction)是完成一个完整事件的一系列SQL语句。这一组SQL语句是一条…

植物大战僵尸融合版2024最新版本登场,绝对能满足你的所有期待!

一开场,就让我们直切主题。各位玩家,是否已对《植物大战僵尸》中的传统植物和僵孠对决失去了新鲜感?是否渴望体验更具创意、更富挑战性的游戏玩法?那么,让我来告诉你,《植物大战僵尸融合版》1新版本的登场&…

AI论文速读 | 2024[KDD]ASeer基于异步时空图卷积网络的不规则交通时间序列预测

题目:Irregular Traffic Time Series Forecasting Based on Asynchronous Spatio-Temporal Graph Convolutional Network 作者:Weijia Zhang, Le Zhang, Jindong Han(韩金栋), Hao Liu(刘浩), Jingbo Zhou…

纯硬件FOC驱动BLDC

1. 硬件FOC 图 1 为采用 FOC 的方式控制 BLDC 电机的过程,经由 FOC 变换( Clark 与 Park 变换) ,将三相电流转换为空间平 行电流 ID 与空间垂直电流 IQ。经过 FOC 逆变化逆( Clark 变换与逆 Park 变换) ,将两相电流转换为三相电流用于控 制电…

容器:deque

以下是对于deque容器知识的整理 1、构造 2、赋值 3、大小操作 4、插入 5、删除 6、数据存取 7、排序 #include <iostream> #include <deque> #include <algorithm> using namespace std; /* deque容器&#xff1a;双端数组&#xff0c;可以对头端进行插入删…

网页用事件监听器播放声音

一、什么是监听器&#xff1a; 在前端页面中&#xff0c;事件监听器&#xff08;Event Listener&#xff09;是一种编程机制&#xff0c;它允许开发者指定当特定事件&#xff08;如用户点击按钮、鼠标悬停、页面加载完成等&#xff09;发生时执行特定的代码块。简而言之&#x…

clonezilla(再生龙)克隆物理机linux系统,然后再去另一台电脑安装

前言: 总共需要2个u盘,一个装再生龙系统,一个是使用再生龙把硬盘备份到另一个盘里面,恢复的时候,先使用再生龙引导,然后再插上盘进行复制 1.制作启动u盘 1.1下载再生龙Clonezilla 下載 1.2下载UltraISO(https://cn.ultraiso.net/uiso9_cn.exe) 1.3 打开UltraISO,选择co…

Vue 解决报错 VM6290:1 Uncaught SyntaxError: Unexpected identifier ‘Promise‘

Vue 报错 VM6290:1 Uncaught SyntaxError: Unexpected identifier ‘Promise’ 排查 控制台报了一个错误 , Uncaught SyntaxError: Unexpected identifier ‘Promise’&#xff0c;网上查到的方法是 缺少符号&#xff0c;语法写法错误&#xff0c;但这些都没有解决我的问题&am…

用Lobe Chat部署本地化, 搭建AI聊天机器人

Lobe Chat可以关联多个模型&#xff0c;可以调用外部OpenAI, gemini,通义千问等, 也可以关联内部本地大模型Ollama, 可以当作聊天对话框消息框来集成使用 安装方法参考&#xff1a; https://github.com/lobehub/lobe-chat https://lobehub.com/zh/docs/self-hosting/platform/…

RCE漏洞

RCE&#xff08;Remote code/command execution&#xff09;&#xff0c;远程代码执行和远程命令执行。在很多web应用开发的过程中&#xff0c;程序员可能在代码中编写一些能够运行字符串的函数&#xff0c;当用户可以控制输入内容时&#xff0c;这就导致了RCE漏洞。 1 远程代…

《昇思25天学习打卡营第4天|数据集 Dataset》

文章目录 前言&#xff1a;今日所学&#xff1a;1. 数据集加载2. 数据集迭代3. 数据集常用操作与自定义数据集 前言&#xff1a; 今天学习的是数据集的内容。首先&#xff0c;数据是深度学习的基石&#xff0c;高质量的数据输入能够在整个深度神经网络中发挥积极作用。MindSpo…

安全和加密常识(6)Base64编码方式

文章目录 什么是 Base64编码原理编解码示例应用什么是 Base64 Base64 是一种用于将二进制数据编码为仅包含64种ASCII字符的文本格式的编码方法,注意,它不是加密算法。它设计的目的主要是使二进制数据能够通过只支持文本的传输层(如电子邮件)进行传输。Base64常用于在需要处…

STM32 SWD烧写

最小电路 stm32f103x 内部已经集成了振荡电路&#xff0c;可以省略&#xff1b;rst引脚电路&#xff0c;可以省略&#xff0c;boot0,boot1不需要设置 正常烧录 -------------------------------------------------------------------STM32CubeProgrammer v2.9.0 …

C++旋转点坐标计算

/// 获取A点绕B点旋转P度后的新坐标/// </summary>/// <param name"Angle">角度</param>/// <param name"CirPoint">圆心坐标</param>/// <param name"MovePoint">移动点的坐标</param>/// <param…

window搭建git环境

1.下载安装window下git专用软件scm 从Git for Windows 官网网站下载&#xff0c;并且一路安装即可 安装成功后通过桌面快捷图标Git Bash点击打开 安装后软件应该会自动帮助配置环境变量&#xff0c;如果没有需要自己配置使用 2.git环境配置 2.1设置姓名和邮箱(github上你注…

编码器的使用

视频 提高部分-第4讲 编码器的使用(1)_哔哩哔哩_bilibili 编码器单位 编码器总分辨率 编码器 一圈所计算的脉冲数&#xff08;但由于定时器会倍频 所以计算时要乘以倍频系数&#xff09; 在淘宝上看的分辨率物理分辨率 实际分辨率物理分辨率 * 定时器倍频数&#xff08;一…