Course:CPSC312-2024/MiniLanguage

Authors: Jade, Inaki, Martin

What is the problem?

Prolog's declarative nature makes it an interesting tool for exploring and implementing a new (albeit small) language. Using the logical codebase provided by prolog, we plan on creating a language with simple syntax, largely based on that of Nix. We plan on handling:

• Numbers
• Math (infix notation)
  • e.g.

1 + 1

-> 2

• Lambdas
• 'let'/'in' bindings
  • e.g.

let x = 2; in x

-> 2

We will use the following grammar rules:

OP	:=	"+" | "-" | "/" | "*"
BINOP	:=	EXPR OP EXPR
DIGIT	:=	[0-9]
LETTER	:=	[a-zA-Z]
IDENTCHAR	:=	LETTER | DIGIT
IDENT	:=	IDENTCHAR+
LITERAL	:=	DIGIT+
BINDING	:=	IDENT "=" EXPR ";"
LET	:=	"let" BINDING* "in" EXPR
LAMBDA	:=	IDENT ":" EXPR
EXPR	:=	LET | LITERAL | LAMBDA | BINOP | IDENT

What is the something extra?

Our project's "something extra" entails the development of a parser for our custom language. This parser will serve as a crucial component in translating the code written in our language into a format that our interpreter can understand and execute. By incorporating a parser into our project, we aim to deepen our understanding of language design and implementation while providing 'users' with a seamless experience in writing and executing programs. We plan to research several parsing libraries to implement the parser efficiently. Effectively, this parser will not only enhance the functionality of our programming language but also showcase our ability to tackle advanced concepts beyond the basics covered in class.

What did we learn from doing this?

In creating a small language along with a parser using Prolog and its various functions, our group learned a lot about the capabilities of Prolog in such a task. As mentioned, Prolog's declarative nature seemed well suited to design a language, since languages are made up of simple rules that stack on top of each other. We ran into hurdles along the way, initially when we realized DCGs were the best tool for declaring such grammar rules. Similarly, when writing the parser we had to avoid infinite recursion by implementing rules such that precedence follows in the order that things are tried. Thus, since the left side of a binary operator will not try to evaluate the same rule again, we can avoid infinite recursion.

A major takeaway from this project is the power of pattern matching that Prolog provides. We had to gain a deeper understanding of Prolog's execution methods and priorities, and in doing so we got ourselves involved in the process of language creation in a practical way. Overall, this was a difficult learning experience, but we found Prolog and functional programming to be extremely well suited for the task of language declaration, evaluation, and parsing.

Work division

Work was divided mostly evenly; We all spent some time brainstorming the idea, and then resolved to work on different components. Once again, Martin updated the wiki continuously and implemented some of the language's syntax. Meanwhile Iñaki implemented some syntax for the language as well, and fleshed out the evaluator. Jade took upon herself the task of writing the parser for the language, extensively researching and diagnosing issues, while also debugging the evaluator. We all feel comfortable with each other as group members, as we communicated frequently and worked well together. The task of debugging and making the parser were more difficult so in the end Jade did some more work overall.

Links to code etc.

https://github.students.cs.ubc.ca/jadefink/cpsc312-group-2.git