CPL Test 1

reasons for studying concepts of programming languages

express ideas, choosing appropriate languages, increased ability to learn new languages, better understanding of significance of implementation, better use of languages that are already known, overall advancement of computing.

programming domains

scientific applications (Fortran), Business applications (COBOL), Artificial intelligences (LISP), Systems programming (C), web software (HTML, PHP, Java Script)

von neumann architecture

data and programs stored in memory, memory is separate from CPU, instructions and data are piped from memory to CPU, basis for imperative languages

language categories

imperative, functional, logic, markup or hybrid

imperative language

uses a sequence of statements to change a programs state and achieve some goal. includes variables, assignment statements, and iteration. supports object-oriented programming. include scripting languages. include visual languages. Ex: C, Java, Perl, JavaScript, Visual BASIC .NET, C++

functional language

Approaches computation as a process of applying functions to given parameters. Ex: LISP, Scheme, ML, F#, Miranda

logic language

a declarative programming language that expresses programs as sets of facts and logical rules, allowing computers to perform computations based on formal logic rather than step-by-step instructions. Ex: Prolog

Markup/programming hybrid

a system for adding annotations (tags or codes) to a document to describe its structure, presentation, and meaning, allowing computers to interpret and display the content correctly. Ex: JSTL, XSLT, HTML, LaTeX

language evaluation criteria

readability (most important), writability, reliability, cost. all interdependent on one another (ex readability can improve reliability by making it harder for programmers to misunderstand)

compilation

programs are translated into machine language. slow translation, fast execution; includes JIT systems. use on large commerfical applications

pure interpretation

programs are interpreted by another program known as an interpreter; python. use on small programs or when efficiency is not an issue

hybrid implementation system (compilation and interpretation)

compromise between compilers and pure interpreters. small and medium when efficiency is not the first concern. Ex: Perl

phases of compilation

lexical analysis: converts characters in the source program into lexical units. syntax analysis: transforms lexical units into parse trees which represent the sytantic structure of program. semantics analysis: generate intermediate code. code generation: machine code is generated.

von neumann bottleneck

connection speed between a computer’s memory and its processor determine the speed of a computer, though program instructions can often be executed much faster. This is the primary limiting factor in the speed of computers

Preprocessors

preprocess macros are commonly used to specify code from another file is to be included. processes a program immediately before the program is compiled to expand embedded preprocessor macros.

readability

the ease with which programs can be read and understood. simplicity/orthogonality, control structures, data types and structures. (maybe expressivity)

writability

the ease with which a language can be used to create programs. simplicity/orthogonality, control structures, data types and structures, syntax design, support for abstraction, expressivity.

reliability

conformance to specification. simplicity/orthogonality, control structures, data types adn structures, syntax design, support for abstraction, expressivity, tpe checking, exception handling, restrict aliasing. 

cost

the ultimate total cost. development, maintenance and reliability most important criteria

orthogonality

means that a relatively small set of primitve constructs can be combined in a relatively small number of ways to build the control and data structures of the language. Closely related to simplicity. need a happy medium. too many rule exceptions leads to non-readability. too much orthogonality would allow for weird applications of the rules.

power of a language

the ability to express requests in very few symbols

other evaluation criteria

portability: ease with which programs can be moved from one implementation to another (degree of standardization of the language), generality: applicability to a wide range of applications, well-definedness: completeness and precission of the language’s official definition.

two pass compilers

go through a first pass to find functions defined after they are used. In the second pass use the functions it found and incorporate them into the program where they are used.

one pass compilers

only go through the code once so functions must be defined before they are used.

APL

a programming lanfuage. interpreted language with dynamic typing. very powerful language. expressions evaluate right to left.

lazy evaluation

evaluation strategy which delays the evaluation of an expression until its value is needed

standard way to publish algorithms for over 20 years

ALGOL 60

ALGOL

the primary first imperative language. “mother of all imperative languages”. all subsequent imperative languages are derived from ALGOL

pessimal algorithms

the absolute worst version of an algorithm you can come up with

four abstraction concepts used in sematic data models (such as EER)

classification and instantiation, identification, specialization and generalization, aggregation and association.

syntax

the form or structure of the expressions, statements, and program units (is it written correctly)

semantics

the meaning of the expressions, statements, and programs (what does it mean)

sentence

a legal string of characters over some alphabet

language

a set of sentences

lexeme

the lowest level syntactic unit of a language (ex *, sum, begin)

token

a category of lexemes (ex identifier)

lexemes and tokens in: index = 2 * Count + 17;

lexemes: =, 2, *, Count, +, 17, ;.  tokens: identifier, equal_sign, int_literal, mult_op, identifier, plus_op, Int_literal, semicolon (match with the lexemes)

what determines the order of operations

the grammar

recognizer

tokenizer. reads input strings over the alphabet of the language and decides whether the input strings belong to the language.

generator

device that generates sentences of a language. one can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator.

backus-naur form

equivalent to context free grammars. an example of a metalanguage.

derivations

every string of symbols in a derivation is a sentential form. A sentence is a sentential form that has only terminal symbols. A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded. A derivation could be either leftmost or rightmost or mixed (mixed is impractical).

What is the language of this grammar?

L = {aⁿbⁿ | n >= 0}

nonterminal symbols

symbols that can be defined with other symbols. set represented by N. (has something to the right of the arrow)

terminal symbols

symbols that are fully defined on their own. set represented by sigma. (will not be defined by something to the right of the arrow)

Regular grammars

productions must be of the form A → xB, where A and B are nonterminal symbols and x is a string of terminal symbols

context-free grammars

productions must be of the form A → alpha, where A is nonterminal symbol and alpha is a string of terminals and nonterminals in any order (essentially the same as BNF grammar)

context-sensitive grammars

productions must be of the form alpha → beta where alpha and beta are strings of terminals and nonterminals with the restriction that the number of symbols in alpha may not exceed the number of symbols in beta.

unrestricted grammars

production rules are of the form alpha → beta with no restrictions (problems figuring out exactly how to go about things)

What is the language of this grammar?

L = { aⁿbⁿcⁿ | n >= 1}

six attributes of a variable

name, address, value, type, lifetime, scope

name (variable)

maximum length? are connector characters allowed? are names case sensitive? are special words reserved words or keywords?

address (variable)

the memory at which a variable is located. may have different addresses at different times in execution or at different places in a program.

value (variable)

the contents of the location at which the variable is associated

type (variable)

determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines precision

alias

two different variable names that refer to the same memory location. changes made through one affect the other. can cause side effects or confusion in programs.

binding

an association between an entity and an attribute, such as between a variable and its value, or between an operation and a symbol. binding time is the point at which binding takes place.

possible binding times

language design time, language implementation time, compile time, load time, runtime

language design time binding

language features are decided by the language designer and certain symbols bound to certain actions by the language’s grammar (* being multiplication for example)

language implementation time binding

details of how the language works are fixed by the compiler/interpreter implementer (ex defining that int uses 32 bits)

compile time binding

When the program you wrote is translated into machine code. The compiler checks types, resolves static bindings, and lays out code and data structures. (binding a variable to a type and checking that + is used correctly for the types involved)

load time binding

when the compiled program is loaded into memory for execution, binding occurs. (assigning static variables to actual memory addresses)

runtime binding

when the program is actively running and dynamic bindings happen (assign local variables to memory on the stack, resolving virtual method calls, or handling dynamic typing in languages like Python)

static vs. dynamic binding

a binding is static if it first occurs before run time and remains unchanged throughout program execution. A binding is dynamic if it first occurs during execution or can change during execution of the program.

explicit vs. implicit declaration

explicit declaration is a program statement used for declaring the types of variables (int i). implicit declaration is a default mechanism for specifying types of variables through default conventions, rather than declaration statements (python just uses whatever the variable is assigned to determine its type)

variant record

used in Ada. a variable with variants depending on a discriminant tag. only one variant’s fields are active at a time allowing the program to save space.

overlay

variants that share the same space in memory. can only have one active variant at a time. used to conserve memory.

ambiguous vs. unambiguous grammars

an ambiguous grammar allows more than one parse tree for the same string, whereas an unambiguous grammar has exactly one parse tree per valid string.

operator presedence specified in a grammar

expression has the lowest precedence because it relies on the evaluation of term.
term has higher precedence because it can still rely on factor.
it seems circular (since factor may rely on an expression), but the whole expression can be enclosed in parentheses and treated as a single factor — making it a subproblem. factor still must be evaluated first.

operator associativity

defines how operators of the same precedence are grouped (think the addition and subtraction part of PEMDAS). could be left to right or right to left for example. ensures consistent parsing when multiple operators of equal precedence appear.

important things about Miranda

a purely functional programming language, meaning you ask the program to do something without specifying how to do it. uses lazy evaluation (only computes what is necessary), has a strong type system that helps catch errors early, no side effects in that functions always give the same result for the same input, and uses lists and function definitions instead of loops.

FORTRAN equivalence / unions / isub

older languages like FORTRAN (equivalence) and C (unions) and PL/I (isub) used equivalence and overlays to reuse memory for different variables or data types.

reserved vs. keywords

a reserved word is one that cannot be used by a programmer as an identifier and keywords are words that have predefined special meaning within the syntax of the language.

language design trade-offs

reliability vs. cost of execution, readability vs writability, writability vs reliability