ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



ʽеĸֵ
ʯԾ顡Ԭǿǿ¾
ժҪ̽ڴʽм븳ֲֵɥʧ͸⣬Щָ壬Щֵһ򵥵ʽԵĽͳ.
ؼʡʽ,ֵ,Monads.
ͼšTP312
Assignments for Pure Functional Languages
SHI Yue-xiangYUAN Hua-qiangCHEN Jing
Department of Computer Science Xiangtan University Xiangtan 411105
SUN Yong-qiang
Department of Computer Science and Engineering Shanghai Jiaotong University Shanghai 200030
Abstract In this paper, the authors show that assignments can be incorporated into pure functional languages without loss of referential transparency. And the denotational semantics of these assignment operations are given. Using these assignment operations, the authors define an interpreter of a simple imperative language.
Key wordsPure functional languages, assignments, Monads.
ڴʽм븳ֵ,ֲɥʧ͸,һֱǺʽѧעĽ.ⷽһϵеķ,Щǻϵͳ,ϵͳʮָ,ûбǹ㷺.ף1Monad13ݣֵ뵽ʽ,õĸӵϵͳ.,ף1һ첽I/OperformIO,͸ͻ.һȱ,״̬תԼ״̬вķиĽ,ʹڴʽм븳ֵ䣬ֲɥʧ͸,Щֵָ,Щֵһ򵥵ʽԵĽͳ.
1״̬ת
1.1. ״̬תSTĺ,һΪsĳʼ״̬,һΪaֵһΪsĽ״̬.
,״̬תSTͿɶΪ: type ST s a=state s->(a,state s)
򵥵״̬תunitST,ֵ,˿Ӱ״̬:
unitSTa->ST s a
unitST x=s->(x,s),Уs->һ˱ʽ.
״̬תܹ˳,Թɸ״̬ת,bindST:
bindSTST s a->(a->ST s b)->ST s b
mbindST k=s->let (x,s)=m s
in k x s
1.13. (ST,unitST,bindST)һMonad.
2״̬в
ף1,ԸֵĴף4ݵĿɸֵRef a,IOaһMonad:
newVara->IO(Ref a)
assignVarRef a->a->IO ()
deRefVarRef a->IO a
ף1һ첽I/OperformIO,͸ͻ.
performIOIO a->a
performIO m=case (m newWorld) of
MkIORes r w->r
:
let v=performIO(newVar true)
in performIO(deRefVar v).
̺һ,ΪvnewVar trueɵ,ִperformIO֮,vͷŵⲿ,óܿڶdeRefVar v֮ǰ,v޸,Ľڼ˳,͸ɥʧ.
 IO a,״̬IO,粻ֱӶ״̬в.Ϊ˸ף1ݵĴ,ǽIOе״̬ʽرʾ,ĽΪST s a,ʹ״̬ΪSTһ,ǳ֮Ϊ״̬в.ף4һ,ǽ״̬Ϊñĵֵַӳļ,Ref aĽΪMutVar s a,ʾñǴΪs״̬з,Ϊaֵ.,ף1ݵñ3ɸĽΪ
newVara->ST s (MutVar s a)
readVarMutVar s a->ST s a
writeVarMutVar s a->a->ST s ()
,ͨ״̬תͶ״̬в,ǾͿԶǵ첽I/OperformIO:
performIO˪a.(s.ST s a)->a
ⲻһHindley-Milner,Ϊʲȫڶ.Ϊʲôͻֹף1еĴ?ǻ:
let v=performIO(newVar true)
in performIO(readVar v)
performIO(readVar v),ñv״̬ת(readVar v),readVar vv,,Ƶʽж:
{...,v:MutVar s Bool}readVar v:ST s Bool
ΪִperformIO(readVar v),readVar vӦǪs.ST s Bool,ʱsɱԪ,,readVarͲǪs.ST s Bool,performIOҪͲƥ.
vĶ:v=performIO(newVar true),newVar trueST s (MutVar s Bool),ƹΪs.ST s (MutVar s Bool),ȻperformIOͲƥ.ǽperformIOͪa.(s.ST s a)->aеaMutVar s Bool:
performIO˪s.ST s (MutVar s Bool)->MutVar s Bool
aMutVar s Boolʱ,Ǳ뽫performIO͵ԼԪ,newVar trueͪs.ST s (MutVar s Bool)s.ST s(MutVar s Bool)ƥ.
,ͨ״̬תͶ״̬в,ǽperformIOͶΪa.(s.ST s a)->a,ȫף1еĴ,֤͸Բɥʧ.
3ָ
״̬׼ӵʽԵı׼.ȣǶչ״̬תĴʽԵ﷨
e=x|k|e1e2|x->e|let x=e1 in e2 
k=...|unitST|bindST|newVar|readVar|writeVar|performIO
xʾ,kʾunitST,bindSTڲ.
򵥵ĴʽԵָ:
šExpr:Env->Val
šk=¡k
šx=x
še1e2=(še1)(še2)
šx->e=v.(še(ѣx->v))
šlet x=e1 in e2=še2(fix(ܦѡ->(ѣx->še1ѡ))
¡performIO e=VperformIO(še)
¡e1 bindIO e2=VbindST(še1)(še2)
¡unitST e=VunitST(še)
¡newVar e=VnewVar(še)
¡readVar v=VreadVar(šv)
¡writeVar v e=VwriteVar(šv)(še)
ʹEnvʾ,Valʾֵ:
Env=Ǧ(var->D)
Val=ȦD
ͦӵıӳΪDӵֵ,ֵDӵĲ.
µ͹ST,MutVar,Ϊ˸ǵ,庯ṩǵĽṹ:
DST s a=State s->(Da->State s)
DMutVar s a=N
State s=(N->Val)
״̬Ǵӵַ(ַȻʾ)ֵ޲ֺ,áͱʾδ״̬,ǾͿԸָ:
(VperformIO m)=x where (x,ҡ)=m 
(VbindST m k)=k x ҡ where (x,ҡ)=m 
(VunitST v) =(v,)
VnewVar v =(,) if =
(p,ңp->v) otherwise
VreadVar p =(,) if pdom
(p,) otherwise
VwriteVar p v =(,) if pdom
((),ңp->v) otherwise
һ,һ򵥵ʽԵĽͳ,Assign Var ExpʾExpֵVar,Read Varʾһ,Ӽ̶ȡһݸVatr,Ϊ,еԤȴһinput,Write Expһ,While ExpComͨѭ.
Data Com=Assign Var Exp|Read Var|Write Exp|While Exp Com
type Var=Char
data Exp=...
interpretˣCom->Int->Int
interpret cs input=performIO(newVar input bindST inp->command cs inp)
commandˣCom->MutVar s Int->ST s Int
command cs inp=obey cs
where
obeyˣCom->ST s Int
obey (Assign v e : cs)=eval e bindST val->
writeVar v val bindST \_->
obey cs
obey (Read v:cs)=readVar v bindST (x:xs)->
writeVar v x bindST _->
writeVar inp xs bindST _->
obey cs
obey (Write e:cs)=eval e bindST out->
obey cs bindST outs->
unitST(out:outs)
obey (While e bs:cs)=eval e bindST val->
if val= =0
then obey cs
else obey(bs++While e bs:cs) 
ʯԾ,1966,ʦҪоΪ.Ԭǿ,1966,ʿڣҪоΪʽԣ.ǿ,1931,ڣʿʦ,ҪоΪۣʽ.¾,Ů,1968,ʦ,ҪоΪʽ.
ͨѶϵ:Ԭǿ̶411105,̶ѧѧϵ
ߵλʯԾ Ԭǿ ¾̶ѧѧϵ̶411105
ǿϺͨѧѧ빤ϵϺ200030
ο
1Jones SL Peyton, Wadler PL. Imperative functional programming. In: Hughes ed. Proceedings of the 20th ACM Symposium on Principles of Programming Languages. New York: ACM Press, 1993. 7184
2Wadler PL. Comprehending Monads. Mathematical Structures in Computer Science, 1992,2(4):461493
3Ԭǿ.ʽI/Oϵͳоʵ֣һMonad۲ʿѧλģ.ϺϺͨѧ1996(Yuan Hua-qiang. The research and implementation of a pure functional I/O systemPh.D. Thesis. Shanghai: Shanghai Jiaotong University, 1996)
4Swarup V, Reddy US, Ireland E. Assignments for applicative languages. In: Hughes ed. Proceedings of Functional Programming Languages and Computer Architecture. Heidelberg: Springer-Verlag, 1991. 192214
1998-04-14ո壩
