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
Introduction
• We will study Computational Processes
• Design Principles
– Modularity, abstraction, contracts…
• Programming Languages Paradigms
– Functional Programming
• E.g. Scheme, ML, JavaScript
• Functions are first-class objects
– Logic Programming
• E.g. Prolog
• “Declarative Programming”
– Imperative Programming
• E.g. C,Java, Pascal
• 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
• 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
Operators/functions ?
order
(5 + 6) * 7
types
Conditions, recursions…
Administrative Issues
•
•
•
•
•
Web-site: http://www.cs.bgu.ac.il/~ppl142
Exercises: 6
Mid-term
Exam
Grade
Use of Slides
• Slides are teaching-aids, i.e. by nature
incomplete
• Compulsory material include everything
taught in class, practical sessions as well as
compulsory reading if mentioned
Today
• Functional Programming in a nutshell
• Scheme basics
– Syntax and Semantics
– The interpreter
– Expressions, values, types..
Functional Programming
• Expressions (no statements)
• No State (no mutable data)
• No side-effects
This is not a course in functional
programming!! (for that you have
APL)
Scheme
• LISP = LISt Processing
– Invented in 1959 by John McCarthy
– Scheme is a dialect of LISP – invented by Gerry
Sussman and Guy Steele
– Small and powerful
10
Quick Guide to Scheme
Expressions
(5 + 6) * 7
*(+(5 6) 7)
(* (+ 5 6) 7)
The Scheme Interpreter
• The Read/Evaluate/Print Loop
– Read an expression
– Compute its value
– Print the result
– Repeat the above
• The
(Global) Environment
– Mapping of names to values
12
Name
score
Value
23
total
25
percentage 92
Language Elements
Primitives
Means of
Combination
(composites)
Means of
Abstraction
13
Syntax
23
+
*
#t, #f
(+ 3 17 5)
(define score 23)
Semantics
23
Primitive Proc (add)
Primitive Proc (mult)
Boolean
Application of proc to
arguments
Result = 25
Associates score with
23 in environment
table
Computing in Scheme
==> 23
Expression whose
value is a procedure
23
==> (+ 3 17 5)
Closing parenthesis
Environment Table
25
Other expressions
Name
Opening parenthesis
==> (+ 3 (* 5 6) 8 2)
43
==> (define score 23)
14
Value
score
23
Computing in Scheme
Atomic (can’t decompose) but not primitive
==> score
Environment
23
Name
Value
==> (define total 25)
score
23
==> (* 100 (/ score total))
total
25
percentage
92
92
==> (define percentage (* 100 (/ score total))
==>
A name-value pair in the env. is called binding
15
Evaluation of Expressions
The value of a numeral: number
The value of a built-in operator: machine instructions to execute
The value of any name: the associated value in the environment
To Evaluate a combination: (as opposed to special form)
a. Evaluate all of the sub-expressions in some order
b. Apply the procedure that is the value of the leftmost
sub-expression to the arguments (the values of the other
sub-expressions)
16
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
17
Abstraction – Compound Procedures
How does one describe procedures?
formal parameters
(lambda (x) (* x x))
To process
something
body
multiply it by itself
• Special form – creates a “procedure object” and
returns it as a “value”
Proc (x) (* x x)
Internal representation
18
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?
19
Syntactic Sugar for naming procedures
Instead of writing:
(define square (lambda (x) (* x x))
We can write:
(define (square x) (* x x))
20
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
21
5
Evaluation of An Expression
The value of a numeral: number
The value of a built-in operator: machine instructions to execute
The value of any name: the associated object in the environment
To Evaluate a combination: (other than special form)
a.
Evaluate all of the sub-expressions in any order
b.
Apply the procedure that is the value of the leftmost sub-expression to the
arguments (the values of the other sub-expressions)
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
22
Using Abstractions
==> (define square (lambda(x)(* x x)))
Environment Table
==> (square 3)
Name
square
9
Value
Proc (x)(* x x)
==> (+ (square 3) (square 4))
(* 3 3)
+
25
23
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
24
Lets not forget The Environment
==> (define x 8)
==> (+ x 1)
9
==> (define x 5)
==> (+ x 1)
6
25
The value of (+ x 1) depends
on the environment!
Using the substitution model
(define square (lambda (x) (* x x)))
(define average (lambda (x y) (/ (+ x y) 2)))
(average 5 (square 3))
(average 5 (* 3 3))
first evaluate operands,
then substitute
(average 5 9)
(/ (+ 5 9) 2)
if operator is a primitive procedure,
(/ 14 2)
replace by result of operation
7
26
Booleans
Two distinguished values denoted by the constants
#t and #f
The type of these values is boolean
==> (< 2 3)
#t
==> (< 4 3)
#f
27
Values and types
In scheme almost 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)
28
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
No Value?
• In scheme most expressions have values
• Not all! Those that don’t usually have side effects
Example : what is the value of the expression
(define x 8)
And of
(display x)
[display is a primitive func., prints the value of its
argument to the screen]
• In scheme, the value of a define, display expression is
“undefined” . This means “implementation-dependent”
30
• Never write code that relies on such value!
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 ]
More examples
==> (define x 8)
==> (define x (* x 2))
Environment Table
==> x
Name
Value
x
16
+
==> (define x y)
reference to undefined identifier: y
==> (define + -)
==> (+ 2 2)
0
Bad practice, disalowed by some interpreters
32
16 8
#<->
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
33
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 !
34
Conditionals
(lambda (a b)
(cond ( (> a b) a)
( (< a b) b)
(else -1 )))
Symbols
> (quote a)
a
> ’a
a
> (define a ’a)
>a
a
> (define b a)
>b
a
> (eq? a b)
#t
> (symbol? a)
#t
> (define c 1)
> (symbol? c)
#f
> (number? c)
#t
Symbols are atomic
types, their values
unbreakable:
‘abc is just a symbol
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 X Number –> Number] is the type of all
procedures that get as input two numbers, and return a number
• If all types are allowed we use a type variable:
– [T –> T] is the type of all procs. That return the same type as they get
as input
• Note: there is nothing in the syntax for defining types! This is a
convention we manually enforce (for now..).
Scheme Type Grammar
Type --> ’Unit’ | Non-Unit [Unit=Void]
Non-unit -> Atomic | Composite | Type-variable
Atomic --> ’Number’ | ’Boolean’ | ’Symbol’
Composite --> Procedure | Union
Procedure --> ’Unit ’->’ Type | ’[’ (Non-Unit ’*’)*
Non-Unit ’->’ Type ’]’
Union --> Type ’union’ Type
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