Issues in Domain Specific Language Design and Implementation Paul Hudak Dept. of Computer Science Yale University with a tip of the hat to: John Peterson, Zhanyong Wan, and Antony Courtney (all at Yale), Conal Elliott (Micro$oft Research), Greg Hager (Johns Hopkins Univ.), and Alastair Reid (Univ. of Utah) Copyright © 2000, Paul Hudak, All rights reserved. Is “Higher Level” Better? • A general-purpose programming language is an interface to an abstract machine. • When is one general-purpose language higher-level than another? • Assembly language is just the right abstraction for a CPU. • Why do some languages better match some applications than others? We Need Domain Specificity • A domain-specific language (or DSL) is a language that precisely captures a domain semantics; no more, and no less. • We also need domain specific: – – – – formalizations (starting point!) optimizations and transformations software tools type systems, aspects, constraints, etc. Advantages of DSL Approach • Programs in the target domain are: – more concise – quicker to write Contribute to higher programmer productivity – easier to maintain Dominant cost in large SW systems – easier to reason about Verification, transformation, optimization These are the same arguments in favor of any highlevel language! But in addition: – can often be written by non-programmers Helps bridge gap between developer and user T o ta l S W C o s t The Bottom Line C o n ve n tio n a l M e t h o d o lo g y C2 S ta rt -u p C o s ts C1 D S L -b a se d M e t h o d o lo g y S o ftw a r e L i fe -C y c l e DSL’s Allow Faster Prototyping Using the “Spiral Model” of Software Development design build specify test Without DSL specify design build test With DSL Why Study DSL’s? • Ok, so DSL’s are useful and important. • But why should we (the POPL community) be interested in DSL’s? – To have an impact on the real world. – The chances of a general purpose language succeeding are slim, no matter how good it is. – DSL design and implementation is a source of new and interesting problems. – It is also fun! • In the remainder of my talk I will concentrate on the latter two points. A Case Study: FRP • Fran is a DSL for functional reactive animation. • Frob is a DSL for functional robotics. • FRP (functional reactive programming) is the essence of Fran and Frob: – Fran = FRP + graphics engine + library – Frob = FRP + robot controller + library • FRP has two key abstractions: – Continuous, time-varying behaviors. – Discrete, reactive events. FRP by example A First Example leftRightCharlotte = moveXY wiggle 0 charlotte wiggle = sin (pi * time) charlotte = importBitmap "../Media/charlotte.bmp" Wiggle vs. Waggle upDownPat = moveXY 0 waggle pat waggle = cos (pi * time) pat = importBitmap "../Media/pat.bmp" The Power of Composition charlottePatDoubleDance = hvDance aSmall aSmall where aSmall = stretch 0.5 charlottePatDance charlottePatDance = hvDance charlotte pat hvDance im1 im2 =moveXY wiggle 0 im1 `over` moveXY 0 waggle im2 Stretching with a Wiggle (and a waggle) dance2 = hvDance (stretch wiggle charlotte) (stretch waggle pat) Integration Over Time velBecky = moveXY x 0 becky where x = -1 + integral 1 Integrate Twice: Acceleration accelBecky = moveXY x 0 becky where x = -1 + integral v v = 0 + integral 1 Mouse Position is a Behavior beckyChaseMouse = move offset becky where offset = integral vel vel = mouseMotion - offset Events • Discrete event streams include user input as well as domain-specific sensors, asynchronous messages, interrupts, etc. • They also include tests for dynamic conditions (“predicate events”) on behaviors (temperature too high, level too low, etc.) • Operations on event streams include: – Mapping, filtering, reduction, etc. – Reactive behavior modification (next slide). Reactivity “Where the Continuous Meets the Discrete” • FRP’s key reactive form: x `until` e ==> y can be read: “Behave as x until event e, then behave as y.” • Declarative semantics. • Rich algebra of transformations. • Examples... Reactive Control of Discrete Values tricycle = withColor (cycle3 green yellow red) (stretch (wiggleRange 0.5 1) circle) where cycle3 c1 c2 c3 = c1 `untilB` lbp ==> cycle3 c2 c3 c1 Reactive Control of Continuous Values growFlower = stretch size flower where size = 1 + integral bSign bSign = 0 `until` (lbp ==> -1 `until` lbr ==> bSign) .|. (rbp ==> 1 `until` rbr ==> bSign) Fran Also Supports 3D spiralTurn = turn3 zVector3 (pi*time) (unionGs (map ball [1 .. n])) where n = 40 ball i = withColorG color (move3 motion (stretch3 0.1 sphereLowRes )) where motion = vector3Spherical 1.5 (10*phi) phi phi = pi * fromInt i / fromInt n color = colorHSL (2*phi) 0.5 0.5 A Formal Semantics for FRP • What should an operational or denotational semantics for FRP look like? • How is Time represented? • Are all continuous behaviors well-behaved? • In what sense is an implementation (which must approximate continuous behaviors) faithful to a formal semantics? Let’s look first at a denotational semantics. The Domain of Time A denotational semantics for Fran requires first a proper treatment of time. as follo ws: Denote the set of real n um b ers as < , and inc in th set the elemen ts 1 and ¡1 . This set com eq ed w the standa arithm ic orde · , incl g the fac th ¡1 · x · 1 for all x 2 < . No w de¯ne Time = < + < , whe elem ts in th se ond \cop y" of < are distin ishe b y pre the w ¸ , as in 42, whic h shou b e read \at lea 42 Th ¸ de¯ne ? = ( ¡1 ), and the dom (i.e inf io ¸ Time orderin on Time b y: x v x; 8 x 2 < x v y if x · y ; 8 x; y 2 < ¸ x v y if x · y ; 8 x; y 2 < ¸ ¸ Analogy between Time and Lists t2 [1,1,1] [1,1] t1 t2 t1 [1] 1:1:_|_ ( ) [] 1:_|_ _|_ Time Here is arithmetic ordering. 1:1:1:_|_ Infinite list Lists Here is list-length ordering. Comparing Partial Elements We can extend the arithmetic ordering partial elements as follows: · to · x · y ´ if x · y th T r e ? ¸ x · y ´ ? ¸ ¸ x · y ´ if x · y th ? e F a ¸ The first line can be read: “The time x is less than or equal to a time that is at least y, if x· y, and undefined otherwise.” · Note: is monotonic and continuous. · · Semantic Functions We define two semantic functions, one for behaviors, the other for events: a : B ! T ! ® ® o c : E ! T £ ® ® We will start with the definition of “at”. Basic Constructs tim : B T a [ [ tim ] ] t = t in g a : V e c a e ® ) B ! T ! B ® ® R t at [ [ in g a b t ] ] t = a [ [ b ] ] 0 t 0 lift : ( ® ! : : : ! ® ! ¯ ) ! 1 n n Be ! : : : ! B ! B ® ® ¯ n 1 at [ [ lift f b : : : b ] ] t = f ( a [ [ b ] ] t ) : : : ( a [ [ b ] ] t ) 1 n 1 n n With lift we can re-define most common functions: sin lift 1 primSin ( ) lift 2 primPlus etc. Reactivity un : B ! E ! B ® ® B ® 0 at [ [ b un e ] ] t = if t · t th a [ [ b ] ] t e a [ [ b ] ] t e 0 wh ( t ; b ) = o cc [ [ e ] ] e Note: • · as used here is the extended version · defined earlier. • Transitions occur just after an event happens. The Semantics of Events c o : T ! ® ! E ® o c [ [ c o t x ] ] = ( t ; x ) e e pr e di at : B ! T ! E () B o o cc [ [ pr e d a b t ] ] = ( in f t > t j a [ [ b ] ] t g ; ( ) 0 0 ( : j : ) : Ev ! Ev ! Ev ® ® ® 0 0 o cc [ [ e : j : e ] ] = ( t ; x ) ; if t · t e e e 0 0 = ( t ; x ) ; ot e e wh ( t ; x ) = o cc [ [ e ] ] e 0 0 0 ( t ; x ) = o cc [ [ e ] ] e Note: “Choice” (.|.) is deterministic. Event Filtering and Snapshots (+ ) ) : Ev ! ( T ! ® ! ¯ ) ! E ® ¯ o cc [ [ e + ) f ] ] = ( t ; f t x ) e e wh ( t ; x ) = o cc [ [ e ] ] e sn : Ev ! B ! E ® ¯ ® £ ¯ o cc [ [ e sn b ] ] = ( t ; ( x; a [ [ b ] ] t ) ) e e wh ( t ; x ) = o cc [ [ e ] ] e For convenience we also define: (= ) ) : Eve ! ( ® ! ¯ ) ! Ev ® ¯ ( ¤ ) ) : Eve ! ( Tim ! ¯ ) ! E ® ¯ ( ¡ ) ) : Eve ! ¯ ! Ev ® ¯ ev = ) g = ev + ) ¸t x: g x ev ¤ ) h = ev + ) ¸t x: h t 0 0 ev ¡ ) x = ev + ) ¸t x: x Some Key Design Issues • Recursion vs. combinators until, switch :: Beh a -> Event (Beh a) -> Beh a b `switch` e = b `until` e ==> \b1 -> b1 `switch` e • A rich algebra of events lbp :: Event ( ); key :: Event Char (==>) :: Event a -> (a->b) -> Event b accum :: a -> Event (a -> a) -> Event a snapshot :: Event a -> Behavior b -> Event (a,b) when :: Behavior Bool -> Event ( ) (.|.) :: Event a -> Event a -> Event a • “Aging” the “user” let getString = constB "Init" `switch` accum "" (key ==> \ch -> (++ [ch])) ==> constB in constB "Start" `switch` lbp -=> getString Visual Languages • In some domains, the most common notation is pictorial. • For example: signal processing, digital hardware design, control systems, and sound synthesis. • Should Fran / FRP be a visual programming language, and if so, what should it look like? • We need tools to provide both views of a program. Visual FRP Implementing DSL’s • Language design is difficult! • Idea: Embed DSL in Haskell (or other language) • Haskell features that facilitate task: – – – – type classes higher-order functions lazy evaluation syntactic extensions • Goal: Embed semantics in functions rather than interpret as a data structure. DSL’s Embedded in Haskell At Yale: • Graphics/Animation (w/Microsoft) • Robotics (w/JHU) • Computer Vision (Fvision) • Computer Music (Haskore) • Sound Synthesis (Hsound) • Dance/choreography (Haskanotation) Elsewhere: • HaskellScript for the WWW (Utrecht) • Scripting COM objects (Utrecht, Microsoft) • Hardware Description (OGI, Chalmers) • Parsing/pretty printing (Utrecht, Chalmers) • GUI’s (FranTK, etc.) A Typical Fran Expression 1 `until` Behavior Infix operator time>2 Predicate event -=> time+1 Behavior Infix operator This is equivalent to: until 1 ((-=>)((>) time 2)((+) time 1)) But, what are behaviors and events? Fran’s Behaviors Haskell’s type classes conveniently describe behaviors: newtype Behavior a = Beh (Time -> a) instance Num (Behavior a) where Beh f + Beh g = Beh (\t -> f t + g t) fromInteger x = Beh (\t -> x) Also define: time = Beh (\t->t) And thus: 1 time+1 Beh (\t->1) Beh (\t->t) + Beh (\t->1) Beh (\t-> (\t->t) t + (\t->1) t) Beh (\t-> t+1) Lazy Evaluation Essential for things like: color = red `until` lbp ==> blue `until` lbp ==> color which would not terminate under a call-by-value interpretation. Lazy evaluation is also used to implement various stream-like objects that represent “demand-driven” computation. Core Semantics of Fran ICFP semantics: User semantics: at :: Beh a -> Time -> a occ :: Event a -> ((Time,a), Event a) at :: Beh a -> (User, Time) -> a occ :: (User, Event a)->((Time,a),User) time :: Beh Time time `at` t = t time :: Beh Time time `at` (u,t) = t switch :: Beh b -> Event (Beh b) -> Beh b (b `switch` e) `at` t = let ((t0,b0),e0) = occ e in if t<=t0 then b `at` t else (b0 `switch` e0) `at` t switch :: Beh b -> Event(Beh b) ->Beh b (b `switch` e) `at` (u,t) = let ((t0,b0),u0) = occ (u,e) in if t<=t0 then b `at` (u,t) else (b0 `switch` e) `at` (u0,t) which suggests the implementation: which suggests the implementation: type Beh a = Time -> a type Event a = [(Time, a)] type Beh a = (User, Time) -> a type Event a = User -> ((Time,a), User) type User = [(Time, UA)] b `at` t = b t occ e = (head e, tail e) b `at` (u,t) = b (u,t) occ (u,e) = e u Time-Ordered Search • Motivation by analogy: Consider ordered list L :: [T] and function: inList :: [T] -> T -> Bool • Now suppose we want to find many elements in L: manyInList :: [T] -> [T] -> [Bool] manyInList xs ys = map (inList xs) ys This is quadratic: O(|xs|*|ys|) • Better to order ys first, then do the search: manyInList xs (y:ys) = let (b,xs’) = inListRem xs y in b : manyInList xs’ ys This is linear: O(|xs|) Type-Directed Derivation Behaviors: Events: specification: Beh a = (User, Time) -> a uncurry: Beh a = User -> Time -> a time-ordered search: Beh a = User -> [Time] -> [a] unfold User: Beh a = [(UA,Time)] -> [Time] -> [a] unzip User and uncurry: Beh a = [UA] -> [Time] -> [Time]->[a] synchronize: Beh a = [UA] -> [Time] -> [a] specification: Ev a = User -> ((Time,a), User) encode non-occurences: Ev a = User -> (Maybe (Time,a), User) decouple aging: Ev a = User -> Maybe (Time,a) time-ordered search: Ev a = User -> [Maybe (Time,a)] unfold User: Ev a = [(UA,Time)] -> [Maybe (Time,a)] unzip User and uncurry: Ev a = [UA] -> [Time] -> [Maybe (Time,a)] synchronize: Ev a = [UA] -> [Time] -> [Maybe a] Note now: Ev a = Beh (Maybe a) Advantages of Stream Design • “User” implicitly “aged;” no User argument to event generators. • No dynamic adjustments in time; everything is fully synchronized. • Behaviors can be memoized using a singleton cache. • Potential for heavy optimization. • Event a = Behavior (Maybe a) One disadvantage: cannot easily time-transform User. Faithful Implementations • The stream implementation of FRP is an approximation to continuous behaviors. • But the denotational semantics is exact. • So in what sense is the implementation faithful to the formal semantics? • Is there any hope for semantics-directed compilation or transformation/optimization? Egregious Behaviors • Consider this behavior: > zeno :: Event () > zeno = when (lift1 f time) where > f t = if t>2 || t<1 then t<0.5 > else f (2*t-2) • This captures Zeno’s Paradox: on or off?? light on light off 1 2 time and is a natural expression of non-determinism! More Egregious Behavior • Consider this simple behavior: > sharp :: Event () > sharp = when (time ==* 1) • This seems innocent enough, but the predicate is true only instantaneously at time = 1. However, a stream-based implementation may miss this event. • In fact we can show that: A stream-based implementation may miss this event even at the limit of event sampling. “Good” Behaviors • Zeno’s paradox represents a problem with the semantics, and instantaneous events represent a problem with a stream-based implementation. • Solution: define good behaviors as those that converge to a stable value as the sampling rate increases. Similarly, good events are those whose frequency within a finite period becomes stable as the sampling rate increases. • Key result: we can show that, with suitable constraints, in the limit, as the sample time increases to infinity, a steam-based implementation is faithful to the denotational semantics. Domain Specific Transformations • Many domains exhibit nice algebraic properties, with which one can reason about, transform, and optimize programs. • Query optimization in databases is the prototypical example. • An implementation can often be proven correct with respect to these properties. • But we cannot expect a general purpose compiler to perform these optimizations for us. • We need source level meta-programming tools. Example: Simple Graphics -- Atomic objects: circle square importGIF "p.gif" -- Composite objects: scale v p color c p trans v p p1 `over` p2 p1 `above` p2 p1 `beside` p2 -- a unit circle -- a unit square -- an imported bit-map ------- scale picture p by vector v color picture p with color c translate picture p by vector v overlay p1 on p2 place p1 above p2 place p1 beside p2 -- Axioms over, above, and beside are associative scale, color, and trans distribute over over, above, & beside scale is multiplicative, trans is additive etc. Thus an algebra of graphics emerges. Simple Animations type Behavior a = Time -> a type Animation = Behavior Picture Now we “lift” the simple graphics operations to work on behaviors as well. For example: (b1 `overB` b2) t = b1 t `over` b2 t (b1 `aboveB` b2) t = b1 t `above` b2 t (b1 `besideB` b2) t = b1 t `beside` b2 t (scaleB v b) t (colorB c b) t (transB v b) t = scale (v t) (b t) = color (c t) (b t) = trans (v t) (b t) And a new function to express the current time: time t = t All previous graphics axioms hold for animations. Basic Haskore Design type Pitch = (PitchClass, Octave) data PitchClass = Cf | C | Cs | Df | D | Ds | Ef | E | Es | Ff | F | Fs | Gf | G | Gs | Af | A | As | Bf | B | Bs type Octave = Int data Music = Note Pitch Dur | Rest Dur | Music :+: Music | Music :=: Music | Tempo Int Int Music | Trans Int Music | Instr IName Music type Dur = Float type IName = String type PName = String -- a note \ atomic -- a rest / objects -- sequential composition -- parallel composition -- scale the tempo -- transposition -- instrument label -- in whole notes Performance & Interpretation A performance is a temporal sequence of musical events. type Performance = [Event] data Event = Event Time IName AbsPitch DurT Volume type Time type DurT type Volume = Float = Float = Float Now we need a way to perform (I.e. interpret) music. perform :: Context -> Music -> Performance type Context = (Time,IName,DurT,Key,Volume) time instrument tempo key volume Music perform Performance Literal Interpretation A literal interpretation is the most straightforward. perform c@(t,pl,i,dt,k,v) m = case m of Note p d -> playNote pl c p d Rest d -> [] m1 :+: m2 -> perform c m1 ++ perform (setTime c (t+(dur m1)*dt)) m2 m1 :=: m2 -> merge (perform c m1) (perform c m2) Tempo a b m -> perform (setTempo c (dt * float b / float a)) m Trans p m -> perform (setTrans c (k+p)) m Instr nm m -> perform (setInstr c nm ) m Player nm m -> perform (setPlayer c (pmap nm)) m Phrase pas m -> interpPhrase pl c pas m Equivalence of Musical Objects Two musical objects are (observationally) equivalent if they result in the same literal performance under all contexts. Definition: m1 = m2 iff for all contexts con, perform con m1 = perform con m2 An Algebra of Music Emerges Using simple equational reasoning, many useful axioms are easily proven: • Tempo-scaling is multiplicative. • Transposition is additive. • Parallel composition is commutative. • Tempo-scaling and transposition are distributive over both sequential and parallel composition. • Sequential and parallel composition are associative. • Rest 0 is a unit for Tempo and Trans, and a zero for sequential and parallel composition. l ll Lambda in Motion: Controlling Robots with Haskell Robots with Vision Motivation • Mobile robot control is hard! • Prototyping is essential: repeated experimentation required. • Must deal with unpredictability: imprecise sensors, uncertain environment, mechanical problems. • Need to compose solved sub-problems. • Reliability needed - programs must recover from errors; explore alternative strategies to meet goals. Our Solution: Frob • Recall that: Frob = FRP + robot controller + robot/vision library • Programming robots is a lot like programming an animation! • … except that: – – – – The robot doesn’t always do what you want it to do. Error / anomalous conditions are more common. Real-time issues are more dominant. Robots are a lot slower than graphics hardware. Our Robots: Nomadic Technologies SuperScout Vision 16 Sonars Bumpers Wheel Controls Computing: PC running Linux Hugs Radio Modem A Control System for Wall Following Time is Implicit! Notation is nearly identical. Details of clocking are hidden. Side Sonar s Objectives: Maintain a specified distance wall follow f sfrom d = (v,w) w where v = turn limit too vmaxmuch (f-d) Don’t w = limit toward wall(vcurr * sin amax) (s-d) - derivative s Stop (slowly) when approaching an obstacle ahead. n Front Sonar f n = limit(nmax, f - d) w = limit(sin qmax * ncurr, s - d) - ds/dt limit(mx,v) = max(-mx,min(v,mx)) Adding Reactivity Wall follower terminates two ways: -- Blocked in front -- No wall on side Data WallEnd = Blocked | NoWall type Wheels = (SpeedB, AngleB) wfollow :: SonarB -> SonarB -> FloatB -> (WallEnd -> Wheels) -> Wheels wfollow f s d c = follower f s d `untilB` ( predicate (f <= d) -=> Blocked .|. predicate (s >= 2*d) -=> NoWall) ==> c Capture this pattern in a Monad! The behavior The Theterminating continuationevent of the overall behavior A Task Monad A task couples a behavior with a termination event. In it’s simplest form, we combine a behavior and an event into a task: mkTask :: (Behavior a, Event b) -> Task a b Continuous value defined by task Value returned at end of task (b1,e1) >> (b2,e2) = (b1 `untilB` e1 -=> b2, e2) Hide reactivity inside monadic sequencing Using Tasks Blocked Wall Follow Left Turn Right Free Wall left No Wall Turn Left wallTask f s d = mkTask (wallFollow f s d, predicate (f <= d) -=> Blocked .|. predicate (s >= 2*d) -=> NoWall) roomFollow f s d = do status <- wallTask f s d case status of NoWall -> turnLeft Blocked -> turnRight roomFollow f s d What’s under the hood? Event based interface to the outside world Smoothing / sampling to allow continuous representations Clocking controls for smoothing / sampling. Dispatch output events Accept input events FRP Gateway Sampling and Smoothing Clocking Policy User Program “Mostly” continuous world Conclusions There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. ---C.A.R. Hoare • Domain Specific Languages are a Good Thing. • Embedded DSL’s (ala Haskell) can be used to implement highly effective programming environments. • “Functional Reactive Programming” is a good abstraction for many real-time reactive domains. • The programming languages community has some good ideas; let’s start using them! • DSL technology is fertile ground for programming language research. Glove by Tom Makucevich with help from Paul Hudak Composed using Haskore, a Haskell DSL, and rendered using csound. For Further Reading... • The Haskell School of Expression -- Learning Functional Programming through Multimedia • Cambridge University Press • Teaches functional programming using Haskell, including three DSL’s: a Fran-like language (FAL), a Haskore-like language (MDL), and an imperative robot language (IRL). • Available now from amazon.com, bn.com, etc. Ongoing Work • Vision-based Control (via FVision, another Haskell DSL) • Planning / Scheduling / Multiple robots • Teach Haskell & robotics to students • Better implementation / optimization • Better tools (debugging, profiling, etc.) • Formal semantics / verification • Hybrid / control systems

Descargar
# Domain-Specific Embedded