Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Cool stuff! How do I decipher the symbols that make up the equations for "application" and "abstraction"?


The definition I gave at the end of the article (the thing starting with `t ::=`) is basically a context-free grammar describing the syntax for terms of the calculus of constructions.

`t ::= ...` is saying "A CoC term, called t, can have the following forms ..." Then each case is separated by `|`.

The cases for application, abstraction, and forall are recursive, in that they contain t (or t') when the thing being defined is also called t. (The prime on t' is just to say that t and t' can be different terms.)

So for instance, the case for application is:

t(t')

That means if you already have two arbitrary CoC terms, called t and t', then if you write down first the term t, then a `(`, then the term t', then a `)`, then you've written down another CoC term representing the application of the term t to the term t'.

And the case for abstraction is

λ(x:t) t'

That means if you have two CoC terms t and t', then if you write down `λ`, then `(`, then a variable name (x is kind of a meta-variable-placeholder name, you can name the variable whatever you want), then `:`, then the term t, then `)`, then the term t', then you've written down an abstraction term. In this case, the variable x (or whatever you called it) has type t, and can appear free in t'.


Awesome, thank you for the thorough explanation!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: