{"entities":{"Q1090671":{"pageid":1101423,"ns":120,"title":"Item:Q1090671","lastrevid":66430848,"modified":"2026-04-12T10:02:14Z","type":"item","id":"Q1090671","labels":{"en":{"language":"en","value":"Variable abstraction in O(n log n) space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4008364"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$04D80F75-15EB-4447-8F61-DD459D6BA416","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e38492530c578734cf8088c28b51917b7d756816","datavalue":{"value":{"text":"Variable abstraction in O(n log n) space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090671$3F6E422E-CAFF-4B2F-BC30-66E5CC905390","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2ff30469f6f5ab44a2797e33f186c36314c3499","datavalue":{"value":"0622.03011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$302866F0-17CB-4CA8-BF4D-1EB651C63B62","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfd3f7ccb0c4d2afb82abb38ea42995831d73219","datavalue":{"value":"10.1016/0020-0190(87)90161-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$3C8B3185-7130-47E6-8EDD-1ECB489C3F2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8a0f83b3a96f90d2c59dc38ce677f7e865be720","datavalue":{"value":{"entity-type":"item","numeric-id":1090669,"id":"Q1090669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$7C2EE325-0D27-4861-88C8-3F9B1A681A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca26fc215e519c9f5e5fec9062509fdc8c55ca7f","datavalue":{"value":{"entity-type":"item","numeric-id":1090670,"id":"Q1090670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$F39178A3-1A3B-4958-950C-5B3B2C60D9DC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$F636B9DA-9E9D-4FFB-85FC-509B59E731F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1090671$F4C2ED4A-7131-431A-B2FA-4922C59148AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc609336543072948dfc88515d80527d0eab99c1","datavalue":{"value":"Turner's translation of lambda calculus into combinators in known to cause in the worst case a quadratic expansion in the size of an expression. This paper defines a more systematic translation into a notation of ''director strings'' closely related to Turner's combinators. The notation admits an obvious compaction by run-length encoding, which reduces the size of the translation of a lambda expression of size n to O(n log n). The time to make the translation is still quadratic in the worst case, but by combining director strings with supercombinators this can also be reduced to O(n log n).    There is a simple linear translation of a director string expression into Turner's combinators, and hence into any other set of combinators sufficiently expressive to represent all lambda expressions. Up to a constant factor, evaluation of director string expressions takes the same time as the corresponding Turner combinator expressions. In practical implementations of functional languages, director strings have been found to give a significant, though not dramatic, improvement in execution speed.    The work reported in this paper predates, and is independent of, \\textit{K. Noshita}'s paper proving some of the same results [ibid. 20, 71-74 (1985; Zbl 0558.68028)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$011CBA60-7946-41A4-BDD3-54E4BA9275F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25aa969dcca62ee94c95b2a54e4102ee8a17d130","datavalue":{"value":"03B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$69B863C7-F789-4E45-9DAB-E343841FC7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8e3f40e3cc87753c4e0b7d7ce4bdc00805f626f","datavalue":{"value":"68N01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$C3326A00-4A57-4699-B020-35F2C32F354A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$A59882E1-DFEE-4032-989E-8DCA9F45B848","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d901fe402e9a0111dfa3e55af1728cfb3cfdacc","datavalue":{"value":"4008364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090671$EC72E62D-2A27-40C1-A7EB-C334C1718D09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00b76a2e54f8798fe172effecd557ced03e2f904","datavalue":{"value":"functional programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$61F450DF-E183-4423-A5B4-86B72E01FB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a2e0a24d33cc55a1243bda19886e6ac508bc07e","datavalue":{"value":"variable abstraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$46B59DD5-12FA-4D23-909D-122C2A0D1CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$C284D1B9-ACDA-4FB1-BFBE-E957D64492AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b876698d821b50cd7ba02ddb5424ed80f1905d8","datavalue":{"value":"lambda calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$88DE1729-0338-42EB-9C59-E0008C485069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48fd5971af07f8c5b531cd8ce79c87b442ade69","datavalue":{"value":"director strings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$1DBE6858-0AF3-4D97-833A-2A485E9E0DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"474e6938b23b686e446fa91b6c396e157bfa6078","datavalue":{"value":"Turner combinator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090671$EFA6DF00-33D7-4C35-9EB3-E2E1A5ED5CC9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$A431CA8B-4183-4DCF-91AF-4456D9D1DFEC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e6f45bf079337a737cf685a4a28bc5114e50b2","datavalue":{"value":{"entity-type":"item","numeric-id":1837177,"id":"Q1837177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$F652E687-34DC-4120-8832-66BDD47FC7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3bb8be7de89f20d22f4ee8d1d86958f7a15e915","datavalue":{"value":{"entity-type":"item","numeric-id":3823125,"id":"Q3823125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$9B5EB594-C7A8-485E-8296-26F7BB1ABFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e0ad154213125ffb5f142ff784e55adc020e567","datavalue":{"value":{"entity-type":"item","numeric-id":802308,"id":"Q802308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$87FFD236-CBD6-47D5-8B5F-6A567F7277F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8470718175ec6109a436628221c5cffb3ba70aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4167525,"id":"Q4167525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$2BCBF393-BE26-48C5-94F1-8F09450002F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10546887ee0615eb07bca2e1dc0f41e60f6caeff","datavalue":{"value":{"entity-type":"item","numeric-id":4194932,"id":"Q4194932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090671$24318A4A-A7C7-4DC0-BEC9-93378A24BEB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"178b5262ae904dc83854f235fd94da878df309ff","datavalue":{"value":{"entity-type":"item","numeric-id":3823125,"id":"Q3823125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8b66df05e816df590a181300730a5d6ab6268b","datavalue":{"value":{"amount":"+0.8356501460075378","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090671$D9C59A30-B9AF-4334-84BC-EC76C990BA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e8987db3debd5454034e0bf186425da87d3e5f2","datavalue":{"value":{"entity-type":"item","numeric-id":802308,"id":"Q802308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a47de618085159668264a8cadbbcfba4b9df9ef7","datavalue":{"value":{"amount":"+0.8332456350326538","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090671$B107188C-0D98-4B0F-B73D-8B47A52BEB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7bd8ab4047404d618bb2309f847cff17a77eac7","datavalue":{"value":{"entity-type":"item","numeric-id":1208420,"id":"Q1208420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66106ae5c07608a51b06f29c708077344a5e0ee0","datavalue":{"value":{"amount":"+0.789113461971283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090671$5C6358FD-8530-4041-8157-7992E2283025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"794156936e4e9887ce952d3246ae8acf205dd964","datavalue":{"value":{"entity-type":"item","numeric-id":3683527,"id":"Q3683527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66106ae5c07608a51b06f29c708077344a5e0ee0","datavalue":{"value":{"amount":"+0.789113461971283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090671$8F867515-B83E-42C1-A64E-E59C321D6477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db743f567637b48771682e15b3dc731517fefcc8","datavalue":{"value":{"entity-type":"item","numeric-id":3775517,"id":"Q3775517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77dcfc4d83e4cea410b6844cbf0d06ed39e65111","datavalue":{"value":{"amount":"+0.7880371809005737","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1090671$120712C6-EB71-478D-AAC5-CBD23B7B5DE1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Variable abstraction in O(n log n) space","badges":[]}}}}}