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.
1
vote
0answers
9 views
How do we know $\neg \neg LEM$ isn't provable in MLTT?
I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions:
$$LEM \equiv \prod_{A : Type} \neg A \vee A$$
$$DNE \equiv \prod_{A : Type} \neg \...
-1
votes
0answers
16 views
in assembly language what does the # sign represent like in LDAA #$10 [on hold]
in assembly language what does the # sign represent like in the instruction LDAA #$10
1
vote
1answer
30 views
Fixed Points of Factorial Function
(This is taken from the book Semantics with Applications)
I'm trying to determine the fixed points for the following block:
...
1
vote
1answer
30 views
Proving Turing Completeness by creating a compiler to a Turing Complete language
Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the ...
0
votes
0answers
23 views
Trying to determine Fixed Points
I'm basically trying to solve 4.2
(Taken from Semantics with Applications)
As I see it, the functional F will be defined like so:
...
-3
votes
0answers
9 views
PhoneBookDirectory array in java, explained in detail in picture below [closed]
The PhonebookEntry class exists and is working fine, so write the code as if you had it already.
0
votes
2answers
43 views
Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
-2
votes
0answers
11 views
Program Please solve in C# [closed]
A Class Diagram clearly showing the class relationships. in a word document . Include a description of the class diagram that describes each class and indicates why it is a good design.
Screen ...
1
vote
1answer
43 views
How much does C# gain from its value types
C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
3
votes
1answer
30 views
“Immediate” method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":
x=1
x=f(x);
x=f(x);
We can rewrite this in "immutable style" without changing the higher-level structure of ...
1
vote
1answer
44 views
Sizeof function definition in a system
Why sizeof(int) and sizeof(int *) takes different value in a system? I mean generally size of integer is 4 B, but size of integer pointer is 8 B. But why they cannot take same value, although their ...
-1
votes
1answer
37 views
Term for the use of the same programming language in every tier?
What is the technical term that describes the use of the same programming language in every tier in the architecture of a system? For example, having JavaScript in model, view and controller.
edit #1:...
1
vote
2answers
113 views
Pass by Value or by Reference and Impure or pure functions
Beginner question: I am teaching myself the two passing techniques: Pass by Value and Pass by Reference.
Can Pass by Value change the states of an object? If yes, how? Which of the two techniques ...
0
votes
0answers
37 views
How does computer work? [duplicate]
I am not a computer scientist or even a student of CS. I just want to find more information and would like if someone could put if in right direction about how actually computer works. I understand ...
0
votes
1answer
60 views
Is ambiguity in Programming Language always bad?
Suppose we have a token and our language allows the compiler to build two different derivation trees. However, it can happen that there exists two semantic ways to interpret our token. So ambiguity is ...
1
vote
2answers
89 views
Is lazy evaluation required for do-notation?
Do-notation is most famous by Haskell, which is also famous for having lazy evaluation.
But is lazy evaluation a requirement for implementing do-notation?
In principle, could do-notation be added ...
5
votes
3answers
70 views
How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:
In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$...
0
votes
3answers
59 views
Preconditions and postconditions
What are preconditions and postconditions in this C++ function?
I have this example in my slides but still didn't get the idea!
...
1
vote
1answer
38 views
Generalization of Functors to other datatypes?
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$,...
0
votes
1answer
36 views
Why in Declarative Programming variables are not reassigned?
I've read that a Declarative language is called "stateless". This means that we can imagine that internally every variable is a constant variable, and it never get reassigned ( in contrast with what ...
2
votes
1answer
66 views
Is the Shakespeare Programming Language Turing complete?
I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought ...
3
votes
0answers
21 views
Static type analysis with dynamic scoping?
Both in school and out, I have only ever encountered dynamic scoping paired with dynamic typing. Is there any published work (even if just academic, not yet implemented in a "real" programming ...
3
votes
2answers
251 views
The idea behind the state of Imperative languages
I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? ...
1
vote
0answers
40 views
Reasons for why x - 1 and x -1 gives different result in some languages [closed]
I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find ...
3
votes
3answers
100 views
How does a computer “wait” time?
Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate.
I know that computers have ...
4
votes
1answer
53 views
Type system and language that implements type constraints?
Occasionally when writing programs in a statically typed language, e.g. some ML, I find having to write code for cases I know will not happen. This is because I know e.g. that a function on some data-...
1
vote
0answers
26 views
Converting (reverse-engineering) Turing machine into program or most concise algorithm?
It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to ...
39
votes
2answers
7k views
How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?
The Short Story
A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it?
The Long Story
Tarjan is known for many ...
5
votes
1answer
584 views
Where are C++ templates inside of the lambda cube?
C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or ...
3
votes
0answers
40 views
Computability of Kolmogorov complexity in total languages
It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages?
For example, is the Kolmogorov complexity of ...
1
vote
1answer
61 views
Reason programming language B was named “B”?
I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.
If C was named “C” because it came after B, why was B named "B", since the only ...
-1
votes
2answers
54 views
Are managed computer programming languages eco-friendly?
Managed code needs to be be interpreted or JIT-ed at runtime.
At first glance it seems to me that in general it is more energy consuming to interpret/compile the program on every user's computer than ...
1
vote
0answers
32 views
How to create model for a powerful language whose programs are guaranteed to terminate?
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
1
vote
2answers
104 views
Are the capabilities of programming languages the same?
Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
0
votes
0answers
45 views
Mathematical resource material accompanying TAPL
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.
Prior to this chapter I found the book challenging but ...
2
votes
1answer
63 views
How do I count the exact number of executed commands for a MIPS program?
I want to know what the best way is to count the number of executed commands for a given MIPS program. Let's say we're given a simple for loop that counts from $0$ to $100$. For this I would write the ...
0
votes
2answers
201 views
Programming Language Hierarchy
I know that Assembly is the lowest level of the stack besides machine code, but are the languages above it all considered "high level languages" or is there a hierarchy amongst these languages. For ...
2
votes
3answers
86 views
Are there any programming languages which support user defined control structures?
For instance, the user would define a for each loop in their code as having a structure something like:
foreach([variable1] : [variable2]){
[statements]
}
(...
2
votes
1answer
46 views
How to make an unambigous grammar of a programming language
We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is ...
1
vote
0answers
39 views
Sequential valid programs to find novel outputs?
I have:
A programming language (P). Programs should take no input and produce a sequence of integers as output.
A way to enumerate all valid programs in this language (R) in a way that each program ...
0
votes
1answer
36 views
How to draw a parsing tree according to syntax diagram?
I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.
0
votes
1answer
17 views
Examples of interesting semantics to study during a small project for a graduate Semantics course
I have been following the course Concrete Semantics with Isabelle/HOL. At some point we are given the task to verify a program/extend some semantic construction/prove some mathematical fact. I ...
3
votes
1answer
59 views
Is there a generally accepted name for creating types that select a subset of other types?
Tl;Dr;
Given:
type A = { int: foo, int: bar }
type B = select foo from A
What is the name of the typing relationship between A and B?
What is the name of the ...
1
vote
0answers
26 views
directed edges in an undirected graph [duplicate]
Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even.
For example, consider a graph ...
2
votes
0answers
27 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 ...
3
votes
0answers
29 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
16 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;
...
6
votes
2answers
143 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 ...
1
vote
3answers
192 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
30 views
Composition of compostion as a functor
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
