Questions tagged [programming-languages]
Questions related to design, implementation, and analysis of programming languages. NOT for questions about how to program, which are off-topic on this site.
0
votes
0answers
10 views
Importance of source program and object program? [on hold]
there are importance of source program and object program in "c". But I want it to know it with explanation.
0
votes
0answers
10 views
Books and resources about production-grade language interpreters(VM)
I've been looking for resources about implementing language interpreters, virtual machines - especially, and there besides the toyish educational examples, I couldn't find much.
My best so far being:
...
2
votes
0answers
21 views
What are the pros and cons of context-oriented programming (COP)?
I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
0
votes
0answers
15 views
Define a heuristic function in Prolog Programming
I'm working on writing a prolog programming to simulate the sliding-tile puzzle games through best first search algorithm with a heuristic function: the counts of the number of tiles out of place.
...
3
votes
0answers
14 views
How do you resolve this paradox with the invariance theorem?
The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have
$$\exists c.\forall s. K_1(s) \le K_2(s) + c$$
Here is an ...
1
vote
0answers
14 views
What are $(S,\Sigma)$-CCCs?
I was reading this and I was trying to understand the definition of $(S,\Sigma)$-CCC. The first requirement says:
a mapping [[_]] : S → |C|, associating some object [[s]] ∈ |C| to
any s ∈ S;
...
5
votes
2answers
96 views
LET REC recursive expression static typing rule
I'm taking a programming languages course and had a question regarding the typing rules for a recursive let rec expression in a static typing system.
To be more ...
0
votes
0answers
13 views
Class Project advice [closed]
Me and my friend are both in high school taking a “PLTW” Engineering class, where our goal is to design a solution to any problem and work on that solution over the course of the year. We’re reaching ...
1
vote
3answers
64 views
Soundness and completeness w.r.t. programming languages
I'm studying programming languages (more specifically type systems) and came across a concept I couldn't quite wrap my head around: soundness and completeness.
I'm taking a class, and according to my ...
0
votes
0answers
20 views
Composition of compostion as a functor
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
1
vote
1answer
35 views
PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?
In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:
Requiring solutions to all type equations may seem suspicious, because
we know by Cantor’s Theorem ...
0
votes
0answers
24 views
What are the guiding design principles for designing programming languages that allow Sketching?
I wanted to implement and design my own programming language that allowed sketching, like Combinatorial Sketching for finite programs. I was reading through the paper but it was unclear to me if there ...
0
votes
0answers
28 views
Why is Combinatorial Sketching for Finite programs possible?
I was reading Combinatorial Sketching for Finite Programs and wanted to understand why synthesis of the sketching language was possible/feasible.
As far as I understand a partial program is ...
0
votes
1answer
45 views
First-order vs Higher-order Programs
Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages?
My understanding so far is that Functional Languages (most) use ...
0
votes
1answer
66 views
What is the difference between “algorithm,” “process” and “program”?
I am currently studying algorithms and algorithmic design, and I am confused those terms. What is the difference between them?
Thank you.
2
votes
0answers
18 views
Results in denotational semantics from model theory? [migrated]
Denotational semantics interpret the theories of various lambda calculi in various (set-theoretic, domain-theoretic, category-theoretic, game...) models. Let $T$ be the theory of one such lambda ...
0
votes
0answers
18 views
What is an intuitive way to understand the definition of Curry and Uncurry in Categorical Language?
I was studying the definition of currying and uncurrying using Category Theory from these slides. The answer and the proof on slide 19 makes 100% sense to me however, the definitions seem to come out ...
0
votes
1answer
32 views
Would hypercomputation machines be capable of simulating/computing/programming everything?
If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that ...
4
votes
0answers
39 views
What is the difference between A-normalization and K-normalization in compilers?
Administrative normal form is a program intermediate representation in which each immediate instruction has a name. It is used in GHC and OCaml.
K-normalized form is an intermediate representation in ...
1
vote
1answer
45 views
Meta Programming Operators
I have a basic understanding how operators work (bitwise, logical, unary, ternary, etc.), but I am confused how you define what the operator does so the machine knows how to treat the operator when ...
4
votes
1answer
89 views
What's the difference between environment and memory in terms of programming languages?
I've been reading up on programming languages to better my understanding with the textbook Essentials of Programming Languages (3e) - Friedman & Wand.
In a chapter regarding the states of ...
1
vote
0answers
46 views
Is there a distinction between pointers and references? [closed]
If so, what are the similarities and differences between the two? I’ve only worked with properties while programming.
1
vote
0answers
27 views
Why the name static and dynamic in static and dynamic scoping
I am wondering, from where static and dynamic scoping got their names.
After understanding the concept of static and dynamic scoping in C, what I assume is that whenever we failed to find out the ...
0
votes
1answer
16 views
CLRS pseudocode involving both subscripting and property access of a data structure
In Introduction to Algorithms, the stack data structure's enqueue operation has the following pseudocode
...
3
votes
0answers
37 views
An instance when you can eliminate propositional double negation in coq
Suppose st: string -> nat and X stands for the string 'X'.
Given the hypothesis ...
2
votes
0answers
40 views
Why interaction net languages use interaction rules to represent their syntaxes?
What I have looked up into:
here, here and here
What I have learnt:
What is an interaction net, its deduction & interaction rules,
How deduction rules can be changed into interaction rules -- ...
0
votes
1answer
18 views
Is it possible to define a pairwise function that can either append to a tuple or make a tuple, potentially with nested tuples?
I lack the vocabulary to appropriately express the question succinctly, so I apologize if the title question is confusing.
Suppose you can define a binary infix operator that produces tuples, and you ...
2
votes
2answers
51 views
How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?
I wanted to show:
$$ (\lambda x . (\lambda y.x))yx \equiv_{\beta} y $$
the definition of beta equivalence is on page 17 of these notes.
I did a few attempts but got different things like $x$. I ...
0
votes
0answers
17 views
How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?
How do we show $$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$$?
I was going through the slides here and it asked to do the above but by page 16 of the slides we have not ...
1
vote
1answer
18 views
Showing that an equivalence relation on programs need not be a congruence
An optional exercise from Programming Language Foundations asks
Can you think of a relation on commands that is an equivalence but not
a congruence?
An equivalence here refers to an ordinary ...
0
votes
1answer
43 views
Bounded Quantification: Full F<: intuition
I'm currently looking into Chapter 26 of Types and Programming Languages and am a bit confused by the "intuition" for Full F<: (p. 395):
A type T = ∀X<:T1.T2 describes a collection of ...
3
votes
2answers
463 views
Do “compiler” and “assembler” correspond to frontend and backend phases of a compiler?
In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition
by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a ...
2
votes
0answers
36 views
Are there any interesting terms in pure LF or $\lambda\Pi$?
In my searching, I've seen that if Church numerals are encoded in a dependently typed Lambda calculus, that we can't derive induction or that $0 \neq 1$.
I know that LF and the dependently typed ...
3
votes
2answers
81 views
Are Bad churches inhabited?
In type theory, some inductively defined data types allow you to prove absurdity. For example
...
2
votes
4answers
81 views
How does one formally show that two lambda functions are $\alpha$ equivalent?
I was going through the following slides and I wanted to show the following:
$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$
formally. They define a an $\alpha$-conversion on page 15 as follows:
$$ ...
3
votes
2answers
67 views
Why does the denotational semantics for a while loop have a existence quantifier?
I was going through these notes and they have the following operator on partial functions:
$$
\mathcal F^{k}(\bot)(\sigma) =
\left\{
\begin{array}{ll}
\alpha( [\![s]\!]\sigma ) & [\![b]\!]\...
1
vote
0answers
26 views
Can I call my library an interpreter?
I am working on tiny programming language (for our specific tasks). It's a script language.
It looks like a library for C++ that can execute a code of this language. This library parses a source code ...
1
vote
2answers
60 views
How is it that programs can be identified with partial functions for programming language semantics?
I was reading about denotational semantics
Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, ...
0
votes
1answer
66 views
Understanding SLDNF-forest
I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.
Question:
In the main tree, why from ←off_gound(a) can you ...
3
votes
1answer
43 views
Common name for a group of commands which break the linear structure of the program
I'm looking for a name of a group of all commands which are break the linear structure of the program.
In C PL, they are: ...
0
votes
1answer
24 views
Basic control statements for Turing equivalence? [duplicate]
Apologies ahead of time, I don't fully understand what I'm asking...
But, is it possible to program using only 'while loops' and still be Turing equivalent?
Or more generally, can I do everything ...
3
votes
0answers
42 views
PL: How can I prove the type of something using “Inversion for Typing”?
I'm currently going through this book about programming languages, and in section 4.2, Lemma 4.2 it says this:
Lemma 4.2 (Inversion for Typing). Suppose that $\Gamma \vdash e : \tau$. If $e = \...
1
vote
1answer
84 views
What other than programming does a computer science degree usually involve? [closed]
Programming courses are about 30% of my computer science degree. Also at my university, around 15-20% of the degree are applied math courses.
What other areas/fields are covered? For the majority of ...
1
vote
1answer
174 views
Difference between Row Major Order and Column Major order
Let take a multi-dimensional array: $a[2][3][4]$
Here $a$ is a three-dimensional array, which means that it is a collection of two-dimensional array's.
Therefore ...
5
votes
0answers
62 views
Which languages, if any, implemented parametric polymorphism before ML?
In particular, was there any kind of implementation at the time Christopher Strachey wrote Fundamental Concepts in Programming Languages?
In that work, Strachey lists Ad Hoc and Parametric ...
0
votes
2answers
52 views
What are constraints on some new logic programming language and system?
As I understand, everyone can create logic programming language and system by declaring that the valid program of some logic programming language is the set of statements in the form: ...
2
votes
2answers
61 views
Machine code and punched cards
I have been looking into the history of programming, and everybody and their grandmothers begin the subject with a claim more or less similar to the following:
At first, programmers used machine ...
22
votes
2answers
6k views
Do any programming languages use general recursive functions as their basis?
This is a naïve and, therefore, possibly malformed question, so apologies in advance!
My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming ...
2
votes
3answers
2k views
Interpretation of for loop.
for every j != i in {0,....,n-1}
How to interpret this for loop? I never seen this type of definition of for loop.
Is it like - j=0 to n-1; j !=i ; ++j
1
vote
2answers
40 views
Are all computational complexity results oracle results?
When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required.
For example, a common argument says ...
