Print This Issue

$10 Million NSF Project on Computer-assisted Programming

April 10, 2012, Volume 58, No. 29

AlurThe University of Pennsylvania will lead a $10 million National Science Foundation (NSF) project to make computer programming faster, easier and more intuitive. Dubbed ExCAPE for Expeditions in Computer Augmented Program Engineering, the project is a highly collaborative effort that will involve multiple research institutions, partners in industry and educational outreach to the next generation of computer scientists.

The project was awarded a five-year, $10 million grant as part of the NSF’s Expeditions in Computing program, which funds teams with ambitious, fundamental-research agendas in computer science. The ExCAPE team will be led by Dr. Rajeev Alur, professor of computer and information science in Penn’s School of Engineering and Applied Science. Dr. Alur will collaborate with fellow Penn engineering professors Dr. Milo Martin, Dr. Boon Thau Loo, Dr. George Pappas and Dr. Steve Zdancewic.

The ExCAPE team also includes researchers from UCBerkeley, UCLA, Cornell University, University of Illinois at Urbana-Champaign,  University of Maryland, MIT, University of Michigan and Rice University.

“Computers have evolved at a dramatic pace, but the technology that’s used to develop programs and software is evolving comparatively slowly,” Dr. Alur said. “What it means to ‘code’ hasn’t changed much in the last 20 to 30 years. It’s still done by expert programmers and is quite time-consuming, expensive and error-prone.”

In today’s programming languages, programmers must write out explicit instructions for what they want the program to do. For large projects, this kind of coding is so complicated that programmers need separate “verification” teams to weed out errors.

During the last two decades, this verification technology has matured, leading to powerful analysis tools that can find subtle mistakes in real-world systems. The ExCAPE approach will leverage these advances to help programmers avoid such mistakes in the first place.

The researchers are proposing an integrated toolkit for automated program synthesis. Such a toolkit would allow a programmer to essentially collaborate with a computer on writing a program, contributing the parts they are most suited to. With more powerful and integrated verification systems, the computer would be able to give feedback to the programmer about errors in the program and even propose corrections.   

“Let’s say you want to program a robotic car for parallel parking,” Dr. Alur said. “Instead of asking the programmer to write complete code in one particular style, we want to offer the programmer flexibility. The programmer can start by specifying high-level goals, such as the final desired car position and the requirement that there should be no collisions along the way.”

Automatically translating such goals directly to code is not yet feasible, so the programmer would still have to do some amount of coding to providing basic solution strategies for the program. For parallel parking, a strategy might correspond to a sequence of basic maneuvers: pull in front of the spot, back up straight, start turning and, finally, straighten out.

While this basic strategy for parallel parking is intuitive for humans, figuring out exactly when to start turning, and by how much, remains tricky. Humans, whether they are drivers or programmers, aren’t good at trying lots of combinations in search of the best one, but that’s exactly what computers are best suited to do.

“The synthesis tool can therefore start with the strategies provided by the coder, then explore different combinations for the tricky parts, automatically filling in the details with the best possible values to produce a complete program,” Dr. Alur said.

Programming for robotic behavior is one of four real-word problem areas the ExCAPE team will test their research on. The researchers will work with programmers at AT&T, Coverity, Honeywell, IBM, Intel, Microsoft and Willow Garage to see if the synthesis tool is effective in meeting their coding challenges.

Other challenge areas involve figuring out how to set up routing policies for flow of information across networks of computers, how software written to work on single processor computers can be correctly translated to improve performance while running on multiple cores that are now common even in mobile devices, and how to design efficient and correct algorithms for coordinating decisions among multiple computers.    

The researchers hope that this toolkit will change the public perception of computer science and, potentially, how it and other sciences are taught. 

“One goal in this regard is to get high school students excited about computer programming,” Dr. Alur said. “We want to convey to them that programming does not mean tedious coding according to strict rules but is more about being able to express a computational strategy for problems.”

The verification systems in the ExCAPE team’s synthesis toolkit could be applied to students working on high school algebra problems, for example, identifying flaws in logic that lead to incorrect answers. The toolkit’s smart feedback could even generate similar problems to test whether a student has learned from a mistake. 

Almanac - ks6+Pe&Ô,YnYRi$Mz~HH  Jo %Q"e)IL3x-v~O~ym,]!QdOHwh3KI80۫vԖ&IYpZ>FB%-0yE#V)iz gDiy#;ElC[NE`B*Xy@bz4^TiW0u0 ƌЁ0rDԖ y>icF\  ]SB((jWα#8ȏyDG802Y-ۇm̨THeP2" 0ːaRP)9146<5Ē'+ĵv-qW!WF9 18&Z%LYFW2 UZ, @6Fe ,NEip ֘(4&' zڐfXG-*p0C#zvhlT1k2l mL}H0pSn<ҘY' %><<ah&z5cg1c6Gli5`+ k jc.P+4S},)ӳ Xm+P"N{5*@;BI48@sUA`v"kep]ﬢyvT[zQׂP ;wGǧ/q *SOd̀yp8)A^ .inUB"e4MlQs?(r!洌aސLnQG]jP¤F<5ơL+9W2X4E!@# C3 $q@+%I &{cy<8k q@y7`d<P2RӺPCYyf B}[h_ dz:Hh]m#Js'QoZҊ0e 뤜lA 2)\ V%Z"U]G6n`%?4ⳅ#B ϐ{`–bHg' YG9ZB.T@Pej!7Xp4^|N ,尩D~̣H! 6ޥr;?!Պj]r!fSFqa hO0_.}uxT#~kVkA$c^v3{G׫A81BGqW-rv[Sly[B!yW@?ml*XavKbFc8Ib)~,"El!+ŷκY0 ])Da246 smǰy'DA B [vntS1@r*@-57['؜O}x79;mC۟ܠNvΒ1tSOɳ/˪kTI ̇5|xe'E =K|ƧWٖms:ꕪBqQco $ksj`;:6U1j Z]_X`h$M j$fɻ(<վМ& Pfr]˹l7;@#CC< lj{е!d~y)uպ٠I#/מEe"X룖fPCjG<h0ke_h.gŞbu_A}=c9tݑ^yv2gtr~1s%Syc\oW/q01?1]9,aI;\ooG^`|mb w WϷ]8W_3gm#Tk7I QԪ}_d|ErA <\U3ʽtpV7u X?;ÜyYX?o1liZSHClК':e4K,*7Ljg(ɐvLˑN11133V2FIY&,:pk{9bDi$r} )lj}nO¼l:&P4YH6SBӘ@a [_!VcIơ]nkz8~0,_%6Xng;8e,8I'źڽ2bf/d(hu 6&F &̨O 8畈d^^n3'\"JΓu)lbwJMcRN`b%[/qmܨ гHfEgY'$~t3c-L|foBq57O-qV%aHYwFq&. ]y WʰKw%2gPTBZ~s9tNVP6Z"2АSc6J! P˨5 \Rc6_is9JJn0CNIq;h68C}{rԦi󐜏H㥭_y3s 3yfV)b ϱ6y/x33ɲ{a萵/rlR0h&`X)ڹIZ}WPŸ3ǁWOG/U8,8QLzgѷzP5%FhٽٙAwknY=, Volume 58, No. 29