4080 Midterm definitions

Simplicity

A language should help a programmer think about the problem in a clear manner not add complexity to the problem solving processs. the language feature set should be minimal, with the rules on how to apply them and combine them as simply and clear as possible

Orthogonality

Refers to the way the different constructs can be combined, and how these combinations are simple to understand and meaningful in the language

Orthogonality example

int = double + int

Level of abstraction

The degree to which the language allows the definition of powerful data abstractions that approxamitaly construct the problem domain

Portability

Refers to the degree to which a program can be moved, or transported from the system it was created in to another computer

Cost

The total cost of using a programming language. i.e. cost of development, compilation, maintenance, execution, etc…

Expressivity

How flexible is the language in providing concise, different ways of defining algorithms and comuptations.

Design issues: Computer architecture

Languages that introduce powerful abstractions that move away from the underlying architecture model have to tackle the problem of how to bridge the abstraction gap introducing execution and runtime design issues.

design issues: implementation

* compilers: source code is translated to machine code
* interpreters: source code is parsed and executed in real time
* virtual machines: middle ground between complilers and interpreters.

Syntax

Lexicon: alphabet (valid symbols), rules to make words

Grammar: rules to create valid sentences (expressions, statements, programs)

Semantics

The meaning behind the language. Without it the language is useless

Alphabet

The set of all valid symbols in the language (0-9, a-z, A-Z)

reserved words

Set of words that programmers may not use as a name. Some of these words will never be used by the language.

Variables

Holds a value, has a datatype, (name) identifier, can be changed (destructively updated), name for a memory location that holds a value of a particular type and can be destructively updated.

Binding

Connection or relation between a name and a property in a program

\

Types of Binding

Memory (memory allocation), Type, scope

Binding time

binding that happens either before exectution (static binding), or during execution (dynamic binding)

Memory Binding (memory allocation)

The process of reserving a block of memory to a particular name. Data allocated statically lives in the data section and persists throughout execution of the program.

Static Binding (static memory allocation)

The allocation happens before execution typically done by the compiler.

Typing (Type binding)

Refers to the association of a name to a type. Can happen statically and dynamically.

Static Typing

Names are typed (assigned a type) before the program runs

Dynamic Typing

Names are assigned a type as the program runs

Explicit Typing

If a language requires the user to explicitly specify the type of element with a syntactic feature (like a keyword)

Implicit Typing

If a language doesn’t require the user to specify the type of element with a syntactic feature

Scoping (scope binding)

The process of associating a name with a scope

Scope

The region/block/area in the code where a name is visible

Static Scoping (Lexical Scoping)

The scope of a name is defined at programming / writing time with lexical features in the code.

Dynamic Scoping

the visibility of names is determined while the program runs by looking at the stack of activation seconds.

Expressions

Sequence of words/symbols (usually operators and operands) that yields a value (meaning/sentiment)

Operators

A syntactic feature in a language that represents a function that takes input and produces a value. It produces an outcome from an input.

Depending on numer of operands an operator can be classified as:

* unary (one operand !, &)
* binary (2 operands: + - \*)
* ternary (3 operands : ?)
* n-ary (n operands)

Depending on the placement of operands we can classify operators as:

* prefix (operator is before the operand: + 3 4)


* infix (operator is between operands 3+4)
* Suffix (operator placed after operands: x++)

Types

The type T of a name is a property that describes the nature of the data associated with the name, and how it should be handled. Its a property associated with a name (var, const, func) that describes a specific property description of that name (size and how it should be handled)

Common Primitive Types

* integral number types
* floating point numbers
* character types
* boolean types

Integral Number Types

* integers (int) (32 bits)
* longs (long) (64 bits)
* short (16 bits)
* byte (8 bits)

Floating point numbers

* float (32 bits)
* double (64 bits)

Character types

Char

* ASCII (8 bits)
* UNICODE (1-4 bytes)

Boolean Types

bool (8 bits) (Side note: we only need 1 bit but we have to use a full byte)

User defined types

Any type created by the user. The variety of the mechanism used to create these types is high, and the complexity can go from simple enumerations to full blown ADTs

Arithmetic Expressions

Any expression that yields a numerical type

Common Arithmetic Operators

* addition (+, plus)
* subtraction (-, minus)
* multiplication (\*, times, x)
* division (/, div)
* Exponentiation (\*\*, ^)
* Modulo (%, mod)

Order of evaluation

in what order are operands evaluated

Precedence

A mechanism to sort ambiguous expressions by a hierarchy of operators, where the position in the hierarchy determines the relative binding strength of the operator.

Common Precedence order for Arithmetic Operators

1. exponentiation
2. modulo
3. multiplication and division
4. addition and subtraction

Parentheses

If order of evaluation and precedence yield an expression with semantics different than desired then parentheses can be used to override these and impose a particular evaluation order

Side effects

An expression is said to have side effects if evaluating it results in visible change (destructive update) in memory

Expressions with side effects

an expression has a side effect if evaluation of the expression results in visible change (destructive update) in memory. If an expression is side effect free we say it’s pure.

Referential Transparency

an expression is referentially transparent if the substitution of the expression by the value it yields results in a program with the same semantics

Overloading of operators

an operator is overloaded if it performs more than one function depending on the type of operands

Overloading example

“pre” + “fix”

2 + 3

Mixed Mode Expressions

An expression in which you have more than one type of operand

Example of a mixed mode expression

int x = 7

real y = 32.5

int z = x + y

// + is overloaded with both int and floating addition

Type Conversions

In certain circumstances a program will require converting a numerical type into another.

Type Coercion

If the conversion is implicit/automatic

Explicit type conversion (casting)

If a type conversion is explicit and performed with some syntatic feature provided by the language

Overflow

Occurs when an arithmetic operation results in a number greater than the maximum representable number in the current data format

Underflow

Occurs when a floating point operation results in a number that is less than the minimum representable number

Relational Expressions

* Great than (or equal)
* Less than (or equal)
* equals
* not equal

Logical expressions

* Logical and (&, &&, and)
* logical or ( |, ||, or )
* logical not (!, \~, not, -)
* logical implication (implies, =>, →)

Short circuit evaluation

A form of lazy evaluation in which given a logical binary operation, if evaluation of the first operand is enough to determine the value of the expression, then the second operand is not evaluated.

Strings

a sequence of characters usually enclosed by syntatic delimiters (“ “, ‘ ‘, / /)

Design and implementation issues (arrays)

* Arrays: fixed size
* linked lists: slow access to characters in the string, changing content is slow
* array list

Design and implementation issues

arrays, mutability, and types of subscript

mutability

Possible to change the string once created

Type of subscript

Typically integers since indices refers to discrete locations in memory. In some languages arrays may use strings as indices.

arrays

A sequential arrangement of elements (or items) with a fixed size in a continuous block of memory. Accessible because it has an index.

\
The simplest data structure in most imperative languages.

Symbol Table

see image:

An orthoganal language

It goes hand in hand with simplicity. But when there are a lot of exceptions it violates orthogonality.

Keywords

These are words used by the language for a particular purpose. Reserved words that are acutally used in the language.

Identifiers

Special characters allowed in words

Literals

Numbers, characters, etc…

Integer (bits)

32 bits

short (bits)

16 bits

long (bits)

64 bits

byte (in bits)

8 bits

float

32 bits

double (bits)

64 bits

ASCII (bits)

8 bits

bool (bits)

8 bits

UNICODE (bits)

1-4 bytes

prefix

the operator is **before** the operand: + 3 4

infix

the operator is **between** operands 3+4)

Suffix

the operator placed **after** operands: x++