Extraordinary Ordinals

(text.marvinborner.de)

21 points | by marvinborner 2 days ago

7 comments

  • tromp 56 minutes ago
    The author presents most known numeral systems (ways of representing natural numbers) in lambda calculus, classified by whether the term use their bound variables exactly one time (linear), at most one time (affine), or multiple times (non-linear). Mackie's paper [0] (one of the references) provides a good introduction to these.

    He illustrates some numerals in each system with a graphical notation that strongly reminds me of interaction nets [1], a computational model closely related to lambda calculus. The notation they use for lambda terms is rather non-standard. Compare

    > In β-reduction, k[(x⇒b)←a]⊳k[b{a/x}]k[(x⇒b)←a]⊳k[b{a/x}]

    with Wikipedia's [2]

    > The β-reduction rule states that a β-redex, an application of the form (λx. t) s, reduces to the term t[x:=s].

    The k[...] part means that β-reduction steps can happen in arbitrary contexts.

    [0] https://www.researchgate.net/publication/323000057_Linear_Nu...

    [1] https://en.wikipedia.org/wiki/Interaction_nets

    [2] https://en.wikipedia.org/wiki/Lambda_calculus

  • Sharlin 19 minutes ago
    The author unfortunately only describes about half of the syntax they use, or rather, they describe the syntax of the language but assume the reader is familiar with the (rather obscure even in a PLT context) metalanguage.
  • lefra 1 hour ago
    I think I lack context to see what this is about. The line graphs are pretty though, and I'd like to understand more.
  • throwaway81523 50 minutes ago
    Hmm nice I guess, but I expected it was going to be about transfinite ordinals. I wonder if it can be extended to them.
  • p1esk 2 hours ago
    I didn’t understand that notation. Can someone please explain?
    • ngruhn 1 hour ago
      I think:

         x => a
      
      is:

         λx. a 
      
      and

         f <- a
      
      is just application. I.e.

         f a
      • lefra 1 hour ago
        What about big T, square/angle brackets, and braces?
        • ngruhn 1 hour ago
          yeah no idea
    • jdw64 20 minutes ago
      const f = (x) => x + 1;
  • bananaflag 1 hour ago
    This should be "numerals"
  • dnnddidiej 59 minutes ago
    This is beautiful art