Transcript Introduction, Scheme basics (expressions, values)

Principles of
Programming Languages
Lecture 1
Slides by Yaron Gonen, based on slides by Daniel Deutch and
lecture notes by Prof. Mira Balaban
4
٤
IV
100
4+5
4 + “hello”
+
So What have We Seen?
•
•
•
•
Syntax
Semantics
Values
Types
Introduction
• We will study Computational Processes
• Design Principles
– Modularity, abstraction, contracts…
• Programming Languages Paradigms
– Functional Programming
• E.g. Racket, Scheme, Python, JavaScript (partially), Java (Since Java 8)
• Functions are first-class objects
– Logic Programming
• E.g. Prolog
• “Declarative Programming”
– Imperative Programming
• E.g. C, Java
• Focuses on change of state
– Not always a crisp distinction – for instance Scheme can be used for
imperative programming.
More topics
• Types
– Type Inference and Type Checking
– Static and Dynamic Typing
• Different Semantics (e.g. Operational)
• Interpreters vs. Compilers
– Lazy and applicative evaluation
Languages that will be studied
• Racket (dialect of Scheme)
– Dynamically Typed
– Functions are first-class citizens
– Simple (though LOTS of parenthesis  )
– Allows to show different programming styles
• Prolog
– Declarative, Logic programming language
• Languages are important, but we will focus on
the principles
Administrative Issues
• Websites prefix http://www.cs.bgu.ac.il/
– Course: /~ppl162
– My personal site (for presentations): /~yarongon
•
•
•
•
Exercises: 6
Mid-term
Exam
Grade
Use of Slides
• Slides are teaching-aids, i.e. by nature
incomplete
• Will be on my personal site
• Compulsory material:
– Lecture notes (see course website)
– Everything taught in class and practical sessions
– Compulsory reading if mentioned
“Wax on, wax off”
Functional Programming
• What is a non-functional (imperative)
programming?
– Imperative computation is a sequence of states
(remember automata?)
– Statements or side effects can modify the state
(e.g. changing value of variable, display output)
Functional Programming
•
•
•
•
•
Expressions (no statements)
No State (no mutable data)
No side-effects (see next slide)
Has variables, but denote values (no location)
We learn as we go
This is not a course in functional
programming!!
Side Effects
• “an expression is said to have a side effect if it
modifies some state or has an observable
interaction with calling functions or the
outside world” (Wikipedia)
• “affect some external state of the computation
environment” (lecture notes)
Why Functional Programming?
• Small paradigm (but powerful)
• Excellent for learning PPL
• Is making a comeback in recent years (Java 8,
Python, JS, NodeJS, MapReduce…)
• There’s FUN in Functional Programming…
The Power of Abstraction
Racket (Scheme)
• LISP = LISt Processing
– Invented in 1959 by John McCarthy
– Scheme is a dialect of LISP – invented by Gerry
Sussman and Guy Steele
– Racket is a dialect of Scheme
– Technical stuff in PS and in course website (how
to install etc.)
16
Why Scheme?
• 5 minutes to learn (but a semester to master)
• One of the most influential languages! (Google
“Programming languages influence network”)
Scheme Expressions
• The building block of every Scheme program
• Each has:
– Syntax
– Type
– Value (evaluation rules, semantics)
Scheme Expressions
• Atomic
– Cannot be
decomposed.
– Example: 34, #f, +
– Can be primitive or
non-primitive (next
slide)
• Composite
– Composed of other expressions
(atomic or composite)
– Starts with ‘(‘, ends with ‘)’
– Leftmost expression is an
operator.
– Can be special-form or not
– Example: (+ 4 3), (* (+ 4
5) 6)
Expressions
6
+
(+ 6 5)
(+ (+ 1 1) 8)
(foo 1 2)
(define x 5)
((lambda (x) x) +)
More on Atomic Expressions
• Primitive
– Evaluation process and value are built in
– Example: numbers, Booleans, primitive
procedures: +, -, *…
• Non-primitive
– All the rest…
Abstraction and Reference
‫ חַ יַת‬,‫ ּולְ כֹ ל‬,‫הַ בְ הֵׁ מָ ה ּולְ עוֹף הַ שָ מַ יִּם‬-‫ לְ כָל‬,‫ָאדם שֵׁ מוֹת‬
ָ ָ‫וַיִּ ְק ָרא ה‬
)20 '‫הַ שָ ֶדה (בראשית ב‬
• Binding
– Binding a name to a value (like naming a value)
– In Scheme: (define size 6)
– And now we can use this name: (* size 1.5)
– size is atomic but non-primitive
• Where do we keep those bindings?
– The global environment (next slide)
The Global Environment
• In short: GE
• A place to keep bindings
• Kind like a function from names (variables) to
values
• Name-value pair is called binding
Evaluating Expressions
Atomic
• Primitive:
– Numbers
– Booleans
– Procedures
• Variables (non primitive)
– Look in the GE
Composite
• Special forms:
– Each has its own rules. E.g.
define: evaluate only the
expression
• Non-special forms:
– Evaluate all sub-expressions
– Apply the operator
Computing in Scheme
> 23
Expression whose
value is a procedure
Closing parenthesis
23
> (+ 3 17 5)
25
Opening parenthesis
GE
Other expressions
> (+ 3 (* 5 6) 8 2)
43
> (define score 23)
25
Name
Value
score
23
Computing in Scheme
> score
Environment
23
Name
Value
> (define total 25)
score
23
> (* 100 (/ score total))
total
25
92
percentage
92
> (define percentage (* 100 (/ score total))
26
Using Evaluation Rules
> (define score 23)
> (* (+
5
6 ) (-
*
5
6
+
-
Special Form (second subexpression is not evaluated)
score
23
(*
2
3
2 )))
*
2
3
2
11
12
11
121
27
User Defined Procedures
(compound procedures)
How does one describe procedures?
formal parameters
(lambda (x) (* x x))
body
To process
something
multiply it by itself
• Special form – creates a “procedure object” (also
called closure) and returns it as a “value”
Internal representation
Proc (x) (* x x)
28
More on lambdas
• The use of the word “lambda” is taken from
lambda calculus.
• A lambda body can consist of a sequence of
expressions
• The value returned is the value of the last one
• So why have multiple expressions at all? (next
slide)
29
Lambdas with Multiple Expressions
• Side effects! Most useful for debugging
> ((lambda (x)
(display x)
(* x x))
3)
39
• display is a primitive procedure.
Syntactic Sugar for naming procedures
Instead of writing:
(define square (lambda (x) (* x x))
We can write:
(define (square x) (* x x))
31
Evaluation of An Expression
To Apply a compound procedure: (to a list of arguments)
Evaluate the body of the procedure with the formal parameters
replaced by the corresponding actual values
==> ((lambda(x)(* x x)) 5)
Proc(x)(* x x)
(* 5 5)
25
32
5
Using Abstractions
> (define square (lambda(x)(* x x)))
GE
> (square 3)
9
Name
Value
square
Proc (x)(* x x)
> (+ (square 3) (square 4))
(* 3 3)
+
25
33
9
16
(* 4 4)
Yet More Abstractions
> (define sum-of-two-squares
(lambda(x y)(+ (square x) (square y))))
> (sum-of-two-squares 3 4)
25
> (define f
(lambda(a)
(sum-of-two-squares (+ a 3) (* a 3))))
Try it out…compute (f 3) on your own
34
Booleans
Two distinguished values denoted by the constants
#t and #f
The type of these values is boolean
> (< 2 3)
#t
> (< 4 3)
#f
35
Values and Types
In scheme every expression has a value
Examples:
1) The value of 23 is 23
2) The value of + is a primitive procedure for addition
3) The value of (lambda (x) (* x x)) is the compound
procedure proc(x) (* x x) (also denoted <Closure (x) (* x
x)>
Values have types. For example:
1)
2)
3)
4)
The type of 23 is numeral
The type of + is a primitive procedure
The type of proc (x) (* x x) is a compound procedure
The type of (> x 1) is a boolean (or logical)
36
Atomic and Compound Types
• Atomic types
– Numbers, Booleans, Symbols (TBD)
• Composite types
– Types composed of other types
– So far: only procedures
– We will see others later
Type Predicates
• We’ll discuss types in depth later, but in the
meanwhile we have some predicates to help
us:
– number?
– boolean?
– procedure?
Void
Example : what is the value of the expression
(define x 8)
And of
(display x)
In scheme, the value of a define, display expression
is “void” of type Void.
Never write code that relies on such value!
39
Dynamic Typing
• Note that we never specify explicitly types of
variables
• However primitive functions expect values of a
certain type!
– E.g. “+” expects numeral values
• So will our procedures (To be discussed soon)
• The Scheme interpreter checks type correctness
at run-time: dynamic typing
– [As opposed to static typing verified by a compiler ]
The IF special form
(if <predicate> <consequent> <alternative>)
If the value of <predicate> is #t,
Evaluate <consequent> and return it
Otherwise
Evaluate <alternative> and return it
(if (< 2 3) 2 3) ==>
2
(if (< 2 3) 2 (/ 1 0)) ==>
ERROR
2
41
IF is a special form
•In a general form, we first evaluate all arguments and then
apply the function
•(if <predicate> <consequent> <alternative>) is
different:
<predicate> determines whether we evaluate
<consequent> or <alternative>.
We evaluate only one of them !
42
Condition
(lambda (a b)
(cond ( (> a b) a)
( (< a b) b)
(else -1 )))
cond is a Special Form
(cond
(<p1> <e11> ... <e1k1>)
(<p2> <e21> ... <e2k2>)
...
(else <en1> ... <enkn>))
Example: sqrt
• Newton’s method: if 𝑦 is a guess of the root of
𝑥, then
𝑥
𝑦+
𝑦
2
is a better guess.
• Example: 𝑥 = 2, 𝑦 = 1:
1. 𝑦1 = 1, y2 =
1+
2
2
1
= 1.5
2
2. 𝑦2 = 1.5, 𝑦3 =
1.5+1.5
2
= 1.4167
sqrt
(define sqrt
(lambda (x)
(sqrt-iter 1 x)))
(define average
(lambda (x y)
(/ (+ x y) 2.0)))
(define sqrt-iter
(lambda (guess x)
(if (good-enough? guess x)
guess
(sqrt-iter
(improve guess x)
x))))
(define good-enough?
(lambda (guess x)
(<
(abs (- (square guess) x))
0.001)))
(define improve
(lambda (guess x)
(average
guess
(/ x guess))))
(define square
(lambda (n)
(* n n)))
Expressions: Summary
Atomic
• Primitives
– Numbers
– Booleans
– Procedures
• Non-primitives
– Variables
– Special operators symbols
Composite
• Specials forms
– define, lambda, if, cond
• Forms
Evaluation: Summary
Atomic
• Number
• Boolean
• Built-in Primitive
• Variable
Composite
• Primitive operator
• Operator is a procedure
(value of lambda)
• Special form (define, if,
lambda, cond)
More on Types
• A procedure type is a composite type, as it is
composed of the types of its inputs (domain)
and output (range)
• In fact, the procedure type can be instantiated
with any type for domain and range, resulting
in a different type for the procedure (=data)
• Such types are called polymorphic
– Another polymorphic type: arrays of values of
type X (e.g. STL vectors in C++)
Type constructor
• Defines a composite type out of other types
• The type constructor for functions is denoted “->”
• Example: [Number * Number –> Number]
is the type of all procedures that get as input two
numbers, and return a number
• Note: there is nothing in the syntax for defining
types! This is a convention we manually enforce
(for now..).
Scheme Type Grammar
Type -> ’Void’ | Non-void
Non-Void -> Atomic | Composite | Type-variable
Atomic -> ’Number’ | ’Boolean’ | ’Symbol’
Composite -> Procedure | Tuple
Procedure -> ’[’ Tuple ’->’ Type ’]’ | ’[’ ’Empty’ ’->’
Type ’]’
Tuple -> (Non-void ’*’ )* Non-void
Type-variable -> A symbol starting with an upper
case letter
Value constructor
• Means of defining an instance of a particular
type.
• The value constructors for procedures is
lambda
– Each lambda expression generates a new
procedure