Core Topics Continued

Recursion
1. a method calling itself
2. Indirect recursion: Method A calls method B that calls method A
3. Potentially can go on forever (until memory full - Stack Overflow
4. Very powerful construct based on mathematical induction.
5. Recursive programming
  1. All loops can be implemented as recursive calls
    1. int f(int x) { if ( x<1 ) { return 0; } return x + f(x-1); }
  2. Inefficient in java, but core concept in functional programming
6. Programming recursively
  1. When programming, "solve" a problem by using another method (call it before you implement it)
  2. When this other method is the calling method, you have recursion.
  3. Recursion is not a goal in itself
  4. Recursive data structures (XML documents, file directories (called folders in windows), linked lists etc.) are most easily handled with recursive functions.
Programming Language Concepts
1. Paradigms
  1. Imperative
    1. describes computation in terms of statements that change a program state
    2. The term is used in opposition to declarative programming, which expresses what the program should accomplish without prescribing how to do it in terms of sequences of actions to be taken
  2. Logic
    1. Popularized by Prolog
    2. Based on predicate calculus
    3. Starts with statements of facts – parent(john, jake), parent(jake, jack)
    4. Uses rules – grantparent(X,Z) :- parent(X,Y), parent (Y,Z)
    5. Uses inference to determine true statements – grantparent(A, jack). will result in A = john
    6. Very good at searching solutions
    7. Basically implements the depth first search algorithm (as used for certain kinds of AI)
  3. Functional
    1. Based on mathematical "pure" functions
    2. Allows for straightforward mapping to computer science
    3. Functions are first class
    4. Based on recursion (and mathematical induction), and conditional expressions (not on explicit loops)
    5. No variables (but named parameters), no side effects
    6. By default thread safe
    7. Lisp, Scheme, ML, Haskell
2. Concepts
  1. Primitive
    1. Primary building block of which other composite types can be build
    2. Corresponds (mostly) with cpu supported type
    3. Operations generally translate directly to machine instructions
  2. Type
    1. Primitive (subset of built-in)
    2. Built-in (generally primitive + string + array)
    3. User defined
      1. Enumerations
      2. Range types
      3. Structured / composite types (classes)
    4. All values have a type. Different types have different sizes, thus type is needed at run-time.
  3. Literal
    1. Directly typed in to code
    2. Mostly only for built-in types
    3. C++11 allows user defined literals
    4. Sometimes has special type system support for conversions
  4. Constant
    1. Name that represents a value that is defined at compile time.
  5. Variable
    1. Name that represents a storage location for a value.
  6. Scope
    1. Block – Visible inside the block of definition
    2. Function – Visible for the function
    3. Class – Visible in the entire class
    4. Unit – Visible in the file
    5. Global – Visible for the whole program (often with import rules), sometimes only at runtime
  7. Namespace
    1. Package in Java
    2. Module in Python
    3. Namespace in C++, XML
    4. Allows for names to be reused without conflicts
    5. Especially useful for libraries, as naming conflicts can be really annoying (esp. as the linker works on a global level)
  8. Function
    1. Group of functionality that takes parameters and returns a value
    2. If pure, only depends on (and doesn't change) its parameters. Repeated invocation has the same results.
    3. Non-pure functions may use external state (a file, the time, etc.), or modify parameters (random.nextInt())
    4. Object member functions have the object as a parameter
  9. Expression
    1. A variable reference
    2. A function call
    3. A literal
    4. The application of a unary operator on an expression
    5. The application of a binary operator on two expressions
    6. An expression always results in a value
  10. Operator
    1. Unary (-x), Binary (x + y) or ternary ( _ ? _ : _)
    2. Makes compound expressions possible
    3. Some languages only have operator for built-in types, others allow overloading
    4. Operator precedence makes custom operators tricky.
  11. Statement
    1. Building block of a code block (such as a function)
    2. Does not necessarily result in a value
    3. An expression may be a statement (depending on the language)
    4. Could be an assignment
    5. Could be a definition (variable, type, function)
3. Type Systems
  1. Static typing – Types are checked at compile time
    1. Types are specified
    2. "more text" – Can be alleviated using type inference.
    3. Sometimes needs type casting to interpret as another type (with checks)
    4. Sometimes automatic conversion (coercion) is used (from int to long)
    5. Allows the compiler to check correctness
  2. Dynamic typing – Types are checked at run time
    1. "less text"
    2. Allows for "duck typing"
      1. Any object with the needed methods will work
      2. Like interfaces without the need for an interface
      3. (C++ templates do this at compile time)
    3. Type errors become apparent at run-time
    4. As different types need different storage sizes, must be heap bound
  3. Strong vs Weak
    1. Strong detects all type errors at compile or run time
    2. Java is strong
    3. C/C++ allow aliasing, unsafe casts, and union types are not checked
  4. Type Compatibility
    1. Structure type compatibility
      1. If the structure is the same, the type is the same.
      2. What about degrees Celcius vs Fahrenheit
    2. Name type compatibility
      1. Type is only compatible with itself
    3. Most languages have a combination
4. Interpreted languages vs compiled languages
  1. Gray area
  2. A parser reads the code and creates (possibly partially) an abstract syntax tree
  3. An interpreter will execute the AST
  4. A compiler will translate the AST into an alternative (executable) representation.

Next up

Core Topics Continued

Description

Resource summary

Similar

	Created by Bhavit Chhatralia almost 10 years ago