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
7
votes
1answer
3k views

What is the difference between assignment, valuation and name binding?

I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, ...
7
votes
1answer
255 views

Tag-free garbage collection for object oriented languages

I'm looking around for a good garbage collection technique for my language and found this paper, where Benjamin Goldberg describes a garbage collection technique for strongly typed languages, which ...
7
votes
1answer
478 views

Can parameters be contra- or covariant in Python?

I've just now studied about covariance and contravariance in static languages (more specifically C#). This concept is rather clear to me, however I'm in doubt on how this applies to dynamic languages ...
7
votes
1answer
1k views

The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail

According to this description of Python's method resolution order (mro), a.k.a. C3 linearization, the algorithm can be described recursively as follows: ...
7
votes
1answer
182 views

Is it possible to prevent arithmetic errors with a dependent type system?

In a functional programming language I have functions like $$f\colon Int \times Int \times \cdots \times Int \to Int$$ which do some computation. However for certain arguments $(x_0, \dots, x_n)$ the ...
7
votes
1answer
1k views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
7
votes
1answer
602 views

What real-world computer languages cannot be described by deterministic grammars?

Are there any examples of real-world computer languages that are non-deterministic? By computer languages I include programming languages, markup languages, query languages, modeling language, ...
7
votes
1answer
1k views

reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
7
votes
1answer
259 views

Difference between row-polymorpism and bounded polymorpishm?

I recently came across this blog post by Brian McKenna explaining row polymorphism. This seemed like a wonderful idea to me, but then I realized it smells an awful lot like bounded parametric ...
7
votes
1answer
464 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 ...
7
votes
2answers
251 views

Are class methods closures?

In the wiki article about closures one can read: closure ... is a function or reference to a function together with a referencing environment At the same time in the wiki article about class ...
7
votes
0answers
131 views

Evolutionary theory applied to programming languages

I'm looking for books applying evolutionary theory to the history of programming languages. Researching the topic I have found an interesting paper - Modelling the Evolution of Programming Languages ...
7
votes
0answers
494 views

Is there any defined programming model for 'Self-Learning' NPUs?

Qualcomm is creating a Neuromorphic Processing Unit or an NPU called zeroth. IBM is also working on a brain inspired chip under Synapse program. Standford's Neurogrid might be a similar example. ...
6
votes
3answers
880 views

Where should I start to understand how computers work? [duplicate]

I am interested in how computers work but I have no idea how the concept of 0's and 1's converts to making possible for people to control a computer by programming. I would like to understand from ...
6
votes
3answers
2k views

Are the words “expression” and “term” interchangeable in programming language theory?

When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of ...
6
votes
4answers
3k views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
6
votes
2answers
476 views

What's the advantage of typed assembly?

I've seen scattered references to typed assembly in high assurance literature, but I don't really understand the advantage. If the compiler/runtime are capable of passing the types down to the CPU, ...
6
votes
4answers
1k views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
6
votes
2answers
346 views

What kinds of programming pitfalls modern languages are able to find?

I often see claims that modern functional strictly-typed languages are 'safer' than others. These statement mostly linked with type systems and their ability to explicitly express the following ...
6
votes
2answers
893 views

Don Knuth and MMIXAL vs. Chuck Moore and Forth — Algorithms and Ideal Machines — was there any cross-pollination / influence in their ideas / work?

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms? I'm interested in citations, ...
6
votes
1answer
713 views

Why product type is a dependent SUM?

It might just be a stupid question but I simply see no obvious reason why dependent sum type is a generalized form of product type. Concretely, the sigma type $\Sigma(x:S)T$ degenerates to a product ...
6
votes
2answers
299 views

What cannot be proven at compile-time about a computer program?

Is there a Turing-Complete-ish programming language without runtime errors? Like segmentation faults, memory leaks, race conditions, deadlock/livelock/starvation, etc.? With strongly typed languages, ...
6
votes
1answer
401 views

Can a functional language be homoiconic?

According to the wikipedia page on homoiconicity: In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself. I was ...
6
votes
2answers
805 views

Are syntax and semantic just 2 structures such that one is a model of the other?

The syntax of a language is a structure. The semantic of a language is a structure. The semantic of a language is a model of its syntax. And that's all ? The duality syntax/semantic is just model ...
6
votes
2answers
757 views

Proper terminology in Prolog/logical programming theory?

I have a good understanding of how to program using logic languages, but I'm currently writing up a paper describing some of my work, and I wanted to ensure that I wasn't abusing the proper ...
6
votes
1answer
142 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 \...
6
votes
2answers
382 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 ...
6
votes
1answer
200 views

How to transpile generic functions into language that do not support generics?

Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C? <...
6
votes
1answer
50 views

When would one use equational dynamics?

I'm trying to sort out in my mind the different ways of assigning semantics to a programming language. There are two main methodologies: operational semantics and denotational semantics (I asked a ...
6
votes
2answers
208 views

Eliminate non-local references from closure

For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure: ...
6
votes
5answers
1k views

Are if statements unnecessary if a program is represented as an explicit state machine?

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
6
votes
1answer
83 views

Good book on the history of programming languages?

I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, ...
6
votes
1answer
114 views

Can all regular tree types be expressed as $\mu$ types?

In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct ...
6
votes
1answer
79 views

Type system with subtyping on abstract data types?

Consider this example on binary trees in some ML-like language: ...
6
votes
1answer
442 views

Lazy concatenative functional language

Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy? I see some problems that I will explain with few examples. I will use a prefix instead of a ...
6
votes
2answers
229 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 ...
6
votes
3answers
12k views

Call by value-result vs. call by reference?

From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee ...
6
votes
3answers
5k views

What is the difference between operator and function?

We have operator and operands, function and formal arguments. Is the difference purely lexical (we use alphanumerics for funciton identifiers but identify operators with special characters, e.g. "+" ...
6
votes
1answer
2k views

Difference between “data dependence graph”, “data dependency graph”, and “data flow graph”

Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not. To make things even more complicated, a "...
6
votes
1answer
165 views

How are data types related to information theory?

I was just reading from wikipedia the following about information: From the stance of information theory, information is taken as a sequence of symbols from an alphabet, say an input alphabet χ, ...
6
votes
1answer
50 views

Dynamic changes to classes or context activation — how to treat existing objects in a consistent way?

I am looking for references and papers on the following topic. In general, some programming languages allow dynamic changes to classes. As an example, a new instance variable ‘weight’ can be added to ...
6
votes
2answers
93 views

Why is the type ∀t.t un-inhabited in System F?

How do you prove that there exists no term with the type $\forall t. t$ in System F? I tried searching through Pierce's TAPL and Reynold's ToPL, but could not find anything. I suspect that the proof ...
6
votes
1answer
247 views

Which object-oriented programming language is the closest to the untyped sigma-calculus?

I'm wondering which of the dynamic object-oriented (or prototype-oriented) languages (like JavaScript, Ruby, Python, etc.) can be considered as the closest to Abadi and Cardelli's untyped sigma ...
6
votes
2answers
218 views

What does Harper mean by “class”?

I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's Types and Programming Languages and Harper's Practical Foundations for Programming ...
6
votes
1answer
1k views

Is there a way of objectively measuring the efficiency or quality of software or code design?

I've been thinking about ways of measuring code, and, quite frankly, I can't think of truly objective, semi-universal ways of evaluating the quality or "strength" of code to say, "Yes, this is better ...
6
votes
2answers
109 views

Formally describing a sensor network language

I have a language for sensor networks (generates C code) and I want to define the formal semantics of it. The language has this form: ...
6
votes
1answer
101 views

Can Tree Transducers Self-Interpret?

Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design ...
6
votes
1answer
527 views

Inductive vs. recursive definition

When should I call a definition recursive and when should I call it inductive? I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like ...
6
votes
1answer
171 views

Efficient subtype testing

Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to ...
6
votes
1answer
134 views

Error in solution in Types and Programming Languages?

I'm reading Types and Programming Languages and trying to understand the solution to exercise 5.2.4 on untyped lambda calculus / Church numerals: Define a term for raising one number to the power ...

1 2 3
4
5
18