Midterm Review
Evaluating a Language
Reliability How well does it perform to specification?
Readability How easily can the language be read and understood?
Writability How easily can someone write in the language
Reusability How easily can code be reused and shared?
Efficiency How fast is the code and the compiler?
Simplicity/orthogonality ∙ ∙ ∙ ∙
Control structures ∙ ∙ ∙ ∙
Data types & structures ∙ ∙ ∙ ∙
Syntax design ∙ ∙ ∙
Support for abstraction ∙ ∙ ∙
Expressivity ∙ ∙
Strong/weak type checking ∙
Exception handling ∙
Restricted aliasing/pointer ∙
Efficiency Readability Writability Reliability
Reusability
Characteristics
Performance metrics
Evaluating a Language
Orthogonality
Combinational Many to Many Relationship
Sort One to Many Relationship
Number If one instance exists, any number can exist
Combinational Orthogonality – I have commands S1 and S2; If S1_a combines with S2_a, then S1 combines with all S2 commands
-Creating a variable, combines idea of variable creation and data types (type var = val)
Sort Orthogonality – I have commands S1 and S2; If S1_a combines with S2_a, then S1_a combines with all S2 commands
-If I can create a variable of a type that implies I should also be able to initialize it, make a constant and make an array (Array varType)
Number Orthogonality – When I have the ability to use a command somewhere, that implies I can use zero or more of that command in the same place
-Classes are an example, like those seen in Java in CSE205
‹#›
Programming Paradigms
Imperative/Procedural fully specified/controlled manipulation of named data in a step-wise fashion
Object-Oriented Encapsulation of state of the program in objects, which can be accessed only through operations defined on them. Also includes: Inheritance and Polymorphism
Functional/Applicative Higher level abstraction, simpler semantics, closer to math functions and referential transparency
Logic/Declarative set of facts about objects, rules about objects, and defining and questioning relations between objects. Get rid of programming altogether
Service-Oriented Programming Runs as a service, listening for connections and fulfilling requests (designed around networks)
Expression of Programs
Lexical Basic building blocks
Is the stuff its built of right?
For the purposes of this class we bundle this error with Syntactic for the most part so know it but do not expect it to be the correct answer.
Syntactic How lexical units are assembled.
Is the statement valid (BNF)?
Is it built correctly?
IF YOUR CODE DOES NOT COMPILE, YOU HAVE A SYNTAX ERROR
Contextual The structure of the semantics, the building blocks of the code.
Do data types do what you need them to? Did your code compile and run, but not give you a correct output?
Is it built from the right stuff?
EX) used integers when you need float/double, using Kilometres instead of Miles.
Semantic The overall meaning… is the logic correct? Did you code compile then bug during runtime?
Is the code doing what I want it to?
Syntactic Analyses: Syntax Graph
A language can also be defined by a syntax graph
if (condition) statements ;
else statements ;
if (a < 0) return -a;
if (a < 0) return -a; else return a;
switch (expr) { case value: statements ;
default: statements;
}
switch (ch) {
case '+': x = a + b; break;
case '-': x = a - b; break;
case '*': x = a * b; break;
case '÷': x = a / b; x = round(x); break;
default: printf("invalid operator"); break;
}
Does a while-loop’s syntax graph have a loop?
Very Simple Programming Language (VSPL)
Example: Define a Very Simple Programming Language (VSPL)
< expr > ::= < variable>
| (
Scheme
Imagine a world where we do things based only on… functionality.
“Does it work?” is your King.
Consistency is law.
Reliability is Faith
Von Neumann is in the Dungeon.
Life is good again.
Scheme: Background I
Known Paradigm: Imperative
Scheme’s Paradigm: Functional
Why Functional?
Von Neumann architecture has several issues…
side effects
difficult semantics
step by step design.
Tough to understand what’s happening sometimes
Scheme focuses on Pure Function
All inputs declared/Nothing hidden.
No shared states, mutable data, or side effects.
Scheme: Background II
Stateless: Input go in, it do job, it output.
Recursion: Loops are not a thing. All iteration is done through recursion.
Referential Transparency: It will do what you expect it to do and predict it to do.
Valuable for Reliability and Consistency
Very noticeable in Functional Programming.
Things do EXACTLY what you ask and return EXACTLY what you expect
Same output for the same input
Example: f(x) always returns the same value when given the same input
Scheme: Basic Syntax I
Identifiers: If we had variables, this is the closest thing we have. These are built using characters
Structured Forms: Lists, Vectors
Constant Data: numbers, characters, strings, quoted vectors, quoted lists, quoted symbols, etc
Whitespace: Literally useless to scheme. It means nothing. Only for readability
Comments:
; is the same as //
;;; a convention that states this comment describes a thing on the next line (such as a function)
Scheme: Basic Syntax II
Building Block: Expressions. A construct that returns a value
variable =
(
Prefix Notation:
The thing we wanna do is first followed by operands
Think (+ 2 3) the prefix is +.
Manifests in scheme as (
Resolve Order:
Inside out.
Imagine diving to the bottom of the ocean before swimming to the surface
Predicates:
Procedure that returns a boolean value.
Example: list? checks if the thing it’s looking at is a list.
Data types (Primitive): Number, Boolean, Character, String
Scheme: Advanced Syntax I
Type Specific Syntax:
Certain predicates and syntax is specific to a type
Syntax: type-
type1->type2 for type conversion
Symbols:
Atomic Value
Syntax: ‘name (this is case sensitive. Has its uses)
The difference between a string and a symbol
Strings can be processed
Symbols can’t be processed
Scheme: Advanced Syntax II
Sameness
Three ways to check equivalence
eq?
Similar to eqv? but is capable of discerning some finer distinctions (probably your goto)
equal?
returns true if two items are recursively equivalent – pairs, vectors, strings, etc. Although often we just want to use the comparison for those things (string=?
eqv?
Returns true of the parameters should normally be regarded as the same – good for integers, characters and reals
Scheme: Advanced Syntax III
Conditionals: There are two ways to handle conditionals.
If statements
Syntax:
(if (
True Case
False Case)
Cond
Syntax:
(cond (
Scheme: Functions I
Function: A form that returns data
First Class Object: Passed around and Returned is good
Common Structure for Functions:
(define
If
Lambda creates a form that receives input and returns data
Define binds the form to a name, which we can then call.
Scheme: Functions II
Evaluations Techniques: Eager vs Lazy
Eager: A proactive system
Evaluates innermost first
Evaluates everything first
Lazy: Do I need this?
Evaluates outermost first
Evaluates as it runs
Only runs what it needs.
Scheme: Lists
Lists: 0 or more scheme expressions
meaning they can contain a lot of different data.
lists are naturally heterogeneous.
Can be homogeneous, but that’s semantic
Declaration:
`(1 2 3 4…)
(list 1 2 3… )
`(1 (1 2) 2)
Operations:
Car: returns the first data in the list
Cdr: returns the rest of the list
Various forms (caddr, caadr, etc)
Append: Stitches two lists together
Needs two lists.
Apply: Applies procedure to entire list
Syntax: (apply
Scheme: Recursion
This will be covered briefly again in the Prolog Section.
For now…
Pieces of Recursion
Base Case (When do I stop)
Recursive Case (How do I deep dive?)
Golden Rule: For the love of god, all recursive cases MUST get closer to the base case.
Patterns
Folds: How recursion is structured
right fold (Operate on first, combine with rest)
Left fold (tail recursion)
How to Study for Scheme Sections
Review homework
Go over quizzes
Look at lecture slides
Rewatch lectures
Questions will likely be reminiscent of the quizzes in style and approach.
Prolog
Two main components: Facts and Rules
Fact – a statement that asserts a truth, end with a period
sunny.
likes(pat, kris).
Rule – something that allows us to make a conclusion from the given facts
Can compound with AND (,) or OR (;)
Given the facts, is this true?
grandparent(X, Z) :- parent(X, Y), parent(Y, Z)
Based on Predicate Logic
Variables – capital letter
likes(pat, who). – its a fact that pat likes someone named who
likes(pat, Who). – returns the value of who pat likes
Wildcard
weather(phoenix, spring, hot).
weather(phoenix, summer, hot).
weather(phoenix, winter, warm).
weather(toronto, spring, cold).
weather(toronto, summer, hot).
weather(City, _ , hot).
City = phoenix;
City = phoenix;
City = toronto;
no
Input/Output
read(X)
– Read user input and store in X
write(‘hello world’)
Uses single quote
Double quote processes is as a list of ASCII characters
write(phoenix)
Writes variable phoenix
write(X) – notice the capital
Prints the current value of X if is has one
Prolog – Structures
Used for facts with nested relationships
Ex:
class(
cse240,
day(mon,wed),
time(130,245),
selgrad
online
)
Used for facts with nested relationships
Ex:
class(
cse240,
day(mon,wed),
time(130,245),
selgrad
online
)
Rulebase
room(Location, Day, Time) :-
class(
_,
Day,
Time,
_,
Location
)
List
Can contain mixed data
Uses []
Ex: [1,2,3,4]
Can contain lists inside of lists
Ex: [1,2,[3,4]]
[] is the empty list
= [
]
[Head|Tail] = [a,b,c,d]
Head = a
Tail = [b,c,d]
Arithmetic Comparisons
X
X>=Y – True if X greater than or equal to Y
X=:=Y – True if X equals Y
X=/=Y – True if X does not equal Y
Term Comparisons
X@
Relational Operators
Math
Uses is keyword
X is 1 + 2
X is 5 + 2
X is 5/2
X is 5//2
X is 5 mod 2
X is 2 ** 3
abs()
sqrt()
random(min,max,X)
Variables
-Scoped to the definition of the rule they are used in
– Ex: likes(Person, prolog) :-
likes(Person, programming),
likes (Person, logic).
Recursion
Create base case rule(s) that ends the call
Create recursive case rule(s) that call itself
Cut (!) ends the rule when its called
Green cut keeps the meaning
Red cut changes the meaning