topics

quizzes 1-4, no writing higher-order func, regular expression, and tail recursion

language specific

foldr :: (a -> b -> b) -> b -> [a] -> b
and from this you can see that the list element (of type a
) is the first argument to the given function, and the accumulator (of type b) is the second.

In addition,

- Hoare,

- Variables

**call by value: **copy going into the procedure
**call by result: **copy going out of the procedure
**call by value result: **copy going in (local vars), and again going out
**call by reference: **pass a pointer to the actual parameter, and indirect through the pointer
===by name and need uses lazy evaluation==
**call by name: **re-evaluate the actual parameter on every use.
For actual parameters that are simple variables, this is the same as call by reference.
For actual parameters that are expressions, the expression is re-evaluated on each access. It should be a runtime error to assign into a formal parameter passed by name, if the actual parameter is an expression. Implementation: use anonymous function ("thunk") for call by name expressions
call by need encapsulate in "thunk", same param replaced by pointor to the same location

- Prolog

Q1 - June 16,17

- Intro:

~

--- should give array starting with a prime
primes [] = []
primes (x:xs) = x : primes (removeMults x xs)
removeMults x xx = filter (notdivides x) xx
notdivides x y = y `mod` x > 0)

- Recursion

- Tail recursion

- Algebraic data Types

data bool = true | false
data <dataName> = <value_constructor> (params) <| value_constructor> (params) 
e.g. `data tree = nil | tree root (tree lb) (tree rb)`

- Using HOFs

Q2 - June 30, July 1

Interpretation
Continuations
Big-step Semantics
Lambda Calculus

1] Interpretation:

• interpretor is a program that takes expressions and convert them into values
  • for this we need: type to represent values, to represent expressions, and a function to eval expressions to vals
  • to get the expressions we need a func that takes user inputs and convert them into expressions. (parser)
  • top-level: RPEL
• Interpretor2:

=========================================

ClosureVal String Exp Env (var name, function body, snapshot of the env at the time)
FunExp String Exp 
eval (FunExp String Exp) env = ClosureVal String Exp Env

note

eval (AppExp e1 e2 env) env = 
let ClosureVal str bodyE CENV= eval e1 env
     arg = eval e2 env -- at top level, call by val
in eval bodyE (str, arg):CENV

2] Continuations

• A tail call occurs when a func returns the result of one func without processing it first
• CPS func "never returns", pass result to another func
• apply order within func k doesn't matter much, e.g. :

fibk 0 k = k 0
fibk 1 k = k 1
fibk n k = fibk (n-1) (\r -> fibk (n-2) (\fib2 -> k (fib2 + r)) ) 

mapk f [] k = k []
mapk f (x:xs) k = mapk f xs (\r -> k $ (f x):r ) or
mapk f (x:xs) k = mapk f xs ( \r-> f $ x (\fx -> k $ fx:r) )

• note the k and newk(latter is accumulated func)

  
  

3] Big-step Semantics

• while loop the true branch

  
  

4] Lambda Calculus

• ** qs**

• alpha capture happens when some free variable in danger of being captured by some lambda (use alpha renaming)

  
  

• function calls associate to the left

*] additional

• 1) type classes

• typeclasses are not like classes in OOPs, but they are interfaces that describe certain behaviors. e.g. the eq typeclass provides interface for testing equality.
• polymorphism (inclusing overload, c++ decides on runtime which func to invoke based on the params)

data Foo int = Foo i
-> instance Eq Foo =  (==) (Foo i) (Foo j) = i==j
-> or just deriving (Eq) (to make our type instance of some typeclass!)

• class (Eq a) => Ord a where
  compare x y = if x==y then .......

• class keyword: A class declaration introduces a new type class and the overloaded operations that must be supported by any type that is an instance of that class.

class Num a where 
      (+) :: a -> a -> a 
      negate :: a -> a

• instance keyword
  An instance declaration declares that a type is an instance of a class and includes the definitions of the overloaded operations - called class methods - instantiated on the named type.

instance Num Int 
where x + y = addInt x y 
negate x = negateInt x

*] Functors and (applicatives)

functor: able to apply regular function on data types

applicative: take out func in one container, take out param from another container, apply f on param, put result back to the container

<*> upacks the contents, do things, pack back

skipped monad, regular language

Q3 - July 14,15

Regular Languages
Grammars
LL Parsing
LR Parsing:

2] Grammars

• (non)terminals, production(S->N verb P: context-free verses xS->blah...), sentence(contains (non)terminals..), parse tree, left-recursive(S->S+X), ambiguous (more than 1 parse tree for a sentence)

• use a gramar to draw the parse tree of a sentence

• Right Linear grammars

  • is one in which all the productions have the form E->xA or E->x
  • This corresponds to the regular language

• fixing ambiguity

  stratification: use recursion only on one side. (left-recursive means "associates to the left"); Put your higher precedence op lower in the tree. (altho may produces highly unbalanced tree)

• first/follow set

3] LL parsing (top-down)

• non-terminals consume input

  
  

• left recursion causes trouble

  • rewrite:

    
    

• common prefixes are bad (cause confusion)

  • just extract the common prefix and inline them

• if a grammar is ambiguous, there's gonna be a shift-reduce conflict (two are almost equivalent both ways)

LR PARSING NO VIDEO, SKIPPED COMBINATOR PARSING

note in the second last rule, it has to be non-terminals left to the cursor

Q4 - July 28,29

1] Unification: to satisfy multiple constrains

• use substitute, deconstruct(f(a)=f(b) => a=b), reorient(var = ..), drop
• the problem is: given terms s and t, try to find a substitution q that q(s) = q(t); if such is possible, s and t unify.

2] Small Step Semantics

skipped

3] Typing Semantics

- Hoare Logic??

*] Params

1. static binding: arributes bound at compile time

2. dynamic binding: (the value attribute is most likely to be dynamic)

3. static typing: the type of vars are known at compile time (haskell)

4. dynamic typing: can change the var time on the go (perl)

5. static(lexical) scoping / dynamic scoping

*) polymorphism: we can have the advantages of strong typing and dynamic typing at the same time:); Using overloading, paramized(c++ template) and automatic..

• Parameters