4

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$ is context-free (indeed, regular). The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; ...


3

This paper is my go-to for implementing dependent types. It starts from the basics, uses bidirectional types, and has accompanying code in Haskell. If you're at all interested in type inference, this paper is great, and also has accompanying Haskell code. David Christiansen has a tutorial on dependent type checking with bidirectional types, with a Haskell ...


2

What is true randomness, and is it necessary? Algorithms cannot distinguish truly random bits from pseudorandom bits (by definition!), and so in practice we are only interested in generating strongly pseudorandom bits. As indicated above, true randomness ensures that even if we run the same algorithm twice, we get different results. True randomness is ...


2

Defining the grammar in terms of an abstract $id$ token allows you to write a context-free grammar for a language which would otherwise be context-sensitive, by dropping restrictions from the grammar. Something like FUNCDEF ::= 'func' ID '(' PARAMDEF ')' FUNCBODY and FUNCCALL ::= ID '(' ARGS ')' This is perfectly context-free, by simply treating the $id$ ...


2

The & operator is a bitwise "AND". Since the binary representation of 1 consists only of a 1 on the least significant bit, the operation c & 1 checks if $c$ contains a 1 on the least significant bit. Another way to say it is that c & 1 is the remainder of $c$ modulo 2, that is 0 if $c$ is even and 1 if $c$ is odd. The >> is a ...


2

There is no need to assign a number. The program already is a number. If you have $m$ opcodes and your program has $n$ instructions, then it can be interpreted as an $n$-"digit" number written in base $m$.


1

Every program that uses local variables can be converted to one that uses only global variables. So, the answer is trivially yes. However, it might not be pleasant for the software developer.


Only top voted, non community-wiki answers of a minimum length are eligible