Final Exam

Front 1

Ruby

Back 1

dynamically-typed(duck typing), object-oriented, interpreted, scripting language.

Front 2

Duck Typing

Back 2

the type of an object is determined at run-time. Advantage: Simplifies code. Disadvantage: Loss of compile-time error checking.

Front 3

Method Calls (Ruby)

Back 3

When a message is sent to an object
The methods of the object’s class are searched for a method with the same name.
If found, the body is executed.
Otherwise the methods of the superclass are searched.
This continues until the top of the class hierarchy, BasicObject is reached.
If the method is not found, then the method_missing message is sent to the original object.
Note: method_missing is defined in BasicObject, but may be overridden.

Front 4

Objects and Classes(Ruby)

Back 4

Everything in Ruby is an object.
An object contains the instance variables and a reference to its class.
Classes are objects.
Every object has a class.
Classes have a reference to their superclass
Classes have references to the methods.

Front 5

Adding Methods to Objects(Ruby)

Back 5

In Ruby methods may be added to objects. These methods are called “singleton methods”

Front 6

The singleton class

Back 6

When a singleton method is defined, Ruby creates an anonymous class object and sets this as the classes new Class object and sets the original Class object as the superclass.

Front 7

Modules

Back 7

Modules are also objects.
They contain methods and instance variables.
Multiple Modules may be included in a Class.
How does Ruby resolve conflicts in Modules?
A Module may be included in different Classes.

Front 8

Including a Module(Ruby)

Back 8

When the statement:
include ‹module name›
is executed
Ruby defines an anonymous Class object that references the Module object
Ruby inserts this class as the superclass.

Front 9

Resolving Conflicts in Modules

Back 9

The chain of superclasses is a single-linked-list that acts as a Last-In-First-Out queue.
Thus the most recently included Module’s methods are searched first.

Front 10

Blocks

Back 10

A block is a sequence of Ruby statements and expressions, optionally preceded with an argument list.
Blocks are delimited by either { ... } or do ... end
A block may only appear after a method invocation.
The invoked method calls the block using the yield statement.
The value of the block is the value of the last statement or the value passed to the next statement executed in the block.

Front 11

Procs

Back 11

A block is not an object.
The class Proc encapsulates a block.
A Proc object can be
stored in a variable
passed as an argument
returned from a function
You invoke the associated block by calling the call method of the Proc object.

Front 12

The & operator

Back 12

If the last parameter of a method begins with a & character
then the block will be converted to a Proc and bound to this parameter.
If the & character is placed before a variable that is a Proc object
the Proc object is converted back to a block

Front 13

lambdas

Back 13

A lambda is a Proc that is created using the lambda method or the -> operator.
The resulting Proc object differs from what is returned from Proc.new:
When called, the number of arguments to the lambda must match the expected number of arguments.
The return statement from a lambda returns to the caller.
The return statement from a proc returns out of the caller.

Front 14

Groovy

Back 14

Groovy is a optionally dynamically-typed, object-oriented, compiled, scripting language.

Front 15

Scripting language

Back 15

There is an implicit main method

There are built-in methods to access the operating system

Front 16

Meta-Object Protocol (MOP)

Back 16

A Meta-Object Protocol (MOP) are the capabilities in a dynamic language (such as Groovy) that enable metaprogramming.

Front 17

The Groovy MOP consists of:

Back 17

reflection
metaclasses
categories
expandos

Front 18

MetaClass

Back 18

The MetaClass maintains the metadata about a Groovy class
methods, fields, and properties
Unlike the java.lang.Class class, the MetaClass can be modified at run-time.
MetaClass objects are assigned to the Java classes by the Groovy run-time.

Front 19

Mixins

Back 19

A mixin is a class that is mixed in (merged) with another class.
Similar to Ruby’s module
A mixin is added to a class as part of its declaration using the @Mixin annotition
A mixin is added to a class during run-time using the mixin method.

Front 20

Scala

Back 20

statically-typed, object-oriented, compiled, scripting language.

Front 21

Statically-typed

Back 21

Type of an object is determined at compile time
Variables are restricted to hold values of a particular type.
Variables may be declared without specifying their type, but the type is determined by the type of the expression that initialized them.

Front 22

Traits

Back 22

Traits are classes that are meant to be added as a mixin to some other class.
Traits do not have constructor parameters.
Traits can define methods or declare abstract methods.
A class/trait that mixes in an abstract method must implement it.
A trait that only defines abstract methods is the same as a Java interface.
Java interfaces may be used as traits.

Front 23

Singleton Objects

Back 23

A singleton object with the same name as a class is known as a companion module.
Companion modules act like ruby’s class objects in that they contain the equivalent of static methods and instance variables.

Front 24

Option Type

Back 24

The Option type is used to express values that might not be present.
The case subclass Some wraps a value.
The case subclass None indicates that there is no value.
Is safer than using null return as in Java.
Note Java 8 has introduced an Option type.

Front 25

Actors

Back 25

An actor is an object that processes incoming messages and executes actions associated with it.
Messages are immutable.
Actors are assigned threads from a thread pool.

Front 26

The Actor trait

Back 26

The Actor trait has one abstract method:
receive
that takes a partial function.
The partial function contains case clauses for each message.
The messages are case classes.

Front 27

Software Transactional Memory

Back 27

Turns the Java heap into a transactional dataset similar to database transactions.
ACID
Atomiticy
All modifications are “all or nothing”
Consistency
Transactions go from one consistent state to another
Isolation
No other transaction sees partial changes
Durability
Not provided by STM (local memory is not durible)

Front 28

State

Back 28

In imperative programming data is directly accessed and mutated.
Problem if two concurrent threads try to access/mutate at the same time.
Especially a problem if multiple values need to be changed consistently.
In STM isolates the values from what are called “identities”
The values are immutable
The identities can change, but do so as atomic operations.

Front 29

PROLOG

Back 29

Prolog (PROgramming in LOGic*) is a declarative language.
Instead of telling the computer the steps to solve the problem, the programmer defines the problem and the computer finds the solution.

Front 30

Prolog Syntax

Back 30

facts Statements that are true
rules Rules of inference
queries Problems to be solved

Front 31

Clojure

Back 31

a compiled dynamic functional programming language based on LISP.
Programs are compiled into JVM byte code, or CLR or Javascript.
The basic execution unit is the function.
The basic data structure is the list, but
Clojure adds the vector, map, and set to the available data structures.
Functions are represented by lists, thus the program and data are the same structure.

Front 32

Data Types (Clojure)

Back 32

Numbers
Symbols
Keywords
Strings
Characters

Front 33

Data Structures (Clojure)

Back 33

Lists, Maps, Vectors, Sets

Front 34

Higher-Order Functions

Back 34

A higher-order function is a function that takes a function as one of its arguments and/or returns a function as its result.

Front 35

Macros

Back 35

When a function is called each of its arguments are evaluated.
When a macro is called, the arguments are not evaluated.
The result of a macro call is Clojure code which will be compiled.
Macros allow you to add a feature to the language.

Front 36

Lazy Sequences

Back 36

The lazy-seq macro generates lazy sequences. (lazy-seq & body) The body is evaluated only when the seq function is called.

Front 37

Context Free Grammar

Back 37

A context free grammar consists of non-terminals and terminals
Non-terminals are of the form ‹string›
Terminals are of the form string
A non-terminal is defined by a string of terminals and non-terminals
More than one definition for a non-terminal is allowed.
Originally developed to study natural languages, these have proven very useful to define computer languages.

Front 38

Type 3 — Regular

Back 38

The left-hand side of a production rule is a single non-terminal
The right-hand side of a production rule is either
a single terminal
a single non-terminal followed by a terminal or a terminal followed by a single non-terminal (but not both in the same grammar)
Type 3 grammars can be expressed as regular expressions.
Type 3 languages can be recognized by a deterministic finite-state automata.

Front 39

Type 2 — Context Free

Back 39

The left-hand side of a production rule is a single non-terminal
The right-hand side of a production rule is a sequence of terminals and non-terminals
Type 2 languages can be recognized by a non-deterministic push-down automata (NP hard)
A sub-set of the type 2 languages can be recognized by a deterministic push-down automata (e.g. a computer program that is either recursive or uses a stack).

Front 40

Type 1 — Context Sensitive

Back 40

The left-hand side of a production rule consists of a sequence of terminals and non-terminals that contains at least one non-terminal.
The right hand side is the same sequence with the designated non-terminal replaced by a non-empty sequence of terminals and non-terminals.
e.g. The production rule established a context in which the designated non-terminal can be expanded, and the context is preserved.
Recognizing a type 1 language is NP hard. However, since programming languages are context sensitive, compilers are possible, but the context sensitivity is not part of the language’s formal definition.

Front 41

Type 0 — Phrase Structured

Back 41

There is no restriction on either the left-hand side or the right-hand side of a production rule.
Type 0 languages are equivalent to computer programs.
A general-purpose recognizer is not possible

Front 42

Parsing

Back 42

Parsing is the process of determining how a sentence was generated by the grammar.
The result is a Parse Tree

Front 43

Abstract Syntax Tree

Back 43

An Abstract Syntax Tree is a tree that shows the structure of the sentence.
The internal nodes are terminals or artificial nodes
The leaves are terminals.

Front 44

Lexer

Back 44

The Lexer parses the input into tokens.
It recognizes that sub-set of the grammar that is regular (e.g. type-3).
The lexer generator lex (flex) which is part of Unix (GNU) is regular-expression based.
A Lexer can also be generated using recursive-decent parsing.

Front 45

Recursive Decent Parsing

Back 45

Given a context-free grammar one can construct a parser as follows:
Define a method for each non-terminal
This method tries to match each of its choices to the input by looking at the next input token.
If there is a match, the method captures the input token and returns true.
If no match, the method leaves the input stream alone and returns false.

Front 46

Bottom-Up Parsing

Back 46

Bottom-up parsing constructs the parse tree starting at the leaves and working to the root.
The parser scans the input string from left to right.
Given a current input subsequence, the parser attempts to match this to the rhs of a production.
If it can match, it replaces the input symbols with the corresponding lhs.

Front 47

LR Parsing Algorithm

Back 47

The LR parsing algorithm is state/input driven.
There is a stack of symbols that represents the input that has been processed.
There is a stack of states that represents the history.
Given a current state/input either:
shift
The current input symbol is pushed onto the symbol stack
The next state is pushed onto the state stack
reduce
The top n symbols of the symbol stack are matched to the rhs of a production.
The top n states are popped off of the state stack
The lhs of the production is pushed onto the symbol stack
The next state is a function of the lhs and the current state

Front 48

What is a Domain Specific Language

Back 48

A computer programming language of limited expressiveness focused on a particular domain.*
Programming Language: Instructs computers to do something
Limited expressiveness: Generally not Turing Complete
Domain focus: Uses vocabulary specific to the problem domain.

Front 49

Types of DSLs

Back 49

Internal:
Build upon an existing general-purpose programming language:
Example: jMock expectations
External:
Processed by an interpreter or compiler:
Examples: Makefiles, SQL, Ant build.xml*