MIT OpenCourseWare http://ocw.mit.edu 6.005 Elements of Software Construction Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. Little Languages Rob Miller Fall 2008 © Robert Miller 2008 Representing Code with Data Consider a datatype representing language syntax ¾Formula is the language of propositional logic formulas ¾a Formula value represents program code in a data structure; i.e.new And(new Var( Var(“xx”) new Var(“y”))), Var( y ))has the same semantic meaning as the Java codex && y¾but a Formula value is a first-class object• first-class: a value that can be passed, returned, stored, manipulated • the Java expression “x && y” is not first-class Today’s Topics Functionals ¾Objects representing executable code Higher-order functions ¾F hi hlFunctiions that acceptffunctions as arguments or return them as results Domain-specific languages ¾PCAP: primitives, combination, abstraction pattern © Robert Miller 2008 Representing Code as Data Recall the visitor pattern ¾A visitor represents a function over a datatype • e.g. new SizeVisitor() represents size : List → int public class SizeVisitor implements ListVisitor { public Integer visit(Empty l) { return 0; } public Integer visit(Cons l) { return 1 + l.rest().accept(this); } } A visitor represents code as a firstA first-class object, tooclass too¾A visitor is an object that can be passed around, returned, and stored¾But it’s also a function that can be invokedToday’s lecture will see more examples of code as data © Robert Miller 2008 © Robert Miller 2008 1 Today’s Problem: Music Interesting music tends to have a lot of repetition ¾Let’s look at rounds, canons, fugues ¾A familiar simple round is “Row Row Row YourBoat”: onevoice starts, other voices enter after a delay Row row row your boat, gently down the stream, merrily merrily ... Row row row your boat, gently down the stream... ¾Bach was a master of this kind of music • Recommended reading: Godel Escher Bach, by Douglas Hofstadter Recall our MIDI piano from early lectures ¾A song could be represented by Java code doing a sequence of calls on a state machine: machine.play(E); machine.play(D); machine.play(C); ... ¾We want to capture the code that operates this kind of machine as first-class data objects that we can manipulate, transform, and repeat easily © Robert Miller 2008 A Few of Music’s Operations notes : String x Instrument → Musicrequires string is in a subset of abc music notatione.g. notes(“E D C D | E E E2 |”, PIANO) abc notation can also encode sharps & flats, higher/lower octaves 1 beat note 2-beat note duration : Music → doublereturns total duration of music in beats e.g. duration(Concat(m1, m2)) = duration(m1) + duration(m2) transpose : Music x int → Musicreturns music with all notes shifted up or down in pitch by the given number of semitones (i.e., steps on a piano keyboard)play : Music → voideffects plays the musicall these operations also have precondition that parameters are non-null © Robert Miller 2008 Music Data Type Let’s start by representing simple tunes Music = Note(duration:double, pitch:Pitch, instr:Instrument) + Rest(duration:double) + Concat((m1:Music, m2:Music)) ¾duration is measured in beats ¾Pitch represents note frequency (e.g. C, D, E, F, G; essentially the keys on the piano keyboard) ¾Instrument represents the instruments available on a MIDI synthesizer Design questions ¾is this a tree or a list? what would it look like defined the other way?¾what is the “empty” Music object?• it’s usually good for a data type to be able to represent nothing • avoid null¾what are the rep invariants for Note, Rest, Concat?© Robert Miller 2008 Implementation Choices Creators can be constructors or factory methods ¾Java constructors are limited: interfaces can’t have them, and constructor can’t choose which runtime type to return • new C() must always be an object of type C, • so we can’t have a constructor Music(String, Instrument), whether Music is an interface or an abstract class Observers & producers can be methods or visitors ¾Methods break up function into many files; visitor is all in one place ¾Adding a method requires changing source of classes (not always possible) ¾Visitor keeps dependencies out of data type itself (e.g. MIDI dependence) ¾Method has direct access to private rep; visitor needs to use observers Producers can also be new subclasses of the datatype ¾e.g. Music = ... + Transpose(m:Music, semitones:int)¾Defers the actual evaluation of the function¾Enables more sharing between values© Robert Miller 2008 ¾Adding a new subclass requires changing all visitors 2 -Duality Between Interpreter and Visitor Operation using interpreter pattern ¾Adding new operation is hard (must add a method to every existing class) ¾Adding new class is easy (changes only one place: the new class) Operation using visitor pattern ¾Adding new operation is easy (changes only one place: the new visitor)¾Adding new class is hard (must add a method to every existing visitor)© Robert Miller 2008 Simple Rounds We need one more operation: delay : Music x double → Musicdelay(m, dur) = concat(rest(dur), m)And now we can express Row Row Row Your Boat rrryb = notes(“C C C3/4 D/4 E | E3/4 D/4 E3/4 F/4 G2 | ...”, PIANO) together(rrryb, delay(rrryb,4)) • Two voices playing together, with the second voice delayed by 4 beats¾This pattern is found in all rounds, not just Row Row Row Your Boat¾Abstract out the common patternround : Music x double x int → Music round(m, dur, n) = together(m, round(delay(m, dur), dur, n-1)) m if n == 1 if n > 1 ¾The ability to capture a general pattern like round() is one of the advantages of music as a first-class object rather than merely a sequence of play() calls © Robert Miller 2008 Multiple Voices For a round, the parts need to be sung simultaneously Music = Note(duration:double, pitch:Pitch, instr:Instrument) + Rest(duration:double) + Concat((m1:Music, m2:Music)) + Together(m1:Music,m2:Music) ¾Here’s where our decision to make Concat() tree-like becomes very useful • Suppose we instead had:Concat = ListTogether = List• What kinds of music would we be unable to express? Composite pattern ¾The composite pattern means that groups of objects (composites) can be treated the same way as single objects (primitives)¾T = C1(... ,T) +...+ Cn(... ,T) + P1(... ) +...+ Pm(... )Music and Formula are composite data types. composites primitives © Robert Miller 2008 Distinguishing Voices We want each voice in the round to be distinguishable ¾e.g. an octave higher, or lower, or using a different instrument ¾So these operations over Music also need to be first-class objects that can be passed to round()¾Fortunately operations implemented as visitors already are objectscanon() applies a visitor to the repeated melody canon : Music x double x Visitor x int → Music e.g. canon(rrryb,4,new TransposeVisitor(OCTAVE),4)produces 4 voices, each one octave higher than the lastcanon() is a highercanon() higher-order functionorder function ¾A higher-order function takes a function as an argument or returns a function as its result© Robert Miller 2008 3 Functional Objects Not all operations are visitors ¾Let’s generalize the idea of a music transformer functioninterface UnaryFunction {U apply(T t); } ¾An instance of UnaryFunction is a functional object, representing some function f :T → U ¾For example: new UnaryFunction() { public Music apply(Music m) { return delay(m, 4); } } ¾In general, we might want a delayer() method that produces a delay transformer with an arbitrary delay (not just 4 beats): delayer : int → UnaryFunction Music → Music this anonymous class is essentially a lambda expression producing a functional object note that delayer is a higher-order function too that UnaryFunction represents © Robert Miller 2008 let’s write it this way, the abstract type Repeating A line of music can also be repeated by the same voice repeat : Music x (Music → Music) x int → Music e.g. repeat(rrryb, octaveHigher, 2) = concat(rryb, octaveHigher(rryb)) ¾Note the similarity to counterpoint():counterpoint: m together f(m) together ... together fn-1(m)repetition: m concat f(m) concat ... concat fn-1(m)¾And in other domains as well:sum: x + f(x) + ... + fn-1(m)() ()product: x · f(x) · ... · fn-1(m)Counterpoint A canon is a special case of a more general pattern ¾Counterpoint is n voices singing related music, not necessarily delayed counterpoint : Music x (Music → Music) x int → Music ¾counterpoint music: Expressed as counterpoint, a canon applies two functions to the delay and transform canon(m, delay, f, n) = counterpoint(m, f ○ delayer(delay), n) Another general pattern function composition ○ : (U → V) x (T → U) → (T → V) public static UnaryFunction compose(final UnaryFunction g,p y p ( y g final UnaryFunction f) { return new UnaryFunction() { publicV apply(T t) { return g.apply(f.apply(t)); } }; } © Robert Miller 2008 Binary Functionals We need first-class representation for binary operations like together, concat, plus, times interface BinaryFunction {V apply(T t U u);t, }¾An instance of BinaryFunction represents some f :T x U → Vtogether: Music x Music → Musicconcat: Music x Music → MusicNow we can capture the pattern series :T x (T x T → T) x (T → T) x int → T initial value binary op f n ¾There’s a general pattern here, too; let’s capture it counterpoint(m, f, n) = series(m, together, f, n) repeat(m, f, n) = series(m, concat, f, n) © Robert Miller 2008 © Robert Miller 2008 4 ¾t Repeating Forever Music that repeats forever is useful for canons forever: Music → Musicplay(forever(m)) plays m repeatedly, foreverd ti (f ()) +∞ duration(forever(m)) = double actually has a value for this: Double.POSITIVE_INFINITY Music = Note(duration:double, pitch:Pitch, instr:Instrument) + Rest(duration:double) + Concat(m1:Music, m2:Music) + Together(m1:Music,m2:Music) + Forever(m:Music) why can’t we implement forever() using repeat(), or any of the existinp g Music (), y subtypes? ¾Here’sthe Row Row Row Your Boatround, forever:canon (forever(rrryb), 4, octaveHigher, 4)© Robert Miller 2008 Pachelbel’s Canon (well, the first part of it, anyway...) pachelbelBass = notes(“D,2 A,,2 | B,,2 ^F,, | ... |“, CELLO) pachelbelMelody = notes(“^F’2 E’2 | D’2 ^C’2 | ... | ... | ... | ... | ... |“, VIOLIN) pachelbelCanon = canon(forever(pachelbelMelody),16,identity,3)pachelbel = concat(pachelbelBass, accompany(pachelbelCanon,pachelbelBass))© Robert Miller 2008 Accompaniment accompany: Music x Music → Musicrepeats second piece until its length matches the first piecemelody linebass line or drum line,repeated to match melody’s lengthaccompany(m, b) = ogether(m, reppeat(b,, identity,, duration(()m)/duration(b))) if duration(()m) finite g(,( y()))together(m, forever(b)) if duration(m) infinite© Robert Miller 2008 Little Languages We’ve built a new language embedded in Java ¾Music data type and its operations constitute a language for describingmusic generation¾Instead of just solving one problem (like playing Row Row Row Your Boat), build a language or toolbox that can solve a range of related problems (e.g. Pachelbel’s canon) ¾This approach gives you more flexibility if your original problem turns out to be the wrong one to solve (which is not uncommon in practice!) ¾Capture common patterns as reusable abstractions Formula was an embedded language too Formula combined with SAT solver is a powerful tool that solves a widerange of problems© Robert Miller 2008 5 Embedded Languages Useful languages have three critical elements Java Formula language Music language Primitives 3, false Var, Bool notes, rest Means of Combination +, *,==, &&,||, ... and, or, not together,concat, transpose,delay, … Means of Abstraction variables, methods, classes Java mechanisms functional objects + Java mechanisms ¾6.01 calls this PCAP (the primitive-combination-abstraction pattern) © Robert Miller 2008 Summary Composite pattern ¾Composite data types allow a group of objects to be treated the same as a single object Functionals ¾UnaryFunction and BinaryFunction represent functions as Java objects¾So do Runnable and Visitor, in factHigher-order functions ¾Operations that take or return functional objects Building languages to solve problems h ibili¾A lA language has greaterflflexibility thhan a mere program, bbecause iit can sollve large classes of related problems instead of a single problem ¾Interpreter pattern, visitor pattern, and higher-order functions are useful for implementing powerful languages ¾But in fact any well-designed abstract data type is like a new language © Robert Miller 2008 6