作业解析-lisp小案例
目录
1. 作业题目………………………………………………………………
2. 作业目的………………………………………………………………
3. 运行效果………………………………………………………………
4. 实现过程………………………………………………………………
5. 知识点巩固…………………………………………………………..
6 知识拓展……………………………………………………………….
7 学习建议……………………………………………………………….
作业辅导解析
ECS 140A Programming Languages
1. 作业题目:
Winter 2019
match (15 points) : Complete the definition of the function match in hw3-handout/match/match.lisp,which compares a pattern and an assertion.
nfa (15 points) : Complete the definition of the function reachable in hw3-handout/nfa/nfa.lisp,which returns true if a final state is reachable from the start state after reading an input sequence of symbols, and nil, otherwise.
matrix (30 points) : Complete the definition of the function matrix-transpose in hw3-handout/matrix/matrix.lisp, which takes a matrix as input, and outputs its transpose. You may assume that the matrix is well-formed, and not empty.
2.作业目的:
1、 掌握 clisp 的 s-expressions 写法
2、 理解 Internal Representation of Lists 并掌握 clisp 的 Basic List Operations 3、 掌握使用 defun 定义函数和常用结构
4、 掌握 High-Order Functions
2. 运行效果:
Match 题目的测试结果:全部通过

Nfa 题目的测试结果:全部通过

Matrix 题目的测试结果:全部通过

4.实现过程:

参考源码图 1.1
核心代码上图所示,本次作业主要通过以下步骤实现: 1、 除了 ‘!’ 其他的原子都匹配一个 assertion 中的原子初始化数组用以接收用户输入的 数字 2、 遇到 ‘!’ 先假设匹配一个原子 继续匹配(cdr pattern)和(cdr assertion) 3、 若 返回的结果为: ‘T’ ,则向上返回 ‘T’ 4、 否则: ‘!’ 匹配两个原子 直到遍历完 pattern 或者 assertion ,此时 若 两者都为: ‘nil’ 返回 ‘T’ 若 一个为:’nil’ 返回 ‘nil’
5.知识点巩固:
-S-expressions
Common Lisp 程序在语言处理器的不同处理阶段有不同的形式体现,在读取器中识别的是 S-表达式,在求值器中识别的是 Lisp 形式–form ,S-表达式的基本元素是列表(list) 和原子(atom)。 Common Lisp 程序就是用无数括号括起来的各种符号表达式,括号里的 S-表达式 可以有这 么几种组合:纯粹的原子,纯粹的列表,列表和原子,如下: (原子 1 原子 2 原子 3) (列表 1 列表 2 列表 3) (原子 1 列表 1 原子 2 原子 3 列表 2)-List
在 Lisp 中 Lists 像一个二叉树,可以用 car 取出左结点,用 cdr 取出右结点。 理解其内部表示是编写程序的必要步骤
-Defun
使用 defun 定义函数,通常格式如下:
例子:

6. 知识拓展:
-Cons 与 List
我们来创建一个特别的 cons: > (setf z (cons 1 (cons 2 (cons 3 (cons 4 nil))))) > z (1 2 3 4) z 值可以这样理解:它由 4 个 cons 组成,最后一个元素是 nil z 也等价于: > (list 1 2 3 4) 1、像 y 这样的列表,我们称之为点列表,其特征是 cons 的最后元素是一个原子,非 nil, 非空列表。 2、而像 z 这样的列表,我们称之为真列表(list) ,其特重是 cons 的最后元素是 nil, 即空列表。真列表打印输出时,会隐藏掉最后的 nil 值及点。 3、所以,list 是一种特殊的 cons,即真列表是一种特殊的点列表。 4、真列表(list)是可以使用 append 函数的,而点列表不行: > (append z 5) (1 2 3 4 5) > (append y 5) *** Eval error *** Wrong type argument: listp, 4 错误指出,4(y 中的最后一个元素) 不是一个 list,所以不能 append。 真列表(list) 最后的元素是 nil,即空列表,所以是可以加进新元素。-Mapcar
在 lisp 中可以将函数作为映射关系应用到一系列变量上,往往是列表表示。 mapcar 是一个操作列表的函数,它的返回结果也是一个列表,它的第一个参数是一个函数, 后续的参数都是列表。 格式:(mapcar func arglist1 … arglistn) 使用 mapcar 可以非常方便地将(1 2 3) 和(10 20 30)对应相加 > (mapcar #’+ ‘(1 2 3) ‘(10 20 30)) (11 22 33)7.学习建议:
1、 数理解列表内部表示是编写程序的必要步骤。 2、 学习 lisp,需要用迭代式的方式学习,边阅读教程、边理解、边实践。 3、 了解语言的起源和优劣: http://www.ruanyifeng.com/blog/2010/10/why_lisp_is_superior.html