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
18
votes
6answers
7k views

Why do more powerful programming languages tend to have slower implementations?

I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. ...
18
votes
2answers
5k views

Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness. However, pure Prolog is incapable of expressing list intersection....
18
votes
4answers
2k views

Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?

I am new to programming language theory. I was watching some online lectures in which the instructor claimed that a function with polymorphic type ...
18
votes
3answers
927 views

Problems Implementing Closures in Non-functional Settings

In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine): In computer science, a closure (...) is a function together with a referencing ...
18
votes
3answers
3k views

How to make a language homoiconic

According to this article the following line of Lisp code prints "Hello world" to standard output. (format t "hello, world") Lisp, which is a homoiconic language,...
18
votes
3answers
541 views

Is there a theory of exception hierarchies?

I'm familiar with a dozen of programming languages which have exceptions in some way, yet I came to witness two "pathological" tendencies. There doesn't seem to be a common pattern or ...
16
votes
8answers
23k views

What problems of procedural programming does OOP solve in practice?

I have studied the book "C++ Demystified". Now I have started to read "Object-Oriented Programming in Turbo C++ first edition (1st edition)" by Robert Lafore. I do not have any knowledge of ...
16
votes
4answers
807 views

Can a program language be malleable enough to allow programs to extend language semantics

With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically ...
16
votes
2answers
1k views

Scott-continuous functions: an alternative definition

I'm really struggling with this property: Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup_{x\in D} x)=\bigcup_{x \in ...
15
votes
5answers
3k views

What makes a language “optimized” for a specific task?

Often there are programming languages that are specialized for specific tasks. Some programming languages are excellent at array arithmetic (such as matrices and the use of multidimensional arrays), ...
15
votes
1answer
679 views

Type inference with product types

I’m working on a compiler for a concatenative language and would like to add type inference support. I understand Hindley–Milner, but I’ve been learning the type theory as I go, so I’m unsure of how ...
14
votes
7answers
26k views

Why do negative array indices make sense?

I have came across a weird experience in C programming. Consider this code: ...
14
votes
3answers
4k views

Which research languages have a stronger typesystem than Haskell and why?

Here I read that: Haskell definitely does not have the most advanced type system (not even close if you count research languages) but out of all languages that are actually used in production ...
14
votes
2answers
637 views

Reference request: Category theory as it applies to type systems

I keep hearing about how one must learn category theory to truly understand programming language theory. So far, I've learned a good deal of PL without ever stepping foot into the realm of categories. ...
14
votes
2answers
326 views

Are there peer-reviewed papers studying the pros and cons of functional programming?

Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in ...
13
votes
4answers
4k views

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars. I understand why languages like $\{ww \mid w \in A^*\}$ $\{a^n b^n c^n \mid n\in\mathbb{N}\}$ are not context free, but what I'd like ...
13
votes
2answers
1k views

Lambda calculus: difference between contexts and evaluation contexts

Firstly, I'd like to say that my text below may contain errors, so feel free to point out any mistakes in my formulation of the question. Consider an untyped lambda calculus with booleans and if-...
13
votes
6answers
43k views

Definition of the state of an object in OOP

I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find ...
13
votes
3answers
3k views

Why is using a lexer/parser on binary data so wrong?

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
13
votes
3answers
444 views

What's the difference between a calculus and a programming language?

I think I'm pretty confused about what's called a calculus and what's called a programming language. I tend to think, and might have been told, that a calculus is a formal system for reasoning about ...
13
votes
3answers
1k views

Relation between Russellian type theory and type systems

I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have ...
13
votes
0answers
199 views

Why do we have to forbid non-conforming lower and upper type bounds?

(it's a repost of my unanswered question from scala-user@googlegroups.com about Scala) In the Scala Language Specification, §4.4 Type Parameters, there is a requirement: The most general form of a ...
12
votes
3answers
4k views

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks? [closed]

Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very ...
12
votes
1answer
236 views

Is the IO monad technically incorrect?

On the haskell wiki there is the following example of conditional usage of the IO monad (see here). ...
12
votes
1answer
961 views

Why aren't we researching more towards compile time guarantees?

I love all that is compile time and I love the idea that once you compile a program a lot of guarantees are made about it's execution. Generally speaking a static type system (Haskell, C++, ...) seems ...
11
votes
3answers
850 views

Polymorphism and Inductive datatypes

I'm curious. I've been working on this datatype in OCaml: ...
11
votes
4answers
1k views

Does it make sense to have both the concept of 'null' and 'Maybe'?

While creating a client for a web API in C#, I ran into a problem regarding null as a value where it would represent two different things: nothing, e.g. a ...
11
votes
2answers
3k views

Why is least fixed point (lfp) important in program analysis

I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on ...
11
votes
4answers
2k views

Why do we have to trade abstraction for speed?

Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier ...
11
votes
3answers
6k views

What is the difference between Abstract Data Types and objects?

An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying Objects behave like a characteristic function over the values of a type, rather than as an algebra. ...
11
votes
4answers
437 views

Can you specify a programming language without implementation?

Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to ...
11
votes
2answers
2k views

Is there an equivalent of lambda calculus for object oriented languages? [duplicate]

Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object ...
11
votes
2answers
5k 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 ...
11
votes
1answer
593 views

Inferring refinement types

At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested let expressions, like so: <...
11
votes
1answer
180 views

Programming language semantics prototyping tool

Is there any tool for prototyping a programming language semantics and type system and that also allows for some sort of model checking of standard properties, like type soundness? I'm asking this, ...
11
votes
1answer
495 views

Constraint-based Type Inference with Algebraic Data

I am working on an expression based language of ML genealogy, so it naturally needs type inference >:) Now, I am trying to extend a constraint-based solution to the problem of inferring types, based ...
10
votes
8answers
669 views

Corresponding noun for “side-effect-free”?

For functions or computations we have terms like: Deterministic – Determinism Pure – Purity Now what is the correct corresponding noun for side-effect-free? "Side-effect freeness"? "...
10
votes
3answers
623 views

anonymous lambda functions (functional programming)

What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language? In my simple terms, when I am programming in scheme/lisp I would ...
10
votes
4answers
1k 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 ...
10
votes
2answers
8k views

Compile a programming language with itself

I'm a computer science student. I want to create my own programming language (A basic language with few instructions). I know how to do a syntactic analyser, I already did it in Perl. In an article, ...
10
votes
2answers
838 views

Which fixpoint is Haskell list type?

Let's say that lists are defined as List a = Nil | Cons a (List a) Then, in Haskell is List x the greatest or least fixpoint? ...
10
votes
2answers
1k views

What makes lambda calculus relevant to study?

I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based ...
10
votes
1answer
1k views

Types as first class Citizen

Coming from a C++ background I don't understand why one needs types / type expressions as first class citizen? The only language I know that supports this feature is Aldor. Does anybody have some ...
10
votes
1answer
533 views

A programming language that can only implement computable bijective functions?

Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?
10
votes
1answer
561 views

Alternatives to Defunctionalization

Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order ...
10
votes
1answer
480 views

When used as call stack, do garbage-free spaghetti stacks form a DAG?

I'm looking into implementation techniques for programming languages, and recently came across spaghetti stacks, which are supposedly a good fit for a continuation passing style model (given their use ...
10
votes
0answers
132 views

Denotational semantics of object-oriented languages

I am interested in denotational semantics of object oriented languages. Namely, what are the common/typical denotations of objects used in the literature? Is this an interesting topic these days? The ...
9
votes
3answers
931 views

Why does the state remain unchanged in the small-step operational semantics of a while loop?

Usually I see that in the structural operational semantics representation for the while loop, the program state don't change: $(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> ...
9
votes
4answers
9k views

A faster, leaner JavaScript for scientific computing: what features should I keep?

Here I'm really interested in lowering barriers to mathematical education. Target: I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-...
9
votes
3answers
2k views

Why are strings immutable in some languages?

String is an immutable class in Java. An immutable class is simply a class whose instances cannot be modified. Why does the Java programming language choose to make objects of class String immutable?

1
2
3 4 5
18