Core Topics Continued - created from Mind Map

Página 1

Recursion

a method calling itself

Indirect recursion: Method A calls method B that calls method A

Potentially can go on forever (until memory full - Stack Overflow

Very powerful construct based on mathematical induction.

Recursive programming

Programming recursively

All loops can be implemented as recursive calls

Inefficient in java, but core concept in functional programming

int f(int x) { if ( x

When programming, "solve" a problem by using another method (call it before you implement it)

When this other method is the calling method, you have recursion.

Recursion is not a goal in itself

Recursive data structures (XML documents, file directories (called folders in windows), linked lists etc.) are most easily handled with recursive functions.

Programming Language Concepts

Paradigms

Concepts

Type Systems

Interpreted languages vs compiled languages

Imperative

Logic

Functional

describes computation in terms of statements that change a program state

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

Popularized by Prolog

Based on predicate calculus

Starts with statements of facts – parent(john, jake), parent(jake, jack)

Uses rules – grantparent(X,Z) :- parent(X,Y), parent (Y,Z)

Uses inference to determine true statements – grantparent(A, jack). will result in A = john

Very good at searching solutions

Basically implements the depth first search algorithm (as used for certain kinds of AI)

Based on mathematical "pure" functions

Allows for straightforward mapping to computer science

Functions are first class

Based on recursion (and mathematical induction), and conditional expressions (not on explicit loops)

No variables (but named parameters), no side effects

By default thread safe

Lisp, Scheme, ML, Haskell

Primitive

Type

Literal

Constant

Variable

Scope

Namespace

Function

Expression

Operator

Statement

Primary building block of which other composite types can be build

Corresponds (mostly) with cpu supported type

Operations generally translate directly to machine instructions

Primitive (subset of built-in)

Built-in (generally primitive + string + array)

User defined

All values have a type. Different types have different sizes, thus type is needed at run-time.

Enumerations

Range types

Structured / composite types (classes)

Directly typed in to code

Mostly only for built-in types

C++11 allows user defined literals

Sometimes has special type system support for conversions

Name that represents a value that is defined at compile time.

Name that represents a storage location for a value.

Block – Visible inside the block of definition

Function – Visible for the function

Class – Visible in the entire class

Unit – Visible in the file

Global – Visible for the whole program (often with import rules), sometimes only at runtime

Package in Java

Module in Python

Namespace in C++, XML

Allows for names to be reused without conflicts

Especially useful for libraries, as naming conflicts can be really annoying (esp. as the linker works on a global level)

Group of functionality that takes parameters and returns a value

If pure, only depends on (and doesn't change) its parameters. Repeated invocation has the same results.

Non-pure functions may use external state (a file, the time, etc.), or modify parameters (random.nextInt())

Object member functions have the object as a parameter

A variable reference

A function call

A literal

The application of a unary operator on an expression

The application of a binary operator on two expressions

An expression always results in a value

Unary (-x), Binary (x + y) or ternary ( _ ? _ : _)

Makes compound expressions possible

Some languages only have operator for built-in types, others allow overloading

Operator precedence makes custom operators tricky.

Building block of a code block (such as a function)

Does not necessarily result in a value

An expression may be a statement (depending on the language)

Could be an assignment

Could be a definition (variable, type, function)

Static typing – Types are checked at compile time

Dynamic typing – Types are checked at run time

Strong vs Weak

Type Compatibility

Types are specified

"more text" – Can be alleviated using type inference.

Sometimes needs type casting to interpret as another type (with checks)

Sometimes automatic conversion (coercion) is used (from int to long)

Allows the compiler to check correctness

"less text"

Allows for "duck typing"

Type errors become apparent at run-time

As different types need different storage sizes, must be heap bound

Any object with the needed methods will work

Like interfaces without the need for an interface

(C++ templates do this at compile time)

Strong detects all type errors at compile or run time

Java is strong

C/C++ allow aliasing, unsafe casts, and union types are not checked

Structure type compatibility

Name type compatibility

Most languages have a combination

If the structure is the same, the type is the same.

What about degrees Celcius vs Fahrenheit

Type is only compatible with itself

Gray area

A parser reads the code and creates (possibly partially) an abstract syntax tree

An interpreter will execute the AST

A compiler will translate the AST into an alternative (executable) representation.

Core Topics Continued