Wiki
Clone wikiinf225 / 2017 / Term Project
Purpose
-
Learn – Gain extra insight into something that interests you.
-
Do – Get (good or bad) hands-on experience with tools.
-
Share some of your new insight with the other students.
Grading
At the final exam, you will be asked to show stuff from your term project, and reflect on what you've learned and the choices you made.
Time Frame
- Until Friday, November 11th: Think about what to do, try to decide on something, get started
-
Make a decision together with Anya, either in person or via email/facebook (more likely, due to travelling).
-
November/early December: Working. If Anya hasn't given you a paper or book chapter to read, nag her until you get it.
-
Check in with Anya and/or Anna for advice and follow up every week.
-
Finish some time around December 10th, so you have time left over to study for the exam and other exams. You should expect to have a prototype at least two weeks before the exam, which will be some time in December (we'll make Doodle and pick a date that suits everyone).
-
Do a short show-and-tell to the other students. You don't have to have your whole stuff finished to do this, just show an interesting aspect, or some insight about the technology you're using.
-
You can work on your project until the week of the exam, though you should have a prototype ready before then.
Organisation
The project is individual, but with a certain level of cooperation allowed. For example, a small group could work on the same language, but deal with different components of the implementation. Discussion is OK. Again, the purpose is to learn something. (You should of course be prepared to explain any part of your own code and design. Normal rules for copying/plagiarism/cheating apply, as always.)
You select what project to work on and what technology to use – though you should get it approved by Anya before you start. Obviously, it needs to be relevant for the course.
Technology Choices
-
You choose! (within reason)
-
Nice if several similar project use different technologies
Typical choices:
-
Plain Java, handwritten recursive-descent parser
-
ANTLR+Java, [some parser tech]+Java – ANTLR is particularly popular in mainstream language implementation
-
Transformation languages: Stratego/XT, TXL, ASF+SDF, Elan, Tom, ...
-
Xtext (popular on the interwebs)
Project Ideas
0. Particular Project Ideas
(Based on Anya's and Anna's current hobby research ideas.)
-
Web-based syntax/grammar explorer: create a web app that lets a user explore grammars and parse trees. E.g., upload/enter a grammar and a text, visualise the parse trees and link it back to the text and the grammar. Anya has code that can build parsers and give access to a serialized representation (e.g., JSON) of grammars and parse trees and such.
-
Generate API usage info from Java code. You can load class files and examine what method calls they make (Anya has code you can start with). The idea would be to (perhaps later) see how API usage changes over time.
-
Visualise a (virtual) machine, with a graph for the instructions and the objects in memory, so students can learn what happens in a computer while a program executes.
-
Make a small visual language where you can draw objects and attach code to them. (Dan Ingalls is working on a system like this: Lively.)
-
Use the Java debugging interface to connect to a running Java program, and "audialize" its execution.
1. Programming Language Implementation
Implement (and design) a programming language. (This is the classic INF225 project; Lisp/Scheme is particularly easy.)
-
Functional
- make an evaluator or compiler
- should have anonymous functions / lambdas and closures
- algebraic data types
- REPL (read-eval-print-loop)
- Fairly easy to implement. A pure function version of Scheme (or other Lisp-like languages) is particularly easy
-
Imperative
- make a compiler (to JVM/C/Java/ARM/i386/68000/Z80/6502/Analytical Engine...)
- static typing / typechecker
- structure types
- optimizer, perhaps?
- You can find tutorials for this on the net; also, most compiler books have a simple imperative language used as an example. Tiger (from Appel's book) is particularly common and well-suited as a small implementation project.
-
Dynamic
- make an evaluator (typically)
- REPL
- dynamic typing, no typechecker
- could be functional or imperative or combination
For a trivial design, you can do everything yourself. With a more sophisticated language, it makes sense to split the work into neat chunks. For example:
- Frontend (grammar, parser, typechecker)
- Optimizer (work on some intermediate representation)
- Backend (generate code from the intermediate representation)
- Garbage collector (particularly useful for functional and/or dynamic langs)
- IDE / infrastructure (simple IDE stuff is easy to do in Rascal)
- Implement automated refactorings
- Dataflow analysis – can be used for various cool stuff, such as:
If multiple groups / persons work on the same or similar languages, it would be nice to use different technologies and see how the experiences differ.
2. Make a Domain-Specific Language (DSL)
- Make an evaluator or a compiler (typically to a high-level language)
- Or, embed the DSL in a language such as Haskell, Scala or Racket
DSL Ideas
- 3D printing (not sure how this would work)
- Graph/tree algorithms. For example; check out Nuthatch – a Java library for tree traversal that's just waiting for someone to make a nice DSL frontend for it.
- DSL for programming lunar landers
3. Tree Walking
-
Implement something useful (refactoring? optimisation? analysis? using Nuthatch
-
You can pick up a paper about this on the shelf outside Anya's office.
-
Participate in actual research. No one knows how this approach works out in practice – your case study can help.
4. Code Formatting
-
Take messy code as input, produce beautiful formatted code
-
Maybe use the PGF framework (project page not filled in yet...)
-
You can pick up a paper about this on the shelf outside Anya's office.
-
Compare with other formatters, see how good yours is.
-
Participate in actual research. No one knows how this approach works out in practice – your case study can help.
5. Language Specification
-
Formalise the semantics of a language (perhaps a language someone else is implementing?)
-
You can use Prolog to make an executable specification. This could then be used to test the implementations (if someone has made an implementation).
Resources
Backend / Code Generation
Assembly Programming
- Programming from the Ground Up (PDF) by Jonathan Bartlett
- Specific architectures:
- ARM (as seen on phones, Raspberry Pi, etc): see below
- JVM: see below
- Atmel AVR (as seen on Arduino etc): Beginners Introduction to the Assembly Language of ATMEL-AVR-Microprocessors by Gerhard Schmidt
- x86-64: Introduction to X86-64 Assembly for Compiler Writers by Douglas Thain
ARM Architecture
- Introduction to ARM Assembly Language
- ARM: Assembly Language Programming (pdf)
- ARM assembler in Raspberry Pi
JVM
- JVM Compilation Basics
- ASM Java Bytecode Manipulation and Analysis Library
- The Byte Code Engineering Library
- Introduction to JVM Internals and Garbage Collection (slides)
- Code Generation on the JVM (video)
Semantics
-
Specification of YAFPL in Prolog – syntax and (small-step/big-step/denotational) semantics of a tiny functional language
-
Grigore Rosu's lecture notes Particularly the first four sections.
JIT Compilation
- How to JIT – An introduction (for native code)
- Hello, JIT World: The Joy of Simple JITs (for native code)
- Getting started with libjit
- ASM – Java Bytecode Framework (for JVM)
- Byte Code Engineering Library (for JVM)
Projects from 2013
-
@emaziz: A traditional imperative-style language implemented in Visual C++. Interpreter-based
-
@ahjortland: Hand-written parser and compiler; hopefully with user-defined rewrite rules for optimisation.
-
@sowhow: Language specification in Prolog.
-
@antonlindstrom: Implementing a Language with LLVM
-
@bbuanes: Implementing Befunge in different languages.
-
JP Indrøy: The possible use of domain specific languages as indicators for join points in tree walking, using Nuthatch/J.
-
@Guildenstern : Stack Lang – A stack based Forth-like language with interactive evaluator in Haskell.
-
@skoging: Java formatting in PGF
-
@trippler: Code formatting in C
-
@patmon and @mockillo : Scripted Offline Fighting Arena (SOFA). A DSL to control characters in a top-down view RPG simulation. Technologies: Xtext, ANTLR, libGDX, Java
-
@poglesbyg: Implementing Lisp/Scheme in Lisp/Scheme
-
@swi083: JSONfunc
Updated