Stack-oriented programming

Stack-oriented programming is a programming paradigm that relies on a stack (or multiple stacks) to manipulate data and/or pass parameters. Several programming languages fit this description, notably Forth, RPL, and PostScript. Stack-oriented programming languages operate on one or more stacks, each of which may serve a different purpose. Programming constructs in other programming languages need to be modified for use in a stack-oriented system.[1] Most stack-oriented languages operate in postfix or Reverse Polish notation. Any arguments or parameters for a command are stated before that command. For example, postfix notation would be written 2, 3, multiply instead of multiply, 2, 3 (prefix or Polish notation), or 2 multiply 3 (infix notation). The programming languages Forth, Factor, RPL, PostScript, BibTeX style design language[2] and many assembly languages fit this paradigm.

Stack-based algorithms manipulate data by popping data from the stack and pushing data to the stack. Stack manipulation operators govern how the stack manipulates data. To emphasize the effect of a statement, a comment is often used showing the top of the stack before and after the statement. This is known as the stack effect diagram. PostScript uses separate stacks for additional purposes, including variables, dictionaries, procedures, some typical procedures, and control flow statements. Analysis of the language model allows expressions and programs to be interpreted simply.

Stack-based algorithms

PostScript is an example of a postfix stack-based language. An expression example in this language is 2 3 mul('mul' being the command for the multiplication operation). Calculating the expression involves understanding how stack orientation works.

Stack orientation can be presented as the following conveyor belt analogy. at the end of a conveyor belt (the input), plates marked 2, 3, and mul are placed in sequence. The plate at the end of the conveyor (2) can be taken, however other plates cannot be accessed until the plate at the end is removed. The plates can only be stored in a stack, and can only be added or removed from atop the stack, not from the middle or bottom. Blank plates (and a marker) can be supplied and plates can be permanently discarded.

Take plate 2 and put it on the stack, then take plate 3 and put it on the stack. Next, take the mul plate. This is an instruction to perform. Then, take the top two plates off the stack, multiply their labels (2 and 3), and write the result (6) on a new plate. Discard the two old plates (2 and 3) and the plate mul, and put the new plate on the stack. With no more plates remaining on the conveyor, the result of the calculation (6) is shown on the plate atop the stack.

This is a very simple calculation. What if a more complex calculation is needed, such as (2 + 3) × 11 + 1? If it is first written in postfix form, that is, 2 3 add 11 mul 1 add, the calculation can be performed in exactly the same manner and achieve the correct result. The steps of the calculation are shown in the table below. Each column shows an input element (the plate at the end of the conveyor), and the contents of the stack after processing that input.

Input 2 3 add 11 mul 1 add
Stack 2 3
2
5 11
5
55 1
55
56

After processing all the input, the stack contains 56, which is the answer.

From this, the following can be concluded: a stack-based programming language has only one way to handle data, by taking one piece of data from atop the stack, termed popping, and putting data back atop the stack, termed pushing. Any expression that can be written conventionally, or in another programming language, can be written in postfix (or prefix) form and thus be amenable to being interpreted by a stack-oriented language.

Stack manipulation

Since the stack is the key means to manipulate data in a stack-oriented language, such languages often provide some sort of stack manipulation operators. Commonly provided are dup, to duplicate the element atop the stack, exch (or swap), to exchange elements atop the stack (the first becomes second and the second becomes first), roll, to cyclically permute elements in the stack or on part of the stack, pop (or drop), to discard the element atop the stack (push is implicit), and others. These become key in studying procedures.

Stack effect diagrams

As an aid to understanding the effect of the statement, a short comment is used showing the top of the stack before and after the statement. The top of the stack is rightmost if there are multiple items. This notation is commonly used in the Forth language, where comments are enclosed in parentheses.

( before -- after )

For example, the basic Forth stack operators are described:

dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

The fib function below is described:

fib  ( n -- n' )

It is equivalent to preconditions and postconditions in Hoare logic. Both comments may also be referenced as assertions, though not necessarily in the context of Stack-based languages.

PostScript stacks

PostScript and some other stack languages have other separate stacks for other purposes.

Variables and dictionaries

The evaluation of different expressions has already been analysed. The implementation of variables is important for any programming language, but for stack-oriented languages, it is of special concern, as there is only one way to interact with data.

The way variables are implemented in stack-oriented languages such as PostScript usually involves a separate, specialized stack which holds dictionaries of key-value pairs. To create a variable, a key (the variable name) must be created first, with which a value is then associated. In PostScript, a name data object is prefixed with a /, so /x is a name data object which can be associated with, for example, the number 42. The define command is def, so

/x 42 def

associates with the name x with the number 42 in the dictionary atop the stack. A difference exists between /x and x – the former is a data object representing a name, and x stands for what is defined under /x.

Procedures

A procedure in a stack-based programming language is treated as a data object in its own right. In PostScript, procedures are denoted between { and }.

For example, in PostScript syntax,

{ dup mul }

represents an anonymous procedure to duplicate what is on the top of the stack and then multiply the result – a squaring procedure.

Since procedures are treated as simple data objects, names with procedures can be defined. When they are retrieved, they are executed directly.

Dictionaries provide a means of controlling scoping, as well as storing definitions.

Since data objects are stored in the top-most dictionary, an unexpected ability arises naturally: when looking up a definition from a dictionary, the topmost dictionary is checked, then the next, and so on. If a procedure is defined that has the same name as another already defined in a different dictionary, the local one will be called.

Anatomy of some typical procedures

Procedures often take arguments. They are handled by the procedure in a very specific way, different from that of other programming languages.

To examine a Fibonacci number program in PostScript:

  /fib
  {
     dup dup 1 eq exch 0 eq or not
     {
        dup 1 sub fib
        exch 2 sub fib
        add
     } if
  } def

A recursive definition is used on the stack. The Fibonacci number function takes one argument. First, it is tested for being 1 or 0.

Decomposing each of the program's key steps, reflecting the stack, assuming calculation of fib(4) :

                stack: 4
   dup
                stack: 4 4
   dup
                stack: 4 4 4
   1 eq
                stack: 4 4 false
   exch
                stack: 4 false 4
   0 eq
                stack: 4 false false
   or
                stack: 4 false
   not
                stack: 4 true

Since the expression evaluates to true, the inner procedure is evaluated.

                stack: 4
   dup
                stack: 4 4
   1 sub
                stack: 4 3
   fib
(recursive call here)
                stack: 4 F(3)
   exch
                stack: F(3) 4
   2 sub
                stack: F(3) 2
   fib
(recursive call here)
                stack: F(3) F(2)
   add
                stack: F(3)+F(2)

which is the expected result.

This procedure does not use named variables, purely the stack. Named variables can be created by using the /a exch def construct. For example, {/n exch def n n mul}

is a squaring procedure with a named variable n. Assuming that /sq {/n exch def n n mul} def and 3 sq is called, the procedure sq is analysed in the following way:

               stack: 3 /n
   exch
               stack: /n 3
   def
               stack: empty (it has been defined)
   n
               stack: 3
   n
               stack: 3 3
   mul
               stack: 9

which is the expected result.

Control and flow

As there exist anonymous procedures, flow control can arise naturally. Three pieces of data are required for an if-then-else statement: a condition, a procedure to be done if the condition is true, and one to be done if the condition is false. In PostScript for example,

 2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse

performs the near equivalent in C:

 if (2 > 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }

Looping and other constructs are similar.

Analysis of the language model

The simple model provided in a stack-oriented language allows expressions and programs to be interpreted simply and theoretically evaluated much faster, since no syntax analysis needs to be done but lexical analysis. The way such programs are written facilitates being interpreted by machines, which is why PostScript suits printers well for its use. However, the slightly artificial way of writing PostScript programs can form an initial barrier to understanding stack-oriented languages such as PostScript.

While the ability to shadow by overriding inbuilt and other definitions can make programs hard to debug, and irresponsible use of this feature can cause unpredictable behaviour, it can simplify some functions greatly. For example, in PostScript use, the show page operator can be overridden with a custom one that applies a certain style to the page, instead of having to define a custom operator or repeat code to generate the style.

See also

References

  1. ^ Luerweg, T. (2015). Stack based programming paradigms. Concepts of Programming Languages–CoPL’15, 33.
  2. ^ Oren Patashnik, Designing BibTeX styles (PDF)[dead link]

Read other articles:

スーパーニュウニュウ 左から大将、ふるやいなや(2018年10月)メンバー 大将ふるやいなや結成年 2012年事務所 マセキ芸能社活動時期 2012年10月 -出身 ヒューマンアカデミー(大将)ワタナベコメディスクール11期(ふるやいなや)旧コンビ名 大将ラインズマンプラチナポケットユニバーサルボンボンふるやいなやねぇ、ねえさん。どりーみーぱんだいくかいなかあげもの

 

 

إدارة في بوليفيامعلومات عامةصنف فرعي من التقسيم الإداري في بوليفياdepartamento (en) المستوى الأول من التقسيم الإداري البلد بوليفيا الكمية 9 تعديل - تعديل مصدري - تعديل ويكي بيانات إدارات بوليفيا تنقسم بوليفيا إلى تسعة إدارات هي كالتالي (بالأسبانية: departamentos). وهذه الإدارات هي وحدة ال

 

 

Sungai Orontes di Turki Orontes (/ɔːˈrɒntiːz/; dari Yunani Kuno Ὀρόντης, Oróntēs) atau Asi (Arab: العاصي, translit. al-‘Āṣī, IPA: [alˈʕaːsˤiː]; Turki: Asi) adalah sebuah sungai yang melintasi Lebanon, Suriah dan Turki. Pada masa kuno, sungai ini merupakan sungai yang penting di Levant dan disebut Draco, Typhon dan Axius. Sejarah Sejak lama, Orontes telah dijadikan penanda perbatasan. Bangsa Mesir menggunakannya sebagai penanda batas utara Amur...

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (mars 2009). Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes. Plan de partage de 1947. Le 29 novembre 1947, le plan...

 

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يناير 2022) هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. ...

 

 

Protests against Reddit's API-access prices An image posted on many subreddits as protest during the blackout.[1] In April 2023, the discussion and news aggregation website Reddit announced its intentions to charge for its application programming interface (API), a feature which had been free since 2008, causing a dispute. The move forced multiple third-party applications to shut down and threatened accessibility applications and moderation tools. On May 31, Apollo developer Christian...

FoxcatcherPoster film FoxcatcherSutradara Bennett Miller Produser Megan Ellison Bennett Miller Jon Kilik Anthony Bregman Ditulis oleh E. Max Frye Dan Futterman PemeranSteve CarellChanning TatumMark RuffaloSienna MillerVanessa RedgravePenata musikRob SimonsenWest Dylan ThordsonSinematograferGreig FraserPenyuntingStuart LevyConor O'NeillJay CassidyPerusahaanproduksiAnnapurna PicturesLikely StoryDistributorSony Pictures ClassicsTanggal rilis 19 Mei 2014 (2014-05-19) (Festival Film...

 

 

Ridge or wall to hold back water For other uses, see Levee (disambiguation). Components of a levee: Design high water level (HWL)Low water channelFlood channelRiverside slopeRiverside banquetteLevee crownLandside slopeLandside banquetteBermLow water revetmentRiverside landLeveeProtected lowlandRiver zone The side of a levee in Sacramento, California A levee (/ˈlɛvi/),[1][2] dike (American English), dyke (Commonwealth English), embankment, floodbank, or stop bank is a structu...

 

 

Страва з молюсками та креветками Морепродуќти, дари́ моря — різноманітні їстівні морські тварини, такі, як ракоподібні (включаючи креветок, крабів, лангустів та омарів), молюски, голкошкірі тощо. Зміст 1 Загальний опис 2 Основні різновиди 3 Склад: холестерин, вітаміни, м...

The concept of entropy developed in response to the observation that a certain amount of functional energy released from combustion reactions is always lost to dissipation or friction and is thus not transformed into useful work. Early heat-powered engines such as Thomas Savery's (1698), the Newcomen engine (1712) and the Cugnot steam tricycle (1769) were inefficient, converting less than two percent of the input energy into useful work output; a great deal of useful energy was dissipated or ...

 

 

John Jenkins (Gwili) For other people with the same name, see John Jenkins (disambiguation). Welsh poet and theologian, 1872–1936 John Jenkins (8 October 1872 – 16 May 1936)[1] was a Welsh poet and theologian. Known by his bardic name of Gwili, he served as Archdruid of the National Eisteddfod of Wales from 1932 to 1936. Early life and education Gwili was born at Hendy in Carmarthenshire, the fifth child of John Jenkins, a metal refiner, and his wife Elizabeth.[1] His pare...

 

 

State park in New Haven County, Connecticut Southford Falls State ParkEight Mile BrookLocation in ConnecticutShow map of ConnecticutSouthford Falls State Park (the United States)Show map of the United StatesLocationOxford & Southbury, Connecticut, United StatesCoordinates41°27′15″N 73°09′42″W / 41.45417°N 73.16167°W / 41.45417; -73.16167[1]Area126 acres (51 ha)[2]Elevation561 ft (171 m)[1]DesignationConnecticut sta...

This article may contain an excessive number of citations. Please help remove low-quality or irrelevant citations. (October 2021) (Learn how and when to remove this template message) A75 road, eastbound near Kinmount Ackergill Tower Airth Castle Ardrossan Castle Dryburgh Abbey Hotel Edinburgh Castle Edinburgh Vaults Fyvie Castle Glamis Castle Holyrood Palace Mary King's Close RAF Montrose, 1917 Stirling Castle There are a number of reportedly haunted locations in Scotland. List A A fifteen-mi...

 

 

Voce principale: The Best FIFA Football Awards. I The Best FIFA Football Awards 2016, presentati dall'attrice e modella Eva Longoria, si sono svolti il 9 gennaio 2017 a Zurigo, in Svizzera.[1] Il riconoscimento nasce con lo scopo di dare continuità al FIFA World Player of the Year, che era stato fuso con il Pallone d'oro di France Football nel 2010 dando vita al Pallone d'oro FIFA, assegnato congiuntamente per sei anni.[2][3] I criteri di selezione per i giocatori (ma...

 

 

1998 single by ZardUnmei no Roulette MawashiteSingle by Zardfrom the album Eien ReleasedSeptember 17, 1998RecordedMay 1998-August 1998StudioB.Gram-RECORDSGenre J-pop R&B pop rock alternative rock LabelB-Gram RecordsSongwriter(s)Izumi Sakai, Seiichiro Kuribayashi, Aika OhnoProducer(s)Daiko Nagato, ZARD,Zard singles chronology 'Iki mo Dekinai' (1998) Unmei no Roulette Mawashite (1998) 'Atarashii Door ~Fuyu no Himawari~' (1998) Unmei no Roulette Mawashite (運命のルーレット廻して, ...

City in Pennsylvania, United States City in Pennsylvania, United StatesHazletonCityDowntown Hazleton in 2004Nickname(s): The Mountain City, Mob City, The Power CityLocation of Hazleton in Luzerne County, Pennsylvania.HazletonLocation within the U.S. state of PennsylvaniaShow map of PennsylvaniaHazletonHazleton (the United States)Show map of the United StatesCoordinates: 40°57′32″N 75°58′28″W / 40.95889°N 75.97444°W / 40.95889; -75.97444CountryUnited St...

 

 

Telephone signaling protocol Panel Call Indicator, or PCI, is a form of signalling used between two telephone offices. It was also originally called Relay Call Indicator (RCI). Originally designed along with the panel type telephone office, PCI was intended to allow subscribers in fully automated exchanges to dial numbers in manual offices the same way they dialed numbers in their own exchange. For PCI to achieve its purpose, the panel office sent the requested number to the manual office, wh...

 

 

Japanese professional wrestler (born 1970) Masao InoueBorn (1970-03-06) March 6, 1970 (age 53)Chūō, Yamanashi PrefectureProfessional wrestling careerRing name(s)Chunen Mogura Otoko[1]Masao InoueMogura[1]Naomichi Marufuji?[2][unreliable source?]Billed height1.80 m (5 ft 11 in)Billed weight106 kg (234 lb)DebutApril 4, 1991 Masao Inoue (井上雅央, Inoue Masao, born March 6, 1970 in Chūō, Yamanashi Prefecture, Japan) is a Japane...

إحداثيات مسار الشمس تتركز على الأرض كما تشاهد من خارج الكرة السماوية. يقاس الطول البروجي (الأحمر) على طول دائرة البروج من نقطة الاعتدال الربيعي. ويقاس العرض البروجي (الأصفر) عموديا على دائرة البروج. نظام الإحداثيات الكسوفية أو نظام الإحداثيات البروجية (بالإنجليزية: Ecliptic coord...

 

 

الصفحه دى يتيمه, حاول تضيفلها مقالات متعلقه لينكات فى صفحات تانيه متعلقه بيها. ادڤارد كورنيليوس اوپداهل (بالنرويجى الbokmål: Edvard Opdahl)[1]  معلومات شخصيه الميلاد 22 يوليه 1844[2]  الوفاة 17 اغسطس 1934 (90 سنة)[3]  مواطنه النرويج  الحياه العمليه المهنه سياسى[2]  ...

 

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!