Skip to content
This repository has been archived by the owner on Sep 3, 2024. It is now read-only.

CPSC 320 Lecture Notes

Jump to bottom
michaelconnor00 edited this page Sep 24, 2015 · 1 revision

CPSC 320 Lecture and Study Notes

Oct 15, 2014 Lecture

Project discussion:

  • Write a paper on a concrete language with analysis of all the aspects discussed in the course.

  • Will need to do research, start with wikipedia and use the links and references.

  • Language must have a free downloadable translator.

  • Do not choose Java or other languages that you have been formally taught.

  • Preferably not a main stream language where there is so much material ones opinion can be distorted.

  • Stay away from a language where the purpose is too narrow (ie Latex)

  • Language report, not a tutorial, roughly 10 pages focusing on highlights, what is important/interesting.

  • Make sure to cite quotes from other sources.

    • Prolog,
    • Angular.js (javascript),
    • jQuery...

Lecture:

Language Constructs

  • Expressions:
    • side effects in expressions are where they modify a memory location
    • order in which functions are evoked matter, z = f(x) + g(x) or z = f(x) && g(x).

C: (sidebar?) What does this loop do?

unsigned char *p, *q;
while (*p++=*q++); //*p is the location that the pointer p points to.

//p = x, *p is the memory location of x
//q = y, *q is the memory location of y
//so the contents of q is stored at the location *p. Then incremented.
//This loop essentially copies one string to another location. terminates when it hits the null char, and evaluates to false.
  • Definitions:
    • int x
    • assigns meaning to a name
  • Commands:
    • Construct that modifies the state of computation
    • Could do I/O
    • Cannot under actions on commands
    • irreversible effects.
  • Sequencers:

Example:

source

x = x +1
  • left part is an expression that points to a box where the new value will be placed. Called L-value.
  • right part is also an expression (variables). Called R-value
    • however, x on the right is the value of the box

An L-expression is a reference to a memory location

int x = 2+3; - Definition: a storage location that is bound to the variable x (int x). not a pure definition because it effects storage (reserves space) - Expression: 2+3 is put in the storage location(x=2+3)

Oct 17th, 2014 Lecture

Control Structure

Sequential Composition:

x = x + 1; y = y + 1;
Bracketing:
  • ie - use in if condition to group the contents together.
Selection:
  • if/then/else
Repetition:
  • iteration...
  • while loops

Sidebar:

  • ((lambda)x.Ex)a
    • where x is the 'formal parameter',
    • and a is the 'actual parameter'
    • and Ex is the 'Abstract'
..note::
  • Value returning expression is a function
  • Side effect expression is a procedure...
  • Class is an abstraction of definition

f(x) = x^2 (f defines the function x^2) f = (lambda)x.*xx (f defines the function (lambda)x.*xx)

Parameter Passing

source

int n = 10; // 1 binds n to a storage location with 10
int f (int x){ // 3 binds x to a storage location, 10 copied to x
    x = x + 1; //
    return x;
}
n = f(n); // 2 function is called
Ways to Pass Parameters:
  • The above is 'Pass by Value'
  • Another possibility for the above is to 'Pass by Reference', where x would be a pointer to n. Then the function could be a void function
  • A third option is to 'Call(Pass) by Name', used in Alog60 for example, but not used very often.
  • 'Pass by Value-Result', used in distributed computing and remote calls...
  • 'Pass by Result', random number function or input function

Oct 22nd, 2014 Lecture

Talk about abstractions. It is probably the most important feature of programming languages. How is this supported in Programming languages?

lambda - (l)x1x2...xn.E[x1,x2,...,xn] --> Definition, where E[x1,x2,...,xn] is the Abstract, and x1x2...xn are the Formal Parameters

fa1a2...an --> Invocation (call), where a1a2...an are the Actual Parameters

Principle of Extraction

Expression --> Function (return values) Command --> Procedure (do not return values...) Definitions --> Class Sequencers --> ? not exactly abstracted straight

f(x) = ... , where = is the assignment operator

int x = 1;
int &y = x; will put the alias y on x.

int a = 1;
int & f(int x){
    return a;
}
(define square
    (lambda (x)
        (* xx)))
function f(x:integer):integer
begin ... end

Types of Parameter Passing (Passing By:)

int a = 10;
int f(int x){
    ...
}
f(a);
  • Value: contents of a are copied into the location of x, on invocation.
  • Result: contents of x are copied into the location of a, on return.
  • Value-Result: does Value passing first on invocation, then Result passing on return.
  • Reference: Where x is an alias to the the parameter a.
int a = 10, b = 0;
int f(int x){
    a = a-1;
    return (x+1);
}
b = f(a);
output a, b;
  a b
Value-Result 10 11
Reference 9 10

Note

The above code is bad practice, because the function f side effects on a.

Important

In distributed systems Reference passing is not feasible.

Knowing the how a language uses parameters is very important.

Static vs Dynamic scoping of variables

int a = 10, k = 5;
int g(int x){
    return (x * k);
}
void f(void){
    int k = 3;
    output g(2);
}
  Static Dynamic
output k=5, 5*2 = 10 k=3, 3*2 = 6 
const int i = 1;
const int j = 2;
const int k = 3;
int global = 66;
void f(int x){
    int i = i + j + k;
    int j = i + j + k;
    int k = i + j + k;
    x = i + k;
    global ++;
}
int main(){
    f(global);
    cout << global <= eval; //This line isn't right
    return 0;
}
Def Par Output
Seq. Value 67
Seq. Value-Result 26
Seq. Reference 27
Sim. Value 67
Sim. Value-Result 12
Sim. Reference 13

Pass by Name

int a = 10, k = 5;
int f(int x){
    return (2 * x + a + k); // Here x would be substituted by a,
                            // and introduce a naming conflict. Rename a in main().
}
int main(){
    int a = 20, k = 10; rename to a1, and k1
    cout << f(a) + a + k; //cout???? 85 -- rename to a1, k1, [2*a1+a+k] would be substituted here.
    return;
}

Procedure: * Substitute (textually) actual parameter for formal parameter in procedure body (remove naming conflicts). (Bracketing if not an L-Exp) * Substitute (textually) modified procedure body for the invocation (remove naming conflicts).

Note

When removing naming conflicts, always rename the bound variable. Depends on scope. The most local.

What is an L-expression???

int i = 0;
a[3] = {0, 1, 2};
int f(int x){
    int y = x; // sub a[i], a[0]
    i++;
    y = y + x; // sub a[i], a[1]
    i++;
    y = y + x; // sub a[i], a[2]
    return y;
}
int main(){
    f(a[i]); // Hard to track mentally.
}

Note

Compiler uses a function to do the substitution (pass by name), called THUNK.

void f(int x, int &y){ // x is pass by value, y is pass by reference
    c(x,y);
}
int a = 1, b = 2;
f(a, b); // contents of a will be copied to x, y will be an alias to b.

Correspondence of languages...

Assignment:

Example A: L := E; -> L is an L-Exp, E is and Expression

  1. Find L-value of L, l
  2. Find R-value of E, e
  3. Place e into location l

After A:

The R-value of E *before* execution of A is the same as the R-value of L after execution of A.
There are situations where this is not true. ie - a[i++] = i, after execution a[i+1] != a[i]. Because a side effect
was introduced into L.

Warning

Exam question: a = (b = c), Cleft, Cright are implementation. Cleft = (steps 1,2,3), Cright = (steps 2,1,3)

Oct 24th, 2014 Lecture

Memory Allocation models:

  • Stack Frames for local variables and data, and heap space

  • More simplistic, static allocation where the compiler handles the storage of every variable. This doesn't work for recursion.

    • Need to be able to explain the purpose and need of the heap.

Stack Frame:

F(x)
params | |
dynamic link | | admin - also called control link
static link | | admin - also called access link
return addr | | admin
locals | |
temporaries | |

Who creates What?:

  • The calling procedure of F, will push the params, push links, push return address, and jump to F.
  • Static link (access link), used to access non-local variables.
  • Dynamic link (control link), points to the "parent" stack frames static link.

Note

The links get complicated when functions are passed as a parameter. When a function is passed, it is encapsulated in an object called a closure. It includes a code pointer, and an environment pointer. A location of where the code is, and a point to the environment where it's local variables are, also where the static link points to. This is not the case with C/C++ where a pointer is passed as the parameter. The enivronment pointer is .. note:: note is not required because the passed function can only use global variables, and thus doesn't need to be told where they are.

Warning

This cannot accommodate returning a function as a result of a function. This is using closure, where the environment pointer will point to the environment that created it, but that environment is deleted on return.

Clone this wiki locally