Transcript Algol and Haskell

The Algol Family and Haskell
Chapter 5
Dr. Muhammed Al-Mulhem
ICS535-091
1


The Algol family developed in parallel with
Lisp languages to the late development of
Haskell and Modula.
The main characteristics of the Algol family
are:




Colon-separated sequence of statements.
Block structure
Functions and procedures
Static typing.
Dr. Muhammed Al-Mulhem
ICS535-091
2
Language Sequence
Lisp
Algol 60
Algol 68
Pascal
ML
Modula
Haskell
Many other languages:
Algol 58, Algol W, Euclid, EL1, Mesa, Modula-2, Oberon, Modula-3
Dr. Muhammed Al-Mulhem
ICS535-091
3
Algol 60
 Designed between 1958 and 1963 by a
committee that include many computer
pioners such as:
 John McCarthy (designer of Lisp)
 John Backus (designer of Fortran)
 Intended to be a general purpose
language.
Dr. Muhammed Al-Mulhem
ICS535-091
4
Algol 60
 Important features of Algol 60
 Simple imperative language + functions
 Successful syntax, BNF -- used by many successors
 statement oriented
 begin … end blocks (like C { … } )
 if … then … else
 Recursive functions and stack storage allocation
 Fewer ad hoc restrictions than Fortran
 General array references: A[ x + B[3]*y]
 Procedures with procedure parameters.
 A primitive static type system, improved by later languages
(Algol 68, and Pascal)
 Very influential but not widely used in US
 Tony Hoare: “Here is a language so far ahead of its time that
it was not only an improvement on its predecessors but also on
nearly all of its successors.”
Dr. Muhammed Al-Mulhem
ICS535-091
5
Algol 60 Sample
real procedure average(A,n);
real array A; integer n;
no array bounds
begin
real sum; sum := 0;
for i = 1 step 1 until n do
sum := sum + A[i];
average := sum/n
end;
Dr. Muhammed Al-Mulhem
no ; here
set procedure return value by assignment
ICS535-091
6
Algol 60 Oddity
 Question:
 Is x := x equivalent to doing nothing?
 Interesting answer in Algol
integer procedure p;
begin
….
p := p
….
end;
 Assignment here is actually a recursive call
Dr. Muhammed Al-Mulhem
ICS535-091
7
Some trouble spots in Algol 60
 Holes in type discipline
 Parameter types can be arrays, but
 No array bounds
 Parameter types can be procedures, but
 No argument or return types for procedure parameters
 Problems with parameter passing mechanisms
 Pass-by-name “Copy rule” duplicates code,
interacting badly with side effects (How?).
 Pass-by-value expensive for arrays
 Some awkward control issues
 goto out of block requires memory management (Why?).
Dr. Muhammed Al-Mulhem
ICS535-091
8
Algol 60 Pass-by-name
 Substitute text of actual parameter
 Unpredictable with side effects!
 Example
procedure inc2(i, j);
integer i, j;
begin
i := i+1;
j := j+1
end;
inc2 (k, A[k]);
begin
k := k+1;
A[k] := A[k] +1
end;
Is this what you expected?
Dr. Muhammed Al-Mulhem
ICS535-091
9
Algol 68
 Considered difficult to understand
 new terminology
 Types were called “modes”
 Arrays were called “multiple values”
 One contribution of Algol68 is its type system
 Type construction can be combined without
restriction (array of pointers to procedures).
 Eliminated pass-by-name
 Not widely adopted
Dr. Muhammed Al-Mulhem
ICS535-091
10
Algol 68 Modes
 Primitive modes











int
real
char
bool
string
compl (complex)
bits
bytes
sema (semaphore)
format ( for I/O)
file
Dr. Muhammed Al-Mulhem

Compound modes





arrays
structures
procedures
sets
pointers
Rich, structured, and
type system is a major
contribution of Algol
68.
ICS535-091
11
Advances in Algol 68
 Storage management
 Stack for Local variables
 Heap storage for data intended to live beyond the current
function call.
 As in C, data on the heap is explicitly allocated.
 But unlike C, heap data are recalimed by garbage collection.
 This combination of explicit allocation and garbage collection
carried over to Pascal
 Parameter passing
 Pass-by-value
 Use pointer types to obtain pass-by-reference (like C)
Source: Tanenbaum, Computing Surveys
Dr. Muhammed Al-Mulhem
ICS535-091
12
Pascal
 Designed by Niklaus Wirth (Turing Award) in
the 1970s
 Revised the type system of Algol
 Good data-structuring concepts
 records, variants, subranges
 More restrictive than Algol 60/68
 Procedure parameters cannot have procedure
parameters
 Popular teaching language
 Simple one-pass compiler
Niklaus Wirth
Dr. Muhammed Al-Mulhem
ICS535-091
13
Limitations of Pascal
 Array bounds part of type
illegal
procedure p(a : array [1..10] of integer)
procedure p(n: integer, a : array [1..n] of integer)
 Example: A procedure of the form:
procedure p(a : array [1..10] of integer)
 May be called only with an array of length 10
as an actual parameter.
 Later versions of Pascal removed this
limitation.
Dr. Muhammed Al-Mulhem
ICS535-091
14
Designed by Dennis Ritchie, Turing Award winner,
for writing Unix
 Evolved from B, which was based on BCPL
 B was an untyped language; C adds some checking
 Relationship between arrays and pointers
 An array is treated as a pointer to first element
 E1[E2] is equivalent to ptr dereference: *((E1)+(E2))
 Pointer arithmetic is not common in other languages
 Ritchie quote
 “C is quirky, flawed, and a tremendous success.”
Dr. Muhammed Al-Mulhem
ICS535-091
15
 Statically typed, general-purpose programming language
 Type safe!
 Intended for interactive use
 Combination of Lisp and Algol-like features






Expression-oriented
Higher-order functions
Garbage collection
Abstract data types
Module system
Exceptions
 Designed by Turing-Award winner Robin Milner for LCF
theorem prover
 Used in textbook as example language
Dr. Muhammed Al-Mulhem
ICS535-091
16
 Haskell is a programming language that is
 Similar to ML: general-purpose, strongly typed, higherorder, functional, supports type inference, supports
interactive and compiled use
 Different from ML: lazy evaluation, purely functional,
rapidly evolving type system.
 Designed by committee in 80’s and 90’s to unify
research efforts in lazy languages.
 Haskell 1.0 in 1990, Haskell ‘98, Haskell’ ongoing.
 “A history of Haskell: Being lazy with class” HOPL 3
Phil Wadler
Paul Hudak
Simon
Peyton Jones
John Hughes
Dr. Muhammed Al-Mulhem
ICS535-091
17
 Good vehicle for studying language concepts
 Types and type checking
 General issues in static and dynamic typing
 Type inference
 Polymorphism and generic programming
 Control
 Lazy vs. eager evaluation
 Tail recursion and continuations
 Precise management of effects
Dr. Muhammed Al-Mulhem
ICS535-091
18
 Functional programming will make you think
differently about programming.
 Mainstream languages are all about state
 Functional programming is all about values
 Ideas will make you a better programmer in
whatever language you regularly use.
 Haskell is “cutting edge.” A lot of current
research is done in the context of Haskell.
Dr. Muhammed Al-Mulhem
ICS535-091
19