Atodiad: Scheme

Dylid cynllunio ieithoedd rhaglennu drwy ddileu'r gwendidau a'r cyfyngiadau sy'n gwneud i nodweddion ychwanegol ymddangos yn angenrheidiol, yn hytrach na phentyrru nodwedd ar ben nodwedd. Mae Scheme yn dangos bod nifer fach iawn o reolau ar gyfer ffurfio mynegiadau, heb gyfyngiadau ar sut y cânt eu cyfansoddi, yn ddigon i ffurfio iaith raglennu ymarferol ac effeithlon sy'n ddigon hyblyg i gefnogi'r rhan fwyaf o'r prif baradeimau rhaglennu a ddefnyddir heddiw.

IEEE Standard for the Scheme Programming Language [24], t. 3

Yma rhoddwn gyflwyniad elfennol i Scheme.¹ Am esboniad mwy manwl gywir o'r iaith gweler safon IEEE [24]; am gyflwyniad hwy gweler y gwerslyfr [1].

Mae Scheme yn iaith raglennu syml sy'n seiliedig ar fynegiadau. Mae mynegiad yn enwi gwerth. Er enghraifft, mae'r rhifolyn 3.14 yn enwi brasamcan o rif cyfarwydd. Ceir mynegiadau cyntefig, megis rhifolion, a adnabyddwn yn uniongyrchol, a cheir mynegiadau cyfansawdd o sawl math.

Galwadau gweithdrefn

Math o fynegiad cyfansawdd yw galwad gweithdrefn. Mae galwad gweithdrefn yn ddilyniant o fynegiadau wedi'i amgáu mewn cromfachau crwn. Cymerir bod yr isfynegiad cyntaf mewn galwad gweithdrefn yn enwi gweithdrefn, a bod gweddill yr isfynegiadau yn enwi'r argiau i'r weithdrefn honno. Y gwerth a gynhyrchir gan y weithdrefn wrth ei chymhwyso i'r argiau a roddir yw'r gwerth a enwir gan yr alwad gweithdrefn. Er enghraifft,

(+ 1 2.14)

3.14

(+ 1 (* 2 1.07))

3.14

mae'r ddau yn fynegiadau cyfansawdd sy'n enwi'r un rhif â'r rhifolyn 3.14.² Yn yr achosion hyn mae'r symbolau + a _* yn enwi gweithdrefnau sy'n adio ac yn lluosi, yn ôl eu trefn. Os rhoddwn, yn lle unrhyw isfynegiad mewn unrhyw fynegiad, fynegiad sy'n enwi'r un peth â'r isfynegiad gwreiddiol, mae'r peth a enwir gan y mynegiad cyfan yn aros heb newid. Yn gyffredinol, ysgrifennir galwad gweithdrefn

( operator operand-1 … operand-n )

lle mae operator yn enwi gweithdrefn ac operand-i yn enwi'r arg rhif i.³

Mynegiadau lambda

Yn union fel y defnyddiwn rifolion i enwi rhifau, defnyddiwn fynegiadau λ i enwi gweithdrefnau.⁴ Er enghraifft, gellir ysgrifennu'r weithdrefn sy'n sgwario ei mewnbwn:

(lambda (x) (* x x))

Gellir darllen y mynegiad hwn: “Y weithdrefn ag un arg, x, sy'n lluosi x ag x.” Wrth gwrs, gallwn ddefnyddio'r mynegiad hwn mewn unrhyw gyd-destun lle mae angen gweithdrefn. Er enghraifft,

((lambda (x) (* x x)) 4)

16

Ffurf gyffredinol mynegiad λ yw

(lambda formal-parameters body)

lle mae formal-parameters yn rhestr o symbolau a fydd yn enwau argiau'r weithdrefn ac mae body yn fynegiad a all gyfeirio at y paramedrau ffurfiol. Gwerth galwad gweithdrefn yw gwerth corff y weithdrefn gyda'r argiau wedi'u hamnewid am y paramedrau ffurfiol.

Diffiniadau

Gallwn ddefnyddio'r lluniad define i roi enw i unrhyw wrthrych. Er enghraifft, os gwnawn y diffiniadau⁵

(define pi 3.141592653589793)

(define square (lambda (x) (* x x)))

gallwn wedyn ddefnyddio'r symbolau pi a square lle bynnag y gallai'r rhifolyn neu'r mynegiad λ ymddangos. Er enghraifft, arwynebedd arwyneb sffêr â radiws 5 yw

(* 4 pi (square 5))

314.1592653589793

Gellir mynegi diffiniadau gweithdrefn yn fwy cyfleus drwy ddefnyddio “siwgr cystrawennol.” Gellir diffinio'r weithdrefn sgwario

(define (square x) (* x x))

a gallwn ddarllen hwn: “I sgwario x, lluoswch x ag x.”

Yn Scheme, gellir trosglwyddo gweithdrefnau fel argiau a'u dychwelyd fel gwerthoedd. Er enghraifft, mae'n bosibl gwneud gweithdrefn sy'n gweithredu'r syniad mathemategol o gyfansoddi dau ffwythiant:⁶

(define compose
  (lambda (f g)
    (lambda (x)
      (f (g x)))))

((compose square sin) 2)

.826821810431806

(square (sin 2))

.826821810431806

Gan ddefnyddio'r siwgr cystrawennol a ddangosir uchod, gallwn ysgrifennu'r diffiniad yn fwy cyfleus. Mae'r ddau ganlynol yn gyfwerth â'r diffiniad uchod:

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define ((compose f g) x)
  (f (g x)))

Mynegiadau amodol

Gellir defnyddio mynegiadau amodol i ddewis ymhlith sawl mynegiad i gynhyrchu gwerth. Er enghraifft, gellir ysgrifennu gweithdrefn sy'n gweithredu'r ffwythiant gwerth absoliwt:

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) x)
        ((> x 0) x)))

Mae'r lluniad amodol cond yn cymryd nifer o gymalau. Mae gan bob cymal fynegiad traethol, a all fod yn wir neu'n anwir, a mynegiad canlyniad. Gwerth y mynegiad cond yw gwerth mynegiad canlyniad y cymal cyntaf y mae'r mynegiad traethol cyfatebol yn wir ar ei gyfer. Ffurf gyffredinol mynegiad amodol yw

(cond
  (predicate-1 consequent-1)
  ...
  (predicate-n consequent-n))

Er cyfleustra ceir mynegiad traethol arbennig else y gellir ei ddefnyddio fel y traethiad yng nghymal olaf cond.

Mae'r lluniad if yn darparu ffordd arall o wneud mynegiad amodol pan nad oes ond dewis deuaidd i'w wneud. Er enghraifft, gan nad oes rhaid inni wneud rhywbeth arbennig ond pan fo'r arg yn negatif, gallem fod wedi diffinio abs fel:

(define (abs x)
  (if (< x 0)
    (- x)
    x))

Ffurf gyffredinol mynegiad if yw

(if predicate consequent alternative)

Os yw predicate yn wir, gwerth y mynegiad if yw gwerth consequent; fel arall, gwerth alternative ydyw.

Gweithdrefnau dychweliadol

Gyda mynegiadau amodol a diffiniadau, gallwn ysgrifennu gweithdrefnau dychweliadol. Er enghraifft, i gyfrifo'r rhif ffactoraidd rhif n gallwn ysgrifennu:

(define (factorial n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

(factorial 6)

720

(factorial 40)

815915283247897734345611269596115894272000000000

Enwau lleol

Defnyddir y mynegiad let i roi enwau i wrthrychau mewn cyd-destun lleol. Er enghraifft,

(define (f radius)
  (let ((area (* 4 pi (square radius)))
        (volume (* 4/3 pi (cube radius))))
    (/ volume area)))

(f 3)

1

Ffurf gyffredinol mynegiad let yw

(let ((variable-1 expression-1)
      ...
      (variable-n expression-n))
  body)

Gwerth y mynegiad let yw gwerth y mynegiad body yn y cyd-destun lle mae gan y newidynnau variable-i werthoedd y mynegiadau expression-i. Ni chaiff y mynegiadau expression-i gyfeirio at unrhyw un o'r newidynnau variable-j y rhoddir gwerthoedd iddynt yn y mynegiad let.

Mae mynegiad let_* yr un fath â mynegiad let heblaw y gall mynegiad expression-i gyfeirio at newidynnau variable-j y rhoddwyd gwerthoedd iddynt yn gynharach yn y mynegiad let_*.

Mae amrywiad bach ar y mynegiad let yn darparu ffordd gyfleus o fynegi lluniadau dolennu. Gallwn ysgrifennu gweithdrefn sy'n gweithredu algorithm amgen i gyfrifo rhifau ffactoraidd fel a ganlyn:

(define (factorial n)
  (let factlp ((count 1) (answer 1))
    (if (> count n)
      answer
      (factlp (+ count 1) (* count answer)))))

(factorial 6)

720

Yma, diffinnir y symbol factlp sy'n dilyn y let yn lleol fel gweithdrefn sydd â'r newidynnau count a answer yn baramedrau ffurfiol. Fe'i gelwir y tro cyntaf â'r mynegiadau 1 ac 1, gan gychwyn y ddolen. Pryd bynnag y gelwir y weithdrefn o'r enw factlp wedyn, mae'r newidynnau hyn yn cael gwerthoedd newydd sef gwerthoedd y mynegiadau operand (+ count 1) a (_* count answer).

Data cyfansawdd—rhestrau a fectorau

Gellir gludo data at ei gilydd i ffurfio strwythurau data cyfansawdd. Mae rhestr yn strwythur data lle mae'r elfennau wedi'u cysylltu'n ddilyniannol. Mae fector Scheme yn strwythur data lle mae'r elfennau wedi'u pacio mewn arae linol. Gellir ychwanegu elfennau newydd at restrau, ond mae cyrchu elfen rhif n rhestr yn cymryd amser cyfrifo sy'n gyfrannol i n. Mewn cyferbyniad, mae hyd fector Scheme yn sefydlog, a gellir cyrchu ei elfennau mewn amser cyson. Gweithredir pob strwythur data yn y llyfr hwn fel cyfuniadau o restrau a fectorau Scheme. Llunnir gwrthrychau data cyfansawdd o gydrannau gan weithdrefnau a elwir yn adeiladwyr, a chyrchir y cydrannau gan ddetholwyr.

Y weithdrefn list yw'r adeiladydd ar gyfer rhestrau. Mae'r detholwr list-ref yn cael elfen o'r rhestr. Mae pob detholwr yn Scheme yn dechrau cyfrif o sero. Er enghraifft,

(define a-list (list 6 946 8 356 12 620))

a-list

(6 946 8 356 12 620)

(list-ref a-list 3)

356

(list-ref a-list 0)

6

Adeiledir rhestrau o barau. Gwneir pâr gan ddefnyddio'r adeiladydd cons. Y detholwyr ar gyfer dwy gydran y pâr yw car a cdr (yngenir “could-er”).⁷ Mae rhestr yn gadwyn o barau, fel bod car pob pâr yn elfen y rhestr ac cdr pob pâr yn bâr nesaf, heblaw'r cdr olaf, sy'n werth gwahaniaethadwy a elwir yn rhestr wag ac a ysgrifennir (). Felly,

(car a-list)

6

(cdr a-list)

(946 8 356 12 620)

(car (cdr a-list))

946

(define another-list
(cons 32 (cdr a-list)))

another-list

(32 946 8 356 12 620)

(car (cdr another-list))

946

Mae a-list a another-list ill dau yn rhannu'r un gynffon (eu cdr).

Ceir traethiad pair? sy'n wir am barau ac yn anwir am bob math arall o ddata.

Mae fectorau yn symlach na rhestrau. Ceir adeiladydd vector y gellir ei ddefnyddio i wneud fectorau a detholwr vector-ref i gyrchu elfennau fector:

(define a-vector
(vector 37 63 49 21 88 56))

a-vector

#(37 63 49 21 88 56)

(vector-ref a-vector 3)

21

(vector-ref a-vector 0)

37

Sylwch fod fector yn cael ei wahaniaethu oddi wrth restr mewn allbrint gan y nod # sy'n ymddangos cyn y gromfach gron gyntaf.

Ceir traethiad vector? sy'n wir am fectorau ac yn anwir am bob math arall o ddata.

Gall elfennau rhestrau a fectorau fod yn unrhyw fath o ddata, gan gynnwys rhifau, gweithdrefnau, rhestrau, a fectorau. Gellir dod o hyd i nifer o weithdrefnau eraill ar gyfer trin data â strwythur rhestr a data â strwythur fector yn nogfennaeth ar-lein Scheme.

Symbolau

Mae symbolau yn fath pwysig iawn o ddata cyntefig a ddefnyddiwn i wneud rhaglenni a mynegiadau algebraidd. Mae'n debyg eich bod wedi sylwi bod rhaglenni Scheme yn edrych yn union fel rhestrau. Mewn gwirionedd, rhestrau ydynt. Mae rhai o elfennau'r rhestrau sy'n ffurfio rhaglenni yn symbolau, megis + a vector.⁸ Os ydym am wneud rhaglenni sy'n gallu trin rhaglenni, mae angen inni allu ysgrifennu mynegiad sy'n enwi symbol o'r fath. Cyflawnir hyn drwy fecanwaith dyfynnu. Enw'r symbol + yw'r mynegiad '+, ac yn gyffredinol enw mynegiad yw'r mynegiad â nod dyfyniad sengl o'i flaen. Felly enw'r mynegiad (+ 3 a) yw '(+ 3 a).

Gallwn brofi a yw dau symbol yn unfath drwy ddefnyddio'r traethiad eq?. Er enghraifft, gallwn ysgrifennu rhaglen i benderfynu a yw mynegiad yn swm:

(define (sum? expression)
  (and (pair? expression)
       (eq? (car expression) '+)))

(sum? '(+ 3 a))

#t

(sum? '(* 3 a))

#f

Yma #t a #f yw cynrychioliadau printiedig y gwerthoedd Boole gwir ac anwir.

Ystyriwch beth fyddai'n digwydd pe baem yn hepgor y dyfyniad yn y mynegiad (sum? '(+ 3 a)). Pe bai gan y newidyn a y gwerth 4 byddem yn gofyn a yw 7 yn swm. Ond yr hyn yr oeddem am ei wybod oedd a yw'r mynegiad (+ 3 a) yn swm. Dyna pam mae angen y dyfyniad arnom.

Effeithiau

Weithiau mae angen cyflawni rhyw weithred, megis plotio pwynt neu brintio gwerth, yn ystod cyfrifiad. Gelwir gweithred o'r fath yn effaith.⁹ Er enghraifft, i weld yn fwy manwl sut mae'r rhaglen ffactoraidd yn cyfrifo ei hateb gallwn fewnosod datganiad write-line yng nghorff y weithdrefn fewnol factlp. Bydd hyn yn argraffu rhestr o'r cyfrif a'r ateb ar gyfer pob iteriad:

(define (factorial n)
  (let factlp ((count 1) (answer 1))
    (write-line (list count answer))
    (if (> count n)
      answer
      (factlp (+ count 1) (* count answer)))))

Pan weithredwn y weithdrefn factorial wedi'i haddasu gallwn wylio'r rhifydd yn cynyddu a'r ateb yn cael ei adeiladu:

(factorial 6)

(1 1)
(2 1)
(3 2)
(4 6)
(5 24)
(6 120)
(7 720)
720

Mae corff pob gweithdrefn neu let, yn ogystal â rhan ganlyniad pob cymal cond, yn caniatáu defnyddio datganiadau sydd ag effeithiau. Fel arfer nid oes gan y datganiad effaith werth defnyddiol. Y mynegiad olaf yn y corff neu'r cymal sy'n cynhyrchu'r gwerth a ddychwelir. Yn yr enghraifft hon mae'r mynegiad if yn cynhyrchu gwerth yr factorial.

Aseiniadau

Mae effeithiau fel printio gwerth neu blotio pwynt yn weddol ddiniwed, ond ceir effeithiau mwy pwerus (ac felly mwy peryglus), a elwir yn aseiniadau. Mae aseiniad yn newid gwerth newidyn neu gofnod mewn strwythur data. Ffwythiannau mathemategol yw bron popeth yr ydym yn ei gyfrifo: ar gyfer mewnbwn penodol maent bob amser yn cynhyrchu'r un canlyniad. Fodd bynnag, gydag aseinio gallwn wneud gwrthrychau sy'n newid eu hymddygiad wrth eu defnyddio. Er enghraifft, gallwn wneud dyfais sy'n cyfrif bob tro y galwn arni:

(define (make-counter)
  (let ((count 0))
    (lambda ()
      (set! count (+ count 1))
      count)))

Gadewch inni wneud dau rifydd:

(define c1 (make-counter))
(define c2 (make-counter))

Mae gan y ddau rifydd hyn gyflyrau lleol annibynnol. Mae galw rhifydd yn peri iddo gynyddu ei newidyn cyflwr lleol, count, a dychwelyd ei werth.

(c1)

1

(c1)

2

(c2)

1

(c1)

3

(c2)

2

Mae aseinio i newidynnau weithiau'n ddefnyddiol. Er enghraifft, gall fod yn ddefnyddiol cronni rhai gwrthrychau mewn rhestr i'w dadansoddi ymhellach. Dyma ffordd gain o wneud hyn:

(define (make-collector)
  (let ((lst '()))
    (cons (lambda (new)
            (set! lst (cons new lst))
            new)
          (lambda () lst))))

Mae'r weithdrefn hon yn gwneud pâr o ddwy weithdrefn. Gweithdrefn sy'n ychwanegu at restr yw car y pâr, a gweithdrefn sy'n adrodd y rhestr a gasglwyd yw cdr y pâr.

Gadewch inni wneud dau gasglwr a chwarae gyda hwy:

(define c3 (make-collector))
(define c4 (make-collector))

((car c3) 42)

42

((car c4) 'jerry)

jerry

((car c3) 28)

28

((car c3) 14)

14

((car c4) 'jack)

jack

((cdr c3))

(14 28 42)

((cdr c4))

(jack jerry)

Mae hefyd yn bosibl aseinio i elfennau strwythur data, megis rhestr neu fector. Nid oes angen hyn yn ein gwaith felly ni fyddwn yn dweud wrthych sut i'w wneud! Yn gyffredinol, mae'n arfer da osgoi aseiniadau lle bynnag y bo modd, ond os oes eu hangen arnoch maent ar gael.¹⁰

¹Mae llawer o'r gosodiadau yma yn ddilys dim ond os tybir na ddefnyddir aseiniadau.

²Yn yr enghreifftiau dangoswn y gwerth a fyddai'n cael ei brintio gan system Scheme gan ddefnyddio nodau ar ogwydd ar ôl y mynegiad mewnbwn.

³Yn Scheme mae pob cromfach gron yn hanfodol: ni allwch ychwanegu cromfachau ychwanegol na thynnu unrhyw rai.

⁴Dyfeisiodd y rhesymegydd Alonzo Church [13] nodiant λ er mwyn gallu pennu ffwythiant dienw o baramedr a enwir: λx[mynegiad yn x]. Darllenir hwn, “Y ffwythiant hwnnw ag un arg a geir drwy amnewid yr arg am x yn y mynegiad a nodir.”

⁵Nid y diffiniad o square yn system Scmutils yw'r diffiniad o square a roddir yma. Yn Scmutils, estynnir square ar gyfer twpledi i olygu swm sgwariau cydrannau'r twpled. Fodd bynnag, ar gyfer argiau nad ydynt yn dwpledi mae square Scmutils yn lluosi'r arg ag ef ei hun.

⁶Mae'r enghreifftiau wedi'u mewnoli i'w gwneud yn haws i'w darllen. Nid yw Scheme yn poeni am ofod gwyn ychwanegol, felly gallwn ychwanegu cymaint ag y dymunwn i wneud pethau'n haws i'w darllen.

⁷Damweiniau hanes yw'r enwau hyn. Maent yn sefyll am “Contents of the Address part of Register” a “Contents of the Decrement part of Register” cyfrifiadur IBM 704, sef cynnwys rhan gyfeiriad a rhan ostyngiad y gofrestr; defnyddiwyd y cyfrifiadur hwn ar gyfer gweithrediad cyntaf Lisp ar ddiwedd y 1950au. Mae Scheme yn dafodiaith o Lisp.

⁸Gall symbolau gynnwys unrhyw nifer o nodau. Ni chaiff symbol gynnwys gofod gwyn na nod amffinydd, megis cromfachau crwn, cromfachau sgwâr, dyfynodau, coma, neu #.

⁹Jargon cyfrifiadureg yw hwn: newid i rywbeth yw effaith. Er enghraifft, mae write-line yn newid yr arddangosfa drwy brintio rhywbeth arni.

¹⁰Gelwir disgyblaeth rhaglennu heb aseiniadau yn rhaglennu ffwythiannol. Mae rhaglenni ffwythiannol yn gyffredinol yn haws eu deall, ac mae ganddynt lai o wallau na rhaglenni gorchmynnol.