Typically, OCaml and Scala seem to be used for designing any programming languages tool. But what features offer them an edge over other languages.

A related question, is a type system for a language always written in the native language itself?


OCaml and Scala are popular choices for types systems, but they are by no means the only languages you can write a compiler, interpreter, typechecker, or type system in.

Type-checking involves traversing syntax trees representing terms and types. Languages with some form of algebraic data type make this easy, since these traversals can be defined using pattern-matching . In an object oriented language, these traversals have to be done using a Vistor pattern, which ends up using much more boilerplate. Languages like Haskell can use techniques like monads or datatype-generic programming to abstract away even more of the boilerplate of these traversals.

Also, functional programming languages tend to be closer to the lambda calculus and the other formalizations of programming languages. Since programming language researchers are often the ones developing both these formalizations and the implementations, so it makes sense that they'll be more comfortable in languages like these.

It's worth mentioning that a some work has been put into developing other ways to declaratively specify type systems for languages. For example:

  • Turnstile is a Racket DSL that lets you develop type systems in a form that looks a lot like formal inference rules.
  • Spoofax is a toolkit for writing programming languages, that can generate a typechecker with IDE integration from a specification.

A related question, is a type system for a language always written in the native language itself?

Certainly not! It's popular for writers to implement a language in the language itself, (often called "self hosting"). If you're writing a programming language, then there's a good chance that it's been designed to solve problems that whoever was writing the language had. So whoever is designing the language probably finds it a pleasant language to use.

But for performance reasons, often languages are implemented lower-level languages like C or Rust. This is particularly important for interpreted languages: if you write your interpreted language in another interpreted language, then interpreting code involves running your interpreter in yet another interpreter, which is a lot of indirection that hurts performance.

  • $\begingroup$ If we are extending an existing language’s type systems, is it recommended to implement it in the current compiler’s language? Is there a way to combine this extended type system in a functional language with a compiler in an imperative language? $\endgroup$ – mythbuster Nov 11 '20 at 20:09
  • $\begingroup$ @mythbuster what do you mean by "extending an existing language's type system?" Are you "forking" a compiler to make a new type system? What kind of extension do you mean? As for functional vs imperative, there is no technical reason you cannot implement a functional language with an imperative one or vice versa. It's just a matter of what is easy and what requires the least boilerplate. Basically, people us functional languages not because they have to, but because they want to. $\endgroup$ – jmite Nov 11 '20 at 21:30
  • $\begingroup$ I’m talking about forking a compiler and then adding a new type system. Here do I need to use the same language as the compiler for implementation? $\endgroup$ – mythbuster Nov 12 '20 at 0:42
  • $\begingroup$ You don't have to, but it's much easier if you do. One way to think of a type system is as a "filter": it reads a program, and either passes it on to the translating part of the compiler, or it fails with a type error message. So in principle, you can write your filter in any language you want, provided you interface with the rest of the compiler in some way (FFI? external process?). It's a bit more complicated in cases where the code generation depends on typing information coming from your type system i.e. if you have any form of type inference that guides compilation. $\endgroup$ – jmite Nov 12 '20 at 3:39
  • $\begingroup$ @mythbuster Extending a type system is not a trivial task. Learning the language that the compiler is implemented in is likely to be significantly less work than trying to patch together your own extension in a different language. If you're not comfortable enough with different languages to be able to write in whatever language the compiler is implemented in, you're probably not going to be comfortable enough with programming languages to be writing your own type system. $\endgroup$ – jmite Nov 12 '20 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.