Questions tagged [lambda-calculus]
11 questions
14
votes
2 answers
What is the relationship between lambda calculus and programming languages?
I am starting my first year (in college) in Computer Science next year and I write mostly in C (if that is to matter). I have tried searching but most of what I find assumes knowledge of lambda calculus. Why is lambda calculus considered so much…
RonaldMunodawafa
- 661
- 1
- 6
- 12
11
votes
1 answer
What Is λ-calculus essentially?
I have what I would call a philosophical question about λ-calculus.
When you explore λ-calculus you will be surprised to see all the things that you can do there. You can define integers, arithmetic operations, booleans, if-then-else statements,…
Florian F
- 1,127
- 1
- 6
- 13
9
votes
3 answers
Lambda expressions with no parameters in Haskell and / or lambda calculus
In eager languages like Scheme and Python, you can use a lambda expression without parameters to delay evaluation, e.g. in Scheme (Chicken Scheme):
#;1> (define (make-thunk x) (lambda () (+ x 1)))
#;2> (define t (make-thunk 1))
#;3> (t)
2
In line…
Giorgio
- 19,486
- 16
- 84
- 135
3
votes
2 answers
What is the equivalent of The Little Lisper project in Haskell?
In the book The Little Lisper, you implement a minimal Scheme in 10 Chapters that is capable of interpreting any chapter in the book.
To me it seems you could do the same for a 'minimal subset of a typed language' to be self-bootstrapping. I'm…
hawkeye
- 4,819
- 3
- 24
- 35
3
votes
3 answers
If Scheme is untyped, how can it have numbers and lists?
Scheme is said to be just an extension of the Untyped Lambda Calculus (correct me if I am wrong). If that is the case, how can it have Lists and Numbers? Those, to me, look like 2 base types. So I'd say Racket is actually an extension of the Simply…
MaiaVictor
- 5,820
- 7
- 27
- 45
2
votes
1 answer
Notation/Meta Language To Express An Algorithm
I need to learn a notational language, so I can express and possibly prove the correctness of what I believe to be a complicated algorithm that distributes a credit adjustment across multiple water bills in issue date descending order. But I cannot…
octopusgrabbus
- 699
- 1
- 8
- 20
2
votes
2 answers
General recursion to tail-recursion
Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.
My view is that it's not possible…
user131411
- 121
- 1
1
vote
1 answer
Generating a Beta Reduced Lambda Expression in Java
Good day, I'm a beginner in Java and I was wondering if, in Java, I'm able to do a beta reduction with a given lambda expression in Java. Basically lambda reduction is like this:
1.)
Expression : (λa.abc)x
Beta-Reduced Expression (without…
Samuel David
- 19
- 1
1
vote
1 answer
Which Algorithm Approach Should I Take to Generate Lambda Expressions in Java?
Good day, I'm trying to find a way to program a lambda expression generator in java with this context-free grammar, and I would want to ask ; what would be the best way to tackle this problem and be able to manipulate them with basic lambda calculus…
nathan De Guia
- 41
- 4
0
votes
2 answers
Lambda calculus: Call by value / Call by name (lazy)
Having difficulties deciding which rules to apply on by value / by name evaulation.
Say I have:
(λz.zz)(λb.b)
And I want to evaluate according to call by valute, will the next step be
(λz.z)(λb.b)
(evaluate the left side - z apply on z),
or …
Jayn
- 3
- 1
- 2
-1
votes
1 answer
Appropriate base type for simply typed lambda calculus
Given the following hypothetical programming language:
Intended for practical programming
A simply typed lambda calculus (STLC)
All objects are functions, based on Church encodings
I am aware that making everything a function means a STLC with no…
Ari Fordsham
- 107
- 5