我试图在这里理解SICP中描述的统一算法
特别是,在"尽可能扩展"的过程中,有一个检查(标有星号"*"的第一个地方),它检查右手"表达式"是否是已经绑定到某个东西的变量.当前帧:
(define (extend-if-possible var val frame)
(let ((binding (binding-in-frame var frame)))
(cond (binding
(unify-match
(binding-value binding) val frame))
((var? val) ; *** why do we need this?
(let ((binding (binding-in-frame val frame)))
(if binding
(unify-match
var (binding-value binding) frame)
(extend var val frame))))
((depends-on? val var frame)
'failed)
(else (extend var val frame)))))
相关评论指出:
"在第一种情况下,如果我们尝试匹配的变量没有绑定,但我们试图匹配它的值本身就是一个(不同的)变量,有必要检查该值是否绑定,并且如果是的话,要匹配它的价值.如果比赛的双方都没有约束,我们可能会绑定到另一方."
但是,我想不出这实际上是必要的情况.
我认为,它正在谈论的是你目前可能有以下框架绑定的地方:
{?y = 4}
然后要求"extendIfPossible"绑定从？z到？y.
当出现"*"检查时,当被要求用"？y"扩展"？z"时,我们看到"？y"已经绑定到4,然后递归地尝试将"？z"与"4"统一,这导致我们用"？z = 4"扩展框架.
没有检查,我们最终只用"？z =？y"扩展框架.但在这两种情况下,只要？z还没有被其他东西绑定,我就没有看到问题.
请注意,如果- Z 就已经被绑定到别的东西,然后代码没有达到部分标有"*"(我们早就递归到什么？ž统一已经匹配).
经过深思熟虑之后,我意识到可能存在某种形式的争论,即生成一个"最简单"的MGU(Most General Unifier).例如,您可能希望MGU具有引用其他变量的最少数量的变量...也就是说,我们宁愿生成替换{？x = 4,？y …
所以; 我是一个尝试通过SICP工作的业余爱好者(它是免费的!)并且在第一章中有一个示例程序,旨在计算用美国硬币进行更改的可能方法; (change-maker 100)=> 292.它的实现类似于:
(define (change-maker amount)
(define (coin-value n)
(cond ((= n 1) 1)
((= n 2) 5)
((= n 3) 10)
((= n 4) 25)
((= n 5) 50)))
(define (iter amount coin-type)
(cond ((= amount 0) 1)
((or (= coin-type 0) (< amount 0)) 0)
(else (+ (iter amount
(- coin-type 1))
(iter (- amount (coin-value coin-type))
coin-type)))))
(iter amount 5))
无论如何; 这是一个树递归过程,作者"留下挑战"找到一个迭代过程来解决同样的问题(即固定空间).我没有幸运得到这个或在沮丧后找到答案.我想知道这对我来说是不是一个大脑放屁,或者是作者和我搞砸了.
我在网上找到了本课的代码(http://groups.csail.mit.edu/mac/ftpdir/6.001-fall91/ps4/matcher-from-lecture.scm),我有一段时间了试图调试它.该代码看起来与Sussman所写的相当:
;;; Scheme code from the Pattern Matcher lecture
;; Pattern Matching and Simplification
(define (match pattern expression dictionary)
(cond ((eq? dictionary 'failed) 'failed)
((atom? pattern)
(if (atom? expression)
(if (eq? pattern expression)
dictionary
'failed)
'failed))
((arbitrary-constant? pattern)
(if (constant? expression)
(extend-dictionary pattern expression dictionary)
'failed))
((arbitrary-variable? pattern)
(if (variable? expression)
(extend-dictionary pattern expression dictionary)
'failed))
((arbitrary-expression? pattern)
(extend-dictionary pattern expression dictionary))
((atom? expression) 'failed)
(else
(match (cdr pattern)
(cdr expression)
(match (car pattern)
(car expression)
dictionary)))))
(define (instantiate skeleton …我是麻省理工学院开放式课程的SICP课程的初学者,使用视频讲座和在线提供的书籍.昨天我遇到了一个例子,它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量.
这个问题有一个简单的解决方案作为递归过程:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
如果你想检查更多,我从这里拿走它.
他们通过添加以下内容计算使用K种硬币改变数量(N)的数量(N):
没有第一类硬币的改变A的方式(X)的数量.
改变(A - D)的方式(Y)的数量,其中D是fisrt硬币的面额,使用所有K种类型的硬币.
问题是,我只是不明白这一点.接着,他们试图解释说:
"要明白为什么这是真的,请注意改变的方法可以分为两组:那些不使用任何第一种硬币的那些,以及那些使用任何第三种硬币的方法.因此,改变方法的总数对于某些金额等于不使用任何第一种硬币进行金额变更的方式的数量,加上假设我们使用第一种硬币进行变更的方式的数量.(最后一句话)与加法N = X + Y相同？)但后一个数字等于使用第一种硬币后剩余数量的变化方式的数量.(使用此硬币后,它们指的是方式是否使用第一种硬币进行更改？) " …
在尝试通过SICP(可能同时观看部分/全部MIT 6.001视频)的背景下,使用MIT Scheme与使用DrScheme的优缺点是什么？
我一直在研究计算机程序的结构和解释,并完成Haskell的练习.前两章很好(github上的代码),但第3章让我更难思考.
首先是谈论管理国家,以银行账户为例.他们定义一个函数make-withdraw通过
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
这样您就可以执行以下代码:
(define w1 (make-withdraw 100))
(define w2 (make-withdraw 100))
(w1 50)
50
(w2 70)
30
(w2 40)
"Insufficient funds"
(w1 40)
10
我不确定如何在Haskell中模仿这个.我首先想到了一个使用State monad的简单函数:
import Control.Monad.State
type Cash = Float
type Account = State Cash
withdraw :: Cash -> Account (Either String Cash)
withdraw amount = state makewithdrawal where
makewithdrawal balance = if balance …在SICP的3.2.2节中执行以下代码
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
(f 5)
根据该图解释.
每次应用函数时,都会创建一个新帧(标记为E1through E4),表示符号和值之间的一组绑定.当符号未绑定在框架中时,将查询该框架的封闭环境以查找该特定符号的绑定.
该图的有趣之处在于标记的所有帧E都包含在全局环境中.该文本解释说这是因为函数是在全局环境中定义的,但没有详细说明问题:
请注意,每个帧都由
square指向全局环境创建,因为这是square过程对象指示的环境.
相反,如果框架包含在调用函数的环境中,比如E3包含在E2其中E1,那么它是否是动态作用域语言如何工作的有效模型？此外,图中的框架具有相同的"父"环境的方式是因为Scheme是词法范围的吗？
我在阅读dr drcket的输出时遇到了麻烦.默认情况下,它使用mcons显示列表.例如,sicp exercise 2.32产生:
> (subsets (list 1 2 3))
(mcons
(mcons
'()
(mcons
(mcons 3 '())
(mcons
(mcons 2 '())
(mcons
(mcons 2 (mcons 3 '()))
(mcons
(mcons 1 '())
(mcons
(mcons 1 (mcons 3 '()))
(mcons
(mcons 1 (mcons 2 '()))
(mcons (mcons 1 (mcons 2 (mcons 3 '()))) '()))))))))
'())
我读这篇文章时遇到了麻烦.有没有办法使输出看起来像:
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
谢谢!
我将通过SICP进行自学,并参与第2章的图片语言部分.我一直在使用DrRacket进行早期练习,但在尝试基于"画线"进行练习时出现编译错误本书这一部分的图片功能.
具体来说,这段代码......
(define (segments->painter segment-list)
(lambda (frame)
(for-each
(lambda (segment)
(draw-line
((frame-coord-map frame) (start-segment segment))
((frame-coord-map frame) (end-segment segment))))
segment-list)))
...产生这个错误......
draw-line: unbound identifier in module in: draw-line
所以我在这个论坛做了一些研究,并安装了Neil Van Dyke提供的SICP软件包(http://www.neilvandyke.org/racket-sicp/#(part._usage)).我按照所有步骤,按照指示将语言更改为SICP,但仍然得到相同的错误.
我认为这个软件包的目的是定义这个"内置"函数(以及书中的其他函数).只是为了预测一些问题,我在文件中没有'require'语句并使用'#lang planet neil/sicp'来指定语言而不是使用菜单(我也尝试使用菜单将语言更改为SICP并获取一个更奇怪的错误;请参阅下面的附言).我的环境是Windows 7,DrRacket的版本是5.3.1.
也许我只是犯了一个菜鸟错误; 任何见解将不胜感激.
谢谢.
PS:对于那些感兴趣的人,当我使用菜单将语言设置为'SICP(PLaneT 1.17)'时,对于我尝试编译的任何定义(即使是最微不足道的),我都会收到以下错误...
<unsaved editor>:1:0: #%top-interaction: unbound identifier;
also, no #%app syntax transformer is bound in: #%top-interaction
sicp ×10
scheme ×9
racket ×5
lisp ×3
coin-change ×2
algorithm ×1
haskell ×1
recursion ×1
state ×1
state-monad ×1
unification ×1