CS 420/520 Project Suggestions

Here are some suggestions for projects.  They mostly involve improving the minigrace implementation in some useful way, because that's where my current interests lie.   You can also make a proposal based on  your own ideas.

1. Better Graphics.  As you know, Grace's graphics capabilities are limited, in two ways.  First, they don't allow much in the way of graphical operations, like scaling or rotation, even though these are supported by the HTML5 Canvas on which Grace draws.  Second, they are not very object-oriented, for example, they don't allow one to compose graphical objects out of simpler graphical objects; mouse clicks are not sent to the object under the mouse, and so on.  This project could focus on designing a nice OO graphics interface, perhaps based on the Morphic graphics system developed for Self and Smalltalk, or anothre OO graphics library.  Alternatively,  it could focus on just enhancing the graphical capabilities themselves.
   In a prior year,  a team of students created graphix, an interface to the CreateJS libraries, which provide much nicer graphics with a simpler and more-OO interface.  Unfortunately, it's not quite complete, and there are issues with using it in a separate window.  Solving these problems would be a very useful contribution.  A working knowledge of HTML5 graphics, or willingness to learn, is a prerequisite for this project.
   
   
2. A previous undergraduate project implemented a simple Omniscient Debugger for Grace.  (An omniscient debugger lets one move backward as well as forward in time; see the linked paper.)  In addition to stepping, it allows one to inspect variables.  It runs (sort of) in an older web IDE, but needs to be integrated into the current programming environment, and made more sophisticated.  The goal is to support novice learning rather than debugging "real world" programs; being able to see objects react to requests is a powerful learning aid.
   
   
3. Improve the Grace IDE.  As you know, the Grace IDE runs in a web browser.  It's written in JavaScript, and uses WebWorkers to run the compiler in the background.  The "folders" you see in the web file system and the automatic conversion of -> into → etc are the results of previous student work.  Possible enhancements include:
   

   • Simple refactorings like renaming; renaming across multiple modules is more significant.
     
   • Showing variable bindings graphically (Dr Racket does this)
   • Remembering the state of folders (open or closed)
   • Clone and commit from github
   • Direct submission to D2L
   • With the user's permission, capturing all versions of the user's program for later analysis, so that we can see if some miss-feature of the Grace language or compiler is getting in the way of student success
   • Automatically compiling imported modules as necessary
     

4. Visual Test Runner.  We have the gUnit testing framework for Grace, and the dialects minitest and minispec that supports simple inline tests for novices who have not yet learned about inheritance. 
   To promote Test Driven Development, I would like these to be integrated into the Web IDE, so that a student can run a test suite at the click of a button.  It would be nice to show the status of all modules loaded into the IDE (are the tests are red or green?),  and to focus the IDE on a failing test.  This would make it easier to introduce testing early in an introductory course. 
   
   
5. Performance Monitoring.  Modern computers give us the freedom to focus on clarity of expression in student programs, rather than on minimizing execution time.   However, once students start processing real-world data, execution time starts to matter.   For example, one of the assignments in my introductory programming course was analyzing books for authorship. This should be an O(n) task; some carelessly-written programs made it O(n²), and thus appeared to run forever!   Of course, we can explain the problem to the student, but a performance monitor that will let the student see this problem for themselves would promote more effective learning. 
   
   A simple performance-measurement module would be a good place to start. (Note that the measurement facilities offered by JavaScript in the web browser are different from those offered by node.js at the command line.)   Generating instrumented code would permit automated profiling.   Visualizing the results of a performance monitor is a significant project all by itself.
   
   
6. Performance Improvement. The current (self-hosting) implementation of Grace is slow enough that students notice that larger programs take a long time to build.   While minigrace will probably never evolve into a high-performance compiler, I believe that its current performance could be improved by a factor of 10, by generating JavaScript that takes advantage of the optimizations already performed by the V8 JIT.  Doing so would significantly improve the student experience,  and make it more likely that Grace be widely adopted.  The first step in this project would be finding out where Grace programs spend most of their time, which would involve JavaScript profiling.
   
   
7. Static type-checking.  The static type-checker is at present quite limited.  The basic type-checking algorithms work, I believe, but the software engineering to integrate it with the module system and the standard prelude remains to be done.  Gradual typing remains to be done, too.  This would involve coordinating with Prof. Bruce at Pomona College, who is the type-checking expert, and who has written the existing type-checker.
   
   
8. A regular-expresson library for Grace.  Past students have noted that it would sometimes be convenient to be able to use match(_)case(_)... with regular expressions.  It's possible to define patterns in Grace, so this could, at least in principle, all be done as a library.  A knowledge of the relevant theory of DFAs, NFAs, and regular languages would be an advantage.
   
   
9. Connecting to External Libraries.  Students interested in endangered species, melting glaciers, fish harvests, indie music, art, earthquakes, or weather patterns, all know that there is data "out there" on the Internet. We would like them to be able to use Grace to pull-down and analyze that data, which means providing more extensive libraries. 
   Fortunately, this does not mean reproducing all of the libraries available in other languages; all that we need do is build a relatively simple converter that allows a Grace program to access a "foreign" library.  We have already done this for some domains, such as accessing web pages, drawing graphics and creating animations.  I would like to increase the versatility of Grace as a teaching tool by creating more libraries;  HTML audio is an obvious candidate.  In the long term, I would like a tool that constructs the converters, given a description of the interface of the foreign tool, and the desired interface of the Grace library.   Building a couple of converters "by hand" would probably help the team figure out exactly what needs to be done; automating the process would probably be a follow-on project.
   
   
10. JVM code generator.  There are two code generators for the minigrace compiler: one generates C, and the other JavaScript.  For many reasons, JVM-code would be a better target: the JVM is universally available, support concurrent processes, and, with the advent of the invoke dynamic instruction, can support dynamically-typed languages.  This project would involve emitting JVM byte codes from the existing abstract syntax tree for Grace.
    
    
11. Better JavaScript from minigrace. The current JavaScript code generator doesn't do a very good job of taking advantage of the features of JavaScript.  In particular, the JavaScript object corresponding to each Grace object has its own methods, whereas many of these methods could be shared with object Grace objects generated form the same object constructor or class.  (They can't all be hared, because Grace methods close over their context).  It may also be possible to use JavaScript method dispatch directly, rather than using a request function as at present.  This project would be a good one for a student who already knows Javascript, or who wants to learn about prototype-based inheritance.  The deliverables need not necessarily include a full-function code generator,  but instead a paper design and a prototype generator that works on a few dozen examples.
    
    
12. Minigrace compiler cleanup.  minigrace's code generator is a bit of an embarrassment.  This project would involve applying the lessons of OO-design that we have studied this quarter and creating better structured code.  The code generator is rife with class tests, which could be removed either by modularizing the code differently or by using the visitor pattern consistently.  The new code would need to be integrated back into the minigrace source pool.  The goal here is to produce a better-structured compiler that is no slower than the current one.
    


13. Extended collection Libraries for Grace.  The basic collection libraries include mutable sets and dictionaries, and immutable sequences, but no efficient immutable data structures using trees.  We can do better, perhaps by borrowing the interfaces from Google's Guava libraries.  Possible candidates are matrices, priority queues, multisets and multi-dictionaries, bi-directional dictionaries, and their immutable variants.
    
    
14. Grace reflection interface.  We do not have a design or an implementation for Grace's reflection interface.  There is a module "mirrors" (should be singular!) that allows one to ask about the names of the methods defined on an object, and their arguments, and to request one of these methods, but this is hardly adequate.  It should also be possible to ask what fields are defined, which methods are confidential, what annotations are present, what the source code looks like, and so on.  The information to answer these questions is available, but there is no interface to access it.  This project would involve defining an interface to access such meta-information, and implementing it for JavaScript.
    
    
15. Grace in your favorite programming environment.  Others have built good programming environments designed for educational programming:  Smalltalk, Dr Racket and BlueJ are examples.  I'm not sure whether Eclipse, NetBeans, Visual Studio, etc qualify as being suitable for novice users, but there is a clear argument in favour of integrating Grace into an existing environment rather than "starting over" building our own. This project would probably be a feasibility study for a follow-on project that would actually do the implementation, so I'm hesitant to suggest it for this class, since a project for CS420/520 really needs a programming component, but if you already know a lot about a particular IDE, this might be feasible.
    
    
16. Grace Documentation Project.  Many programming languages have discovered that documentation is most likely to be kept up to date it it is included as comments in the source code.  But then there needs to be a tool that extracts the docmentation for the source, and displays it in a nice format, usually as a web page, sometimes also as LaTeX source that can be compiled into a PDF document.  Java, Haskell, Python, Node, and even Nim have such tools.   Having documentation available in such a form also makes it relatively simple to access from within the programming environment.  For example, in IDLE, a simple Python environment, the documentation for a function is displayed (after a short pause) when one types the open parenthesis of a call of that function.
    
    Since it makes sense to reuse existing tools rather than creating a new one, much of this project will be concerned with setting conventions for documenting Grace, extracting the documentation from the source, and translating it to the right input format for Jekyl &emdash; the tool used to build Grace's documentation site.  Essentially, this is a parsing problem.  It will also involve some background research understanding the workflow for an existing tool, and some work documenting the existing source of a few sample modules.  There is a graceDoc module, which resulted from a previous student project, but it needs updating to deal with changes in Grace's syntax.