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 that Grace uses to draw on.  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 it could focus on just enhancing the graphical capabilities themselves.  Performance may be a limiting issue. 
    Last year a team of students created graphix, an interface to the CreateJS libraries, which provide much nicer garphics with a simpler and more-oo inetrface.  Unfrotunatley, 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 grahics is a prerequisite.

  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. Visual Test Runner.  We have the gUnit testing framework for Grace, and the dialect minitest 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. 

  4. Performance Monitor.  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(n2), 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.  It would also help us in the next task.

  5. Performance Improvement. The current (self-hosting) implementation of Grace is slow enough that students notice that their 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 peformed by the V8 JIT.  Doing so would significantly improve the student experience,  and make it more likely that Grace be widely adopted.

  6. Efficient Dynamic Type-checking.  Grace's current dynamic type-checker is slow, because it repeatedly re-checks the same object against the same type.  There is only a bounded number of different types of object in a Grace program — it’s bounded by the number of object constructors and classes) in the source.  There is also only a bounded number of type expressions.  Most type checks at a given place in the code are comparing an object that was created by the same object constructor as on the previous attempt!  So, caching the results of type checks is an obvious approach to speeding them up.
    This project will involve mostly JavaScript programming in the minigrace runtime support library.

  7. Static type-checking.  The static type-checker is at present quite limited.  The basic type-checking algorithms work, I believe, but the software enginering to integrate it with the module system and the standard prelude remains to be done.  Gradual typing remains to be done, too.

  8. A Series of Dialects.  Research in learning has shown that it is beneficial for students to start programming in a restricted language, and then shift to more comprehensive languages as their skills develop.
    Indeed, this is the motivation behind some of the educational mini-languages like Logo and Scratch.  However, the problem with starting teaching in a mini-language is that switching to a real language is disruptive: students may see it as “starting over”, even though the students are in fact building on a base of acquired skills.  Felleisen, Findler, and colleagues solved this problem in DrScheme (now DrRacket) by defining a series of increasingly powerful languages, through which students can progress without having to “unlearn” anything that they have already mastered.  Grace implements this idea with its dialect mechanism.
    A Grace dialect can extend the language by adding new libraries, restrict access to the features of the base language, and customize error messages to the students' level of knowledge.
    We have defined a few sample dialects, including a Logo-like dialect,  a dialect that enforces static types, and a simple testing dialect, but we do not yet have a series of dialects for teaching an introductory course.
    This project might involve designing and implementing a sequence of dialects that supports my personal teaching preferences — so I would be your customer — or improving the staticTypes dialect to make it more functional.

  9. A regular-expresson library for Grace.  As some students noted while working on the lexer, it would sometimes be convenient to be able to use match(_)case(_)… with regualr expressions.  It's possible to define patterns in Grace, so this could, at least in principle, all be done as a library.

  10. 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.   Bulding a couple of converters “by hand” would probably help the team figure out exactly what it needs to do.

  11. 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.

  12. 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, it stores Grace methods in a methods object attached to the JS representation of each Grace object.  This means that Grace method request has to search through these methods objects in the receiver, and in its superobject, and so on.  I believe that it is possible to devise a better representation for Grace objects so that Grace method request could use JavaScript method dispatch directly, and the JavaScript prototype chain instead of explicit superobjects.   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.

  13. Minigrace lexer.  Extend the lexer that you staretd writing in assignment 2 so that it lexes the whole Grace language, and interfaces with the minigrace parser.  Interpolated strings may be the most complex part.

  14. Minigrace compiler cleanupminigrace's parser code generators are 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, and also eliminating some of the bugs that we have seen during the quarter.   The code generators are 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.

  15. Exytended 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 priority queues, multisets and multi-dictionaries, bi-directional dictionaries, and their immutable variants.

  16. 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 alows 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, and (possibly) for C too.

  17. Enhance Grace's Web-based Programming Environment. The ideal programming environment for Grace will be simple to use, produce excellent error-messages, and will  capture all versions of the 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.  It should also support simple refactorings like renaming, and show variable bindings graphically.

    The current environment is simple, and the error messages aren’t bad, but it lacks many of the above features.  It's written in JavaScript, an object-based language that has a simple core but which is far from simple in its entirety.  Useful enhancements include adding folders to the client-side storage, and providing a way to re-upload a new version of an existing file, as well as downloading and re-uploading a zip archive containing all of the files in the environment.  It would also be nice to be able to customize the ACE editor used for code editing, for example, by adding buttons to insert characters like ⟦ and ⟧.

    Support for recursive compilation of imported modules would be useful.  At the command line, the compiler uses the timestamps on source and object code files to decide if a file needs to be recompiled; in the browser, there are no timestamps on localstorage, so some other method will be necessary.

    Support for renaming (across a group of files) and visualizing variable bindings would make a more significant project.

  18. 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.

  19. Grace Documentation Project.  Many programming langauges have dicsovered 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 form 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. 

    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 some existing tool — essentially, 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 previosu student project, but it needs updating to deal with changes in Grace’s syntax.




Most recently modified sometime in the past


Andrew P. Black