AST ADT chicken egg problem

• AST algebraic syntax tree
• ADT algebraic data type

ADT modeling AST

Lambda calculus, it's variants, and
in general formal systems (core of many programming languages)
are usually specified in Bakus Naur form.
This is basically a specific algebraic data type (ADT) with both sum types and product types.
– sum type for the various options a term can take
– product types for the components a term must have

AST modeling ADT

Better programming languages need algebraic datatypes.
Even in basic untyped lambda calculus there are simple embeddings for sum types and product types.

The chicken egg problem

(wiki-TODO: Main point of the topic is still missing here)

Related

• Edit time immutability
• Lambda calculus encodings of algebraic data types

External links

• https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form
• https://mathoverflow.net/questions/151240/why-is-there-no-product-type-in-simply-typed-lambda-calculus