GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — GitHub - ldb/lambda: An implementation of the untyped Lambda Calculus.

BranchesTags
Open more actions menu

Latest commit

 

History

14 Commits
14 Commits

Folders and files

NameName
Last commit message
Last commit date
ast
ast
 
 
cmd
cmd
 
 
eval
eval
 
 
lexer
lexer
 
 
parser
parser
 
 
repl
repl
 
 
testutil
testutil
 
 
token
token
 
 
wasm
wasm
 
 
.gitignore
.gitignore
 
 
go.mod
go.mod
 
 
go.sum
go.sum
 
 
readme.md
readme.md
 
 

Repository files navigation

lambda

lambda is an implementation of the untyped Lambda Calculus.

The Lambda calculus

"The Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution."

Grammar

The grammar for the untyped Lambda calculus is fairly simple. Here it is in EBNF:

variable    = "v" | variable, "'";
application = term, " ", term;
abstraction = "λ", letter, ".", term;
term        = variable | "(", application, ")" | "(", abstraction, ")";

Examples for valid terms ("lambda-terms"):

v
(v v')
(λv.v)
(λv.(v v')
((λv.((λv''.(v'' v')) v)) v''')

The lambda language

Grammar

We make some small changes to the lambda calculus' grammar for our convenience:

First, we replace the variable rule by the following one:

variable = "a" | "b" | ... | "z";

While the original rule technically allowed for an infinite number of variables, we very likely won't run into issues limiting ourselves to just 26 variable names.

Secondly, we add a rule to allow omitting the outermost parentheses:

lambdaterm  = variable | application | abstraction | term;

Now, we make a small change to the abstraction rule:

abstraction = "\", letter, "." , ( abstraction | term );

This is allows us to write nested abstractions more easily, without having to use many parentheses, for example λx.λy.(x y).

Finally, also substitute the λ symbol for \ to make it easier to type.

As a result, these are also valid terms in lambda:

x y
\x.x
\x.(x y)
(x y) (x y)
\x.\y.(x y)

The final grammar now looks like this:

variable    = "a" | "b" | ... | "z";
application = term, " ", term;
abstraction = "\", letter, "." , ( abstraction | term );
term        = variable | "(", application, ")" | "(", abstraction, ")";
lambdaterm  = variable | application | abstraction | term;

About

An implementation of the untyped Lambda Calculus.

Resources

Readme
Activity

Stars

4 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.