Tagged Questions
5
votes
2answers
193 views
What is, exactly, $\lambda$-calculus?
I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based ...
1
vote
1answer
59 views
A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language
Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program.
But Simply-typed lambda calculus has to stop - so the question is, can anyone ...
6
votes
3answers
132 views
anonymous lambda functions (functional programming)
What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language?
In my simple terms, when I am programming in scheme/lisp I would ...
5
votes
2answers
102 views
Clear, intuitive derivation of the fixed-point combinator (Y combinator)?
The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as:
FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. ...
5
votes
3answers
232 views
Can someone give a simple but non-toy example of a context-sensitive grammar?
I'm trying to understand context-sensitive grammars.
I understand why languages like
$\{ww \mid w \in A^*\}$
$\{a^n b^n c^n \mid n\in\mathbb{N}\}$
are not context free, but what I'd ...
7
votes
1answer
198 views
Reduction rule for IF?
I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see:
IF TRUE ((λp.p) 3) ↔ IF TRUE 3 (per β red) (1)
...
