1 Hack Your Language! CS164: Introduction to Programming Languages and Compilers, Spring 2012 UC Berkeley Ras Bodik Shaon Barman Thibaud Hottelier Lecture 1: Why Take CS164?Today What is a programming language Why you will write a few in your life How you will learn language design skills in cs164 2Outline • Ten examples of languages you may write • A puzzle • The puzzle solved in Prolog • Evolution of programming abstractions • Why you will write a small language, sw.eng. view • The course project • The final project: your small language • Other course logistics 3What will I do with knowledge from cs164? or, why you will develop a language 41. You work in a little web search company Boss says: “We will conquer the world only if our search box answers all questions the user may ask.” You build gcalc: Then you remember cs164 and easily add unit conversion. You can settle bar bets such as: How long a brain could function on 6 beers, provided alcohol energy was not converted to fat?: You are so successful that Yahoo and Bing try to imitate you. 52. Then you work in a tiny browser outfit You observe JavaScript programmers and take pity. Instead of var nodes = document.getElementsByTagName('a'); for (var i = 0; i < nodes.length; i++) { var a = nodes[i]; a.addEventListener('mouseover', function(event) { event.target.style.backgroundColor=‘orange'; }, false ); a.addEventListener('mouseout', function(event) { event.target.style.backgroundColor=‘white'; }, false ); } you let them write this, abstracting from iteration and events jQuery('a').hover( function() { jQuery(this).css('background-color', 'orange'); }, function() { jQuery(this).css('background-color', 'white'); } ); jQuery was developed by John Resig, now at Mozilla 6… and the fame follows 73. Then you write visual scripting for musicians Allowing non-programmers produce interactive music by “patching” visual metaphors of electronic blocks: Guitair Zeros: a S.F. band enabled by the Max/MSP language. http://www.youtube.com/watch?v=uxzPCt7Pbds Max/MSP was created by Miller Puckette and is now developed by Cycling ’74. 84. Then you live in open source You see Linux developers suffer from memory bugs, eg buffer overruns and dangling pointers (accesses to freed memory). x = new Foo() y=x … free(y) … x.f = 5 You design a tool that associates each byte in memory with a shadow “validity bit”, set by new and reset by free. When a memory location is accessed, you check its validity bit. To add these checks, the implementation rewrites the binary of the program, and adds shadow memory. Valgrind was developed by Julian Seward 95. Then you decide to get a PhD You get tired of PowerPoint and its animations. Or you realize you are not a WYSIWIG person. You embed a domain-specific language (DSL) into Ruby. see slide 8 in http://cs164fa09.pbworks.com/f/01-rfig-tutorial.pdf 10 …The animation in rfig, a Ruby-based language slide!('Overlays', 'Using overlays, we can place things on top of each other.', 'The pivot specifies the relative positions', 'that should be used to align the objects in the overlay.', overlay('0 = 1', hedge.color(red).thickness(2)).pivot(0, 0), staggeredOverlay(true, # True means that old objects disappear 'the elements', 'in this', 'overlay should be centered', nil).pivot(0, 0), cr, pause, # pivot(x, y): -1 = left, 0 = center, +1 = right staggeredOverlay(true, 'whereas the ones', 'here', 'should be right justified', nil).pivot(1, 0), nil) { |slide| slide.label('overlay').signature(8) } rfig was developed by Percy Liang, a Berkeley student 11More examples of how cs164 will help 12 6. ProtoVis, a DSL for data visualization 7. Roll your own make/ant in Python (Bill McCloskey) 8. Ruby on Rails (another system on top of Ruby) 9. Custom scripting languages (eg for testing) 10. Custom code generators (eg for new hardware) 11. Your language or tool here. 12. Choose the right language (reduce lines 10x)13 Summary Summary: Don’t be a boilerplate programmer. Instead, build tools for users and other programmers – libraries – frameworks – code generators – small languages (such as configuration languages) – and why not also big languages? – we just saw 10 concrete examples Take historical note of textile and steel industries: do you want to build machines and tools or do you want to operate those machines?14 Take cs164. Become unoffshorable. “We design them here, but the labor is cheaper in Hell.”How is this PL/compiler class different? Not really a compiler class. It’s about: a) foundations of programming langauges b) but also how to design your own languages c) how to implement them d) and about PL tools, such as analyzers and bug finders e) and also about some classical C.S. algorithms. 15a 5-minute intermission with a puzzle solve with your neighbor 16Puzzle: Solve it. It’s part of the lecture. From The Lady or the tiger, R. Smulyan 17Solution 18Languages as thought shapers 19 http://soft.vub.ac.be/~tvcutsem/whypls.html>Language as a thought shaper We will cover less traditional languages, too. The reason: A language that doesn't affect the way you think about programming, is not worth knowing. an Alan Perlis epigram <http://www.cs.yale.edu/quotes.html> One of thought-shaper languages is Prolog. You will both program in it and implement it. 20Solving the puzzle with Prolog (part 1) We’ll use integers 1..7 to denote the stamps. Numbers 1 and 2 denote red stamps. Yellow stamps are 3 and 4 … red(1). red(2). yellow(3). yellow(4). green(5). green(6). green(7). 21Solving the puzzle with Prolog (part 2) S is variable that can be bound to a stamp, ie to a number 1, 2, ..7. With the following, we say that a stamp is either a red stamp or a yellow stamp or a green stamp. stamp(S) :- red(S) ; yellow(S) ; green(S). We now state what three stamps, A, B, C, we may see on the three heads. (We are saying nothing more than no stamp may appear on two heads.) valid(A,B,C) :- stamp(A), stamp(B), stamp(C), A\=B, B\=C, A\=C. 22Solving the puzzle with Prolog (part 3) Now to the interesting parts. Here we encode the fact that logician a can't rule out any color after seeing colors B and C on b’s and c’s heads. We define the so-called predicate a_observes(B,C) such that it is true iff all
View Full Document
Unlocking...