Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 views

can programming language be described by ambiguous grammar, if yes, will that cause any problem?

When someone tries to formally describe the syntax of programming languages, they describe with context-free grammar, then for every program we can derive parse tree that would correspond to that ...
3 votes
1 answer
173 views

How did this work apply weakest precondition rule on their example car problem?

While reading the example given in [1]., I couldn't understand how the authors set up the logic to compute the weakest preconditions (wp) in their car example in section 4.2. The dynamics of the ...
0 votes
2 answers
39 views

Reference types

Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing? I'm having a hard time wrapping my head around the concept fundamentally (of course, I have ...
10 votes
6 answers
2k views

Do we create a programming language by writing a compiler?

Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, is ...
1 vote
0 answers
58 views

How to convert wp equations into linear algebra equations?

I am reading this paper [1], wherein the authors first formulated a safety constraint in terms of wp equations. Then, they converted the equations into linear algebra form. As per section 4.3, their ...
3 votes
1 answer
234 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 ...
10 votes
1 answer
192 views

Using naturality to prove $f: \forall\alpha. \alpha\times\alpha\to\alpha$ must be a projection

Suppose we have a System F term $f : \forall \alpha. \alpha\times\alpha\to\alpha$, interpreted in a parametric model which is a bicartesian closed category. I was wondering if in such context it is ...
0 votes
1 answer
37 views

How are PCFGs used in programming language design?

I've been reading the wikipedia article about probabilistic context-free grammars (PCFGs), and they state that PCFGs have application in areas as diverse as natural language processing to the study ...
3 votes
1 answer
484 views

SICP: applicative or normal order evaluation

I'm trying to solve Problem 1.5 from SICP book. Consider the following definitions: (define (p) (p)) (define (test x y) (if (= x 0) 0 y)) (test 0 (p)) The ...
0 votes
2 answers
103 views

Grammar where the precedence of condition operators are asymmetric with regard to assignment operators

In Unix shell programming, there's the ideom: program1 && program2 && program3 where successful completion of ...
1 vote
4 answers
101 views

Should I be a good computer scientist to become a great software developer?

As I am headed into a Computer Science major wishing to eventually become a software developer, I wonder this: should I immerse myself in computer science theory and knowledge (data structures, ...
2 votes
1 answer
42 views

Is there any reference materials on complexity analysis for lazy languages?

Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell? I know how laziness is implemented and how it can be expanded and ...
0 votes
1 answer
126 views

What does it take to support a programming language on an OS?

From my understanding, something like Linux is very geared towards C programs, with things like libc. What I'm wondering is, even in Java, you have arguments to ...
0 votes
2 answers
65 views

What is the precise difference between state and environment and memory?

I was just reading this question regarding the difference between environment and memory. However, the textbook in question, Essentials of Programming Languages, third edition, by Friedman and Wand, ...
1 vote
1 answer
762 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
1 answer
33 views

Creating an executable after code generation - compiler design

I am learning about and building a very basic compiler. My question is about code generation. I have read on a lot of materials about code generation when building a compiler and I get the concept. ...
1 vote
2 answers
59 views

How are conflicts between free and bound de Bruijn indices resolved?

On page 77 (section 6.1) of Types and Programming Languages by Benjamin C. Pierce (1st and only edition thus far), there is the following quote regarding naming contexts and de Bruijn indices: Γ = x ...
3 votes
1 answer
93 views

Named outputs of a function

Is there a programming language with named return values? I imagine something like in the following (syntax to be workshopped): ...
1 vote
0 answers
144 views

How to deal with missing variables when utilizing weakest precondition for verification?

I am reading the example given in [1], section 4.2. It deals with applying weakest precondition (wp) rules to ensure that the velocity of a car doesn't exceed a certain limit. We have the following ...
1 vote
1 answer
122 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 ...
0 votes
2 answers
39 views

Returning more than one value from a function without overhead

In stack languages (e.g. PostScript, Forth), return values are passed on the stack - zero, one, even a variable number. Python supports tuples of values there, frequently used "without tuple ...
41 votes
2 answers
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 ...
-1 votes
1 answer
54 views

Guess the output of a c program [closed]

I have come across a c program like this . int main() { int a,i=4; int z=5; a=--i+ --i+ --z; printf("%d %d",a,i); return 0; } What will be ...
63 votes
10 answers
35k views

What is a safe programming language?

Safe programming languages (PL) are gaining popularity. What is the formal definition of safe PL? For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to ...
0 votes
2 answers
38 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
0 answers
28 views

Formal Proofs for Rust-related Programming Languages Paper

I've done some PL-related work in Rust that requires some proofs to guarantee the resulting language is free of data races. I'd like to include such work in a paper, but I'm not sure whether I should ...
0 votes
1 answer
34 views

Results of a Program After Call By Reference Vs. Call By Value-Result

I have a question that I am trying to work through. I have a program: ...
6 votes
2 answers
269 views

Reference request: Monads, continuations, and other functional CS concepts

I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about. I could visit Wikipedia and read about these two ...
0 votes
1 answer
128 views

Explanation of a simple example of how an interaction net computes?

I have briefly looked through the links at the bottom of this page: Interaction Nets Interaction Combinators Implementation of a low-level language for interaction nets, Shinya Sato Inpla, ...
1 vote
2 answers
57 views

In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?

In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language ...
0 votes
0 answers
60 views

What is the earliest compiler in chain that was used to create what we nowadays have as a modern C compiler?

My apologies if the title is confusing. First I begin with the statement that may be wrong but what I always thought what happened. "Dennis Ritchie created C compiler which was used to create ...
2 votes
5 answers
270 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] } (...
1 vote
0 answers
28 views

A formula of the major garbage collection threshold

I'm studying the garbage collection code of Alex Aiken's COOL programming language's runtime system. (This is the language used in a relatively famous Stanford Online Compilers course) A major garbage ...
20 votes
4 answers
12k views

Are modern programming languages context-free?

Which language class are today's modern programming languages like Java, JavaScript, and Python in? It appears (?) they are not context-free and not regular languages. Are these programming languages ...
3 votes
1 answer
170 views

how to do incremental construction of the minimal model in logic programming?

I was reading a book titled "Essentials of Logic Programming.", most parts of the book are easy to understand. but now having a problem with Theme 45: incremental constructions of the ...
11 votes
3 answers
9k views

What is the difference between variables and pointers?

Whist reading an article outlining differences in OO and Functional programming I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked ...
0 votes
1 answer
63 views

How to evaluate an arbitrary mathematical expression

For Instance, if I allowed the user to pass in expressions like "35 + 2 * 5" as strings, how would I go about writing such a program? Also, what topics does this question fall under?
0 votes
2 answers
86 views

Can you verify the end of a function declaration through syntax analysis?

In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below: PROCEDURE P ; ...
1 vote
0 answers
56 views

Is it possible for Mojo language to include multiple dispatch feature of Julia through some hints or decorators mechanism? [closed]

Can the strengths of Mulitple Dispatch system of Julia language be replicated in a newly designed language like Mojo through cleverly designed mechanism? Or only Julia gets to have such a feature due ...
1 vote
2 answers
69 views

Datatypes and number representaton

I'm a freshman in computer science and I have a question that has been bugging me after my programming and electronics classes were over. My question is that in an integer datatype (assume short ...
12 votes
4 answers
7k views

Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
36 votes
7 answers
7k views

Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as: FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. ...
0 votes
0 answers
46 views

Metaprogramming language

Is there any programming language, by which I can write a code that during run time automatically generates so many other codes and furthermore those codes will be run in parallel?
2 votes
1 answer
63 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/...
0 votes
1 answer
64 views

Show that if <S1;S2,s> => * s', it is not necessarily the case that <S1,s> =>* s'

I am studying Structural Semantics for programming languages and I have come to this proof that I can not achieve. Whith these rules plus Splitting and No interference, I am trying to get a proof. I ...
5 votes
7 answers
3k views

What are the conditions necessary for a programming language to have no undefined behavior?

For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
1 vote
4 answers
3k views

Can we ever achieve Turing completeness?

I want to relate Turing completeness to the Halting Problem. As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
2 votes
3 answers
323 views

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

If I understand correctly, the first incompleteness theorem says that any "effectively axiomatized" formal system which is consistent must contain theorems which are independent of the ...
1 vote
0 answers
26 views

Resources on designing query languages

I'm looking for resources (books, papers, tutorials) on designing domain-specific query languages. I'm mostly interested in the design of syntax and grammar, rather than the implementation. Any UX-...
2 votes
1 answer
105 views

What is the closest theory to "The theory of code refactoring"?

We refactor code lots of times as developers. Metaphorically, our program space is an infinite-dimensional Rubik's cube. Things can be rearranged, preserving the code's action, so a "symmetry ...

1
2 3 4 5
20