صفحه 1:
طراحی و پیاده سازی زبانها a
کنترل زیربرنامه
Narges S. Bathaeian
صفحه 2:
شکل کلی حافظه بعد از 020 پرنامه
وک fe AD مج موم تیصو مد
Narges S. Bathaeian
صفحه 3:
متغییهای 9100۱
بارامترهاى تابع »ا
اد رکشت
متخيررهاى محلى تابع >
متغیسهای موقت تابع 2
متخي ررهاى محلى تابع لا
cla ae موقت تابع لا
“tivation record
X gb Activation record
y gb Activation recor
Narges S. Bathaeian
صفحه 4:
activation record
Remember that data storage for subprograms is in
activation record.
Activation
record for P
۷ integer;
X is of type integer.
L-value of X is some speci
activation record.
Goal is to look at locating activation record
for P.
L*value for x
Given an expression: X= Y+Z
1. Locate activation record containing Y.
2. Get L-value of Y from fixed location in
activation record.
3. Repeat process for Z amd then X.
صفحه 5:
انواع محیطهای اجرا
simple call- :fully static) v4! sults ۴
return
FORTRAN77 ®
(stack based) axe, » مبتنى *
C, PASCAL ®
dully dynamic) ty sus *
LISP =
Narges S. Bathaeian
صفحه 6:
Fully static
* قبل از اجرای برنامه, یک ۲6۵۵۲0 ۸1۷31100 برای
هر تابع , در نظر گرفته می شود.
* همه متغیرها (۱06۱ ,9100۱ از یک آدرس ثابت قابل
۴ پارامترهای توابع تنها اشاره گر به مکانهایی از تابع صدا
زننده هستند.
* توابع بازگشتی نمی توانیم داشته باشیم.
* پوینتر نمی توانیم داشته باشیم.
Narges S. Bathaeian
صفحه 7:
شکل کلی حافظه در محیط کاملا
ایستا(الگوی اول)
صفحه 8:
شکل IS حافظه در محيط كاملا
ایستا(الگوی دوم)
آدرس دستور
كد تابع 2
بارامترها و متغيرهاى محلى
صفحه 9:
PROGROO TEST
000۵000 00۵۵
10۲۵۵66 00۵۵ مثال از تكد ناكاضة
ROG, THOLEWO), TEOP 7D
OOXO1LE = 40
ROPO *, THOLO(), THOLB(C), THOLO! BO RT RA N
OGM GOEDDESO(TOGLE,S, TEDE)
PROT *, PEO
900
GDGBROOMY AOGDOGGO(G, OAL, ADOHO)
0۵0۵000 00۵۵
102۵۵66 ,م00۵۵ CILE
ROP OIL), ADEHO, TEOP
WTOGER K
۵۵ = 0.0
1 (( O1LG.OP.OOXG1LE).OR.(G1LCL1.4))
GOTO 88
09 ۵ 20, O1LB
2۵۵6 - ۵۵6+ ۵0000
10990۵۵6۵
29 AODEGO = GART(TEOP/OTLO)
ROTORO
900 Narges S. Bathaeian
صفحه 10:
مثال از یک برنامه
FORTRAN
Ror’, —" Return addr. (I > MAXSIZE
200 * || TABLE(1)
COGROOMD AOGODGGO(®, OLE, DCG) 3 00 Tn
ی O16 % | [TABLE(20)
ROP OO1LE), BOEHO, ۵۵ ® | | TEMP
10۳۳۵0۵6 a 3 —
POOP = 0.0 >
AP (( C1LE.CT.OGXGILE).OR.(GITELP.) مزاخ
هی 2
00 40 120, 08 2
۵06 - 6۵۵+ ۵00*00 & | |QMEAN
6 @ | [RETURN
موه AOCGO = CART(TEOPIOTLO) 2 | | 6085
ROTORO =
000 8 | ۴
۱۱۵۲96۶ ٩ 0 K
صفحه 11:
Stack based
۲660۲۵ با فراخوانی تابع ۴
مربوط به آن در 0۱151 , 531 می شود
و هنگام بازگشت به تابع صدازننده, از 5101
0 , می شود.
دو نوع
۰ 2
* بدون ۵۲۵660۲6 10681 : مانند زبان )
Pascal jl; ast :local procedure t *
Dynamic Scope ®
Narges S. Bathaeian
صفحه 12:
Activation record structure
Subprogram cade
System data, including |S segnents and aysten Stabe
state chain paint code segments 0
Retun point location ۳
‘station record storage stack مام
Foxmal parameters ۱ 070)
هوم ات
۳
Steck
Local variables اليد
‘ree space
lavalabie fer use)
End of
lack block
Tenporaries for
expraselon evaluation
Tenrares (
garentervananeson heap gout
(atecnen nw)
heap
heap baton ۳
را ۱
صفحه 13:
مثال از یکل برنامه 15 «
6
CEP
موم
y: 10
Act. rec yismain
15
۷ 0
ER
IP
u:10
۷ 5
مع
IP
u:5
v:0
EP:
IP
<stdio.k>
{
P (V==O) retusa إن
ober retro yod(y , u % v);
}
0
{
woe (“Yd%od’, Box, :وق
pric (“Yod\e” ard);
:0 او
} Control link = EP: Environment Poihtel
صفحه 14:
nment Pointer) = FP ۰۶
activation yell »o «55.24 (frame pointer)
جارعدر آرلست 0
pointer " 5۵1 : 50: رجیستریکه در لرآدیسسر 5121 در آن
لست
* ۶۳: آدیس۲660۲0 2011۷110۳0 قبلیا دارد.
* آدرس متغیرهای PUSN شده می تواند با توجه به )و اندازه بایت لازم
* متغیرهای محلی تابع و موقت بعد از 300۳655 push ab jo return
می شوند.
DCP (Dynamic 6۵1۳ ها تشکیلی کزنجیره بنام CEP ®
aay.» Pointer)
Narges S. Bathaeian
صفحه 15:
هنگام فراخوانی یک (PFOIOQUE) wl 4
* آرگومانها محاسبه شده و در 50لا , 51961 می شوند.
" مقدار Stack , push js CEP 42 شود.(۴۳)
ge Ge SP yly CEP wom joie * شود.
۴ آدرس بازگشت (۳) در 0۱151 , 5121 می شود. (۱۳)
uF clos! a JUMP S " تابع فراخوانی شده انجام می شود.
Narges S. Bathaeian
صفحه 16:
هنكام بازكشت از یک (Epilogue) at ۳۹
* مقدار CEP در 50 ریخته می شود.
* مقدار ۶ به داخل 0 س)ريخته می شود.
۴ یک پرش با توجه به آدرس موجود در 200۳655 ۲6۲۱۲۳۲
به كد انجام مى شود.
* آرگومانها از 000 , 5121 می شوند تا مقدار 50 تصحیح
شود.
Narges S. Bathaeian
صفحه 17:
مثال از یک برنامه
C
xo
y: 10
phe {Fed , w % v); Act. rec yismain |CEP= xxoc
returct}}
} Sp = XX04
0
1
عمق ,700707 )مسد , &y );
pri (“Yorn :((موج الح pc = XOXO
مسر ©:
}
Narges S. Bathaeian
صفحه 18:
مثال از یکل برنامه 15 «
6
- 8
—sp=XX11
y: 10
Act. rec yismain
+15.
v :10
XX00
XOXO
Ey
بعد سسا
:(ند قلا د , بلحي 1 ) وطاع
صموور
اسب
{
يا 8x , &y );
prio (“%d\a” xed(x));
vets O;
}
Narges S. Bathaeian
صفحه 19:
مثال از یکل برنامه 15 «
6
- 8
—sp=XX0OF
y: 10
Act. rec yismain
+15.
v :10
XX00
XOXO
Es
بعد P (=O)
:(ند قلا د , بلحي 1{ وطاع
5 صموور
pc = XOXD 1
اسب
{
يا 8x , &y );
prio (“%d\a” xed(x));
vets O;
}
Narges S. Bathaeian
صفحه 20:
مثال از یکل برنامه 15 «
6
۴
y: 10
Act. rec yismain
Narges S. Bathaeian
عمد P (=O)
:(ند قلا د , بلحي 1{ ebe
صموور
اسب
{
يا 8x , &y );
prio (“%d\a” xed(x));
vets O;
}
صفحه 21:
محاسبه 01۴561 متغیرها در زمان کامپایل
* آدرس ۶۳ در هر ۲۵6۵۲۵ 2011۷۵110۳0 مبنا در نظر
گرفته می شود.
* آدرس متغیر هایی که در بالای ۶۳ هستند (پارامترهای تابع) با
مقدار مثبت و بقیه با مقدار منفی نمایش داده می شوند.
Narges S. Bathaeian
صفحه 22:
مثال
3
>.
Int : 2 byte
Float : 4 byte
Address : 4 byte
Char : 1 byte
Double : 8 byte
av +4
~— | cEP "ur +6
=t: -6
Narges S. Bathaeian
x: 15
m
u:15
۷ 0
XX00
XOXO
0 لا
۷9
XX0B
X0XD
ts.
صفحه 23:
6 هایت ودر تو
* در هر حوزه (80006) به اسامی تعریف شده در آن حوزه میتوا
دسترسی داشت. پس:
" هر ule procedure « procedure فرزند و برادر خود دسترسی
دارد و می تواند آنها را فراخوانی کند.
* حوزه متفیرهای تعریف شده در یک حوزه, آن حوزه و حوزه های فرزند آن
حوزه است.
* پیاده سازی:
Act. 91: Access link L, SCP (static chain pointer) =
پدر (دسترسیبه ۳06601۲6 پدر)
* فراخوانی شده از پدر
* فراخوانی شده از برادر
Narges S. Bathaeian
صفحه 24:
منال ۱ از یک برنامه
زا سب
سسب جام ی 9]
Pascal
۳
y: 10
Act. rec gismain
7
تست
(est) :ل لس
اجازه دسترسيها د ie
7 مپسا
زمان كاميايل نكهدارى
.مى شود ead;
بح
8 © :
Oud;
Narges S. Bathaeian
صفحه 25:
flee ۱ از یک برنامه سا يدا
J )2 ~ بر 9
Pascal 1
bead xs:
y: 10 3
main i تايع Act. rec
No SCP 3 =
ae . |DCP
begs ۳
3-3
و6
۰
Oud;
Narges S. Bathaeian
صفحه 26:
منال ۱ از یک برنامه
Pascal
xt
y: 10
Act.recgumain نما
ny
No SCP
DCP
59
SCP لب
DcP
Act. Rec gAct. Rec
فراخوانى از طرفل يد
مقدار 628 در 06 قرار داده مي شو
Narges S. هه
صفحه 27:
منال ۱ از یک برنامه prow test;
—Pascal 24 تسس
y: 10
[Act.rec.ismain
3 ss
No SCP
;| DCP 2
ct. Rec p
SCP لم
DCP —|
59
م50
DCP
فراخوانى از طرف بيلد
مقدار 508 برادر در 56۶ قرار هی و2مو ]دز .5 Narges
Act. REC r Act. Rec
صفحه 28:
منال ۲ از یک برنامه proce bn
px Pascal ف
y: 10
[Act.rec.ismain
No SCP
DCP
ct. Rec p
SCP a
۷ pcp
م50
لد DCP
زنجیره 50
Act. REC r Act. Rec
Narges S. Bathaeian
صفحه 29:
۶ ۹
Whe ideo! Put the stoic اهنا ia a sepordie stack
cited ولو و MRe eotries ia the disphoy ure
porters to the rt_revs thot have the voriubles iu the
Represed rePereuces us
(display_oP Peet, bovol_vP Poet)
where disphoy_oPP set is the sueve us choia_pPPset
Narges S. Bathaeian
صفحه 30:
۶ ۹
(Por :جا خام ار ۱ دص و امه وه
* Gwe, io the vew @ot_rev, ou vopy oP the displ
poitter ut posiiza kK
* ut the tok to the @ot_rec Por P ot positive k io the
display
Narges S. Bathaeian
صفحه 31:
Oispys (Cxcople)
program MAIN 3;
procedure BIGSUB;
procedure SUB1;
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
end; { BIGSUB }
end. { MAIN 3 }
Narges S. Bathaeian
صفحه 32:
Oppky
اس
Ore ٩: 582 امس 1
OePore te oul, we bayet
@.R. Por SUB2
AR. Por MAIN. 3
اس
Pier ther val, wee bene
OAR. Por SUBL
AR. Por SUB2
.R. Por BIGSUB
@.AR. Por MAIN 3
Orch
Narges S. Bathaeian
program MAIN 3;
procedure BIGSUB;
procedure SUB1;
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
end; { BIGSUB }
end. { MAIN 3 }
صفحه 33:
e200
جات
ات0
3 سای ٩82 :0 ع0
تسوا مت ری سا ات0
OR Por GOME
0008
0۸:۳۷ 0۵
اس
Pier the cal, wer bene:
OR. Por ۵9
OR. Por CHOE
OR. Por O1HOOO,
OR. Por ۵
اس
Narges S. Bathaeian
Oispaps
xavpte)
program MAIN 3;
procedure BIGSUB;
procedure SUB1;
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
end; { BIGSUB }
end. { MAIN 3 }
صفحه 34:
9
©
qa
o
Ouse 9: SUB3 vay SUB1
(DePore thee vel weer beet
OR. Por GOOD
OR. Por ©OOE
OR. Por O1WOOO
OR. Por OOT_D
One
[BP ether ویب
OR. Bar ۸
OR. Por GOOD
OR. Por ۵
OR. Por ۵۵۵۸۵
00۵ 00۱۰
اس
Narges S. Bathaeian
Oisplays
xavpt)
program MAIN 3;
procedure BIGSUB;
procedure SUB1;
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
end; { BIGSUB }
end. { MAIN 3 }
صفحه 35:
Dynamic scope rule
= refers to most recent activation
record (DCP)
= Not fully stack based
= Stack: function calls
= Eamples
= Lisp
Narges S. Bathaeian
صفحه 36:
Static vs. Dynamic Scope
outer 6۲
block
(3)
function g(z\{ return x+z; }
function f(y)
02) Ea
Which x is used for expression
?
static scope 1
lynamic scope
ski OO
صفحه 37:
۳۹ Retention vs. Deletion
= Retention = Deletion
= Fortran = Local variables in
= Static and global C, Pascal
variables in C
Narges S. Bathaeian
صفحه 38:
Parameter passing
eter: A variable in a procedure that represents some
data from the procedure that invoked the given
= Parameter transmission: How that information is passed to
the procedure.
The parameter is also called the formal argument.The data
from the invoking procedure is called the actual argument
or sometimes just the argument.
Usual syntax:
Actual arguments: call P(A, B+2, 27+3)
Parameters: Procedure P(X, Y, Z)
What is connection between the parameters and the
arguments?
Call by name
Call by reference
Call by value
Call by result (or value-res@at)
صفحه 39:
Language dependent
۷ جص languages have different
mechanisms:
- ALGOL - name, value
- Pascal - value, reference
* C - value (BUT pointers give us
reference
Constant tension between desire for
efficiency and semantic correctness in
defining parameter transmission.
صفحه 40:
Call by name
= Substitute argument for parameter at each
rrence of parameter:
5 27+3(
9. Definition: procedure P(X,Y,Z)
{int I; I=7; X = I + (7/Y)*Z;}
. Meaning: P(X,Y,Z) {int I; I=7;
A=I+(7/(B+2) )*(27+3) ;}
= This is a true macro expansion. Simple
semantics, BUT:
1. Implementation. How to do it?
2. Aliases. What if statement of P were: I = A?
3. Expressions versus statements: If we had D=P(1,2,3)
and a return(42) in P, what does semantics mean?
4. Error conditions: P(A+B, B+2, 27+3)
40
صفحه 41:
A thunk is the code which computes the L-value and R-
je of an argument.
ach argument,
pass code address that computes both
27+3) generates:
subroutine P
of thunk to return L-value(A)
of thunk to return R-value(A)
of thunk to return L-value(B+2)
of thunk to return R-value(B+2)
of thunk to return L-value(27+3)
of thunk to return R-value(27+3)
to X, call thunk 1, To access X, call thunk 2
to Y, call thunk 3, To access Y, call thunk 4
to Z, call thunk 5, To access Z, call thunk 6
name
P(A, B+2,
jump to
address
address
address
address
address
address
To assign
To assign
To assign
Issue: Assignment to (B+2): How?
= Call by name is conceptually convenient, but
inefficient. 41
صفحه 42:
Examples of Call by Name
) {x = x + xj}
Seems simple enough
Y=2; P(Y); ite(Y) = means Y = Y+Y
write(Y) = prints 4
2. int A[10];
for(I=0; I<10; I++) {A[I]=I;};
I=1; P(A[I]) = A[1] = A[1] + A[1] = A[1] set to 2
3. But: F {I = I + 1; return I;}
What is: P(A[F])?
P(A[F]) = ALF] = A[F]+A[F] => A[I++] = A[I++]+A[I++]
= A[2] = A[3]+A[4]
4. Write a program to exchange values of X and
Y: (swap(X,Y))
Usual way: swap(x,y) {t=x; x=y; y=t;}
Cannot do it with call by name. Cannot handle both of
following: swap(I, A[I]) swap(A[I],1)
One of these must fail. 42
صفحه 43:
Call by reference
= Pass the L-value of the argument for
parameter.
py inx ‘Act Res. for P Act rec. for @
int
= Implementation: 0 ۲ | لجز ر
"۲67001 = B+2 7] ~]
Temp2 = 27+3 call Ux)
jump to subroutin
L-value of A
L-value 1
L-value of Temp2
= This is the most common parameter transmission
mechanism. In the procedure activation record,
parameter X is a local variable whose R-value
is the L-value of the aggument.
صفحه 44:
Gall by value
s the R-value of the argument for the
meter.
cation:
P(A,
۲۳ Act 9۵ 0۴ Act reo. for
ity,
7-7
20
= Implementation:
Templ = B+2
Temp2 = 27+3
jump to subroutine P
R-value of A
R-value of Temp1
R-value of Temp2
= In procedure activation record, parameter X is a local
variable whose R-value is the R-value of the argument.
44
8 از
01 |
صفحه 45:
Call by reference in C
" ©) only has call by value,
=" BUT pointer variables allow for
simulating call by reference:
P(i, j) = passes i and j by value.
P(&i, &j) => passes L-values of i and
I
P(*x, *y) {*x = *y + 1;} => arguments
are addresses (pointers)
45
صفحه 46:
Call by result (or
lue-result)
« )211 ۵۷ value, AND pass back the
final value to argument upon
return.
= Parameter is a local value in
procedure.
"Similar to call by reference,
except for aliasanghcian
صفحه 47:
۳۹ Pass by value
" مقدار یک پارامتر قبل از void inc2(int x)
فراخوانی تابع محاسبه شده و ou 44%{
نتیجه فرستاده می شود. } ++x;
s
تغییر پارامتر در تابع فراخوانی
شده, تأثیری در تابع فراخوانی
کننده ندارد. مگر اينکه اشاره
كر به متغير فرستاده شده 3 ++(*x); {
باشد. } ;)4(4%+
C, Pascal, ADA ®
void inc2(int *
Narges S. Bathaeian
صفحه 48:
۳۹ Pass by reference
* مقدار آدرس پارامتر فرستاده void inc2(int &x)
مى شود. رب ۲
* عنوان پارامتر در تابع فراخوانی } ++x;
شده, مجازی است.
* :6 در تابع فراخوانی شده,
* ۴0۳۲3077 آدرس پارامتر که بطور
تسبی فرستاده شده باید
۴۵56۵۱ : ۲ ۴
پا توجه به 962۳ دوباره
محاسبه شود.
Narges S. Bathaeian
صفحه 49:
۳۹ Pass by value-result
* مقدار یک پارامتر قبل از void p(int x, int y)
فراخوانی تابع محاسبه شده و +4x; {
نتيجه فرستاده می شود. سپس } ++y;
مقدار پارامتر پس از تغییر در ۱
تابع فراخوانی شده, دوباره در main()
مکان اول خود کپی می شود. int a=1; {
p(a,a); ADA : in out ۴
* پیاده سازی؟ printf(“%d”, a);
return 0;
۷
Narges S. Bathaeian
صفحه 50:
Pass by name
* مقدار یک پارامتر قبل از فراخوانی تابع te
9 و ۲ ۱۳۲
محا 7 5 اخوان ,
void p(int x) Serre 29 Sa Ae ۳
شده محاسبه مى شود. 4
" هر بارامتر, خود يك +4x; } procedure
است.
main() Algol60 ۰
{ i=a[{1]=a[2]=1; sue نا
۳ Si
printf(“%d %d”, a[1],a[2]) پیاده سازی مشکل
return 0; Lazy evaluating *
1
Narges S. Bathaeian
صفحه 51:
Block
" برخى زبانها مانند © بلوك بندى مى شوند.
۴ 56006 متغیرهایت عریفشده در ی کب اوکآنبلوکو بلوکهایف رزند آنبلوک
لست
main()
{
int i,j;
1
. /Jundefined variable k
Narges S. Bathaeian
صفحه 52:
پیاده سازی بلوک 4
۴ با وارد شدن به یک بلوک متغیرها در 0۱05/0 co SACK, شوند.
* با خارج شدن از یک بلوک متغیرها از 000 ,510 می شوند.
* در محاسبه 07۲561 متغیرها در زمان کامپایل باید دقت شود.
بلوکهای برادر از Offset یکسانی شروع می شوند.
Narges S. Bathaeian
صفحه 53:
Fully Dynamic
* در ۷00۱132 می توان یک procedure را به عنوان آرگومان
برگشتی 0۲0۵660۱1۲6 دیگر داشت.
* کاملا در 1680] پیاده سازی می شود.
* مثال صوری:
typedef int (*proc)(void);
proc g(int x)
int f(void) {return x; } {
return f;
main()
{ proc c;
c= (2);
printf(“%d”,c());
return 0;
1
Narges S. Bathaeian
صفحه 54:
* در خواست تخصیص حافظه توسط برنامه
new ۵۱06 "
" بيدا كردن فضاى مناسب خالی در حافظه
= در خواست آزادسازى حافظه توسط برنامه
free "
* آزادسازی حافظه و اضافه کردن آن به لیست فضاهای خالی
Narges S. Bathaeian
صفحه 55:
Dynamic environment
* برای مواقعی که طول عمر یک متغیر بیشتر از
6 مربوطه است.
* بخاطر 000 شدن 0۲۵660۱۲6 با 51001
قابل پیاده سازی نیست.
* مثال:
int *dangle(void)
{int x;
return &x;}
آدرس یک آرگومان برگشتی است. پس باید ذر
قسمتی جدا از 581 تعریف شده باشد.
Narges S. Bathaeian
