guest 언어 안에서 pair와 선택자와 무한 리스트와 map과 take를 정의하여 compound procedure 인자 지연이 스트림 동작을 만들게 합니다.
생각해 볼 질문
평가기가 모든 compound procedure 피연산자를 자동으로 지연하면 리스트 추상화는 어떻게 달라질까요?
guest 언어의 보통 compound procedure로 lazy-cons 정의하기
지연된 꼬리 매개변수를 강제하지 않고 머리 선택하기
자기 자신을 참조하는 무한 ones 바인딩 만들기
정수의 무한 리스트를 재귀적으로 생성하기
완전한 꼬리를 만들지 않고 guest 프로시저를 lazy list에 매핑하기
엄격한 유한 소비자로 필요한 결과만 요구하기
lazy-cons는 선택자 프로시저를 반환하는 보통 프로시저입니다. 지연 평가기에서는 x와 y 매개변수가 thunk입니다. lazy-car는 x를 반환하는 선택자를 pair에 적용하므로 y는 강제되지 않습니다. 따라서 ones의 지연된 꼬리가 자기 이름을 참조해도 그 조회는 define이 바인딩을 설치한 뒤 lazy-cdr가 필요로 할 때까지 일어나지 않습니다.
integers-from과 lazy-map도 보통 재귀 문법을 사용합니다. 재귀 호출은 lazy-cons의 지연된 y 피연산자이므로 무한한 나머지가 평가기 thunk로 표현됩니다. take는 요구 경계입니다. primitive cons는 실제 인자가 필요하므로 요청한 수만큼만 머리와 꼬리를 강제해 유한 호스트 리스트를 만듭니다. 이 예제는 수업 평가기와 리스트를 통합하고 요청한 앞부분의 강제 과정을 기록합니다.
SICP 코드UTF-8 7,774 / 1,048,576바이트
(begin(define(tagged-list?expressiontag)(and(pair?expression)(eq?(carexpression)tag)))(define(self-evaluating?expression)(or(number?expression)(string?expression)(boolean?expression)))(define(quoted?expression)(tagged-list?expression'quote))(define(if?expression)(tagged-list?expression'if))(define(lambda?expression)(tagged-list?expression'lambda))(define(begin?expression)(tagged-list?expression'begin))(define(definition?expression)(tagged-list?expression'define))(define(text-of-quotationexpression)(cadrexpression))(define(if-predicateexpression)(cadrexpression))(define(if-consequentexpression)(caddrexpression))(define(if-alternativeexpression)(cadddrexpression))(define(lambda-parametersexpression)(cadrexpression))(define(lambda-bodyexpression)(cddrexpression))(define(begin-actionsexpression)(cdrexpression))(define(definition-variableexpression)(if(symbol?(cadrexpression))(cadrexpression)(car(cadrexpression))))(define(definition-valueexpression)(if(symbol?(cadrexpression))(caddrexpression)(cons'lambda(cons(cdr(cadrexpression))(cddrexpression)))))(define(operatorexpression)(carexpression))(define(operandsexpression)(cdrexpression))(define(pair-bindingsvariablesvalues)(cond((and(null?variables)(null?values))'())((null?variables)(error"too many guest arguments"))((null?values)(error"too few guest arguments"))(else(cons(cons(carvariables)(carvalues))(pair-bindings(cdrvariables)(cdrvalues))))))(define(make-framevariablesvalues)(cons'*frame*(pair-bindingsvariablesvalues)))(define(first-frameenvironment)(carenvironment))(define(frame-bindingsframe)(cdrframe))(define(extend-environmentvariablesvaluesbase)(cons(make-framevariablesvalues)base))(define(lookup-variable-valuevariableenvironment)(if(null?environment)(error"unbound lazy guest variable"variable)(let((record(assocvariable(frame-bindings(first-frameenvironment)))))(ifrecord(cdrrecord)(lookup-variable-valuevariable(cdrenvironment))))))(define(define-variable!variablevalueenvironment)(let*((frame(first-frameenvironment))(record(assocvariable(frame-bindingsframe))))(ifrecord(set-cdr!recordvalue)(set-cdr!frame(cons(consvariablevalue)(frame-bindingsframe)))))(list'definedvariable))(define(make-procedureparametersbodyenvironment)(list'compoundparametersbodyenvironment))(define(compound-procedure?procedure)(tagged-list?procedure'compound))(define(procedure-parametersprocedure)(cadrprocedure))(define(procedure-bodyprocedure)(caddrprocedure))(define(procedure-environmentprocedure)(cadddrprocedure))(define(delay-itexpressionenvironment)(list'thunkexpressionenvironment))(define(thunk?object)(tagged-list?object'thunk))(define(evaluated-thunk?object)(tagged-list?object'evaluated-thunk))(define(force-itobject)(cond((thunk?object)(let((result(actual-value(cadrobject)(caddrobject))))(set-car!object'evaluated-thunk)(set-car!(cdrobject)result)(set-cdr!(cdrobject)'())result))((evaluated-thunk?object)(cadrobject))(elseobject)))(define(actual-valueexpressionenvironment)(force-it(lazy-evalexpressionenvironment)))(define(true?value)(not(eq?value#f)))(define(eval-ifexpressionenvironment)(if(true?(actual-value(if-predicateexpression)environment))(lazy-eval(if-consequentexpression)environment)(lazy-eval(if-alternativeexpression)environment)))(define(eval-sequenceexpressionsenvironment)(cond((null?expressions)'ok)((null?(cdrexpressions))(lazy-eval(carexpressions)environment))(else(actual-value(carexpressions)environment)(eval-sequence(cdrexpressions)environment))))(define(eval-definitionexpressionenvironment)(define-variable!(definition-variableexpression)(actual-value(definition-valueexpression)environment)environment))(define(list-of-arg-valuesexpressionsenvironment)(if(null?expressions)'()(cons(actual-value(carexpressions)environment)(list-of-arg-values(cdrexpressions)environment))))(define(list-of-delayed-argsexpressionsenvironment)(if(null?expressions)'()(cons(delay-it(carexpressions)environment)(list-of-delayed-args(cdrexpressions)environment))))(define(apply-lazyprocedureargument-expressionscalling-environment)(cond((procedure?procedure)(applyprocedure(list-of-arg-valuesargument-expressionscalling-environment)))((compound-procedure?procedure)(eval-sequence(procedure-bodyprocedure)(extend-environment(procedure-parametersprocedure)(list-of-delayed-argsargument-expressionscalling-environment)(procedure-environmentprocedure))))(else(error"not a lazy guest procedure"procedure))))(define(lazy-evalexpressionenvironment)(cond((self-evaluating?expression)expression)((symbol?expression)(lookup-variable-valueexpressionenvironment))((quoted?expression)(text-of-quotationexpression))((if?expression)(eval-ifexpressionenvironment))((lambda?expression)(make-procedure(lambda-parametersexpression)(lambda-bodyexpression)environment))((begin?expression)(eval-sequence(begin-actionsexpression)environment))((definition?expression)(eval-definitionexpressionenvironment))((pair?expression)(apply-lazy(actual-value(operatorexpression)environment)(operandsexpression)environment))(else(error"unknown lazy guest expression"expression))))(defineprobes0)(define(probevalue)(set!probes(+probes1))value)(defineprimitive-bindings(list(cons'++)(cons'--)(cons'**)(cons'//)(cons'==)(cons'<<)(cons'>>)(cons'listlist)(cons'conscons)(cons'carcar)(cons'cdrcdr)(cons'null?null?)(cons'pair?pair?)(cons'probeprobe)))(defineglobal-environment(list(cons'*frame*primitive-bindings)))(defineguest-program'(begin(define(lazy-consxy)(lambda(selector)(selectorxy)))(define(lazy-carpair)(pair(lambda(xy)x)))(define(lazy-cdrpair)(pair(lambda(xy)y)))(defineones(lazy-cons1ones))(define(takestreamcount)(if(=count0)(quote())(cons(lazy-carstream)(take(lazy-cdrstream)(-count1)))))(takeones5)))(actual-valueguest-programglobal-environment))
예제
결과—
출력
—
값
—
진단
—
실행 추적0 / 0 개 이벤트
예상 결과
자기 참조 리스트는 (1 1 1 1 1)을 반환합니다. 매핑한 정수 리스트는 (1 4 9 16 25 36)을 반환합니다.
실행 추적에서 볼 점
각 lazy-cons 적용과 지연된 y 피연산자를 찾으세요. ones 실행에서는 define이 바인딩을 설치한 뒤 lazy-cdr를 통해 처음 자기 참조가 강제되는지 확인하세요. 매핑 실행에서는 이미 완성된 무한 리스트를 상상하지 말고 take가 요구한 integers-from과 square 적용 수를 세세요.
직접 해보기
프로그램을 수정하고 결과를 비교해 보세요.
lazy-filter를 정의하고 짝수 정수 다섯 개를 요구하세요. 같은 앞부분을 두 번 요청한 뒤 메모이즈된 평가기 thunk 중 무엇이 재사용되는지 살펴보세요.
힌트 보기
술어를 통과하지 못하면 지연된 꼬리로 계속 가고 통과하면 재귀 filter 호출이 지연된 둘째 인자로 남는 lazy-cons를 만드세요.