# Lambda Calculus and Music Calculi

Skip other details (including permanent urls, DOI, citation information)This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. Please contact mpub-help@umich.edu to use this work in a way not covered by the license. :

For more information, read Michigan Publishing's access and usage policy.

Page 243 ï~~Lambda Calculus and Music Calculi Yann Orlarey, Dominique Fober, Stephane Letz and Mark Bilton GRAME 6 quai Jean Moulin 69001 Lyon - France grame @applelink.apple.com Abstract This article presents an approach in the design of music programming languages based on Lambda Calculus. It shows, through several examples, that a purely descriptive language, that is to say a language without any programming capability, can be equipped with programming capabilities by the addition of a limited number of simple constructs. 1. Introduction In this paper we aim to show how a purely descriptive music language can be transformed into a music programming language by introducing the abstraction and application concepts from Lambda Calculus [Church 1941]. Instead of building suitable music data structures and functions on an actual programming language, we suggest to build suitable programming languages on music data structures. This method gives rise to specialized functional programming languages where the same structuring means (the same "glues" using Hughes [Hughes 19891 term) apply to both data and programs. The method is quite general and can be used for descriptive languages of other domains. In fact our first example will be a graphic calculus whose visual aspect enables better understanding of the method. In the second example we will develop a music calculus based a textual music language and we will end with a visual version of this music calculus. 2. The transformation process The transformation process is based on two steps: a) Extension of the descriptive language syntax by introducing the abstraction and application of Lambda Calculus Understanding the notion of abstraction is essential. Abstraction is an operation which makes some part of an object become variable. The resulting object is a generalization of the previous one. This generalization can be given different interpretations: a predicate, a class, a concept, a set, or a function. Here we are mainly concerned by the last interpretation. Application is in some ways the inverse of the abstraction operation. It allows us to specialize an abstraction by fixing some of its parts. b) Extension of the Lambda Calculus reduction rules in order to deal with the new specific descriptive languages constructions In Lambda Calculus, the fl-reduction rule gives a functional significance to abstractions. In the same manner, we add new reduction rules to give a functional significance to the other language constructs. In this way, every construction in the language can be applied as a function. For our examples we shall use the following structure: - descriptive language presentation - syntax - examples - programming language presentation - extended syntax - program examples which use Il-reduction - reduction rules extension - program examples which use the new reduction rules. Due to space restrictions we will not describe Lambda Calculus. The interested reader can refer to [Barendregt 1984]. Also we will not discuss the formal properties of the presented calculi. 3. A Graphic Calculus The aim of this section is to present a very simple 3 -D graphic calculus based on colored cubes. 3.1. The descriptive language Our descriptive language uses basic coloured cubes and operators to construct more complex cubes. The syntax appears as follows: cube Â~' color fcube,jcube2] E cube,] cubes] rcube,/ color o:= white I red I blue I green I invisible I... This states that a cube is either a basic coloured cube or a construction of cubes following the three directions of space. So the construction operators respect the rules: ICMC Proceedings 1994 243 Music Languages

Page 244 ï~~iU.U U Up U/EUo 3.2. The programming language To transform our descriptive language into a graphic calculus we must - Extend the language syntax with abstraction and application. - Extend the reduction rules to deal with the application of colored cubes and constructions. 3.2.1. Syntax extensions Note: A construction of two cubes always remains a cube, the operands are contracted following the construction axis. Some Examples Here are several examples of simple expressions followed by the corresponding graphic result: a) [greeni white] i[whitel green] b) whitej invisible ] white white] The extended syntax is described as follows: cube o a= color I [cubejcube,] E cube, cube2] [cub/] I Xcolor.cube 1 (cube, cube2) color o e white a red I blue I green I invisible I... This adds two new terms to the previous one, Xcolor.cube which represent an abstraction and (cube, cube2) which represent the application of cube, to cube2. In order to simplify the notation we will write (C, C2 C3 C4) instead of (((C, C2) C3) c,) by using left to right associativity for application. As stated earlier, an abstraction is an object generalization obtained by making some part of the object variables. So the abstraction Xwhite.[whitelblue] is a generalization of the cube [whitelblue] obtained by making the white part variable. The Xlwhite. part declares that white is a bounded variable in the abstraction body [whiteiblue]. If we apply?white.[whitelblue] to a cube C, after fl-reduction (that is to say the substitution of each occurrence of white by C in the abstraction body [whitelblue]), we obtain [Clblue]. Therefore, considering the (3-reduction rule, Xwhite.[whitelblue] defines the function "put a blue cube on the right of another cube". A fl-reduction example The following abstraction is the same as example (c) where-the colours white and green become variables. white j invisible white. green. invisible I white [ /invisible I green green Iinvisible] If we apply this abstraction to colour blue and then colour red, we have the following 13-reductions sequence: (we shall write arguments in bold in order to better show the substitution process) Iwhite Iinvisible Are,/invisible j white/,white. green. invisible green blue red L / re invisible ro "white jIinvisible 1 invisible j white I ) invisible I green LgreenIinvisible] Music Languages 244 ICMC Proceedings 1994

Page 245 ï~~blue I invisible 1 =A)Lgreen.I invisible blue re = Iren /invisible green red [ green J invisiblej [blue I invisible] invisible Iblue / -invisiblere [ red[ invisible Construction of a diagonally divided cube We can now try to construct more complicated objects, for example this diagonally divided green and white cube.,red.ren (red red) (red re ed) white Therefore we have: )~red. fgreenjI (red red)] V greenj (V V)]_VV ((red red) Iwhite V -vv)w (V V Consequently, our diagonally divided green and white cube X is defined by the following application: (Xredeenl(redjd) )red. greenj (red red) Note: In our implementation we use Normal Order Reduction. The evaluation stops automatically when an expression is known to be too small to be displayed. 3.2.2. Reduction rules extensions To understand this objects construction, lets look at the following objects A and B: aredwhite The previous example used only the application of abstraction so only the j3-reduction rule was required. But with our extended syntax, we can also apply basic coloured cubes and constructions to other expressions. Therefore we need to define corresponding reduction rules in order to give functional significance to these elements. Application of basic coloured cubes The function of the basic coloured cubes will be to colour their argument. So any object will be whitened by having a white cube applied to it. Consequently, a white cube applied on a red cube will result in a pink cube. (white red) = pink When a colour is applied to a construction, it "propagates" following the construction axis. (whiteEc,cc1) [(white C,)I(white C2)] When a colour is applied to an abstraction, it "propagates" into the abstraction body (renaming bounded variables in case of name conflicts ) (white Ac. C) = Ac.(white C) Application of constructions The principle here is to distribute application on the construction axis. For example: ([c,1c2] [c3,Jc4])=[(c, C,)j(C2 C4)] These new rules are described as follows (c,lci x)= (c, left(X))I (C2,ght(X)) )2 C2 bot(X) C2 /(C. back(X )) Where left, right, top, bot, front, back are cutting algorithms based on the following model (c is for a basic colour, C, C, and C2 are for any cubes): C2ft ) t(C) The object B is obtained by replacing the red parts in A by A itself. So we can see that if we could repeat this process indefinitely, the red parts would disappear completely and the result would be a diagonally divided green and white cube. In other words the problem is to find an object x solution for the following equation: X= [green IX] LXjwhiteJ We can simply resolve this by considering the object x as the application of an object Von itself. X-(V V) So by rewriting the previous equation in this way we have: (V V)=[green(vV) j L (VV)Iwhite J The definition of V is now simply: ICMC Proceedings 1994 245 Music Languages

Page 246 ï~~letC, ) =C, left(c)=* c left(Ac.C)= Xc.C Remark: The two last rules indicate that basic colours and abstractions are not affected by the cutting operation. The consequence is that: Li.(E x)* E These new reduction rules are very powerful. As the following picture shows, they allow to describe functions which have different behaviors in every points in space (note that the numbers and arithmetic are not part of our language, they are simply here to aid understanding). SEl1O 1 3 3.2.3. rules An example using extended [T] - [IFITJ Objects B and C are based on the same model but on complementary axes. b) Then we construct an object X which takes two arguments and applies them to the intersection of objects A, B and C. X =.white. 2invisible. ((AND A(AND B C))whiteinvisible) c) Finally we can define our sponge by "colouring" X with itself in two levels of depth: SPONGE=(((X X F) X F) white invisible) 4. A Music Calculus In this example we shall use a simplified textual music language inspired by Cadenza [Field-Richards 1993]. 4.1. The descriptive language Our descriptive language is composed of notes with pitch, velocity and duration, and two composition operators which allow us to organize notes into sequences and chords. We deliberately omit other kinds of musical information such as tempo and timbre to avoid obscuring the explanation. The syntax is as follows: score 1 event [score; score] [ce'1core event ds -- r il note i event tnodfier The intersection and union operations on objects are commonly used in graphics software. To reproduce these operations we must first construct Boolean functions and values. These enables us to "fill" the interior and exterior parts of objects with Boolean values and then using the Boolean functions AND and OR we can perform the intersection and union of objects. Here is a definition of Boolean values T, F1 and NOT, AND, OR. operators. T )blue.Agreen.blue F - Ablue.Agreen.green NOT = reLeblue. Agreen.(red green blue) AND -=Ablue.Agreen.(blue green blue) OR -)Ablue.Agreen.(blue blue green) Now we can use these to construct a variant of Spenger sponge: a) We begin by constructing objects A, B and C: (here displayed applied to white and invisible) The definition of object A is: note pitch I pitch octave I note nmodifier pitch cidi elflgla lb octave 0111213141516171819 tmodifier a.=.1 * 1 t l/l nmodifier +1-1>1<1 I Boolean values T and F must be understood as selectors: T returns its first argument, F return its second argument. Music Languages 246 ICMC Proceedings 1994

Page 247 ï~~This states that a score can be either an empty score, a musical event, a sequence of two scores [s,;s] following the time axis, or a chord of two scores [l] superposed on time axis. A musical event can be either a rest (r) or a note. The event duration is by default a quarter-note. This duration can be divided by 2 (/), divided by 3 (t), multiplied by 1.5 (.) or multiplied by 2 (*). A note is defined by a pitch value which may be followed by an octave number (octave 3 by default). The note pitch can be modified by adding (+) or subtracting (-) one semitone. In the same way, the default velocity can be accentuated (>) or diminished (<). Here are some examples of events descriptions: c, c3 middle C quarter-note d4> accentuated D4 quarter-note fill F3 32nd-note a++ A3 double sharp quarter-note r quarter-note rest r** whole-note rest In order to simplify the notation, we use associativity rules for the sequence and chord operators. - Like this we can write [S,;S2; s3; S4] instead of [s,;[S2;[S,; S,]]] by using right to left associativity for the sequence operator. 2c part declares that c is an abstract note in the abstraction body [c;c] (In other terms c is a bounded variable, this will be written in italics to distinguish it from a real note). If we now apply this abstraction to note a4, written (Ac.[c;c] a4), after f3-reduction (that is substitution of each c occurrence with a4) we obtain the sequence [a4;a41. So the abstraction Ac.[c;c] really defines an operation that repeats the same object two times. 4.2.1. Syntax extension In the same way we can write[lj instead of writ by using bottom to top associativity for the chord operator. Here is a simple example: A Fc4;b//f 4;ii] 1 4.2. The programming language To transform the descriptive language into a music calculus, we first introduce abstraction and application, and then extend the reduction rules. Here follows an example to explain the role of abstraction and application. Using our descriptive language we can explicitly describe repetition of notes, like: [c;cJ, [f3//;f3//] or [b2+;b2+1, but we can't describe the underlying concept of repetition: the sequence of two identical objects. Abstraction will allows us to describe such concepts. We can generalize a particular repetition, for example [c;c], by making the note c become variable. In this case the abstraction is written Ac.[c;c], where the The syntax of our musical calculus is described as follows: score - event I [score,; score2] [score] [score2J I Xevent.score I (score, score2) It extends the descriptive language syntax with two new forms: Xevent.score which is for abstraction, and (score, score2) for application. Again in order to simplify the notation, we assume associativity rules to write the applications: like this we can write (S, SS S3 S,) instead of (((S, S2) S,) S4) by using left to right associativity for the application. P1-reduction examples Here are some examples of applications and their sequence of corresponding R1-reductions. (we shall write arguments in bold in order to better show the substitution process). a) 3 time repetition: ( c4fl [ c4][c4 ]c4] Ac.[c c, c -e4 e4.e4 { ' g4 gjj 4flg4 g4 b) ABBA form: (uta.Ab.[a; b; b; a] b5 tc4;e4]) =% [b5;[c4;e4];[c4;e4]; b5] c) canon form: rc [c4; e4;g4;c31 ( c[j],[4;;cJ 4;e4;g4;c3 Infinite sequences As with Lambda Calculus we can't directly define recursive functions, however they can be easily simulated. To understand this principle let's look at the following abstraction: v-f.(f f) When we apply V on V, after (3-reduction: (v v) = (f.(ff) v)=,(v v) This is V applied on V again, consequently the evaluation on such a form never terminates (i.e. it doesn't have a normal form). We shall use this principle to define infinite sequences. ICMC Proceedings 1994 247 Music Languages

Page 248 ï~~a) An infinite sequence Let's start with an infinite sequence of c4 notes: X = [c4;c4;c4;....J] A recursive definition of x would be: X = [c4;X]. To obtain this result we shall modify the definition of V- Af.(f f) in: V'= Af.[c4;(f f)] By applying V' on V' we have: (V" V')=(Af.[c4;(f f)J v') =, [c4;(V' V')] =%. [c4;c4;c4;...] So, the required definition is: X = (f.[c4;(f f)] df.[c4;(f f)]) b) A looping function We can now generalize the preceding object x by making the note c4 become variable: Loopsf?c4.(f.[c4;(f f)] f.[c4;(f f)]) So if we apply Loop to the [a2;a2//l sequence we obtain: (Loop [a2;a2 //]) = [[a2;a2 I/I]a2;a2 I IJ;(a2;a2 /I ];... c) Infinite alternation By slightly modifying the preceding definition, we can define an infinite alternation of two objects: Alt-Ac. d.(f.[c;d;(f f)] f.[c;d;(f f)]) If we apply Alt on c3 and c3+ we obtain (Alt c3 c3+)=,. [c3;c3+;c3;c3+;c3;... ] Notice that this result is not equivalent to: (Loop [c3;c3 +]) te. [[c3;c3 +];[c3;c3+];[c3;c3 +];... (although the sound result would be the same) We must also give functional significance to basic objets likes notes and rests. The principle we choose is to consider a note as a function which transforms its argument according to the differences between the note and a reference note (the c3 quarter-note in our case). So if we represent a note as a tuple <pitch, velocity, duration> then the application of a note to another one ((h'i,'d,) (h,i,d2)) gives a new note: = (h+h -h~,, i2+i, -i, d2 *d,/d,,) To summarize, the new reductions rules are as follows (we give only the principal rules, E, F, G, H are for any terms, N is for a note): a) Sequence application: ([E;F] [G;H]) =[(E G);(F H)] G ([E;F] G) L[FJHJ) I[QE;FJ H)] ([E;F] N) =(E N) b) Chord application: E[n]G (E G)1 c) Note application: (N [G;H])=[(N G);(N H)] (V1 E=(N G)] LHJ) (NIH)] (N, N2) (h +h, - hI, i2 +i1 -it d2 *d,/d,f,) d) Application of 0: (0 E) = Simples examples The following examples use the reduction rules for note application: a) One semi-tone transposition (c3+ [e4;f3;g4]) = [f4;f3+;g4 +] b) Duration division by 4 (c3// [e4;f3;g4]) = [e4 / I;f311 I;g4 I] c) Transposition, expansion and accentuation (e3>* [e4;f3;g4) = [g4+ > *;a3 > *;b4 > *] Treatment of sequences The following examples take advantage of the new rule for the application of sequences. Indeed, in order to treat each element of a sequence, we now just have to describe a sequence of treatments and apply it to a sequence. a) Repetition of each sequence element We want here to apply the function X.[c;c] on each element of a sequence. For a specific sequence [e;f;g] we can write: ([Ac.Ec;cJc.[cc];..c.[c;c]J [e;f;gJ) [[e;e];[f;f];[g;g]] 4.2.2. Reduction rules extension The preceding examples only used the usual fl-reduction rule. By extending reduction rules we shall give functional capabilities to each language construction. Let's take for example the application of sequence [E;F;G] on sequence [H;I;J]. Following the intuitive concepts of sequence we consider [E;F;G] as a time ordering of functions. This means that when applied to a sequence the time ordering is maintained, as we show in the following example: ([E;F;G] [H; I;J)=[(E H);(F I);(G J)] In the same way we can consider [E] as time superimposed functions, therefore: With these two rules, we are able to time-organize functions in the same way as other musical objects. Music languages 248 ICMC Proceedings 1994

Page 249 ï~~The problem is now how to make it work for sequences of any length. Note that our reduction rules can treat expression as follows: ([A;B;C;D;...] [U;V;W])=*[(A U);(B V);(C W)] So the solution consist in creating an infinite sequence of Xc.[cc] functions (using the preceding Loop function) and applying it on the argument sequence: (Loop Ac.[c;c] [e;f;g]) [[e;eJ;[f;f];[g;g]] Here the treatment sequence could be more complex. For example: (Alt kc.[c;cJ c.fc;c; c] [e;f;g;a]) =,[[e;e];[f; f;f];[g; g];[a;a;a]] b) Sequences interlacing Suppose we want a function Inter such that: (Inter [c;d;c] [e;f;g])= [[c;e];[d;fl;[c;g]] Following the previous example the definition we need is: Inter= (Loop a. Ab.[a;b]) Indeed we have: (Loop Aa.b.[a;bJ [c;d;c] [e;f;g]) ([AZa.ab.[a;b]; A2a.Ab.[a;b];...j [e;d;e] [e;f;g]) =([ab. [c; b]; ),b.[d;b; a,.[c; b]] [e;f;g]) = [[c; e;[d;e];c;e]J c) Sequence multiplication Here we want to define a Mult function that takes two sequences as arguments and applies each note of the first sequence on the entire second sequence: (Muir [a;b;cJ S) =[(aS);(b S);(c S)] The definition we need is simple: Mul --)a.) b. (Loop c. (c b) a) Here is a example of multiplication and its result: Mul [c3;e3+;c3 -][e/;///;a// SL/-IJ fine a purely graphical musical calculus. We shall also maintain the same reductions rules. 5.1. Abstraction Abstractions are represented in a rectangle. The abstract note is declared first and separated from the abstraction body by a vertical line. Abstract notes are coloured gray to be distinguishable from real notes. Here are some abstractions representations. a) Two times repetition l tiJ Jfi aa3.[a3; a3] b) ABBA form c) Canon form Aa.Ab.[a; b; b; al 5.1.1. Application Compared to the textual representation, here the application of a to b will be written using brackets a[b]. Below are some application examples and their corresponding evaluation. a) One semi-tone transposition All notes are in effect transformation functions who's transposition value is the difference between their pitch and the reference pitch c3. Therefore by applying c3+ to an argument we transpose it by one semi-tone. b) Three time repetition Application of the "repeat three times" operation on a sequence. r- 2 3 FAn r-xu i I i~ 0), s lWi. By multiplying the same sequence with itself several times we can define a sort of "fractal" structure. Fractalize-=c.(Mult c (Muir c (Mult c c))) 5. A Visual Music Calculus Here we introduce a visual representation for our musical calculus. Here our descriptive language can be graphically represented using common musical notation, then we only have to introduce a graphical representation for abstraction and application to de ICMC Proceedings 1994 249 Music Languages

Page 250 ï~~oA - representation of control functions [Desain and Honing 1991]. By returning to the root of functional programming, Lambda calculus, we are able to propose a new approach in designing music programming languages. The central idea of our approach is to start from the music data structures and to introduce Lambda Calculus abstraction and application. Abstract music objects lead to a "natural" expression of music functions and operations. This has also been proposed by M. Balaban in a recent paper [Balaban 1994]. c) ABBA form Application of the Aa.tb.[a;b; two sequences. b; a] abstraction on A " Tim-I&,,u lt..ad d) Infinite sequence This example is the visual translation of the infinite sequence of c4 defined in 1.2.1.2.: X =( f.[c4;(f f)] Af].[c4;(f f)]) e) Looping function The loop function is defined by making the note c4 (from the preceding example) become variable. Loop= lc4.(/f.[c4;(f f)] f.[c4;(f f)]) 6. Conclusion We believe that the functional programming model is of great interest for music languages. Since 1984 R. Dannenberg proposed several functional music languages that demonstrate the advantages of features like lazy evaluation and high-order functions [Dannenberg 1984, 1989, 1991]. The functional approach is also central to the solution proposed by P. Desain and H. Honing for the A very interesting consequence of our approach is that, being music objects, functions can be composed, processed and represented in the same way as real music objects. Therefore, the programming activity is naturally in keeping with the composition activity which is more familiar to the user. References [Balaban 1994], M. Balaban, "Introducing Formal Processing into Music - The Music Structure Approach", Technical Report FC-94-07, Dept. of Math. and Comp. Science, Ben-Gurion University of the Negev, 1994. [Barendregt 1984] H. P. Barendregt, The Lambda Calculus, Its Syntax and Semantics. North-Holland, Amsterdam, 1984. [Church 1941], A. Church, The Calculi of Lambda Conversion, Princeton University Press, Princeton, N.J., 1941. [Dannenberg 1984], R. B. Dannenberg, "Artic: A Functional Language for Real-Time Control", in 1984 ACM Symposium on LISP and Functional Programming, ACM, New-York, 1984. [Dannenberg 1989], R. B. Dannenberg, "The Canon Score Language", Computer Music Journal, 13 (1), pp. 47-56, 1989. [Dannenberg et al. 1991 ], R. B. Dannenberg, C. L. Fraley and P. Velikonja, "Fugue: A Functional Language for Sound Synthesis", Computer, 24 (7), pp. 36-42, 1991. [Desain and Honing 1991], P. Desain and H. Honing, "Time Functions Function Best as Functions of Multiple Times", Computer Music Journal, 16 (2), pp. 17-34, 1991. [Field-Richards 1993] H. S. Field-Richards, "Cadenza: A Music Description Language", Computer Music Journal, 17 (4), pp. 60-72, 1993. [Hughes 1989] J. Hughes, Why Functional Programming Matters, The computer Journal 32 (2), pp. 98-107, 1989. Acknowledgment This research was sponsored by the music research department of French Ministry of Culture. Music Languages 250 ICMC Proceedings 1994