[PDF] Les fonctions en Coq Coq. ? Les fonctions décrivent

View - Download Les fonctions en Coq

Previous PDF

Next PDF

Lesfonc tionsenCoq

YvesBerto t

Lesfonc tions:outilprincipalenCoq

Lesfonctionssont lesunités debase delap rogra mmationen Coq Lesfonctionsdécr iventles opérationsàe!ectuerda nsun langagemathématique Lesfoncti onspermettentdes'adapteràde sdonnées di!érentesenutilisantdes var iables Lesfonctionsp euvent elles-mêmesêtreutiliséescommedes données

Construiredesfonctionssimples

Ondéfinit unefonctionenfournissantune expression bien forméeetunevar iablesp éciale

Utilisezfunet=>pourindiquer lavariablespéciale

Exemple:lafonctionquiajoute 2àson entrée

Checkfunx =>x +2.

Lesystèm erépond

funx: nat=> x+2 :nat-> nat

Letexte":nat->nat"in diquequec'estunefonc tionqui

prendenentréeunn ombree tretourneunnomb re Coqmodifiel 'expressionpour ajouteruntypeàlavariablex

Lesfonctionssont anonymes

Commel'expressi on2+3,l' expressionfunx=> x+2 n'a

pasdenom

Pourdonneru nnomàunefonctionilf aututi liserla

commandeDefinition

Appliquerlesfonct ions

Onutil iseunefonctionenl'app liquantàu nevaleur Ilsu !td' écrirelafonctionsurlagau chedel avaleur onn'aj outedesparenthèsesquep ouréviterle sambiguités, autourdelafoncti on,oua utourde l'argument Exemple:appliquerlafonction quiajoute2 aunombre 4,

Evalvm_computein (funx =>x+ 2)4.

Lesystèm erépond6:nat

Quandlafonction estunnom, onpeut sepasserde

parenthèses

Exemple:Definitionadd2 :=funx=>x+ 2.

Checkadd24 .

Lesystèm erépondadd24: nat

Lesfonc tionssontdesvaleurs

Lesfonctionsp euvent retournerdesfonctionscommerésultat C'estlareprésen tationus uelledesfonctionsàplusieurs arguments

Coqfourni tunenotationabrégée

Exemple:unefonctionavec deuxentrées

Checkfunx =>funy =>y+ (x+2).

Lesystèm erépond

funxy :nat=> y+(x +2): nat->nat ->nat Quandonl'appliq ueàuns eulargumentcelaretourneune fonction Lanouve llefonctionpeutàsontou rêtreappliquéeàunautre argument

Check(funx y=>y +(x +2))5.

Lesystèm erépond

(funxy :nat =>y+ (x+2)) 5:nat ->nat

Lesfonc tionspeuventêtredesargumen ts

Lesfoncti onsd'ordresupérieur

Checkfunf =>f (f0).

Lesystèm erépond

funf: nat->nat =>f(f 0) :(nat->nat)->nat

Ceciindiquequel'argume ntfestunefon ction

Exempled'utilisation

Evalvm_computein (funf=> f(f0))

((funx y=>y +(x+ 2))3).

Lesystèm erépond10:nat

Alpha-conversion

Dansunefonction lenomde lava riablespéciale peutchanger sanschangerle sensde lafonction funx=> x+ 2etfuny=> y+2 sontlamêmefo nction, Lechan gementdunomdevariableestappelé alpha-conversion

Bêta-réduction

Danslescalculs, lav ariablesp écialeestremplacée partoutpar l'argument

Evalvm_computein (funxf =>f(f x))2.

Lesystèm erépond

funf: nat->nat =>f(f 2) :(nat->nat)->nat Cetteétapeél émentairedec alculestappeléeBeta-réduction

Variablesliées,variablesl ibres

Lesvariabl estouchéesparlesdeuxproc édéssontdesvariables liées l'occurrenceentrefunet=>estl' occurenceliante Lorsqu'unevariabledansuneex pressionn'estpasliée,ell edoit avoirétédé finiepar ailleurs

Utilisationdevariables locale s

Laconstruction letv:= einF

Cetteconstruct ionpermetd'écrireuneseulefoise

Lava riablevauralam êmevaleu retlemêmetype queeet pourraêtreutilis éedansF

Evalcomputein letv: =3in v+v.

Lesystème répond

=6:nat

Lestype senCoq

YvesBertot

Lestype s:outilsprinci pau xcontrelesfautes

Lesty pessontdesensemblesdedonnées

Ilspermet tentd'observerlesprogrammesav ecmoinsdedétail Leserr eurslesplusgrossièressevoientr apidement Lavér ificationdestypespeutêtrefaite sansex écuterles programmes

Lestype s

Toutobjet auntype,

Toutefonctionat tendunargumentd'untypepr écis,

Mêmelorsquel 'onnedonnepasdetypeàl 'argumentd 'une fonction,lesy stèmeen calculeunourefuse,

Lacommande Checkpermetdetrouverlet yped'u ne

expression.

Quelquesexpressi onsetleurtype

Check1.

Lesystème répond:

1:nat

Check1+ 2.

Lesystème répond:

1+2:nat

Checkfunx =>1+ x.

Lesystème répond:

funx: nat=> 1+x :nat->nat

Check(funx =>1 +x)2.

Lesystème répond:

(funx :nat =>1+ x)2:nat

Quelqueserreursde type

Check1+ true.

Lesystème répond:Theterm"true" hastype"bool" whileitis expectedtohave type"nat".

Checkfunx =>x.

Lesystème répond:

Error:Cannotinfer thetypeof x.

Check12.

Lesystème répond:

Error:Illegal application(Non-functional

construction):

Theexpression"1" oftype "nat"cannotbe applied

totheterm "2":"nat"

Règlesdevérificationdes type s

Typagedesapplica tionsdef onctions

Siunef onctionfale typeA->B

Sil'on veutconstruire l'express ionfe

Alorsl'expressi onedoitavoirlet ypeA.

Typagedesabstrac tions

Sil'on veutconstruire l'express ionfunx: t=> M

Dansl'expre ssionM,xdoitavoirlet ypet

Sil'o nn'écritpa sletypet,Coq essaiededevinersavaleur

Polymorphisme

Lecompo rtementdecertainesfonctionsestcommunàtous lesty pes letf:= fun(A :Type) (x:A)=>xin (fnat 3,fbool true) Polymorphisme:fréquentdans leslangagescomme ML,

OCaml,Haskell,

EnCoq, lepolymorphi smees texplicite:l'argumentdetypeest ajoutéàlaf oncti on,

Notationliante:forall,

Notationpluslourde, compenséepa runmécanisme d'argumentsimplicites.

Argumentsimplicites

Lava leurdecertainsarguments peutêtr edevinéequandon connaîtletyped'autresa rgume nts

ExempleDefinitionid:= fun(A:Type)(x:A) =>x.

Checkid_ true.

Lesystèm erépond:idbooltrue :bool

Lesystèm epeutdevinerbool

ImplicitArgumentsid. permetd'utiliserce ttecapacité Onn'écritplus queidtrue,l' autreargumentestcac hé

Onpeut utiliserlepr éfixe@pourdésactiver .

Check@idbo ol.

Lesystèm erépond:id(A:=bool): bool->bool

Ordresupérie ur

Lanotation fun_ =>_permetdeconstru iredes fonctions, Desfonctionsp euvent produiredenouvellesfonctions, Desfonctionsp euventp rendredesfonctionsenargument, Unefonc tiondepremierordreestunefo nction quiprenden argumentunedonnée nombresnaturels,boolée ns,pairesdedonnées,etc. Unefonc tiondesecondordreprendenarg umentu nefonction dupr emierordre, Unefoncti ond'ordresupérieurprende nargumentunefonct ion d'ordrearbitraire,

EnCoql adistinct ionent relesordresn'existepas.

Notationspourl'ordresupé rieur

Onécritsouv entdesfonctions àunargumentquiretournent unefonctionà unar gument, Lespar enthèsesdanslesapplicationssontév itées(àdroite),

Lespar enthèsesdansletypage sontévitées,

Lesmotsclefs funnesontpa srép étés.

Lesstru cturesdedonnéesenCoq

YvesBerto t

Structuresdedonn ées

Pourprogrammerilfaut pouvoirdéfinirdenouvellesstructures dedonnées Ils'agi tderegrouperdes donné esoudedécriredesalternativ es Desopérations sontfourniespourdégrouper ettraiterles cas Larécu rsionpermetd'avoirdanslemêm etypedesobjetsde taillesdi !érentes

Regrouperdesdonnées

Untyp eprédéfinid ecouples,notationA*B

Notationpour lesdonnéeselles-mêmes(.,.)

Check(3,fu nx: nat=>x+3).

Lesystèm erépond

(3,funx =>x +3): nat*nat ->nat Besoind'uneconstruc tionpourobs erverl'intérieurd'uncouple

Observationparmotif,sy ntaxematch...with ...end

Evalcomputein

match(1, 3)with(a, b)=>a +bend.

Lesystèm erépond

=4:na t

Lecalcul fonctionneencomparant (a,b)aveclavale ur

observée(1,3) atombeenfacede 1 aalavaleur1danslecalcul dea+b

Définirsonp ropretype

Unmo t-clef:Inductive

Inductivet1: Type:=

ct1(xy :nat) (b:bool).

Cecidéfinitde uxnouveauxobjets: t1etct1

t1estuntype ct1estunefo nctionpour construiredesélémentsd et1 observationparmotif:

Checkfund :t1 =>

matchd withct1 uvw=>u+ vend.

Lesystèm erépond

fund: t1=> matchdwith ct1u vw=> u+v end:t1 ->nat L'observationparmotifpermetdeconnaî treletyped euetv

Structuresdedonn éesavecva riantes

Onpeut avoirplusieurscasdefi gure

Parexempleuncalculpeutretourner deuxentiersou une

chainedecara ctères

Inductivet2:= ct2n(xy :nat) |ct2s

(s:string) .

Toutedonnéede t2estsoit ct2nnoùnestentier

soitttct2ss oùsestunecha înedecara ctères

L'observationparmotifdevientuntraiteme ntparcas

Checkfunc :t2=>

matchcwith ctnn =>n+ n |ctss =>0 end. sicaété obtenu parctnlepre miercalculeste!ectué sicaété obtenu parctsledeuxi èmecalculeste!ectué

Terminologiesurlesstructuresdedon nées

Dansladéfi nitioninductive suivante:

Inductivet2:= ct2n(x y:nat) |ct2s

(s:string). Lesnouvelles fonctionsct2netct2ssontapp eléesdes constructeurs x,y,ssontdeschamps lesty pesnatetstringsontdes typ esdechamps

Structuresdedonn éesrécursives

Lesty pesdechampssonthabituellementdest ypes déjàdéfinis

Lety peencoursdedéfinitionestaussia utorisé

Exemple:

Inductivet3 :=ct3r(s:string)(r:t3) |ct3e.

Ceciindiqueque

ct3eale typet3 ct3r"a"(ct 3r"b" (ct3r"c"(ct3r"d"ct3e))) aussi Touslesél émentsdet3contiennentct3eprécédéd'uncertain nombred'utilisatio nsdect3r

Programmationrécursive

Pourobserver lecontenud'unélémentd'unt yperéc ursif Uneconstr uctionquivas'adapteraunnombredefoiso ùle typeestut ilisédefa çonimbriquée

Formegénéral e:Fixpointf(x :t) :t':= B.

Lety pet'estlet ype deretourdelafonction

Lafonctionfpeutêtreré utiliséedans lecorpsdelafonction, B

Seulementsurunevariableobten ue

partraiteme ntparcassurx

Exemplesdetypes récursifs utilisésdansCoq

Inductivenat: Set:=O :nat| S:nat ->nat.

Inductivelist(A :Type): Type:=

|nil:listA |cons:A->listA->listA.

CheckS( S(S O)).

Lesystème répond

3:nat

LafonctionScorrespondàl'operation"ajouter 1"

Exemplesdeprogrammatio nréc ursive

Lafonctionqui additionne touslesnomb respluspetitsque n:

Fixpointsum (n:nat) :nat:=

matchnwith |O=>O |Sp=>p+sump end.

Lafonctionqui calcule lasuitede Fibonacci:

Fixpointfib(n:nat) :nat :=

matchn with |O=>O |1=>1 |S(Sqasp)=>fibp+fibq end. Notezl'utilisati ondeaspourrespec terlacontraintede variable

Fonctionsrécursivessurd' autrestypes

Lafonc tionquiconcatènetoutesl eschaine sd'unobjetdetype t3

Fixpointcat(x :t3): string:=

matchx with |ct3e=>"" |ct3rsy=>s++caty end.

Violationdelacontrainte

Messaged'erreurlorsque lacontrainten'estpasr espectée

Fixpointfib' (n:nat):nat :=

matchn with |O=>O |1=>1 |S(Sq)=>fib'(Sq)+fibq end.

Lesystème répond

Recursivecall tofib'has principalargument

equalto "Sq" insteadofone ofthef ollowingvariables:n0 q.

Bibliothèquedebase

YvesBerto t

Lesnomb res

Pardéfautlesnombresutilisésen Coq sontdesnomb res naturels

Ils'écr ivent0,3,47,268

adaptéepourleraison nementlogiq ue

Pasdenombresnégatifs danscet ype

Check3.

Lesystème répond:

3:na t

Lesopér ationssurlesnombres

addition,multiplication, soustraction

Notationsinfix es:

Checkplus1 2.

Lesystème répond:

1+2:nat

Checkmult2 3.

Lesystème répond:

2*3:nat

soustractiontotale: résultatirrégulierdans certainscas

Evalvm_computein minus2 3.

Lesystème répond:

=0:na t

Programmationparcassurlesen tiersnaturels

Lesentiers naturelssontdedeux formes

0

Spoùpestunautre nombre naturel

Iles tpossibl ededéfinirunevaleurdefaçondi!érentesuivant laform ed'uneautreexpre ssion matchnwith 0= >1| Sp= >3end Lava leurdecetteexpressionest1 sinest0, 3sinestnonnul

Exempledecalcul avec traitementparcas

Evalvm_computein

(funn => matchnwith 0=> 1| Sp= >n+p end) (2+1).

Lesystème répond:

=5:na t

Fonctionsrécursivessurle snombresnaturels

Ilestp ossiblede définirunefonctionquis'ap pellee lle-même Aco nditionquel'appelsefasse surunpréd écesseurde l'argument Lepréd ecesseurdoitêtreobtenupartraitementparc as Cettecontrai ntegarantitquelecalculs'a rrêtetoujours

Syntaxeparticulière :

Fixpointfact(n :nat) :nat:=

matchnwith 0=>1 |Sp =>n* factpend. Calculd'unefonctio nr écursivesurlesentie rsnaturels

Exempledecalcul:

Evalvm_compute infact6.

Lesystème répond:

=720:nat Larep résentationnaïvedesentiersnaturelsempêchede calculerdesgra ndesva leurs.

Lesvale ursdevérité

Untyp eboolcontenantdeuxvaleur strueetfalse

Unecons tructionif...th en...else ...pourfaire

uncalc ulquidépendd'untes t Unce rtainnombredefonc tiondetestretourn antune valeur booléenne

Searchbool.

Lesystème répond

leb: nat->nat ->bool beq_nat:nat ->nat-> bool andb:bool ->bool ->bool orb:bool ->bool ->bool beq_natestuntest d'égali tépourlesen tiersnaturels,lebunquotesdbs_dbs27.pdfusesText_33

[PDF] complement d'agent

[PDF] attribut du cod ou épithète

[PDF] attribut du coi

[PDF] complément du nom

[PDF] exercice attribut du sujet cm2

[PDF] complément circonstanciel

[PDF] évaluation attribut du sujet cm1

[PDF] exercice épithète attribut 5ème

[PDF] attribut du sujet cm1 pdf

[PDF] accord attribut du sujet exercices

[PDF] attribut du sujet cm1 leçon

[PDF] séquence attribut du sujet cm1

[PDF] attribut du sujet cm1 évaluation pdf

[PDF] leçon attribut du sujet cm2

[PDF] evaluation attribut du sujet cm1 avec correction