Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
Back to Stack Frames. On to Symbol Tables.
Held Friday, November 1, 2002
Summary
Today we continue our investigation of stack frames by considering some particular examples.
Notes
Overview
factorial
,
so we'll try that first.
function factorial(n: integer): integer; var tmp1: integer; begin if (n = 0) then factorial := 1 else begin tmp := factorial(n-1); factorial := n * tmp; end end;
+--------------+ <- FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ | n | +--------------+ <- SP
+--------------+ <- FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ | n | +--------------+ | tmp | +--------------+ | extra | +--------------+ <- SP
+--------------+ <- FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ | n | +--------------+ | tmp | +--------------+ | extra | +--------------+ <- SP | our FP | +--------------+ | rec. result | +--------------+
factorial
look like?
In a generic language with four bytes per word
BEGIN_FACTORIAL: # Do anything appropriate for the beginning of a procedure call ... # if (n = 0) START_FACTORIAL_CODE: PUSH 8 # Space for temps COMPARE MEM[FP+12], CONSTANT[0] JUMP IF EQUAL BASE_CASE JUMP RECURSIVE_CASE # factorial := 1 BASE_CASE: STORE INTO MEM[FP+4] FROM CONSTANT[1] JUMP END_FACTORIAL # tmp := factorial(n-1) RECURSIVE_CASE: # Compute n-1 SUBTRACT CONSTANT[1] FROM MEM[FP+12], STORE IN MEM[SP-8] # Call factorial ... # Copy the value back STORE INTO MEM[SP-8] FROM MEM[SP+4] # factorial := n * tmp MULTIPLY MEM[SP-12] BY MEM[SP-8], STORE IN MEM[FP+4] JUMP END_FACTORIAL # Clean up END_FACTORIAL: ...
# Do anything appropriate for the beginning of a procedure call ADD CONSTANT[8] to SP
END_FACTORIAL: SUBTRACT CONSTANT[8] from SP
SET FP to MEM[FP]
JMP MEM[FP+8]
STORE INTO MEM[SP+12] FROM MEM[SP-8]
STORE INTO MEM[SP] FROM FP
SET FP to SP
ADD CONSTANT[16] to SP
STORE INTO MEM[SP+8], RETURN_HERE
JUMP BEGIN_FACTORIAL RETURN_HERE:
SUBTRACT CONSTANT[16] from SP
Back to Stack Frames. On to Symbol Tables.
Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Fri Dec 6 10:38:24 2002.
The source to the document was last modified on Wed Sep 4 10:08:36 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.25.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby