Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...