proglang-10-22-19.md

Midterm Review - Programming Languages - Oct 22nd, 2019

Python Method Resolution Order (Simple)

(We haven't gone through it in-depth)

• It's not depth-first search, but it's similar to it
• Just need to know it for simple cases
  • Non-multiple inheritance (the same as C++)

Interpreter vs Compiler

Interpreter

• Behavior is produced immediately

Compiler

• Produces executable code
• Executable code can be run by processor

Is Python interpreted?

Historically, python has been interpreted, but recently that has changed. Python is compiled into python bytecode and then it is interpreted immediately after. From a developer's point-of-view, it still seems like it is interpreted.

Laziness

• Values are calculated on-demand rather than when they are declared

Abstract Syntax Tree

(know what is)

Name Resolution

Static Scoping (Lexical)

• Scope is based on the structure of the code
• In C++, this refers to the curly braces
  • It looks at the inner scope and then the outer scopes
• This is all implemented in terms of Symbol Tables

Dynamic Scoping

• The order of the search reflects the function call stack

Dynamic Binding

• OOP
• If I call a function, how do I know which function to use? (Virtual Functions)

Lifetime vs Scope

Lifetime

• How long a variable is allocated is in memory

Scope

• Area or time when a variable is accessible by name

void example(){
    int q;
    q = 5;

    print(q);
}

In this case both the lifetime and scope of q are from the beginning of the function to the end of the function.

void example2(){
    SomeClass *v = new SomeClass;
    printf(v->whatever());
}

The lifetime and scope of v is from the beginning of example2 to the end of the function.

What is the lifetime of the thing that v points to?

Answer:

From when `example2` is called to the end of the program (because it's a memory leak)

What is the scope of the thing that v points to?

Answer:

It has no name so it has no scope

void example3() {
    static int w = 0;
    print(w++);
}

A static variable's lifetime and scope if from the start of the program to the end of the program

Tail-call Recursive

A program is tail-call recursive then the last thing that the program does is make a recurisive

From HW5:

def mystery(lst):
    if len(lst) > 2:
        return lst
    return [lst[1]] + [lst[0]] + mystery(lst[2:])

This is not tail-call recursive because the last thing happening in the function is appending lists.

Haskell

Reminders

• a : [b, c, d] prepending an item to a list
• [a] ++ [b] appending two lists

Types

-- must being with a capital letter
data TypeName param = Bar b
                    | Baz Int String a

Typeclasses

data Foobar = Bar | Baz

instance Ord Foobar where
    Bar <= Baz = True
    _ <= _ = False

Exercise: type signature

data Either a b = Left a | Right b
foo x = if x `mod` 2 == 0
    then Left x
    else Right "it's odd"

What is the type signature of foo?

Answer:

`foo :: Integral a => a -> Either a [char]`

Exercise: myzip

• zip :: [a] -> [b] -> [(a,b)]
• zip "hello" [1..]
  • this returns [('h',1) ('e',2) ('l',3) ('l',4) ('o',0)]

Make a function called myzip mimicking zip.

Answer:

```haskell
myzip [] _ = []
myzip _ [] = []
myzip (h1:t1) (h2:t2) = (h1,h2) : myzip t1 t2
```

Exercise: intersection

Return all the common elements of two lists without using recursion. Use higher-order functions.

Hint: use elem

Answer:

```haskell
intersection :: Eq a => [a] -> [a] -> [a]
intersection a b = filter (`elem` b) a
-- similar way with a lambda
-- intersection a b = filter (\x -> x `elem` b) a
```

Exercise: fromhex

Convert a hexdecimal to an integer

• should be the sum of each character's ASCII value
• You can use the function ord which returns the ASCII value of a char

letterToDigit :: Char -> Int
-- e.g. letterToDigit "f" = 15

stringToDigitValues :: String -> [Int]
-- e.g. stringToDigitValues "f3" = [15,3]

fromHex :: String -> Int
-- uses foldl

Answer:

```haskell
letterToDigit c
    | c `elem` ['a' .. 'f'] = (ord c - ord 'a') + 10
    | c `elem` ['A' .. 'F'] = (ord c - ord 'A') + 10
    | c `elem` ['0' .. '9'] = ord c - ord '0'

stringToDigitValues :: String -> [Int]
stringToDigitValues chars = map letterToDigit chars

fromHex :: String -> Int
fromHex s =
    let digitalvals = string toDigitalValues s
        myFunc acc el = acc*16 + el
    in foldl myFunc 0 digitalvals
```

Unasked Questions

• subtypes vs subclasses
• parametric vs ad hoc polymorphism
• mimicking thunks in python