Chapter 4
Definelang: A Language with Global Variables
Our goal in this chapter is to learn about global definitions and usage, and to contrast them with locally scoped definitions discussed in the previous chapter.
4.1 Local vs. Global Definitions
So far each variable that we have defined in a let expression has had a local lexical scope. So in the let expression (let ((a 3)(b 4)(c 2)) (+ a b c)), variables a, b, and c are defined only during the evalution of (+ a b c) and not outside it. Sometimes it is useful to define a variable and have it available for the entire duration of our interaction with the interpreter. For example, we can define the roman numerals using such a feature.
$ (define i 1)
We will call this feature a define declaration. A define declaration has three parts: the define keyword, name that is being defined (here i), and the initial value given to the name (here 1). We can similarly define other roman numerals.
$ (define ii 2) $ (define iii 3) $ (define iv 4) $ (define v 5)
69
DRAFT. NOT FOR DISTRIBUTION.
70
CHAPTER 4. DEFINELANG
We can then use these definitions in all of our programs as shown below.
$ (+ (⇤ iii iv v v) (⇤ ii iv v) ii )
342
$( (⇤vvvv)(+i ii iii iv)(⇤ iii vv)) 540
$ (+ (⇤ v ii iv) i (⇤ v v iv v)) 541
$ (+ (+ v v v i) (⇤ v v v v)) 641
Note that this is di↵erent from extending the initial environment of programs in Varlang with predefined values. Those definitions would have e↵ect on each run of the interpreter, whereas names defined by the define form during a particular run of the interpreter would not be automatically valid for the next run of the same interpreter.
4.2 Define, define
To support the define form, we extend the syntax of Varlang as shown in figure 4.1 to create a new language that we will call Definelang.
There are two major syntax changes. First, the syntax of the program changes in this language. A program in Definelang consists of zero or more definitions, represented as DefineDecl* followed by an optional expression, represented as Exp?. We have also added the syntax for define declarations. The syntax of DefineDecl takes an identifier (name being defined) and an expression (value of the name being defined). Here are some additional examples.
$ (define R 8.3145) // The gas constant R
$ (define n 2) // 2 moles of gas
$ (define V 0.0224) // Volume of gas 0.0224 mˆ2
$ (define T 273) // Temperature of gas 273 K
$ (define P (/ (⇤ n R T) V)) // Using Boyles law to compute pressure $ P //What is the pressure?
202665.93750000003
Notice that the expression in a define declaration can make use of pre- viously defined names, but it cannot utilize those that might appear later.
DRAFT. NOT FOR DISTRIBUTION.
4.2. DEFINE, DEFINE
71
Program Define Expressions NumExp AddExp SubExp MultExp DivExp
| Identifier VarExp
| (let ((Identifier Exp)+ ) Exp) LetExp
Number ::=
| DigitNotZero Digit+
Program ::= DefineDecl ::= Exp ::=
DefineDecl⇤ Exp?
(define Identifier Exp)
Digit ::= DigitNotZero ::= Identifier ::= Letter ::= LetterOrDigit ::=
Digit Number [0-9] Digits
Figure
4.1: Grammar for the Definelang Language
Number
| (+ Exp
| (- Exp
| (* Exp
| (/ Exp
Exp+ ) Exp+ ) Exp+ ) Exp+ )
[1-9]
Letter LetterOrDigit⇤ [a-zA-Z$ ] [a-zA-Z0-9$ ]
Non-zero Digits Identifier Letter LetterOrDigit
Each line in the previous example is a separate Definelang program according to the syntax in figure 4.1. Each of these programs defines a single variable, but it is possible to define multiple variables at once, e.g. both Faraday and Rydberg constant1.
$ (define F 96454.56) (define R 10973731.6)
The Definelang language also permits defining one or more constants
and then computing the value of an expression.
$ (define R 8.3145) (/ (⇤ 2 R 273) 0.0224) 202665.93750000003
We will now explore the semantics and implementation of this new lan- guage feature, and changes in the semantics of programs to add define declarations.
1For the curious reader, Faraday’s constant is the charge on a mole of electrons.
DRAFT. NOT FOR DISTRIBUTION.
72 CHAPTER 4. DEFINELANG Extending the AST, the visitor, and the formatter
Besides the grammar, we would also need to extend the AST, and the visitor infrastructure to accomodate these language changes. These changes include adding a new AST node DefineDecl, modifying the AST node for Program to also store define declarations, modifying the visitor interface to support new AST node, and finally modifying the formatter to print the new AST node. The reader is encouraged to review these changes in the companion code before proceeding further.
4.3 Semantics and Interpretation of Programs with Define Declarations
A correct Varlang program cannot have any free variables. A Definelang program can have free variables. For example, after starting the interpreter if a Definelang programmer types the following program the interpreter will evaluate the program to a dynamic error.
$ (/ (⇤ 2 R 273) 0.0224)
No binding found for name: R
On the other hand, if the interaction of the programmer was like the following the same program would produce the anticipated value.
$ (define R 8.3145) unit
$ (/ (⇤ 2 R 273) 0.0224) 202665.93750000003
To understand the di↵erence between these two behaviors, it would help to ask: when both of these programs start running, what was the value of the environment? In Varlang, when a program starts running, no variables have been defined yet. If you would recall from the realization of Varlang, we started evaluating every program in an empty environment. The semantics of Definelang is slightly di↵erent — when an interpreter starts running, no variables have been defined yet; when a program starts running all variables that have been declared since the interpreter started running are defined. To a reader familiar with interpreters or similar systems, this distinction will not come as a surprise, but it is important to make a note of it as we develop the realization of Definelang.
DRAFT. NOT FOR DISTRIBUTION.
4.3. SEMANTICS AND INTERPRETATION OF PROGRAMS WITH DEFINE DECLARATIONS 73
Recall from previous chapters that in our interpeter, a single Evaluator object persists through the lifetime of the interpreter. In Definelang, we want definitions to be retained across runs, which can be achieved by making the initial environment an attribute of the Evaluator object. Following implementation changes model that.
1 class Evaluator implements Visitor
2 Env initEnv = new EmptyEnv(); //New for definelang
4 Value valueOf(Program p) {
return (Value) p.accept(this, initEnv); public Value visit (Program p, Env env) {
for(DefineDecl d: p.decls()) d.accept(this, initEnv);
return (Value) p.e().accept(this, initEnv); }
…
}
8 9
10
11 12
13 14
5 6}
The set of legal values for Varlang was limited to NumVal, however, for Definelang this set needs to be extended as shown in figure 4.2 to model the semantics that define declarations do not produce any values.
Value ::= |
Values Numeric Values Unit Values NumVal NumVal
Figure 4.2: The Set of Legal Values for the Definelang Language
The figure defines a new kind of value UnitVal, for unit values. A UnitVal is like a void type in Java. It allows programming language def- initions and implementations to uniformly treat programs and expressions as evaluating to ‘a value’, which could be a UnitVal when producing other kinds of value is not sensible.
The semantics of define declarations is very similar to the let expressions, except that each definition changes the global initEnv to add a new binding from name to value.
NumVal ::=
UnitVal ::= (UnitVal)
NumVal
UnitVal
(NumVal n), where n 2 the set of doubles
DRAFT. NOT FOR DISTRIBUTION.
74 CHAPTER 4. DEFINELANG
public Value visit (DefineDecl d, Env env) { // New for definelang . String name = d.name();
Exp value exp = d.value exp();
Value value = (Value) value exp.accept(this, env);
initEnv = new ExtendEnv(initEnv, name, value); return new Value.UnitVal();
1
2
3
4
5
6 7}
The implementation evaluates the value expression on line 4, creates a new environment by extending the current value of initEnv on line 5. The value of a define declaration is a UnitVal.
Exercise
4.3.1. [Volume of Sphere] Define a constant pi with the usual value of 3.14159265359. Define a constant fourByThree with the value of 1.33333. Using the definition of pi and fourByThree, compute the volume of a sphere with radius 1.42. Recall that the volume of a sphere is 4/3 * pi * radius * radius * radius.
4.3.2. [Lazy Definitions] Extend the Definelang programming language from this chapter such that it supports a variation of the define decla- ration, say ldefine declaration (for lazy define). In a regular define declaration in an expression such as the following, first the value of the expression (/ (* n R T) V) is computed, then the global envi- ronment is extended with a mapping from name P to this value.
$ (define P (/ (⇤ n R T) V))
In a lazy define declaration, the value of the expression (/ (* n R T) V) will be computed when the name P is used. An example appears below.
$ (define P (/ (⇤ n R T) V))
$ (define R 8.3145) // The gas constant R
$ (define n 2) // 2 moles of gas
$ (define V 0.0224) // Volume of gas 0.0224 mˆ2 $ (define T 273) // Temperature of gas 273 K
$ P //What is the pressure? 202665.93750000003
DRAFT. NOT FOR DISTRIBUTION.
4.4. FURTHER READING 75
Notice that the interaction above would not have worked with the regular define declaration because the names n, R, T, and V would not be defined. In the lazy define declaration, since the value of the expression (/ (* n R T) V) is computed when P is looked up the interaction works.
4.3.3. [Macros] Extend the Definelang programming language from this chapter such that it supports declaring macros and macro expansion.
A macro definition has the following form.
$ (define (macro name argument1, argument2, …) Example:
$ (define (square x) (⇤ x x) )
$ (square 2) // This is expanded to (⇤ 2 2) 4
$(define(pressure nRTV) (/(⇤nRT)V)) $ ( pressure 2 8.3145 273 0.0224 ) 202665.93750000003
expression )
4.4
Template Metaprogramming
Further Reading
The macros described in the exercise were a simplified form of a more gen- eral idea known as template metaprogramming. Template metaprogram- ming, broadly, refers to a collection of technique that consume user facing syntax to generate more source code at compile-time. Template metapro- gramming is utilized by a number of programming languages most notably C++, but also in Haskell and Curl.
DRAFT. NOT FOR DISTRIBUTION.
DRAFT. NOT FOR DISTRIBUTION.
Chapter 5
Funclang: A Language with Functions
Our goal in this chapter is to learn about functions in full detail. We will especially focus on first-class functions, lambda abstraction, closures, higher-order functions, currying, and on functional data structures. We will also learn about the essence of pairs and lists and about techniques for flat recursion.
5.1 Function as Abstraction
We have already discussed variables, the most elementary abstraction mech- anism in computer programming languages, in previous chapters. A vari- able name is a proxy for a piece of computation. For example, the variables x and y below stand for the definitions on the right.
x = b ± pb2 4ac y = b0 ± pb02 4a0c0 2a 2a0
which allows us to write x ⇤ (y x) instead of the following more complex
form.
We can think of these variables as an opaque, fixed abstraction, once we define them we cannot customize their functionalities. For some ab- stractions it might be desirable to alter some portion of its functionality.
77
b±pb2 4ac ⇤( b0 ±pb02 4a0c0 b±pb2 4ac ) 2a 2a0 2a
DRAFT. NOT FOR DISTRIBUTION.
78 CHAPTER 5. FUNCLANG
For example, for variable definitions x and y above it may be sensible to change values of a, b, and c and get a di↵erent instantiation of the ab- straction. Functions, procedures, and methods in computer programming languages provide such an abstraction. This ability to instantiate an ab- straction by assigning concrete values in place of formal parameters is known as parametrization.
There are many variations of programming language features that can be used for parameterization of a computation. Each such feature is a variation of two elementary concepts: the ability to define a procedure, and the ability to call a procedure. In this chapter, we first focus on these concepts and then study some variations. We will gradually define a programming language with these features that we will call Funclang.
5.2 Function Definition and Calls
We will start by studying two features: lambda abstraction, and call. Think of a lambda abstraction as a tool for defining anonymous function. Let us start with simple examples of such feature. For example, the listing below defines an anonymous function that takes a single parameter x and the value of the function is x. It may be useful for you to try out these examples using the interpreter for this chapter.
(
x //Body of the function )
If you are familiar with the notion of procedure or methods in ALGOL family of languages like C, C++, Java, C#, etc…, you should notice three key di↵erences in syntax and one key di↵erence in semantics. Key di↵er- ences in syntax are:
1. We are not specifying the name of the function.
2. The formal parameter name is neither preceded nor followed by the type of the formal parameter.
lambda //Lambda special function for defining functions (x) //List of formal parameter names of the function
DRAFT. NOT FOR DISTRIBUTION.
5.2. FUNCTION DEFINITION AND CALLS 79
3. We don’t have to write an explicit “return” statement to specify the value returned by the function. In the function definition above, the value of the formal parameter x is the return value of the function.
In ALGOL family of languages as well as in lower-level languages like assembly language, procedures and methods are thought of as a subsection of the code section, procedure/method names are thought of as a proxy for the location of that subsection in the code section, and procedure/method call as a jump to that location after adjusting the environment. Unlike this mental model, it is perhaps best to think of a lambda abstraction as a generator of runtime values that represent functions. A lambda abstraction can be used to create many such function values, and each of these function values have a di↵erent identity. Each such function value can be used multiple times.
The following listing shows another anonymous function that takes a single parameter x and the value of the function is x + 1.
(
)
lambda
(x)
(+ x 1)
//Lambda special form for defining functions //List of formal parameter names of the function //Body of the function
The listing belows defines an anonymous function that takes two pa- rameters x, y and the value of the function is x + y.
(lambda (x y) (+ x y))
We can call an anonymous function also. Here, is an example of calling
the identity function.
( )
(lambda (x) x) 1
//Begin function call syntax //Operator: function being called //Operands: list of actual parameters //End function call syntax
The value of this program is 1. Notice the prefix notation for function calls. The operator here is the function (lambda (x) x). Here, is another example of calling the addition function.
( //Begin function call syntax (lambda (x) (+ x 1)) //Operator: function being called
DRAFT. NOT FOR DISTRIBUTION.
80
1
CHAPTER 5. FUNCLANG
//Operands: list of actual parameters //End function call syntax
)
The value of this program is 2. The operator here is the function (lambda (x) (+ x 1)). Here, is a third example of calling the function that adds two numbers. The value of this program is 2.
(
(lambda (x y) (+ x y)) 11
)
If we desire, we can also give these lambda abstractions lexically scoped name using the let expression. For example, we can give the name identity to the lambda abstraction that we defined previously.
( let
(( identity (lambda (x) x))) //Naming the function ( identity 1) //Function call
)
We can also give these functions globally scoped name using the define declaration.
$ (define identity (lambda (x) x))
$ ( identity 1) 1
As is usual, functions can be defined in terms of other helper functions.
$ (define square (lambda (x) (⇤ x x)))
$ (square 1.2)
1.44
$ (define cube (lambda (x) (⇤ (square x) x))) $ (cube 1.2)
1.728
Exercise
5.2.1. [Area] Using the define declaration, define a constant pi with the usual value of 3.14159265359. Use the definition of pi to define a function area of a circle that takes a radius and computes the area using the standard formula pi * radius * radius.
DRAFT. NOT FOR DISTRIBUTION.
5.3. FUNCTIONS FOR PAIRS AND LISTS 81
5.2.2. [sumsquares] Define a function sumsquares that takes two integers as a parameter and computes the sum of square of numbers from the first number to the second number.
5.2.3.
$ (sumsquares 0 0) 0
$ (sumsquares 1 2) 5
$ (sumsquares 3 5) 50
[sumseries] Define a function sumseries that takes a number n as ar- gument and computes the series below. Take the value of (sumseries 0) to be 0.
(1/2) (1/4) + (1/8) (1/16) + …
$(sumseries 0) 0
$(sumseries 1) 0.5 $(sumseries 2) 0.25 $(sumseries 3) 0.375
Functions for Pairs and Lists
5.3
Most programming languages provide some built-in functions, i.e. functions that programmers do not have to define from scratch and can assume to be available. In Funclang, we have several such built-in functions, mostly related to list manipulation. Funclang programmers have access to list, car, cdr, cons, and null? built-in functions. These functions car, cdr, cons, and null? operate on both pairs and lists in Funclang.
A pair in Funclang is a 2-tuple written as (fst.snd). A list in Funclang is a pair, where the second element is a list. There is a special list, empty
DRAFT. NOT FOR DISTRIBUTION.
82 CHAPTER 5. FUNCLANG
list, which is not a pair. Not all pairs are lists. Each list except for the empty list is a pair.
The function list is a constructor for list and it takes zero or more val- ues as arguments, and produces a list containing these values. The function car takes a single argument, a pair or a list, and produces the first element of that pair or list. The function cdr also takes a single argument, a pair or a list, and produces the second element of that pair or list. The function cons takes two values as arguments. If the second value is a list, it produces a new list with the first value appended to the front of the second value list. Otherwise, it produces a pair of two argument values. The function null? takes a single argument and evaluates to #t if that argument is an empty list. Exercises in this section will help you become more familiar with the semantics of these functions.
Using these basic functions, other functions over lists can also be defined. For example, the function cadr defined below returns the second element of the argument list.
(define cadr (lambda (lst)
(car (cdr lst)) )
)
Similarly the function caddr defined below produces the third element of the argument list.
(define caddr (lambda (lst)
(car (cdr (cdr lst ))) )
)
(define length (lambda (lst)
(if (null? lst) 0
(+ 1 (length (cdr lst )))
) )
)
The length function below computes the size of the list.
DRAFT. NOT FOR DISTRIBUTION.
5.3. FUNCTIONS FOR PAIRS AND LISTS 83
The length function is an excellent first example of a recursive function over list. A recursive function’s definition should mirror the definition of the input data types. For example, a list can be thought of as follows.
List := (list) | (cons val List), where val 2 Value
The definition says that a list is either an empty list, or a pair con- structed by joining an element and another list. Notice that the function length is structured just like the definition of list into two cases. First case handles empty lists. Second case handles non-empty list.
The append function below combines two lists.
(define append (lambda (lst1 lst2)
(if (null? lst1) lst2 (if (null? lst2) lst1
(cons (car lst1 ) (append (cdr lst1 ) lst2 )) )
) )
)
Notice that for append the definition of list suggests that the function’s structure should have four cases.
1. lst1 is empty, lst2 is empty.
2. lst1 is empty, lst2 is not empty.
3. lst1 is not empty, lst2 is empty.
4. lst1 is not empty, lst2 is not empty.
On closer observation, we realize that the value of the function append in the first and second case will be the same, so to optimize function definition we merge these two cases. Thus, we arrive at a suggested recursive function structure with three cases. In summary, when writing recursive functions that process data types such as lists, the structure of the data type provides useful hint for creating the structure of the function.
DRAFT. NOT FOR DISTRIBUTION.
84 CHAPTER 5. FUNCLANG Exercise
5.3.1.
Experiment with built-in functions for lists.
1. Use (list) to create an empty list,
2. Use (list 342) to create a list with a single element 342.
3. Use (car (list 342)) to get the first element of the previously defined list.
4. Use (cdr (list 342)) to get the rest of the elements of the previ- ously defined list.
5. Use (null? (list)) to check if the list created in part 1 is an empty list.
6. Use (cons 541 (list 342)) to append an element at the beginning of the list created in part 2.
7. Use (cadr (list 541 342)) to get second element of the list.
8. Use (caddr (list 641 541 342)) to get third element of the list.
9. Usefunctionlengthtofindlengthofthelistcreatedbyexpression (list).
10. Use function append to concatenate a list with a single element 3, with another list with a single element 4.
[Sum of Even Numbers] Write a function, sumeven, that takes a list of numbers and returns the summation of the even numbers in this list. For example
$ (sumeven (list 1 1 1 1 1)) 0
$ (sumeven (list 1 1 1 1 2)) 2
[Frequency] Write a function, frequency, which takes a list, lst, and an element, elem, and returns the frequency of that element in that list. For example:
$ (frequency ( list ) 5)
0
$ (frequency ( list #t ”hello”) 5)
5.3.2.
5.3.3.
DRAFT. NOT FOR DISTRIBUTION.
5.3.
5.3.4.
FUNCTIONS FOR PAIRS AND LISTS 85
0
$(frequency ( list #t 5 ”hello”) 5)
1
$(frequency ( list #t 5 ”hello” 5) 5) 2
[Reverse] Write a function, reverse, which takes a list, lst and re- turns the reverse of that list. For example:
$(reverse (list)) ()
$(reverse (list 3)) (3)
$(reverse (list 34)) (4 3)
$( reverse ( list 3 4 2)) (2 4 3)
[Sum of 2n] Write a recursive function called sumPower, that takes a list of numbers, and computes the sum of 2 to the power of each element in the list.
The following interactions log illustrates semantics of sumPower:
$ (sumPower (list)) 0
$ (sumPower (list 0)) 1
$ (sumPower (list 1)) 2
$ (sumPower (list 3)) 8
$ (sumPower (list 1 3)) 10
5.3.5.
5.3.6. [Get books] Write a function, getbooks that takes in a list of lists with author/book string pairs and returns a single list of only the books. Assume the author is the first element and the book is the second
DRAFT. NOT FOR DISTRIBUTION.
86
5.3.7.
CHAPTER 5. FUNCLANG
$ (get books (list ( list ”C. S. Lewis” ”The Last Battle”)
( list ”Charles Dickens” ”A Christmas Carol”)
( list ”Arthur C. Clarke” ”Rama”))) (”The Last Battle” ”A Christmas Carol” ”Rama”)
[Triangle] Write a function, triangle, which takes a number and pro- duces a list each element of which is a list of symbols.
When triangle is called with a non-negative integer, n, it returns a list containing n number of lists. The first inner list has n elements, the second inner list has n-1 element, and so on until you reach the top with only one element list, which forms the shape of a triangle. Each of the inner lists contain only the numbers 0 and 1 and they alternate across lists. The result always has the 0 as the first element of the first inner list, if any.
In the following examples, we have formatted the output to show the result more clearly, but your output will not look the same; it is su cient to just get the outputs that are equal to those shown. Spaces in the lists are just for displaying purposes and you are not required to print them.
$ ( triangle 0) ()
$ ( triangle 1) ((0) )
$ ( triangle 2) ((0 1)
(1) )
$ ( triangle 3) ((0 1 0)
(1 0) (0) )
$ ( triangle 4) ((0 1 0 1)
(1 0 1)
DRAFT. NOT FOR DISTRIBUTION.
5.3.
FUNCTIONS FOR PAIRS AND LISTS 87 (0 1)
(1) )
$ ( triangle 5) ((0 1 0 1 0)
(1 0 1 0) (0 1 0) (1 0)
(0) )
$ ( triangle 6)
((0 1 0 1 0 1)
(1 0 1 0 1) (0 1 0 1) (1 0 1) (0 1)
(1) )
[Board] Write a procedure, board, which takes a integer number as input and produces a list as an output, each element of which is a list of 0s and 1s.
When board is called with a non-negative integer, n, it returns a list containing n lists each of which have n elements. These lists form the shape of a square board. Each of the inner lists contain only numbers 0 and 1 and they alternate across lists. The result always has 0 as the first element of the first inner list, if any.
The following examples, shows a formatted output of the board, but your output does not need look the same regarding spaces. For your output it is su cient to just produce the list. Spaces in the lists are just for displaying purposes and you are not required to print them.
$ (board 0) ()
$ (board 1) ((0) )
$ (board 2)
5.3.8.
DRAFT. NOT FOR DISTRIBUTION.
88
CHAPTER 5.
FUNCLANG
5.4
Higher-order Functions
((0 1) (1 0))
$ (board 3) ((0 1 0)
(1 0 1) (0 1 0))
$ (board 4) ((0 1 0 1) (1 0 1 0) (0 1 0 1)
(1 0 1 0))
$ (board 5) ((0 1 0 1 0) (1 0 1 0 1) (0 1 0 1 0) (1 0 1 0 1)
(0 1 0 1 0))
$ (board 6) ((0 1 0 1 0 1) (1 0 1 0 1 0) (0 1 0 1 0 1) (1 0 1 0 1 0) (0 1 0 1 0 1)
(1 0 1 0 1 0))
A higher-order function is a function that accepts a function as argument or returns a function as value. In Funclang we can define higher-order functions. For example, here is a function that returns (lambda (x) c), which is also a function.
(lambda (c) //Lambda abstraction with a single argument
DRAFT. NOT FOR DISTRIBUTION.
5.4. HIGHER-ORDER FUNCTIONS 89 (lambda (x) c) //Result of running this lambda expression
)
If we call this function with argument 1 as follows:
(
(lambda (c)(lambda (x) c)) 1
)
//Function call //Operator //Operand
the result would be (lambda (x) 1). If we call this function with ar- gument 2 as follows:
(
(lambda (c) (lambda (x) c)) 2
)
//Function call //Operator //Operand
the result would be (lambda (x) 2). So we can think of (lambda (c) (lambda (x) c)) as a constant function generator.
(define
constgen
(lambda (c) (lambda (x) c))
)
We can also define functions that take other functions as parameter. For example, the listing below defines a function that takes a function f and applies it to 1.
(define
applytoone (lambda (f) (f 1))
)
(define add3
(lambda (x) (+ x 3))
)
$ (applytoone add3) 4
To try out this function, we can define another function.
We can then use add3 as an argument to applytoone.
DRAFT. NOT FOR DISTRIBUTION.
90 CHAPTER 5. FUNCLANG We can also create a function on the fly and give it as an argument to
applytoone.
$ (applytoone (lambda (x) x)) 1
$ (applytoone (constgen 342)) 342
The second call to function applytoone is specially noteworthy. It makes use of the previous higher-order function constgen to create a func- tion that when called returns 342, and calls applytoone with this function as argument.
Higher-order functions can be particularly useful for defining reusable algorithmic structures. For example, the listing below shows a higher-order function that accepts an operation and a list and applies the operation on each element of the list.
(define map (lambda (op lst)
(if (null? lst) (list)
(cons (op (car lst )) (map op (cdr lst)))
) )
)
$ (define num1to10 (list 1 2 3 4 5 6 7 8 9 10))
$ (define identity (lambda (x) x))
$ (map identity num1to10) (1 2 3 4 5 6 7 8 9 10)
$ (define square (lambda (x) (⇤ x x)))
$ (map square num1to10)
(1 4 9 16 25 36 49 64 81 100)
Exercise
5.4.1. Define a function filter with the signature. (define filter (lambda (test op lst) …) )
Here are some examples of using this function.
DRAFT. NOT FOR DISTRIBUTION.
5.4.
HIGHER-ORDER FUNCTIONS 91
The function takes two inputs, an operator test op that should be a single argument function that returns a boolean, and lst that should be a list of elements. The function outputs a list containing all the elements of ”lst” for which the test op function returned #t.
5.4.2.
Define a function foldl (fold left) with three parameters op, zero element and lst. The parameter op itself is a two argument function, zero element
is the zero element of the operator function, e.g. 0 for plus function
or 1 for multiply function, and lst is a list of elements. (plus func-
tion takes two parameters and adds them, multiply function takes two parameters and multiplies them.)
The function successively applies the op function to each element of the list and the result of previous op function ( where no such results exists the zero element is used). The following interaction log illustrates foldl function
$ (define plus (lambda (x y) (+ x y)))
$ (foldl plus 0 (list)) 0
$ ( foldl plus 0 ( list 1))
1
$ (foldl plus 0 (list 1 2)) 3
$ (foldl plus 0 (list 1 2 3))
6
$(foldl plus 0(list 1234)) 10
$ (define $ ( filter ()
$ ( filter () $(filter (6) $(filter (6 7) $(filter (6 7 9)
gt5? (lambda (x) (if (> x 5) #t #f))) gt5? ( list ))
gt5? ( list 1)) gt5?(list 16)) gt5?(list 1627)) gt5?(list 162759))
DRAFT. NOT FOR DISTRIBUTION.
92 5.4.3.
CHAPTER 5. FUNCLANG
Define a function foldr (fold right) with three parameters op, zero element and lst. The parameter op itself is a two argument function, zero element
is the zero element of the operator function, e.g. 0 for ‘+’ operator
or 1 for multiply operator, and lst is a list of elements. (plus func-
tion takes two parameters and adds them, multiply function takes two parameters and multiplies them.)
The function successively applies the op function to each element of the list and the result of previous op function ( where no such results exists the zero element is used). The following interaction log illustrates foldr function
$ (define minus (lambda (x y) ( x y))) $(foldr minus0(list))
0
$(foldr minus0(list 1))
1
$(foldr minus0(list 1234)) $ 2
$(foldr minus0(list 4321)) $2
[GCD] Greatest common divisor (GCD) of two numbers a and b is defined as follows. If a > b then (gcd a b) is gcd of a – b and b. Elseif a < bthen(gcd a b)isgcdof aandb - a. Otherwise,itis a.
1. Define a function gcd that computes greatest common divisor according the definition above.
The following interaction log illustrates the function:
$ (gcd 4 2) 2
$ (gcd 12 15) 3
2. Use the function gcd to define gcds that takes two list of num- bers and produces a third list that contains the list of gcd of corresponding elements from the first list and the second list.
5.4.4.
DRAFT. NOT FOR DISTRIBUTION.
5.5.
FUNCTIONAL DATA STRUCTURES 93 The following interaction log illustrates the function:
$(gcds ( list ) ( list )) ()
$ (gcds ( list 4) ( list 2)) (2)
$ (gcds (list 4 12) (list 2 15)) (2 3)
Functional Data Structures
5.5
Our ability to define abstractions that represent a piece of computation is essential to creating meaningful software systems, but we also need to be able to represent data structures. Fortunately, first-class functions of Funclang can serve both purposes equally well.
To illustrate, imagine that we want to create a data type that holds a pair of values. In order to define the data type, from the perspective of the client of the data type, it would be su cient to provide definition for all operations that can be applied to that data type: a constructor for creating pairs, an observer for getting the first element of the pair, and another observer for getting the second element of the pair. We can define a constructor operation that can be used to create values of that data type as follows.
(define pair (lambda (fst snd)
(lambda (op)
(if op fst snd)
) )
)
$ (pair 3 4)
(lambda ( op ) (if op fst snd))
We can then use this operator to create a new pair value.
DRAFT. NOT FOR DISTRIBUTION.
94 CHAPTER 5. FUNCLANG
Here, pair is a higher-order function. It returns a function value that takes a single parameter op and based on the value of op evaluates to fst or snd. We can also store this pair to use later.
$ (define apair (pair 3 4))
An important property to re-emphasize here is that apair is a function value. This function can be called by providing a value for the parameter op, which will then run its body (if op fst snd). The body of the function has two variables fst and snd. So in addition to the code, the function value apair also stores mappings from fst to 3 and snd to 4.
Now, we can define observer operations first and second.
$ (define first (lambda (p) (p #t)))
$ (define second (lambda (p) (p #f)))
$ ( first apair) 3
$ (second apair) 4
The function first and second assume that their argument p is a func- tion. We can implement runtime checks, but for simplicity let us avoid them at the moment. These functions then call p with argument #t and #f respectively. Recall from before that when a function value created by the constructor pair is called with argument #t and #f it returns the value of fst or snd.
Exercise
5.5.1. [Procedural representation of records] Define a function, record, which takes a list of strings, fields, and a list of values, values, and returns a procedural representation of record. Write a second procedure lookup, which takes a procedural representation of record and a string and and returns the ith element of the list values if i is the index of name in list fields. For example:
$ (define roman (record ( list ”i” ”v” ”x”) ( list 1 5 10)))
$ (lookup roman ”i”) 1
$ (lookup roman ”v”)
5
DRAFT. NOT FOR DISTRIBUTION.
5.6. CURRYING 95
5.5.2.
$ (define empty (record ( list ) ( list )))
$ (lookup empty ”a”)
” error ”
$ (define bad (record ( list ) ( list 1 2 3))) $ (lookup bad ”a”)
” error ”
$ (define bad2 (record ( list a b c) ( list ))) $ (lookup bad2 ”a”)
” error ”
[Procedural representation of tree] Define a procedural representation of binary tree. A binary tree is either a terminal node that contains a value or a non-terminal node containing two children that are both binary trees. Define two constructors leaf and interior for creating terminal and non-terminal tree. Define an observer traverse that traverses the tree in a depth-first manner, applies op to each value stored in the tree, and applies combine to combine values from root node, left subtree, and right subtree to produce a single value.
(define leaf (lambda (leafval) ... ))
(define interior (lambda (rootval lefttree righttree ) ... )) (define traverse (lambda (tree op combine) ... ))
5.6 Currying
All functions that we have written are defined using lambda abstractions that could take zero or more arguments. The ability to take zero or more arguments isn’t an essential property of a lambda abstracton. In fact in a programming language with support for first-class functions it is possible to model multiple argument lambda abstractions as a combination of single argument lambda abstraction. Take the function plus that we defined previously as follows.
(define plus (lambda (x y)
(+ x y) )
)
DRAFT. NOT FOR DISTRIBUTION.
96 CHAPTER 5. FUNCLANG We can easily redefine plus using single argument lambda abstractions
as follows.
(define plusCurry (lambda (x)
(lambda (y) (+ x y)
) )
)
This form where a function is defined using only single argument lambda abstraction is called its curried form. Since a curried form accepts only a single argument, calling it is slightly di↵erent. An example appears below.
$ ((plusCurry 3) 4) 7
Note that the expression (plusCurry 3) only partially evaluates the function. The value of this expression is a function, which when applied on 4 evaluates to the final value 7.
Exercise
5.6.1.
5.6.2.
[volume] Write a curried form of a function using lambda abstraction that takes length, width, and height of a cuboid, and computes the volume of cuboid by multiplying length, width and height.
Use that function, to compute volume of a cuboid with length equal to 3, width equal to 4 and height equal to 2.
[speed-mph] Define a curried version of the following procedure, call it speed-mph.
(define (speed kms kmToMile hours) (/ (⇤ kms kmToMile) hours) )
Test your code by executing the following.
$ //Speed of carA that traveled 150 km in 2 hours in mph
$ (speed 150 0.62 2)
46.5
$ //Speed of carB that traveled 250 miles in 3 hours in mph
DRAFT. NOT FOR DISTRIBUTION.
5.7. SYNTAX OF LAMBDA AND CALL EXPRESSIONS 97 $ (speed 250 0.62 3)
51.666666666666664
5.6.3. [speed-miles-per-two-hours] Using your solution from the previous problem, define a procedure,
speedMilesPerTwoHours
which takes a single number (kilometers) as an argument and com- putes the speed of a car in miles per two hours.
Test your code by executing the following.
$ (speedMilesPerTwoHours 50) $ (speedMilesPerTwoHours 120)
In the rest of this chapter, we will understand di↵erent aspects of the semantics of function definitions and calls by building an implementation of Funclang. As with Varlang, we will build an interpreter as opposed to a compiler. Fortunately, we have the Definelang implementation to work with. So the interpreter discussed in this chapter will build on that.
5.7 Syntax of Lambda and Call Expressions
We will first build support for lambda abstractions and calls, and di↵er dis- cussions about other features such as the list-related functions, if expression, conditional expressions, etc...
Like the grammar for Definelang, in the grammar for Funclang a pro- gram consists of zero or more definitions (define declarations) followed by an optional expression (exp)?. We also have two new expressions lambdaexp and callexp. We have used the syntax of these expressions often in previous sections of this chapter. We also need to extend the AST representation to support these two new nodes as shown in figure 5.2.
The AST node for a lambda expression has fields to store the formal parameter names and the body of the lambda expression, whereas the call expression has fields to store the operator expression and zero or more operand expressions.
We would also need to extend the visitor infrastructure to accomodate these language changes. That will include adding new methods to the
DRAFT. NOT FOR DISTRIBUTION.
98
Program
DefineDecl
Exp
CHAPTER 5.
Number
Digit
DigitNotZero
Identifier
Letter
LetterOrDigit
Cal lExp LambdaExp ::= Digit Number
FUNCLANG
Program Define Expressions NumExp AddExp SubExp MultExp DivExp | Identifier VarExp
::= DefineDecl⇤ Exp?
::= (define Identifier Exp) ::=
Number | (+ Exp | (- Exp | (* Exp | (/ Exp
Exp+ ) Exp+ ) Exp+ ) Exp+ )
| (let ((Identifier Exp)+ ) Exp) | ( Exp Exp+ )
| (lambda (Identifier+) Exp)
LetExp
| DigitNotZero Digit+
::= [0-9] Digits
::= [1-9]
::= Letter LetterOrDigit⇤ ::= [a-zA-Z$ ]
::= [a-zA-Z0-9$ ]
Non-zero Digits Identifier Letter LetterOrDigit
Figure 5.1: Grammar for the Funclang Language. Non-terminals that are not defined in this grammar are exactly the same as that in Definelang.
Visitor interface for CallExp and LambdaExp types. The standard visitors such as the Formatter would need to provide functionality to handle AST nodes of these new types. The reader is encouraged to review these changes in the companion code before proceeding further.
5.8 Value of a Lambda Expression
Functions are a first-class feature in Funclang, since values of type functions are treated just like numeric, string, boolean and list values. They can be passed as parameters, returned as values, and stored in environments1. This enables us to program higher-order functions, and procedural representation of data structure as discussed in previous sections.
1An expression (let ((identity (lambda (x) x))) ...) stores a 2-tuple: a name identity and a value of type FunVal in the environment
DRAFT. NOT FOR DISTRIBUTION.
1
2
5.8. VALUE OF A LAMBDA EXPRESSION 99
class LambdaExp extends Exp { List
3
4
5
6 7}
Exp body;
LambdaExp(List
formals = formals; body = body;
List
Object accept( Visitor visitor , Env env) {
return visitor . visit (this, env); }
}
class CallExp extends Exp { Exp operator ;
List
CallExp(Exp operator , List
operator = operator; operands = operands;
}
Exp operator() { return operator ; }
List
return visitor . visit (this, env); }
}
8
9 10 11 12 13
15
16
17
18
19
20
21
22
23
24
25
26
27
Figure 5.2: New AST nodes for the Funclang Language.
Since Funclang program and expressions can produce functions as val- ues, it becomes essential to extend the set of legal values to include a new kind of value: FunVal.
From our previous discussion about the lambda expression, recall that a lambda expression evaluates to a function value.
DRAFT. NOT FOR DISTRIBUTION.
1
e 2 Exp, env 2 Env
Figure 5.3: The Set of Legal Values for the Funclang Language
Value of LambdaExp
(FunVal vari,for i = 0…k expb env) = v value (LambdaExp vari,for i = 0…k expb) env = v
Here, FunVal is a new kind of value for Funclang. It encapsulates the names of the formal parameter, the body of the lambda expression, and the current environment. A realization of FunVal is shown in figure 5.4.
class FunVal implements Value { private Env env;
private List
100
Value ::=
|
CHAPTER 5. FUNCLANG
2
3
4
5
6
7
8 9}
NumVal
Values Numeric Values Function Values NumVal FunVal
FunVal NumVal ::= (NumVal n)
FunVal ::= (FunVal var0,.., varn e env) where var0,.., varn 2 Identifier,
10
11
12
13 }
public FunVal(Env env, List
formals = formals; body = body;
public Env env() { return env; }
public List
Figure 5.4: FunVal: A New Kind of Value for Functions
The implementation of the lambda expression case in the interpreter is shown below.
DRAFT. NOT FOR DISTRIBUTION.
5.9. VALUE OF A CALL EXPRESSION 101
Value visit (LambdaExp e, Env env) {
return new Value.FunVal(env, e.formals(), e.body());
}
This implementation exactly models the semantics. It creates a func- tion value that encapsules formal parameter names, function body, and the current environment.
5.9 Value of a Call Expression
Evaluating a call expression has three key steps.
1. Evaluate operator. Evaluate the expression whose value will be the function value. For example, for the call expression (identity i) the variable expression identity’s value will be the function value.
2. Evaluate operands. For each expression that is in place of a formal parameter, evaluate it to a value. For example, for the call expres- sion (identity i) the variable expression i’s value will be the only operand value.
3. Evaluate function body. This step has three parts.
a) Find the expression that is the body of the function value, b) create a suitable environment for that body to evaluate, and
c) evaluate the body.
For example, for the call expression (identity i) if the function value is (lambda (x) x), then the body of the function would be x. A suitable environment for running the body of this function would have a binding from formal parameter name x to actual parameter value, 1 for our example call expression. Evaluating that body would result in the value 1.
The value relation below models this intent.
DRAFT. NOT FOR DISTRIBUTION.
102
CHAPTER 5. FUNCLANG
Value of CallExp
value expb envk+1 = v
value exp env = (FunVal vari ,for i = 0…k expb env0 ) value expi env = vi, for i = 0…k
envi+1 = (ExtendEnv vari vi envi), for i = 0…k
value (CallExp exp expi,for i = 0…k) env = v
First condition above the line says that the value of a call expression is the value of body in a new environment envk+1. Second condition says that evaluating exp results in a function value, and that function value has expb as the function body. We also get the names of the formal parameters vari,for i = 0…k from the function value. Third condition says that evaluating each of the exp0 to expk in the original envirnoment results in values v0 to vk respectively. The fourth condition of this relation defines the extended environment envk+1 that maps formal parameter names to corresponding actual parameter values.
The case for CallExp in the interpreter implements this semantics as shown below. To improve user experience, it also implements some checks. For example, if the result of evaluating the operator is not a function value, e.g. in expression (1 2), the result is a dynamic error. Similarly, if the number of formal parameters do not match the number of actual arguments, the call expression results in a dynamic error also.
Dynamic Errors To support dynamic error as a legal value, we redefine the set of legal values in Funclang as shown in figure 5.5. A dynamic error encapsulates a string s e.g. for describing the cause of the error.
There are no expressions that the programmer can use to directly pro- duce dynamic errors with their own custom string. However, programmers can easily produce dynamic errors indirectly, e.g. by using a call expression incorrectly.
Implementation of Call Expression The implementation also mirrors the value relation and the informal semantics of call expressions.
Value visit (CallExp e, Env env) {
//Step 1: Evaluate operator
Object result = e.operator().accept(this, env);
DRAFT. NOT FOR DISTRIBUTION.
5.9. VALUE OF A CALL EXPRESSION
103
Values Numeric Values Function Values Dynamic Error NumVal FunVal
dynamic error value
if (!( result instanceof Value.FunVal))
return new Value.DynamicError(”Operator not a function”);
Value.FunVal operator = (Value.FunVal) result ; List
//Step 2: Evaluate operands
List
actuals .add((Value)exp.accept(this, env));
//Step 3: Evaluate function body
List
return new Value.DynamicError(”Argument mismatch in call ”); Env fenv = appendEnv(operator.env(), initEnv);
for (int i =0; i
An if expression is di↵erent from if statement in ALGOL-like languages. In Java for example, an if statement can have a condition, a then block of statements and optionally an else block of statements. An if expression in function consists of three expressions: the condition expression, the then expression, and the else expression. All parts are mandatory, and all three of them are expressions.
The comparison expressions are standard, except like other expressions in Funclang are written using the prefix form.
Exp ::= |
| | | | | | | | | | | |
Expressions NumExp AddExp SubExp MultExp DivExp Identifier VarExp
Number
(+ Exp
(- Exp
(* Exp
(/ Exp
Exp+ ) Exp+ ) Exp+ ) Exp+ )
(let ((Identifier Exp)+ ) Exp) ( Exp Exp+)
LetExp CallExp LambdaExp IfExp Exp) LessExp Exp) EqualExp Exp) GreaterExp BoolExp
(lambda (Identifier+ ) (if Exp Exp Exp)
(< Exp
(= Exp
(> Exp #t|#f
Exp)
Figure 5.6: Extended Grammar for the Funclang Language. Non-terminals that are not defined in this grammar are same as that in figure 5.1.
To add these new expressions to the language, we should first decide about the legal values produced by these expressions. Here, we have two options.
1. Encode using NumVal: We could choose to use the domain of NumVal as legal values produced by the comparison expressions and that con-
DRAFT. NOT FOR DISTRIBUTION.
110
Value
NumVal
BoolVal
FunVal
DynamicError
CHAPTER 5. FUNCLANG
::= Values
NumVal | BoolVal
| FunVal
| DynamicError ::= (NumVal n)
::= (BoolVal true)
| (BoolVal false) ::= (FunVal var0 ,..,
e
Numeric Values Boolean Values Function Values Dynamic Error NumVal BoolVal
FunVal DynamicError
varn
where var0,.., varn 2 Identifier,
e 2 Exp, env 2 Env ::= (DynamicError s),
where s 2 the set of Java strings
Figure 5.7: The set of Legal Values for the Funclang Language with new
boolean value
sumed by the if expressions. For example, a greater expression (> a b) could produce 0 as value when a is not greater than b, otherwise it can produce a nonzero value. Similarly, an if expression (if (> a b) ..) could assume that any value of its condition expression (> a b) greater than zero would be taken as true, and false otherwise.
2. Introduce new kind of values: We could also choose to introduce a new kind of value to model boolean conditions. A disadvantage of this option is that the language definition and implementation must support an additional feature. A distinct advantage is that the results of a boolean comparison may not be confused with results of arith- metic operations since they would be values of di↵erent kind. This has the potential to reduce errors, therefore most modern languages introduce boolean as a new kind of value.
In Funclang, following recent trends, we will also extend the set of legal values produced by Funclang programs to include boolean values. This extended set of values is shown in figure 5.7. A true literal is represented as #t and false literal as #f as shown in figure 5.6. A BoolVal can either be true or false.
env)
DRAFT. NOT FOR DISTRIBUTION.
5.10. SEMANTICS OF CONDITIONAL EXPRESSIONS 111 With new set of legal values, and syntax, we can give the semantics of
the three comparison expressions in Funclang as shown below.
Value of GreaterExp
value exp0 env = (NumVal n0 )
value exp1 env = (NumVal n1) n0 > n1 = b
value (GreaterExp exp0 exp1) env = (BoolVal b)
Value of EqualExp
value exp0 env = (NumVal n0 )
value exp1 env = (NumVal n1) n0 == n1 = b
value (EqualExp exp0 exp1) env = (BoolVal b)
Value of LessExp
value exp0 env = (NumVal n0 )
value exp1 env = (NumVal n1) n0 < n1 = b
value (LessExp exp0 exp1) env = (BoolVal b)
The semantics of if expression is a bit more involved, and is given by the two rules below. First rule handles the case when the boolean condition expcond evaluates to true, and second rule handles the false case.
Value of IfExp - True
value expcond env = (BoolVal true) value expthen env = v value (IfExp expcond expthen expelse) env = v
Value of IfExp - False
value expcond env = (BoolVal false) value expelse env = v value (IfExp expcond expthen expelse) env = v
The reader is encouraged to review the implementation of these expres- sions in the companion code before proceedings further.
Exercise
5.10.1. [Logical conjunction and disjunction expressions] Extend the syn- tax and semantics of the Funclang language to add support for the logical conjunction (and) and logical disjunction (or) expressions.
Examples:
DRAFT. NOT FOR DISTRIBUTION.
112
CHAPTER 5. FUNCLANG
$ (&&(<34)(>42)) #t
$ (|| (>34)(>42)) #t
5.10.2. [Switch expression] Extend the syntax and semantics of the Fun- clang language to add support for a switch expression.
Examples:
$ (define x 0)
$ (switch (x) (case 0 3) (case 1 4) (case 2 2)) 3
$ (define x 1)
$ (switch (x) (case 0 3) (case 1 4) (case 2 2)) 4
$ (switch ((+ x 1)) (case 0 3) (case 1 4) (case 2 2)) 2
$ (switch (x) (case 0 3) (case 1 4) (case 2 (+ 1 1))) 2
5.11 Semantics of Pairs and Lists
A Funclang programmers also has access to pair values, list values and related expressions. Recall that a pair in Funclang is a 2-tuple. A list is either an empty list or a pair, where the second element is a list.
Funclang supports several built-in expressions such as list for creating a new list, car for getting the first element of a pair, cdr for getting the second element of a pair, cons for constructing a pair, and null? for checking for empty list. Support for these expressions is orthogonal to function-related features (as we have discussed in section 5.5), but Funclang includes this support to make it easier to write interesting programs.
To support these expressions, we include two additional kinds of value PairVal and Null. This is an inductively-defined value. A ListVal is either an empty list, represented as the type EmptyList, or a pair that consists of a value as the first element and a ListVal as a second element, represented as the type ExtendList. New AST nodes ListExp, CarExp, CdrExp, ConsExp, and NullExp are also added to store these expressions.
DRAFT. NOT FOR DISTRIBUTION.
5.11. SEMANTICS OF PAIRS AND LISTS
113
Exp ::= |
| | | | | | | | | | | | | | | | |
Expressions NumExp AddExp SubExp MultExp DivExp Identifier VarExp
Number
(+ Exp
(- Exp
(* Exp
(/ Exp
Exp+ ) Exp+ ) Exp+ ) Exp+ )
(let ((Identifier Exp)+ ) Exp) ( Exp Exp+)
LetExp CallExp LambdaExp IfExp LessExp EqualExp GreaterExp BoolExp CarExp CdrExp Nul lExp ConsExp ListExp
(lambda (Identifier+ ) (if Exp Exp Exp)
(< Exp Exp)
(= Exp Exp)
(> Exp Exp)
#t | #f
(car Exp)
(cdr Exp) (null? Exp) (cons Exp Exp) (list Exp⇤ )
Exp)
Figure 5.8: Extended Grammar for the Funclang Language. Non-terminals that are not defined in this grammar are same as that in figure 5.1.
The semantics of list-related expressions is given in terms of the list values. The value of a ListExp is given by the following relation.
value (ListExp exp0 . . . expn) env = (ListVal val0 lval1)
where exp0 … expn 2 Exp env 2 Env
value exp0 env = val0, . . ., value expn env = valn lval1 = (ListVal val1 lval2), . . .,
lvaln = (ListVal valn (EmptyList))
A corollary of the relation is:
value (ListExp) env = (EmptyList)
DRAFT. NOT FOR DISTRIBUTION.
114
Value
NumVal
BoolVal
FunVal
PairVal
NullVal
DynamicError
CHAPTER 5.
FUNCLANG
Values Values Values Values Values
::=
NumVal
| BoolVal Boolean | FunVal Function | PairVal Pair
| NullVal
| DynamicError ::= (NumVal n)
::= (BoolVal true)
| (BoolVal false) ::= (FunVal var0 ,..,
Null Value Dynamic Error NumVal BoolVal
FunVal
PairVal Nul lVal
DynamicError
e
::= (DynamicError s),
where s 2 the set of Java strings
varn
where var0,.., varn 2 Identifier,
e 2 Exp, env 2 Env ::= (PairVal v0 v1)
where v0, v1 2 Value ::= (NullVal)
Figure 5.9: The set of Legal Values for the Funclang Language with new
pair and null values
The value of a CarExp is given by:
value (CarExp exp) env = val
where exp 2 Exp env 2 Env
value exp env = (ListVal val lval) where lval 2 ListVal
The value of a CdrExp is given by:
value (CdrExp exp) env = lval
where exp 2 Exp env 2 Env
value exp env = (ListVal val lval) where lval 2 ListVal
The value of a ConsExp is given by:
value (ConsExp exp exp’) env = (ListVal val lval)
env)
Numeric
DRAFT. NOT FOR DISTRIBUTION.
5.11. SEMANTICS OF PAIRS AND LISTS 115
where exp,exp’ 2 Exp env 2 Env value exp env = val value exp’ env = lval
The value of a NullExp is given by:
value (NullExp exp) env = #t if value exp env = (EmptyList)
value (NullExp exp) env = #f
if value exp env = (ListVal val lval’) where lval’ 2 ListVal
where exp 2 Exp env 2 Env
Exercise
5.11.1. [Pairs and Lists] In some programming languages such as Scheme, pairs are the basic values and lists are defined in terms of pairs. Define a pair as a 2-tuple, and redefine the value relations for list, car, cdr, cons, and null? in terms of pair values.
5.11.2. [equal? expression] Extend the FuncLang language to support a new expression equal? that takes two subexpressions and returns #t if their values are equal and #f otherwise.
The following interaction log illustrates the semantics of equal?
$(equal? #t #t) #t
$(equal? #t 1) #f
$(equal? #t ”Hello”) #f
$(equal? ( list ) ( list )) #t
$(equal? ( list ) ( list 1))
#f
$(equal? ( list ( list 1)) ( list ( list 0))) #f
$(equal? ( list ( list 1)) ( list ( list 1))) #t
$(equal? (+ 2 3) (+ 2 3))
DRAFT. NOT FOR DISTRIBUTION.
116
CHAPTER 5. FUNCLANG
#t
$(equal? (let ((x 2)) x) (let ((y 2)) y))
#t
$(equal? (let ((x 2)) y) (let ((y 2)) x)) funclang.Env$LookupException: No binding found for name: y
5.11.3. [List comprehension] Extend the Funclang programming language to support a new list comprehension expression. A list comprehension is a concise way of representing higher-order functions that operate over list. It should have the following syntax:
comp exp : ‘[’ exp ‘| ’ identifier ‘< ’ exp ’ , ’ exp ‘] ’
The following interaction log illustrates the list comprehension expres-
sion:
$ (define add2 (lambda (x) (+ x 2))) $ (define list1 ( list 3 4 2))
$ [ (add2x) | x < list1 , #t] (5 6 4)
$ [ (add2x) | x < (list) , #t] ()
$ [ (add2x) | x < list1 , (>x2)] (5 6)
DRAFT. NOT FOR DISTRIBUTION.