Input commands may appear in guards. A guarded command with an input guard is selected for execution only if and when the source named in the input com- mand is ready to execute the corresponding output com- mand.

for each node labeled by m, create one child for each marking of Post(m)

Ingredients

Manynewcomers to Haskell are puzzled by the concept ofmonads

monad

Strictness agsmaybeusedtoaddressmemoryleaks:structuresretainedbythegarbagecollector but no longer necessary for

Data structures in Haskell are generallylazy:the comp onents are not evaluated until

two other useful p olymorphic functions on lists that will b e used later.Functionheadreturns the rst element of a list, functiontailreturns all but the

Thelengthfunction is also anexample ofa p olymorphic

typ esysteminfersthecorrecttyp esforus

typ e errors are detected at compile-

Lambdas are basically anonymous functions

Putting a space between two things is simply function application.

exhaustive patterns

Pattern matching consists of specifying patterns to which some data should conform and then checking to see if it does and deconstructing the data according to those patterns.

ength function has a type declaration of length :: [a] -> Int

Haskell is a statically typed language, it has to know all the types before the code is compiled

ccess! Note that weeding out lists by predicates is also called filtering.

list comprehension

You can also use ranges to make infinite lists by just not specifying an upper limit.

reverse reverses a list.

A common task is putting two lists together. This is done by using the ++ operator.

if you see something like bar (bar 3), it doesn't mean that bar is called with bar and 3 as parameters. It means that we first call the function bar with 3 as the parameter to get some number and then we call bar again with that number

we just separate the function name from the parameter with a space

Haskell is statically typed. When you compile your program, the compiler knows which piece of code is a number, which is a string and so on.

and a function doubleMe which multiplies every element by 2 and then returns a new list. If we wanted to multiply our list by 8 in an imperative language and did doubleMe(doubleMe(doubleMe(xs))), it would probably pass through the list once and make a copy and then return it. Then it would pass through the list another two times and return the result. In a lazy language, calling doubleMe on a list without forcing it to show you the result ends up in the program sort of telling you "Yeah yeah, I'll do it later!". But once you want to see the result, the first doubleMe tells the se

So in purely functional languages, a function has no side-effects. The only thing a function can do is calculate something and return it as a result.

1.Call by name is the same as normal order reduction except that no redexin a lambda expression that lies within an abstraction (within a functionbody) is reduced. With call by name, an actual parameter is passed as anunevaluated expression that is evaluated in the body of the function be-ing executed each time the corresponding formal parameter is referenced.Normal order is ensured by choosing the leftmost redex, which will al-ways be an outermost one with an unevaluated operand.2.Call by value is the same as applicative order reduction except that noredex in a lambda expression that lies within an abstraction is reduced.This restriction corresponds to the principle that the body of a function isnot evaluated until the function is called (in a β-reduction). Applicativeorder means the argument to a function is evaluated before the functionis applied.

The α-reduction rule simply allows the changing of bound variables as longas there is no capture of a free variable occurrence.

LAMBDA REDUCTIONSimplifying or evaluating a lambda expression involves reducing the expres-sion until no more reduction rules apply. The main rule for simplifying alambda expression, called β-reduction

(λx . (mul y x))[y→x] to get (λx . (mul x x))is unsafe since the result represents a squaring operation whereas the origi-nal lambda expression does not.

The notation E[v→E1] refers to the lambda expression obtained by replacingeach free occurrence of the variable v in E by the lambda expression E1.Such a substitution is called valid or safe if no free variable in E1 becomesbound as a result of the substitution E[v→E1]

Evaluatinga lambda expression is called reduction.

higher-order functions—that is, functions thattake functions as arguments and/or return a function as their result.

(D → D) → D → D

of associating → to the right

curried version of the function with the property that argumentsare supplied one at a time

application has a higher precedence than abstraction

Function application associates to the left.E1 E2 E3 means ((E1 E2) E3)

thenumber of parentheses in lambda expressions can become quite large

n an abstraction, the variable named is referred to as the bound variableand the associated lambda expression is the body of the abstraction

140 CHAPTER 5 THE LAMBDA CALCULUS5.1 CONCEPTS AND EXAMPLESOur description of the lambda calculus begins with some motivation for thenotation. A function is a mapping from the elements of a domain set to theelements of a codomain set given by a rule—for example,cube : Integer → Integer where cube(n) = n3.Certain questions arise from such a function definition:• What is the value of the identifier “cube”?• How can we represent the object bound to “cube”?• Can this function be defined without giving it a name?Church’s lambda notation allows the definition of an anonymous function,that is, a function without a name:λn . n3 defines the function that maps each n in the domain to n3.We say that the expression represented by λn . n3 is the value bound to theidentifier “cube”. The number and order of the parameters to the functionare specified between the λ symbol and an expression. For instance, theexpression n2+m is ambiguous as the definition of a function rule:(3,4) |→ 32+4 = 13 or (3,4) |→ 42+3 = 19.Lambda notation resolves the ambiguity by specifying the order of the pa-rameters:λn . λm . n2+m orλm . λn . n2+m.Most functional programming languages allow anonymous functions as val-ues;

The number and order of the parameters to the functionare specified between the λ symbol and an expression

higher-order functions of the lambda cal-culus.

AlonzoChurch developed the lambda calculus in the 1930s

While static type checkers/inferencers oer a great help toprogrammers to catch (trivial) errors at early stages in theirprograms and to programming language implementers to generatemore ecient code (by assuming the untyped memory model), theyhave an inherent drawback: theydisallow correct programs whichdo not type check.

et-polymorphism.The idea is to type theletlanguage constructs dierently.

ce the identityfunction types to a polymorphic type,t(0) -> t(0)

Let Polymorphism

most general unier

The technique that we used to solve the type equations is calledunication.

If anycon ictis detected while solving thesystem then we say that the process of typingEfailed,

type inferenceand consists of two steps:1.Collect information under the form of type parametricconstraints by recursively analyzing the expression;2.Solve those constraints.

Polymorphic Functions

f x then y else z + xis seen then one knows that there is a typing error because the typeofxcannotbe bothintegerandbool

pe check programs without the need forthe user to provide any auxiliary type information

nfer the intended types from how the names are used.

What about some popular languages? Common Lisp: strong, dynamic, implicit Ada: strong, static, manifest Pascal: strong, almost static, manifest Java: strong, some static and some dynamic, manifest ML: strong, static, implicit JavaScript and Perl: weak, dynamic Ruby and Python: strong, dynamic

ML

Type Conversion Explicit operation that takes in an object of one type and returns an object of a different type that has the "same value" (not necessarily the same bit pattern). Type Coercion Implicit Non-converting Type Cast "Reinterpret" an object as an object of another type by preserving its bit pattern, regardless of value.

ML seems to use structural equivalence:

Type Equivalence When are two types the same?

A set of basic types A mechanism for defining new types Rules for type equivalence Rules for type compatibility Rules for type inference Rules for handling type clashes (a.k.a type checking)

A value's type constrains the way it may be used in a program.

Suppose that each variant of the recordSTypeis to be processed by its own subprogram. Acase-statement must be used todispatch

The assumption underlying variant records is that exactly one of the fields of the union is mean-ingful at any one time

the fielddatais allocated enough memory tocontain the larger of the array fieldaor the record fieldr

typedef int Arr[10];typedef structf oat f1;int i1;gRec

aunion typein C can be used to create a variant record which can itself be embedded into astructure that includes the common tag field

To solve these types of problems, programming languages introduce a new category of types calledvariant recordswhich havealternativelists of fields. Thus a variable may initially contain a valueof one variant and later be assigned a value of another variant with a completely different set offields. In addition to the alternative fields, there may be fields which are common to all recordsof this type;

Variant records are used when it is necessary to interpret a value in several different ways at run-time. Common examples are:

The first parameter,Item, is declared with the notation(<>)

he generic parameters arecompile-timeparameters and are used by the compiler to generate thecorrect code for the instance.

To get a (callable) procedure, you mustinstantiatethe generic declaration, that is, create an in-stance by furnishing generic actual parameters

genericsthat allows the programmer to define a templateof a subprogram and then to create instances of the template for several types

if we are working only with homogeneous data structures such as an array ofintegers, or a list of floating-point numbers, it is sufficient to use static polymorphism to createinstances of a program template at compile time

the same name can be used for two or more different subprograms providedthat theparameter signaturesare different.

Overloadingis the use of the same name to denote different objects in a single scope. T

Polymorphism can be either static or dynamic. In static polymorphism, the multiple forms are

Somehow the program must be able to identify thestatic chain, the link of activation records thatdefines the static context of the procedure according to the rules of scope, as opposed to the dy-namic chain of procedure calls at execution time. As an extreme example, consider a recursiveprocedure: there may be dozens of activation records in the dynamic chain (one for each recur-sive call), but the static chain will consist only of the current record and the record for the mainprocedure.

Somehow the program must be able to identify thestatic chain, the link of activation records thatdefines the static context of the procedure according to the rules of scope, as opposed to the dy-namic chain of procedure calls at execution time. As an extreme example, consider a recursiveprocedure: there may be dozens of activation records in the dynamic chain (one for each recur-sive call), but the static chain will consist only of the current record and the record for the mainprocedure

If deeper nesting is used, each activation record contains a pointer to the previous one. Thesepointers to activation records form thedynamic chain(Figure 7.9). To access ashallow variable(one that is less deeply nested), instructions have to be executed to “climb” the dynamic chain.This potential inefficiency is the reason that accessing intermediate variables in deeply nestedprocedures is discouraged. Accessing the immediately previous level requires just one indirectionand an occasional deep access should not cause any trouble, but a loop statement should notcontain statements that reach far back in the chain.

If the only recursive call in a procedureis the last statement in the procedure, it is possible to automatically translate the recursion intoiteration.

ail-recursion

However, the stack may hold other data besides that associated with a procedure call (such astemporary variables, see Section 4.7), so it is customary to maintain an additional index calledthebottom pointerwhich points to the start of the activation record (see Section 7.7). Even if thetop-of-stack index varies during the execution of the procedure, all the data in the activation recordcan be accessed at fixed offsets from the bottom pointer.

Upon completion of the procedure the above steps are reversed:1. The top-of-stack index is decremented by the amount of memory allocated for the localvariables.2. The return address is popped and the instruction pointer reset.3. The top-of-stack index is decremented by the amount of memory allocated for the actualparameters

Activation recordsThe stack is actually used to support the entire procedure call and not just the allocation of localvariables. The segment of the stack associated with each procedure is called theactivation recordfor the procedure. In outline,10, a procedure call is implemented as follows (see Figure 7.8):1. The actual parameters are pushed onto the stack. They can be accessed as offsets from thestart of the activation record.2. Thereturn addressis pushed onto the stack. The return address is the address of the state-ment following the procedure call.3. The top-of-stack index is incremented by the total amount of memory required to hold thelocal variables.4. A jump is made to the procedure code.

How is a stack used in the implementation of a programming language? A stack is used to storeinformation related to a procedure call, including the local variables and parameters that are auto-matically allocated upon entry to the procedure and released upon exit.

stack contains an additional piece of data—thetop-of-stackpointer. This is an index to the first available empty position in a stack

Astackis a data structure that stores and retrieves data in a Last-In, First-Out (LIFO) order.

The second requirement arises from consideration of the lifetime of the local variables. In theexample, the lifetime of the formal parameternis from the moment that the procedure is calleduntil it is completed. But before the procedure is completed, another call is made and that callrequires that memory be allocated for the new formal parameter. To computefactorial(4), a mem-ory location is allocated for4, then3and so on, five locations altogether. The memory cannot beallocated before execution, because the amount depends on the run-time parameter to the function.Section 7.6 shows how this allocation requirement is directly supported by the stack architecture.

During run-time, it must be possible to allocate an arbitrary number of memory cells for theparameters and local variables.

declaration has associated with it three properties:7ScopeThe scope of a variable is the segment of the program within which it is defined.VisibilityA variable is visible within some subsegment of its scope if it can be directly accessedby name.LifetimeThe lifetime of a variable is the interval during the program’s execution when memoryis assigned to the variable.Note that lifetime is a dynamic property of the run-time behavior of a program, while scope andvisibility relate solely to the static program text.

Block structure was first defined in the Algol language which includes both procedures and un-named blocks.

eferentially transparent

The real disadvantage of call-by-reference is that the mechanism is inherently unsafe. Supposethat for some reason the subprogram thinks that the actual parameter is an array whereas in factit is just a single integer. This can cause an arbitrary amount of memory to be smeared, sincethe subprogram is working on the actual parameter, and not just on a local copy.

The solution, which is known ascall-by-referenceorreference semantics,is to pass the address of the actual parameter and to access the parameter indirectly

copy-out semantics. The actual parameter mustbe a variable, and the subprogram is passed the address of the actual parameter which it saves

we will oftenwant to modify the actual parameter despite the fact that such modification is “unsafe”:

Since only a copy of the actual pa-rameter is passed, the subprogram cannot cause any damage to the actual parameter

The formal parameter is just a variable declared within the subprogram, so theobvious mechanism is to copy the value of the actual parameter into the memory location allocatedto the formal parameter. This mechanism is calledcopy-in semanticsorcall-by-value.

parameters are values, they can be constants or expressions

Aformal parameteris a declaration that appears in the declaration of the subprogram. Thecomputation in the body of the subprogram is written in terms of formal parameters.Anactual parameteris a value that the calling program sends to the subprogram.

Notethat C does implicit type conversions in many cases, while in Ada the result type must exactlymatch the context.

Semanticsis the meaning of an expression (program) in a (programming) language.While the syntax of languages is very well understood, semantics is much more difficult.

arious other symbols are used to make the rules more concise:[ ] OptionalfgZero or more repetitionsjO

In EBNF,we start with a highest level entityprogramand use rules to decompose entities until single char-acters are reached

Thesyntaxof a (programming) language is a set of rules that define what sequencesof symbols are considered to be valid expressions (programs) in the language

When the slow memory is disk and the fast memory is ordinary RAM (Random Ac-cess Memory), the concept is calledvirtual memoryorpaged memory

Memory access:Loadthe contents of a memory word into a register, andStorethe contentsof a register into a memory word.Arithmetic instructions such as add and subtract. These operations are performed on thecontents of two registers (or sometimes between the content of a register and the content ofa memory word). The result is left in a register. For example:add R1,Nadds the contents of the memory wordNto the contents of the registerR1and leaves theresult in the register.Compare and jump. The CPU can compare two values such as the contents of two registers;depending on the result (equal, greater than, etc.), the instruction pointer is changed to pointto another instruction. For example:jumpeq R1,L1. . .L1: . . .causes the computation to continue with the instruction labeledL1if the contents ofR1arezero; otherwise, the computation continues with the next instruction

The CPU contains a set ofregisterswhich are special memory locations in which computation isbe done. The CPU can execute any one of a set ofinstructionswhich are stored in memory; theCPU maintains aninstruction pointerwhich points to the location of the next instruction to beexecuted

computer architecture so that a minimal set of terms can be agreed upon. A computeris composed of acentral processing unit(CPU) andmemory(Figure 1.1). Input/output devicesCPUMemoryI/OBus--Figure 1.1: Computer architecturecan be considered to be a special case of memory.

We will discuss two non-imperative language formalisms: (1) functional programming (Chap-ter 16), which is based on the mathematical concept of pure functions, likesinandlogthat do notmodify their environments, unlike so-called functions in an ordinary language like C which canhave side-effects; (2) logic programming

Another approach to abstract programming is to describe a computation using equations, func-tions, logical implications, or some similar formalism.

Java7is both a programming language and a model for developingsoftware for networks. The model is discussed in Section 3.11. The language is similar to C++in syntax, but its semantics is quite different, because it is a “pure” OO language like Eiffel andrequires strong type checking.

There is a technical aspect of these pioneering object-oriented languages that prevented wideracceptance of OOP: allocation, operation dispatching and type checking are dynamic (run-time)as opposed to static (compile-time).

he first object-oriented programming language, Simula, was created in the 1960’s by K. Ny-gaard and O.-J. Dahl for system simulation: each subsystem taking part in the simulation wasprogrammed as an object.

The three elementary operations of Lisp are:car(L)andcdr(L)5which extract the head and tail ofa listL, respectively, andcons(E, L)which creates a new list from an elementEand an existinglistL

LispLisp’s basic data structure is the linked list.

e C and Pascal) leave to the operating system,

Ada extends the scope of programming languages by supporting error handling and concur-rent programming which are traditionally left to (non-standard) operating system functions

C++lan-guage, extending C to include support for object-oriented programming similar to that provided bythe Simula language.

t extremely easy to write programs with obscure bugs because unsafe constructsare not checked by the compiler as they would be in Pascal.

C was developed by Dennis Ritchie of Bell Laboratories in the early 1970’s as an implementa-tion language for the UNIX operating system.

Modula (now in version 3 which supports object-oriented pro-gramming) is a popular alternative to non-standard Pascal dialects

ut perhaps the most famousdescendent of Algol is Pascal, developed in the late 1960’s by Niklaus Wirth. The motivation forPascal was to create a language that could be used to demonstrate ideas about type declarationsand type checking. In later chapters, we will argue that these ideas are among the most significantconcepts ever proposed in language design

Simula, one of the first simulation languages

Algol has influenced language design more than any other.

e abstraction quickly won over most programmers: quicker andmore reliable development, and less machine dependence since register and machine instructionsare abstracted away. Because most early computing was on scie

Fortran was the first programming language that significantly rose above the level of assemblylanguage. It was developed in the 1950’s by an IBM team led by John Backus,

rolog, you lose the ability you had in C to specify arbitrary linkedstructures using pointers.

The higher the abstraction, the more detail is lost.

why there are hundreds of programming languages: two different classesof problems may demand different levels of abstraction, and different programmers have differentideas on how abstraction should be done.

An assembler takes a program written inassemblylanguage, which represents each instruction as a symbol, and translates the symbols into a binaryrepresentation suitable for execution on the computer

rogramsand languages can be defined as purely formal mathematical objects.

Aninterpreteris another way of implementing a programming language. Interpre-tation shares many aspects with compiling. Lexing, parsing and type-checking arein an interpreter done just as in a compiler.

The phases of a compiler

In order to reduce the complexity of designing and building computers, nearly allof these are made to execute relatively simple commands (but do so very quickly).A program for a computer must be built by combining these very simple commandsinto a program in what is calledmachine language. Since this is a tedious and error-prone process most programming is, instead, done using a high-levelprogramminglanguage. This language can be very different from the machine language that thecomputer can execute, so some means of bridging the gap is required. This is wherethecompilercomes in.

Type 2 grammars correspond tothe BNF grammars

These rules are called context-sensitive be-cause the replacement of a nonterminal by its definition dependson the surrounding symbols

Definition: A grammar < Σ,N,P,S> consists of four parts:

Java may wind up as the instructional language of tomorrow as it is truly object-oriented and implements advanced techniques such as true portability of code and garbage collection.

Unix gives C such advanced features as dynamic variables, multitasking, interrupt handling, forking, and strong, low-level, input-output.

ascal did not implement dynamic arrays, or groups of variables

Pascal also helped the development of dynamic variables, which could be created while a program was being run, through the NEW and DISPOSE commands.

Algol implemented some novel concepts, such as recursive calling of functions,

The Algol language was created by a committee for scientific use in 1958. It’s major contribution is being the root of the tree that has led to such languages as Pascal, C, C++, and Java.

LISP) language. It was designed for Artificial Intelligence (AI) research. Because it was designed for a specialized field, the original release of LISP had a unique syntax: essentially none.

A compiler is a program that turns the language’s statements into 0’s and 1’s for the computer to understand

“conditional control transfer” (