Questions tagged [variable-binding]
The variable-binding tag has no summary.
40 questions
1
vote
1
answer
337
views
What is a simple explanation and example of de Bruijn indices?
In order to find the recurrence formula for the number of λ-terms of a given size, we make use of the representation of variables in λ-terms by de Bruijn indices. Recall that a de Bruijn index is a ...
- 182
0
votes
1
answer
164
views
Free variable in the programming language
From the wikipedia of Free variables and bound variables
In computer programming, the term free variable refers to variables used in a function that are neither local variables nor parameters of that ...
- 208
1
vote
2
answers
124
views
(how) is assignment or binding possible in purely functional languages?
i can't seem to find much info on the following question:
how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus?
i'...
- 11
2
votes
1
answer
59
views
How are closures supposed to interact with variable binding and resolving?
I am currently reading the Crafting Interpreter book and I have a question about the Resolving and Binding chapter
The author gave this example to illustrate the problem with the implementation at ...
- 145
2
votes
0
answers
106
views
Lambda calculus with unordered application
In lambda calculus, $\lambda xy.\phi$ isn't in general equivalent to $\lambda yx.\phi$. However, it seems possible to imagine a calculus which replaces application with something like specification, ...
- 241
1
vote
0
answers
336
views
What actually IS lambda calculus and how do I actually apply it?
Trying to wrap my head around lambda calculus but am really clueless right now.
First of all, I'm really confused WHAT it's actually supposed to be. I've found these definitions:
Lambda calculus (...
- 19
1
vote
0
answers
124
views
Shallow Binding with static scope, is it possible?
I'm new in programming, I'm currently studying programming languages.
I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
1
vote
1
answer
187
views
What attributes are bound statically vs dynamically [closed]
I am having a hard time understanding the concept of what attributes get bound statically instead of dynamically. Below is code and from that code, what gets bound statically?
Here is an example (In ...
- 113
3
votes
0
answers
146
views
Lemma relating variable substitution to de Bruijn substitution
Notation:
Let $t$ and $u$ be terms in the $\lambda$-calculus, and $x$ be a variable name.
Let $[x\mapsto u]t$ be the substitution in $t$ of free variable $x$ for the term $u$. Specifically, I'm ...
- 183
0
votes
1
answer
372
views
What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?
Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the ...
- 111
0
votes
0
answers
61
views
formal definition of lexical scope
I wonder if there is a formal definition of lexical scope so that people can prove things with respect to it, for example, that an interpreter implements lexical scope. You may ask what level of ...
- 781
3
votes
0
answers
130
views
Semantics of "write-once" variables for complex data structures
Question
My use case for what is described below is not a language or compiler implementation, but finding a reasonable semantics for this feature in a an abstract calculus.
Ideally, you give me a ...
- 370
3
votes
1
answer
479
views
Difference between assignment, binding, and substitution?
I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration,...
- 221
0
votes
2
answers
63
views
Does hiding variables work in terms of blocks or line-by-line?
Let's assume I have the following code:
declaration of a
declaration of b
..a..b
{
..a..b
declaration of a
declaration of b
..a
}
In this code {} ...
- 17
1
vote
0
answers
109
views
How to use dynamic scope?
I have this example code, which is an undefined language. We want to know what will be printed if we use static versus dynamic scope.
...
- 387
2
votes
1
answer
106
views
Is there a good way to hash abstract binding trees?
The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
- 230
3
votes
2
answers
274
views
Is there a systematic way to know when to alpha-transform free variables?
So, using Church numerals, we define
$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,
and
$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.
We can then add with an expression like
$3\ g\ (4\ g\ z)$
And ...
- 1,730
0
votes
1
answer
43
views
Relating indexes for parameters and variables
I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.
I have the following ...
- 45
5
votes
2
answers
456
views
Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?
The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:
Does the $x$ in the ...
- 171
2
votes
1
answer
166
views
How shall I resolve a nonlocal name in a language with deep binding?
From Programming Language Pragmatics by Scott,
Figure 3.14 Deep binding in Python. At right is a conceptual view of the run-time stack.
Referencing environments captured in closures are shown as ...
- 5,045
3
votes
1
answer
552
views
what are Structural recursion, primitive recursion, recursion combinator and recursion principles?
Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link
I googled and read some, but missing the points of them. I know that ...
- 1,034
1
vote
2
answers
535
views
When is a variable bound or free in a lambda application?
I am currently reading the book "An Introduction to Functional Programming through Lambda Calculus" (the 2011 edition) and am a bit puzzled by the definitions of free and bound variables ...
- 273
5
votes
0
answers
201
views
Characterization of alpha-equivalence in languages with bindings
Following up on this post denoting $(x \leftrightarrow y)$ the permutation of $x$ and $y$ and $P[x \leftrightarrow y]$ the term obtained from the term $P$ by permuting $x$ and $y$ (so for example if $...
- 265
16
votes
0
answers
3k
views
Barendregt's Variable Convention: what does it mean?
Barendregt's Variable Convention: If $M_1,...,M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free ...
- 1,034
1
vote
1
answer
189
views
Claimed problems with Lisp dynamic scoping
What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do?
...
- 2,252
5
votes
2
answers
530
views
How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages
On page 7/8, section 1.2, of Practical Foundations of Programming Languages, 2nd edition, Robert Harper gives this initial definition of abstract binding trees:
The smallest family of sets closed ...
- 307
5
votes
2
answers
2k
views
what is variable capture in nominal logic?
While reading a paper Nominal Unification from a Higher-Order Perspective, in the abstract I noticed something feel bit confusing,
Nominal Logic is an extension of first-order logic with equality,
...
- 1,034
34
votes
5
answers
12k
views
How do computers remember where they store things?
When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?
- 451
5
votes
4
answers
16k
views
What are differences between Static Scope and Dynamic Scope?
My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is ...
- 391
3
votes
2
answers
105
views
Is there a formal term for functions that have static state across executions?
Two examples, one in PHP:
function adder($i){
static $a = 0;
$a += $i;
return $a;
}
A similar effect can be achieved with closures in javascript:
...
- 131
2
votes
2
answers
2k
views
How do global variables and automatic variables with the same name interact?
Suppose I define a global variable and I define an automatic variable within a function definition with the same name as the aforementioned global variable.
What would happen to the global variable ...
- 123
10
votes
1
answer
5k
views
What is the difference between assignment, valuation and name binding?
I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, ...
- 857
4
votes
1
answer
557
views
Is There a Programming Language That Embraces Globals?
All programming languages have globally defined symbols. While best practices invariably abjure their use as mutable entities the philosophy of what is mutable and what is not mutable is highly ...
- 394
6
votes
2
answers
718
views
Free and bound variables
I am familiar with free and bound variables theory , but while learning I somewhere saw
this lambda expression
((lambda var ((fn1 var) & (fn2 var))) argument)
From what I have learned it seems ...
- 184
0
votes
1
answer
313
views
Is there a name for the 'scope tree' organization?
I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML.
When you are ...
- 111
1
vote
1
answer
413
views
Interactive example of Dynamic scoping and evaluation order of expressions
Given the following (arbitrary language, although I think it is close to Algol 60) program:
...
- 111
2
votes
0
answers
858
views
lexical scoping vs. dynamic scoping
I'm wondering about the result of this program as I get confused when it comes to lexical scoping and dynamic scoping.
...
- 161
2
votes
1
answer
115
views
Is this $\beta$-reduction well defined?
Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it $\...
- 123
5
votes
2
answers
4k
views
Static scope and dynamic scope
I am perpetually confused when it comes to static scoping and dynamic scoping and their differences and Wikipedia isn't of any help, so here's my question:
Given the following pseudo code in a ...
- 81
0
votes
1
answer
278
views
Free and bound variables in a lambda-calculus term
For this term:
$\lambda x.(f (g x))$, what are the free and bound variables?
I'm confused as to how to expand this so it will be easier to see.
If I expand this will it be $\lambda x. \lambda f....
- 129