Table of Contents for Programming Languages: a survey

Expressions, functions, and evaluation strategy


Other names for things similar to functions are subroutines and procedures. Sometimes the word 'function' is used to denote something that returns a value and another word is used to denote something that is called only for its side-effects. In this chapter, we will just use the word 'function' throughout.

everything is an expression vs. statements and expressions


evaluation strategy and parameter passing (call-bys/pass-bys)

Parameter Passing Concepts in Programming Languaues

 distinguish six such mechanisms: call by text substitution, call by name, call by reference, call by value, call by result, and call by value-result

("Jones and Muchnick[81]" are said to have given 6; here's a Jones and Muchnick from 1978, but i havent read it: TEMPO: A Unified Treatment of Binding Time and Parameter Passing Concepts in Programming Languages)

todo read

todo i've heard of this, but which one is it? call-by-text?



Often there is a misconception that references passed by call-by-value is an instance of call-by-reference [1]. An example that clarifies the distinction is a swap function. Using call-by-value, it is not possible for a programmer to write a function 'swap(x,y)' such that calling 'swap' actually switches the values bound to x and y. Using call-by-reference with side-effects, however, this is possible.

For example, in pseudocode:

def swap(a,b):
  c = a;
  a = b;
  b = c;

a = 1;
b = 2;
# at this point, is a == 2?


" Blogger Alastair Reid said...

    I think Scala has an interesting approach to defining your own control constructs. It lets you declare a function parameter as call by name and it automatically inserts a lambda round the actual parameter and an application round uses of the formal parameter.
    Just one of Scala's tricks to make it easier to implement EDSLs.
    Tuesday, May 3, 2011 at 9:18:00 AM GMT+1"

todo: what is call-by-name? what is the difference b/t it and call-by-text?

todo: what is the difference between call-by-name and hygenic macros?

"Call-by-need is a memoized version of call-by-name (see wikipedia). In call-by-name, the argument is evaluated every time it is used, whereas in call-by-need, it is evaluated the first time it is used, and the value recorded so that subsequently it need not be re-evaluated." -- "[2]

"Most programming language pass arguments by value: the argument is evaluated, and then its value is passed to the function. An alternative approach, required by Algol60 but rarely used since, is to pass arguments by name : intuitively, the text of the argument, rather than its value, is passed to the function.

In lambda-calculus, there is sometimes a choice of several beta-reductions that we can use to simplify an expression. Consistently choosing the innermost redex corresponds to call by value; consistently choosing the outermost redex corresponds to call by name.

Consider the rather contrived function

function f ( x, y : integer ): integer; 
    if x =0 then f := − 1 else f := y 

and the invocation e = f(z, 1/z). If we use call by value when z = 0, the function is never called because evaluation of the arguments fails. If we use call by name, the expression effectively becomes:

if z =0 then e := − 1 else e := 1/z

which is well-defined when z = 0. (It was considerations such as these that led the Algol60 committee to require call by name as the default method of passing arguments.) " -- section 7.1.4


call-by-text / fexprs

'fexprs' use call-by-text

fexpr/call-by-text: callee controls how MANY times each argument is evaluated. the arguments AND EVEN THE RETURN VALUE are not necessarily evaluated. This can give very unexpected results if the either the argument is not pure (unexpected results due to textual duplication of the argument), or if the fexpr does something impure (unexpected results due to textual duplication of the return value). Fexprs are similar to C #define, which is also call-by-text (i think a difference is that #defines are not first class, whereas some languages may have first-class fexprs/"runtime" fexprs); this also explains the motivation for the difference between C #define and C inline (imagine someone who wants to #define double x to x + x for efficiency; this will have problems with "double x++" due to textual duplication of side effects, whereas inline will work) (also, i think call-by-text may implicitly group its arguemtns, whereas #define certainly does not: )

vs call-by-name:

"In fact, there are two flavors of lazy evaluation: call-by-name requires promises to be forced relative to their delaying environments, while call-by-text (very rare) uses the forcing environment." -- Programming and Meta-Programming in Scheme By Jon Pearce, section 8.3, page 311


call-by-need / lazy evaluation

like call-by-name, can implement things like short-circuit 'if' this way:

other reasons for laziness:

Which is not the same as

    let x = error "BOO!"
    in  if c then x else 0"  short-circuit if * alternatives: " For some language constructs the solution adopted by Smalltalk (and later Ruby), i.e., a very lightweight way on constructing closures is acceptable. So, for instance, I could accept writing
    ... myAnd x {y} ...

(In SML you could make something using functors, but it's just too ugly to contemplate.) "

Lazy constructors todo Cyclic data structures "Sometimes you really want cyclic data structures. An example are the Haskell data types in Data.Data that describe data types and constructors. A data type descriptor needs to contain a list of its constructors and a constructor descriptor needs to contain the data type descriptor. In Haskell this can be described very naturally by having the two descriptors reference each other. In SML this is not possible. You will have to break the cycle by somthing like a reference (or a function). In OCaml you can define cyclic data structures in a similar fashion to Haskell, so this isn't really a problem with strict languages, but rather a feature that you can have if you like. " " Reuse I've saved my biggest gripe of strict evaluation for last. Strict evaluation is fundamentally flawed for function reuse. What do I mean? I will illustrate with and example. Consider the any function is Haskell:

any :: (a -> Bool) -> [a] -> Bool any p = or . map p

It's quite natural to express the any function by reusing the map and or functions. Unfortunately, it doesn't behave like we would wish in a strict language. The any function should scan the list from the head forwards and as soon as an element that fulfills the predicate is found it should return true and stop scanning the list. In a strict language this would not happen, since the predicate will be applied to every element before the or examines the elements."

so, some languages offer optional lazy sequences; some languages offer lazy sequences by default; and some languages offer lazy control flow by default. One argument for lazy control flow by default is that otherwise 3rd party library functions will tend to be written in a strict fashion, which means that they can't be applied to infinite sequences (the catchphrase for this argument among lazy proponents is "laziness is the right default").



lazy vs. non-strict; lenient evaluation

good paper: Lenient evaluation is neither strict nor lazy by G Tremblay - ‎2000 - ‎Cited by 2 - ‎Related articles


A thread in which people say that "Call-by-need is definable in ML as an (admittedly cumbersome) idiom, and in fact ML programmers use laziness all the time. The reverse is not true: call-by-value semantics is not definable as an idiom in call-by-need" but "In practice it doesn't work as well as you would think. As most likely someone has at some point in the stack of functions you are calling forgotten to put lazy, and then everything is immediately forced":

see also

see also plPartConstructs Chapter Managing State, plChMacros section call-by-text/fexprs


todo: complete this sentence from Jones and Muchnick "The effect of call by name is identical to call by text substitution except that under call by name variables in the actual arguments are bound in the calling..."

first-class functions

also called "higher order functions", "hof", "reified functions"

example: python's 'map' function that takes a function and a list as arguments

example: python 2.5's 'sort' function that takes a comparator cmp function and a list (actually, it only needs a multiset) as arguments (bad example b/c python 3.0 has not cmp, instead a 'key' function: ; mb use On Lisp's example " (sort ’(1 4 2 5 6 7 3) #’<)" instead)

example: python's 'filter' function that takes a predicate and a list as arguments

see also On Lisp's section 2.2 and 2.3 for more examples

function objects

anonymous functions

syntax examples: function(x) {return x + 1} (javascript <ES6), x => x + 1 (javascript ES6) , \x -> x + 1 (Haskell), lambda x: x + 1 (Python)

partial function application

note: it's tricky to combine lightweight partial function application (where partial function application looks the same as normal function applicaton, just with some of the arguments left out) with default arguments to functions, because at any time when the mandatory arguments are bound, you will be wondering if the function should execute, using defaults for all optional arguments, or if it should wait for the optional arguments to be given.

in C++, partial application is provided by std::bind.

python generators

also clojure sequence protocols, IEnumerable

ruby's blocks

you can call 'continue' in a ruby block

lazy evaluation

prob: foldl, foldl', foldr, foldr', memory (dont hold onto your head?/space leak)

(see lazy section in plPartConstructs)


single dispatch; multiple dispatch