Wiki
Clone wikiinf225 / Home
Welcome to INF225!
This is the Wiki for the INF225 course at the University of Bergen (Fall 2017). Previous editions: 2013 2016
Notes
- Complete notes in PDF (to be updated)
- Appendix A: Glossary [wiki, tags]
- Flash cards with many of the glossary entries
Things you should know
(for the exam...) Ch. X refers to the PDF file with lecture notes
Concepts
- Languages (Ch. 0–1): formal languages – software languages – programming languages (general-purpose, domain-specific) – modelling languages – data languages – APIs
- software languages; general-purpose (can may new abstraction to fit your purpose) vs domain-specific languages (already has good abstractions for a particular purpose)
- Syntax and grammars (Ch. 1): regular and context-free – limits of regular and context-free grammars – terminals, non-terminals, productions
- BNF style grammars, regular expressions
- Dealing with priorities and associativity (mainly by declaring it in the grammar formalism, rather than encoding it as grammar productions)
- Full Context-Free Grammars (as with Rascal's generalised parsing) can have ambiguities
- Restricted grammars (e.g., LALR) may not be composable, and can require tricks to encode the syntax
- Trees: parse tree vs. abstract syntax trees
- Semantics:
- (Ch. 2) scoping – environments – dynamic vs lexical/static scoping
- (Ch. 3) static semantics, name binding, type checking
- (Ch. 2) dynamic semantics – evaluation, compilation
- closures -- function bundled with context information
- Types and type systems (Ch. 3):
- static vs dynamic typing
- what is a type?
- Abstract view: a type tells you how something can be used – i.e., syntax: which functions/operators can be called, which variables can take what values etc
- Concrete view: a type tells you about memory layout, implementation details (where to find method code)
- Set view: a type is a set of values
- By-example view: a type is an example of something. E.g. objects in JavaScript are made by cloning prototypes that are also objects (examples); Smalltalk works this way; in Biology, taxonomy also works similar to this way: e.g., type specimen of Homo sapiens, type specimen (holotype) of T. rex (though, in biology, the type specimen is typically not the “prototype” (i.e., ancestor) of all members of the species, just a representative that is defined to be of the the species (and biologists may argue about the species (“type“) of other individuals)).
- Execution model:
- computing with immutable variables / pure functional; rebindable variables; with memory/store
- memory model – typical address space layout
- call stack – stack frame
- three-address code (rough idea), code generation
- Overall compilation process
Skills
- Write, work with, test and debug
- grammars (Ch. 1, Ex. 1, 2, 3)
- simple evaluators and typecheckers
- (in Rascal, or in any language you're familiar with)
- Dealing with context: passing around environments
- Tree traversal: recursive
Optional
- Simple data-flow analysis
Lectures
- 1 (22.8): Introduction to software language engineering
- 2 (29.8): Syntax, parse trees and abstract syntax trees
- 3 (30.8): Overview of language processing – syntax / parsing, semantics / semantic analysis, translation
- 4,5 (5–6.9): Syntax and grammars: production rules, regular grammar operators, priority/associativity/disambiguation operators
- 6,7 (12–13.9): Grammars and parsing in practice; working with parse trees in Rascal
- 8,9 (19–20.9): Evaluation of programs
- 10,11 (26–27.9): Working with environments and context – name binding
- 12,13 (3–4.10): Type checking, name binding and semantic analysis
- 14,15 (10–11.10): Store vs value – machines, memory layout
- 24–25.10: SPLASH'17 / SLE'17 no lectures/labs**
- Type systems
- Closures, classes and objects
- Pattern matching
- Analysing code – data-flow – slicing
- 21–22.11: Anya travelling
- Refactoring (slides)
Exercises
- Exercise 1 – Regular expressions and grammars
- Exercise 2 – Grammars and parsing
- Exercise 3 – Processing JSON data (please complete by 2017-10-03)
- Exercise 4 – not released yet (2016 version)
Term Project
- There will be a term project. You will be able to choose what to work on (within guidelines) and which technologies to use. Decide on the project and start working by the end of October. You will be expected to present / report on your progress in November. The final deadline will be the week of the exam (you will be asked about the project on the exam).
Practical Help
Links
Updated