Wiki
Clone wikiinf225public / 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 exam, you will/may be asked to show stuff from your term project, and reflect on what you've learned and the choices you made.
List of criteria TBD.
Time Frame
-
Until Thursday, Oct 24: Think about what to do, try to decide on something
-
Make a decision together with Anya, either in person or via email. Anya is available Wed, Oct 23 and Thu Oct 24. Otherwise, she's travelling until Nov 4.
-
Oct 28: Start 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 Naim for advice and follow up every week.
-
Finish by end of November. You should expect to have a prototype at least two weeks before the exam, which will be some time in the beginning of December.
-
Do a short show-and-tell to the other students some time in November. 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.
-
Deadline to be announced – depends a bit on the exam date.
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
-
Transformation languages: Stratego/XT, TXL, ASF+SDF, Elan, Tom, ...
-
Xtext (popular on the interwebs)
Project Ideas
1. Programming Language Implementation
Implement (and design) a programming language.
-
Functional
- make an evaluator or compiler
- should have anonymous functions / lambdas and closures (from Ex. 4B)
- algebraic data types
- REPL (read-eval-print-loop)
-
Imperative
- make a compiler (to JVM/C/Java/ARM/i386/68000/Z80/6502/Analytical Engine...)
- static typing / typechecker
- structure types
- optimizer, perhaps?
-
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 (avoid if possible)
- Implement automated refactorings
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).
Projects In-Progress
-
@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
Resources
Backend / Code Generation
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)
Updated