Difference between revisions of "Lambda Calculus"

From PKC
Jump to navigation Jump to search
(Created page with "Lambda calculus is a universal/Turing-complete language specification, that is considered to be mathematically elegant, due to its small size. Almost all text-based formal lan...")
 
 
(17 intermediate revisions by one other user not shown)
Line 1: Line 1:
Lambda calculus is a universal/Turing-complete language specification, that is considered to be mathematically elegant, due to its small size. Almost all text-based formal languages are defined using Lambda calculus.
Lambda calculus is a universal/Turing-complete language specification invented by [[Alonzo Church]], that is considered to be mathematically elegant, due to its small size. Almost all text-based formal languages are defined using Lambda calculus. To learn about its history, it is recommended to watch this video by [[Dana Scott]]<ref>{{:Video/Dana S. Scott Lambda Calculus, Then and Now}}</ref>.
 
[[wikipedia:Lambda calculus|Lambda calculus]] is a formal language that can serve as a foundation of all general purpose programming languages. It is also a kind of [[Universal Data Abstraction]]. Essentially, a lambda calculus is a recursively defined dictionary with just three branches of possible values.
 
{| class="wikitable"
|-
! Syntax !! Name !! Description
|-
| ''x'' || Variable || A character or string representing a parameter or mathematical/logical value.
|-
| (λ''x''.''M'') || Abstraction || Function definition (''M'' is a lambda term). The variable ''x'' becomes [[Free variables and bound variables|bound]] in the expression.
|-
| (''M'' ''N'') || Application || Applying a function to an argument. ''M'' and ''N'' are lambda terms.
|}
 
==Lambda Calculus expressed in Backus-Naur form==
 
=Relevant Learning Material=
 
A nice video<ref>{{:Video/Lambda Calculus - Computerphile}}</ref> tutorial by [[Hutton Graham]] is available. An interactive web page to illustrate the working process of [[Lambda calculus]] can be found here: [https://opendsa-server.cs.vt.edu/OpenDSA/Books/PL/html/Syntax.html Syntax of the Lambda Calculus]. A related language is called: [[Pi Calculus]].
 
<noinclude>
 
 
 
=References=
<references/>
 
==Related Pages==
[[Category:Programming Language]]
</noinclude>
 
 
 
=[[Lambda Calculus]] and [[Abstract Syntax Tree]]=
All decision making procedures can be represented into three major kinds of branching:
{{:Table/Representable Closure}}
# [[Naming Abstraction]]:[[Naming Abstraction|<math>\alpha</math> conversion]]
# [[Functional Abstraction]]:[[Functional Abstraction|<math>\beta</math> reduction]]
# [[Composition Abstraction]]:[[Composition Abstraction|<math>\gamma</math> reduction]]
 
These three types also relate to the reason why [[Kan Extension]] is universal. To understand the intricate mechanisms of [[Lambda calculus]], and why and how this simple language can be universal, please read this page:[[Dana Scott on Lambda Calculus]].
 
=Video Playlist=
* For people who wants to learn about Lambda Calculus, this video playlist<ref>[https://www.youtube.com/playlist?list=PLDjUBodUgvYOAkBEOszGH8R6WEw_vG0H_ Lambda Calculus Playlist on Youtube]</ref> would be very useful.


<noinclude>
<noinclude>
=References=
=References=
<references/>
<references/>
Line 12: Line 57:
[[Category:Monad]]  
[[Category:Monad]]  
[[Category:Lambda Calculus]]
[[Category:Lambda Calculus]]
[[Category:Gödel Number]]
</noinclude>
</noinclude>

Latest revision as of 18:44, 2 January 2023

Lambda calculus is a universal/Turing-complete language specification invented by Alonzo Church, that is considered to be mathematically elegant, due to its small size. Almost all text-based formal languages are defined using Lambda calculus. To learn about its history, it is recommended to watch this video by Dana Scott[1].

Lambda calculus is a formal language that can serve as a foundation of all general purpose programming languages. It is also a kind of Universal Data Abstraction. Essentially, a lambda calculus is a recursively defined dictionary with just three branches of possible values.

Syntax Name Description
x Variable A character or string representing a parameter or mathematical/logical value.
(λx.M) Abstraction Function definition (M is a lambda term). The variable x becomes bound in the expression.
(M N) Application Applying a function to an argument. M and N are lambda terms.

Lambda Calculus expressed in Backus-Naur form

Relevant Learning Material

A nice video[2] tutorial by Hutton Graham is available. An interactive web page to illustrate the working process of Lambda calculus can be found here: Syntax of the Lambda Calculus. A related language is called: Pi Calculus.



References

  1. ↑ Scott, Dana (Aug 24, 2012). Dana S. Scott Lambda Calculus, Then and Now. local page: princetonacademics. 
  2. ↑ Graham, Hutton (January 28, 2017). Lambda Calculus - Computerphile. local page: Computerphile. 

Related Pages



Lambda Calculus and Abstract Syntax Tree

All decision making procedures can be represented into three major kinds of branching:

A Table that Shows Representable Closure in Abstraction types
Technical Term Abstraction types Symbolic representation Description
-conversion Variable Naming abstraction A collection of symbols (names) that act as unique identifiers.
-reduction Substitution rule Function evaluations A template or executable function that can be reused in multiple contexts.
-composition Sequential composition Function composition The sequential/structural arrangements of known representable data.
  1. Naming Abstraction: conversion
  2. Functional Abstraction: reduction
  3. Composition Abstraction: reduction

These three types also relate to the reason why Kan Extension is universal. To understand the intricate mechanisms of Lambda calculus, and why and how this simple language can be universal, please read this page:Dana Scott on Lambda Calculus.

Video Playlist

  • For people who wants to learn about Lambda Calculus, this video playlist[1] would be very useful.


References

  1. ↑ Lambda Calculus Playlist on Youtube

Related Pages

D
J
L
P
Q
T
V
V cont.
V cont.

Retrieved from "https://pkc.pub/index.php?title=Lambda_Calculus&oldid=37351"