作业解析-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 题目的测试结果:全部通过

image

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

image

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

image

4.实现过程:

4.1 match

image

参考源码图 1.1

核心代码上图所示,本次作业主要通过以下步骤实现: 1、 除了 ‘!’ 其他的原子都匹配一个 assertion 中的原子初始化数组用以接收用户输入的 数字 2、 遇到 ‘!’ 先假设匹配一个原子 继续匹配(cdr pattern)和(cdr assertion) 3、 若 返回的结果为: ‘T’ ,则向上返回 ‘T’ 4、 否则: ‘!’ 匹配两个原子 直到遍历完 pattern 或者 assertion ,此时 若 两者都为: ‘nil’ 返回 ‘T’ 若 一个为:’nil’ 返回 ‘nil’
    1. nfa

      image 核心代码上图所示,本次作业主要通过以下步骤实现: 1、在 nfa 中所有可能的结果组成一棵树, 2、如果叶子节点的值与状态 final 相同,则为可行路径,返回’T’。 3、否则 没有可行路径,返回’nil’。 4、使用深度优先搜索这颗树。
    2. matrix

image 核心代码上图所示,本次作业主要通过以下步骤实现: 1、第一个 mapcar 取出 m1,m2 中对应的每一行作为参数调用 lambda 2、再在 lambda 声明的函数中使用 mapcar 将两个列表对应对应的位置相加,得到结果。

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 取出右结点。 理解其内部表示是编写程序的必要步骤 image

-Defun

使用 defun 定义函数,通常格式如下: image

例子:

image 定义函数 sum ,它的参数是 x 和 y,在函数中执行 x+y 操作。调用 sum 函数,2 和 3 作为实 参传入,结果输出 5。

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