Questions tagged [variable-binding]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
18 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 ...
3
votes
2answers
48 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 ...
0
votes
1answer
13 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 ...
4
votes
2answers
249 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 ...
2
votes
1answer
59 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 ...
2
votes
1answer
161 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
vote
1answer
316 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 with regards ...
5
votes
0answers
131 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 $...
6
votes
0answers
633 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
vote
1answer
115 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? ...
5
votes
1answer
206 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 ...
4
votes
2answers
666 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, ...
31
votes
5answers
9k 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?
4
votes
4answers
8k 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 ...
3
votes
2answers
41 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: ...
2
votes
2answers
863 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 ...
7
votes
1answer
3k 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, ...
4
votes
1answer
360 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 ...
6
votes
2answers
447 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 ...
0
votes
1answer
236 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 ...
1
vote
1answer
311 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: ...
2
votes
0answers
707 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. ...
2
votes
1answer
66 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 $\...
3
votes
2answers
3k 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 ...
0
votes
1answer
202 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....