Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Referential Transparency is Overrated

But let’s keep this between us. . .

Didier Verna

didier@lrde.epita.fr

http://www.lrde.epita.fr/˜didier

http://www.facebook.com/didierverna

@didierverna

ACCU 2015 – Thursday, April 23rd

1/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Table of contents

1 Introduction

2 Scoping

3 Syntax Extension (RTMP)

4 Symbol Macros / Generalized Variables

5 Macros (CTMP)

6 Conclusion

2/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Natural Languages (Analytical Philosophy)

Origins

Quine

reference ≈ meaning

replacing an expression by another one which refers to

the same thing doesn’t alter the meaning

Example: “Wallace’s dog” ≡ “Gromit”

4 Tomorrow, I’ll go feed Wallace’s dog.

6 Gromit isn’t Wallace’s dog anymore.

4/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Programming Languages (Semantics)

Inspired from Quine

Strachey

If we wish to ﬁnd the value of an expression which

contains a sub-expression, the only thing we need

to know about the sub-expression is its value.

Reade

Only the meaning of immediate sub-expressions is

signiﬁcant in determining the meaning of a

compound expression. Since expressions are

equal if and only if they have the same meaning,

[it] means that substitutivity of equality holds.

Fundamental Concept of Programming Languages, 1967

Elements of Functional Programming, 1989

5/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Purely Functional Languages

A more extremist view

Take your pick

An expression which can be replaced with its value

without changing the behavior of a program.

Evaluation of the expression simply changes the

form of the expression but never its value.

All references to a value are equivalent to the value

itself.

There are no other effects in any procedure for

obtaining the value.

6/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

The original points

Quine and Strachey agreed

Quine’s point

Natural languages are complicated because they need to

be practical.

Strachey’s point

The same! And BTW, he was talking about imperative

languages.

A sound denotational semantics would render even

imperative languages referentially transparent (by telling you

when two expressions are equal).

7/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Purity vs. Referential Transparency

Are we talking about the same thing ?

What purely functional programmers talk about

values instead of meaning

evaluation process becomes relevant

side effects (or lack thereof)

8/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

The Typical PFP’s argument

Which is refutable

This is referentially transparent

i n t plus_one ( x ) { ret ur n x + 1 ; } / ∗ plus_one ( 1 ) i s always 2 ∗ /

This is not

i n t f oo = 10;

i n t p lus _f o o ( x ) { re tu rn x + f oo ; } /∗ p lu s_f oo ( 1 ) depends on f oo ∗ /

Really? What about this?

fo o : : I n t

fo o = 10

plu s_ foo : : I n t −> I n t

plu s_ foo x = x + foo −− p lus _f oo 1 i s always 1 1 . . .

l e t f oo = 20 in l e t p l us _fo o x = x + foo i n p lus _f oo 1 −− 2 1. Woops !

14/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

One ﬁnal deﬁnition

Gotta stop somewhere

Gelernter & Jagannathan

A language is referentially transparent if (a)

every subexpression can be replaced by any other

that’s equal to it in value and (b) all occurrences of

an expression within a given context yield the

same value.

Applies to languages, not expressions

Mostly rules mutation out

15/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Intermediate Conclusion

Where to go from here

There is always some form of context dependency

(lexical / dynamic deﬁnitions, free / bound variables,

side effects etc)

PFPs disregard their own contexts (lexical and purity)

PFPs reduce the notion of “meaning” to that of “value”

(result of a λ -calculus evaluation process)

Consequently, I hereby claim that the expression “referential

transparency” is not referentially transparent :-).

16/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Optimization, Safety, Expressiveness. . .

Why referential transparency is proﬁtable

Optimization:

Memoization

Parallelism (Cf. Erlang)

Safety:

Localized semantics (hence localized bugs)

Program reasoning and proof

Expressiveness:

Lazy evaluation

17/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Safety with Program Proof

Formal reasoning

Demonstrate (please) that ∀n, ssq(n) > 0

Purely functional

ssq : : I n t −> I n t

ssq 1 = 1

ssq n = n∗n + ssq ( n−1)

True for N = 1

Assuming it holds for

N − 1. . .

Imperative

i n t ssq ( i n t n )

{

i n t i = 1 , a = 0 ;

while ( i <= n )

{

a += i ∗ i ;

i += 1 ;

}

re tu rn a ;

}

Ahem. . .

18/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Views

Confusion

Beneﬁts

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Expressiveness with Lazy Evaluation

Thank you Church-Rosser

Explicit representation of inﬁnite data structures

Haskell

i n t l i s t : : I n t −> [ I n t ]

i n t l i s t s = s : i n t l i s t ( s + 1)

−− ( i n t l i s t 0 ) ! ! 3 −> 3 .

Lisp

( defun i n t l i s t ( s )

( cons s ( i n t l i s t (1+ s ) ) ) )

; ; ( e l t ( i n t l i s t 0) 3 ) −> ^C^C

20/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Where to Look for Bindings?

Scoping

Lexical Scoping: in the deﬁning context

Dynamic Scoping: in the calling context

Lexical Scope

( l e t ( ( x 1 0 ))

( defun f oo ( )

x ) )

( l e t ( ( x 2 0 ))

( foo ) ) ; ; −> 10

Dynamic Scope

( l e t ( ( x 1 0 ))

( defun f oo ( )

( de cla re ( s p e cial x ) )

x ) )

( l e t ( ( x 2 0 ))

( foo ) ) ; ; −> 20

First Lisp was dynamically scoped

Lexical scope since Scheme (except Emacs Lisp!)

Common Lisp still offers both (Emacs Lisp now does)

22/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Lexical Closures

Brought to you by lexical scope

Deﬁnition:

Combination of function deﬁnitions and their deﬁning

environment (free variables values at deﬁne-time)

Beneﬁts:

1st order functional (anonymous) arguments

1st order functional (anonymous) return values

. . . (e.g. encapsulation)

Lisp note: lexical state is mutable

23/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Why lexical closures are crucial

They’re everywhere!

1st order functional (anonymous) arguments

( defun l i s t + ( l s t n )

( mapcar ( lambda ( x ) (+ x n ) )

l s t ) )

1st order functional (anonymous) return values

( defun make−adder ( n )

( lambda ( x ) (+ x n ) ) )

Mutable lexical state

( l e t ( ( cnt 0 ) )

( defun newtag ( ) ( i ncf cnt ) )

( defun r e s ett a g ( ) ( setq c nt 0 ) ) )

24/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Why is dynamic scoping dangerous ?

But also useful

Problems:

Name clashes on free variables

Very difﬁcult to debug

Mc Carthy’s ﬁrst example of higher order function

(1958) was wrong!

Advantages:

Dynamic paradigms (e.g. COP)

Global variables!

As per defvar and defparameter

E.g. Emacs user options

29/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Mc Carthy’s bugged example

Transcribed in Common Lisp

The ﬁrst mapping function

( defmacro w hi l e ( t e s t &re st body )

‘ ( do ( ) ( ( not , t e s t ) )

,@body) )

( defun my−mapcar ( func l s t )

( l e t ( e l t n )

( wh i le ( setq e l t ( pop l s t ) )

( push ( fu n ca l l f un c e l t ) n ) )

( nreverse n ) ) )

( defun l i s t + ( l s t n )

( my−mapcar ( lambda ( x )

( de cla re ( s p e cial n ) )

(+ x n ) ) ; ; B ar f ! !

l s t ) )

30/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Deﬁnitions

Lexical Scope

Dynamic Scope

Interlude

Syntax

Extension

Symbol

Macros

Conclusion

Intermediate Conclusion

Remember when I asked you about (let ((x 10)) (foo)) ?

Duality of syntax (intentional):

Lexical scope

( l e t ( ( l ock n i l ) )

( defun l ock ( ) ( test−and−set l o ck ) )

( defun u nl oc k ( ) ( setq l o ck n i l ) ) )

Dynamic scope

( l e t ( ( case−fold−search n i l ) )

( sea rch−forward "^Bcc: " ) )

Going further

Semantics-agnostic macros (e.g. being-true)

32/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Reader Macros

Applications

Symbol

Macros

Conclusion

Reader Macros

Hijacking the Lisp syntax

Hooking into the Lisp reader

readtable: currently active syntax extension table

macro character: special syntactic meaning

reader macro: implements macro character behavior

Note: RTMP

Standard syntactic extensions

’ quote

#’ function

#c complex

. . .

34/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Reader Macros

Applications

Symbol

Macros

Conclusion

Why is RTMP useful?

Not only for syntactic sugar

Examples

; ; Of course , t he comment s yn ta x i s implemented w i th macro c har a ct e rs . . .

( asdf : defsystem : com . d v l s o f t . c lon

: d e s c ript i o n "The Command-Line Options Nuker."

: au tho r "Didier Verna <didier@lrde.epita.fr>"

: m ai n tai n er "Didier Verna <didier@lrde.epita.fr>"

: l i c e n se "BSD"

: v er s ion # . ( ver s ion : s hor t )

: depends−on (#+ s b cl : sb−posix

#+( and c l i s p com . d v l s o f t . c lon . t erm io ) : c f f i )

: s e r i a l t

# | . . . | # )

35/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Reader Macros

Applications

Symbol

Macros

Conclusion

Application to DSLs

The embedded homogeneous kind

From a previous talk:

; ; Going from t h i s :

{ o p t io n : f or eg ro un d w hi te

: fa ce { s yn ta x : bo ld t : f or eg ro un d cyan }

: fa ce { usage : f or eg ro un d y e ll o w }

}

; ; To t h a t :

( defi ne −f ace o p ti o n : foregroun d w hi te

: fa ce ( define− fa ce sy nt ax : bo ld t : f or eg ro un d cyan )

: fa ce ( define− fa ce usage : fo re gr ou nd y e ll o w ) )

What kind of underlying data structure would you like ?

{ : key1 v a l1 : key2 val 2 # | . . . | # }

What about this?

( defun random− f f i −bri dge ( foo bar ) { s t ru c t w ins ize window ; / ∗ . . . ∗ / } )

36/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Symbol Macros

Generalized

Variables

Application

Macros

Conclusion

Symbol Macros

A special kind of macros

Macro-expanded symbols

( define−symbol−macro foo expansion− form )

; ; L o c a l l y w ith SYMBOL−MACROLET

Expansion then subject to regular macro-expansion

Example

( defun compute−thing ( ) # | . . . | # )

( define−symbol−macro t h i ng ( compute−thing ) )

; ; Using THING i s c l ea ner th an using (COMPUTE−THING) .

38/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Symbol Macros

Generalized

Variables

Application

Macros

Conclusion

Generalized Variables

l-values vs. r-values

The problem

( setq l s t ’ ( 1 2 3 ) ) ; ; −> (1 2 3)

( nth 1 l s t ) ; ; −> 2

( defun s e tn t h ( nth l s t newval )

"Replace the NTH element in list LST with NEWVAL."

( rp lac a ( nthcdr l s t nth ) newval )

newval )

( se t n th 1 l s t 2 0) ; ; −> 20

l s t ; ; −> (1 20 3 )

Different setters for every data structure ?

How boring. . .

The solution

( se t f ( nth 1 l s t ) 2 0)

39/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Symbol Macros

Generalized

Variables

Application

Macros

Conclusion

Making your own

Setf expanders

50 or so expanders in the Lisp standard

Accessors (struct or class instances)

Make your own with

(defun (setf foo) ...)

defsetf

define-setf-expander

40/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Symbol Macros

Generalized

Variables

Application

Macros

Conclusion

Application

Combining symbol macros and generalized variables

with-slots / with-accessors

( with− acce sso rs ( ( o r i g i n c i r c l e − o r i g i n ) ( rad i us c i r c l e − r a d ius ) ) c i r c l e

; ; . . .

( se t f o r i g i n (+ o r i g i n t r a n s l a t i o n − fa c t o r ) )

( in c f r a diu s 3)

# | . . . | # )

41/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Crash Course

What are Lisp macros exactly?

Ordinary Lisp functions (almost)

Macro arguments: chunks of code (seen as data)

Non-strict: arguments not evaluated

Transform expressions into new expressions

43/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Why are macros useful?

CTMP, factoring, non-strict idioms etc

Will this work?

( defun i f n o t ( t e s t t hen e ls e )

( i f t e s t e lse t hen ) )

; ; ( i f n o t t ( e r r o r " Kaboum ! " ) ’ okay ) −> Kaboum!

This will

( defmacro i f n o t ( t e s t t hen e ls e )

( l i s t ( quote i f ) t e s t e lse then ) )

; ; ( i f n o t t ( e r r o r " Kaboum ! " ) ’ okay ) −> ( i f t ’ okay ( e r r o r " Kaboum ! " ) )

Even better, and even more better

( defmacro i f n o t ( t e s t t hen e ls e )

( l i s t ’ i f t e s t e l se th en ) )

( defmacro i f n o t ( t e s t t hen e ls e )

‘ ( i f , t e s t , el se , then ) )

44/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Macro pitfalls

Evaluation control, unwanted variable capture

Does this work?

( defmacro maybe−push ( o b j e ct p lace )

‘ ( when , o bje c t ( push , o b jec t , plac e ) ) )

And this?

( defmacro maybe−push ( o b j e ct p lace )

‘ ( l e t ( ( obj , ob j e c t ) )

(when o bj ( push obj , place ) ) ) )

At last!

( defmacro maybe−push ( o b j e ct p lace )

( l e t ( ( th e− ob je ct ( gensym ) ) )

‘ ( l e t ( ( , t he − o bject , obj e c t ) )

(when , the−obj ec t ( push , the− object , plac e ) ) ) ) )

45/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Intentional variable capture I

By example

This screams for abstraction

( defun sig ns ( l i s t )

( mapcar ( lambda ( x ) ( i f (= −1 ( signum x ) ) ’− ’ + ) )

( remove−if ( lambda ( x )

( or ( not ( numberp x ) ) ( complexp x ) ) )

l i s t ) ) )

This screams a little less

( defun f i lte r − ma p ( term f i l t e r l i s t )

( mapcar term ( remove− i f f i l t e r l i s t ) ) )

( defun sig ns ( l i s t )

( fil t er− m a p ( lambda ( x ) ( i f (= −1 ( signum x ) ) ’− ’ + ) )

( lambda ( x ) ( or ( not ( numberp x ) ) ( complexp x ) ) )

l i s t ) )

46/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Intentional variable capture II

By example

This doesn’t scream anymore

( defmacro f i lt e r − ma p ( term f i l t e r l i s t )

‘ ( mapcar ( lambda ( x ) , term ) ( remove−if ( lambda ( x ) , f i l t e r ) , l i s t ) ) )

( defun sig ns ( l i s t )

( fil t er− m a p ( i f (= −1 ( signum x ) ) ’− ’ + )

( or ( not ( numberp x ) ) ( complexp x ) )

l i s t ) )

Exercise: write a Haskell-like list comprehension

facility.

47/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Side Note: Alternatives with Syntax Extension

More than one way. . .

With capture

( defun bra ce−reader ( stream subchar a rg )

( de cla re ( ig n or e su bchar ) )

( l e t ( ( body ( r e a d− d e l i mit e d − lis t # \ } stream t ) ) )

( push ( cond ( ( or ( n ull ar g ) ( = 1 a rg ) ) ’ ( x ) )

( ( = 2 a rg ) ’ ( x y ) )

( ( = 3 a rg ) ’ ( x y z ) )

( ( = 4 a rg ) ’ ( x y z t ) ) )

body )

( push ’ lambda body )

body ) )

( set −dis patc h−ma cro− char acte r # \# # \ { # ’ brace− reader )

; ; ( # 2{ (∗ x y ) } 3 4 ) −> 12

Without capture (unicode Lisp)

( set− macro− characte r # \λ ( lambda ( stream char ) ’ lambda ) )

; ; ( ( λ ( x y ) (∗ x y ) ) 3 4 ) −> 12

48/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Anaphora

In the grammatical sense

Graham’s classical examples

( defmacro a i f ( t e s t t hen & o p t i o n a l e ls e )

‘ ( l e t ( ( i t , t e s t ) )

( i f i t , the n , el se ) ) )

; ; awhen , acond , a whi le , aand etc .

( defmacro alambda ( args &body body )

‘ ( lab el s ( ( s e l f , arg s ,@body ) )

# ’ s e l f ) )

And the all-mighty and highly controversial loop

macro!

49/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Pure (Free Variable) Injection

Lexical trojans

In its simplest form

( defmacro i n j e c t ( ) ’ x )

50/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Application: Lexical Communication Channels

Under the hood. . .

Principle:

Two or more macros communicating with each other by

injecting / capturing lexical bindings (variables, macros,

symbol macros etc)

This lexical communication channel does not even have

to be visible in the source code

51/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Crash Course

Variable Capture

Variable Injection

Lexical channels

Conclusion

Examples

Cf. live demo (if it works. . . )

Tracing anaphora

( t r a c i ng− co n d i t i o n a l s

; ; . . .

( i f t h i s do− t his do−that )

# | . . . | # )

Alternate version

( t r a c i ng− co n d i t i o n a l s . . .

; ; . . .

( i f t h i s ( progn d o− t his . . . here ) do− that )

# | . . . | # )

52/54

Referential

Transparency

is Overrated

Didier Verna

Introduction

Scoping

Syntax

Extension

Symbol

Macros

Conclusion

Bringing programming languages closer to natural ones

Referential transparency is useful

Breaking it is also useful (readability, concision)

Breaking it is dangerous (safety vs. expressiveness)

54/54