Mimir:Spring 2019 Lectures

From Openitware
Revision as of 14:12, 1 May 2019 by Mcy59 (Talk | contribs)

Jump to: navigation, search


Week 1 - Introduction: categorizing programming languages

Content author Mike Jonas


  • How to Categorize a programming language
    • by paradigm: imperative, procedural, functional, logic, visual, oop
    • by its use: development vs utility
    • by implementation: interpreted, compiled, hybrid
    • by attribute: data typed, free format, indentation driven
    • by generation: 1st, 2nd, 3rd, 4th, 5th

Categorizing programming Languages

How do we discuss programming languages? What forms do we use to analyze the effectiveness of a language, be it a newly created one or one that has been around for a long time. We'll briefly hit upon five, some standard and some more practical. Note that here we will not delve into the specifics of each of the methods a programming language can be classified, that will be left to specific lectures following on subsequent weeks. We merely introduce the notions here.

Classifying by Paradigm

We generally look to paradigms (imperative, procedural, functional, logic, visual, oop, multi) when we discuss programming languages. These are tried and true classifications that a language fits into to. However, paradigm really only focus how the programmer is impacted when developing code and says little about how the language fits into the development cycle.

Classifying by Use

A less common way to look at programming languages is by its purported use, mainly because programmers have the freedom to apply any language to any solution. However, this does not always yield optimal results. Should one use a scripting language to develop a word processor? Some languages that gain public support end up being transformed and its purpose changes. Sometimes this results in a better, more powerful language and sometimes it becomes somewhat of a mess. Python is such a language that has become popular as now a development language.

Classifying by Implementation

Languages are generally interpreted or compiled (details to follow in week 2). There are some that use a hybrid approach (Java) compiling into an intermediate form and then using a virtual machine to run them. Is that virtual machine an interpreter or an emulator? That question requires further thought, however, classifying languages by implementation is a popular means to gauge effectiveness of use by programmers.

Classifying by Attributes

It could be argued that how a language is implemented is just an attribute, we separated it out (above) because it is a profound means to look at a language. In actuality, one could look at most of what has already been discussed as an attribute of the language. So this is a catch-all for smaller distinctions that may or may not deserve their own section. One such attribute is whether a language is "typed" or not (we mean data type here). Another is whether the language is free format (most) or uses indentation (Python) to determine block structure. Is the language case sensitive?

Classifying by Generation

A much less used (and somewhat older) means of talking about a programming language. First generation languages were the processor's code (aka machine code). Second generation languages mapped this machine code to more human readable form of an Assembly Language (a one-to-one mapping of mnemonics to instructions). Third generation languages gets us to where we are now with modern high-level languages (giving a one-to-many mapping from code to instructions). There are also fourth generation classifications focusing on systems such as DB's and fifth generation classifications designed to make the computer solve a given problem without the programmer (i.e. expert systems).

Week 2 - Compilers, interpreters and BNF grammars

Content authors (Group #1) Ethan Jarzombek & Kevin Richardson


    • Tools used in Programming Languages
      • Compiler
        • what is it and how does it work (add picture)
        • pros and cons of compiler
      • Interpreter
        • what is it and how does it work (add picture)
        • pros and cons of an interpreter
      • How does an Assembler fit into this picture
        • explain what an assembler is
    • Grammars - what are their purpose
      • Backus Naur form - define and describe BNF and give examples
      • Context Free Grammars (CFG) - define and discuss
        • brief description explaining why CFG's are best for programming languages
      • Parsing - what is it and how does it relate to both grammars
        • where does it fit in with compilers and interpreter

Tools in Programming Languages

When selecting a programming language to use, there are many different factors to take into consideration. One feature that deserves some thought is whether the language compiles or interprets the source code. The way a computer interprets what you are telling it to do greatly affects the way it is executed. Both methods have their pros and cons, so it is important to know and understand the key differences before you dive right in.


Compilers are distinguished by their ability to convert an entire script into executable machine code all at once to be able to run instantly on other machines. Once the source code is translated into machine code, you are left with two separate files: your original source code, and an executable file. The executable file is essentially 1's and 0's known as machine code, which can be understood by your computer, but not the human eye (without a lot of work). The source code can remain on your system, and the executable can then be used or sent to any other machine to run.

What it is and how it works

A program that compiles its source code does so in stages. The source code first runs through a preprocessor to manage all of the files' imports. A parser is then used to check if the syntax is accurate and build a parse tree. From there, the code can then be generated and optimized for execution. A linker, the last stage of the compiler, finalizes the transaction of turning the file into an executable. Once the executable has been created, it is finally ready to be run by the user.


Pros and Cons

The initial process of compiling code into an executable might take some time, but will be much faster in the long run since the executable file is ready to go whenever you run it. Having the source code compiled into an executable also allows you to keep the source code private, since only the executable file is shared (which is written in machine code). The down-side to compiling your programs means that your executable is not cross-platform compatible. This means you would have to create separate binaries (executable machine code) for each type of operating system to understand, making it less flexible or interactive than interpreters. In addition to this, compiling also requires an extra compiling step while you are developing the code, meaning every time you want to run your code for debugging purposes, it will have to be compiled. This may not seem so bad, but can prove to be quite the nuisance for larger programs that require a lot of testing.



Interpreters are distinguished by the way they translate your source code line by line as the program is run, rather than doing it all at once as a compiler does. Sending your source code directly to the consumer, or they can then download the appropriate interpreter program for their machine to translate the program during run-time.

What it is and how it works

A program that is interpreted on a machine is translated as it runs. This means that each line of code is converted to binary machine code and executed ont he user's machine before moving to the next line of code.


Pros and Cons

Interpreting code can be useful in that it is cross-platform compatible, meaning the programmer only needs to distribute one file for all systems, and let the interpreter program on the consumer's machine do the rest. In addition to this, debugging is made simpler since the source code does not need to be compiled every time during development. Translating code line-by-line can be useful in some situations, but may also prove to be inefficient in others. For instance, having to translate each line of code every time the program runs makes it much slower than a fully compiled executable. Also, since the source code is distributed to the users rather than an almost cryptic executable file, the source code is open free to the public.



Both compiled and interpreted programs are written in a high level fairly easy-to-read programming language, then translated into machine code to be understood by a computer. An assembler, on the other hand, takes in a low level language known as assembly language, which is essentially the first step up from binary code. It takes blocks of binary and groups them together into more manageable commands to be used by humans for coding. Simply writing machine code in itself would be near impossible due to its complex and cumbersome nature of millions of 1's and 0's, so assembly turns those bytes of unmanageable data into something easier to understand and use. Once your assembly program is written, an assembler is used to convert it to machine code for execution.

What is an assembler?

An assembler is a program that converts assembly language into machine code. It works much like a compiler in that it produces a single executable file rather than line-by-line like an interpreter. The only difference is, that assemblers can only handle low-level languages. Every processor interprets machine code differently, so there is different assembly language for every type of machine.


Programming languages can be described by both their semantics and the syntax of the language. The semantics of a language describes the process a computer follows when executing a program in a specific language. In essence, semantics indicates the meaning of every possible construction that is possible within that particular programming language. Syntax defines the rules for arranging the structure of a programming language. While the semantics of a programing language can be described in multiple different ways, one technology is typically used to describe the syntax of a language, which are known as context free grammars.

Backus-Naur Form

Backus-Naur Form (BNF), also commonly referred to as Backus-Naur notation is a formal method of notation used to describe a programming language. The goal of Backus-Naur form is to ensure that there is absolutely no ambiguity or conflicting information when defining a programming language. Production rules, used by Backus-Naur Form grammars, resemble mathematical expressions are used to define the set of strings and symbols used in a programming language. Below is an example of BNF notation.

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

A production rule states that the symbol on the left hand side of the "::=" must be replaced with one of the alternatives on the right side. The bar symbols on the right side of the above expression separate the alternative options as to what <digit> can be.

Context Free Grammars

Context Free Grammars (CFG) are used to generate context free languages by taking sets of variables defined recursively in terms of one another by a set of production rules. Context free grammars are referred to as such because the production rules in the grammar can be applied regardless of context. Context free grammars are typically made up of the following components: terminal symbols, non-terminal symbols (also referred to as variables), production rules, and a start symbol. Terminal symbols are characters that appear in the language or strings generated by the grammar. In context free grammars terminal symbols never appear on the left side of the production rule expression and always appear on the right side. Non-terminal symbols or variables, act as placeholders for combinations of terminal symbols that can be generated by the non-terminal symbols. Typically non-terminal symbols appear on the left hand side of the production rule but can also be included on the right side of the expression as well. Production rules, as mentioned above, are the rules for replacing non-terminal symbols. A start symbol is a special non-terminal symbol that appears in the initial line of the grammar. Languages that can be generated using regular expressions can be generated by a context-free grammar as well.



Parsing involves analyzing a series of symbols to determine its grammatical structure with respect to a given formal grammar. A parser will then build a data structure based on these symbols and when used with a compiler or interpreter an executable program can be created. Parsing considers a grammar and a string of text and applies two essential questions. First, does the string exist in the language of the grammar? Secondly, what is the structure of the string relative to the grammar?

Week 3 (& 2) - Programming paradigms; an overview of Perl

Content authors (Group #2) Adam Harney & Daniel Scott


  • Programming Paradigms - what is a programming paradigm?
    • Define each paradigm and give language example
      • Imperative, Procedural, Functional, Logic, Visual, OOP, Multi
  • Overview of Perl - give a one paragraph introduction about the history of the language
    • A couple of paragraphs discussing its basic structure (i.e. it's a statement based/imperative language)
      • add an example to highlight that
    • Types in Perl - one paragraph discussion of three types:
      • scalar, array, hash - add an example to show syntax
    • Print statement - one paragraph discussion of what it's used for
      • add example to show syntax on how to construct printed strings via concatenation operator "."
    • Conditionals - one paragraph discussion of the two types if & if/else
      • add example to show syntax of if
      • add example to show syntax of if/else
    • Loops - one paragraph discussion of both while and for loops
      • add example to show syntax of while loop
      • add example to show syntax of for loop
    • File I/O - one paragraph discussion of file i/o
      • add example to show syntax of how to read from a file (use a while loop like we did in class)
    • Subroutines - one paragraph discussion of subroutines (i.e. what they are)
      • add example to show syntax of a subroutine, specifically how to pass parameters

Programming Paradigms - what is a programming paradigm?

Programming Paradigms are a ways in which you can classify programming languages based on several factors such as features, organization, and execution model. Programming languages do not always neatly fall into one category, and can exhibit traits of several different paradigms.


Examples: BASIC, Perl

Imperative Programming is made up of step by step commands, which are all executed in order from beginning to end. These commands can change variable values, do math, or otherwise change the state of the program, but they do not allow you to call sub routines. An advantage of this type of language is that you have much more knowledge about how and in what order your code is being executed, although you are much more limited in what you can do.


Examples: C, C#, COBOL

The procedural paradigm is often considered a subset of the imperative paradigm. All procedural programming languages run through one or more subroutines (aka functions).


Examples: Lisp

Functional programming is completely based on mathematical functions. Functional languages have what are called pure functions, which means functions that have no side effects and no state. This means that recursion is incredibly important for functional languages.


Examples: Mercury

Logical programming is based entirely on logical reasoning, facts, and rules. Code in this language looks more like pseudo code than languages such as C++ and Java. A valid piece of code in a logical programming language could look like "x is true if y and z are false"


Examples: Scratch

Visual programming languages are coded using visual elements, such as blocks that can be dragged and dropped or manipulatable flow charts. These languages are very useful as learning tools, as they can be used by kids, or people who have a hard time visualizing the logic of a traditional programming language.


Examples: C++, Java

Object Oriented Programming focuses more on defining and interacting with objects than traditional languages, which were just about processing commands from the top down. Object Oriented languages allow multiple objects from a single class, as well as sub classes which can inherit traits of their parent classes. This can cut down on repeated code, and help organize large programs that need to keep track of tons of data.


Examples: Almost all of them

Multi-Paradigm languages are simply languages that do not strictly adhere to any of the above listed paradigms. Many languages can be considered multi-paradigm.

Overview of Perl

Perl is a Unix Scripting Language invented in 1987 by Larry Wall. It was created because Wall was unhappy with the functionality of the languages available at the time such as C. Perl has gone through several iterations throughout the years, with Perl 5 being the definitive version for many years, and Perl 6 being the most recent version.


Perl is a multi-paradigm language. Older versions of the language are entirely in the imperative paradigm, meaning that functions are processed line by line. However, more recent versions of Perl have given the language features of the functional and object-oriented paradigms.

$msg = "hi";
if ($msg eq "hi")
    print "hello\n";

Here is an example of a typical piece of Perl Code

Types in Perl

Unlike most languages, Perl only utilizes three types of variables. These variables are the bare basics necessary to emulate the same functions of the variables that are not available in Perl. While a language like Python might use dictionaries, Perl can combine two different types of variables to gain the same effect (hashes and arrays.) Though they may be few in number, they distinguish themselves in their own way. Here are the distinguishing traits and syntax of Perl data types:

Scalar Variables - Always preceded by a '$', a scalar variable is used to contain simple single values. For example, a scalar variable may hold an integer, string, or Boolean.

 $variable = 1

Array Variables - An ordered list of scalar values. An array is always preceded by a '@' symbol. To access a place in the list, call upon it as a scalar variable followed by the list position within brackets.

 @list = (1, 2, 3)

Hashes - A set consisting of a key and a value. Always preceded by a '%' symbol followed by a key and the value or variable within curly braces. To initialize one, however, a key must precede a ',' and then the value assigned to it.

 %Identification = ("John", 12345)

Print Statement

Print statements in Perl are quite similar to the print statements in other similar language. Much like in python it starts with the command which in this case is "print" then enclosed in quotes the string that the user desires to be printed. This simple and common command does almost exactly as it would in any other language, printing the string onto the screen with minimal formatting. Less common traits might include the finer details of the print statement's usage. For example, the use of single and double quotes when it comes to the content being printed. While normally, with double quotes, a line break or tab character sequence would be interpreted as it's designated action, but with single quotes, it is printed literally as the character sequence is typed.



File I/O


Week 4 - Language concepts: statements, control flow, expressons & operators

Content authors (Group #3) George Harvey & Wesley Krol


  • Language concepts: statements, control flow and expressions
    • Statements - give definition of statement
      • How this impacts paradigms
        • i.e. imperative is statement based but others do what differently?
      • discuss implied sequential nature
        • how program only sees current line and keeps state
        • perhaps draw a picture
    • Control flow - discuss how it manipulates execution
      • Draw picture showing sequential, conditional & loop
      • discuss how this adds structure to code to avoid spaghetti logic
      • Two categories - define, provide examples and a pictorial representation
        • <s>Conditional - represents if, if/else, switch (what else)
        • Loops - represents for, while, do/while (anything else?)
    • Expressions - define
      • Boolean - examples
      • Numeric - examples
    • Operators - explain the order of operations and how it affects execution.
      • give details about PEMDAS and examples
      • contrast with other standards



A statement is a block of code that executes some action. A statement can be one or several lines and also be comprised of other embedded statements. For example a variable assignment such as num = 32; is one statement. The previous example would be written on a single, however, a statement can be multiple lines of code and contain other statements. For example lets define a method in java that assigns the value 1 to a variable.

In the above example the method itself is a statement that includes everything within the "{ }" however, within the brackets is another statement the int num = 2.

Control Flow

Control is an integral part in any language as it is sequence the language executes statements. Computing languages have a fundamental practice of going sequentially, that is, line by line, however in most languages there are certain statements that adjust the control from being line to line and dictate what the languages overall control flow is. These statements can include but are not limited to, comparisons ( if, else if, else ), switches, loops (for, do while, while, repeat), goto, etc... These statements can cause the control flow to deviate from the line by line sequence and "jump around" to other sections. The first example shows a basic line by line control whereas the second shows how control flow can change with certain statements. The lines are numbered by order of execution.

Example 1:

Example 2:

Week 5 (& 4) - An overview Lisp

Content authors (Group #4) Dylan Durand & Brandon Peterson


  • Lisp - explain the paradigm and what it implies for Lisp.
    • A little history, background and application of Lisp (i.e. Artificial Intelligence).
    • Give a brief overview of the language with Lisp example of each
      • Recursion in Lisp - discuss and give a coding example (i.e. fibonacci or factorial)
      • Basic components - discuss
        • atoms, lists and s-expressions
      • Some common functions
        • Assignment: set (remind readers to quote arguments with ' to prevent evaluation)
        • Math functions: +, -, *, /
        • List functions: list, cons, append, car, cdr
        • Defining functions: defun
        • Conditional functions: cond, null
      • Examples programs in Lisp
        • factorial function
        • a reverse function
        • a function that doubles each element in list

Some Common Functions


In LISP, variable assignment is done with SET function. The SET function takes two arguments, the symbol being assigned and what is assigned to that variable. For instance, ( set 'x 30 ) would set the symbol x to 30. It is important to note that there must be a ' in front of x, otherwise LISP will attempt to evaluate it. Because of this, there is a common shortcut in the form of the command SETQ. SETQ works just like SET, except that it puts an apostrophe in front of the first argument automatically. That means that the above code is equivalent to (setq x 30). LISP is typeless, so SET can be used to assign anything to a symbol. This includes lists, or other symbols.

Math Functions

LISP supports the four basic math operations using the operators +, -, * and /. Like all of LISP's other functions, they are called using pre-fix notation instead of the more common in-fix method. That means that an expression like 8 + 2 * 5 / 1 -10 in LISP would instead look like (- (+ 8 (/ (* 2 5) 1) ) 10 )

List Functions

Lists are one of the two most important data types in LISP. Fortunately, LISP has several functions predefined for working with and manipulating lists. These functions include list, cons, append, car and cdr. These functions may not be straightforward at first, but they each fulfill an important role in the programming language. First is list, which is fairly simple.

The list function returns the argument passed into it as a list. For instance (list 'a) returns (A). List can be given any number of arguments. If one wanted to create the list (A B C), they could use the command (list 'a 'b 'c) .

Append is another command that is easy to guess. Append adds the second list to the end of the first list passed in as arguments. Let's say that the user wants to add the symbol d to the list (A B C). Instead of creating a new list, one could type (append (list 'a 'b 'c) (list 'd)) .

The cons function is similar to append, but it has a few important distinctions. For one, cons adds the first argument to the beginning of the second argument. Secondly, it adds the entire argument instead of the contents of it. This is a subtle distinction that is best illustrated with an example. Let's see what happens when we try to create the list (A B C D) from the previous example, but this time using cons instead of append. The code (cons (list 'a 'b 'c) (list 'd) instead returns ( (A B C) D ). Cons added the list (A B C) to the list ( D ) instead of appending the contents. (car '(a b c)) The last two list functions, car and cdr, are incredibly important for iterating through lists in LISP. Using the car function on a list returns the first element in that list. For example (car '(a b c)) will print A to the console. Cdr on the other hand, does the opposite of car. Cdr returns a list containing everything except the first element of the list given as an argument. For comparison (cdr '(a b c)) returns (B C). These two functions, along with recursive function calls, allow a programmer to traverse a list in LISP.

Defining Functions

In order to define functions in Lisp, one must use the Defun command. This command is in the form of defun <function_name> (<arguments>) (<body>). Because Lisp is a symbolic language, there are no restrictions on what a function can be named. A function can have zero or more arguments. There are some additional ways to define arguments to give a function increased functionality. For instance one can specify certain parameters as &optional. This means that if the function is called with more arguments than required, they will be assigned to the symbols listed after the &optional symbol. For example, defun echo (string &optional number) ... . This defines a function called echo which takes one argument, string. If echo is called with two arguments, the second argument will be assigned to the symbol number. Otherwise, number will default to nil. If a programmer wants to change the default value of an optional parameter, they can enter a list after the &optional symbol. The list contains the symbol being assigned and the value assigned to it. For instance, defun echo (string &optional (number 10)) ... will set number to either the second parameter, or 10 if there is no second parameter. Lastly, to define a function with a variable number of arguments, one can use the &rest command. This stores any additional parameters given to the function in a list called &rest, which can be called within the body of the function. The body of the function defines what the program will execute when that function is called. By default the function will return the results of the last command executed.

Conditional Functions

Conditional functions in Lisp can be created with the command cond. This command may look strange to people used to programming in other languages, but it is actually quite simple. Cond is called in the form of cond ( (<test> <result>) ) ... . Essentially, cond takes a list of if then statements contained in a list. The first value in each list is the condition that is being checked. The second value is what will be evaluated if the previous condition is true. Cond can be given any number of arguments. In order to create a default case, one can put t as the first value in a conditional list. T stands for true, and cond will evaluate that expression of none of the previous conditions evaluate to true. This is equivalent to an else statement in other languages. Here is an example of a cond statement in Lisp. cond( ((= a 10) (- a 10)) (t (+ a 1) ) When this code runs, it will check if the symbol a evaluates to 10. If it does, it will subtract 10 from a. Otherwise it will increase a by 1.

Example Programs in Lisp


This function takes a number and returns the factorial of that number.

   (defun fact (n)
           ((= n 0) 1 )
           (t (* n (fact (- n 1))))


This function returns the nth number in the fibonacci sequence, where fibonacci of n = (fib n-1) + (fib n-2).

   (defun fib (n)
           ((= n 0) 0)
           ((= n 1) 1 )
           (t (+ (fib(- n 1)) (fib (- n 2))))

Double List

This function takes a list as input and returns a list where each element is equal to 2 the element in the original list.

   (defun double (n)
           ((null (car n)) nil)
           (t (cons (* 2 (car n)) (double (cdr n))))

Week 6 (& 5) - Language concepts: variable types, scope, implementation & parameter passing

Content authors (Group #5) Miranda Thompson & Jim Canavan


  • Variables (what are variables in computer Programming?)
    • How are variables represented (it's three values: address, size, information)
  • Data Types (what does type mean for a variable and why is it important -- i.e. reserving memory)
    • Strong vs weak typed language (definition with examples)
    • Dynamic vs static typed language (definition with examples)
    • Data types (each with definition and a simple example if needed)
    • Primitive (discuss/list common ones: i.e. int, flat, char, bool)
    • Complex (i.e. structs/records, classes)
  • Scope (define and discuss scope levels)
    • Who can see a variable (define and discuss global vs local scope)
    • Local
    • Global
    • parameter
    • Variable scope in OOP (reasoning behind using local and global in OOP)
  • Parameter Passing
    • Pass by value
      • Provide example in Java
    • Pass by reference
      • Provide example in C++
    • Briefly mention others like In/out but don't discuss them


A variable is an entity that is used as a reference point for the variable's stored information. The information stored in the variable may change when needed. A good variable name will describe what information that variable contains. Variables are used in programming so that the operations of code on the variable remain the same, but the stored information of that variable may change. An easy to understand example of a variable is found in basic algebra, for example x=y+z. Both variables y & z can store different information to produce x whose stored information will also change depending on y & z.

There are (6) properties that define variables that are extremely important to memorize.

  • Name - Symbolic representation of the data being stored with the variable. Example: Name_First, Name_Last, DOB, Gender, Phone_Num
  • Type - Represents what that data stored as. Example Name_first & Name_last suggests a String data type. DOB suggests a Date data type, and Phone_Num suggests an integer data type
  • Value - What the variable literally is. Example Name_first = "programming" we know the value of Name_first is programming and that it is a string
  • Scope - Defines which functions within the code have access to variables. Scope is detailed below.
  • Life Time - Closely tied to Scope, the lifetime of a variable is when the program reaches the line of code where they are "declared". Variables "die" when the program leaves the "Scope" of the variable.
  • Location (in Memory) - The space where the variable is stored in bits.

Representing Variables

  • Addressing:

All variables are loaded into the computer's memory in segments, typically as bytes. These segments are then assigned anaddress so that the processor can access the address containing the variable. Addressing has it's own section bellow which has more detail on addressing.

  • Size :

Size refers to how many bytes are needed to allocate the specified variable to memory and address it. The built-in data types that languages provide to programmers define the amount of bytes for each data type. This is important for the compiler as the compiler will reserve the necessary bytes in order to create a variable in question.

  • Information :

Data Types

Data type is an attribute of data which tells the compiler or interpreter how the programmer intends to use that data. For example, an integer is different from a string and defining "9" attribute to be an integer allows the user and compiler/interpreter to treat "9" as an integer versus a string. There are (2) data types, Primitive & Complex

  • Primitive-

Variables that do not contain value directly, but instead reference an object. An example of a primitive variable is a boolean or a float because booleans and floats do not have values themselves they point to their assignments of a true & false for boolean, or decimal number for float. These are very basic data types, and in most languages these are built-in.

  • Complex-

A data structure that isn't a primitive provided by the language. In other words, these are variables which are composites of existing data types. Complex data types should not be confused with aggregate data types which are data types like lists & arrays. An example of this is Date Time provided in Java. Date Time has (3) primitive data structures bundled into (1) date time complex structure. It is important to note, that date time cannot be broken down into smaller units. To break down date time you would just have 3 primitive data structures.

Common Primitive Data Types in Java:

  • Integer : Whole numbers where the size of the values depend on the type of integer the programmer chooses to use.

Brave 2019-04-16 14-52-06.png

  • Floating Point : Represent numbers with a fractional part. Single precision floating point numbers occupy 4 bytes and Double precision floating point numbers occupy 8 bytes.
  • Character : Stores character constants as a size of 2 bytes.
  • Boolean : Stores values as either True or False


Scope refers to the visibility of variables given the privileges of the user interacting with the program.

  • Who can see a variable-
    • An easy to understand example of scope is how users interact with variables differently such as front-end users, administrators, and super-admins. A front-end user would see fewer variables than an admin would. An example of this might be a reporting program for a business. A front-end user using a reporting program may only be able to see their own sales numbers and may have restrictions on how that data is sliced, for example not being able to view an average cost for a product. Admins, on the other hand, are able to view this data. Another more meaningful way, with regards to programming, to think about Scope is; how do programs access these variables? An example can be a function that only accesses the Local Variable versus a Global Variable. Using functions that only manipulate local variables may be necessary as to not damage the data from the originating source. There are (3) levels of scope wich a program can apply the rules of scope to, Global, Local and Parameter
    • Global-
      • Variables that are referenced and accessible throughout the entire program.
    • Local-
      • Variables that are referenced and accessible in a function or block that in some cases may override the same variable if it were defined in a larger scope. Consider the image below, where $a is globally set to (1). It is then re-defined locally to be (2), then called. $a is called twice but takes the local variable value.


  • Parameter-
    • A Parameter is the symbolic name for "data" that passes through a function. Consider the mathematical problem 1 + 2. We can assign a=1, b=2 and use a function add(a, b) to get the answer 3. Within the function, a & b are parameters. Outside of the context of the function, a & b are primitive data structures. More specifically, the example demonstrates the use of a Formal Parameter being treated as local variable.

Passing Parameters

There are (3) Calling Modes in which parameters can be passed through functions or procedures. Each Mode uniquely treats how parameters are accessed, as well as different degrees of efficiency in accessing those parameters being passed which is explained in the "Stack & Address" section below.

  • Call by Value

Call by Value protects the actual parameter value. Regardless of what the subprogram does, the parameter can not be changed.

  • Call by Reference
  • Call by Name

Stack & Address

  • Stack in programming is an array or list that follows a particular order which is performed.
    • Stack Frame-
      • Stack frame is a frame that has data that gets pushed up onto the stack.


  • Memory Access of Stack Frame-
    • Difference Between "Call by Reference" and "Call by value"


Week 7 (& 6) - An overview of Scratch

Content authors (Group #6) Xavier Doyle & Yurii Gromakov


  • What is a visual Programming Language
    • brief description of its paradigm
    • advantages and disadvantages of Scratch
  • A tutorial on Scratch with example
    • pictorial view of Scratch Window
    • explain Scratch block types.
      • i.e.Scratch data types.
    • functionalities of each pane: list categories and describe
      • i.e. the 8 main for 1.4 (maybe more for 2.0)
      • short code example for each category
      • Note: give a feel of the language without being complete
    • what are sprites - how do they compare to objects
    • Complexity in Scratch
      • Race Conditions
      • How to avoid Race Condition
      • Concurrency issues


No classes

Week 9 - Language usage (utility, development) and the modern paradigm: OOP vs procedural

Content authors (Group #5) Miranda Thompson & Jim Canavan


  • Language usage - utility vs development. - Include a brief discussion of what is implied here.</s>
    • Development - elaborate on what makes a language this</s>
      • What makes a language transform from utility to development</s>
    • Utility - what makes a language this</s>
      • Usage of web development and scripting languages</s>
  • Comparison of the modern paradigm - OOP vs procedural.</s>
    • Structure put on language and its purpose</s>
      • Typed languages - restricts freedom to reduce error</s>
      • how a struct (record) in procedural transformed into a class in OOP</s>
      • Fundamentals structure of OOP</s>
        • Encapsulation - reduces access to data (example)</s>
        • Inheritance - adds hiarchy to data reuse (example)</s>
        • Polymorphism - allows generality of data (example)</s>
    • A quick contrast with pre-procedural paradigm - imperative</s>
      • lacks structure - no subroutines</s>
      • spaghetti logic - "go-to" dilema</s>
      • An example of OOP vs Procedural would be good here </s>

        • Fundamentals structure of OOP
          • Ecapsulation

Encapsulation is Encapsulation.jpg

          • Inheritance


Week 10 - Parsing: syntax vs semantics; Tokenization - a lexical analyzer in Java

Content authors (Group #2) Adam Harney & Daniel Scott


  • Parsing - Syntax vs. Semantics - Includes a brief summary of the two.
    • Syntax - A set of rules to be followed.
      • The arrangement of words/symbols in the structure.
    • Semantics - The meaning of a text.
      • The logic concerned with its meaning in the structure
  • A Lexical Analyzer in Java.
    • What is a token?
      • Tokenization: mapping keyword to numeric value
    • Source code for Java based tokenizer written in class (use week10.zip on web page as source).
      • break into functions and discuss each purpose
      • add header and footer for class definition to make complete Parser.java class

Week 11 - Parsing: implementing a language - a recursive descent parser in Java

Content authors (Group #2) Adam Harney & Daniel Scott


  • What is a Parser
    • Types of Parsers: Top-Down vs Bottom-Up
  • Structure of a Parser
    • Parse Tree
    • Grammar in Parsing
  • A Recursive Descent parser: definition
    • Implementing SQRL
      • BNF Grammar for SQRL
      • Source code for SQRL written in class (use week11.zip on web page as source).
        • break into functions and discuss each purpose
        • group some of the one line functions into one chunk
      • some examples of SQRL in action

What is a Parser?

A parser's function is to take code and break it down into distinct parts called "tokens" (see wk 10 notes) which can be executed by another part of the compiler. There are two different approaches to the way a Parser can work, either with a Top Down structure or a Bottom Up structure.

Top Down

Top Down parsing is a very simple to understand, but has many downfalls. Top Down Parsing starts at the beginning of a piece of code and continues downwards, working as it goes. This type of Parser is what was mainly used back in the 70s and earlier. The main problem with this type of parser is that it struggles with expressions, or any piece of code that forces it to look ahead very far.

Bottom Up

Bottom Up parsing works in the opposite way of Top Down parsing. Bottom Up parsing starts at the leaf nodes of the code, and tries to work it's way up to the root. This is generally the way parsers are built nowadays. Bottom Up parsing is not just defined as one thing however, as it can be further divided into seperate structures such as LR parsers, simple LR parsers, LR look ahead parsers, shift reduce parsers, and many more.

Structure of a Parser

Parse Tree

Photo source: http://interactivepython.org/runestone/static/pythonds/Trees/ParseTree.html
Parse Trees are extremely important to parsers, and are extremely important to modern programming languages. Parse Trees are ordered trees derived from the language's grammar that represent an equation or string in a way that can be interpreted by a compiler. They allow use to do many things, including writing expressions in our code, which is represented in the image above. The above image shows what a typical parse tree would look like for the expression: (7 + 3) * (5 * 2). As you can see, the tree's root is the * symbol, as it is the last part of the expression which needs to be executed. Further down the tree, we go into the parentheses to find more operators, whose leaf nodes are the integer values which they are going to operate on.

Grammar in Parsing

Another important aspect of parsers are the grammars on which they operate. A grammar can make the monumental task of creating a language with almost infinite variations of possible code much simpler, by breaking down all of those possibilites into a much smaller set of rules. These grammars are the basis for any programming language, as they define the keywords, constants, syntax, and structure of the entire language. Grammars are also helpful as a checklist when implementing a language.

A Recursive Descent parser

A recursive descent parser is a type of parser which is top-down and uses recursion on input to create it's parse tree. This is the type of parser that was used to implement our SQRL language.

Implementing SQRL

BNF Grammar for SQRL

Our grammar for SQRL seems rather limiting at first, but there is a lot that can be done with it. It defines code as one of 5 statements, a print statement, a load statement, an input (or variable assignment) statement, an if statement, or a mathematical expression. The last of these statements, the mathematical expression, can be one of addition, subtraction, multiplication, division, or just a lone value. The grammar also expands the conditional portion of the if statement to be greater than, less than, or equals to. The rest of the grammar is simply defining characters, digits, numbers, symbols, text, strings, and values within the language.

Source code for SQRL

public Parse()

This is the constructor for our parser. It completes the setup necessary for our parser to work. It creates a line variable which it sets to blank as a default, it creates a new Scanner called scan which will be used to read input, and it creates an array of integers 26 elements long called vars, which is used to store variable values, with each element of the array corresponding to a letter of the alphabet (a=1,b=2,...,z=26).

public void run()

run() is the first method called by SQRL after the parser has been constructed. It prints out an introductory message to the user, grabs the first token, and passes that token to parseCode().

private void parseCode(String token)

parseCode() is the main loop of our parser. It is called from run() at the beginning of the program, and will continue to grab tokens and call parseStmt() on those tokens until it detects the . token, which is SQRL's end of code symbol.

private void parseStmt(String token)

Parse4 1.PNG
Parse4 2.PNG
parseStmt() is the main method in charge of taking tokens and performing different actions based on the content of those tokens. Many of the methods in our parser will be called from this method. This is the incomplete version of the method provided on the stem.unh.edu site, and this description only covers the functionality of the provided code.

If the token given to parseStmt is "load", the parser will take the next token as a string and pass it into the loadPgm method, which takes care of loading external files into SQRL as code. If the token given to parseStmt is "print", it will do one of two things depending on what the first character in the next token is. If that character is a quotation mark, the rest of the string will be outputted as is to the command line. Otherwise, parseExpr() will be called to handle the expression. If the token given to parseStmt is "input", the parser will check that the token is a valid variable value using the isVar() method. If this is successful, SQRL will prompt the user to give a value, which will be stored in the vars array with a location that represents the variable it is being assigned to.

private String loadPgm(String name)

loadPgm() is in charge of executing code from a file. It will simply scan in every line from the file it is given until there are no new lines to scan.

private int parseExpr(String token)

This method is used to evaluate mathematical expressions. The version shown here is the one provided on the stem.unh.edu site, and is incomplete, as it only performs addition, whereas the final version will perform subtraction, multiplication, and division as well. The method first takes a token, and then looks at the next token to check if it is an operator. The next token is checked in a switch statement, where it will break out of if the next token is not an operator, returning just the original token value. If the next token IS an operator, it will take one more token and perform the given operation on the two token values. The result will be returned.

private int parseVal(String token)

This method takes in a value as a parameter and checks if it is an numeric value or a variable. If it is a numeric value it is returned as an integer. Otherwise it is passed into the parseVar() method, which is then returned.

private int parseVar(String token)

This method is called from the parseVal() Method. It calls the isVar() Method to check if the passed token is a valid variable value. If it is not, reportError() is called. If it is, the ascii value for the variable is returned.

private boolean isVar(String token)

This method is called from parseVar and is meant to return true if the passed token is a valid variable, or false if it is not. It checks that the token is only one character long, and that it is an alphabetical symbol, not a numeric or other symbol.

private void storeVar(String token, int val)

This method is used to store variable values. It takes in a token and a value. The value is stored in the index number of the vars array that corresponds to the ascii value of the token.

private boolean isNumeric(String token)

This method checks that a token is a number. It iterates through every character in the token, calling the isDigit() method to ensure that they are all numeric values. If they are, it returns true, but if there is a non-numeric symbol at any point in the token it returns false.

private boolean isDigit(char ch)

This method is used by the isNumeric() method to check if a single character is numeric or non-numeric.

private boolean isAlpha(char ch)

This method checks the ascii value of a character to check if it is an alphabetical or non-alphabetical character.

private String parseString(String token)

This method is in charge of parsing strings and ensuring that values passed to it are actually valid strings. The method takes the content in between the two " marks in the token, and returns that as a string. It will throw an error if the first character in the token is not a " mark, if a second " mark is not found in the token, or if a new line character is found in the string.

private boolean isNewLine(char ch)

This is a basic boolean method which simply takes a character as an input and checks if that character matches with one of SQRL's new line characters (\n and \r).

private boolean isBlank(char ch)

This is a basic boolean method which takes in a character and checks if it is blank.

private boolean isDelim(char ch)

This is a basic boolean method which takes in a character and checks if it is delimeter. Defined delimeters in SQRL are +, -, *, /, >, <, =, ", and .

private String skipLeadingBlanks(String buffer)

This method is called every time we go to grab a new token. It's function is to eliminated blank spaces before the start of the next token. This allows us to not have to worry about an extra space confusing our parser. For example, "print", " print", and " print" will all be converted to the string "print".

private String getToken()

This method is used to grab the next token in the code. It starts by calling skipLeadingBlanks() to skip all blank spaces in the code, until we reach a non-blank space. Once a non-blank character is detected, the method iterates until it reaches a delimiter or blank space, at which point it grabs all the characters it has iterated through and returns them as a string.

private void reportError(String token)

This method is used to report errors in a piece of code. When it is called from another method, it will print the line where the error occurs, and add a carat symbol to show exactly where the error has occured. It will then exit out of SQRL.

SQRL in Action

Loading Files and Printing Strings

above text contained within the file test.sqrl
Here is an example of a simple SQRL program which simply prints a few strings to the command line. The file test.sqrl is located in the same folder as SQRL.java and Parse.java

Input, Math, and the . symbol

above text contained within the file test2.sqrl
Here is an example of a simple SQRL program which takes input for 2 variables, and prints the result of adding those two variables. I've also added the . symbol to the end of the program, which causes the command prompt to exit out of SQRL once the program has been executed.

Week 12 - Grammars: Chomskys Hierarchy, Context Sensitive Grammars & Regular Expressions

Content authors (Group #3) George Harvey & Wesley Krol


  • Chomsky’s hierarchy. Touch upon each type, give examples and provide the table for creating production rules given in class
    • Type 0: Recursively enumerable grammars (give example)
    • Type 1: Context-sensitive grammars (give example)
    • Type 2: Context-free grammars (give example)
    • Type 3: Regular grammars (give example)
  • BNF versus notational form
    • discuss the two ways we've represented them
    • i.e. S -> A vs <start>  ::= <rule>
  • Properties of context-sensitive languages (CSG).
    • Compare CSG to Context Free Grammars (CFG) with respect to programming languages
    • Show and expand example: a^n b^n c^n done on board
      • First show a^n and its grammar (Regular) and a^n b^n and its grammar (CFG)
      • Give the solution of the class: S -> abc S-> aSBc cB -> Bc bB -> bb
        • Explain Kuroda normal form and how it impacts that solution
  • Regular Expression Syntax
    • Character classes ([0-9], [a-z], ...)
    • Meta-characters (., ?, *, \n, \t, ...)
      • Boolean "or"
      • Anchors
      • Iteration
    • Grouping (parentheses)

Week 13 - Table driven parsing

Content authors (Group #4) Dylan Durand & Brandon Peterson


  • Explain 2 types of Parsing in detail.
    • Difference between top-down and bottom-up parsing.
      • Top-down: Recursive Descent and LL(K)
      • Bottom-up: LL(R)
      • Give parse tree example of differences
    • Explain why most programming languages are "Bottom-up"
      • What are the difficulties in parsing.
  • Explain Table-driven parser.
    • Give an example, complete with example grammar, table and parse run
      • Include algorithm to parse
      • like to see a bit of a narrative of what's going on

Week 14/15 - An overview of lex and yacc

Content authors Mike Jonas


  • add item 1
  • add item 2