blob: 7d15dbfdbbf8548ce8f6a389285dee2aa83a2a0a (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
---
layout: plt
title: computation/lambda calculus
---
# the lambda calculus
the lambda calculus is a simple expression of computation.
```racket
;; A full implementation of the untyped lambda calculus in Racket.
(define (interpret expr [ctx #hash()])
(match expr
[val #:when (value? val) val]
[val #:when (symbol? val)
(if (dict-has-key? ctx val)
(interpret (dict-ref ctx val) ctx) val)]
[`(λ ,id ,body) `(λ ,id ,body)]
[`(,body ,arg)
(match (interpret body ctx)
[`(λ ,id ,body) (interpret body (dict-set ctx id (interpret arg ctx)))]
[expr `(,(interpret expr ctx) ,(interpret arg ctx))])]
[expr (error (format "invalid expression ~a" expr))]))
```
in computer science, the lambda calculus is often used as a base for languages and types systems for its simplicity and extended with syntax and types of various fashions. in linguistics, the lambda calculus is used for its compact notation of functions and is often extended with quantifiers and abstract functions. in mathematics, the lambda calculus is studied in its own right.
|
