Presentation (PDF)

File information

Title: Implementation Oriented Language Targeted Goto {((x.x x)(y.y y))} Guide:
Author: Roscoe S. Casita

This PDF 1.5 document has been generated by LaTeX with Beamer class version 3.33 / pdfTeX-1.40.15, and has been sent on on 02/12/2015 at 22:04, from IP address 157.245.x.x. The current document download page has been viewed 554 times.
File size: 970.77 KB (27 pages).
Privacy: public file

File preview

Implementation Oriented
Language Targeted
Goto {((λx.xx)(λy .yy ))} Guide:
Roscoe S. Casita
University of Oregon

December 2, 2015

λ Calculus to − calculate: One Axiom, One Reduction

Core Axiom: α non-naming equivalence: (λy .y y ) == (λx.x x)

Core Reduction: β replacement: Replace x with a is this operator

Identity Function = ((λx.x)a) ↓ (x)[a/x] ↓ (a)
Identity applied to identity = ((λx.x)(λy .y )) ⇒ (λy .y )
Infinite Loop = ((λy .y y )(λx.x x)) ⇒ ((λx.x x)(λx.x x))∞

Problem statement: Implement a λ expression evaluator
λ Calculus can model all computations, even evaluate itself.
Evaluate stepwise PRED(SUCC ZERO) ⇒ ZERO as test.
Interpret ((λx.xx)(λy .yy )) ... FOREVER!

Parser Generate : Grammar ⇒ lexical -parser
Parser Engine : lexical -parser + λ expression ⇒ parse-tree
Translater : parse-tree ⇒ expression-tree.
Interpreter : expression-tree ⇒ expression-tree until done.

Overview of the pipeline:
From text-strings to Data evaluating Data as Code:

Parser Generator: Add λ-grammar -definition-rules ⇒

Divergent directions...

Grammars are a language... thus a meta-language encoding exists

Let’s define a grammar that defines a grammar.

Let’s ensure the grammar definition can parse its OWN definition!


Parser Generator: Add λ-grammar -definition-rules ⇒

Pit Falls in “commonly repeated” λ-grammars:

<exp>::==<var> |(λ <var> . <exp>)|(<exp><exp>)

This is not an adequate grammar unless you LOVE lots of “()”

λx.λy .y (xx) must be written as (λx.(λy .((y (xx)))))

Nested variable capture is an advanced topic: λx.λy .x((λx.x)y )

Download Presentation

Presentation.pdf (PDF, 970.77 KB)

Download PDF

Share this file on social networks


Link to this page

Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)


Copy the following HTML code to share your document on a Website or Blog

QR Code to this page

QR Code link to PDF file Presentation.pdf

This file has been shared publicly by a user of PDF Archive.
Document ID: 0000318886.
Report illicit content