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.
957
questions
0
votes
0
answers
30
views
Function types in Computer Science Metanotation
See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF.
I often make use of the BNF syntax observed there, as a substitute for ...
- 111
-1
votes
0
answers
10
views
Rewriting with http queries and path with caddy server [closed]
1. The problem I'm having:
I want to rewrite an URL who contain http query to another URL who replace the query by a directory.
I have a URL like this:
...
0
votes
1
answer
26
views
Discarding lists of same elements
Suppose, I have a list of lists where multiple lists can have same elements. In my final output, I just want one list with the same element. An example is the following:
Input: A=[[1,2,0], [0,1,2], [2,...
0
votes
1
answer
55
views
Can contiguous arrays be lazily evaluated?
Contiguous arrays with variable length, such as C++'s std::vector, have been a major sequential container for languages whose evaluation is eager. However, it has ...
- 241
3
votes
0
answers
67
views
Formalize the proof of theorem 2.4 in Harper's PFPL
In Harper's Practical Foundations for Programming Languages, page 19, rule (2.9) defines the $sum$ function inductively.
$$
\frac{b:nat}{sum(zero;b;b)}\tag{rule 2.9a}
$$
$$
\frac{sum(a;b;c)}{sum(succ(...
1
vote
0
answers
41
views
Is there any formalization of GADTs implemented in OCaml?
There are papers that describe how generalized algebraic datatypes (GADTs) are encoded in core Haskell (System FC)[1][2], but I could not find any documentation on how OCaml formalizes/implements/...
- 639
-2
votes
1
answer
44
views
How a computer works?
I know that a computer can be mechanical, screws/nuts or even water/pipes. Of course, it would be slow and big, but it doesn't have to be electric, transistors, etc. How can a machine like this do all ...
- 11
1
vote
2
answers
61
views
Division by zero in APL: assign return value 0 or 1
Recently I began learning a couple array based programming languages: Dyalog APL and BQN. And I cam across this peculiar manner in which division by zero is handled in Dyalog APL. Using the in-built ...
- 113
1
vote
1
answer
32
views
Example of preservation failing in Java - follow up question
This is a follow-up question to my previous question
I have been reading this post and it comes up with the following example showing how Java type system is unsound:
...
- 99
0
votes
2
answers
38
views
Types and programming languages: strange term construction?
Pierce's Types and Programming Languages has the following definition of terms:
$$S_0=\emptyset$$
$$S_{i+1} = \{true,false,0\} \cup \{succ(t), pred(t),iszero(t)|t \in S_i\} \cup\{if(t_1)then (t_2)...
- 159
1
vote
2
answers
91
views
Example of progress and preservation failing in a commonly used programming language like Java
I am wondering if my solution is correct or I am on the right track. I have searched online and found a paper about Java type system being unsound but that doesn't really answer the progress and ...
- 99
0
votes
0
answers
29
views
Programming language implementation challenge: is recursion harder than HOFs, or vice versa?
(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to ...
- 159
-3
votes
1
answer
67
views
A chatbot's take on dynamic scoping: it is easier to debug - correct?
I asked the chatbot at you.com, "what is an advantage of dynamic scoping?" and it said the following on the pane titled YouChat. (If you click the link, you will probably see a different ...
- 159
0
votes
0
answers
45
views
what are all the ways of delimiting blocks
To my knowledge, in block-structured programming languages, there are 2, maybe 3 main ways of delimiting a block.
Using start and end tokens, this can be brackets or reserved words etc
Using ...
- 81
0
votes
0
answers
43
views
Semantics Equivalence of Structural Semantics of While Programming Language
I'm taking a course about the formality of programming languages and while reading Semantics with Applications: An Appetizer by H.R Nielson and F. Nielson
I came across the following exercise:
I'm ...
0
votes
0
answers
18
views
Reference request: Domain specific language, runtime, virtual machine design and implementation
I'm a working software engineer who is interested in programming language design and I want to try to implement a simple DSL as an exercise and a side project. I want to apply for grad school in this ...
- 101
0
votes
0
answers
18
views
BSS/Data section question [duplicate]
There is something i would like some enlightenment on : Studying the BSS and data section on Assembly, we know that the data section is for the initialized data to be declared, while the bss section ...
- 1
0
votes
1
answer
34
views
Regular grammar such that it rejects keywords
I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.
Def: A variable can be any combination of characters, ...
- 1
0
votes
1
answer
55
views
Why is Javacript's Object not a primitive data type?
If javascript's object is just associative array, what makes it non-primitive as they have labeled it? It is certainly already built in. Its not like I'm creating my own concrete implementation of ...
- 13
0
votes
0
answers
10
views
Unary Function definition and Regularity in Elements of Programming
I was reading through Elements of Programming by Stepanov and I had a curiosity regarding the precondition for regular unary function
Domains and codomains are only defined for "functional ...
3
votes
1
answer
140
views
Is “x' = f(x)” a programming paradigm?
I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the ...
- 66
1
vote
1
answer
66
views
Programming language compiler that will perform the composition of primitive functions with optimization
Is it possible to create a some programming language compiler that will perform the composition of primitive functions with optimization?
In fact, the maximum possible optimization in the context of ...
- 45
0
votes
0
answers
52
views
How to translate Python's For loop into operational semantics?
I've spent hours, struggling to understand the basics of operational semantics. In a couple of resources and videos that I've reviewed, one of the most intuitive example that I found was the ...
- 1
1
vote
1
answer
96
views
Is it true that everything is a side effect in C?
I'm just a beginner, I've started learning programming, CS, math, and Unix. I know how to code in Pascal and also study C.
In the university a professional programmer, who teaches coding, said that ...
0
votes
1
answer
103
views
formal definition for "data type with larger range"
Wikipedia defines range of data type:
the set of possible values that that variable can hold.
Suppose we have two data types A and B. Now, with attention to
the ...
- 103
1
vote
2
answers
58
views
What is this definition of orthogonality in programming language trying to convey?
My book Sebasta's Concepts of Programming Language (Chapter 1) states:
Orthogonality in a programming language means that a relatively small
set of primitive constructs can be combined in a ...
- 33
1
vote
0
answers
115
views
Simple proof that Lisp expresses all computable list functions
Given computable function $f : LispTerm \rightarrow LispTerm$ is it possible to implement it in Lisp?
The $LispTerm$ is any term that is constructed using cons, <...
- 93
0
votes
0
answers
48
views
What are optimizations that can be made after the type checker has completed?
So I am implementing a statically typed version of solidity.
I have a type checker built. I am working on User defined aliases currently.
...
0
votes
0
answers
89
views
What are Funges?
I am currently reading up about esoteric programming languages and came across a COS theory question stated as follows:
Esoteric programming languages can be categorised in a variety of different ...
- 1
0
votes
0
answers
57
views
Question about complexity of two topics in programming language theory
I am a student who is currently finishing second year of university mathematics. This summer I have to choose a topic for my diploma. Because I am particularly interested in computer science I am ...
- 203
0
votes
2
answers
62
views
Why is there a difference between the meaning of the word 'statement' in programming and linguistics?
In linguistics, the word 'statement' means something that is true or false, closer to a declarative sentence, but in programming, the meaning is closer to an imperative sentence.
What is the reason ...
- 13
2
votes
0
answers
64
views
What are strong examples of programming languages whose type systems don't embed into their native type theory?
Given a typical popular programming language, its native type theory is a dependent type theory which describes invariants, preconditions, predicates, and other generalizations of typical type-system ...
- 221
1
vote
1
answer
117
views
What exactly does Turing Equivalence mean?
Assume I have a programming language $L$ with well-defined semantics.
Showing Turing-completeness is straightforward: if I write a program using $L$ simulating the universal TM, I'm done.
What I'm ...
- 295
0
votes
0
answers
23
views
resources about programming language theory,topics: zipper and monads
I am in need of exercises and solutions about these topics in programming language theory with ocaml, zippers and monads, I can't find much on google, or I am missing something?
7
votes
1
answer
820
views
What exactly is the relation between Haskell and category theory?
In articles or Quora posts about category theory, I often find mentions of the programming language Haskell. I have little knowledge of category theory and even less of programming. Could someone ...
0
votes
1
answer
45
views
Structural induction proof for reverse(push(as, bs)) = push(reverse(bs), reverse(as))
I need to prove:
reverse(push(as,bs)) = push(reverse(bs), reverse(as))
where:
...
3
votes
2
answers
301
views
Similarities and differences between Unit and Bottom types?
I came across this recent Reddit thread, Thoughts on Botton vs Unit Types, but I don't understand what the similarities and differences are in regards to when you are creating a programming language.
...
- 1,953
1
vote
0
answers
53
views
First piece of code in scientific papers
What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
- 111
4
votes
1
answer
64
views
Covariance and Contravariance: Conflict without a Cause
Here is the last paragraph at page 441 of the paper ‘Covariance and Contravariance: Conflict without a Cause’ by Giuseppe Castagna:
How is all this translated into object-oriented type systems? ...
- 113
3
votes
2
answers
171
views
What does Herb Sutter refer to in his seminal paper The free lunch is over?
In his paper The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Herb Sutter writes:
The mainstream state of the art revolves around lock-based programming, which is subtle and ...
- 335
0
votes
1
answer
18
views
Find the output value using call by value and call by reference
Given the following code:
int p = 5 , q=2;
int f( int b, int c){
b = 2 * c;
c = 3 + p;
return b + c ;}
print f(p,q);
print p;
print q;
I have found that the output values using call by value are:
f(p,...
- 13
0
votes
1
answer
74
views
What is an API, exactly
I’ve read the Wikipedia article and know it’s basic function but I don’t understand what it physically is. Like, is an api a text file that the main program reads from and you are just putting your ...
- 137
1
vote
1
answer
216
views
What is the definition of a redex and what are they for in programming languages literature?
I saw the word "redex" in the context of proramming language theory/semantics in 2018 and now when I was reading a neurosymbolic research paper (machine learning with neural nets + symbolic ...
- 2,950
0
votes
1
answer
76
views
Partially correct?Totally correct?Deterministic?Determined?Terminating? What do these adjectives mean for an algorithm?
These terms are often used to describe algorithms but I'm not really sure what they mean. I would like to see more examples of what each one is like and how they can be identified. Can anyone please ...
- 1
0
votes
1
answer
436
views
How to incorporate Duplicate Letter Handling for Wordle?
I am trying to reverse engineer the following image. So far, the way I would take into account of duplicate letter handling is the following .
I am unsure how I could code this such that the ...
1
vote
2
answers
158
views
What are the technical reasons programs in C and C++ do not show runtime errors, but programs in Rust and Golang do?
When a runtime error occurs with a program in language likes C or C++ using GCC/G++, it just crashes the process. When it occurs with a program in language like Rust or Golang, a detailed error ...
- 111
0
votes
0
answers
36
views
Interpretation of semantics of queue algebra
I am trying to understand the semantics for stack algebra and queue algebra as introduced in section 8.5, "Specification Algebras" of textbook Software Engineering 1, Abstraction and ...
- 481
-1
votes
2
answers
174
views
In Programming data types size are depends upon what?
In Programming there is different data types (int , cahr , bool ,
float ) and they have different sizes (1,2,4,8 .. Bytes) , and the
size of data type are depends upon hardware or architecture of
...
- 1
1
vote
1
answer
64
views
What exactly are functions in programming?
Are conditional statements, loops, and basic maths operators are functions? I learn functions as a "specific action". But, I saw in a video from youtube that a guy called loops and math ...
- 23
1
vote
1
answer
38
views
Books for learning horn clause logic
I want to learn prolog,two reason for that are -one can always find a counter example to the argument by searching for negation.So,one can learn by debugging the scripts.I heard that prolog is based ...
user139614