Description
For this lab, you will need to be on a linux system. If you have a linux system or a Mac, you are already ok. If you are Windows, you will need to connect to a linux system — https://its.ucsc.edu/unix-timeshare/tutorials/how-to-connect.html . If you are on your own system, then install BitVise and connect to unix.ucsc.edu . If you are on a lab computer open the “Software” folder on the Desktop, then navigate to “Internet Tools” -> “Unix – SSH”, and double click on the “unix.ucsc.edu” shortcut. If you are doing this, you have two options, use a command line text editor on linux or work locally on your computer and copy over the files to compile and run. While it will have a steeper initial learning curve, it’s suggested to use a text editor on linux, as it’s very easy to forget to copy over a file which can lead to some very frustrating bugs. If you have a text editor you like, then go with that, but if you don’t, emacs with CUA-bindings is probably the closest for people used to working on Windows. To use it, you will need to do the following: 1) Open .emacs by typing $ nano ~/.emacs 2) Type (cua-mode 1) 3) Save the file by pressing Ctrl+o and close nano by pressing Ctrl+x 4) You can now use emacs, for instance, opening up the included code by typing $ emacs tracery_recursion.c 5) The commands for copy (Ctrl+c), cut (Ctrl+x), and paste (Ctrl+v) will be as you expect. But a few won’t be like Find (Ctrl+s), Find Backwards (Ctrl+r), Save (Ctrl+x Ctrl+s), or Exit (Ctrl+x Ctrl+c) This lab will introduce you to C. C is something akin to the grandfather of Java (Java came from C++ and C++ came from Java). It is much closer to the bare metal of how a computer operates, and as such does not have a lot of the niceties that we have gotten used to in Java. This lab once again returns to Tracery, although in this case we’ll be doing something that we took for granted before — splitting a line. To do this, we will become acquainted with C: how to compile a program, how to allocate memory, and how to free memory. You will be doing the following: ● Compiling a C program ● Including the correct standard libraries to read from and print to a command line ● Iterating over the input character by character, constructing strings as you encounter the correct delimiters ● Allocating memory for the strings, filling the strings with the correct characters, and freeing memory when it is no longer needed Open the file tracery_recursion.c that came with the lab. This is where you’ll make all your changes. Inside the file you will see what is basically the simplest C program possible int main(int argc, char** argv){ return 0; } Just as with Java, the entry point to the program is a function called main, but unlike Java, this main function is floating free and is not contained in a class. In fact, C doesn’t have classes: functions and data (struct in C) are completely separate. This main is very similar to the one you’ve seen in Java, and is essentially how one would write the equivalent to public static void main(String[] args) { } in C. The differences being: 1. There is no String class in C, and the C equivalent is a pointer to a location in memory containing characters, char* 2. While C has arrays, arrays are nothing more than a pointer to a memory location storing multiple of a certain type. So the C equivalent to a String[] can be written as a pointer to a location in memory containing pointers to locations in memory containing characters, char**. 3. These pointers don’t have any of the nice helper functions we’ve gotten used to in Java, so there isn’t a way to do anything like argv.length(). Instead, the integer argc contains the number of strings found in argv. C is somewhat nice and gives you this for free, but any other time you have an array of strings, you’ll have to keep track of the count yourself As a start, we’ll print out the arguments passed to program. To do this, we’ll need to include the correct libraries. In Java, you always have access to the System library (where we’ve been using System.out.println), but in C there are very few things available to you without including the correct libraries. In C, to include a library you have to use a preprocessor directive (#) that tells the compiler to include the header file for the file you want to include. This is done with the code: #include NOTE: It is common practice in C to use < > for standard libraries and “ “ for your personal created libraries but the following code snippet #include “stdio.h” #include is equivalent to #include #include “mylibrary.h” The stdio (Standard I/O) library contains just what you would expect, a collection of input and output functions. The first that we will acquaint ourselves with is the C equivalent to System.out.println — printf (formatted print). The arguments to printf are: printf(char* formatting_string, …) Where … is a variable number of arguments based on the formatting string. An example of this is printf(“%d, %d, %0.1f, %c, %s\n”, 1,2,3.4,’a’,”bcd”); which would print the line 1, 2, 3.4, a, bcd Where %d means print an integer, %f means print a floating point number (and the 0.1 means only show the first decimal place), %c means print a character, and %s means print a string. Note that unlike println, printf doesn’t automatically print a new line character, so we have to add that ourselves, ‘\n’. Given this, you now have the tools to print out all of the arguments passed in to the program. Todo 1 ● In TODO 1, you will add code that loops through the arguments and prints each argument on its own line We’ll now compile our program. The command to do that is $ gcc tracery_recursion.c You might get an error, since most of you will probably have written code where you declare your iterator inside your for loop. C doesn’t like that, and originally, you had to place all declarations at the beginning of every function before you did anything else. However, times have changed, and so has C, so now you can add the option $ gcc tracery_recursion.c -std=c99 to tell the compiler to use the C standard that allows this , C 1999. By default, gcc will compile this to a program named a.out which you can run with the command $ ./a.out . However, we would like a more descriptive name, so run the compiler with the additional option $ gcc tracery_recursion.c -std=c99 -o tracery_recursion which will now generate a program called tracery_recursion which we can run with the command $ ./tracery_recursion. When you run tracery_recursion with no arguments, you should get the output tracery_recursion If you were to run with the arguments $ ./tracery_recursion abc def You should get the output tracery_recursion abc def You’ll notice that unlike Java, the first argument in C is always the name of the program you ran, so you’ll need to keep account of that in the future when dealing with the command line. Now we come to memory management in C. We can declare an array in C in a very similar way to in Java: int int_array[3]; Which declares an integer array with 3 elements. Declaring an array like this is referred to as “allocating on the stack.” Stack memory is what you get when you declare a local variable of some type in a function definition. Stack memory is allocated when the function is called and is de-allocated when it returns. The memory area associated with a given function call is called a stack frame or just a frame. A frame includes memory for all local variables, formal parameters, and a pointer to the instruction in the calling function to which control will be transferred after the function returns. The function call stack is literally a stack data structure whose elements are (pointers to) these so-called frames. The frame at the top of the stack corresponds to the function currently executing. Each function call pushes a new frame onto the stack, and each return pops a frame off the stack. The following code will compile but won’t do what we would want: int* make_array(){ // This function returns a pointer to an int int int_array[3]; // Declare an int array on the stack // Set the three int array locations equal to values int_array[0] = 1; int_array[1] = 10; int_array[2] = 100; // The value of the name of an array (without any []) is the // memory location (a pointer) of the beginning of the array. // So the line below returns an int*, which is a pointer to the // beginning of int_array. return int_array; } int main(int argc, char** argv){ // Store the int* returned from make_array() into made_array int* made_array = make_array(); // This won’t work, because the pointer returned from make_array() // is no longer valid when make_array() returns! This is because // int_array was allocated on the call stack, not the heap. printf(“%d\n”,made_array[1]); } The thought would be that this should print 10, but instead this will give us Segmentation fault (core dumped) Which is due to us trying to access memory that is no longer allocated — the int_array we return in make_array essentially ceases to exist once we leave the function. If we want to be able to return something like an array, we have to dynamically allocate the memory, referred to as “allocating on the heap.” Heap memory is not associated with the function call stack and must be explicitly allocated and de-allocated by program instructions. Heap memory is often said to be dynamically allocated, which means that the amount of memory to be used can be determined at run time. Storage in the heap is organized into blocks of contiguous bytes, and each block is designated as either allocated or free. Allocated blocks are reserved for whatever data the programmer wishes to store in them. Free blocks are simply those blocks which are not currently allocated. It is important to remember that the code you write should never access the contents of free blocks. Most bytes in free blocks contain meaningless garbage, but some bytes contain critical information about the locations and sizes of the free and allocated blocks. If a program corrupts that information, it may crash in a way which is mysterious and difficult to diagnose. To do this, we need to include another standard library, stdlib.h. stdlib gives us a lot of functions, but the ones we care about for dynamic memory are: void* malloc (size_t size); void* calloc (size_t num, size_t size); void free (void* ptr); void* is similar to Object in Java: it is a generic pointer to anything, but we don’t know anything about the type. When malloc or calloc are called, they allocate a block of memory (size bytes for malloc and num*size bytes for calloc), and return a pointer to the first location in that block of memory. So, the a dynamic version of the code above is: int* make_array(){ // Allocate enough memory to store the integers on the heap // instead of the stack. int* int_array = malloc(sizeof(int)*3); int_array[0] = 1; int_array[1] = 10; int_array[2] = 100; return int_array; } int main(int argc, char** argv){ int* made_array = make_array(); // Now this printf will work because the memory for int_array // stays around after make_array disappears. printf(“%d\n”,made_array[1]); } We use, sizeof(int) , to tell the compiler how many bytes we want to use for each element of the array. In this case we want to allocate enough memory to store 3 ints. We use the function sizeof() because how many bytes it takes to store an integer in C is dependent on the computer we are running it on. So sizeof(int) will return different values on different computers, and our code will now work on different computers. While malloc is useful, calloc is a slightly better way to do this. calloc has two separate parameters, num and size, so we don’t have to do the multiplication (it just looks a bit cleaner), and it zeroes out the new memory block. This might not seem like much, but it’s actually very helpful for us as programmers. When malloc returns a block of memory, that block might still have stuff in it. A very easy mistake to make is to not properly initialize your memory, and this can be hard to catch as the stuff in the block of memory might be close enough to not look obviously wrong. So, the better way to write the above function is: int* make_array(){ int* int_array = calloc(3,sizeof(int)); int_array[0] = 1; int_array[1] = 10; int_array[2] = 100; return int_array; } int main(int argc, char** argv){ int* made_array = make_array(); printf(“%d\n”,made_array[1]); } If you were to compile and run this code, it would seem to do exactly what you think it should. But there’s one thing it is missing. Unlike Java, we are responsible for all of the memory we dynamically allocate in C. Java has garbage collection and figures out on its own what to do with dynamically allocated memory (which in Java is any object created with the new keyword). But in C this code will have a memory leak. This means that memory is allocated and never freed, which will eventually cause your computer to run out of memory (if the offending code was run enough). So, we need to add the line free(made_array); to the end of the program to release the memory back. int* make_array(){ int* int_array = calloc(3,sizeof(int)); int_array[0] = 1; int_array[1] = 10; int_array[2] = 100; return int_array; } int main(int argc, char** argv){ int* made_array = make_array(); printf(“%d\n”,made_array[1]); free(made_array); } Having seen how we can allocate and free memory — it’s now time to implement a function that will make a new string, and fill it with the contents of the buffer, up to a certain point. Todo 2 ● Now implement the code for char* make_string_from(char* from, int count) ● This function will allocate memory for a new string of size count+1. The plus 1 is because C strings are referred to as null-terminated (the last element of the string is the \0 (a zero) and it tells functions like printf that the end of the string has been reached). ● Loop through the characters in from up to index count and put them into your new string ● Finally, return the new string. Now, we are going to read in from standard input, as we did in the last lab. Unlike the last lab, we are going to be reading in one character at a time. You will run your code with $ ./tracery_recursion abc def < grammar-story.txt which is functionally equivalent to $ cat grammar-story.txt | ./tracery_recursion abc def So, we are going to loop through the input one character at a time, checking to see what those characters are, storing some of them, and making and printing strings for others. Recall that a line in a grammar looks like color:red,blue,green Where everything before a ‘:’ is the name of the rule, and everything between ‘,’ is an expansion. Before, all of the strings we received were split on the new lines, so we also have to be aware of them. The above actually looks like: “color:red,blue,green\n” Because the newline character is denoted as ‘\n’. Before this next part, we are going to declare a few variables — char_buffer, buffer_index, rule, and expansion. char_buffer will be a statically allocated array of characters, that we will fill up with the characters that we read in one at a time, using getchar(). Whenever we read in a character that isn’t a ‘:’, ‘,’, ‘\n’, or EOF we will put that character into char_buffer, moving buffer_index up by one. When we read a ‘:’, we know that everything in char_buffer up to buffer_index is a rule, and we’ll set rule to be a new string with those characters using the helper function we made in Todo 2. We will then reset buffer_index to 0. Similarly, whenever we read a ‘,’ or ‘\n’ we know that we’ve just finished reading an expansion and we will set expansion to be a new string with the correct characters from char_buffer. We will now print “A potential expansion of rule ” is ‘<EXPANSION’>\n” e.g., with the above line, we should expect to see: A potential expansion of rule ‘color’ is ‘red’ A potential expansion of rule ‘color’ is ‘blue’ A potential expansion of rule ‘color’ is ‘green’ If the character is EOF, then we have hit the end of the file, we are done. Todo 3 ● Use getchar(), which takes a character from standard input one at a time, to loop through all of the input in standard input, until we hit the EOF character. EOF is a constant (like null) that you can use to tell that you’ve reached the end of the input. ● If the character is a ‘:’ , then make a new string called rule with the contents of the buffer up to the current index, and reset buffer_index to 0. ● If the character is either a ‘,’ or ‘\n’ then we know we have just read in an expansion, so make a new string called expansion with the contents of the buffer up to the current index, and reset the index to 0 ● Otherwise, put the character into char_buffer, a statically allocated character array of size 1000, moving to the next index after you read a character ● Whenever you read in an expansion — you should print the following line “A potential expansion of rule ” is ‘<EXPANSION’>\n” – where is the last rule you read in, and is the expansion you just read in. ● As a final note, make sure you free all memory you allocate. A good practice to get in is to initialize all pointers to NULL. When you want to free a pointer, check to see if it is NULL. If it isn’t, then free it and set it to NULL. If it is, then don’t free it, since it’s already pointing to nothing). To check if your program is properly freeing all memory use a tool called valgrind to check your code like so: $ valgrind –leak-check=full -v ./tracery_recursion < grammar-story.txt Which will tell you if you have a memory-leak, and if so, where. Expected Behavior If you run your code with $ ./tracery_recursion < grammar-story.txt You should get the output An expansion for rule ‘animal’ is ‘cat’ An expansion for rule ‘animal’ is ’emu’ An expansion for rule ‘animal’ is ‘okapi’ An expansion for rule ’emotion’ is ‘happy’ An expansion for rule ’emotion’ is ‘sad’ An expansion for rule ’emotion’ is ‘elated’ An expansion for rule ’emotion’ is ‘curious’ An expansion for rule ’emotion’ is ‘sleepy’ An expansion for rule ‘color’ is ‘red’ An expansion for rule ‘color’ is ‘green’ An expansion for rule ‘color’ is ‘blue’ An expansion for rule ‘name’ is ’emily’ An expansion for rule ‘name’ is ‘luis’ An expansion for rule ‘name’ is ‘otavio’ An expansion for rule ‘name’ is ‘anna’ An expansion for rule ‘name’ is ‘charlie’ An expansion for rule ‘character’ is ‘#name# the #adjective# #animal#’ An expansion for rule ‘place’ is ‘school’ An expansion for rule ‘place’ is ‘the beach’ An expansion for rule ‘place’ is ‘the zoo’ An expansion for rule ‘place’ is ‘Burning Man’ An expansion for rule ‘adjective’ is ‘#color#’ An expansion for rule ‘adjective’ is ‘#emotion#’ An expansion for rule ‘origin’ is ‘once #character# and #character# went to #place#’ Grading TODO 1: 20 points TODO 2: 30 points TODO 3: 35 points Style: 15 points As a note, it is far more important to turn in code that compiles and is missing a TODO or only partially does a TODO, than it is to attempt a TODO and make your code uncompilable. If you code doesn’t compile, you will receive 40 points off, so make sure your code compiles before you submit it (even if you are missing a TODO). Turning the code in ● Create a directory with the following name: _lab3 where you replace with your actual student ID. For example, if your student ID is 1234567, then the directory name is 1234567_lab3. ● Put a copy of your edited tracery_recursion.c file in the directory. ● Compress the folder using zip. Zip is a compression utility available on mac, linux and windows that can compress a directory into a single file. This should result in a file named _lab3.zip (with replaced with your real ID of course). ● Upload the zip file through the page for Lab 3 in canvas.
