This one is not hard work, so it won’t take you much time. I need the tutor who can use the logic which I will show you to write your code. Please read the requirement carefully and don’t forget “make notes as detailed as you can in your codes”, which I will show the sample when you accept this work.
If you think you can take on the important task, please bid kindly 🙂
Assignment-5: Programming Calculator
CS 210, Fall 202
Bonus Assignment
1
Introduction
For many reasons, a programmer might not want to use statically defined memory. So, in this assignment you will be
learning to write and debug code that manages its own dynamically allocated memory. Specifically we will use the standard
allocators to create or remove memory on the Heap.
The Heap is a large area of memory, a range of addresses, set aside by the compiler and operating systems which is
free for arbitrary use. In other words there is no other part of you program’s variables or code placed within the Heap.
The C standard library provides a Heap memory allocator called the malloc package. C programs allocate a block of
memory by calling the “malloc” function, and free a block by calling the “free” function.
A block of memory is simple a contiguous set of bytes starting at a specific address and ending at a specific address.
As your program executes it can use the function malloc to request a new block of memory of a particular size. malloc
will return the starting address of a block that is at least as big as the size requested. If it cannot find enough space it
returns NULL, the zero address. malloc ensures that the block it returns does not overlap with any other allocated or free
blocks. In this way your program can safely use this memory to store whatever it likes. Similarly, your program can free
a block it has previously allocated by calling the free function passing the starting address of a block it allocated with
malloc earlier.
Dynamically allocated memory is very powerful and the heart of how most real programs work. Most languages like
Java, python, ruby, javascript, etc are really just programs themselves that make heavy use dynamic memory in their
operation. These languages, however, largely hide the details of dynamic memory management from the programmer.
While dynamically allocated memory is very powerful it can be very tricky to get right. Many bugs can occur if you
don’t fully understand how things work. For example, if your program allocates memory for something that is temporary,
for some operation it has been requested to do, and then never frees that memory it creates what’s called a ’leak’. Given
how fast a computer can operate, in time such leaks can exhaust the memory capacity of your computer and things will
begin to fail. Or perhaps your program attempts to use memory, read or write it, that it has already freed. This can lead
to very difficult bugs as there will be no immediate error. In fact, it may have no noticeable affect for a very long time
until one day some other part of your program reallocates a block that ends up overlapping with the free memory that
is being still actively used. All of a sudden your data structures seem to be magically changing for no apparent reason.
Another common bug, is freeing memory that you already freed before, this too can lead to nasty bugs. Unfortunately
there are many more mistakes one can make.
In order to write powerful programs such as new programming languages, operating systems, databases, and high
performance programs one must learn to program with dynamic memory and perhaps more importantly become familiar
with debugging the bugs that can arise from the common mistakes made. Remember despite other languages hiding it from
you someone wrote the dynamic memory management code in that language and they too had to learn how to properly
use dynamic memory and debug the code they wrote.
In this assignment, we will explore programming and debugging with dynamic memory in the construction of an infix
calculator. We will build a calculator that uses two types of stacks, data and operator stacks that store items on it. The
stacks and the items will use dynamically allocated memory. Additionally, we will use this assignment to explore how large
more complex programs, composed of multiple source files are constructed. In Part A of the assignment you will construct
a Stack Abstract Data Type (StackADT) module, in a separate set of files, that you will use in Part B to implement the
actual calculator.
Careful analysis of your code, defensive programming and knowledge of the debugger is critical to getting dynamic
memory management code working correctly.
You can also read Chapter 19 for more details about the Heap and how it grows.
1
2
Logistics
The only “hand-in†will be electronic. Any clarifications and revisions to the assignment will be posted on the course
Piazza site.
3
Background
Some building blocks are needed to understand this assignment.
3.1
Linked Lists
A linked list is a linear collection of data elements whose order is not given by their physical placement in memory.
Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent
a sequence. So, each node, contains the data and also a pointer to the next node, as shown in Fig. ??. Linked lists are
great tools to master as they can be used to not just create uni-directional lists but bi-directional, circular or any fun shape
you can imagine. As they have no fixed size, when a new node is added memory needs to be dynamically initialized for
that node via C code and later when we remove the node it should be freed as to not run out of memory.
Figure 1: Linked List
3.2
Stack
A Stack is a data structure that is used to store information in a distinct order.
Two key operations on a stack are, (1) push operation which inserts an element into the stack, and (2) pop operation which
removes the last element that was added into the stack. The way a stack grows is, last in first out (LIFO), i.e. when a
push occurs the element is added to the top of the list and when it is popped is the first to be removed. We are using a
one directional linked list implementation for the stack.
Looking at Fig. ??, the first element that created the stack was 2, hence it is at the bottom and does not have a pointer
to another node but has null. Then 7 is pushed and last element to be pushed onto the stack is 4. Hence the stack pointer
is pointing to memory address 709. If pull was called on this stack. The node with data 4 and addr. pointer 351 will be
deleted by freeing the memory and moving the stack pointer to point at address 351 as the top should now me element 6.
Figure 2: Stack using Linked List
3.3
Part A: StackADT
Readings:
1. Please read Chapter 19 of your text. This introduces the concept of dynamically allocated memory. Also provides
various implementation of STack Data Structure that will be useful in part A of the homework assignment.
2
2. Chapter 15 will help you understand how the various files of this assignment are used to create the program. It helps
understand the use of header files and building a makefile.
3. You will also likely find it useful to review the material of chapter 17.
Part A of this assignment is essentially programming project 4 on page 506 of your textbook. However, we have
provided some additional support and guidance.
3.4
Details
Begin by clone a copy of the your assignment-5A repository from you cs210-gitlab account. In the repository you will find
several files.
Makefile This file describes how to construct your program from the other files. In particular when you run the
program called make it will read this file and run the compiler on the various files to produce intermediate fragments
called object files. It then uses the compiler again to link them together to produce the executables. See chapter
15 for more information on make and makefiles. In partA the makefile will direct make to try and build two
executables stackclient and stackclient memtrace (discussed below). Initially, make will not work as the solution
in stackADT4.c is not implemented.
stackADT.h This is the header file on page 496 of the textbook. We have modified the names by prefixing them with
Stack . We have also modified. as per programming project 4 to remove the use of the Item typedef. Instead it
is written around the idea of using void *. You should not have to modify this but you should carefully review in
context of the material in Chapter 19 so you understand what it is you are trying to write.
stackADT4.c this is the file that you will spend most of your effort on. We have seeded the file with some includes that
you should not have to modify. You main goal is to write implementations of the functions listed in stackADT.h. As
suggested in the textbook you should use stackADT3.c on page 500 as your starting point. You will need to type
this in and modify as you go. Be very careful to analyze and understand what you are doing. Remember dynamic
memory bugs find their way into code very easily.
stackclient.c to make your life easier we are providing you with a version of the stackclient.c code on page 494 that
has been modified to exercise the new version of the stackADT that you are writing in stackADT4.c. You should
carefully study this code!. By understanding it you can better understand what you stack code has to do. In it
you can see examples of the client code using malloc and free to create memory items that it uses the stack code to
store and recall. It is careful to free the memory when it is done with an item. Pay attention to this as this will be
used in part B when you have to manage the stacks for the calculator!
memtrace.h This is a header file that must be included to use the memory tracing infrastructure. This is required for
the tests and will aid in your debugging. You should not have to modify it and by default it is already included in
the necessary c files. See the appendix on memtrace for more information.
memtrace.c This is the implementation associated with memtrace.h. You should not have to modify it.
uthash.h This is hashtable code used by the memtrace code to track the each malloc and match up the frees. You should
not have to modify it.
test.sh As always, use this file to see how your code is working. There is a slight modification as to how you run it. Now
test.sh takes an argument. Type ./test.sh 1 to run the test. It take stackclient.c and use your implementation in
stackADT4.c to test the code.
stackclient This should just be the executable version of stackclient.c. If you run ./reference stackclient, the
output should match for both if your implementation of the stack code is correct.
stackcient memtrace This is another executable that can be executed by typing ./stackclient memtrace. This will
help you know if you are leaking memory in your code. The full potential of this is explained in the Appendix. This
along with GDB will be the most useful tools for debugging your code.
3.5
Tips and Hints
1. You may find it useful to simply get the code from the textbook working first by creating your own copy of
stackclient.c and stackADT3.c from the textbook. To do this you might create two new files (bookstackclient.c
and stackADT3.c). Then add lines to the makefile so that you can compile these into a new binary eg. bookstackclient
that you can then play with. This will also be good practice in managing big projects.
3
2. Learn to use the debugger! See appendix GDB.
3. Be careful to think about what Stack make empty should do given that the stack is now storing items that are
dynamically allocated.
4. Figure out how to use the memtrace infrastructure we have provided. See appendix memtrace.
5. It is very important you see how the stack data type has been changed from Item to void *. How does this change
each individual function?
6. Read stackclient.c, it has comments to explain how having a void * type changes use of malloc for using an int vs
char.
4
Evaluation
Auto-grader will be grading most of the assignment, but as always there will be points for comments, gitlog and coding
style.
5
Submission Instructions
Use Gradescope to submit your solution.
Please commit and push your code at regular intervals. When you push please leave meaningful comments as the commit
message. As before, when you submit to Gradescope you must use the gitlab option. This will submit your last pushed
version to cs210-gitlab.bu.edu as your submission.
6
Late Policies and Plagarism
Late submission will be permitted using the default penalty outline in the syllabus.
Plagiarism: DO NOT CHEAT!!! We will be using input from a similarity checker, git history inspection and manual
code inspection to identify possible cases of plagurism. Please see the syllabus for the formal Plagiarism policy.
Git Histories and Plagiarism: Note if your git history shows a small number of commits that takes your code from
an empty solution to a working solution your solution will automatically be flagged as suspicious. Get in the habit of
making commits that reveal your effort. For example even if you are only planning out your solution or exploring how C
works add some comments and code to your source file and commit these, even if it is not working, with a commit message
that indicates what you were trying to do. Eg. One commit might be: “Trying to figure out how to use scanf to read in
input. Unfortunately not working quite yet.†and a following 10 minutes later after you figure it out might be “Got it!
Can now read in a number using scanf. Next will try and read in two numbers in the format of mm/ddâ€Â. In this way your
effort and progress is clearly reflected in your commit histories. Remember your git histories will capture not just your
messages but what exact changes have been made to the files – what characters you have added and removed, so do make
sure your messages and changes match up.
See the http://www.bu.edu/academics/resources/academic-conduct-code for the CAS Academic Conduct Code, in
particular regarding plagiarism and cheating on exams. Copies of the CAS Academic Conduct Code are also available in
room CAS 105. A student suspected to violate this code will be reported to the Academic Conduct Committee, and if
found culpable, the student will receive a grade of â€ÂF†for the course.
4
Appendix: GDB
As you may have figured out GDB is the standard debugger available on the Linux. It is a powerful tool for controlling
and inspecting a running binary executable. The vscode debugger panes are in reality just a frontends to gdb. To launch
gdb directly you simply open terminal window and issue the command gdb where executable is the name
of the binary program file produced by the compiler. Eg. gdb stackclient. This will start gdb which in turn will load
stackclient in preparation for debugging its execution. gdb can be use on any binary executable including the system
installed programs like ls. However, to make use of all of gdb’s power you need to have the compiler leave extra information
in the binary so that gdb can understand how your logical variables and functions map to your program memory. To do
this we pass the -g flag to gcc when we compile the files that constitute our program. If you inspect the makefiles or
watch the commands that run when you issue make you will see this flag being passed.
Like other power tools gdb requires the user to learn how to use it effectively. You can use gdb to:
1. Inspect any portion of you programs memory.
2. print the value of variables in various formats decimal, hex, binary, etc.
3. stop execution
4. single step both the underlying assembly code and have it step the logically associated C source lines.
5. You can have it stop execution because a certain variable has changed.
6. You can have it display the value of variables every time you step.
7. and many more things.
Perhaps one of the most important aspect of gdb is its ability to let you inspect and follow pointers as you program
executes.
We highly recommend that you look at the resources we have posted on Piazza regarding gdb and start exploring its
use. PartB of this assignment will be considerably more challenging to get right without using the debugger.
Here as some things you will want to clarify how to do:
1. Get help Eg. help or help data or help breakpoints
2. list the source code associated with binary you are debugging. Eg. list main
3. Set a breakpoint on a function or line. Eg. break main or break 120
4. Single step: allow you program to execute the equivalent of one line of source code including going into functions.
eg. step
5. Stepping execution but not going into functions rather executing the function as if it where a single operation. Eg
next
6. print the value of a variable. Eg. p s1
7. examine memory Eg. x /16bx 0x606010
8. display a value ever time you stop the program eg. display /x s1
There are many more things you can do but the above should get you going with things to explore.
Remember our field is a rapidly changing world of technology. A common hallmark of masterful computer scientists and
programmers is the ability to explore and learn technologies and tools in order to get the job done. This skill is developed
by doing and exploring not by following recipes. Treat learning gdb as such an opportunity.
5
Appendix: memtrace
In order to help you learn and debug dynamic memory allocation we have written a simple memory tracing facility for
you to use. In the memtrace.h and memtrace.c files is a set of functions that override the functions malloc and free.
These new versions create trace or log of each allocation and free call as your program executes and at the end of program
prints out a summary. These functions attempt to inform you of â€Âstrange†behavior that might indicate that you have
errors.
Specifically every time you call malloc this code will call the real malloc, printing out an index, the address of the
newly allocated block and its size. It will also keep a record of this so that when you invoke free it can search to see that
there is a matching prior allocation. If it sees strange behavior such as a free to an address that it does not have a record
of an allocation it will print an error message and increase an error count. Additionally this code keeps track of the total
number of; calls to malloc and free, and the total number of bytes allocated and free.
When you program exits the tracing code will print a summary. If it detects anomalies it will print out error messages.
Additionally if there are allocations for which there were no frees it will print these â€Âleaked†allocations.
To use this code you must include memtrace.h in your c files and also link them with memtrace.o. By default the makefile we distribute compiles and links your source twice to produce two version of your program. One that does not conduct
tracing and the other that does. In partA these executable are respectively: stackclient and stackclient memtrace.
The following is an example of using the memtrace infrastructure in context of PartA.
In the following I first compile my attempted solution using make:
[jappavoo@csa2 handoutA]$ make
cc -std=c99 -g -c stackADT4.c
cc -std=c99 -D MEMTRACE -g -c memtrace.c
cc -std=c99 -g stackclient.c stackADT4.o memtrace.o -o stackclient
cc -std=c99 -D MEMTRACE -g -c stackADT4.c -o stackADT4_memtrace.o
cc -std=c99 -D MEMTRACE -g stackclient.c stackADT4_memtrace.o memtrace.o -o stackclient_memtrace
[jappavoo@csa2 handoutA]$ ls
Makefile memtrace.o stackADT4.c stackclient test.sh
memtrace.c reference_stackclient stackADT4.o stackclient.c uthash.h
memtrace.h stackADT.h stackADT4_memtrace.o stackclient_memtrace
We see that the makefile directs make to run the compiler on our source code twice. Once to produce stackclient
and once to produce stackclient memtrace. Both files are displayed when we run ls.
Running the stackclient we see that it successfully runs and even matches the output from reference stackclient.
[jappavoo@csa2 handoutA]$ ./stackclient
Popped 2 from s1
Popped 1 from s1
Popped goodbye!!! from s2
Popped hello world from s2
s2 is empty
[jappavoo@csa2 handoutA]$ ./reference_stackclient
Popped 2 from s1
Popped 1 from s1
Popped goodbye!!! from s2
Popped hello world from s2
s2 is empty
[jappavoo@csa2 handoutA]$
However, when we run the test script we see that it does not pass the test.
[jappavoo@csa2 handoutA]$ ./test.sh
run stackclient_memtrace : FAIL
score: 0/1
[jappavoo@csa2 handoutA]$
6
Running the memtrace version reveals that there are things wrong with our handling of dynamically allocated memory:
[jappavoo@csa2 handoutA]$ ./stackclient_memtrace
memtrace: 1: malloc(8)=0x2072010 (bytes:8)
memtrace: 2: malloc(8)=0x20722f0 (bytes:16)
memtrace: 3: malloc(4)=0x2072370 (bytes:20)
memtrace: 4: malloc(16)=0x20723f0 (bytes:36)
memtrace: 5: malloc(4)=0x2072470 (bytes:40)
memtrace: 6: malloc(16)=0x20724f0 (bytes:56)
memtrace: 1: free(0x20724f0) (bytes:16) -> 6: malloc(16)=0x20724f0
memtrace: 2: free(0x2072470) (bytes:20) -> 5: malloc(4)=0x2072470
Popped 2 from s1
memtrace: 7: malloc(12)=0x2072470 (bytes:68)
memtrace: 8: malloc(16)=0x20724f0 (bytes:84)
memtrace: 3: free(0x20723f0) (bytes:36) -> 4: malloc(16)=0x20723f0
memtrace: 4: free(0x2072370) (bytes:40) -> 3: malloc(4)=0x2072370
Popped 1 from s1
memtrace: 9: malloc(11)=0x2072370 (bytes:95)
memtrace: 10: malloc(16)=0x20723f0 (bytes:111)
memtrace: 5: free(0x20723f0) (bytes:56) -> 10: malloc(16)=0x20723f0
Popped goodbye!!! from s2
memtrace: 6: free(0x2072370) (bytes:67) -> 9: malloc(11)=0x2072370
memtrace: 7: free(0x20724f0) (bytes:83) -> 8: malloc(16)=0x20724f0
Popped hello world from s2
memtrace: 8: free(0x2072470) (bytes:95) -> 7: malloc(12)=0x2072470
memtrace: 11: malloc(14)=0x2072470 (bytes:125)
memtrace: 12: malloc(16)=0x20724f0 (bytes:141)
memtrace: 9: free(0x20724f0) (bytes:111) -> 12: malloc(16)=0x20724f0
s2 is empty
memtrace: SUMMARY: malloc_cnt=12 bytes=141 free_cnt=9 bytes=111 diff:cnt:3 bytes:30
memtrace: ERROR: 3 more mallocs that frees…leak???
memtrace: ERROR: 30 more bytes malloced that frees…leak???
memtrace; ERROR: leaked: 1: malloc(8)=0x2072010
memtrace; ERROR: leaked: 2: malloc(8)=0x20722f0
memtrace; ERROR: leaked: 11: malloc(14)=0x2072470
[jappavoo@csa2 handoutA]$
The memtrace code produces a line for every call to malloc and every call to free. For malloc calls it prints the size
requested and the address of the newly allocated block. Additionally it firsts prints the count indicating what call to
malloc this is. Eg. the first call to malloc is count 1 and the second is count 2 etc. It also keeps a running total of
the number of bytes allocated with calls to malloc (this number will only go up). Similarly every time a free occurs the
tracing code produces a message that indicates the address being freed and what allocation this corresponds to if it can
find it. If it cannot find a valid allocation that match the free it will print an error message (there are no such bugs in the
above example). Finally when your program is done the memory trace code will print a summary. If it found errors or if
cannot determine that the malloc and frees matched up it will print error lines. In the above we see that the tracing code
determined that 3 allocations were not freed. If it can it will print which allocations where leaked.
Getting familiar understanding the memory trace output can help you not only debug you code but also really understand how dynamic memory works and how to use it correctly.
7
Purchase answer to see full
attachment
