languag3
Mon 10/27/08
so that's the C/ C++/C#/ Java
but there are many that don't
design issues
1. type and form of the control expression
2. how are those "clauses" specified .. "thenClause" "elseClause"
3. How are nested selectors assigned meaning
control expression
- - - - - - - -
C, C++, Java, C# all use () to enclose it
so does perl, pascal
python uses nothing
ruby goes both ways
expression itself
C . was an int where 0=false everything else true
Python, C++ allows int or bool
Ruby, Java & C# allow bool only
if I don' have parens, harder to parse
pytohon put's a : to signify the end of the expression
clause specifications:
much more varient
c / c++ / java .. body is either one statement or black (ie, curlies - {})
in perl, all are block statements whether there's one or many
python - uses indentation
if a< 10:
a--;
puts a;
Ruby -
if a < 10
a--;
print a
end
.. keyword end finishes the body of the if
language that deals with indentation:
yikes!
1, should be just a visual thing
2, we don't agree on tabs
python else:
else
and must line up with ip
ruby:
if a< 10
..
else
..
end
so the keywords else and end lock the clause
some langaagessuse a then .. pascal did .. but that' the function of the colon in python
nesting
if ()
if()
state1;
else
state1;
C/ C++ /C#/ Java .. else goes with nerest unended if
in Perl this is a non-issue - you have curlies
nesting is not usually about as simple as that .. usually about multi-way selection
C/C++/Java/C# -
nest if else's
if (cond1)
else if (cond2)
multiway branch
design issues -
what can i test on and can i execute more than one segment?
1. form and type of the expression
2. how are selectable segments specified
3. does execution allow none, one or many selectable segments
4. switch case specifically - how are case values specified?
5. hw should unrepresented selector expressions be handled if at all
nested if else is really a whole bunch of if.. else statement
at most one block is executed .. the else part is not required
nothing to stop me from useing a whole bunch but perl has a constrct
if () {
elsif
perl does not have a switch
python similar
if expr :
elif ... some expression
how shoul unrecognized expressions be handled.
in C/ C++ .. can let an unrepresented value to not have anything
switch (expr)
{
case const1: statl;
case const2: stat2;
default: statdefault;
}
is is what c/c++ / C# and java wil look like
but behavior of C# is different
in C and C++, from top down, compares the expression to const1, const2, until finds equality
.. and the conts have to be known at compile time
.. char, int, .. can't strings, nor doubles
char, int .. holds for C, C#?, Java
char, int, bool .. c++
as well as enumerated types
can't put 1.7 and 1.72 .. can't always distinguish in the machine .. and their supposed to be mutually exclusive
once it finds equality C, C++, Java executes until a break or end of statement .. falls through
soeetimes we like that
switch (ch)
{
case a;
case B;
...
break;
}
allows code to be accessible .. don't have to repeat it
C# - only executes ONE block .. no breaks required for this to happen.
c# .. you get to match one and one only and I do it and it's done
so C# is very much else if, else if .. everthing else falls through
no need for switch, but allows us to do some readability but in c and c++ also introduces errors
how shoudd unrepresented selector expressions be handled.
- if none of the case hold we just fall out
so I can always pick up the unmatched cased with a default
default: always at the end
perl and python don't have those
.. can't switch on a string.
.. so ddl's , which return strings, aren't useful to us unless weemake them a has .. then we can refer by number
next: iteration:
let the computer do what it does best.
- how is the duration controlled
- where do I control it frm?
counter controled loops
initally, langaages used the do loop or a for loop
for (initialization ; when I finish .. ending value ; imcrement .. or decrament.
and then the body ..
this is a counting loop - set counter .. determine end value .. and at some point I move closer to my end value
Do 101: I=1,10
body
10: continue
counter, intializaton, ending, increment by
typically not allowed to change i in the body
.. could use i, but never allow to ccange it .. because it was the counting varible for th looop .. could only e incremented in the test.
in fortran, the end value was determined when I frist encountered the loop
.. we know that it's not true in C++
fortran initially alloweddme to only go up by 1 or -1 .. but still had to be a value.
so ounter controled loops were way more sticky than they needed to be .. but they also don't let you to read to the end of nput .. just a certain nummber of times
more fun and more dangerous:
logically controlled
-- - - - - -
c++
for(int; cond; statment) {
body;
}
.. issentially a while loop
where should the control mechanism appear - these are pretest .. i test before the body
foreach belongs with perl, too.
-------
Wed 10/29/08
exam monday
5,6, and perl
don't expect to write a lot of perl .. adapt it instead
chap 8 - finish
chap 12 - start - OOP
last time - conditionals / selection statements
2 - way selection
multiway selection
- switch/case
- if eslif else
languages didn't really differ a whole lot here
same flow of control
what differs .. determination of clauses .. body of the if, else .. what marks those ..
in some cases, {} ... perl
python uses end
indentation
not much to say except that they're there .. syntax somewhat different
one branch is executed
swtich case -- idea that it falls trhough
c# where the break is implied .. enforces one branch.
all langauges have some kind of selection
.. need a selection statement and a logically controlled loop -- everything else is extra
interative statements
- imparative langauges such as what we're used to use pimarily statements to do repetition
function languages use recursion as their primary (possibly only) form of repetition
as far as statements , several categories
- general design issues
- how should the lop be controlled .. where is the control mechanism
how is it controlled
counter controlled loop
logically controlled loop
counter controlled loops - we're acquainted with them but not with anything that must be counter controlled
.. idea of doing something 10 times .. etc
there is a counter that counts for me
so typically these involve a
loop variable
initial vaule
terminal value
step size .. how am i going to get there
the last three are typically called loop parameters
.. back in the scientific days of CS .. they wanted primarily a counter variable .. a lot of arrays
so they were the first kinds of loops
Fortran 95
Do Here I=2,10,1
---
---
---
Here continue
1. what should the type and scope of the loop variable be
.. do I allow ints, chars, other innumerated types
2. value of loop variable at termination
3. is it legal to change the loop parameters in teh body of the loop
.. can i mess with the i inside
if so, how does this affect the loop?
4. loop parameters -- how often are they evaluated .. once or each time through
what fortran did -- go ahead and change the loop variable .. but it'll still run as you specified at the start.
operational symantics .. how doesthis operate?
fortran .. sets' inital val
and terminal val
do label variable = initl, terminal, optional step size.
.. loop parameters are evaluated once
stepval = stepsize
dovar = initval
dovar is an internal variable that my program isn't touching
iterCount = how many times is this loop going to happen
max(0, (terminal val - initial value +step) / step)
so the reason you can mess with i is because it's already determined how many times this loop will go
label: if iterCount ≤0, goto out;
loopbody
dovar = dovar + stepval
itercount = itercount -1;
goto loop;
counts backwards - so we know how many times it'll be run
this is not how C++ works
i better be 11 when I get out .. but the internal counter, we can't even see
so this was the fortran do
c-based languages for loop
.. not really simply a counting loop anymore
for(expr, expr, expr)
body
expr1 - once
2 - before body and evals each time
3 - after loop
there realy isn't a loop parameter
i'm using i as the counter , but I'm doing th counting
.. nothing about an automatic increment or decrement .. we do that with i++;
if our terminating condition is a variable, we can change it in the loop
we're looking for a false from the terminating condition
eval exp1;
loop: if (exp2 ==0) goto out;
body
expr3
goto loop;
out:
all parts are optional - and if the middle part is missing, you have 0
perl behaves exactly as this.
Logically controlled loops.
- any counter controlled loop can be written as a logically controlled loop
but not the other way
design issues:
1. when do I test? - pretest or postest
2. can logically controlled loop statements be special cases of counting loops?
we can do that in c++ .. can turn any while loop into a for loop
but the thought is .. when i start allowing boolean expressions in the middle part of the for, then its not about counting anymore.
C/C++/C# /Java
while(exp)
body
do
body
while (expr)
do
body
while(expr);
loop: body
if expr is true, goto loop
body will execute at least once because it is a post test loop
as opposed to the while loop
loop: if expr = false goto out
body
goto loop;
out:
- pretest - body done 0,1, or many times
fortran 95 does not have a logically controlled loop
.. so you have to have gotos
c++ keeps one around . it shouldn't
Java does not have a goto
but there are disasterous times that I want to leave early
-------------
perl statements:
while (expr) {block}
do {block} while (expr);
.. exactly mimic c and c++
until (expr) {block}
do {block} until (expr);
until comes from pascal
- so if expression is false, I do the block
loop: if expr = true goto out
block
goto loop
out:
perl starts to get on the endge where it allows you to do too many things
user (really programmer) leaving llop control mechanism
1. how to leave not using thh loop control
2. how far do you leave? - nested loops
. do I leave one enclosing loop or all enclosing loops?
unconditional unlabeled breaks
prefer to have a single entry
but adding a break allows me to leave the loop in more than one way
can have unconditional lableled breaks
java and perl do the 2nd
c / c# /C++ / ruby / python do the unlabeled.
C++
for (i=, .... ) {
for j = 0 ... {
if _---
break;
}
cout << "here";
}
cout << "there";
statement is break - so its unconditional
the break goes to "here"
so break in the C's jumps out of one.
java lets me jump out of more than one. ie, can force it to
unconditional labeled breaks
outerloop: for (r=0; r< rose; r++) {
innerloop: for (c=0; c< columns ; c++) {
sum += a[r][c];
if (sum > 100)
break outerloop;
}
}
.. so that allows me to jump out of both
so label a loop and then kill that loop with a break statement.
perl allows the same thing in two different ways
out: while (1) {
stmt;
mid: while(1) {
if (---) last out;
while(i)
if (---)
next mid;
so in perl , break doesn't exist but last does
so last out .. leave the loop labled out
next is like a labeled continue
break in for loop not good .. hard to tell visually if we still do the i++
iterative statements over data structures
"intro"
for (i=0; i< size; i++)
... a[i] .....
. iterating through the structure starting at the front, going to the next one .. until I get to the end.
for (p=first; p !=; p = p-> next}
--- *p
processing a linked list
.. but no one writes code like hat
iterating through a strucuture
purists say that if i'm defining a class, i should have the ability to iterate through a collecion class
.. there is an iterator class
for ( first A, not at end, next A) {
//
}
so itrator classes that wnet hand in hand with the collection class
foreach variable (collection) {
process var
}
perl
foreach (@arrlist)
foreach $a (@arrlist)
c#
foreach object in a form
new creation .. really nice ways to step through collections
c++, c does not
java does but not with "each"
for something in collection
-------
Fri 10/31/08
Exam 2 - Mondaay, Nov 3:
Chapter 5 -
Names - waht did they decide ere valid names .. length .. case sensative or not , keywords or special words and at the end of chapter 5 - programming language w/o keywords --> probably not
variables: names, address, type, value, lifetime, scope
binding and binding times
- language design
- language implementation / compiler dessgn - length of an identifier
- compile time
- link \
- load /
- runtime
static binding .. everything is known before runtime
dynamic binding
when is the datatype bound? in perl, when I assign to it!, in C++ .. when I declare it -> compile time
storage binding .. when did it get the actual memory associated with that variable.
lifetime of binding .. how long is that variable tied to taht location.
this is where we looked at static variables
stack dynamic variables
explicit heap dynamic
implicit heap dynamic
type checking -- when does that happen? .. based entirely on when the type is bound
type equivalence - is it by name or is it by structure?
scope - when can I use that guy by name .. we talked about static scoping
and dynamic scoping .. order of function calls determine what x i'm looking at
lithese are only real interstting if we allowed, and we did, nested dclarations
in C and C++, we looked at nested blocks
in other lagnuages we could look at blocks and subprograms
perl allows me to nest function defintions as well
scope - where is the variable visible?
referencing environment -- given a statement, which variables are visible - so it's the opposite
if I know one, I know the other -- not exciting
Chapter 6-
- datatype - values and operations on those values
- primitive types .. one that when i define it , it's not defined in terms of other types
when w talk about a string in C++, we talk about it as really eing an array of char .. but there are string constants in other languages that we can call primative
but most of the time, it's numeric, boolean, and chars.
doesn't seem to fit
character string
- static - address and length fixed .. track - static string, address, length
- limited dynamic -- limited dynamic, ned to track maxlength , current length and address
so if I have those things, i know how to describe it and that's what a descriptor is
skipped the section on user defined ordinals .. they add no power .. primaryily adds readability and sometimes destroys compatibility of types
one enumerated type that we know about is bool - .. true and false enumerated.
Array types - indicies - what can you use, what can't you use
subscript binding .. when do I know what valid subscripts are -- time of definition .. using it? can i cahgne it?
plus storage allocation -- when that happened
these two things characteristics .. hwen things were allocated and when the substrings were bound led to these array categories
staic
fixed stack dynamic
stack dynamic
fixed heap dynamic
heap dynamic
example of fixed stack dynamic .. int a[5]; .. in main
stack dynamic:
cin << num;
f(num)
f() {
int a[num];
}
we know that we're not allowed to do that but it would be nice
fixed heap dynamic
int* p = new int[5];
so unless I reallocate , the size is fixed.
heap dynamic -- the arrays of Perl and javascript
. you wanna make it longer, push(),, shorter - shift
descriptor -
-- array
-- array of something -- int, char etc.
-- in some worlds, you can use different indecies .. so index types
-- index low
- index high
-- address - where the hell is it?
what array operatons are allowed -
as i pikk an array further down the chart, the operations became - got to do more things
in heap dynamic , we can concat arrays
where forget that up at the top
so theemore flexible everything is, the more things I can creatively do with array operattions
we did breifly look at 2d arrays -- row major and colum major
we don't reaaly heavily emphasize ...
process by column if column major
for a long time we have know that a 2d array is not really 2d
associative arrays - for us the perl hash
key, value pair
if I have the key I can get the value if I have the value I can look up the key
in perl this is heap dynamic .. I want it, I have it .. make it bigger, delete everything
Record types
------------
wasn't much to deal with
- structs for us (classes but not in the pure sense)
- record in pascal
operations on them .. are limited as well .. can always be done data member by data member
skip union types
pointer types vs reference types
pointer
- how
- problems - dangling pointers, lost memory
- how some implimentations try to resolve problems
if using pointers, you must manage the dynamic memory yourself -- explicit dynamic memory management
most languge, the gather equest is explicit -- new command .. and then lnguages such as C#/Java, dont use pointers .. they use refrence variables
they refer to memory locations -- don't think of them as storing an address
when reference types are used instead of ponters, it's implicit memory mangement.
As far as implicit - two ways to go about it
eagar - as soon as it's no longer accessible, reclaim memory
lazy - when none available, reclaim the unused
up to the language implimentation
one method that went really well -
Problem : dangling pointers - causes program to crash or give unexpected results.
in c++
int * p = new int;
*p = 52;
int * q = p;
delete p;
q is a dangling pointer - looking at memory I don't have
a couple ways that languages have tried to resolve this
one solution -- no pointers allowed.
2nd - locks and keys - when I really allocate a variable P = new int;
p has two parts to it .. the address of this thing in memory but also contains the key.
key and lock hold 79. .. Lock and key assigned to each.
every time I try to say *p, it compares the key and lock .. if they agree , all is good .. if they don't agree, it says "you can't try to access that'
so now if I say q= p;
q can access that memory location
but if I delete p, the lock value is cleared.
everytime I allocate a dynamic variable, I must also allocate a lock .. even if I delete p, I still have the lock
so rather than crashing or giving you crap results .. this mechanism will tell you that you made an illegal memory access .. at least it's grace
tumbstone method
--------------
every heap dynamic variable has a special cell (tumbstone)
the tumbstone contains the actional address of the dynamic variable
int * p = new int;
p[----> tumbstone --> real location.
q = p;
now q holds the tumbstone
delete p .. then the tumbstone holds nill
so once again, that little chunk of memory has to hang around!
this guy costs me space too -- but also time -- now it's another address lookup!
-------
Fri 11/07/08
"i'd a been feeling a whole lot better had I not forgotten the name tag"
could open up all files in folder
object based
document -- the page
object properties
primitive types - number, string, bool, undefined, null
- non-primatives: number object, .. tehy're all reference types
var list = new Array();
list.push
list.shift
unshift, pop
if declared implicitly .. that means global, type assigned at declaration
make a variable local is var and the variable name
.. diverges in string functions.
this.
sharing the same name -> implicit array.
if( dfadf.[i].checked ) = true;
x.onchange = func;
-------
Mon 11/10/08
-------
Wed 10/12/08
scheme folder
Dr. Scheme
Chapter 15
functional programming languages
- imperative - variables/assignment statements
- exploit the von Neumann Arch .. iteration on places close in memory is very efficient
- C, C++, ...
under imperative, we have the list Object oriented .. funcins are not completely eparate from data
GUI languages .. MFC, etc .. technically they're imperative .. they deal with objects, so they might be a subset of oop
scripting languages .. even though different variables, still variables and assignments
- logic programming .. rule based programming .. you design the rules .. order is not important . so when you write a program, the order in which you put things in doesn't matter . very different than C++
- functional programming.
everything is a function
allwe're really doing .. apply functon to arguments .. so you have to think about things in a different way
- LISP .. first real popular functional programming language . still has some widespread use
- developed in the 50's .. couldnt do link structures and recursion .. multibranch conditionals
.. they wanted to do symbolic computation and list processing
- 1977 .. Backus was given the ACM Turing award .. highest award you can get in CS .. he got it for developing fortran
.. person who gets the award gts to give a big lecture .. he basically put thumbs down on the imperative languages
and up with functional
.. he thought cs was going the wrong direction .. says functional is more readable, more relyable, limited or no side-effects
.. big part of that comes foom the idea that in functional programming (purely) there are no variables
thought this was the way to go but we haven't ended up there
but there is wide use of lisp primarily in ai
scheme is a teaching language
.. numerous free interpreters out there
functions are the courner stone .. first class entitities
.. they can be used in any way shape or form you can possibly imagine
C++ .. first class entities .. int .. but array .. can't return an array from a function.
so scheme functions can be
- elements of lists ..
- passed as parameters
- returned from functioos
- evaluated as an expression.
you can actually pass functions to functions in c/ c++
void bisection( double f(double), int a, int b);
can send a function to another function
functions are our building blocks.
15.2 mathematical functions
- mapping from a domain to a range
- Rule: f(x) -> x+2
- table: x and f(x)
mathematical functions as values
input , output, and magic inbetween.
functions define values .. not a sequence of operations.
simple functions
- named function: -
cube(x) = x * x * x
(define(cube x)(* x x x ))
- unnamed functions:
λ(x) x * x * x
(λ(x) x * x * x) (2) --> 8
(define(lambda .. but not flying
function application
.. in order to apply a function .. need name and parameter
(Name parameter)
function name and then expression
(cube 3) --> 27
(+ 2 3 ) .. primitive function +
.. evaluates to 5
( + ( - 2 3 ) 4 ) --> 3
- define functions
- primitive functions
- create more complex functions from existing functions
- apply functions
oone way to make more complex is to compose functions
f(x) = x^2
g(x) = 2x+1
h(x) = fog(x)
f(g(2))
f(5)
25
fundamentals of functional programming languages
if pure,
- no variables .. imperative focused on memory
- no assignment statments.
- no iteration
- you must be given a set of primitive functions
advanced student stage
(+ 3 4)
read scheme chapter 1
(zero? 4) .. is it zero?
numeric functions
predicate functions
list functions
functional forms that allow us to construct complex functions
.. using (define ... )
3. function application .. be able to apply function -->
(funcname expr)
4. structures for representing data
.. parameters in and gettting values out
.. paramenters and valuesreturned.
scheme interpretor does the following
- read
- evaluate
- print/ write the expressions.
REP loop or REW loop
print vs write
Scheme primative functions
+ - * /
= <> > < >= <=
zero? // not case sensative except for identiiers you used
even?
odd?
those are soee numeric primitive.
#t --> true , # f --> false
parens make function call
quote to create a list.
'(1,2,3)
can create a constant that presents my list .. have to redefine it to change it.
define x 10 .. can define constants
define mylst (1, 23, 3, 3);
built in function on lists.
car cdr cons
cdr .. give the tail of thh list
cons (A, myList);
didn't change myList (globally) but i did stick something on the front of it
can also add a list to a lst.
first item of a list is a list.
strings are fine
define y = "hello mom";
and I have numbers .. that's pretty much is.
constructing moore complicated .. if statements
define add1 -- on sheet
(add1 7);
define add2
(+ x y ;
function composition
looks like i've passed a funcion to a function
keeps thinking you're always imcvey
sum to n
.. o if n is 0
if
^two way banch
miltiway branch with con for "condition"
( cond
(predicate exe)
pred2 exe
else expr
else is optional
comment is a ;
list processing.
sympletypes.sng
ways to print:
~ .. get it off the list
define X, a ..
only time you can change the contents of Y with set.
lists
car .. front of list
cdr - cutter .. everythiig front on back
cons - add , not necessarily appending
cons .. starts with element in list
appends - also primative function.
so you can print and display
average function.
2 4 5 .. ag = 11/3
this guy says
average of this list
6, 2, 4, 5,
.. average of the list . times length of the list plus the six divided by 4.
cdr .. last part of list
car .. first part of list
-------
Fri 11/14/08
chapter 15
we did a lot with numeric
+ - * /
zero? negative? number?
integer? exact? -- is it exactly what it says it is or am I rounding?
rational? real?
< > <> = >= <=
control flow
------------
if is a two-way branch
(if bool thenexpr elseexpr)
(cond
(bool expr)
(bool expr)
(else expr) .. optional
)
no loop
let is optional
(let ((x 3) (y 4))
(begin
.
.
.
)
bollean
(and e1 e2 ) .. as many expr as I want
(or e1 e2)
(not e1)
number?
bollean?
symbol?
null?
list?
pair? .. a list of two
list?
(define '(1 2 3))
lists can be of mixed mode
cons car cdr
car returns the first
cdr is itself a list
a list
.. an element followed by another list .. the cdr aka tail
(define (len myL)
(if null?
0
otherwise return 1 followed by the tail of the list
stop recursing with a zero.
so trying to always process the end of the list
- note car fails on an empty list
(if (null? myL)
nothin
(cond (null? myL) --)
count zeros
if (first
tail recursion!!
simple equal
there are all kinds of ways fpr asking if two things are equal
= .. numeric only
(memq obj list) is the thing in there?
eq does't work for char, numbers
eqv? like eq? but does numeric?
why use = for numbers -- fastest
eqv will take the time to check the type
(member obj list)
this guy uses equals?
same structure and content .. even less efficient than the other guys
... so you can always use this, but it's more expensive.
checking two lists for equality
- simple lists
- all elements are at the same level
(1, 2, 3, 4) .. all at the top-most level
multi-level list
elements are at different levels .. or can be
(1 2 (3 4 5 ) 6 7)
not the same list!
.. recursively call yourself on the list
compare two lists for equality
"replace is fun" ... hmmmmm
-------
Mon 11/17/08
nov 17 folder
functional programming languages
- function / procedure
- scheme function programming language .. chapter 15.5
function
whereas imperatives are all about variables and assignment
purly function programming languages don't have assignment statements but we do have some sorts of assignments
set vs let vs define
set is a ture assignment
let is not .. let creates a new binding
let instanciates local variables / bindings
so the x (define) is global .. let is local
variables define such as x .. can'' be changed unless I use an assignment statement
set .. does indeed change the global variable
procedure vs syntatic structure
with a procedure call
(proc arg1 arg2), the arguements are evaluated before the procedure begins
in a syntactic structure
( if bool expr then exrp else expr)
parameters are evaluated as needed
don't look any different but they behave very differently.
syntactic forms do what they need to do ..
bool
syntactic forms -- lazy / short circult evaluation
args are evluated as nnede
or only goes as far as it neeeds to
.. lazy evaluation
syntactc form and proceedure
lis processing
try to do something to everybody in the list.
p= fList;
while(p ≠ null)
{
process
p= p->link;
}
void DoLuist .. could send it the front of the list and then function
pass the functon as a parameter to a function
Sequire gaitway
define the function as before -- maccolor
pass funct and list
if my list is null, regurn the empty seat
otherwise, need to create a new list and apply it to the first car of my list.
myL (2, 5, 9, 8, 3)
mapchar
mapchar .. is a functon wh's parameters are a functon and a list.
function is applied to the fron of the list.
very powerful .. can process a
constantly compsing function call here
MapCar -
sort lists .. how many occurangces ..what's the bigget now, smalest?
minimum .. smallest of the first .. or the smallest of the remainning list.
choose the smaller
in order to do this comparrison, I found the miniumu for ___
finds the miniumum multiple times
but finding the min and box is the hcornerstop of any search algorithm
she gave us a replace .. you could find theeminimum and then replace.
another way -- inseration sort -- kinda boring, too ..
bubble sort
heapsort n log n
quicksort .. worst: n^2 .. avg .. n log n
radix sort:
shell
bin
counting
quick sort and heap sort are inerantly recursive
heap is really a list .. so we like that
merge sort
but we don't typically think of bubble sort as being recursive
selection sort goes out there, finds the minimum and then puts him in the right spot.
don't think of it as recursive ..but it can be..
find smallest, swap into place,
and then same thing on smaller array
alist (2 4 5 6 7 )
1 2 4 5 6 7 .. last part is the cdr .. it is indeed recursive!
selSort(intfirst , intlast, array)
min
swap
selSort(first_1, last, a)
so it is indeed a recursive call until first = last
bubbleSort
2 4 5 1 6 7
does a lot more work in one pass.
swaps everything out of order as it goes trhough.
keeps moving the big guy to the bottom .. but if we want to use scheme we should put the first one in place.
one more pass, no changes, and we're done
but even this way is recursive .. if I woul do a buble sort on this guy
bubblesort(int first, int last, int A[])
if (first == last) return;make a pass
bublesort (first, last,-1, A)
}
attach after removing the first two items
cddr
new list by sticking the a in fron t, jusing the tain of the tal and then bpass1 as well
so ths is the work horse .. bpass1 , not bubble sort
-------
Wed 11/19/08
project -- quirky thing
dec 12 for inbound flight
create a file
permissions issues
public_html/csci322datafiles . that folder is wide open
scheme - identify what a program is doing
project:
performing tasks and where they should be performed.
bpass -- 1 pass through the array, swapping out of order pairs
mySort
removeFirst
.. if null, send list back
if first guy in list is x, return the rest of the list.
else ..
removefirst(x)
2 3 4 9 3 1
if that's my list
this guy comessin
areeyou x? no
does the else
cos the 2 with removeFirst x and the rest of the list
2 4 9 3 1
.. so removes the first occurance of x
how does mysort work?
mysort
if my list is
2 3 4 9 1 3
finds the 1
puts that in front with the first occurance of the 1 removed
.. make two passes.
could add a let
(Let (m mymin mL))
so we don't have to call the same function a gazillion times
selection sort
.. has to do a ton of work .. find the min again
but selection sort, bubble sort, and insertion sort were never meant to be recursive.
a reminder about merge sort
2 9 4 3 2 7 1
spits into two parts
2 9 4 3 2 7 1
sort and then merge
(mergesort A)
(if |A| >)
(split A B C)
(mergsort B)
(mergesort C)
(merge A B C)
else return A
merge
take it off and merge with rest of list
mergesort
appropriate use of set
quotient --> what we get by doing %
.. so this is a great application of recursion in scheme
left and right
files
doesn't get rid of eol
-------
Mon 12/01/08
change a reservation:
cancel and then get a new reservation
comment files with name and anything unusual
don't have to worry about past and future dates
-------
Wed 12/03/08
12:00 Adam, Francis, Van
reflection due Thursday 2:15
I will never forget the name tag every again
don't look for specific questions about :
exam 3 q 6 does not say speciffically waat does c do with that
.. so big picture is not what a language does with what
no writing scheme . but know what it does
grammar stuff to cheme constructs
scheme is interpreted
what makes a language good, bad
why don't we just have one
why do we bother with several?
-------
Fri 12/05/08
might get a quesiion a lot like the first .. really likes that question
readability, writability .. etc
orthoganality .. that's picky
suppose I have a great idea .. also a conceptual question
hypothetical .. what class of langauges would be a good choice
.. very high level questins .. pull together some of the concepts
sceme .. interpreted
javascript - interpreted
java .. hybrid .. compiles down to a point : byte code.
skipped chap 2
chapter 3 .. syntax and symantics
quesion2 on exam 1
grammars
BNF
won't be asked to write any .. might be given one .. give the parse tree
we have lexical analysis
split up the data into toeksn
- regular exp
- state diagrams
use of a state diagram to recognize tokens
break any program into pieces.
identifying the small pieces . tokens / lexemes
lab 1.. brute force
lab 3 .. take a grammar, some of the code .. bnf to ebnf .. will not be asked to do that .. that's a nice tecnique .. but the more important is to move to a recursive decent parser
ebnf .. dealing with program code
will not be asked to add something
sould be able tt understand precidence and associativity
deeper down .. happens first.
take the grammar, construct an example
talk about example
left and right assoc.
E -> E + T | T .. left recursive --> left associatative
T -> T * F
F -> a | (E)
operational symantics .. intrduced in chapter 3.5, used in chpater 8 .. but we didn't do the math
recursive decent parsing
.. constants are common
term
while addition and subtraction .. need to parse and get the next term
E → T ((+ | - ) T) *
table on exam 1-- don't worry about
.. why recursive decent parsing works
out of exam 1
know
lex , syntax anal
grammar to parse tree
ebnf to recursive decent
use some of the terms from chapter 1 to discuss strengths and weaknesses for particular applicaations
exam 2 -
constants and for statements
six attributes of variables
- name
- location
- type
- value
- scope
- lifetime
binding times
.. with respect to all six
... static vs dynamic-> may occur during runtime or change during runtime
name .. usually static
location -- all different classifications
stack dynamic .. that should have a meaning .. allocated on the stack . and allocated during runtime
not on the heap . on the stack!
give c++ or perl examples
exam question about location
different binding times for types
there are types that can be dynamically found .. in javascript
implicit and explicit type declarations
static and dynamic type binidngs
scoping .. static vs dynamic scopiing .. which x am I using?
arrays .. they are more complex than a single variable . therefore more interesting
talked about these same things.
perl - no homogeneous arrays
.. a lot of different things that signify
mumps .. what do I need to know
explicit variables?
am I fixing a type?
what do function calls loook like .. reference type, primative type? variable that is itself the location.
tthese are the kinds of things that make picking up a new language hard.
where are those variables allocated and how ...
know the questions to ask
no writing perl, javascript unless you choose to
C/C++ .. maybe ... but the idea .. this isn't about writing code .. knowing characteristics
no writing scheme
real meat of the course: exam 2, syntax and lex from exam 1, variable attributtes anddbinding times (exam 2)
exam 3.. idea of a functional programming language ..
repetition and conditionals .. idea that they differ
need to know something about how a language implements them before you start writing
length .. not any longer than anything else ..
less questions overall .. more overview tyype questions than nitty gritty
exam 2.. was fairly big picture
no simple phrases !
no creating grammar
no add to
open book, open note, open exam!