Scheme - データによる抽象の構築(対を手続きで表現、Church数)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.1(データ抽象入門)、2.1.3(データとは何か)の問題 2.4、問題 2.5、問題 2.6を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.4

置き換えモデル

(car (cons x y))

((cons x y) (lambda (p q) p))

((lambda (m) (m x y)) (lambda (p q) p))

((lambda (p q) p) x y)

x

証明終

次にcdrの定義。

コード

sample.scm

(define (cons x y)
  (lambda (m) (m x y)))

(define (cdr z)
  (z (lambda (p q) q)))

置き換えモデルで確認。

(cdr (cons x y))

(cdr (lambda (m) (m x y)))

((lambda (m) (m x y)) (lambda (p q) q))

((lambda (p q) q) x y)

y

実際に確認してみる。

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (cdr (cons 1 2))

;Value: 2

問題 2.5

コード

sample.scm

(define (cons a b)
    (* (expt 2 a) (expt 3 b)))

(define (car c)
  (count-div c 2))

(define (cdr c)
  (count-div c 3))

(define (count-div n d)
  (define (inner m result)
    (if (= (remainder m d) 0)
        (inner (/ m d) (+ result 1))
        result))
  (inner n 0))

(define c (cons 5 6)) ; 23328

(define a (car c))

(define b (cdr c))

(define f (cons 12345 67890))

(define d (car f))

(define e (cdr f))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> a

;Value: 5

1 ]=> b

;Value: 6

1 ]=> c

;Value: 23328

1 ]=> d

;Value: 12345

1 ]=> e

;Value: 67890

1 ]=> f

;Value: 949028794864302284513896821444895073398701306901785357161590505610218684257214798785447346306445084081198406087977344683996445063684872838897218339302375051046292634688641985067014501554811998393768600663231403066985104723646190704834252373021456250541577391428280496187604087606330783918580574505108826873136420622805102095880110388155164796512412860741651347382699790664452530050263327560204739491083416097592977742253110516663279662442044362448714973561459538056701499672220672081742468516297330194491515743414919719090268369991356359358805633922370273258432689762096529357094687558905208008801628117279440088368189399755653239474216848508989651893757987512635455699347632027525742075397152183303717805172304813684884821309633569063095931298000303564783135656883910970654413244861357861706915307238137390778621598370957609984315131198991182973611062869449579449649716294911011918515444503146680525642252204806749065916001036634287996505213658655317165764155681402895636486471257610260661492638816126464044706113880860578959454502415326880659045104629873879404334883519289700380652668965092638593495954759701955451176100955445842604900576496363167502953582377009243562736102584847389918402810346281516792338060622078913200750677172525358657874594648204643216888962873103940608108365964383138679076904993329578336404890479947975991427876391138875285630065009844941787439774159913494916761653224858466235677309201586046815555345546647417994045625457782355770895491750477539209821700633467710340982454224860172360682396993302032630233205002683689527845521072613107391617111627079202736013574548354551050436240732855413368216029056623629764923131186914103987701500444264767087157026638274799949151585556350788196290901037985286506583222898760163206854279383988642713242375139162806055199692246547558309754997341964981107761120218896310584705958647887072908406324610516946575826659743562899711855946218149582922135108771558110864682267610034500914602330055915517845110987486238519387759347376959844612402606178634324212218532620175343039736509621891138300776582704071471270028526728763574631930124902388041157409689944815454998063492634000836289831628862043907331313282116761881814273558460983617275642496746896515989435394313427145864929142535077864977513438535590059433346845002460787035399364203291734926451461871262080616816625457387477110724196000456346653713424082477977946420857667669021065045852026552239740693662409807282059072082109830009432132568649031244759741796371371475532630363767540027727704196677602835795859876966478657883405839543084091637592804483129363987470680888335550153306567090096575457465265136433438381338380830611732214566374285698915204136015323440234975179756114614055930308114035050364820049608592573670253892648137855738976306649568842230740213201460939634326046815850473575234209899872626202836623322219782530347810640065157129856762602139895536353176859632968214730699549441825277884766157811902939963661468221701665765392787039186723760363141032158221784690049501053103913320171385790271204122761386648015494129472127344545154264763863963464952513868999562649106758427546073549821362053857569140891487104178848043897533604790471743140953949460563840595803434427170815864167216882086197040964206651657778412422217836367050663768885108151794151737278477115945039065057706548349710437723701079112741652159873843257684183087212869483924097363397365067556583611251478928263066032379343295193137826661000711914227815203652973795903222667469113691588700081014376765288909925135564784770129453630893703419414503111071010528747645480414744004559308247925318735582401654463761026908116757416310448086048065397916264185260331923168116093422374156124625329128847812092240325288937345153345911534527178021543044639495252786111315602228005220048067718571580922264530362355252676216880225934238045983458253628750536247018240222479041155887504008966813789494758214119664193832559597163222698380169996156352079637172256986046305968747384016568226036557565234734670863292367657016205613682405996575600929015016199990850830268231507131972859846126340413582351543812564980227099474366603175314099766523956687364197370540939831024700456891306348282819015739020185070557761274904135248411059525718041194505442784116805916409080005779284733082201884093504633961227953455445894903465410550141064509873960530217986633443537479788099339004897911594287734118685195330634367696461559593179596946389792925412041125717532795951913475825897982234123088715575384947915621602850984950303077100566561258282323314949234271947635040070578591419308210531730273439286481214374161241947700687230936221729521678145771540561181547931340066769640944597849033327866544937945973941844980809529849430562309885799407559237563921283708142205097338238856356840156060365818792865968139052094518301191551870038891530751471420590790544533928796102185012075664679467178377278743923878482240277353252442636888650631425758734577738974541340556116228089413556959948352014219298136801131105891942638207718965527636162801884974805792860051468496434081814380744588198787708399476573859149344615200013734043380491077046013603191651563981602685656777514299194013680175772566992075519332740317124892599595517336868277347680671534087509630386124304047243297637122755047394355658962716430937538142765156704935756125723951033230963073738177556837403505416177895529679853189879346846455498752110925027269916049549634027270052741679645067726354606167990615860179161630874389082296666964735062051381411004293090377976924240501969267082248148098363549676216221372892696227306150382504075318451545744191285241574377487949019518441116656842449559433884475230855700667655808920798316501451644484419269293884001035722408256871330142085682623211192650043391730660484604047876499814615913220664563062482119356940426050601601239838728316289778752786436161320176416322374606769022509177590129523319936881539713597535226785111610501368800089985218385057741125067616333497545906416371408465169400649554955202413856876164049370195848132660942498297670423534056274915021211308345887508629166814720065749760809662226776377387042739404449827517262455899697391099785721225908091141808939524952007822876977216327229444280103787786028899796135329952535117490439407109886693374604148582212285483567626516706248127634198410742877433955603038244000317100421150264631500574743056152207644831332276666883709023582166124682827835247134332733578013496803609980381043413401072295865583718418942771012098877067909494071588957482012508718530148022933481991127630113739304908363199704563362087820074279933754264977261719262180694759233575962704441935187971685239708880989040671188351354527564034305760833273446323660338954734669985022853081176872936411169952763219139984407708318336048105135669543422980301188763811386062322102947723817932513331095258287554380084674326763887694244199045570235254571565447751276452952235254998344712049250797623005541524531520794716917093247156607393047862090042881148595804325587774073492539291457074223351506907101001834086418625609693214516520401881793999890926176974149412438187601068101485164145219468239168463247899399578378713379556663029687904007765375995950287232569641996076466115869859457231953174783626577192319437700563693605616728755577391047891500025485117213322984950400618432700141120712599237035797613968612634606543381756392299233043413105360244253243437265548472756791798405463267153272043804477887275304498292793401014086788659650076079245781860748374958678662967115364120725775890502449526927540133153175572098335861126042222930378432723483365750041037097764979923772620791569559491879836852491369731862264632108042536938406285904495403330461808748499321823035761799316935720426603123850911622118156776072561612845330428346871281617675357145144597774731136267906227728969546091478676424438634169965448364125289910352380710406567708406504802761166863994871922496631740567377789369531660674291203643581556566950756250629266521552452616252333033344267131209655470468048290835011064848051659323538217654220025562766153072267042082269474608534767109552814969090250090682973340633258564190089064017100025431581856213551728592914735439721014371034097321343498540357294164236367017105575060797447464631471610948355183733009527088390475823621289510663165197177879196322138732460670528856774746048971165793225295455943984041801970277877421252380407222110401071138373883184056698926141153598690059373795187475061437147498076204733324156299369090508570210983337217115138284204303592839027287106299092914390553697084458864939604881585891602004684812566469949867871375886420316174900275188969796735077611739220688284712701097408971119946528578058217303748311176570682429169461719017987977410976529486676895247873954707367615032058403194648023470972611718586148180587004094743954233722777486038268352581438550353061231697597836538438628326174657797712158985903165215614732973629352490422078044864189103501630986609661058755545666532129717588175734858649343530976984079253549895340011055878251692689758166636652114967255416887268241931579771266146220321603734330400581676839922668680475801026462920248832409448157981474091878732705668980767060727323816001256110657865855675082298171052780718151734681521092300991060279974718014459488440800023141814342942192186367873074279517555671407543122484974196246280782189517310284109450869636557024150811854418294215438784379110556457271289651611128445152683011861371032536075212753816782123677856831791307213016809970764240695155460076529963954522522414907251203151303888441131674200790519480524406638720740037989071016760123993015111325907221482694049941747447391100214553188260650322804303359819161296940580994704884926662358321508917050980952533350627145418451588478669733258316623315602198429602460603119120474844035603767964422297597611154066441620059865618282937944200320349650187525844554842007027612812887077734339991041896691565858886035757641285738282485449868595618770626543567977489474756947291886242129534524196029774205756572220459016504070982758106256359891485237201570360502156702783901397905545597724562691222991352217951827814313434676623232364630939825548519307541810287222125550013876162729454722336896109519625338078538111244468021733781856805444917217399438701528323155026438803163229368715471678422908415259790902325854116490799311075095208742246661174602637688346535973637118025943388550414528373668379964808051551123284976937833458978710628224445922216623372116455894911405844465611651695014326134985452458020111406821852808456463309623588294275985078893237371501362648277726538159941421540556642367126761016256845557728654543595519371485566419682645432200077407241601795810531901698609425942092107873758676399610682999840260092852384522367610480992881426012822329837466452199413955961060898621020187353813667564160504656733029582098682114535566526432199421647725737017704277936931388037194923295506723037666535431956054706416033961131965157167740279205796997285490862030624315986503143057729586343136264508306328801511721765618548017786427934582457881164172891952029094011036407379459684474419763178035253321787642296926956784791262385574298578097535669899759370819732886509005893060039904647943423370189124312464107427634155878647036567761589367576313488181257416770352176692366573755287402437367121077125863927212641197169557991631401700353974278112779106032243057925942616430191452794769811287355816459971190451984191671639688470872993770772917439727503209012711920804714397698456032086785164807400905737652771232664328171550880457474327792024685730668766412633345665200985850251554574514925528116157368369933191081006908060738661342020329353117412073837671694446884017633197339292060750345786934540541894656597727267000547467221668017175678215106201228050634014326412383107624646549302098765302320491286611761598277100887962690410788618175414276455005408566543889409015869865839681407288662430956981648830026597445860733171262928913768964287392692430314148870699338168100259826129292316707920445761786613504850463984817295623880780316655787100276047788511369179037517678507307471994122663735157655085556280999099200552371392937562835601206448131696146446901991389091589719779682648365058195055378944009147860394497436109953005214586211076969340376262629067691017140682086176310261280345807527939639953473935680412263064211703126851997333367268588098100853291470899624628605939793513430515861011868821875241044514154228684780528072215784160318682090221189806825757903495417532141266969605293673063921557327312725716308167536670675396148144845503277422692649995731553920109149998584844728979362755996333511916830014748384932877368179789752446022107820923284685254269178895171521136976041266135100082922184401493588867185782991941235372043794719618674085776300280426753508057048082340571453333962981883403330164666082000894001226891104812354795939240868057853253811679883420743465731168550903701147474075073392058721996192273165158047310754779458724205352221855304831169190593244391762046285717423925703874588976259804405046517140210289709370148528261759721402244029439827005162170433818600773876151275080762444133266638212753068224441214525046975675395412445150596215262286412996680904265200647481619032678678448911915271432572518156407180348586518772037993452674903996182538827776278107910336838768343438231325722703028119974652437318502510372527819660369826402014719685448127857032896553878451216300526496117345599731450547910010964659282871998751036289872366652704071404273607895092294938863810325665844552997232935300187731395871679376807061034785635406144518179771100028941395876322041148915850221617044446104931860968628240960657160184954831359482419633214995722260703454530123518259276438994156971269104612394323342230834721243086786105591697697391426097593850086463414133606743986312323590484322341576928970885018235258088969579846664726429024251499361845942144485076325229926605696686173216914934575421876307370908210784438237731844968066073479406933870811791258472114001135420241467539724321169051867209071901344103448027106091580624296242365882839356374524583124195276803646642137549206990971393250020849845425263029406643859898584332610457123504316199608376231306248985690695867830431444097984035813581870416938290168366508116677130856177947079330682597355632155861069988392399316169393135586742161353440751093113144738365925283399582588146990853328803074425012703038472580192339996079746472806067022133604602053833498730755660533217665902352771248000123542361741385170050738150417328657698240682792272160509006033606986024952051735008934328969491530170424274616572510889469358053226490016131739027201292653302514433696544113561146822475217960796831601963406713387487451179585336120548530008545384575634691582613804107814315094200919878644227799303972531428585209490895010473081765300606383256084861294243848229850106738115954287939029843885508122018045771043596543567747890890166744223875035474086757971787876353229670389366473707438389849120685346895423767425479852573615956578157783498772713181912643437151672117321355030917802072688897688773808044278125986205596699556602659311481118680446417129790035870188038045833587466178341836344651184299463773312649930161880855012117160031391295811684731693696616386750555092521552848364346530818469267687895163632553156189488792912756228591499794077151049366815791618260065149571912154932134284995460150831260006254947119011243096527876241966558696130870084361833004780006320082094830473552273657227479096935651683212400080482241619235733050815266034196903508635208483092904190959969600160651654234649577819589520152375255313612044092987160852781872197379229124695643000647230119197471560562381470967930278419122252241324857121509768211542291452521980025191903109833304958884262821404883176570855651187377285247877890251047465599294557862324906316273220525097272421494248984706618079627049831077806577957863753578063333911950909001640010673840835038667950954424562429502499861596769691905411844121151514885382612845476267702087851841795718525688254042519935887715101721155342882454492087332390355413632896273550724448923662408399675678862923855579662248300112737346457907025496200470491938874645554725992811731556804783888145773113164613247404882137128989637415186927409821826764380597576985990159414150619000128220170302005507119996504203168473689758707227650011044563331907116415386996442539649076429763944472526347183526974667228412663586433769924891360864905472777888920169306509446834317145466597977928660158829673557494820170102768162536039226446252511456113689725288529250659058150106927827943133771059913217689189497588906739969110857429775018036642411357661325790705243390978988738172093638167611097776418969188272429464158825872050094885355080774195155399792402977534282482130240389259630652396040057647202448635130124633773411841403644975986862747327270365596178790900068950681821482260973066831923459150135851204130175010501460493462530775183770564015121178999250591757240025881336747514446300560951137509873067136151499264701946748844531421287458507974382526644976774178923701918680587359187041486721496901951908099006132302266117670922445347017008081492462264808119792418433328534198586226199708972659491047531369374670711364676728795662675443141880906391393626085798327766975561748359036449268788554679455136612861921053982413120724661413517124951820997945459413068452232045152315998778732306706888471881702215035635650805906089083886189693543760470769637774397754430403126365812415184076844434644031267353235572676256337042033297921272723034762703567168002650735707940396730832972264689005053229906352429609310124174595056584368414225606307463361829245446017057053450560894352745891203727788380263714756836798714409059619472307153814327431077634702054001225295839240393778707516860708444991437529902789175838575273896249650021435271896717390684258459021590868560153901408568934804741700073641832202073784212784494089689567035281382142864374545576685890309753107387667228780370125798042736573373795698182611057694450724374666753802381318833610653796101079208848720344549986103115140924941127342593710758577675028180827188731692768095188106498907443997346794947655765999606817529310366563843917169604250257227094459355525416617011931943335679817601885501852350570639790415706298647031048713505838874374855257755282107059761740417384636459278653428676072564498241075639256534072366385614180863303449681621986551206158848366195178344475296796351657940210166472722891985087158161801032383023679233638637040277790662715159026218657774351260480055904521216180971250284276103294184297378043545691431377384882979682646300953537873753882547464206573172869365402041456251460626439752860746193662918111465426999999029987905675760671728793327334315666402463922087241791171395678779614715152599212989001261576090408500498694398707114777679147817839951913830097323376541767236186694119747308537435528997802679093882803239764418605635126573715803605028976911790502053551293895641101527813288522463847045075008877286602086354035399038626961991383299950257896191448348708427997716475684573629274069869567607947378377828973593552428145199726334237708185932787744481081481439317964744854573981480361945101758171946214220093320353939649096144642718957961105529410513522823543605814287140203424867178622866448569760049002721977076629748348036018547652757806020559765474122679174060320703538355892252342433994687651012407315179191029617985149051803240196296586197205550409898752527842400650107881370476044551221930561951420064126503065884913001599427827814398561761550955470039347710377935430376540997666946732121050843943749113492456070208722584367960097193687068316198442251779996732370869956929154264599266558656998291277615472089316924824858509461968839560373847123720302209499188368577051388332118545647663499060310173238950445428065112782260341420786331573640423109123998871497386871255035519083533912545892193880065315348877403300582568486621407361500316149529826000301851854298225243004887134832995786317749406171558582924198304368104714986219031307479748428743032467140973874144668949035392372642311697440589918166525082655776297056665485571695194361213825860891281700257622160134188573315004659315552037023455156224112852855409552840560676809610659364534019843716667528320861783790470135132252554982383619409605735871723653872520775339489691485931713460644595140144475541409110588163364087551232836845830695547942152717257411567456719330540589809245218577244740006501921237942942980048354207356160078766172344092111288725170335319059624965937528663770449851973907751821832807806710093378320693505177121340730148723514950098690167524202989360541323245921023712916359374264868785960322720992841045219491441258977478191633883101659664952558559890504542073571801431776968543704035110053798922220934303778138273796175051852086764381745916258811466762800228917051789980861215214110270112810676814448667666622881573987963562421467262340458228385390137062072117607392144233167549189338542911152122326131564270571951824330981320390251178659227103409903462908177618859496883996022086618151413387922496226020834832000435293311545836968817174960974554958641764592099317232132440571203361067722618432317333812093571411518830967650039083020361949205886346500505209625560095589292128134040248924147768646398380221600316417996467494738746240515369738597650550643224119719859169933271233241959823693162829637976197165888346458437550155272395416291897833016122231541469065710823605995442926514293382634458536961006463289728594201669361194439648100945209827862279811799813211413503525576732302378722657592510104549090328279105443524322387013695071352172679442875491231145716131930393958537791854516227526179805844009589282698305553311603350517820995619933442794338209627401838613777569367277825872282687338574041903378763032504830682120391233213019239401536078368227667105268046428945388324198665577862162939515210304941047747131980736334697983545992150550483058764380358672809089583994352027990302433223468218272942526288927224660893230101392979028791798923047281230076759595046089710852198844678555075016935113924246881411054205395873201643255007252524101848154191656751134394562040078429038874684394864165800041945954128450386498789711839552110158033775820326726696895694444824175554545416453427272467970500439142838263451322791436206319391022945898775187452690856229596059532538096492103992089141148980184923790665880258460255814176702857908809079368454186467838961467463367948705004910810484015543002950663849920107375429206414117615994720974584272336425666056012634457940472187657159628497035931562062277635574409590858720565133874813343018541142778457545461343091040324809674292368999233303761234545925629119860478916774596177368756849900209836092880855491180978524057178665546279461763244404189523602482465527662567808169703839678446654285688821806998423790778351697878381774169631669505831979262584501783255045751641082958247283869797326695448401240398861153139228714544447696625149028399403582714196960936217794301993212368458364685960576424164080130668851338627306568903034504349586104366805302081902831167514640912745465362577840480295014653947206213581923689083204499895008744949471095489440568542207856932779163387582289262425702844010854907799401907959086234037560184585685513241542484149047630303827710694363984617654960015307719666225345427857424149507260802591920812678233057184075571911854539102884384233194396378294407359820061345464282290169740777855878700603368229883879629909895774350291565310082223898915298733864529390684101379483013062935310860932248077180573959027033718944603047823482493207539487482564533872424243380394642545734571846936068613874419235288291187101317841734454881191454595011780749360339888931938820268784950107123800030621105129518176882498551427801867324227159446727318005369930920694377941987614658412361051272355796722321397730230779294957465243376341434536845453232579111939395985759870898968279742060400763675580917610573104332744231982019035028369780303515703867195320309944175002832926892800275433515654444805092971792743290610712954008895049057102958227464662484396125638223702229814513008454161115942669470132149115826437653522470497173102118838260093219245401612513201441267291084993212938558285478905479046792233712576425237479079197429515191056487176745443497467691778133961714729688587712165624129676729576570905085492152418319061737271528282976028789381482191758666521379039819367382141176877902706384647751538557745493990434676529424318689004229666179557066049011876123844930960296342777999617976769672635984900993327653259546583986381364068217634286532889765898322297790163621189996973760491216039220479852981375991820326232590759252508943003339103070714717459192792672989773231339953865355665508062981068871753224648457468557819898380515327944725380577278449019511958457865058469672403950435871167218783156782484537017799293863327702767796143165444687055465482862330105176790326865725700879584313510791249424118877397134360682473598786938748010839376715073023074893917118881120654032011649512145697592403333548573681850960351751193740486769009950133949455822346983568530834550617904045552341808006789437594659775831055922498440389519462893013307719117756129189098279085658095013641688263745541518655942735647434019473305765841620643230183828614905217941883454955574035830283548543451456909212700894902241218275160436461190289254830716962236128763408477022597696078200885956015872040105387744596642941431224556689432766010132540275701527579848917606858621974410673557394323517965317099026879944593674565359699102789774694362883165544413248841952437969560242033517214854124146887407254565678915989180073905916443111256553722624347496922628028480403662465631436917694999112518599236006265027513605839342814912229240681187177902995948084208937564623505089843098818685457016500228527037091391164346982742625712904280550471616197102059000746561684849177005709982245837231806640940701723270900400034385009648082733488552015974395607267484059599012218050435707179544938269446898991153290634777503426156133878591289270619713800396007442664292364379950754618785664272631509896220695700222633688247997925113370013804095882607868794544921618399225526673837323889121391250993107546634757514401470331814497092467947711764791180812723593045579822970614293896655905007140742331901666793723782652030382086694097190923163693948549882285208516579217458096364104527227389663442196948609946993106829629678946484292984265997218754258225147166523227284357822330819822224677587479443145867835705614319430105498187761402160051803821550522135433354340367214968052432666700922283473745615661257598619805569276595832284470304281507206492798942275432776961188051665384388026363986255185946919916768939608268745594964688892345465273645680776543139572294731286501461822563478577543023120861166714746498190225989869858347863887281043735118235003776183330649705509079285240514092968541587215790495249592693663410956613037617532801232210108574834787758110483327345915465576858107637360497765807218840581204603666335397031758974904189472990660550393055625605985095188900969960157800922648642424443778664001807591917116733209071943431409730665983200770169758993247450498839017673704238099525961077154920719428282557502302114664847939081457526046025481362828381873140323770854667146124368724978965797111143037672495456280580996220124324010846685981167357330188413491703661957280653261854218418188005672654118955220217140867053999319384324547602049458313183012018574616336926475332034238745259086697473260663716534842427251640903501688675530366433859978985338176795153382001049672949827300979362686699010776464392025802116333538138574156476321196800183942623758426867746055516191769771926625827511351558994151671521686487645296461330533334766606618819665656925175025788499535075784648151602741779329053246473934593300853910696552890200242805672156366887706797892670252301135317180789975616380523864383293767640689669327646961480870910738027419852498212035126025862147990860120147861547463335478002183775527998007232180566162525895627465857411541016779071800566601057139193875496388178685825610209175759249213236507580513902130343079886499338047656077230576213308687365173392002543931803096844488099164247275205687397475633579087240333361374454225225271653797093232543599437201151939510720218728349555599739356494144853578966792409117272527272768862514771592512064469339498740613444016150567969563163825631170803477351379334827170853991838143968700933274688679221490704041797663265405769254196921399285517997593905395166262394927182990628701218515558696743963963260684442547523665643335021248839000520053767939009518342865246919838059404752517773008086273696590751567799514070775336303437349223521341461778078693924098215743892120253196245090693897268293302465327750493823238491852351349177097306237015251111236360740317870909141674349338506045814755999295159339984612262558599647888498510273988701174629492700379884203069937528361228611271223246613853103810576953162282316434573611855286154570009598629230542684615667511758640888780219082213847005016439021337884973790281379043241430560881363283009921880657807907369122860176061278642861345425813400326239897904029033112939443858583264606430912619451403767060456446625030209210929076598330120371184473978240690920631836621258314025432176810688471902017673135483331514196867449788594423841568724677789247525283839104204823838319505324609854765626329392502051554754164850386386059614243708935207484357137373220314082144033677979530053980897849293353642962364199395123030724053937439868545871790886428054011710355298592675175736134443964514029998974883932959405705974961577187328189252811305352363050485976907501255765456698820471508284004171365702379957315057311447916326368292428176649561041660080254557882524979099877170839522095636052612161960778091362340845009006330088759619844779302632190894172487895554136165085747556737508374073732047604766331584668922985429774934564462761361745594592357911338831300130974649979644785021080628784696271896630113347286166046299152669993963374869743359964126529371273949915249652265738875319842058547881671391689124080377904377674740006992175890748629448784257140664182473364986102007386018593115742084161433947813607132651567755148301280461829088744420462977402839598400769703851503614352695373437899333457680505663520973225339418189288170285659490460954601996013887411967815742532054997486309388443871121550043071659755539203529182177598118883403971291567778666654975893816488121467450048153478838740292986690123535596910791802366807400439570678512183597837789843405612471789458114785105950641243321284794097807889338574145309250393044072457898556623011954061022046938808407334046149819324878687598649907894801816149505152654918626335442427055079594606133479310076335951352506804239694884233283069798541887170963173479529025326638272842479197028928297113370655999095248437459983834804667984365782984717560734423015598844917141990878908670781640870569464879003434297571643035505938324102538500941840177351488611471503586104068469867766723264327006290126882633682693836641127588813804750940224420973153218967163493676661392203493971965252435160504445908919991975360021240084727604566326556245945415394319863159153179483895277585244652311276961929542893678463288884533915935681777927378784888224691377818862623834346071650866384410932642138242772625613137853455310959065369170163115290376958985905857343379268052837472128519183420932423433905363200496644974745804919779889930665871901458701292828630397737934621451369203283075795162294701799266076797338442035032897729789778678203999562267964515209769841731596997653887251023544932522565137508006344719380646199536021380711055791079777688726377276680309027290939382259858024805643148726777938894383150666540235309775137140100476669739371638147455134924659555214980208874554101944454568578987902922593556416670724980023692739882493103348935365992532590198498084732878637799108295577068249180442218951460360799595789173734750718027897673412547174901332414431458109547572272388569544058979503204283297311350656036296735739812128577773739474691991779208798812210500325598291182444051405283733381781972355087093350495522123208429149001658018113101979997377875019888939580635008948929606987595262372832178690097507637074108980096618339885374538496763299492472627832696789142579765305921426425642833599065201701568007431502957535701837870552495919859217913820897808582644770464727576585119709446728304083004528053670906054933419448098422895556264783884333032147153735498347527308617659544378655057106332288218807914741624233713160723947560004533406924146713672323270986580666958410204059518115810442979308657880369406306762612097917830192409606904001182937553164290522535485804280939937615594455860001916285840982140023392775138976373879151281945140021950744792288935903950531816650502734166971716860427120958748185606948055933907159345339039683300420441384135908968822644772937874288465561875435897663923625182163794865360428835740895149512024538377831285812693623680502353049694883113062676241090575957364240661097518999678869148564488112997725546248768884385536141191442041470300934724664088068807277281657616185485566807284428048984736063187494098627893175577422340427481150491367018532125590012124946006882071224501569130293122566891605442157859373386275298776085824203692473663648856701385786741919563041435472210700714458423473258474990601310464889871616250115995988040471563129659850470288843970510299503533852107234696933412908850652828367410144014518740288311113095677547412505126442080263940213742653747533988118162899734794200231189889445326923127246701400294234025965694107739957495114780965153738071015979405519562536791533720539773506545701446159521485475088670649361622020324451542350759432746222707438427511863171761479284167482610658840151970339366126350093442726387419202088928591989634920323155842380498872236918172155415135727030354720719480929741568175424486212929329551403229853586121888690250012313380654487275794640114792767882923828598106365924409789815455523568671490588753183725879882354092533673363521102701378717077889467251654275674877744015656870885101395227102689723396460584002893906145606152099533020354772688170456275232823872732933774357489816108347864077683975222395752648355873628269197941098593925731403746627250024635831130775689035005164707050043939075339948313413676648187981127538669245960058629314954794378454631958217270318813279523153653242030568034871925664313065436765234073066817593458633419477588676932562492048888626554983679058764284159160281424990636665848123109007273809641906372235706539997582112554631524947416973631595010776664583992495485898324851421595889625729059421067790880429764038363168490266946319612178775102501675603028578275345318111786701337634767666922729828998876908319431421903041812356951572618221225808415494734697551887238357288866039962815887227161144974284190210999126188567881518665418346747550733629508276384834719373831371887078362035482357128563201521326399474695244604583553604380553302754436655492925489858720437108422063734347346166676768087312130712707416835356465185214427471852469097192433748367461238451652519871948392787756847833485850303330505408500487101162892326722959480940567990907260189073234966149979117264065369152956364961871573083079495900765691245633843309804461132196993556795909196276635584943158991561338370539812857587099819106825063515547931394570815057357014025601231455258339056291242642886384956999632122458832254110550816561504034005054447309674619259945145981133089019918864903542821056112039980768464584185110964940951509395378535009487218904831656806459296183140217995181055502001203128588360180384130135256829495536347567678679798604929461639269037443885083232991246861499107852284103426767922633935910637421262429942293812196077267023985693893276864390489651555230517310615760058789572528548516133401669434409394493581343054233862572692597767811967994748608272190612912449722146351592941093493674221853396602268558354381716161458331916917977329330648464172174020593637176483579796001860081538091951334345355525105273368184483491463398138819443286513632242560550323352374327257491634307553366961856047677831647836614597175600841149031550684741205229568

問題 2.6

置き換えモデルでzeroに1を足すとどうなるのか確認。

(add-1 zero)

(lambda (f) 
  (lambda (x) 
    (f ((zero f) x))))

(lambda (f)
  (lambda (x)
    (f (((lambda (x)
           (lambda (x) x)) f) x))))

(lambda (f)
  (lambda (x)
    (f ((lambda (f) f) x))))

(lambda (f)
  (lambda (x) (f x)))

となったので、1足すごとに、

(lambda (f)
  (lambda (x) (f (f x))))

(lambda (f)
  (lambda (x) (f (f (f x)))))

ってなるっぽい。

このことからone、two、加算手続き+を直接定義。

コード

sample.scm

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))

(define two (lambda (f) (lambda (x) (f (f x)))))

(define (+ a b)
  (lambda (f) (lambda (x) ((b f) ((a f) x)))))

oneとtwoの加算の評価がthree、(lambda (f) (lambda (x) (f (f (f x)))))になるかどうかを置き換えモデルで確認。

(+ one two)

(lambda (f)
  (lambda (x) 
    ((two f) ((one f) x))))

(lambda (f)
  (lambda (x) 
    (((lambda (f) (lambda (x) (f (f x)))) f) (((lambda (f) (lambda (x) (f x))) f) x))))

(lambda (f)
  (lambda (x)
    ((lambda (x) (f (f x))) ((lambda (x) (f x)) x))))

(lambda (f)
  (lambda (x)
    ((lambda (x) (f (f x))) (f x))))

(lambda (f)
  (lambda (x) (f (f (f x)))))

ということで、threeになった。

ちょっと修正して+加算演算子をaddとし、元の加算演算子+(数値の足し算)を使えるようにして、普通の数値を使ってREPLで確認。

コード

sample.scm

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))

(define two (lambda (f) (lambda (x) (f (f x)))))

(define (add a b)
  (lambda (f) (lambda (x) ((b f) ((a f) x)))))

(define (f n) (+ n 1))

(define a ((zero f) 0))
(define b ((one f) 0))
(define c ((two f) 0))
(define d (((add one two) f) 0))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> a

;Value: 0

1 ]=> b

;Value: 1

1 ]=> c

;Value: 2

1 ]=> d

;Value: 3

結果は期待した通りだったから合ってるっぽい。